Bug: Consumed too many input on neighboring Nilfixes

[andylokandy]

Given an input [Literal(1), Literal(1)], the pratt parser is expected to output a single 1 and leave the latter 1 in the input iterator. But it instead returns a single 1, leaving an empty iterator.

Here is a minimal reproducible example:

use pratt::{Affix, Associativity, PrattParser, Precedence, Result};

fn main() {
    let ast = vec![AST::Nilfix, AST::Nilfix, AST::Nilfix];
    let mut iter = ast.into_iter();
    println!("{:?}", ExprParser.parse(&mut iter));
    println!("{:?}", iter.collect::<Vec<_>>());
}

#[derive(Debug, Eq, PartialEq)]
pub enum AST {
    Nilfix,
}

#[derive(Debug, Eq, PartialEq)]
pub enum Expr {
    Nilfix,
}

#[derive(Debug, Eq, PartialEq)]
struct ExprParser;

impl<I> PrattParser<I> for ExprParser
where
    I: Iterator<Item = AST>,
{
    type Error = pratt::NoError;
    type Input = AST;
    type Output = Expr;

    fn query(&mut self, tree: &AST) -> Result<Affix> {
        let affix = match tree {
            AST::Nilfix => Affix::Nilfix
        };
        Ok(affix)
    }

    fn primary(&mut self, tree: AST) -> Result<Expr> {
        let expr = match tree {
            AST::Nilfix => Expr::Nilfix,
        };
        Ok(expr)
    }

    fn infix(&mut self, lhs: Expr, tree: AST, rhs: Expr) -> Result<Expr> {
        unreachable!()
    }

    fn prefix(&mut self, tree: AST, rhs: Expr) -> Result<Expr> {
        unreachable!()
    }

    fn postfix(&mut self, lhs: Expr, tree: AST) -> Result<Expr> {
        unreachable!()
    }
}

Once it runs, it prints:

Ok(Nilfix)
[Nilfix]

while I'm expecting two Nilfix in the iterator.

[segeljakt]

Hi, sorry I missed your issue. I think the problem is that pratt requires one token lookahead. Inside the parser I'm creating a peekable iterator using iter.peekable() which basically consumes the next token when using peek(). However, you can also pass in your own peekable iterator directly with the parse_input() function:

fn main() {
    let ast = vec![AST::Nilfix, AST::Nilfix, AST::Nilfix];
    let iter = &mut ast.into_iter();
    let mut iter = iter.peekable();
    println!("{:?}", ExprParser.parse_input(&mut iter, Precedence(0)));
    println!("{:?}", iter.collect::<Vec<_>>());
}

This prints

Ok(Nilfix)
[Nilfix, Nilfix]

Perhaps we could update the API to allow doing this more easily. I'm not sure what's the best solution.

[segeljakt]

We could make it so the parse function takes ownership of the input iterator and parse_input only borrows it, but requires passing a peekable iterator.

[andylokandy]

Thank you! The workaround solved the problem. :wink:

BTW, in my use case, a slice as input may work better than an iterator because I parse the input using nom, which always gives me a Vec of input elements, and I frequently have to query the precedence of elements, where I have to write PrattParser::<std::iter::Once<_>>::query(&mut ExprParser, &elem). I'm not urging anyone to change the API but just giving some information.