chumsky/
error.rs

1//! Error types, traits and utilities.
2//!
3//! *“I like the cover," he said. "Don't Panic. It's the first helpful or intelligible thing anybody's said to me all
4//! day.”*
5//!
6//! You can implement the [`Error`] trait to create your own parser errors, or you can use one provided by the crate
7//! like [`Simple`] or [`Cheap`].
8
9use super::*;
10use alloc::{format, string::ToString};
11use core::hash::Hash;
12
13#[cfg(not(feature = "std"))]
14use hashbrown::HashSet;
15#[cfg(feature = "std")]
16use std::collections::HashSet;
17
18// (ahash + std) => ahash
19// (ahash)       => ahash
20// (std)         => std
21// ()            => ahash
22#[cfg(any(feature = "ahash", not(feature = "std")))]
23type RandomState = hashbrown::hash_map::DefaultHashBuilder;
24#[cfg(all(not(feature = "ahash"), feature = "std"))]
25type RandomState = std::collections::hash_map::RandomState;
26
27/// A trait that describes parser error types.
28///
29/// If you have a custom error type in your compiler, or your needs are not sufficiently met by [`Simple`], you should
30/// implement this trait. If your error type has 'extra' features that allow for more specific error messages, you can
31/// use the [`Parser::map_err`] or [`Parser::try_map`] functions to take advantage of these inline within your parser.
32///
33/// # Examples
34///
35/// ```
36/// # use chumsky::{prelude::*, error::Cheap};
37/// type Span = std::ops::Range<usize>;
38///
39/// // A custom error type
40/// #[derive(Debug, PartialEq)]
41/// enum MyError {
42///     ExpectedFound(Span, Vec<Option<char>>, Option<char>),
43///     NotADigit(Span, char),
44/// }
45///
46/// impl chumsky::Error<char> for MyError {
47///     type Span = Span;
48///     type Label = ();
49///
50///     fn expected_input_found<Iter: IntoIterator<Item = Option<char>>>(
51///         span: Span,
52///         expected: Iter,
53///         found: Option<char>,
54///     ) -> Self {
55///         Self::ExpectedFound(span, expected.into_iter().collect(), found)
56///     }
57///
58///     fn with_label(mut self, label: Self::Label) -> Self { self }
59///
60///     fn merge(mut self, mut other: Self) -> Self {
61///         if let (Self::ExpectedFound(_, expected, _), Self::ExpectedFound(_, expected_other, _)) = (
62///             &mut self,
63///             &mut other,
64///         ) {
65///             expected.append(expected_other);
66///         }
67///         self
68///     }
69/// }
70///
71/// let numeral = filter_map(|span, c: char| match c.to_digit(10) {
72///     Some(x) => Ok(x),
73///     None => Err(MyError::NotADigit(span, c)),
74/// });
75///
76/// assert_eq!(numeral.parse("3"), Ok(3));
77/// assert_eq!(numeral.parse("7"), Ok(7));
78/// assert_eq!(numeral.parse("f"), Err(vec![MyError::NotADigit(0..1, 'f')]));
79/// ```
80pub trait Error<I>: Sized {
81    /// The type of spans to be used in the error.
82    type Span: Span; // TODO: Default to = Range<usize>;
83
84    /// The label used to describe a syntactic structure currently being parsed.
85    ///
86    /// This can be used to generate errors that tell the user what syntactic structure was currently being parsed when
87    /// the error occurred.
88    type Label; // TODO: Default to = &'static str;
89
90    /// Create a new error describing a conflict between expected inputs and that which was actually found.
91    ///
92    /// `found` having the value `None` indicates that the end of input was reached, but was not expected.
93    ///
94    /// An expected input having the value `None` indicates that the end of input was expected.
95    fn expected_input_found<Iter: IntoIterator<Item = Option<I>>>(
96        span: Self::Span,
97        expected: Iter,
98        found: Option<I>,
99    ) -> Self;
100
101    /// Create a new error describing a delimiter that was not correctly closed.
102    ///
103    /// Provided to this function is the span of the unclosed delimiter, the delimiter itself, the span of the input
104    /// that was found in its place, the closing delimiter that was expected but not found, and the input that was
105    /// found in its place.
106    ///
107    /// The default implementation of this function uses [`Error::expected_input_found`], but you'll probably want to
108    /// implement it yourself to take full advantage of the extra diagnostic information.
109    fn unclosed_delimiter(
110        unclosed_span: Self::Span,
111        unclosed: I,
112        span: Self::Span,
113        expected: I,
114        found: Option<I>,
115    ) -> Self {
116        #![allow(unused_variables)]
117        Self::expected_input_found(span, Some(Some(expected)), found)
118    }
119
120    /// Indicate that the error occurred while parsing a particular syntactic structure.
121    ///
122    /// How the error handles this information is up to it. It can append it to a list of structures to get a sort of
123    /// 'parse backtrace', or it can just keep only the most recent label. If the latter, this method should have no
124    /// effect when the error already has a label.
125    fn with_label(self, label: Self::Label) -> Self;
126
127    /// Merge two errors that point to the same input together, combining their information.
128    fn merge(self, other: Self) -> Self;
129}
130
131// /// A simple default input pattern that allows describing inputs and input patterns in error messages.
132// #[derive(Clone, Debug, PartialEq, Eq, Hash)]
133// pub enum SimplePattern<I> {
134//     /// A pattern with the given name was expected.
135//     Labelled(&'static str),
136//     /// A specific input was expected.
137//     Token(I),
138// }
139
140// impl<I> From<&'static str> for SimplePattern<I> {
141//     fn from(s: &'static str) -> Self { Self::Labelled(s) }
142// }
143
144// impl<I: fmt::Display> fmt::Display for SimplePattern<I> {
145//     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
146//         match self {
147//             Self::Labelled(s) => write!(f, "{}", s),
148//             Self::Token(x) => write!(f, "'{}'", x),
149//         }
150//     }
151// }
152
153/// A type representing possible reasons for an error.
154#[derive(Clone, Debug, PartialEq, Eq)]
155pub enum SimpleReason<I, S> {
156    /// An unexpected input was found.
157    Unexpected,
158    /// An unclosed delimiter was found.
159    Unclosed {
160        /// The span of the unclosed delimiter.
161        span: S,
162        /// The unclosed delimiter.
163        delimiter: I,
164    },
165    /// An error with a custom message occurred.
166    Custom(String),
167}
168
169impl<I: fmt::Display, S: fmt::Display> fmt::Display for SimpleReason<I, S> {
170    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
171        const DEFAULT_DISPLAY_UNEXPECTED: &str = "unexpected input";
172
173        match self {
174            Self::Unexpected => write!(f, "{}", DEFAULT_DISPLAY_UNEXPECTED),
175            Self::Unclosed { span, delimiter } => {
176                write!(f, "unclosed delimiter ({}) in {}", span, delimiter)
177            }
178            Self::Custom(string) => write!(f, "error {}", string),
179        }
180    }
181}
182
183/// A type representing zero, one, or many labels applied to an error
184#[derive(Clone, Copy, Debug, PartialEq)]
185enum SimpleLabel {
186    Some(&'static str),
187    None,
188    Multi,
189}
190
191impl SimpleLabel {
192    fn merge(self, other: Self) -> Self {
193        match (self, other) {
194            (SimpleLabel::Some(a), SimpleLabel::Some(b)) if a == b => SimpleLabel::Some(a),
195            (SimpleLabel::Some(_), SimpleLabel::Some(_)) => SimpleLabel::Multi,
196            (SimpleLabel::Multi, _) => SimpleLabel::Multi,
197            (_, SimpleLabel::Multi) => SimpleLabel::Multi,
198            (SimpleLabel::None, x) => x,
199            (x, SimpleLabel::None) => x,
200        }
201    }
202}
203
204impl From<SimpleLabel> for Option<&'static str> {
205    fn from(label: SimpleLabel) -> Self {
206        match label {
207            SimpleLabel::Some(s) => Some(s),
208            _ => None,
209        }
210    }
211}
212
213/// A simple default error type that tracks error spans, expected inputs, and the actual input found at an error site.
214///
215/// Please note that it uses a [`HashSet`] to remember expected symbols. If you find this to be too slow, you can
216/// implement [`Error`] for your own error type or use [`Cheap`] instead.
217#[derive(Clone, Debug)]
218pub struct Simple<I: Hash + Eq, S = Range<usize>> {
219    span: S,
220    reason: SimpleReason<I, S>,
221    expected: HashSet<Option<I>, RandomState>,
222    found: Option<I>,
223    label: SimpleLabel,
224}
225
226impl<I: Hash + Eq, S: Clone> Simple<I, S> {
227    /// Create an error with a custom error message.
228    pub fn custom<M: ToString>(span: S, msg: M) -> Self {
229        Self {
230            span,
231            reason: SimpleReason::Custom(msg.to_string()),
232            expected: HashSet::default(),
233            found: None,
234            label: SimpleLabel::None,
235        }
236    }
237
238    /// Returns the span that the error occurred at.
239    pub fn span(&self) -> S {
240        self.span.clone()
241    }
242
243    /// Returns an iterator over possible expected patterns.
244    pub fn expected(&self) -> impl ExactSizeIterator<Item = &Option<I>> + '_ {
245        self.expected.iter()
246    }
247
248    /// Returns the input, if any, that was found instead of an expected pattern.
249    pub fn found(&self) -> Option<&I> {
250        self.found.as_ref()
251    }
252
253    /// Returns the reason for the error.
254    pub fn reason(&self) -> &SimpleReason<I, S> {
255        &self.reason
256    }
257
258    /// Returns the error's label, if any.
259    pub fn label(&self) -> Option<&'static str> {
260        self.label.into()
261    }
262
263    /// Map the error's inputs using the given function.
264    ///
265    /// This can be used to unify the errors between parsing stages that operate upon two forms of input (for example,
266    /// the initial lexing stage and the parsing stage in most compilers).
267    pub fn map<U: Hash + Eq, F: FnMut(I) -> U>(self, mut f: F) -> Simple<U, S> {
268        Simple {
269            span: self.span,
270            reason: match self.reason {
271                SimpleReason::Unclosed { span, delimiter } => SimpleReason::Unclosed {
272                    span,
273                    delimiter: f(delimiter),
274                },
275                SimpleReason::Unexpected => SimpleReason::Unexpected,
276                SimpleReason::Custom(msg) => SimpleReason::Custom(msg),
277            },
278            expected: self.expected.into_iter().map(|e| e.map(&mut f)).collect(),
279            found: self.found.map(f),
280            label: self.label,
281        }
282    }
283}
284
285impl<I: Hash + Eq, S: Span + Clone + fmt::Debug> Error<I> for Simple<I, S> {
286    type Span = S;
287    type Label = &'static str;
288
289    fn expected_input_found<Iter: IntoIterator<Item = Option<I>>>(
290        span: Self::Span,
291        expected: Iter,
292        found: Option<I>,
293    ) -> Self {
294        Self {
295            span,
296            reason: SimpleReason::Unexpected,
297            expected: expected.into_iter().collect(),
298            found,
299            label: SimpleLabel::None,
300        }
301    }
302
303    fn unclosed_delimiter(
304        unclosed_span: Self::Span,
305        delimiter: I,
306        span: Self::Span,
307        expected: I,
308        found: Option<I>,
309    ) -> Self {
310        Self {
311            span,
312            reason: SimpleReason::Unclosed {
313                span: unclosed_span,
314                delimiter,
315            },
316            expected: core::iter::once(Some(expected)).collect(),
317            found,
318            label: SimpleLabel::None,
319        }
320    }
321
322    fn with_label(mut self, label: Self::Label) -> Self {
323        match self.label {
324            SimpleLabel::Some(_) => {}
325            _ => {
326                self.label = SimpleLabel::Some(label);
327            }
328        }
329        self
330    }
331
332    fn merge(mut self, other: Self) -> Self {
333        // TODO: Assert that `self.span == other.span` here?
334        self.reason = match (&self.reason, &other.reason) {
335            (SimpleReason::Unclosed { .. }, _) => self.reason,
336            (_, SimpleReason::Unclosed { .. }) => other.reason,
337            _ => self.reason,
338        };
339        self.label = self.label.merge(other.label);
340        for expected in other.expected {
341            self.expected.insert(expected);
342        }
343        self
344    }
345}
346
347impl<I: Hash + Eq, S: PartialEq> PartialEq for Simple<I, S> {
348    fn eq(&self, other: &Self) -> bool {
349        self.span == other.span
350            && self.found == other.found
351            && self.reason == other.reason
352            && self.label == other.label
353    }
354}
355
356impl<I: Hash + Eq, S: Eq> Eq for Simple<I, S> {}
357
358impl<I: fmt::Display + Hash + Eq, S: Span> fmt::Display for Simple<I, S> {
359    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
360        // TODO: Take `self.reason` into account
361
362        if let Some(found) = &self.found {
363            write!(f, "found {:?}", found.to_string())?;
364        } else {
365            write!(f, "found end of input")?;
366        };
367
368        match self.expected.len() {
369            0 => {} //write!(f, " but end of input was expected")?,
370            1 => write!(
371                f,
372                " but expected {}",
373                match self.expected.iter().next().unwrap() {
374                    Some(x) => format!("{:?}", x.to_string()),
375                    None => "end of input".to_string(),
376                },
377            )?,
378            _ => {
379                write!(
380                    f,
381                    " but expected one of {}",
382                    self.expected
383                        .iter()
384                        .map(|expected| match expected {
385                            Some(x) => format!("{:?}", x.to_string()),
386                            None => "end of input".to_string(),
387                        })
388                        .collect::<Vec<_>>()
389                        .join(", ")
390                )?;
391            }
392        }
393
394        Ok(())
395    }
396}
397
398#[cfg(feature = "std")]
399impl<I: fmt::Debug + fmt::Display + Hash + Eq, S: Span + fmt::Display + fmt::Debug>
400    std::error::Error for Simple<I, S>
401{
402}
403
404/// A minimal error type that tracks only the error span and label. This type is most useful when you want fast parsing
405/// but do not particularly care about the quality of error messages.
406#[derive(Clone, Debug, PartialEq, Eq)]
407pub struct Cheap<I, S = Range<usize>> {
408    span: S,
409    label: Option<&'static str>,
410    phantom: PhantomData<I>,
411}
412
413impl<I, S: Clone> Cheap<I, S> {
414    /// Returns the span that the error occurred at.
415    pub fn span(&self) -> S {
416        self.span.clone()
417    }
418
419    /// Returns the error's label, if any.
420    pub fn label(&self) -> Option<&'static str> {
421        self.label
422    }
423}
424
425impl<I, S: Span + Clone + fmt::Debug> Error<I> for Cheap<I, S> {
426    type Span = S;
427    type Label = &'static str;
428
429    fn expected_input_found<Iter: IntoIterator<Item = Option<I>>>(
430        span: Self::Span,
431        _: Iter,
432        _: Option<I>,
433    ) -> Self {
434        Self {
435            span,
436            label: None,
437            phantom: PhantomData,
438        }
439    }
440
441    fn with_label(mut self, label: Self::Label) -> Self {
442        self.label.get_or_insert(label);
443        self
444    }
445
446    fn merge(self, _: Self) -> Self {
447        self
448    }
449}
450
451/// An internal type used to facilitate error prioritisation. You shouldn't need to interact with this type during
452/// normal use of the crate.
453pub struct Located<I, E> {
454    pub(crate) at: usize,
455    pub(crate) error: E,
456    pub(crate) phantom: PhantomData<I>,
457}
458
459impl<I, E: Error<I>> Located<I, E> {
460    /// Create a new [`Located`] with the give input position and error.
461    pub fn at(at: usize, error: E) -> Self {
462        Self {
463            at,
464            error,
465            phantom: PhantomData,
466        }
467    }
468
469    /// Get the maximum of two located errors. If they hold the same position in the input, merge them.
470    pub fn max(self, other: impl Into<Option<Self>>) -> Self {
471        let other = match other.into() {
472            Some(other) => other,
473            None => return self,
474        };
475        match self.at.cmp(&other.at) {
476            Ordering::Greater => self,
477            Ordering::Less => other,
478            Ordering::Equal => Self {
479                error: self.error.merge(other.error),
480                ..self
481            },
482        }
483    }
484
485    /// Map the error with the given function.
486    pub fn map<U, F: FnOnce(E) -> U>(self, f: F) -> Located<I, U> {
487        Located {
488            at: self.at,
489            error: f(self.error),
490            phantom: PhantomData,
491        }
492    }
493}
494
495// Merge two alternative errors
496pub(crate) fn merge_alts<I, E: Error<I>, T: IntoIterator<Item = Located<I, E>>>(
497    mut error: Option<Located<I, E>>,
498    errors: T,
499) -> Option<Located<I, E>> {
500    for other in errors {
501        match (error, other) {
502            (Some(a), b) => {
503                error = Some(b.max(a));
504            }
505            (None, b) => {
506                error = Some(b);
507            }
508        }
509    }
510    error
511}