New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

`simplify()` returns `RangeError: Maximum call stack size exceeded` for certain expressions containing `n` #948

Closed
tanman- opened this Issue Sep 28, 2017 · 19 comments

Comments

Projects
None yet
4 participants
@tanman-

tanman- commented Sep 28, 2017

Not OK

The n mixed with - or / seems to be an issue.

math.simplify('2n - 1').toString();
math.simplify('16n - 1').toString();
math.simplify('16n / 1').toString();
math.simplify('8 / 5n').toString();
math.simplify('8n - 4n').toString();

OK

math.simplify('n - 1').toString();
math.simplify('1n - 1').toString();
math.simplify('2n + 1').toString();
math.simplify('2z - 1').toString();
math.simplify('2n -- 1').toString();

Workaround

math.simplify('2n - 1',[]).toString();

[]: no rules applied.

@tanman- tanman- changed the title from `simplify()` returns `RangeError: Maximum call stack size exceeded` for certain expressions to `simplify()` returns `RangeError: Maximum call stack size exceeded` for certain expressions containing `n` Sep 28, 2017

@firepick1 firepick1 self-assigned this Sep 28, 2017

@firepick1 firepick1 added the bug label Sep 28, 2017

@firepick1

This comment has been minimized.

Collaborator

firepick1 commented Sep 28, 2017

@josdejong I think I need help here. The issue seems to be triggered by simplify.js@356, which is transforming a tree. The tricky bit is that the tree is the pattern tree that is used to match expressions. Specifically, the pattern being replaced is "n", which is the pattern for "node". What appears to happen is that the transformation is recurring on the the symbol "n" which is part of the input expression. Essentially, we appear to have a conflict between a placeholder "n" and its replacement, which contains "n". Ugh. Is the original simplify author available to assist here?

@josdejong

This comment has been minimized.

Owner

josdejong commented Sep 30, 2017

Essentially, we appear to have a conflict between a placeholder "n" and its replacement, which contains "n". Ugh. Is the original simplify author available to assist here?

ha ha, yes @ericman314 created the first implementation and @tetslee did some refactoring and improvements. Apparently none of us thought about the possibility that there could be a conflict between the variables in the rules and variables in the expression itself 😳.

I think to solve this we can do something like:

  1. before processing an expression, extract all used symbols (create a "blacklist"). Before using rules, check whether any of the placeholders is a name used in the expression to be processed (one from the "blacklist"), and if so, rename this placeholder to an unused name, so there will be no conflicts
  2. Or the other way around: before processing, check whether the expression contains a variable name that's also used as placeholder in one of the rules. If so, replace it with a temporary, unique name, and after processing, replace it again with the original name.

I'm not sure but I can imagine that option (2) is more efficient since its less work to transform a large set of rules than to transform one expression.

@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Sep 30, 2017

I'll try to help, although It's been a long time since I worked on simplify. If I remember right there shouldn't be a direct string comparison between a pattern and an input expression. The n in a pattern should match a node, not a literal 'n'. Or at least that's the way it should be. Maybe this is a stupid question, but does the bug still occur with another symbol in the input expression, like x?

@josdejong

This comment has been minimized.

Owner

josdejong commented Sep 30, 2017

there shouldn't be a direct string comparison between a pattern and an input expression

that sounds even better than my suggestions...

The issue does not occur with symbols that are not used in the rules:

math.simplify('2x - 1').toString();  // OK
math.simplify('2n - 1').toString();  // NOT OK (infinite loop)
math.simplify('2n1 - 1').toString(); // NOT OK (returns 1)
@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Sep 30, 2017

@josdejong

This comment has been minimized.

Owner

josdejong commented Sep 30, 2017

Thanks Eric 👍

@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Oct 1, 2017

I found the source of the bug, it does indeed occur on line 356 and has existed since simplify was first written.

My test input was 1 - n. At the point where the bug occurs, the expression being simplified is (-(1 * n)) + 1 and the rule being applied is n+-n1 -> n-n1. A match between the expression and the rule is found, and the placeholders are correctly assigned as n = 1 and n1 = 1 * n. To generate the simplified expression, the right-hand-side n-n1 is transformed by traversing the tree top-down, replacing n with 1 and n1 with 1 * n:

n - n1
1 - n1        (Replaced n with 1)
1 - (1 * n)   (Replaced n1 with 1 * n)
1 - (1 * 1)   (Replaced n with 1)

By the time we get to step 3, the transform happily continues deeper into the already-transformed nodes, and transforms them further. My intuition says that if we traverse the tree bottom-up instead, this won't happen. Another alternative is to add a flag to each SymbolNode in the right-hand-side of the rule, and only transform those nodes:

res.traverse(function(n, path, parent) {
  if(n.isSymbolNode) {
    n.TransformThisNode = true;
  }
});

res = res.transform(function(n, path, parent) {
  if(n.TransformThisNode) {
    if(matches.placeholders.hasOwnProperty(n.name)) {
      var replace = matches.placeholders[n.name].clone();
      return replace;
    }
  }
  return n;
});
@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Oct 1, 2017

Resolved by #950

@firepick1

This comment has been minimized.

Collaborator

firepick1 commented Oct 1, 2017

Eric, thanks for the fix and insight. I woulda totally botched it.

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 1, 2017

Thanks a lot Eric!

I've added some unit tests for these cases to prevent regressions, see e033697.

Will be interesting to see whether we can find a solution which does not need .TransformThisNode to prevent infinite loops (though maybe this is simply the most robust solution). Traversing depth first could be interesting to look into, should not be hard to implement ortry, see #939.

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 1, 2017

This issue should be fixed now in v3.16.4

@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Oct 1, 2017

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 2, 2017

I'm don't directly see where we should apply stopping traversal. The transform part res = res.transform(...) already stops iterating when you return a replacement instead of the original node, it will not traverse new, replaced parts of the tree, so I would think that already works as we want. Should matches = _ruleMatch(rule.expanded.l, res)[0]; only return one matched rule instead of multiple or something like that?

@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Oct 2, 2017

Are you sure? It looks like the replacement is made, and then the replacement itself is transformed:

Node.prototype.transform = function (callback) {
// traverse over all childs
function _transform (node, callback) {
return node.map(function(child, path, parent) {
var replacement = callback(child, path, parent);
return _transform(replacement, callback);
});
}
var replacement = callback(this, null, null);
return _transform(replacement, callback);
};

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 2, 2017

hm, you're right. Thinking about it again this does not look like the most desirable solution to me in general, maybe we should change this? (not sure if you can consider this a bug but it gives tricky behavior...)

@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Oct 2, 2017

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 2, 2017

that's a good idea, at least for the time being. But I think it makes sense to change the behavior of the built in transform (will be a breaking change for v4).

@ericman314

This comment has been minimized.

Collaborator

ericman314 commented Oct 5, 2017

I removed the old traversal method and replaced it with a single-pass method that stops going deeper after replacing a node. #951

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 5, 2017

👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment