Feedback using winnow to implement hcl-edit

[martinohmann]

Hi there @epage!

In #223 I promised you some feedback about using winnow to create the parser for hcl-edit. I didn't get to it in the past few weeks due to other obligations, but now I've got a little bit of time to note down some of the things I learnt.

Ergonomics

First of all I'd like to point out that the ergonomics of using winnow are much better than what I observed when initially starting out with nom. I like it a lot that &str, char, byte etc. also implement the Parser trait, which avoids a lot of wrapping in other combinators like char() or tag().

Also, converting some of the combinators into methods on the Parser trait really helps ergnonomics.

parser.context("foo").context("bar).context("baz").parse(input)

is certainly easier to follow than

context("foo", context("bar", context("baz", parser)(input)

Type inference

Type inference works really well in most cases, but the many* and separated* combinators in particular require to help the compiler via turbofish here and there. This is sometimes a bit cumbersome and adds noise since these functions have a ton of type parameters, but only the parameter with the Accumulate trait bound needs a type hint.

For example, I'm parsing whitespace interleaved with comments as follows, which wouldn't typecheck without the turbofish:

pub(super) fn ws(input: Input) -> IResult<Input, ()> {
    (multispace0, many0::<_, _, (), _, _>((comment, multispace0)))
        .void()
        .parse_next(input)
}

I hit this issue in quite a few other places where I just want to accumulate sequences into () and then pick them up with .span() or .recognize() later, so worked around this with a helper function that gets optimized away:

#[inline(always)]
pub(super) fn void<P, I, E>(inner: P) -> impl Parser<I, (), E>
where
    P: Parser<I, (), E>,
{
    inner
}

pub(super) fn ws(input: Input) -> IResult<Input, ()> {
    (multispace0, void(many0((comment, multispace0))))
        .void()
        .parse_next(input)
}

Combinators

I found that some combinators might be missing or are behaving differently to what I observed when using nom.

recognize

One example are .recognize() and .with_recognized(). They return Stream::Slice instead of Stream (which would be equivalent to the nom version of it returning the original input type).

Initially, i was doing something like this in nom where the input type was nom_locate::Located<&str>:

map_parser(recognize(first), second)(input)

Here the second parser will receive an input of type nom_locate::Located<&str>.

In winnow, the equivalent of this would be to use winnow::stream::Located<&str> as input and do something like this:

first.recognize().and_then(second).parse(input)

Now the problem is the following: second will receive a &str as input instead of winnow::stream::Located<&str>, which means I'm losing span information in the second parser. Even if I used .map_res() instead of .and_then() and did wrap the input in there via Located::new(output_of_first) and fed it into second, the span information is incorrect since it will reset the offset to 0.

But maybe I'm stupid and there is a way to work around this that I missed. 😉

If there would be a variant of .recognize() that returned a Stream instead of Stream::Slice it would have prevented me from doing this gnarly crime: https://github.com/martinohmann/hcl-rs/blob/503e827a6a7c1f9073aced44ea4977ea90265f13/crates/hcl-edit/src/parser/template.rs#L35-L77. This was much shorter and more elegant using nom and map_parser.

map-like combinator to work with Stateful

When using winnow::stream::Stateful<I, S> I didn't find a way to access and update the state within a map closure. I was thinking that it should be possible to have a Parser method like .map_with_state(f) that accepts a closure which receives the parser's output and a mutable reference to the state.

I'm not sure though if the borrow checker would like that, but was wondering if you experimented with something like that.

Why I'm bringing this up is because I copied your approach from toml_edit using a ParserState (e.g. here: https://github.com/martinohmann/hcl-rs/blob/2f5c9ad0e3f62edd59ac434ffd7942f4f252edb8/crates/hcl-edit/src/parser/expr.rs#L30-L89) to work around performance issues when large return types are involved (see below).

If it would be possible to manipulate the state of a Stateful input inside a map-like combinator, we could avoid littering parser functions signatures with the additional reference to the ParserState.

Performance footguns

I guess #191 would be really useful for people aiming to implement a performant parser. I found a couple of things that might be worth documenting. Maybe some of them can even be fixed.

Large return types

Since IResult<I, O, E> is essentially a Result<(I, O), E>, return type size is both influenced by the size of the input and the output types. You already track this via #72 which already shows that Located<&[u8]> increased parse time by 30% compared to &[u8] albeit being only twice as large.

Something like fn (&mut I) -> Result<O, E> vs. fn (I) -> Result<(I, O), E> might help to close this performance gap, but i'm wondering if it would make writing parser much less ergonomic.

One thing that further decreases performance are large output types. Surprisingly, I've seen quite big performance improvements by Box-ing large types that are passed though multiple layers of parser code. Of course, boxing by default is a performance footgun and usually makes the parser substantially slower.

In addition to that, tuple parsers should be used carefully as they can run into the same performance issues when multiple large output types are involved or if they simply have too many items in them.

E.g. i replaced something like

(a, b).map(...).parse_next(input)

with

let (input, a) = a.parse_next(input)?;
...
let (input, b) = b.parse_next(input)?;
...
Ok((input, ...))

in quite a few places to resolve performance issues.

"a" vs. 'a' vs. b'a' vs. b"a"

I had some confusion around parsers that accept all of these: b'a', 'a', b"a", "a". Which variant would yield the best performance? If there's a clear answer for the common case, maybe it's worth documenting that in the performance topic as well.

I've settled for using the byte variants in most cases but can remember that using the "wrong" variant in certain places had noticeable impacts on parser performance. Sadly I cannot find an example anymore where it really mattered.

Final words

I hope I didn't exclusively mention things that you're already aware of and this feedback is useful for you to further improve winnow.

If I happen to remember something else not already mentioned I'll try to add it here. 😄

[epage]

Thank you, this is very useful feedback!

I'll break down my comments by section so its easier to follow the threads

[epage]

btw any feedback for #95?

[martinohmann]

I can try to have a deeper look into it at a later point in time. All I can say is, while I'm also a bit obsessed with properly naming things, I cannot remember anything particular that stood out.

[epage]

Ergonomics

First of all I'd like to point out that the ergonomics of using winnow are much better than what I observed when initially starting out with nom. I like it a lot that &str, char, byte etc. also implement the Parser trait, which avoids a lot of wrapping in other combinators like char() or tag().

It is good to hear that this worked out for you!

And you are using the latest version which solved the type inference problems with this. That was my first concern when I saw the next section

[martinohmann]

Yep, type inference works good for these. One place I just found which I find confusing is that i can use take_until("foo"), but take_until(b"foo"). Not a big issue though I guess.

[epage]

take_until and take_till are two functions I want to change up; I just haven't decided how yet.

take_until works with FindSlice rather than using the same API as tag so it can be optimized with the simd feature (iirc). Hopefully we can add some more implementations and make it work. Feel free to create an issue so we don't lose track of this.

[epage]

recognize

One example are .recognize() and .with_recognized(). They return Stream::Slice instead of Stream (which would be equivalent to the nom version of it returning the original input type).

Yeah, I was torn when writing these on which use case to optimize for. length_value does serve as an example of how to workaround this. Its not obvious or ergonomic and this example isn't discoverable.

As for providing an ergonomic variant, the concern I have is making the API overwhelming. This is a problem we have in clap where there are so many knobs that you can't discover what you want exists. I've had a similar problem in using nom. I'm trying to consolidate and reduce the number to make things easier to discover, like with #98. I've been looking at chumsky with its map variants and not been thrilled by the combinatorial explosion of options and am trying to find a third-way to solve these problems even if there might not be a combinator that does the exact thing someone needs but instead they need to ... combine some combinators. I don't have a good idea yet on what we can/should do for improving this case.

[martinohmann]

Thanks for the hint towards length_value. I'll see if its internal implementation could be adjusted to my usecase to actually make the status quo better.

I'm fully with you in terms of reducing API surface to make it easier to discover what exists. In the end, I think the goal should be a minimal API that can be combined in various ways to build something more useful which is part of the user's parser code, but does not need to be bundled with winnow.

[epage]

Type inference

Type inference works really well in most cases, but the many* and separated* combinators in particular require to help the compiler via turbofish here and there. This is sometimes a bit cumbersome and adds noise since these functions have a ton of type parameters, but only the parameter with the Accumulate trait bound needs a type hint.

I've run into this myself. My first thought was to see if we could have a function on Parser that constrains O so you can more cleanly set just that one type but that didn't work.

One possible route is #98. I've been thinking of creating a repeated::<A: Accumulator>(range: ..) -> Repeated<A> that would allow repeated(10) * (comment, multispace0) instead of many(10, (comment, multispace0)). This would let you set the Accumulator type on just the repeated call. I was also thinking of offering a special case of skip(range: ...) -> Repeated<()> so you could do skip(10) * (comment, multispace0).

[martinohmann]

That sound interesting, but I wonder if "abusing" std::ops::Mul here would be a good idea. The short examples look nice and easy to understand, but in a bigger piece of code I could imagine that this could get confusing, especially when rustfmt tries to breaks it apart.

[epage]

For reference, ABNF which served as inspiration:

Variable repetition

n*nRule

To indicate repetition of an element, the form *element is used. The optional gives the minimal number of elements to be included (with the default of 0). The optional gives the maximal number of elements to be included (with the default of infinity).

Use element for zero or more elements, 1element for zero or one element, 1element for one or more elements, and 23element for two or three elements, cf. regular expressions e*, e?, e+ and e{2,3}.
Specific repetition

nRule

To indicate an explicit number of elements, the form element is used and is equivalent to *element.

Use 2DIGIT to get two numeric digits, and 3DIGIT to get three numeric digits. (DIGIT is defined below under "Core rules". Also see zip-code in the example below.)

(this doesn't mean its right to abuse operator overloading, just look at boost::spirit or any library that starts to use - to mean something)

[epage]

For comparison, the options are (using rustfmts single-line and multi-line rendering):

// `Fn` (Today)
repeated(10, (comment, multispace0))
repeated(
    10,
    (comment, multispace0)
)

// `Parser` (Chumsky)
(comment, multispace0).repeated(10)

(comment, multispace0)
    .repeated(10)

// `Mult` (Proposed)
repeated(10) * (comment, multispace0)

repeated(10)
    * (comment, multispace0)

For me, I feel like Parser obscures important information. That concern is what led to the current API style guide which bans combiantors on Parser that are significant* to the grammar

* Technically Parser::verify is significant but in a different way and closely coupled to whats its being used with

I might need to try it in toml_edit to get a bigger example, but Multi reads more clearly to me. For me, I think its the aspect of avoiding too many large, nested ()

[epage]

Large return types

Something like fn (&mut I) -> Result<O, E> vs. fn (I) -> Result<(I, O), E> might help to close this performance gap, but i'm wondering if it would make writing parser much less ergonomic.

I think I've found a framing that should keep things ergonomic. The nice thing is most of winnow is written the same way users would write code, so I can verify assumptions like that as I go.

The new framing is: on error, &mut I points to the error location. If you are doing a linear sets of parses with ?, that'll just work. alt and dispatch will take care of checking and restoring state. If you want to manually implement conditionals, that is where things will get a little more complicated but that shouldn't be too often (I hope?).

This would also allow users to drop I from the trivial error case because the location will be passed back up through &mut I.

One thing that further decreases performance are large output types. Surprisingly, I've seen quite big performance improvements by Box-ing large types that are passed though multiple layers of parser code. Of course, boxing by default is a performance footgun and usually makes the parser substantially slower.

I hadn't thought of that but that is a good point! I've linked to this discussion from the performance issue to make sure we include it. I also likely should go back and review some toml_edit code to see if changing it will make it faster.

[martinohmann]

Regarding manually implemented conditionals I can say that I don't have any of these in hcl-edit. The closest I could get to a manual conditional is this handrolled object item parser, which technically is a dispatch where one of the cases is an early return that does not further poke at the input: https://github.com/martinohmann/hcl-rs/blob/2f5c9ad0e3f62edd59ac434ffd7942f4f252edb8/crates/hcl-edit/src/parser/expr.rs#L378-L452

[martinohmann]

Just realized that I do use conditional parsing in one place: https://github.com/martinohmann/hcl-rs/blob/2f5c9ad0e3f62edd59ac434ffd7942f4f252edb8/crates/hcl-edit/src/parser/expr.rs#L45-L51

With &mut I there needs to be a way to manually rewind the input stream to support cases like this then.

[epage]

"a" vs. 'a' vs. b'a' vs. b"a"

I had some confusion around parsers that accept all of these: b'a', 'a', b"a", "a". Which variant would yield the best performance? If there's a clear answer for the common case, maybe it's worth documenting that in the performance topic as well.

I think these are mostly even. The one case if unexpected performance with different trait implementations, I plan to just remove (#226)

[martinohmann]

Another compiler performance footgun I can remember is returning a long combinator chain from a function, e.g. something like this:

fn foo() -> impl Parser<I, O, E> {
    (...some chained combinators...)
}

vs. this:

fn foo() -> impl Parser<I, O, E> {
    move |input: I| {
        (...some chained combinators...).parse_next(input)
    }
}

I had a case where the former variant increased the compile time in debug mode by around 30 seconds for an, if I remember correctly relatively innocent looking chain of combinators. I guess this generates very long deeply nested generic types that rustc has a hard time to process. Wrapping everything in an FnMut makes the compile time issue go away without any performance impact (at least I cannot remember).

[epage]

map-like combinator to work with Stateful

When using winnow::stream::Stateful<I, S> I didn't find a way to access and update the state within a map closure. I was thinking that it should be possible to have a Parser method like .map_with_state(f) that accepts a closure which receives the parser's output and a mutable reference to the state.

Yeah, right now hand-written parsers are the main way to deal with this. Which isn't necessarily bad in my opinion but if its used enough, we should likely help with it. With all the caveats we discussed in the other post about API bloat.

I think I'd general this to map_with_input / map_err_with_input or something so users can deal with any type of wrapped-input they want (like Location). The problem is

• This starts to look like a parser though it would likely be &I rather than &mut I (in future terms)
• Which input, before, after, or both

[epage]

If we switch to &mut I and call it map_with_stream, I think that might make it clearer that you are getting a snapshot of the stream at that time? Unsure. remaining bloats the name quiet a bit and I'm always suspicious of really long function names, feeling like they are either doing the wrong thing or there is a clearer way to explain it. That doesn't mean that my suspicion is always right though.

[martinohmann]

Long function names usually indicate that it's doing too many things at once. Or we accidently entered java-lang 😂.

Jokes aside, but struggling to come up with a good name for this might even indicate that this feature might not fit too well into the existing frame.

[epage]

Jokes aside, but struggling to come up with a good name for this might even indicate that this feature might not fit too well into the existing frame.

How about you create an issue for this and we sit on it for a bit to see how things evolve to see if a new idea comes up or if future changes provide a new opportunity.

[martinohmann]

Sounds like a plan, will try to do that next week.

[martinohmann]

Here's the issue for cross-referencing: #231

[epage]

@martinohmann in case you are interested in error recovery, I thought I'd let you know that I've started mapping out a design, see #96 (comment)