Stack overflow before parsing

[spoutn1k]

Hello, getting a stack overflow when trying to parse a recursive type using nom. The leaves of the AST tree were reduced to make the example simpler.

Maybe I am not using nom the proper way ?

Prerequisites

Here are a few things you should provide to help me understand the issue:

• Rust version : rustc 1.74.1 (a28077b28 2023-12-04)
• nom version : nom = "7.1.3"
• nom compilation features used: default from cargo add nom

Test case

Example test case:

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::combinator::map;
use nom::sequence::separated_pair;
use nom::IResult;

mod ast {
    use std::rc::Rc;

    #[derive(Debug, Clone, PartialEq)]
    pub enum Test {
        AccessMin(i32),
    }

    #[derive(Debug, Clone, PartialEq)]
    pub enum Operator {
        And(Expression, Expression),
    }

    #[derive(Debug, Clone, PartialEq)]
    pub enum Expression {
        Operator(Rc<Operator>),
        Test(Test),
    }
}

fn parse_operator(input: &str) -> IResult<&str, ast::Operator> {
    alt((map(
        separated_pair(parse_expression, tag(" -and "), parse_expression),
        |(lhs, rhs)| ast::Operator::And(lhs, rhs),
    ),))(input)
}

pub fn parse_expression(input: &str) -> IResult<&str, ast::Expression> {
    alt((map(parse_operator, |val| {
        let val = std::rc::Rc::new(val);
        ast::Expression::Operator(val)
    }),))(input)
}

fn main() {
    let _ = parse_expression("");
}

Interestingly, using the not operator works with a recursive type. I had the following before:

fn parse_operator(input: &str) -> IResult<&str, ast::Operator> {
    log::info!("Parsing operator !");
    alt((
        map(
            delimited(
                terminated(tag("("), character::complete::space0),
                parse_expression,
                preceded(character::complete::space0, tag(")")),
            ),
            ast::Operator::Precedence,
        ),
        map(
            separated_pair(
                alt((tag("!"), tag("-not"))),
                character::complete::space0,
                parse_expression,
            ),
            |(_, e)| ast::Operator::Not(e),
        ),
    ))(input)
}

So it would seem calling the parse_expression twice creates the issue.
And this worked fine. Am running on arm macOS.

[spoutn1k]

Found https://github.com/dalance/nom-recursive. Worth putting on the README.