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

[tanman-]

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.

[firepick1]

@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]

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 :flushed:.

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]

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]

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]

Ok. I will try to take a closer look tonight.

On Sep 30, 2017 8:11 AM, "Jos de Jong" [e-mail] wrote:

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(); // OKmath.simplify('2n - 1').toString(); // NOT OK (infinite loop)math.simplify('2n1 - 1').toString(); // NOT OK (returns 1)

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/josdejong/mathjs/issues/948#issuecomment-333311118,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGDTkQyZgFe0EYJy6-VlftNF3RiEeiynks5snkwZgaJpZM4PmtFi
.

[josdejong]

Thanks Eric :+1:

[ericman314]

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]

Resolved by #950

[firepick1]

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

[josdejong]

Thanks a lot Eric!

I've added some unit tests for these cases to prevent regressions, see https://github.com/josdejong/mathjs/commit/e033697001459b220a394d5e6cd9b508da4760ff.

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 issue should be fixed now in v3.16.4

[ericman314]

True, a custom function that stops traversing deeper after transforming a
node would be more efficient.

On Oct 1, 2017 12:29 PM, "Jos de Jong" [e-mail] wrote:

Thanks a lot Eric!

I've added some unit tests for these cases to prevent regressions, see
e033697
https://github.com/josdejong/mathjs/commit/e033697001459b220a394d5e6cd9b508da4760ff
.

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
https://github.com/josdejong/mathjs/issues/939.

—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
https://github.com/josdejong/mathjs/issues/948#issuecomment-333396426,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGDTkcBD0Xm35Ow8whzQvxkvBsxsnpz9ks5sn9oSgaJpZM4PmtFi
.

[josdejong]

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]

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

https://github.com/josdejong/mathjs/blob/d12d8f76d3a52a299f74464247520b573bffb156/lib/expression/node/Node.js#L153-L164

[josdejong]

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]

I will write a custom traversal function.

On Oct 2, 2017 11:38 AM, "Jos de Jong" [e-mail] wrote:

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...)

—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
https://github.com/josdejong/mathjs/issues/948#issuecomment-333607612,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AGDTkaCym2x4PR7lBUrWPdnYSSbXvuOAks5soR-QgaJpZM4PmtFi
.

[josdejong]

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]

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

[josdejong]

:+1: