winnow/
error.rs

1//! # Error management
2//!
3//! Errors are designed with multiple needs in mind:
4//! - Accumulate more [context][Parser::context] as the error goes up the parser chain
5//! - Distinguish between [recoverable errors,
6//!   unrecoverable errors, and more data is needed][ErrMode]
7//! - Have a very low overhead, as errors are often discarded by the calling parser (examples: `repeat`, `alt`)
8//! - Can be modified according to the user's needs, because some languages need a lot more information
9//! - Help thread-through the [stream][crate::stream]
10//!
11//! To abstract these needs away from the user, generally `winnow` parsers use the [`PResult`]
12//! alias, rather than [`Result`].  [`Parser::parse`] is a top-level operation
13//! that can help convert to a `Result` for integrating with your application's error reporting.
14//!
15//! Error types include:
16//! - [`EmptyError`] when the reason for failure doesn't matter
17//! - [`ErrorKind`]
18//! - [`ContextError`]
19//! - [`InputError`] (mostly for testing)
20//! - [`TreeError`] (mostly for testing)
21//! - [Custom errors][crate::_topic::error]
22
23#[cfg(feature = "alloc")]
24use crate::lib::std::borrow::ToOwned;
25use crate::lib::std::fmt;
26use core::num::NonZeroUsize;
27
28use crate::stream::AsBStr;
29use crate::stream::Stream;
30#[allow(unused_imports)] // Here for intra-doc links
31use crate::Parser;
32
33/// [Modal error reporting][ErrMode] for [`Parser::parse_next`]
34///
35/// - `Ok(O)` is the parsed value
36/// - [`Err(ErrMode<E>)`][ErrMode] is the error along with how to respond to it
37///
38/// By default, the error type (`E`) is [`ContextError`].
39///
40/// When integrating into the result of the application, see
41/// - [`Parser::parse`]
42/// - [`ErrMode::into_inner`]
43pub type ModalResult<O, E = ContextError> = Result<O, ErrMode<E>>;
44
45/// Deprecated, replaced with [`ModalResult`]
46#[deprecated(since = "0.6.25", note = "Replaced with ModalResult")]
47pub type PResult<O, E = ContextError> = ModalResult<O, E>;
48
49/// Deprecated, replaced with [`PResult`]
50#[deprecated(since = "0.6.25", note = "Replaced with `ModalResult`")]
51pub type IResult<I, O, E = InputError<I>> = ModalResult<(I, O), E>;
52
53/// Contains information on needed data if a parser returned `Incomplete`
54///
55/// <div class="warning">
56///
57/// **Note:** This is only possible for `Stream` that are [partial][`crate::stream::StreamIsPartial`],
58/// like [`Partial`][crate::Partial].
59///
60/// </div>
61#[derive(Debug, PartialEq, Eq, Clone, Copy)]
62pub enum Needed {
63    /// Needs more data, but we do not know how much
64    Unknown,
65    /// Contains a lower bound on the buffer offset needed to finish parsing
66    ///
67    /// For byte/`&str` streams, this translates to bytes
68    Size(NonZeroUsize),
69}
70
71impl Needed {
72    /// Creates `Needed` instance, returns `Needed::Unknown` if the argument is zero
73    pub fn new(s: usize) -> Self {
74        match NonZeroUsize::new(s) {
75            Some(sz) => Needed::Size(sz),
76            None => Needed::Unknown,
77        }
78    }
79
80    /// Indicates if we know how many bytes we need
81    pub fn is_known(&self) -> bool {
82        *self != Needed::Unknown
83    }
84
85    /// Maps a `Needed` to `Needed` by applying a function to a contained `Size` value.
86    #[inline]
87    pub fn map<F: Fn(NonZeroUsize) -> usize>(self, f: F) -> Needed {
88        match self {
89            Needed::Unknown => Needed::Unknown,
90            Needed::Size(n) => Needed::new(f(n)),
91        }
92    }
93}
94
95/// Add parse error state to [`ParserError`]s
96#[derive(Debug, Clone, PartialEq)]
97pub enum ErrMode<E> {
98    /// There was not enough data to determine the appropriate action
99    ///
100    /// More data needs to be buffered before retrying the parse.
101    ///
102    /// This must only be set when the [`Stream`] is [partial][`crate::stream::StreamIsPartial`], like with
103    /// [`Partial`][crate::Partial]
104    ///
105    /// Convert this into an `Backtrack` with [`Parser::complete_err`]
106    Incomplete(Needed),
107    /// The parser failed with a recoverable error (the default).
108    ///
109    /// For example, a parser for json values might include a
110    /// [`dec_uint`][crate::ascii::dec_uint] as one case in an [`alt`][crate::combinator::alt]
111    /// combinator. If it fails, the next case should be tried.
112    Backtrack(E),
113    /// The parser had an unrecoverable error.
114    ///
115    /// The parser was on the right branch, so directly report it to the user rather than trying
116    /// other branches. You can use [`cut_err()`][crate::combinator::cut_err] combinator to switch
117    /// from `ErrMode::Backtrack` to `ErrMode::Cut`.
118    ///
119    /// For example, one case in an [`alt`][crate::combinator::alt] combinator found a unique prefix
120    /// and you want any further errors parsing the case to be reported to the user.
121    Cut(E),
122}
123
124impl<E> ErrMode<E> {
125    /// Tests if the result is Incomplete
126    #[inline]
127    pub fn is_incomplete(&self) -> bool {
128        matches!(self, ErrMode::Incomplete(_))
129    }
130
131    /// Prevent backtracking, bubbling the error up to the top
132    pub fn cut(self) -> Self {
133        match self {
134            ErrMode::Backtrack(e) => ErrMode::Cut(e),
135            rest => rest,
136        }
137    }
138
139    /// Enable backtracking support
140    pub fn backtrack(self) -> Self {
141        match self {
142            ErrMode::Cut(e) => ErrMode::Backtrack(e),
143            rest => rest,
144        }
145    }
146
147    /// Applies the given function to the inner error
148    pub fn map<E2, F>(self, f: F) -> ErrMode<E2>
149    where
150        F: FnOnce(E) -> E2,
151    {
152        match self {
153            ErrMode::Incomplete(n) => ErrMode::Incomplete(n),
154            ErrMode::Cut(t) => ErrMode::Cut(f(t)),
155            ErrMode::Backtrack(t) => ErrMode::Backtrack(f(t)),
156        }
157    }
158
159    /// Automatically converts between errors if the underlying type supports it
160    pub fn convert<F>(self) -> ErrMode<F>
161    where
162        E: ErrorConvert<F>,
163    {
164        self.map(ErrorConvert::convert)
165    }
166
167    /// Unwrap the mode, returning the underlying error
168    ///
169    /// Returns `None` for [`ErrMode::Incomplete`]
170    #[inline(always)]
171    pub fn into_inner(self) -> Option<E> {
172        match self {
173            ErrMode::Backtrack(e) | ErrMode::Cut(e) => Some(e),
174            ErrMode::Incomplete(_) => None,
175        }
176    }
177}
178
179impl<I: Stream, E: ParserError<I>> ParserError<I> for ErrMode<E> {
180    #[inline(always)]
181    fn from_error_kind(input: &I, kind: ErrorKind) -> Self {
182        ErrMode::Backtrack(E::from_error_kind(input, kind))
183    }
184
185    #[inline(always)]
186    fn assert(input: &I, message: &'static str) -> Self
187    where
188        I: crate::lib::std::fmt::Debug,
189    {
190        ErrMode::Cut(E::assert(input, message))
191    }
192
193    #[inline]
194    fn append(self, input: &I, token_start: &<I as Stream>::Checkpoint, kind: ErrorKind) -> Self {
195        match self {
196            ErrMode::Backtrack(e) => ErrMode::Backtrack(e.append(input, token_start, kind)),
197            e => e,
198        }
199    }
200
201    fn or(self, other: Self) -> Self {
202        match (self, other) {
203            (ErrMode::Backtrack(e), ErrMode::Backtrack(o)) => ErrMode::Backtrack(e.or(o)),
204            (ErrMode::Incomplete(e), _) | (_, ErrMode::Incomplete(e)) => ErrMode::Incomplete(e),
205            (ErrMode::Cut(e), _) | (_, ErrMode::Cut(e)) => ErrMode::Cut(e),
206        }
207    }
208}
209
210impl<I, EXT, E> FromExternalError<I, EXT> for ErrMode<E>
211where
212    E: FromExternalError<I, EXT>,
213{
214    #[inline(always)]
215    fn from_external_error(input: &I, kind: ErrorKind, e: EXT) -> Self {
216        ErrMode::Backtrack(E::from_external_error(input, kind, e))
217    }
218}
219
220impl<I: Stream, C, E: AddContext<I, C>> AddContext<I, C> for ErrMode<E> {
221    #[inline(always)]
222    fn add_context(self, input: &I, token_start: &<I as Stream>::Checkpoint, context: C) -> Self {
223        self.map(|err| err.add_context(input, token_start, context))
224    }
225}
226
227impl<T: Clone> ErrMode<InputError<T>> {
228    /// Maps `ErrMode<InputError<T>>` to `ErrMode<InputError<U>>` with the given `F: T -> U`
229    pub fn map_input<U: Clone, F>(self, f: F) -> ErrMode<InputError<U>>
230    where
231        F: FnOnce(T) -> U,
232    {
233        match self {
234            ErrMode::Incomplete(n) => ErrMode::Incomplete(n),
235            ErrMode::Cut(InputError { input, kind }) => ErrMode::Cut(InputError {
236                input: f(input),
237                kind,
238            }),
239            ErrMode::Backtrack(InputError { input, kind }) => ErrMode::Backtrack(InputError {
240                input: f(input),
241                kind,
242            }),
243        }
244    }
245}
246
247impl<E: Eq> Eq for ErrMode<E> {}
248
249impl<E> fmt::Display for ErrMode<E>
250where
251    E: fmt::Debug,
252{
253    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
254        match self {
255            ErrMode::Incomplete(Needed::Size(u)) => write!(f, "Parsing requires {u} more data"),
256            ErrMode::Incomplete(Needed::Unknown) => write!(f, "Parsing requires more data"),
257            ErrMode::Cut(c) => write!(f, "Parsing Failure: {c:?}"),
258            ErrMode::Backtrack(c) => write!(f, "Parsing Error: {c:?}"),
259        }
260    }
261}
262
263/// The basic [`Parser`] trait for errors
264///
265/// It provides methods to create an error from some combinators,
266/// and combine existing errors in combinators like `alt`.
267pub trait ParserError<I: Stream>: Sized {
268    /// Deprecated, replaced with [`ParserError::from_input`]
269    #[deprecated(since = "0.6.26", note = "replaced with `ParserError::from_input`")]
270    fn from_error_kind(input: &I, kind: ErrorKind) -> Self;
271
272    /// Creates an error from the input position
273    #[inline(always)]
274    fn from_input(input: &I) -> Self {
275        Self::from_error_kind(input, ErrorKind::Fail)
276    }
277
278    /// Process a parser assertion
279    #[inline(always)]
280    fn assert(input: &I, _message: &'static str) -> Self
281    where
282        I: crate::lib::std::fmt::Debug,
283    {
284        #[cfg(debug_assertions)]
285        panic!("assert `{_message}` failed at {input:#?}");
286        #[cfg(not(debug_assertions))]
287        Self::from_error_kind(input, ErrorKind::Assert)
288    }
289
290    /// Like [`ParserError::from_error_kind`] but merges it with the existing error.
291    ///
292    /// This is useful when backtracking through a parse tree, accumulating error context on the
293    /// way.
294    fn append(self, input: &I, token_start: &<I as Stream>::Checkpoint, kind: ErrorKind) -> Self;
295
296    /// Combines errors from two different parse branches.
297    ///
298    /// For example, this would be used by [`alt`][crate::combinator::alt] to report the error from
299    /// each case.
300    #[inline]
301    fn or(self, other: Self) -> Self {
302        other
303    }
304}
305
306/// Used by [`Parser::context`] to add custom data to error while backtracking
307///
308/// May be implemented multiple times for different kinds of context.
309pub trait AddContext<I: Stream, C = &'static str>: Sized {
310    /// Append to an existing error custom data
311    ///
312    /// This is used mainly by [`Parser::context`], to add user friendly information
313    /// to errors when backtracking through a parse tree
314    #[inline]
315    fn add_context(
316        self,
317        _input: &I,
318        _token_start: &<I as Stream>::Checkpoint,
319        _context: C,
320    ) -> Self {
321        self
322    }
323}
324
325/// Capture context from when an error was recovered
326#[cfg(feature = "unstable-recover")]
327#[cfg(feature = "std")]
328pub trait FromRecoverableError<I: Stream, E> {
329    /// Capture context from when an error was recovered
330    fn from_recoverable_error(
331        token_start: &<I as Stream>::Checkpoint,
332        err_start: &<I as Stream>::Checkpoint,
333        input: &I,
334        e: E,
335    ) -> Self;
336}
337
338/// Create a new error with an external error, from [`std::str::FromStr`]
339///
340/// This trait is required by the [`Parser::try_map`] combinator.
341pub trait FromExternalError<I, E> {
342    /// Like [`ParserError::from_error_kind`] but also include an external error.
343    fn from_external_error(input: &I, kind: ErrorKind, e: E) -> Self;
344}
345
346/// Equivalent of `From` implementation to avoid orphan rules in bits parsers
347pub trait ErrorConvert<E> {
348    /// Transform to another error type
349    fn convert(self) -> E;
350}
351
352/// Capture input on error
353///
354/// This is useful for testing of generic parsers to ensure the error happens at the right
355/// location.
356///
357/// <div class="warning">
358///
359/// **Note:** [context][Parser::context] and inner errors (like from [`Parser::try_map`]) will be
360/// dropped.
361///
362/// </div>
363#[derive(Copy, Clone, Debug, Eq, PartialEq)]
364pub struct InputError<I: Clone> {
365    /// The input stream, pointing to the location where the error occurred
366    pub input: I,
367    /// A rudimentary error kind
368    pub kind: ErrorKind,
369}
370
371impl<I: Clone> InputError<I> {
372    /// Creates a new basic error
373    #[inline]
374    #[deprecated(since = "0.6.26", note = "replaced with `InputError::at`")]
375    pub fn new(input: I, kind: ErrorKind) -> Self {
376        Self { input, kind }
377    }
378
379    /// Creates a new basic error
380    #[inline]
381    pub fn at(input: I) -> Self {
382        Self {
383            input,
384            kind: ErrorKind::Fail,
385        }
386    }
387
388    /// Translate the input type
389    #[inline]
390    pub fn map_input<I2: Clone, O: Fn(I) -> I2>(self, op: O) -> InputError<I2> {
391        InputError {
392            input: op(self.input),
393            kind: self.kind,
394        }
395    }
396}
397
398#[cfg(feature = "alloc")]
399impl<I: ToOwned> InputError<&I>
400where
401    <I as ToOwned>::Owned: Clone,
402{
403    /// Obtaining ownership
404    pub fn into_owned(self) -> InputError<<I as ToOwned>::Owned> {
405        self.map_input(ToOwned::to_owned)
406    }
407}
408
409impl<I: Stream + Clone> ParserError<I> for InputError<I> {
410    #[inline]
411    fn from_error_kind(input: &I, kind: ErrorKind) -> Self {
412        Self {
413            input: input.clone(),
414            kind,
415        }
416    }
417
418    #[inline]
419    fn append(
420        self,
421        _input: &I,
422        _token_start: &<I as Stream>::Checkpoint,
423        _kind: ErrorKind,
424    ) -> Self {
425        self
426    }
427}
428
429impl<I: Stream + Clone, C> AddContext<I, C> for InputError<I> {}
430
431#[cfg(feature = "unstable-recover")]
432#[cfg(feature = "std")]
433impl<I: Clone + Stream> FromRecoverableError<I, Self> for InputError<I> {
434    #[inline]
435    fn from_recoverable_error(
436        _token_start: &<I as Stream>::Checkpoint,
437        _err_start: &<I as Stream>::Checkpoint,
438        _input: &I,
439        e: Self,
440    ) -> Self {
441        e
442    }
443}
444
445impl<I: Clone, E> FromExternalError<I, E> for InputError<I> {
446    /// Create a new error from an input position and an external error
447    #[inline]
448    fn from_external_error(input: &I, kind: ErrorKind, _e: E) -> Self {
449        Self {
450            input: input.clone(),
451            kind,
452        }
453    }
454}
455
456impl<I: Clone> ErrorConvert<InputError<(I, usize)>> for InputError<I> {
457    #[inline]
458    fn convert(self) -> InputError<(I, usize)> {
459        InputError {
460            input: (self.input, 0),
461            kind: self.kind,
462        }
463    }
464}
465
466impl<I: Clone> ErrorConvert<InputError<I>> for InputError<(I, usize)> {
467    #[inline]
468    fn convert(self) -> InputError<I> {
469        InputError {
470            input: self.input.0,
471            kind: self.kind,
472        }
473    }
474}
475
476/// The Display implementation allows the `std::error::Error` implementation
477impl<I: Clone + fmt::Display> fmt::Display for InputError<I> {
478    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
479        write!(
480            f,
481            "{} error starting at: {}",
482            self.kind.description(),
483            self.input
484        )
485    }
486}
487
488#[cfg(feature = "std")]
489impl<I: Clone + fmt::Debug + fmt::Display + Sync + Send + 'static> std::error::Error
490    for InputError<I>
491{
492}
493
494/// Track an error occurred without any other [`StrContext`]
495#[derive(Copy, Clone, Debug, Eq, PartialEq)]
496pub struct EmptyError;
497
498impl<I: Stream> ParserError<I> for EmptyError {
499    #[inline(always)]
500    fn from_error_kind(_: &I, _: ErrorKind) -> Self {
501        Self
502    }
503
504    #[inline]
505    fn append(
506        self,
507        _input: &I,
508        _token_start: &<I as Stream>::Checkpoint,
509        _kind: ErrorKind,
510    ) -> Self {
511        Self
512    }
513}
514
515impl<I: Stream, C> AddContext<I, C> for EmptyError {}
516
517#[cfg(feature = "unstable-recover")]
518#[cfg(feature = "std")]
519impl<I: Stream> FromRecoverableError<I, Self> for EmptyError {
520    #[inline(always)]
521    fn from_recoverable_error(
522        _token_start: &<I as Stream>::Checkpoint,
523        _err_start: &<I as Stream>::Checkpoint,
524        _input: &I,
525        e: Self,
526    ) -> Self {
527        e
528    }
529}
530
531impl<I, E> FromExternalError<I, E> for EmptyError {
532    #[inline(always)]
533    fn from_external_error(_input: &I, _kind: ErrorKind, _e: E) -> Self {
534        Self
535    }
536}
537
538impl ErrorConvert<EmptyError> for EmptyError {
539    #[inline(always)]
540    fn convert(self) -> EmptyError {
541        self
542    }
543}
544
545impl crate::lib::std::fmt::Display for EmptyError {
546    fn fmt(&self, f: &mut crate::lib::std::fmt::Formatter<'_>) -> crate::lib::std::fmt::Result {
547        "failed to parse".fmt(f)
548    }
549}
550
551impl<I: Stream> ParserError<I> for () {
552    #[inline]
553    fn from_error_kind(_: &I, _: ErrorKind) -> Self {}
554
555    #[inline]
556    fn append(
557        self,
558        _input: &I,
559        _token_start: &<I as Stream>::Checkpoint,
560        _kind: ErrorKind,
561    ) -> Self {
562    }
563}
564
565impl<I: Stream, C> AddContext<I, C> for () {}
566
567#[cfg(feature = "unstable-recover")]
568#[cfg(feature = "std")]
569impl<I: Stream> FromRecoverableError<I, Self> for () {
570    #[inline]
571    fn from_recoverable_error(
572        _token_start: &<I as Stream>::Checkpoint,
573        _err_start: &<I as Stream>::Checkpoint,
574        _input: &I,
575        (): Self,
576    ) -> Self {
577    }
578}
579
580impl<I, E> FromExternalError<I, E> for () {
581    #[inline]
582    fn from_external_error(_input: &I, _kind: ErrorKind, _e: E) -> Self {}
583}
584
585impl ErrorConvert<()> for () {
586    #[inline]
587    fn convert(self) {}
588}
589
590/// Accumulate context while backtracking errors
591#[derive(Debug)]
592pub struct ContextError<C = StrContext> {
593    #[cfg(feature = "alloc")]
594    context: crate::lib::std::vec::Vec<C>,
595    #[cfg(not(feature = "alloc"))]
596    context: core::marker::PhantomData<C>,
597    #[cfg(feature = "std")]
598    cause: Option<Box<dyn std::error::Error + Send + Sync + 'static>>,
599}
600
601impl<C> ContextError<C> {
602    /// Create an empty error
603    #[inline]
604    pub fn new() -> Self {
605        Self {
606            context: Default::default(),
607            #[cfg(feature = "std")]
608            cause: None,
609        }
610    }
611
612    /// Access context from [`Parser::context`]
613    #[inline]
614    #[cfg(feature = "alloc")]
615    pub fn context(&self) -> impl Iterator<Item = &C> {
616        self.context.iter()
617    }
618
619    /// Originating [`std::error::Error`]
620    #[inline]
621    #[cfg(feature = "std")]
622    pub fn cause(&self) -> Option<&(dyn std::error::Error + Send + Sync + 'static)> {
623        self.cause.as_deref()
624    }
625}
626
627impl<C: Clone> Clone for ContextError<C> {
628    fn clone(&self) -> Self {
629        Self {
630            context: self.context.clone(),
631            #[cfg(feature = "std")]
632            cause: self.cause.as_ref().map(|e| e.to_string().into()),
633        }
634    }
635}
636
637impl<C> Default for ContextError<C> {
638    #[inline]
639    fn default() -> Self {
640        Self::new()
641    }
642}
643
644impl<I: Stream, C> ParserError<I> for ContextError<C> {
645    #[inline]
646    fn from_error_kind(_input: &I, _kind: ErrorKind) -> Self {
647        Self::new()
648    }
649
650    #[inline]
651    fn append(
652        self,
653        _input: &I,
654        _token_start: &<I as Stream>::Checkpoint,
655        _kind: ErrorKind,
656    ) -> Self {
657        self
658    }
659
660    #[inline]
661    fn or(self, other: Self) -> Self {
662        other
663    }
664}
665
666impl<C, I: Stream> AddContext<I, C> for ContextError<C> {
667    #[inline]
668    fn add_context(
669        mut self,
670        _input: &I,
671        _token_start: &<I as Stream>::Checkpoint,
672        context: C,
673    ) -> Self {
674        #[cfg(feature = "alloc")]
675        self.context.push(context);
676        self
677    }
678}
679
680#[cfg(feature = "unstable-recover")]
681#[cfg(feature = "std")]
682impl<I: Stream, C> FromRecoverableError<I, Self> for ContextError<C> {
683    #[inline]
684    fn from_recoverable_error(
685        _token_start: &<I as Stream>::Checkpoint,
686        _err_start: &<I as Stream>::Checkpoint,
687        _input: &I,
688        e: Self,
689    ) -> Self {
690        e
691    }
692}
693
694#[cfg(feature = "std")]
695impl<C, I, E: std::error::Error + Send + Sync + 'static> FromExternalError<I, E>
696    for ContextError<C>
697{
698    #[inline]
699    fn from_external_error(_input: &I, _kind: ErrorKind, e: E) -> Self {
700        let mut err = Self::new();
701        {
702            err.cause = Some(Box::new(e));
703        }
704        err
705    }
706}
707
708// HACK: This is more general than `std`, making the features non-additive
709#[cfg(not(feature = "std"))]
710impl<C, I, E: Send + Sync + 'static> FromExternalError<I, E> for ContextError<C> {
711    #[inline]
712    fn from_external_error(_input: &I, _kind: ErrorKind, _e: E) -> Self {
713        let err = Self::new();
714        err
715    }
716}
717
718// For tests
719impl<C: core::cmp::PartialEq> core::cmp::PartialEq for ContextError<C> {
720    fn eq(&self, other: &Self) -> bool {
721        #[cfg(feature = "alloc")]
722        {
723            if self.context != other.context {
724                return false;
725            }
726        }
727        #[cfg(feature = "std")]
728        {
729            if self.cause.as_ref().map(ToString::to_string)
730                != other.cause.as_ref().map(ToString::to_string)
731            {
732                return false;
733            }
734        }
735
736        true
737    }
738}
739
740impl crate::lib::std::fmt::Display for ContextError<StrContext> {
741    fn fmt(&self, f: &mut crate::lib::std::fmt::Formatter<'_>) -> crate::lib::std::fmt::Result {
742        #[cfg(feature = "alloc")]
743        {
744            let expression = self.context().find_map(|c| match c {
745                StrContext::Label(c) => Some(c),
746                _ => None,
747            });
748            let expected = self
749                .context()
750                .filter_map(|c| match c {
751                    StrContext::Expected(c) => Some(c),
752                    _ => None,
753                })
754                .collect::<crate::lib::std::vec::Vec<_>>();
755
756            let mut newline = false;
757
758            if let Some(expression) = expression {
759                newline = true;
760
761                write!(f, "invalid {expression}")?;
762            }
763
764            if !expected.is_empty() {
765                if newline {
766                    writeln!(f)?;
767                }
768                newline = true;
769
770                write!(f, "expected ")?;
771                for (i, expected) in expected.iter().enumerate() {
772                    if i != 0 {
773                        write!(f, ", ")?;
774                    }
775                    write!(f, "{expected}")?;
776                }
777            }
778            #[cfg(feature = "std")]
779            {
780                if let Some(cause) = self.cause() {
781                    if newline {
782                        writeln!(f)?;
783                    }
784                    write!(f, "{cause}")?;
785                }
786            }
787        }
788
789        Ok(())
790    }
791}
792
793impl<C> ErrorConvert<ContextError<C>> for ContextError<C> {
794    #[inline]
795    fn convert(self) -> ContextError<C> {
796        self
797    }
798}
799
800/// Additional parse context for [`ContextError`] added via [`Parser::context`]
801#[derive(Clone, Debug, PartialEq, Eq)]
802#[non_exhaustive]
803pub enum StrContext {
804    /// Description of what is currently being parsed
805    Label(&'static str),
806    /// Grammar item that was expected
807    Expected(StrContextValue),
808}
809
810impl crate::lib::std::fmt::Display for StrContext {
811    fn fmt(&self, f: &mut crate::lib::std::fmt::Formatter<'_>) -> crate::lib::std::fmt::Result {
812        match self {
813            Self::Label(name) => write!(f, "invalid {name}"),
814            Self::Expected(value) => write!(f, "expected {value}"),
815        }
816    }
817}
818
819/// See [`StrContext`]
820#[derive(Clone, Debug, PartialEq, Eq)]
821#[non_exhaustive]
822pub enum StrContextValue {
823    /// A [`char`] token
824    CharLiteral(char),
825    /// A [`&str`] token
826    StringLiteral(&'static str),
827    /// A description of what was being parsed
828    Description(&'static str),
829}
830
831impl From<char> for StrContextValue {
832    #[inline]
833    fn from(inner: char) -> Self {
834        Self::CharLiteral(inner)
835    }
836}
837
838impl From<&'static str> for StrContextValue {
839    #[inline]
840    fn from(inner: &'static str) -> Self {
841        Self::StringLiteral(inner)
842    }
843}
844
845impl crate::lib::std::fmt::Display for StrContextValue {
846    fn fmt(&self, f: &mut crate::lib::std::fmt::Formatter<'_>) -> crate::lib::std::fmt::Result {
847        match self {
848            Self::CharLiteral('\n') => "newline".fmt(f),
849            Self::CharLiteral('`') => "'`'".fmt(f),
850            Self::CharLiteral(c) if c.is_ascii_control() => {
851                write!(f, "`{}`", c.escape_debug())
852            }
853            Self::CharLiteral(c) => write!(f, "`{c}`"),
854            Self::StringLiteral(c) => write!(f, "`{c}`"),
855            Self::Description(c) => write!(f, "{c}"),
856        }
857    }
858}
859
860/// Trace all error paths, particularly for tests
861#[derive(Debug)]
862#[cfg(feature = "std")]
863pub enum TreeError<I, C = StrContext> {
864    /// Initial error that kicked things off
865    Base(TreeErrorBase<I>),
866    /// Traces added to the error while walking back up the stack
867    Stack {
868        /// Initial error that kicked things off
869        base: Box<Self>,
870        /// Traces added to the error while walking back up the stack
871        stack: Vec<TreeErrorFrame<I, C>>,
872    },
873    /// All failed branches of an `alt`
874    Alt(Vec<Self>),
875}
876
877/// See [`TreeError::Stack`]
878#[derive(Debug)]
879#[cfg(feature = "std")]
880pub enum TreeErrorFrame<I, C = StrContext> {
881    /// See [`ParserError::append`]
882    Kind(TreeErrorBase<I>),
883    /// See [`AddContext::add_context`]
884    Context(TreeErrorContext<I, C>),
885}
886
887/// See [`TreeErrorFrame::Kind`], [`ParserError::append`]
888#[derive(Debug)]
889#[cfg(feature = "std")]
890pub struct TreeErrorBase<I> {
891    /// Parsed input, at the location where the error occurred
892    pub input: I,
893    /// Debug context
894    pub kind: ErrorKind,
895    /// See [`FromExternalError::from_external_error`]
896    pub cause: Option<Box<dyn std::error::Error + Send + Sync + 'static>>,
897}
898
899/// See [`TreeErrorFrame::Context`], [`AddContext::add_context`]
900#[derive(Debug)]
901#[cfg(feature = "std")]
902pub struct TreeErrorContext<I, C = StrContext> {
903    /// Parsed input, at the location where the error occurred
904    pub input: I,
905    /// See [`AddContext::add_context`]
906    pub context: C,
907}
908
909#[cfg(feature = "std")]
910impl<'i, I: ToOwned, C> TreeError<&'i I, C>
911where
912    &'i I: Stream + Clone,
913    <I as ToOwned>::Owned: Clone,
914{
915    /// Obtaining ownership
916    pub fn into_owned(self) -> TreeError<<I as ToOwned>::Owned, C> {
917        self.map_input(ToOwned::to_owned)
918    }
919}
920
921#[cfg(feature = "std")]
922impl<I, C> TreeError<I, C>
923where
924    I: Stream + Clone,
925{
926    /// Translate the input type
927    pub fn map_input<I2: Clone, O: Clone + Fn(I) -> I2>(self, op: O) -> TreeError<I2, C> {
928        match self {
929            TreeError::Base(base) => TreeError::Base(TreeErrorBase {
930                input: op(base.input),
931                kind: base.kind,
932                cause: base.cause,
933            }),
934            TreeError::Stack { base, stack } => {
935                let base = Box::new(base.map_input(op.clone()));
936                let stack = stack
937                    .into_iter()
938                    .map(|frame| match frame {
939                        TreeErrorFrame::Kind(kind) => TreeErrorFrame::Kind(TreeErrorBase {
940                            input: op(kind.input),
941                            kind: kind.kind,
942                            cause: kind.cause,
943                        }),
944                        TreeErrorFrame::Context(context) => {
945                            TreeErrorFrame::Context(TreeErrorContext {
946                                input: op(context.input),
947                                context: context.context,
948                            })
949                        }
950                    })
951                    .collect();
952                TreeError::Stack { base, stack }
953            }
954            TreeError::Alt(alt) => {
955                TreeError::Alt(alt.into_iter().map(|e| e.map_input(op.clone())).collect())
956            }
957        }
958    }
959
960    fn append_frame(self, frame: TreeErrorFrame<I, C>) -> Self {
961        match self {
962            TreeError::Stack { base, mut stack } => {
963                stack.push(frame);
964                TreeError::Stack { base, stack }
965            }
966            base => TreeError::Stack {
967                base: Box::new(base),
968                stack: vec![frame],
969            },
970        }
971    }
972}
973
974#[cfg(feature = "std")]
975impl<I, C> ParserError<I> for TreeError<I, C>
976where
977    I: Stream + Clone,
978{
979    fn from_error_kind(input: &I, kind: ErrorKind) -> Self {
980        TreeError::Base(TreeErrorBase {
981            input: input.clone(),
982            kind,
983            cause: None,
984        })
985    }
986
987    fn append(self, input: &I, token_start: &<I as Stream>::Checkpoint, kind: ErrorKind) -> Self {
988        let mut input = input.clone();
989        input.reset(token_start);
990        let frame = TreeErrorFrame::Kind(TreeErrorBase {
991            input,
992            kind,
993            cause: None,
994        });
995        self.append_frame(frame)
996    }
997
998    fn or(self, other: Self) -> Self {
999        match (self, other) {
1000            (TreeError::Alt(mut first), TreeError::Alt(second)) => {
1001                // Just in case an implementation does a divide-and-conquer algorithm
1002                //
1003                // To prevent mixing `alt`s at different levels, parsers should
1004                // `alt_err.append(input, ErrorKind::Alt)`.
1005                first.extend(second);
1006                TreeError::Alt(first)
1007            }
1008            (TreeError::Alt(mut alt), new) | (new, TreeError::Alt(mut alt)) => {
1009                alt.push(new);
1010                TreeError::Alt(alt)
1011            }
1012            (first, second) => TreeError::Alt(vec![first, second]),
1013        }
1014    }
1015}
1016
1017#[cfg(feature = "std")]
1018impl<I, C> AddContext<I, C> for TreeError<I, C>
1019where
1020    I: Stream + Clone,
1021{
1022    fn add_context(self, input: &I, token_start: &<I as Stream>::Checkpoint, context: C) -> Self {
1023        let mut input = input.clone();
1024        input.reset(token_start);
1025        let frame = TreeErrorFrame::Context(TreeErrorContext { input, context });
1026        self.append_frame(frame)
1027    }
1028}
1029
1030#[cfg(feature = "std")]
1031#[cfg(feature = "unstable-recover")]
1032impl<I: Stream + Clone, C> FromRecoverableError<I, Self> for TreeError<I, C> {
1033    #[inline]
1034    fn from_recoverable_error(
1035        _token_start: &<I as Stream>::Checkpoint,
1036        _err_start: &<I as Stream>::Checkpoint,
1037        _input: &I,
1038        e: Self,
1039    ) -> Self {
1040        e
1041    }
1042}
1043
1044#[cfg(feature = "std")]
1045impl<I, C, E: std::error::Error + Send + Sync + 'static> FromExternalError<I, E> for TreeError<I, C>
1046where
1047    I: Stream + Clone,
1048{
1049    fn from_external_error(input: &I, kind: ErrorKind, e: E) -> Self {
1050        TreeError::Base(TreeErrorBase {
1051            input: input.clone(),
1052            kind,
1053            cause: Some(Box::new(e)),
1054        })
1055    }
1056}
1057
1058#[cfg(feature = "std")]
1059impl<I, C> TreeError<I, C>
1060where
1061    I: Stream + Clone + crate::lib::std::fmt::Display,
1062    C: fmt::Display,
1063{
1064    fn write(&self, f: &mut fmt::Formatter<'_>, indent: usize) -> fmt::Result {
1065        let child_indent = indent + 2;
1066        match self {
1067            TreeError::Base(base) => {
1068                writeln!(f, "{:indent$}{base}", "")?;
1069            }
1070            TreeError::Stack { base, stack } => {
1071                base.write(f, indent)?;
1072                for (level, frame) in stack.iter().enumerate() {
1073                    match frame {
1074                        TreeErrorFrame::Kind(frame) => {
1075                            writeln!(f, "{:child_indent$}{level}: {frame}", "")?;
1076                        }
1077                        TreeErrorFrame::Context(frame) => {
1078                            writeln!(f, "{:child_indent$}{level}: {frame}", "")?;
1079                        }
1080                    }
1081                }
1082            }
1083            TreeError::Alt(alt) => {
1084                writeln!(f, "{:indent$}during one of:", "")?;
1085                for child in alt {
1086                    child.write(f, child_indent)?;
1087                }
1088            }
1089        }
1090
1091        Ok(())
1092    }
1093}
1094
1095#[cfg(feature = "std")]
1096impl<I: Stream + Clone + fmt::Display> fmt::Display for TreeErrorBase<I> {
1097    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1098        if let Some(cause) = self.cause.as_ref() {
1099            write!(f, "caused by {cause}")?;
1100        } else {
1101            let kind = self.kind.description();
1102            write!(f, "in {kind}")?;
1103        }
1104        let input = abbreviate(self.input.to_string());
1105        write!(f, " at '{input}'")?;
1106        Ok(())
1107    }
1108}
1109
1110#[cfg(feature = "std")]
1111impl<I: Stream + Clone + fmt::Display, C: fmt::Display> fmt::Display for TreeErrorContext<I, C> {
1112    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1113        let context = &self.context;
1114        let input = abbreviate(self.input.to_string());
1115        write!(f, "{context} at '{input}'")?;
1116        Ok(())
1117    }
1118}
1119
1120#[cfg(feature = "std")]
1121impl<
1122        I: Stream + Clone + fmt::Debug + fmt::Display + Sync + Send + 'static,
1123        C: fmt::Display + fmt::Debug,
1124    > std::error::Error for TreeError<I, C>
1125{
1126}
1127
1128#[cfg(feature = "std")]
1129fn abbreviate(input: String) -> String {
1130    let mut abbrev = None;
1131
1132    if let Some((line, _)) = input.split_once('\n') {
1133        abbrev = Some(line);
1134    }
1135
1136    let max_len = 20;
1137    let current = abbrev.unwrap_or(&input);
1138    if max_len < current.len() {
1139        if let Some((index, _)) = current.char_indices().nth(max_len) {
1140            abbrev = Some(&current[..index]);
1141        }
1142    }
1143
1144    if let Some(abbrev) = abbrev {
1145        format!("{abbrev}...")
1146    } else {
1147        input
1148    }
1149}
1150
1151#[cfg(feature = "std")]
1152impl<I: Stream + Clone + fmt::Display, C: fmt::Display> fmt::Display for TreeError<I, C> {
1153    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1154        self.write(f, 0)
1155    }
1156}
1157
1158/// Deprecated
1159///
1160/// For en error type, consider [`EmptyError`] instead
1161///
1162/// For creating an error, use [`ParserError::from_input`], [`InputError::at`]
1163#[rustfmt::skip]
1164#[derive(Debug,PartialEq,Eq,Hash,Clone,Copy)]
1165#[allow(missing_docs)]
1166#[deprecated(since = "0.6.26")]
1167pub enum ErrorKind {
1168  Assert,
1169  Token,
1170  Tag,
1171  Alt,
1172  Many,
1173  Eof,
1174  Slice,
1175  Complete,
1176  Not,
1177  Verify,
1178  Fail,
1179}
1180
1181impl ErrorKind {
1182    #[rustfmt::skip]
1183    /// Converts an `ErrorKind` to a text description
1184    pub fn description(&self) -> &str {
1185    match *self {
1186      ErrorKind::Assert                    => "assert",
1187      ErrorKind::Token                     => "token",
1188      ErrorKind::Tag                       => "tag",
1189      ErrorKind::Alt                       => "alternative",
1190      ErrorKind::Many                      => "many",
1191      ErrorKind::Eof                       => "end of file",
1192      ErrorKind::Slice                     => "slice",
1193      ErrorKind::Complete                  => "complete",
1194      ErrorKind::Not                       => "negation",
1195      ErrorKind::Verify                    => "predicate verification",
1196      ErrorKind::Fail                      => "fail",
1197    }
1198  }
1199}
1200
1201impl<I: Stream> ParserError<I> for ErrorKind {
1202    #[inline]
1203    fn from_error_kind(_input: &I, kind: ErrorKind) -> Self {
1204        kind
1205    }
1206
1207    #[inline]
1208    fn append(
1209        self,
1210        _input: &I,
1211        _token_start: &<I as Stream>::Checkpoint,
1212        _kind: ErrorKind,
1213    ) -> Self {
1214        self
1215    }
1216}
1217
1218impl<I: Stream, C> AddContext<I, C> for ErrorKind {}
1219
1220impl<I, E> FromExternalError<I, E> for ErrorKind {
1221    /// Create a new error from an input position and an external error
1222    #[inline]
1223    fn from_external_error(_input: &I, kind: ErrorKind, _e: E) -> Self {
1224        kind
1225    }
1226}
1227
1228/// The Display implementation allows the `std::error::Error` implementation
1229impl fmt::Display for ErrorKind {
1230    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1231        write!(f, "error {self:?}")
1232    }
1233}
1234
1235#[cfg(feature = "std")]
1236impl std::error::Error for ErrorKind {}
1237
1238/// See [`Parser::parse`]
1239#[derive(Clone, Debug, PartialEq, Eq)]
1240pub struct ParseError<I, E> {
1241    input: I,
1242    offset: usize,
1243    inner: E,
1244}
1245
1246impl<I: Stream, E: ParserError<I>> ParseError<I, E> {
1247    pub(crate) fn new(mut input: I, start: I::Checkpoint, inner: E) -> Self {
1248        let offset = input.offset_from(&start);
1249        input.reset(&start);
1250        Self {
1251            input,
1252            offset,
1253            inner,
1254        }
1255    }
1256}
1257
1258impl<I, E> ParseError<I, E> {
1259    /// The [`Stream`] at the initial location when parsing started
1260    #[inline]
1261    pub fn input(&self) -> &I {
1262        &self.input
1263    }
1264
1265    /// The location in [`ParseError::input`] where parsing failed
1266    ///
1267    /// <div class="warning">
1268    ///
1269    /// **Note:** This is an offset, not an index, and may point to the end of input
1270    /// (`input.len()`) on eof errors.
1271    ///
1272    /// </div>
1273    #[inline]
1274    pub fn offset(&self) -> usize {
1275        self.offset
1276    }
1277
1278    /// The original [`ParserError`]
1279    #[inline]
1280    pub fn inner(&self) -> &E {
1281        &self.inner
1282    }
1283
1284    /// The original [`ParserError`]
1285    #[inline]
1286    pub fn into_inner(self) -> E {
1287        self.inner
1288    }
1289}
1290
1291impl<I, E> core::fmt::Display for ParseError<I, E>
1292where
1293    I: AsBStr,
1294    E: core::fmt::Display,
1295{
1296    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1297        let input = self.input.as_bstr();
1298        let span_start = self.offset;
1299        let span_end = span_start;
1300        #[cfg(feature = "std")]
1301        if input.contains(&b'\n') {
1302            let (line_idx, col_idx) = translate_position(input, span_start);
1303            let line_num = line_idx + 1;
1304            let col_num = col_idx + 1;
1305            let gutter = line_num.to_string().len();
1306            let content = input
1307                .split(|c| *c == b'\n')
1308                .nth(line_idx)
1309                .expect("valid line number");
1310
1311            writeln!(f, "parse error at line {line_num}, column {col_num}")?;
1312            //   |
1313            for _ in 0..gutter {
1314                write!(f, " ")?;
1315            }
1316            writeln!(f, " |")?;
1317
1318            // 1 | 00:32:00.a999999
1319            write!(f, "{line_num} | ")?;
1320            writeln!(f, "{}", String::from_utf8_lossy(content))?;
1321
1322            //   |          ^
1323            for _ in 0..gutter {
1324                write!(f, " ")?;
1325            }
1326            write!(f, " | ")?;
1327            for _ in 0..col_idx {
1328                write!(f, " ")?;
1329            }
1330            // The span will be empty at eof, so we need to make sure we always print at least
1331            // one `^`
1332            write!(f, "^")?;
1333            for _ in (span_start + 1)..(span_end.min(span_start + content.len())) {
1334                write!(f, "^")?;
1335            }
1336            writeln!(f)?;
1337        } else {
1338            let content = input;
1339            writeln!(f, "{}", String::from_utf8_lossy(content))?;
1340            for _ in 0..span_start {
1341                write!(f, " ")?;
1342            }
1343            // The span will be empty at eof, so we need to make sure we always print at least
1344            // one `^`
1345            write!(f, "^")?;
1346            for _ in (span_start + 1)..(span_end.min(span_start + content.len())) {
1347                write!(f, "^")?;
1348            }
1349            writeln!(f)?;
1350        }
1351        write!(f, "{}", self.inner)?;
1352
1353        Ok(())
1354    }
1355}
1356
1357#[cfg(feature = "std")]
1358fn translate_position(input: &[u8], index: usize) -> (usize, usize) {
1359    if input.is_empty() {
1360        return (0, index);
1361    }
1362
1363    let safe_index = index.min(input.len() - 1);
1364    let column_offset = index - safe_index;
1365    let index = safe_index;
1366
1367    let nl = input[0..index]
1368        .iter()
1369        .rev()
1370        .enumerate()
1371        .find(|(_, b)| **b == b'\n')
1372        .map(|(nl, _)| index - nl - 1);
1373    let line_start = match nl {
1374        Some(nl) => nl + 1,
1375        None => 0,
1376    };
1377    let line = input[0..line_start].iter().filter(|b| **b == b'\n').count();
1378
1379    // HACK: This treats byte offset and column offsets the same
1380    let column = crate::lib::std::str::from_utf8(&input[line_start..=index])
1381        .map(|s| s.chars().count() - 1)
1382        .unwrap_or_else(|_| index - line_start);
1383    let column = column + column_offset;
1384
1385    (line, column)
1386}
1387
1388#[cfg(test)]
1389#[cfg(feature = "std")]
1390mod test_parse_error {
1391    use super::*;
1392
1393    #[test]
1394    fn single_line() {
1395        let mut input = "0xZ123";
1396        let start = input.checkpoint();
1397        let _ = input.next_token().unwrap();
1398        let _ = input.next_token().unwrap();
1399        let inner = InputError::new(input, ErrorKind::Slice);
1400        let error = ParseError::new(input, start, inner);
1401        let expected = "\
14020xZ123
1403  ^
1404slice error starting at: Z123";
1405        assert_eq!(error.to_string(), expected);
1406    }
1407}
1408
1409#[cfg(test)]
1410#[cfg(feature = "std")]
1411mod test_translate_position {
1412    use super::*;
1413
1414    #[test]
1415    fn empty() {
1416        let input = b"";
1417        let index = 0;
1418        let position = translate_position(&input[..], index);
1419        assert_eq!(position, (0, 0));
1420    }
1421
1422    #[test]
1423    fn start() {
1424        let input = b"Hello";
1425        let index = 0;
1426        let position = translate_position(&input[..], index);
1427        assert_eq!(position, (0, 0));
1428    }
1429
1430    #[test]
1431    fn end() {
1432        let input = b"Hello";
1433        let index = input.len() - 1;
1434        let position = translate_position(&input[..], index);
1435        assert_eq!(position, (0, input.len() - 1));
1436    }
1437
1438    #[test]
1439    fn after() {
1440        let input = b"Hello";
1441        let index = input.len();
1442        let position = translate_position(&input[..], index);
1443        assert_eq!(position, (0, input.len()));
1444    }
1445
1446    #[test]
1447    fn first_line() {
1448        let input = b"Hello\nWorld\n";
1449        let index = 2;
1450        let position = translate_position(&input[..], index);
1451        assert_eq!(position, (0, 2));
1452    }
1453
1454    #[test]
1455    fn end_of_line() {
1456        let input = b"Hello\nWorld\n";
1457        let index = 5;
1458        let position = translate_position(&input[..], index);
1459        assert_eq!(position, (0, 5));
1460    }
1461
1462    #[test]
1463    fn start_of_second_line() {
1464        let input = b"Hello\nWorld\n";
1465        let index = 6;
1466        let position = translate_position(&input[..], index);
1467        assert_eq!(position, (1, 0));
1468    }
1469
1470    #[test]
1471    fn second_line() {
1472        let input = b"Hello\nWorld\n";
1473        let index = 8;
1474        let position = translate_position(&input[..], index);
1475        assert_eq!(position, (1, 2));
1476    }
1477}
1478
1479/// Creates a parse error from a [`ErrorKind`]
1480/// and the position in the input
1481#[cfg(test)]
1482macro_rules! error_position(
1483  ($input:expr, $code:expr) => ({
1484    $crate::error::ParserError::from_error_kind($input, $code)
1485  });
1486);
1487
1488#[cfg(test)]
1489macro_rules! error_node_position(
1490  ($input:expr, $code:expr, $next:expr) => ({
1491    let start = $input.checkpoint();
1492    $crate::error::ParserError::append($next, $input, &start, $code)
1493  });
1494);