Provide a new type impl Alt which tries at last the parser which succeeded last time

[LambdaAlpha]

It's a common pattern to parsing like repeat(occurrences, alt((p1, p2, p3, ..., pn))), where pi never succeed if it succeeded last time.
The current impls of Alt for tuples always try from the first parser to the last parser.
We can add new type wrappers AlternateI for tuples, which records the index of last succeeded parser, and skip the parser when trying parsers in sequence and try it at last. We use it like repeat(occurrences, alt(AlternateN((p1, p2, p3, ..., pn)))). This will massively increase success rate when n is small, for example, when n = 2, we alternately try p1 and p2 which always succeed before exiting repeating.

[epage]

Let me rephrase to see if I understand.

The idea would be to have a stateful alt implementation that would record the last successful parser and on the next invocation it would prioritize trying that again. Oh, I think this is instead something else. This isn't about optimizing for repeating of the same content but for optimizing for unique content. De-prioritize the last successful parser so it gets tried last.

It is an interesting idea. I am concerned about generalizing that to being included in winnow though may be useful for people to provide it in a third-party.

alt is an if/else if ladder and is order dependent. Changing the order would fundamentally break its operation. That could be a caveat on this new type but I worry about it being clear enough for people to successfully use it, especially if its a first class feature.

The statefulness would have limited applicability because the state is recreated each time alt is called. For instance, changing alt() to |i| alt().parse_next would remove the statefulness.

alt can't actually be stateful right now. Either a new combinator would be needed or the Alt trait would need to be changed which would be a breaking change which we do but try to limit how often.

alts current implementation would also be complex to do in this way as we generate the code to try each branch one after the next. #810 would offer an easier to work with way of doing this.

We also have to weigh the API cost for new features. The more that exists in an API, the harder it is to find what you need and the less you use of everything that exists. We've been actively working to shrink our API (through composability). For things that we add, we need to ask if the cost of adding it is worth the benefit. For the benefit, we consider how strong the benefit is and how many people are likely to leverage it.

[LambdaAlpha]

Let me give an real example for what this is about optimizing for.
my_until_newline is a parser which takes input until a \n or a \r\n. Notice that no_rn will never succeed if it succeed last time, same as r_only. For a string "a\rb\rc\rd\re", my_until_newline tries no_rn before only_r for every \r in iteration, which is a waste of computing.

fn my_until_newline<'a>(i: &mut &'a str) -> ModalResult<&'a str> {
    let no_rn = take_till(1 .., |c| matches!(c, '\r' | '\n')).void();
    let only_r = ('\r', peek(not('\n'))).void();
    repeat(0 .., alt((no_rn, only_r))).map(|()| ()).take().parse_next(i)
}

This applies to anything composed by a sequence of fragments where the same kind of fragments are not adjacent.

So we need a new stateful type which impl Alt trait, not a new stateful alt function. I'm not familiar with the Alt trait, but I think it's doable because it takes &mut self.

pub struct AltTuple2<A1, A2> {
    a1: A1,
    a2: A2,
    last_a1: bool,
}

impl<A1, A2> AltTuple2<A1, A2> {
    pub fn new(a1: A1, a2: A2) -> Self {
        Self {a1, a2, last_a1: false}
    }
}

impl<I: Stream, O, E: ParserError<I>, A1: Parser<I, O, E>, A2: Parser<I, O, E>> Alt<I, O, E> for AltTuple2<A1, A2> {
    fn choice(&mut self, input: &mut I) -> Result<O, E> {
        if self.last_a1 {
            // if a2 succeed, last_a1 = false
            // if a1 succeed, last_a1 = true
        } else {
            // if a1 succeed, last_a1 = true
            // if a2 succeed, last_a1 = false
        }
    }
}

fn my_until_newline<'a>(i: &mut &'a str) -> ModalResult<&'a str> {
    let no_rn = take_till(1 .., |c| matches!(c, '\r' | '\n')).void();
    let only_r = ('\r', peek(not('\n'))).void();
    repeat(0 .., alt(AltTuple2::new(no_rn, only_r))).map(|()| ()).take().parse_next(i)
}

I know it's hard to impl a stateful Alt and it may not compose well, but I think the need for sth like it is real and common. It's fine that this problem is solved by any other means.

[epage]

To double check my understanding, shouldn't that be

        if self.last_a1 {
            // if a1 succeed, last_a1 = true
            // if a2 succeed, last_a1 = false
        } else {
            // if a2 succeed, last_a1 = false
            // if a1 succeed, last_a1 = true
        }

Either way, several of my concerns are still relevant

• order dependence of alt
• gotchas due to when the state is recreated
• general complexity cost of this
• feels like it has limited general applicability

Some other things to consider, at least for this example code

• Using take_until instead of take_till
• Whether manually checking would be better than an alt

For an idea of what I mean, check out implementation of till_line_ending at https://docs.rs/winnow/latest/src/winnow/ascii/mod.rs.html#168-201

[LambdaAlpha]

To double check my understanding, shouldn't that be

No, last_a1 means a1 succeeded last time, which is initialized to false.
Take string "a\rb\rc" for example,

• last_a1 is false, so we try a2 at last, which means try a1 first, a1 suceed with ("a", "\rb\rc"), we set last_a1 to true,
• in next repeatation, last_a1 is true, so we try a1 at last, which means try a2 first, a2 succeed with ("\r", "b\rc"), we set last_a1 to false
• in next repeatation, last_a1 is false, so we try a2 at last, which means try a1 first, a1 succeed with ("b", "\rc"), we set last_a1 to true
• in next repeatation, last_a1 is true, so we try a1 at last, which means try a2 first, a2 succeed with ("\r", "c"), we set last_a1 to false
• in next repeatation, last_a1 is false, so we try a2 at last, which means try a1 first, a1 succeed with ("c", ""), we set last_a1 to true
• in next repeatation, last_a1 is true, so we try a1 at last, which means try a2 first, a2 failes, we try a1 then, a1 failes too, the repeatation ends

You can see in each repeatation, we succeed at first try.

Using take_until instead of take_till

Ok, it seems better.

Whether manually checking would be better than an alt

Maybe not better, because no_rn and only_r both fail quickly.