Timeout in recursion

[Keats]

Found while fuzzing Tera v1.

The following expression is very slow: https://github.com/Keats/tera/blob/v1/src/tera.rs#L1028
and adding a level of recursion (eg _(p=__(p=[_(p=__(p=[_(p=[_(p=[_1(p=[_(p=[_1) will timeout

As far as I can see, the issue is that the rule fn_call is in the basic_val (https://github.com/Keats/tera/blob/v1/src/parser/tera.pest#L82) which is part of the potential values for a function argument -> recursing.

The issue seem to be in the generated lexer since it timeouts in the pest generated code.

[Keats]

I've added a test for it in Keats@4749b31

That also allowed me to find the issue:

Keats@4749b31#diff-0a31f1c430e1b35cb3a08b8f7e2762c4R68 is probably ambiguous in comparison_expr since it can start with fn_call. Removing those fn_call in string_concat solves the timeout issue.

Should I do a PR with the test in the meantime @dragostis ?

Edit: actually pasting the whole Tera grammar causes it to timeout again 🤔 so the previous successful result was probably from me removing a bunch of rules to make the grammar shorter for the test

[dragostis]

The issue is probably related to some degenerate case that passes the optimization phase, so this is most definitely a bug. Unfortunately, I still haven't had the time to take a better look at it.

[Keats]

Unfortunately, I still haven't had the time to take a better look at it.

Don't worry about it. I'll have a look when I get some time to see if I can figure it out but I haven't looked at the internals of pest yet so that's going to take some time/effort. I've tried the debugger but wasn't sure how the breakpoints and everything worked.

[Keats]

@dragostis any pointers on where to look for the bug?