Error recovery support

[epage]

Please complete the following tasks

• I have searched the discussions
• I have searched the open and rejected issues

winnow version

0.2.0

Describe your use case

Some times a user will want to collect and report all errors or append semantic errors, like compilers do. See toml-rs/toml#371

Describe the solution you'd like

Error recovery support

https://eyalkalderon.com/blog/nom-error-recovery/ started to experiment with it based on the papers at https://arxiv.org/pdf/1806.11150.pdf

Alternatives, if applicable

No response

Additional Context

Tasks

• feat: Unstable support for error recovery #388
• Happy path for error reporting
• An example of error recovery

[epage]

See also rust-bakery/nom#499

[epage]

https://eyalkalderon.com/blog/nom-error-recovery/

• Only implements expect, a combinator that captures the error and picks up parsing from where it left off

https://arxiv.org/pdf/1806.11150.pdf

• Talks a lot about "skip all until delimiter" (;, }, etc)
• They fully leverage PEG parsers inside of recovery

https://docs.rs/chumsky/latest/chumsky/

• special top-level parse function that returns (Option<T>, Vec<Error>)
• Parser::parse returs Result<T, Vec<Error>>
• Parser::parse_inner (sort-of like our Parser::parse_next) returns (Vec<Error>, Result<T, Error>) (recovered errors, current error)
• Parser::recover_with combinator
  • Instead of returning Option<O>, it requires O to have a valid state
  • takes a Strategy
    • repeat_til-style
      • Parser's output is what is returned on failure
    • take_until-style
      • Takes a fallback function that chooses an output based on the span
      • Allows skipping first token
      • Allows skipping over the until value
    • take_until with retry
      • By retrying, we don't have to worry about O
      • Allows skipping first token
      • Allows skipping over the until value
    • nested delimiters
      • Takes a fallback function that chooses an output based on the span

[epage]

Proposal

Add

pub trait Recover<I: Stream, E> {
    // For `Stream`s other than `Recoverable` (like `&str`), this will reset the stream to `err_start` and return `err` back to the caller causing `Parser::parse` to behave as it does today. 
    // If performance is bad, maybe we could have a `is_recoverable` function to skip running the `recover` parser...
    fn record_err(&mut self, token_start: I::Checkpoint, err_start: I::Checkpoint, err: E) -> Result<(), E>;
}

pub struct Recoverable<I, E> {
    input: I,
    errors: Vec<E>,
    is_recoverable: bool,  // allow runtime deactivation so people don't have to make their parser generic over it if they need both modes, avoiding bloating the binary / compile times
}

pub trait Parser<I, O, E> {
    // ...

    fn parse_recovery<I1>(&mut self, input: I1) -> (O, Vec<E>) {
        // ... implicitly wraps `input` with `Recoverable` and then pulls out `Recoverable::Errors` and adds any trailing errors to it
    }

    fn resume_after(self, recover: impl Parser<I, O, E>)
      where I: Recover<I, E> {
        // ...
    }
    fn retry_after(self, recover: impl Parser<I, (), E>)
      where I: Recover<I, E> {
        // ...
    }
}

• Unlike chumsky, we track the errors in the Stream, rather than by passing them around, making this less intrusive
• When we recover, we allow recording the location where the recoverable parse started as well as where the error happened (since we don't capture that today and would be lost in this design)
• Like chumsky, the value on failure (when resuming) is determined by the recovery parser
• Unlike chumsky, all strategies are just parsers
  • We'd add a mod recovery for combinators specifically designed for recover purposes

We might also want to consider modifying our til parsers to have a consume_end method

An unknown to me is how to handle ErrMode

• Incomplete is unrecoverable, thats easy
• I can see recovering only Cut parsers as that means you aren't getting in the way of retrying alts, etc so you can put this on wider swaths of parsers and just let things work out
  • Sprinkling cut in all the right places would be annoying
• Conceptually, Cut should be unrecoverable but that gets in the way of error handling in light of alts

[epage]

Parser::parse_recovery isn't working because it constrains I of the parser. This will likely need to be an extension trait.