Exponential time explosion with deeply nested binary expressions
lizreu opened this issue · 2 comments
Minimal reproducible example:
return (((((((((((((((("a" .. a) .. ",") .. b) .. ",") .. c) .. ",") .. d) .. ",") .. e) .. ",") .. f) .. ",") .. g) .. ",") .. h) .. ",") .. i
On my hardware, full_moon took >100s to parse this expression in release mode.
I had a very similar issue in my hand-rolled pest parser for Lua, which drove me to switch to full_moon. Admittedly, it was much worse with pest, because it really didn't handle that sort of recursion for a number of reasons.
While it's easy to rewrite this statement manually, this is still valid Lua, and the Lua parser itself has no issues parsing this in linear time. Incidentally, this is how TypeScriptToLua outputs interpolated string expressions.
I have a feeling this might be fixed by the ongoing parser rewrite, where we try to remove the backtracking in the parser: #274
I think the baseline Lua 5.1 syntax is complete, so if you can get it compiling enough for your case, I wonder if it indeed improves for this case
Can confirm, this is fixed in the parser rewrite and is basically instant