working hours and can't get pratt to work, trait bounds not satified

[myrfy001]

This question is related to #566. I'm trying to parse with the pratt parser, and I can't get the code to compile. I have copied the return type definition from the nanorust example, but it doesn't work for my code.

The code below is a minimized version of my code and you can copy the whole code into a blank project and to see the compiler error output.

the compiler says that the Operator trait is not implemented for Prefix parser, I have implemented the Clone for all my custom types and I don't know where else could be wrong.

use chumsky::prelude::*;

use chumsky::pratt::*;

// use chumsky::input::{Stream, MapExtra};
use chumsky::span::SimpleSpan;

pub type Span = SimpleSpan<usize>;
pub type Spanned<T> = (T, Span);

use chumsky::{extra, prelude::Rich, primitive::just};

// The type of the input that our parser operates on. The input is the `&[(Token, Span)]` token buffer generated by the
// lexer, wrapped in a `SpannedInput` which 'splits' it apart into its constituent parts, tokens and spans, for chumsky
// to understand.
type ParserInput<'tokens, 'src> =
    chumsky::input::SpannedInput<Token<'src>, Span, &'tokens [(Token<'src>, Span)]>;

#[derive(Debug, Clone)]
pub enum AstOperatorExpr<'src> {
    UniOp {
        op: Spanned<&'src str>,
        expr: Box<Spanned<AstExpression<'src>>>,
    },
    BinOp {
        op: Spanned<&'src str>,
        expr1: Box<Spanned<AstExpression<'src>>>,
        expr2: Box<Spanned<AstExpression<'src>>>,
    },
}

#[derive(Debug, Clone)]
pub enum AstExpression<'src> {
    Op(Spanned<AstOperatorExpr<'src>>),
}

#[derive(Debug, Clone)]
pub enum AstExprPrimary<'src> {
    Expr(Box<Spanned<AstExpression<'src>>>),
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Token<'src> {
    Identifier(&'src str),
    Keyword(&'src str),
    Op(&'src str),
}

fn parser_operator_expr<'tokens, 'src: 'tokens>(
    expression: impl Parser<
            'tokens,
            ParserInput<'tokens, 'src>,
            Spanned<AstExpression<'src>>,
            extra::Err<Rich<'tokens, Token<'src>, Span>>,
        > + Clone,
) -> impl Parser<
    'tokens,
    ParserInput<'tokens, 'src>,
    Spanned<AstExpression<'src>>,
    extra::Err<Rich<'tokens, Token<'src>, Span>>,
> + Clone {
    let ret = expression.pratt((prefix(18, just(Token::Op("-")), |rhs| {
        AstExpression::Op((
            AstOperatorExpr::UniOp {
                op: ("-", SimpleSpan::new(0, 0)),
                expr: (Box::new((rhs, SimpleSpan::new(0, 0)))),
            },
            SimpleSpan::new(0, 0),
        ))
    }),));
    ret
}

Comiler error msg is :

error[E0277]: the trait bound `chumsky::pratt::Prefix<Just<lexer::Token<'_>, _, _>, [closure@src/bsv_parser/mod.rs:771:66: 771:71], _, _>: pratt::Operator<'_, SpannedInput<lexer::Token<'src>, SimpleSpan, &'tokens [(lexer::Token<'src>, SimpleSpan)]>, (ast::AstExpression<'src>, SimpleSpan), chumsky::extra::Full<chumsky::error::Rich<'tokens, lexer::Token<'src>>, (), ()>>` is not satisfied
   --> src/bsv_parser/mod.rs:765:6
    |
765 |   ) -> impl Parser<
    |  ______^
766 | |     'tokens,
767 | |     ParserInput<'tokens, 'src>,
768 | |     Spanned<AstExpression<'src>>,
769 | |     extra::Err<Rich<'tokens, Token<'src>, Span>>,
770 | | > + Clone {
    | |_________^ the trait `pratt::Operator<'_, SpannedInput<lexer::Token<'src>, SimpleSpan, &'tokens [(lexer::Token<'src>, SimpleSpan)]>, (ast::AstExpression<'src>, SimpleSpan), chumsky::extra::Full<chumsky::error::Rich<'tokens, lexer::Token<'src>>, (), ()>>` is not implemented for `chumsky::pratt::Prefix<Just<lexer::Token<'_>, _, _>, [closure@src/bsv_parser/mod.rs:771:66: 771:71], _, _>`
    |
    = help: the following other types implement trait `pratt::Operator<'a, I, O, E>`:
              chumsky::pratt::Prefix<A, F, Op, (O,)>
              chumsky::pratt::Prefix<A, F, Op, (Op, O)>
              chumsky::pratt::Prefix<A, F, Op, (Op, O, <I as chumsky::input::Input<'a>>::Span)>
    = note: required for `Pratt<impl Parser<'tokens, ParserInput<'tokens, 'src>, Spanned<AstExpression<'src>>, extra::Err<Rich<'tokens, Token<'src>, Span>>> + Clone, ...>` to implement `chumsky::private::ParserSealed<'_, SpannedInput<lexer::Token<'src>, SimpleSpan, &'tokens [(lexer::Token<'src>, SimpleSpan)]>, (ast::AstExpression<'src>, SimpleSpan), chumsky::extra::Full<chumsky::error::Rich<'tokens, lexer::Token<'src>>, (), ()>>`
    = note: required for `Pratt<impl Parser<'tokens, ParserInput<'tokens, 'src>, Spanned<AstExpression<'src>>, extra::Err<Rich<'tokens, Token<'src>, Span>>> + Clone, ...>` to implement `chumsky::Parser<'tokens, SpannedInput<lexer::Token<'src>, SimpleSpan, &'tokens [(lexer::Token<'src>, SimpleSpan)]>, (ast::AstExpression<'src>, SimpleSpan), chumsky::extra::Full<chumsky::error::Rich<'tokens, lexer::Token<'src>>, (), ()>>`

[zesterer]

I should have time to look at this more closely tomorrow, sorry to hear that you're running into issues.

[myrfy001]

It's very nice of you to take some time to help me. When use &str as input, the code works well, but after parsing &str into my own tokens, and use tokens as input, the compiler begins to complain. Facing those error messages I really don't know howto handle with it. Porting from 0.9x to 1.0 seems not an easy work and there are more lifetimes and type annotations need.

[zesterer]

Well, turns out that I tested positive for COVID just a few hours after posting this, so I've been too exhausted to do anything over the last day. Sorry again, perhaps Monday instead.

[Zij-IT]

I got your back @zesterer ;)

As the error message implies (although although not clearly), the issue has to do with your pratt operator. This is because your pratt operator, despite what I believe you think, is Fn(Spanned<AstExpression<'src>>) -> AstExpression<'src>. This is an issue because a pratt function must be of the form Fn(O) -> O. In order to fix this you just have to add a span to the AstExpression::Op`, a la:

fn parser_operator_expr<'tokens, 'src: 'tokens>(
    expression: impl Parser<
            'tokens,
            ParserInput<'tokens, 'src>,
            Spanned<AstExpression<'src>>,
            extra::Err<Rich<'tokens, Token<'src>, Span>>,
        > + Clone,
) -> impl Parser<
    'tokens,
    ParserInput<'tokens, 'src>,
    Spanned<AstExpression<'src>>,
    extra::Err<Rich<'tokens, Token<'src>, Span>>,
> + Clone {
    expression.pratt((prefix(
        18,
        just(Token::Op("-")),
        |rhs: Spanned<AstExpression<'src>>| {
            (
                AstExpression::Op((
                    AstOperatorExpr::UniOp {
                        op: ("-", SimpleSpan::new(0, 0)),
                        expr: Box::new(rhs),
                    },
                    SimpleSpan::new(0, 0),
                )),
                SimpleSpan::new(0, 0),
            )
        },
    ),))
}

I've done a LOT of work with the pratt operators, so while it may be familiarity with the issue that led me to fix it, I can at least give you some advice:

If the compiler is complaining about the pratt operators, indicated by this help error message:

help: the following other types implement trait `pratt::Operator<'a, I, O, E>`:
             chumsky::pratt::Prefix<A, F, Op, (O,)>
             chumsky::pratt::Prefix<A, F, Op, (Op, O)>
             chumsky::pratt::Prefix<A, F, Op, (Op, O, &mut MapExtra<'a, '_, I, E>)>

I would recommend that you add the types to your pratt operator functions. This can help to assure that your operators are properly formed. Ideally this would be a type error instead of a trait error, but I don't know if we can help Rust to construct error messages quite.