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.

[gammelalf]

I personally would prefer a newtype which wraps a &[T] and implements Stream with this alternative behaviour.

This would behave similar to Bytes and Str being wrappers for &[u8] and &str.

This is what I went with in a project I have been working on.

[epage]

Having a TokenSlice<T> could provide for some nice flexibility in how we provide helpers for tokens, whether its extracting locations or having a helper trait to implement for ContainsToken to work.

As your project evolves, I'd be curious to hear of any lessons learned from the effort

[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

[gammelalf]

I would be really interested in a solution for that but don't have any real input yet for how that might work.

For context, I have tried using winnow for parsing TokenStreams in proc macros because I was looking for a syn alternative.
With a great recovery mechanism, I could for example recover from a syntax error in an expression and continue parsing the following code, collecting all syntax errors and reporting them all at once. This would be an advantage over syn which always stops at the first syntax error.

[epage]

I'm playing with error recovery in a parser I'm working on in (rare) spare moments. It'll hopefully help inform things with the unstable feature.

[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]

In cratesland/spath#5, they also call out the desire to match text inside the token.

[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.

[epage]

FYI I've posted #720 which adds TokenSlice with the following characteristics

• Uses &Token in case cloning of tokens is expensive
• Forwards Location to the Token in case it carries a span into the original input
• Implements Compare for any PartialEq type, allowing literal to be used with a TokenKind, &str, or anything else.

I'll leave it as a draft for a few days to collect feedback.

[mhedgpeth]

Again, it was a little confusing to me when approaching winnow whether to lex first (I took a look at and liked logos) or during my parse. I settled on keeping it all in winnow and it has led me to sometimes confusing logic (i.e. do I have whitespace preceding my colon? if so consume that but don't consume the whitespace after the colon because it might be this other thing). Plus I thought that the regex version of logos would be slower than just doing the if statements off of characters.

Which leads me to ask you: when would you recommend using winnow as a parser of lexed tokens? This might relate to the binary question in the other topic, and might be a nice element of the introduction.

[epage]

At least for toml, I found directly parsing useful because I could easily map every function and constant back to the grammar. This gave me a lot of confidence that my parser was right and requires less upkeep on my side.

I am experimenting with rewriting toml_edit with separate lexing + parsing. It makes that mapping between grammar and parser much more difficult and I'm only considering it because of how comfortable I've gotten with TOML's grammar. Even then, I hesitate. My main motivation is that this is a last ditch effort to see if I can get a TOML parser any faster before considering more drastic efforts inside of cargo.

Hmm, I should update https://docs.rs/winnow/latest/winnow/_topic/lexing/index.html with some of this information

[pcone]

This threw me for a loop too:

Writing a seperate tokenization step, and then using the token objects/enums produced by that as the input to a second parser that outputs an AST struck me as a much cleaner/easier to understand approach that rolling it all into one, so that's what I did.

After a bit of trial and error, reading the docs, and then going back and really reading the docs I had a pretty good understanding of how the library worked and ended up with a tokenizer without a huge amount of effort.
(I think the one thing that wasted a bunch of time was not clicking on the definition for 'set of tokens' early/not realizing most of the combinators support all of those things - but this is probably a me problem - the docs are fairly clear about this when you click the 'set of tokens' link).

After that though I realized trying to write parser functions that took anything other than &mut &str as input just resulted in fairly cryptic type errors (I also haven't written any rust for a few months though so that could be partially on me).
I made a bit of progress after reading the parser impls for string and byte string as mentioned in the docs, but it didn't really click properly until I stumbled across this QA discussion, and found the lexing topic page via here.

I think a few things might have made the experience for me, and anyone else with a similar "skim read the docs and start churning out code" approach to learning new libraries a bit easier/faster:

• Mention this use case more explicitly on the main docs landing page or in a "what's next?"/"alternate approaches" type section at the end of the tutorial (or both).
• Explain the need for some kind of less specific comparison that just matches the 'type' of token rather than the token and the value - this is 'TokenKind' in the code example (this feels pretty obvious/necessary in hindsight, but it took reading the example code and thinking about it for a while to really click initially).
• Explicitly talk about the need to impl ContainsToken for the aforementioned TokenKind (it's in the code example, but it's a fairly big chunk of code and it's in the middle).

(Also worth noting I haven't gotten very far into writing the AST generation step still - I believe I understand what I need now, but it's very likely I'll hit hurdles I don't know about yet)

[epage]

Thanks for sharing your experience! Its a big help to see the path someone took to try to help other people.

I've made some tweaks in #776 to help in discovery and to be a bit more complete in relevant traits.

Explain the need for some kind of less specific comparison that just matches the 'type' of token rather than the token and the value - this is 'TokenKind' in the code example (this feels pretty obvious/necessary in hindsight, but it took reading the example code and thinking about it for a while to really click initially).

I assume this is for the lexing section. Yes, a lot more content is needed for that section.

Are you referring to giving suggested design principles for Token, TokenKind, etc?

[pcone]

Are you referring to giving suggested design principles for Token, TokenKind, etc?

Yes exactly - especially explaining the problems that those design principles are solving - effectively filling in the 'why' while the code example shows the 'how'/'what'.