chumsky/
recovery.rs

1//! Types and traits that facilitate error recovery.
2//!
3//! *“Do you find coming to terms with the mindless tedium of it all presents an interesting challenge?”*
4
5use super::*;
6
7/// A trait implemented by error recovery strategies.
8pub trait Strategy<I: Clone, O, E: Error<I>> {
9    /// Recover from a parsing failure.
10    fn recover<D: Debugger, P: Parser<I, O, Error = E>>(
11        &self,
12        recovered_errors: Vec<Located<I, P::Error>>,
13        fatal_error: Located<I, P::Error>,
14        parser: P,
15        debugger: &mut D,
16        stream: &mut StreamOf<I, P::Error>,
17    ) -> PResult<I, O, P::Error>;
18}
19
20/// See [`skip_then_retry_until`].
21#[must_use]
22#[derive(Copy, Clone)]
23pub struct SkipThenRetryUntil<I, const N: usize>(
24    pub(crate) [I; N],
25    pub(crate) bool,
26    pub(crate) bool,
27);
28
29impl<I, const N: usize> SkipThenRetryUntil<I, N> {
30    /// Alters this recovery strategy so that the first token will always be skipped.
31    ///
32    /// This is useful when the input being searched for also appears at the beginning of the pattern that failed to
33    /// parse.
34    pub fn skip_start(self) -> Self {
35        Self(self.0, self.1, true)
36    }
37
38    /// Alters this recovery strategy so that the synchronisation token will be consumed during recovery.
39    ///
40    /// This is useful when the input being searched for is a delimiter of a prior pattern rather than the start of a
41    /// new pattern and hence is no longer important once recovery has occurred.
42    pub fn consume_end(self) -> Self {
43        Self(self.0, true, self.2)
44    }
45}
46
47impl<I: Clone + PartialEq, O, E: Error<I>, const N: usize> Strategy<I, O, E>
48    for SkipThenRetryUntil<I, N>
49{
50    fn recover<D: Debugger, P: Parser<I, O, Error = E>>(
51        &self,
52        a_errors: Vec<Located<I, P::Error>>,
53        a_err: Located<I, P::Error>,
54        parser: P,
55        debugger: &mut D,
56        stream: &mut StreamOf<I, P::Error>,
57    ) -> PResult<I, O, P::Error> {
58        if self.2 {
59            let _ = stream.next();
60        }
61        loop {
62            #[allow(deprecated)]
63            let (mut errors, res) = stream.try_parse(|stream| {
64                #[allow(deprecated)]
65                debugger.invoke(&parser, stream)
66            });
67            if let Ok(out) = res {
68                errors.push(a_err);
69                break (errors, Ok(out));
70            }
71            #[allow(clippy::blocks_in_if_conditions)]
72            if !stream.attempt(
73                |stream| match stream.next().2.map(|tok| self.0.contains(&tok)) {
74                    Some(true) => (self.1, false),
75                    Some(false) => (true, true),
76                    None => (false, false),
77                },
78            ) {
79                break (a_errors, Err(a_err));
80            }
81        }
82    }
83}
84
85/// A recovery mode that simply skips to the next input on parser failure and tries again, until reaching one of
86/// several inputs.
87///
88/// Also see [`SkipThenRetryUntil::consume_end`].
89///
90/// This strategy is very 'stupid' and can result in very poor error generation in some languages. Place this strategy
91/// after others as a last resort, and be careful about over-using it.
92pub fn skip_then_retry_until<I, const N: usize>(until: [I; N]) -> SkipThenRetryUntil<I, N> {
93    SkipThenRetryUntil(until, false, true)
94}
95
96/// See [`skip_until`].
97#[must_use]
98#[derive(Copy, Clone)]
99pub struct SkipUntil<I, F, const N: usize>(
100    pub(crate) [I; N],
101    pub(crate) F,
102    pub(crate) bool,
103    pub(crate) bool,
104);
105
106impl<I, F, const N: usize> SkipUntil<I, F, N> {
107    /// Alters this recovery strategy so that the first token will always be skipped.
108    ///
109    /// This is useful when the input being searched for also appears at the beginning of the pattern that failed to
110    /// parse.
111    pub fn skip_start(self) -> Self {
112        Self(self.0, self.1, self.2, true)
113    }
114
115    /// Alters this recovery strategy so that the synchronisation token will be consumed during recovery.
116    ///
117    /// This is useful when the input being searched for is a delimiter of a prior pattern rather than the start of a
118    /// new pattern and hence is no longer important once recovery has occurred.
119    pub fn consume_end(self) -> Self {
120        Self(self.0, self.1, true, self.3)
121    }
122}
123
124impl<I: Clone + PartialEq, O, F: Fn(E::Span) -> O, E: Error<I>, const N: usize> Strategy<I, O, E>
125    for SkipUntil<I, F, N>
126{
127    fn recover<D: Debugger, P: Parser<I, O, Error = E>>(
128        &self,
129        mut a_errors: Vec<Located<I, P::Error>>,
130        a_err: Located<I, P::Error>,
131        _parser: P,
132        _debugger: &mut D,
133        stream: &mut StreamOf<I, P::Error>,
134    ) -> PResult<I, O, P::Error> {
135        let pre_state = stream.save();
136        if self.3 {
137            let _ = stream.next();
138        }
139        a_errors.push(a_err);
140        loop {
141            match stream.attempt(|stream| {
142                let (at, span, tok) = stream.next();
143                match tok.map(|tok| self.0.contains(&tok)) {
144                    Some(true) => (self.2, Ok(true)),
145                    Some(false) => (true, Ok(false)),
146                    None => (true, Err((at, span))),
147                }
148            }) {
149                Ok(true) => break (a_errors, Ok(((self.1)(stream.span_since(pre_state)), None))),
150                Ok(false) => {}
151                Err(_) if stream.save() > pre_state => {
152                    break (a_errors, Ok(((self.1)(stream.span_since(pre_state)), None)))
153                }
154                Err((at, span)) => {
155                    break (
156                        a_errors,
157                        Err(Located::at(
158                            at,
159                            E::expected_input_found(span, self.0.iter().cloned().map(Some), None),
160                        )),
161                    )
162                }
163            }
164        }
165    }
166}
167
168/// A recovery mode that skips input until one of several inputs is found.
169///
170/// Also see [`SkipUntil::consume_end`].
171///
172/// This strategy is very 'stupid' and can result in very poor error generation in some languages. Place this strategy
173/// after others as a last resort, and be careful about over-using it.
174pub fn skip_until<I, F, const N: usize>(until: [I; N], fallback: F) -> SkipUntil<I, F, N> {
175    SkipUntil(until, fallback, false, false)
176}
177
178/// See [`nested_delimiters`].
179#[must_use]
180#[derive(Copy, Clone)]
181pub struct NestedDelimiters<I, F, const N: usize>(
182    pub(crate) I,
183    pub(crate) I,
184    pub(crate) [(I, I); N],
185    pub(crate) F,
186);
187
188impl<I: Clone + PartialEq, O, F: Fn(E::Span) -> O, E: Error<I>, const N: usize> Strategy<I, O, E>
189    for NestedDelimiters<I, F, N>
190{
191    // This looks like something weird with clippy, it warns in a weird spot and isn't fixed by
192    // marking it at the spot.
193    #[allow(clippy::blocks_in_if_conditions)]
194    fn recover<D: Debugger, P: Parser<I, O, Error = E>>(
195        &self,
196        mut a_errors: Vec<Located<I, P::Error>>,
197        a_err: Located<I, P::Error>,
198        _parser: P,
199        _debugger: &mut D,
200        stream: &mut StreamOf<I, P::Error>,
201    ) -> PResult<I, O, P::Error> {
202        let mut balance = 0;
203        let mut balance_others = [0; N];
204        let mut starts = Vec::new();
205        let mut error = None;
206        let pre_state = stream.save();
207        let recovered = loop {
208            if match stream.next() {
209                (_, span, Some(t)) if t == self.0 => {
210                    balance += 1;
211                    starts.push(span);
212                    true
213                }
214                (_, _, Some(t)) if t == self.1 => {
215                    balance -= 1;
216                    starts.pop();
217                    true
218                }
219                (at, span, Some(t)) => {
220                    for (balance_other, others) in balance_others.iter_mut().zip(self.2.iter()) {
221                        if t == others.0 {
222                            *balance_other += 1;
223                        } else if t == others.1 {
224                            *balance_other -= 1;
225
226                            if *balance_other < 0 && balance == 1 {
227                                // stream.revert(pre_state);
228                                error.get_or_insert_with(|| {
229                                    Located::at(
230                                        at,
231                                        P::Error::unclosed_delimiter(
232                                            starts.pop().unwrap(),
233                                            self.0.clone(),
234                                            span.clone(),
235                                            self.1.clone(),
236                                            Some(t.clone()),
237                                        ),
238                                    )
239                                });
240                            }
241                        }
242                    }
243                    false
244                }
245                (at, span, None) => {
246                    if balance > 0 && balance == 1 {
247                        error.get_or_insert_with(|| match starts.pop() {
248                            Some(start) => Located::at(
249                                at,
250                                P::Error::unclosed_delimiter(
251                                    start,
252                                    self.0.clone(),
253                                    span,
254                                    self.1.clone(),
255                                    None,
256                                ),
257                            ),
258                            None => Located::at(
259                                at,
260                                P::Error::expected_input_found(
261                                    span,
262                                    Some(Some(self.1.clone())),
263                                    None,
264                                ),
265                            ),
266                        });
267                    }
268                    break false;
269                }
270            } {
271                match balance.cmp(&0) {
272                    Ordering::Equal => break true,
273                    // The end of a delimited section is not a valid recovery pattern
274                    Ordering::Less => break false,
275                    Ordering::Greater => (),
276                }
277            } else if balance == 0 {
278                // A non-delimiter input before anything else is not a valid recovery pattern
279                break false;
280            }
281        };
282
283        if let Some(e) = error {
284            a_errors.push(e);
285        }
286
287        if recovered {
288            if a_errors.last().map_or(true, |e| a_err.at < e.at) {
289                a_errors.push(a_err);
290            }
291            (a_errors, Ok(((self.3)(stream.span_since(pre_state)), None)))
292        } else {
293            (a_errors, Err(a_err))
294        }
295    }
296}
297
298/// A recovery strategy that searches for a start and end delimiter, respecting nesting.
299///
300/// It is possible to specify additional delimiter pairs that are valid in the pattern's context for better errors. For
301/// example, you might want to also specify `[('[', ']'), ('{', '}')]` when recovering a parenthesised expression as
302/// this can aid in detecting delimiter mismatches.
303///
304/// A function that generates a fallback output on recovery is also required.
305pub fn nested_delimiters<I: PartialEq, F, const N: usize>(
306    start: I,
307    end: I,
308    others: [(I, I); N],
309    fallback: F,
310) -> NestedDelimiters<I, F, N> {
311    assert!(
312        start != end,
313        "Start and end delimiters cannot be the same when using `NestedDelimiters`"
314    );
315    NestedDelimiters(start, end, others, fallback)
316}
317
318/// See [`skip_parser`].
319#[derive(Copy, Clone)]
320pub struct SkipParser<R>(pub(crate) R);
321
322impl<I: Clone + PartialEq, O, R: Parser<I, O, Error = E>, E: Error<I>> Strategy<I, O, E>
323    for SkipParser<R>
324{
325    fn recover<D: Debugger, P: Parser<I, O, Error = E>>(
326        &self,
327        mut a_errors: Vec<Located<I, P::Error>>,
328        a_err: Located<I, P::Error>,
329        _parser: P,
330        debugger: &mut D,
331        stream: &mut StreamOf<I, P::Error>,
332    ) -> PResult<I, O, P::Error> {
333        a_errors.push(a_err);
334
335        let (mut errors, res) = self.0.parse_inner(debugger, stream);
336        a_errors.append(&mut errors);
337        (a_errors, res)
338    }
339}
340
341/// A recovery mode that applies the provided recovery parser to determine the content to skip.
342///
343/// ```
344/// # use chumsky::prelude::*;
345/// #[derive(Clone, Debug, PartialEq, Eq, Hash)]
346/// enum Token {
347///     GoodKeyword,
348///     BadKeyword,
349///     Newline,
350/// }
351///
352/// #[derive(Clone, Debug, PartialEq, Eq, Hash)]
353/// enum AST {
354///     GoodLine,
355///     Error,
356/// }
357///
358/// // The happy path...
359/// let goodline = just::<Token, _, Simple<_>>(Token::GoodKeyword)
360///     .ignore_then(none_of(Token::Newline).repeated().to(AST::GoodLine))
361///     .then_ignore(just(Token::Newline));
362///
363/// // If it fails, swallow everything up to a newline, but only if the line
364/// // didn't contain BadKeyword which marks an alternative parse route that
365/// // we want to accept instead.
366/// let goodline_with_recovery = goodline.recover_with(skip_parser(
367///     none_of([Token::Newline, Token::BadKeyword])
368///         .repeated()
369///         .then_ignore(just(Token::Newline))
370///         .to(AST::Error),
371/// ));
372/// ```
373
374pub fn skip_parser<R>(recovery_parser: R) -> SkipParser<R> {
375    SkipParser(recovery_parser)
376}
377
378/// A parser that includes a fallback recovery strategy should parsing result in an error.
379#[must_use]
380#[derive(Copy, Clone)]
381pub struct Recovery<A, S>(pub(crate) A, pub(crate) S);
382
383impl<I: Clone, O, A: Parser<I, O, Error = E>, S: Strategy<I, O, E>, E: Error<I>> Parser<I, O>
384    for Recovery<A, S>
385{
386    type Error = E;
387
388    fn parse_inner<D: Debugger>(
389        &self,
390        debugger: &mut D,
391        stream: &mut StreamOf<I, E>,
392    ) -> PResult<I, O, E> {
393        match stream.try_parse(|stream| {
394            #[allow(deprecated)]
395            debugger.invoke(&self.0, stream)
396        }) {
397            (a_errors, Ok(a_out)) => (a_errors, Ok(a_out)),
398            (a_errors, Err(a_err)) => self.1.recover(a_errors, a_err, &self.0, debugger, stream),
399        }
400    }
401
402    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, O, E> {
403        #[allow(deprecated)]
404        self.parse_inner(d, s)
405    }
406    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, O, E> {
407        #[allow(deprecated)]
408        self.parse_inner(d, s)
409    }
410}
411
412#[cfg(test)]
413mod tests {
414    use crate::error::Cheap;
415    use crate::prelude::*;
416
417    #[test]
418    fn recover_with_skip_then_retry_until() {
419        let parser = just::<_, _, Cheap<_>>('a')
420            .recover_with(skip_then_retry_until([',']))
421            .separated_by(just(','));
422        {
423            let (result, errors) = parser.parse_recovery("a,a,2a,a");
424            assert_eq!(result, Some(vec!['a', 'a', 'a', 'a']));
425            assert_eq!(errors.len(), 1)
426        }
427        {
428            let (result, errors) = parser.parse_recovery("a,a,2 a,a");
429            assert_eq!(result, Some(vec!['a', 'a', 'a', 'a']));
430            assert_eq!(errors.len(), 1)
431        }
432        {
433            let (result, errors) = parser.parse_recovery("a,a,2  a,a");
434            assert_eq!(result, Some(vec!['a', 'a', 'a', 'a']));
435            assert_eq!(errors.len(), 1)
436        }
437    }
438
439    #[test]
440    fn until_nothing() {
441        #[derive(Debug, Clone, Copy, PartialEq)]
442        pub enum Token {
443            Foo,
444            Bar,
445        }
446
447        fn lexer() -> impl Parser<char, Token, Error = Simple<char>> {
448            let foo = just("foo").to(Token::Foo);
449            let bar = just("bar").to(Token::Bar);
450
451            choice((foo, bar)).recover_with(skip_then_retry_until([]))
452        }
453
454        let (result, errors) = lexer().parse_recovery("baz");
455        assert_eq!(result, None);
456        assert_eq!(errors.len(), 1);
457    }
458}
chumsky/recovery.rs

chumsky/
recovery.rs
