What is needed to improve lexing+parsing

[epage]

winnow works well for parsing text, but what about lexed tokens? How can we improve this?

[epage]

For larger Copy tokens or Clone tokens, the performance of cloning can negatively affect things

[epage]

#590 suggests &[T] streams use &T as the token type.

[epage]

Located gets the offset within an input, but there isn't a way to get the span from the tokens

See also

• Spans from custom tokens. #512
• https://www.reddit.com/r/rust/comments/1fa0h2c/thinking_on_switching_from_nom_to_lalrpop/llq526r/

[epage]

One solution left out of #512 is that users could do

impl Location for &[MyToken] {
    fn location(&self) -> usize {
        self.span.start
    }
}

The problem users will run into is that Parser::span assumes that the start of the next token is the end of the previous token.

We likely need to change the trait from

pub trait Location {
    fn location(&self) -> usize;
}

to

pub trait Location {
    fn start(&self) -> usize;
    fn end_exclusive(&self) -> usize;
}

or

pub trait Location {
    fn location(&self) -> Span<usize>;
}

Returning the Span makes the intent of the values the most obvious but most of the time, you don't need the same start and end at the same time but will be joining them from different tokens. It depends on how well the extra lookup gets optimized away.

[epage]

#512 explored this a bit and one of the problems you can hit is finding the location at the end of the input because there are no tokens left.

One approach might be

pub trait TokenLocation {
    fn location(&self) -> Span<usize>;
}

impl TokenLocation for u8 {
    fn location(&self) -> Span<usize> {
        0..1
    }
}

impl TokenLocation for char {
    fn location(&self) -> Span<usize> {
        0..(self.len_utf8())
    }
}

and have Located call that to. Because Located as the original input, we can look up the element before the current location and get its end location.

[epage]

Error recovery. While not required for this case, highly correlated that they'll be done together.

See #96

[epage]

Ease of tag, one_of, etc

See also https://www.reddit.com/r/rust/comments/1fa0h2c/thinking_on_switching_from_nom_to_lalrpop/llq526r/

[epage]

In #512, the poster does

// A TokenKind is a parser that accepts any token with that kind.
impl<'a, 'b, I, E> Parser<I, Token, E> for TokenKind
where
    I: Stream<Token = Token> + StreamIsPartial,
    E: ParserError<I>,
{
    fn parse_next(&mut self, input: &mut I) -> PResult<Token, E> {
        one_of(*self).parse_next(input)
    }
}
// Helper for the above implementation.
impl ContainsToken<Token> for TokenKind {
    fn contains_token(&self, token: Token) -> bool {
        token.kind == *self
    }
}

which allows things like

delimited(LParen, repeat(0.., sexpr), RParen)

Likely, someone will also want to impl Compare

A benefit of us using Parser, ContainsToken and Compare, rather than Eq, is that a Token can only check TokenKind while still having proper Eq that checks all fields.

[epage]

I wonder if we could simplify this by offering a TokenKind trait. We could then impl ContainsToken and Compare for any token that impl TokenKind. Where a parallel TokenKind is not available, users could use discriminant.

[epage]

CC @adamchalmers are you doing separate lexing and parsing?

[adamchalmers]

Hi, yes, we are.

Parser: https://github.com/KittyCAD/modeling-app/blob/main/src/wasm-lib/kcl/src/parser/parser_impl.rs
Tokenizer: https://github.com/KittyCAD/modeling-app/blob/main/src/wasm-lib/kcl/src/token/tokeniser.rs

Happy to sit down and think about this in some more detail (are you at Rustconf again this year? Happy to talk about my experience and walk through the code together...)

[epage]

Yes, I'll be there and was planning to go to your talk!

[adamchalmers]

Great! There's a slide on Winnow :)

[nevakrien]

Would it be possible to unify some of the traits? Specifcly it would be VERY nice if there was 1 big trait u had to implement which gave you virtually all the features of the libarary.

Sure it would be a pain to do. But you won't have ambiguity when there are 2 implementations of similar things (like InputTake and PositionInput) and you would not know that all features are avilble for your.

This is especially nice if you can hardcode a deafualt error type into that trait. So when u use a parser that has an ambitious error the deafualt trait for that input would be used.

I also suspect this will make implementation on the side of libarary maintainers easier since there is less time spend on trying to figure out which traits are needed for functionality.

[epage]

like InputTake and PositionInput

Compared to nom v7, we've unified a lot of traits into Stream and we provide impl Stream for &[T], see also https://docs.rs/winnow/latest/winnow/_topic/stream/index.html

btw nom v8 has done a similar unification (which has been in development since Dec 2022) though they made the change in a slightly different way.