Very slow recursive pattern

[Spu7Nix]

Parsing this expr(ession)
a(b,{a(b,{a(b,{a(b,{a(b,{a(b,{a(b,{a(b,{})})})})})})})})
with this grammar

WHITESPACE = _{ " " | "\t"}
cmp_expr = {"{" ~  expr* ~ "}"}
value = _{cmp_expr | symbol}
call = {value ~ (arguments)*}
arguments = { "(" ~ (expr ~ ",")* ~ expr? ~ ")" }
expr = {(call ~ operator)* ~ call}
operator = {"+"}
symbol = ${ASCII_ALPHA+}

is extremely slow (takes multiple minutes, and gets exponentially slower as you add more recursion).

[SkiFire13]

When parsing expr your rule must parse call then operator and if it fails it has to parse call again. This means that for each level the number of parsing of call rules doubles, hence the exponential time. I'm not sure if this can be optimized in the parser, I guess it could I opened a PR for optimizing expr-like rules, but it can't handle arguments-like rules. For now you may want to rewrite your rules to move the optional rules at the end. The following rules should be equivalent to yours and run in linear time.

WHITESPACE = _{ " " | "\t"}
cmp_expr = {"{" ~  expr* ~ "}"}
value = _{cmp_expr | symbol}
call = {value ~ (arguments)*}
arguments = { "(" ~ (expr ~ ("," ~ expr)* ~ ","?)? ~ ")" }
expr = {call ~ (operator ~ call)*}
operator = {"+"}
symbol = ${ASCII_ALPHA+}

[sbeckeriv]

Thank you for this issue. it was a very helpful example of a recursive pattern. You have helped me get unstuck!

[f0i]

I had a similar performance issue with rules of the form x | (rule ~ rest1) | (rule ~ rest2) | rule (source) that was fixed by changing to x | rule ~ (rest1 | rest2)?.
I guess #473 only optimizes the last two.

One more issue that caused exponential parsing time was in the form of a? ~ b? ~ rule ~ rest | rule (source) that I converted to (a ~ b? | b) ~ rule ~ rest | rule ~ rest?.

It is quite hard to find those when there is some nesting and indirection.
So I was also wondering if the results could be cached, so that it doesn't have to re-evaluate a rule when it's at the same position inside the input.