Adding '{' makes code run exponentially slow.

[nm17]

Just an interesting thing that I found. It seems that continuously adding '{' doubles execution time with each '{' and also consumes 100% CPU while running. Not sure if this should be treated as a bug or not.

Long backtrace of running {{{{{{{{{{{{{{{{{{ (thats 18 '{'):

https://gist.github.com/nm17/ed64b33f838a97c1285aa5ef1229eab0

[pigpigyyy]

Confirmed this performance issue with continuously nesting table literals. Found that it's caused by not arranging the orders of syntax parsing rules properly. Commit 0cc452c7cf2301e75bab1069c9da6ee73c7c5cfd should have fixed this. Before this commit I got

-- file test.yue
{{{{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}}}}

> yue -b test.yue
Parse time:     975.43 ms
Compile time:   0.039875 ms

After this commit I got

> yue -b test.yue
Parse time:     0.25387 ms
Compile time:   0.048875 ms

There may still be cases the parser will go in a needless pretty deep parsing stack. You may keep opening issues when you find more.

[nm17]

@pigpigyyy While the commit did fix the issue of parsing closed blocks of {{{}}}, it still takes a lot of time parsing expressions like {{{ and (((((. Please make a check for this if you can, it will help me find bugs quicker.

[pigpigyyy]

Found it was a redundant PEG syntax back trace issue which happened in rule ChainValue. When the parser failed to check rule Callable >> ChainItems, it fell back to check rule Callable again, the parsing stack for Callable became doubled. Tried to fix it in commit aed06d619272f9e89c27611d9ca6db6002402860.

[nm17]

@pigpigyyy here are cases of hanging I found while fuzzing (This is is on the latest main commit 89b606df6303a44f121be8ff0f4458c97f93d9df):

hangs.zip

Some of them are possibly false positives.

[pigpigyyy]

The nested syntax parser tree is leaving lots of fallback patterns to try, that causes the unclosed {{{{{{{{ expression taking a pretty long match to fail. Added a stoping rule for the error case syntax to prevent parser hanging. Sorry for forgetting testing the invalid codes you mentioned earlier.

[nm17]

Now stuff like [f[f[f[f[f[[f[f[f[f[f[f[f[f[[f[f[f[f[f[f[f[f[f[f[ is making yue hang

[nm17]

@pigpigyyy Here are some more hangs and crashes that I've been able to find using a fuzzer on the latest commit 32f2a57.

hangsandcrashes.zip

[pigpigyyy]

Tried fixing all similar issues by limiting nested expressions parsing depths to 100 levels. The parser is written in a parser combinator which is spawning lots of recursive function call stacks. Maybe a better way to fix is rewriting the recursive parser functions into a common loops and expand temporary memory usage into heap memory.