Stack overflow when parsing an expression

[orf]

Below I've attached a real file that has been published on PyPI. It contains an impressively gigantic expression.

huge.txt

Parsing this file with the current libcst master branch causes a stack overflow. After some debugging, this appears to be caused by the cache_left_rec macro cloning the expression (here), which in this case causes a gigantic recursive clone of the expression, eventually overflowing the stack.

[zsol]

FWIW CPython also chokes on this input:

❯ py -m py_compile 'huge.txt'
Sorry: RecursionError: maximum recursion depth exceeded during compilation

[orf]

Yeah, it's definitely a pathalogical file. What's annoying is that this brings down the entire process in Rust and there isn't really a way to stop that from happening, so you sort of need to heuristically detect if a given file will stack overflow or not based on the tokens.

I thought I'd add this issue anyway.

[zsol]

Fair enough. If anyone's interested in tackling this, here are a bunch of pointers:

There's best-effort recursion depth checking that's defined here:

LibCST/native/libcst/src/parser/grammar.rs

Line 88 in e9bad94

const MAX_RECURSION_DEPTH: usize = 3000;

It's checked in a couple of places, but we could definitely add more checks.

More context in #619, another example in #980

A much more thorough attempt is in the PR attached to kevinmehall/rust-peg#282