Recursion support

[spoutn1k]

Hello all,

I am comparing parser combinators and trying to build a parser for GNU find in each. I am having trouble making a parser in winnow.

The following code will stack overflow:

#![allow(dead_code)]
use std::rc::Rc;
use winnow::{
    ascii::{multispace0, multispace1},
    combinator::{alt, cut_err, delimited, preceded, separated_pair},
    prelude::*,
    token::literal,
};

#[derive(Debug, Clone, PartialEq)]
enum Test {
    False,
    True,
}

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

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

fn parse_test(input: &mut &'_ str) -> PResult<Expression> {
    alt((
        literal("-true").value(Expression::Test(Test::True)),
        literal("-false").value(Expression::Test(Test::False)),
    ))
    .parse_next(input)
}

fn parse_operator(input: &mut &'_ str) -> PResult<Expression> {
    alt((
        preceded(
            (alt((literal("!"), literal("-not"))), multispace0),
            cut_err(parse_expression),
        )
        .map(Operator::Not),
        separated_pair(
            parse_expression,
            delimited(
                multispace1,
                alt((literal("-and"), literal("-a"))),
                multispace1,
            ),
            parse_expression,
        )
        .map(|(lhs, rhs)| Operator::And(lhs, rhs)),
    ))
    .map(Rc::new)
    .map(Expression::Operator)
    .parse_next(input)
}

fn parse_expression(input: &mut &'_ str) -> PResult<Expression> {
    alt((parse_operator, parse_test)).parse_next(input)
}

#[test]
fn test_parse_expression() -> Result<(), Box<dyn std::error::Error>> {
    let res = parse_expression(&mut "! -true").unwrap();
    assert_eq!(
        Expression::Operator(std::rc::Rc::new(Operator::Not(Expression::Test(
            Test::True
        )))),
        res
    );

    let res = parse_expression(&mut "-false -a -true").unwrap();
    assert_eq!(
        Expression::Operator(std::rc::Rc::new(Operator::And(
            Expression::Test(Test::False),
            Expression::Test(Test::True)
        ))),
        res
    );

    Ok(())
}

I was able to achieve the above using nom, nom_locate and nom-recursive, yet I find the solution to lack elegance and I like the error support of winnow. Please let me know if there are any way I can do the above.

One of winnow's examples uses recursion yet I am having trouble figuring out the major difference between it and this project, except that maybe the lack of literal (if) before the recursive expression.

[epage]

Could you share the nom code so i can compare what you are trying to do? Also, is there a reference grammar?

[spoutn1k]

Can I add you to a project with the nom code ? The reference grammar is the one of GNU find, you can find it in the manual, and I modelled it using some AST.

[epage]

If its private and thats what it takes to share, sure.

When I look in man find, I don't quite see a succinct BNF-like grammar, but more a full reference. If thats all you are working off of, thats ok.

[spoutn1k]

Yeah it does not make sense to privatize tests so here is the URL: https://github.com/DDNmea/find-parser.

You will find a comparison between nom and winnow along with the full code, as I posted a minimal version.

[spoutn1k]

Also, this is the reference I am following:

   OPERATORS
       Listed in order of decreasing precedence:

       ( expr )
              Force  precedence.   Since  parentheses are special to the shell,
              you will normally need to quote them.  Many of  the  examples  in
              this  manual page use backslashes for this purpose: ‘\(...\)' in‐
              stead of ‘(...)'.

       ! expr True if expr is false.  This character  will  also  usually  need
              protection from interpretation by the shell.

       -not expr
              Same as ! expr, but not POSIX compliant.

       expr1 expr2
              Two  expressions  in a row are taken to be joined with an implied
              -a; expr2 is not evaluated if expr1 is false.

       expr1 -a expr2
              Same as expr1 expr2.

       expr1 -and expr2
              Same as expr1 expr2, but not POSIX compliant.

       expr1 -o expr2
              Or; expr2 is not evaluated if expr1 is true.

       expr1 -or expr2
              Same as expr1 -o expr2, but not POSIX compliant.

       expr1 , expr2
              List; both expr1 and expr2 are always evaluated.   The  value  of
              expr1  is discarded; the value of the list is the value of expr2.
              The comma operator can be useful for searching for  several  dif‐
              ferent  types  of  thing, but traversing the filesystem hierarchy
              only once.  The -fprintf action can be used to list  the  various
              matched items into several different output files.

       Please  note that -a when specified implicitly (for example by two tests
       appearing without an explicit operator between them) or  explicitly  has
       higher  precedence than -o.  This means that find . -name afile -o -name
       bfile -print will never print afile.

The expressions are made of those operators and tests/actions, but I will spare you the list as they are less relevant to this discussion :)

[epage]

nom-recursive

I guess I didn't look closely enough at nom-recursive. I had thought it was only good for preventing stackoverflow detection, not that it helped you be able to process arbitrarily recursive expressions. I'm not even too sure what the theory of operation is for this in looking at the code.

Generally, when I see people trying to parse grammars like this (take for instance math expressions), they take an iterative approach using separated and do precedence climbing. #131 would simplify this and make it more performant.

[spoutn1k]

It did feel a little magic adding a macro to the function and seeing it work (almost).

I can try this but taking an iterative approach feels much more convoluted than a recursive matching. Would #131 make precedence climbing or recursive parsing more performant ?

[epage]

It would make it more performant than doing it with separated_foldl and separated_foldr. Unsure how it would compare with recursive. Likely, so.

[spoutn1k]

What is the timeline for it ? Obviously not in a hurry and I greatly appreciate all the work that goes into it, just wanted to know if there was some idea of the completion percentage.

[spoutn1k]

So what I am getting from the answers is that recursive parsing is not fully supported by winnow due to the structure of the project ? One should use other methods to achieve parsing a grammar like above ?