Recursive parser blocks indefinitely

[clarkmcc]

I've been fighting this back and forth on my CEL-parser so here's a minimal reproducible example. I'm trying to parse the string "2+2" but the parser blocks indefinitely. This seems like undesirable behavior. Is this a "me" problem or a bug?

let str = "2+2";

#[derive(Debug, Clone)]
enum Operation {
    Add,
    Subtract,
}

#[derive(Debug, Clone)]
enum Expression {
    Number(i32),
    Operation(Box<Expression>, Operation, Box<Expression>),
}

let parser = recursive::<_, _, extra::Err<Rich<char>>, _, _>(|expr| {
    let number = text::int(10)
        .slice()
        .map(|s: &str| Expression::Number(s.parse().unwrap()));

    let op = choice((
        just('+').to(Operation::Add),
        just('-').to(Operation::Subtract),
    ));

    let operation = expr
        .clone()
        .foldl(op.then(expr.clone()).repeated(), |lhs, (op, rhs)| {
            Expression::Operation(Box::new(lhs), op, Box::new(rhs))
        });
    choice((operation, number))
})
.then_ignore(end());

let (out, errors) = parser.parse(str).into_output_errors();

errors.into_iter().for_each(|e| {
    Report::build(ReportKind::Error, (), e.span().start)
        .with_message(e.to_string())
        .with_label(
            Label::new(e.span().into_range())
                .with_message(e.reason().to_string())
                .with_color(Color::Red),
        )
        .finish()
        .print(Source::from(str))
        .unwrap()
});

println!("{:#?}", out);

[clarkmcc]

Okay so I was able to get it to unblock by doing

let operation = number.foldl(op.then(number).repeated(), |lhs, (op, rhs)| {
    Expression::Operation(Box::new(lhs), op, Box::new(rhs))
});

which probably means that a repeated fold inside a recursive parser, on itself is not supported?

The problem that I have is that my arithmetic expressions are performed between two expressions themselves, and folding over the expression itself seems to be locking things up.

pub enum Expression {
    ...
    Arithmetic(Box<Expression>, ArithmeticOp, Box<Expression>),
    ...
}

[zesterer]

At a glance, this seems like you're invoking left recursion. Don't worry though: left-recursive patterns can be rewritten to right-recursive patterns, usually using precedence climbing. The tutorial discusses how this can be done.