Recursive Parser has no limit, leading to stack overflow on deeply nested inputs

[Sahilgill24]

Project version

0.7.2

Project

compiler

What happened?

The chumsky recursive parser (src/parse.rs:2599) re-enters itself once every nesting level of either a block or paranthesis without any depth counter, so for each level a stack frame is pushed and after a certain level of nesting the stack threshold is reached and the Process gets aborted.

Moreover the type parser in (src/parse.rs:1929) also does not have a depth counter, so ideally it could be recreated with nested types as well. I have added an example with paranthesis in the reproduction steps.

This could also lead to a trivial DoS attack on any service that compiles .simf files.

Minimal reproduction steps

fn main() {
    let x: u32 = ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
        (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
        (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
        ((((((((((((((((((0))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
        )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
        )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
        ))))))))))))))))))))));
    assert!(jet::eq_32(x, 0));
}

I tried this upto 300 paranthesis and it starts getting overflow around 150 ish and compiles correctly till 100

error

thread 'main' (5532049) has overflowed its stack
fatal runtime error: stack overflow, aborting
[1]    49397 abort      ./target/debug/simc ./bug.simf

[apoelstra]

When I do a stack trace on this code I see

#50 0x0000555555c97c13 in simplicityhl::ast::{impl#25}::analyze (from=0x555556056110, ty=0x7ffffffe4500, scope=0x7ffffffefec0) at src/ast.rs:1788
#51 0x0000555555c96ba3 in simplicityhl::ast::{impl#24}::analyze (from=0x555556056110, ty=0x7ffffffe4500, scope=0x7ffffffefec0) at src/ast.rs:1681

over and over.

So it's the analyzer, not the parser, which is overflowing. We should fix the analyzer to not be recursive.

[apoelstra]

Compare Value::from_const_expr which also recurses through an expression. It writes

for data in ExprTree::Expression(expr).post_order_iter() {
   // logic here for all the kinds of expressions
}

We should drop the AbstractSyntaxTree trait and instead add a pub fn analyze method directly on Expression which uses the same pattern.