chumsky/
lib.rs

1#![cfg_attr(feature = "nightly", feature(rustc_attrs))]
2#![cfg_attr(not(any(doc, feature = "std")), no_std)]
3#![doc = include_str!("../README.md")]
4#![deny(missing_docs)]
5#![allow(deprecated)] // TODO: Don't allow this
6
7extern crate alloc;
8
9pub mod chain;
10pub mod combinator;
11pub mod debug;
12pub mod error;
13pub mod primitive;
14pub mod recovery;
15pub mod recursive;
16pub mod span;
17pub mod stream;
18pub mod text;
19
20pub use crate::{error::Error, span::Span};
21
22pub use crate::stream::{BoxStream, Flat, Stream};
23
24use crate::{
25    chain::Chain,
26    combinator::*,
27    debug::*,
28    error::{merge_alts, Located},
29    primitive::*,
30    recovery::*,
31};
32
33use alloc::{boxed::Box, rc::Rc, string::String, sync::Arc, vec, vec::Vec};
34use core::{
35    cmp::Ordering,
36    // TODO: Enable when stable
37    //lazy::OnceCell,
38    fmt,
39    marker::PhantomData,
40    ops::Range,
41    panic::Location,
42    str::FromStr,
43};
44
45#[cfg(doc)]
46use std::{
47    collections::HashMap,
48    // TODO: Remove when switching to 2021 edition
49    iter::FromIterator,
50};
51
52/// Commonly used functions, traits and types.
53///
54/// *Listen, three eyes,” he said, “don’t you try to outweird me, I get stranger things than you free with my breakfast
55/// cereal.”*
56pub mod prelude {
57    pub use super::{
58        error::{Error as _, Simple},
59        primitive::{
60            any, choice, empty, end, filter, filter_map, just, none_of, one_of, seq, take_until,
61            todo,
62        },
63        recovery::{nested_delimiters, skip_parser, skip_then_retry_until, skip_until},
64        recursive::{recursive, Recursive},
65        select,
66        span::Span as _,
67        text,
68        text::TextParser as _,
69        BoxedParser, Parser,
70    };
71}
72
73// TODO: Replace with `std::ops::ControlFlow` when stable
74enum ControlFlow<C, B> {
75    Continue(C),
76    Break(B),
77}
78
79// ([], Ok((out, alt_err))) => parsing successful,
80// alt_err = potential alternative error should a different number of optional patterns be parsed
81// ([x, ...], Ok((out, alt_err)) => parsing failed, but recovery occurred so parsing may continue
82// ([...], Err(err)) => parsing failed, recovery failed, and one or more errors were produced
83// TODO: Change `alt_err` from `Option<Located<I, E>>` to `Vec<Located<I, E>>`
84type PResult<I, O, E> = (
85    Vec<Located<I, E>>,
86    Result<(O, Option<Located<I, E>>), Located<I, E>>,
87);
88
89// Shorthand for a stream with the given input and error type.
90type StreamOf<'a, I, E> = Stream<'a, I, <E as Error<I>>::Span>;
91
92// [`Parser::parse_recovery`], but generic across the debugger.
93fn parse_recovery_inner<
94    'a,
95    I: Clone,
96    O,
97    P: Parser<I, O>,
98    D: Debugger,
99    Iter: Iterator<Item = (I, <P::Error as Error<I>>::Span)> + 'a,
100    S: Into<Stream<'a, I, <P::Error as Error<I>>::Span, Iter>>,
101>(
102    parser: &P,
103    debugger: &mut D,
104    stream: S,
105) -> (Option<O>, Vec<P::Error>)
106where
107    P: Sized,
108{
109    #[allow(deprecated)]
110    let (mut errors, res) = parser.parse_inner(debugger, &mut stream.into());
111    let out = match res {
112        Ok((out, _)) => Some(out),
113        Err(err) => {
114            errors.push(err);
115            None
116        }
117    };
118    (out, errors.into_iter().map(|e| e.error).collect())
119}
120
121/// A trait implemented by parsers.
122///
123/// Parsers take a stream of tokens of type `I` and attempt to parse them into a value of type `O`. In doing so, they
124/// may encounter errors. These need not be fatal to the parsing process: syntactic errors can be recovered from and a
125/// valid output may still be generated alongside any syntax errors that were encountered along the way. Usually, this
126/// output comes in the form of an [Abstract Syntax Tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree) (AST).
127///
128/// You should not need to implement this trait by hand. If you cannot combine existing combintors (and in particular
129/// [`custom`]) to create the combinator you're looking for, please
130/// [open an issue](https://github.com/zesterer/chumsky/issues/new)! If you *really* need to implement this trait,
131/// please check the documentation in the source: some implementation details have been deliberately hidden.
132#[cfg_attr(
133    feature = "nightly",
134    rustc_on_unimplemented(
135        message = "`{Self}` is not a parser from `{I}` to `{O}`",
136        label = "This parser is not compatible because it does not implement `Parser<{I}, {O}>`",
137        note = "You should check that the output types of your parsers are consistent with combinator you're using",
138    )
139)]
140#[allow(clippy::type_complexity)]
141pub trait Parser<I: Clone, O> {
142    /// The type of errors emitted by this parser.
143    type Error: Error<I>; // TODO when default associated types are stable: = Cheap<I>;
144
145    /// Parse a stream with all the bells & whistles. You can use this to implement your own parser combinators. Note
146    /// that both the signature and semantic requirements of this function are very likely to change in later versions.
147    /// Where possible, prefer more ergonomic combinators provided elsewhere in the crate rather than implementing your
148    /// own. For example, [`custom`] provides a flexible, ergonomic way API for process input streams that likely
149    /// covers your use-case.
150    #[doc(hidden)]
151    #[deprecated(
152        note = "This method is excluded from the semver guarantees of chumsky. If you decide to use it, broken builds are your fault."
153    )]
154    fn parse_inner<D: Debugger>(
155        &self,
156        debugger: &mut D,
157        stream: &mut StreamOf<I, Self::Error>,
158    ) -> PResult<I, O, Self::Error>
159    where
160        Self: Sized;
161
162    /// [`Parser::parse_inner`], but specialised for verbose output. Do not call this method directly.
163    ///
164    /// If you *really* need to implement this trait, this method should just directly invoke [`Parser::parse_inner`].
165    #[doc(hidden)]
166    #[deprecated(
167        note = "This method is excluded from the semver guarantees of chumsky. If you decide to use it, broken builds are your fault."
168    )]
169    fn parse_inner_verbose(
170        &self,
171        d: &mut Verbose,
172        s: &mut StreamOf<I, Self::Error>,
173    ) -> PResult<I, O, Self::Error>;
174
175    /// [`Parser::parse_inner`], but specialised for silent output. Do not call this method directly.
176    ///
177    /// If you *really* need to implement this trait, this method should just directly invoke [`Parser::parse_inner`].
178    #[doc(hidden)]
179    #[deprecated(
180        note = "This method is excluded from the semver guarantees of chumsky. If you decide to use it, broken builds are your fault."
181    )]
182    fn parse_inner_silent(
183        &self,
184        d: &mut Silent,
185        s: &mut StreamOf<I, Self::Error>,
186    ) -> PResult<I, O, Self::Error>;
187
188    /// Parse a stream of tokens, yielding an output if possible, and any errors encountered along the way.
189    ///
190    /// If `None` is returned (i.e: parsing failed) then there will *always* be at least one item in the error `Vec`.
191    /// If you don't care about producing an output if errors are encountered, use [`Parser::parse`] instead.
192    ///
193    /// Although the signature of this function looks complicated, it's simpler than you think! You can pass a
194    /// `&[I]`, a [`&str`], or a [`Stream`] to it.
195    fn parse_recovery<'a, Iter, S>(&self, stream: S) -> (Option<O>, Vec<Self::Error>)
196    where
197        Self: Sized,
198        Iter: Iterator<Item = (I, <Self::Error as Error<I>>::Span)> + 'a,
199        S: Into<Stream<'a, I, <Self::Error as Error<I>>::Span, Iter>>,
200    {
201        parse_recovery_inner(self, &mut Silent::new(), stream)
202    }
203
204    /// Parse a stream of tokens, yielding an output if possible, and any errors encountered along the way. Unlike
205    /// [`Parser::parse_recovery`], this function will produce verbose debugging output as it executes.
206    ///
207    /// If `None` is returned (i.e: parsing failed) then there will *always* be at least one item in the error `Vec`.
208    /// If you don't care about producing an output if errors are encountered, use `Parser::parse` instead.
209    ///
210    /// Although the signature of this function looks complicated, it's simpler than you think! You can pass a
211    /// `&[I]`, a [`&str`], or a [`Stream`] to it.
212    ///
213    /// You'll probably want to make sure that this doesn't end up in production code: it exists only to help you debug
214    /// your parser. Additionally, its API is quite likely to change in future versions.
215    ///
216    /// This method will receive more extensive documentation as the crate's debugging features mature.
217    fn parse_recovery_verbose<'a, Iter, S>(&self, stream: S) -> (Option<O>, Vec<Self::Error>)
218    where
219        Self: Sized,
220        Iter: Iterator<Item = (I, <Self::Error as Error<I>>::Span)> + 'a,
221        S: Into<Stream<'a, I, <Self::Error as Error<I>>::Span, Iter>>,
222    {
223        let mut debugger = Verbose::new();
224        let res = parse_recovery_inner(self, &mut debugger, stream);
225        debugger.print();
226        res
227    }
228
229    /// Parse a stream of tokens, yielding an output *or* any errors that were encountered along the way.
230    ///
231    /// If you wish to attempt to produce an output even if errors are encountered, use [`Parser::parse_recovery`].
232    ///
233    /// Although the signature of this function looks complicated, it's simpler than you think! You can pass a
234    /// [`&[I]`], a [`&str`], or a [`Stream`] to it.
235    fn parse<'a, Iter, S>(&self, stream: S) -> Result<O, Vec<Self::Error>>
236    where
237        Self: Sized,
238        Iter: Iterator<Item = (I, <Self::Error as Error<I>>::Span)> + 'a,
239        S: Into<Stream<'a, I, <Self::Error as Error<I>>::Span, Iter>>,
240    {
241        let (output, errors) = self.parse_recovery(stream);
242        if errors.is_empty() {
243            Ok(output.expect(
244                "Parsing failed, but no errors were emitted. This is troubling, to say the least.",
245            ))
246        } else {
247            Err(errors)
248        }
249    }
250
251    /// Include this parser in the debugging output produced by [`Parser::parse_recovery_verbose`].
252    ///
253    /// You'll probably want to make sure that this doesn't end up in production code: it exists only to help you debug
254    /// your parser. Additionally, its API is quite likely to change in future versions.
255    /// Use this parser like a print statement, to display whatever you pass as the argument 'x'
256    ///
257    /// This method will receive more extensive documentation as the crate's debugging features mature.
258    #[track_caller]
259    fn debug<T>(self, x: T) -> Debug<Self>
260    where
261        Self: Sized,
262        T: fmt::Display + 'static,
263    {
264        Debug(self, Rc::new(x), *core::panic::Location::caller())
265    }
266
267    /// Map the output of this parser to another value.
268    ///
269    /// The output type of this parser is `U`, the same as the function's output.
270    ///
271    /// # Examples
272    ///
273    /// ```
274    /// # use chumsky::{prelude::*, error::Cheap};
275    /// #[derive(Debug, PartialEq)]
276    /// enum Token { Word(String), Num(u64) }
277    ///
278    /// let word = filter::<_, _, Cheap<char>>(|c: &char| c.is_alphabetic())
279    ///     .repeated().at_least(1)
280    ///     .collect::<String>()
281    ///     .map(Token::Word);
282    ///
283    /// let num = filter::<_, _, Cheap<char>>(|c: &char| c.is_ascii_digit())
284    ///     .repeated().at_least(1)
285    ///     .collect::<String>()
286    ///     .map(|s| Token::Num(s.parse().unwrap()));
287    ///
288    /// let token = word.or(num);
289    ///
290    /// assert_eq!(token.parse("test"), Ok(Token::Word("test".to_string())));
291    /// assert_eq!(token.parse("42"), Ok(Token::Num(42)));
292    /// ```
293    fn map<U, F>(self, f: F) -> Map<Self, F, O>
294    where
295        Self: Sized,
296        F: Fn(O) -> U,
297    {
298        Map(self, f, PhantomData)
299    }
300
301    /// Map the output of this parser to another value, making use of the pattern's span when doing so.
302    ///
303    /// This is very useful when generating an AST that attaches a span to each AST node.
304    ///
305    /// The output type of this parser is `U`, the same as the function's output.
306    ///
307    /// # Examples
308    ///
309    /// ```
310    /// # use chumsky::prelude::*;
311    /// use std::ops::Range;
312    ///
313    /// // It's common for AST nodes to use a wrapper type that allows attaching span information to them
314    /// #[derive(Debug, PartialEq)]
315    /// pub struct Spanned<T>(T, Range<usize>);
316    ///
317    /// let ident = text::ident::<_, Simple<char>>()
318    ///     .map_with_span(|ident, span| Spanned(ident, span))
319    ///     .padded();
320    ///
321    /// assert_eq!(ident.parse("hello"), Ok(Spanned("hello".to_string(), 0..5)));
322    /// assert_eq!(ident.parse("       hello   "), Ok(Spanned("hello".to_string(), 7..12)));
323    /// ```
324    fn map_with_span<U, F>(self, f: F) -> MapWithSpan<Self, F, O>
325    where
326        Self: Sized,
327        F: Fn(O, <Self::Error as Error<I>>::Span) -> U,
328    {
329        MapWithSpan(self, f, PhantomData)
330    }
331
332    /// Map the primary error of this parser to another value.
333    ///
334    /// This function is most useful when using a custom error type, allowing you to augment errors according to
335    /// context.
336    ///
337    /// The output type of this parser is `O`, the same as the original parser.
338    // TODO: Map E -> D, not E -> E
339    fn map_err<F>(self, f: F) -> MapErr<Self, F>
340    where
341        Self: Sized,
342        F: Fn(Self::Error) -> Self::Error,
343    {
344        MapErr(self, f)
345    }
346
347    /// Map the primary error of this parser to a result. If the result is [`Ok`], the parser succeeds with that value.
348    ///
349    /// Note that even if the function returns an [`Ok`], the input stream will still be 'stuck' at the input following
350    /// the input that triggered the error. You'll need to follow uses of this combinator with a parser that resets
351    /// the input stream to a known-good state (for example, [`take_until`]).
352    ///
353    /// The output type of this parser is `U`, the [`Ok`] type of the result.
354    fn or_else<F>(self, f: F) -> OrElse<Self, F>
355    where
356        Self: Sized,
357        F: Fn(Self::Error) -> Result<O, Self::Error>,
358    {
359        OrElse(self, f)
360    }
361
362    /// Map the primary error of this parser to another value, making use of the span from the start of the attempted
363    /// to the point at which the error was encountered.
364    ///
365    /// This function is useful for augmenting errors to allow them to display the span of the initial part of a
366    /// pattern, for example to add a "while parsing" clause to your error messages.
367    ///
368    /// The output type of this parser is `O`, the same as the original parser.
369    ///
370    // TODO: Map E -> D, not E -> E
371    fn map_err_with_span<F>(self, f: F) -> MapErrWithSpan<Self, F>
372    where
373        Self: Sized,
374        F: Fn(Self::Error, <Self::Error as Error<I>>::Span) -> Self::Error,
375    {
376        MapErrWithSpan(self, f)
377    }
378
379    /// After a successful parse, apply a fallible function to the output. If the function produces an error, treat it
380    /// as a parsing error.
381    ///
382    /// If you wish parsing of this pattern to continue when an error is generated instead of halting, consider using
383    /// [`Parser::validate`] instead.
384    ///
385    /// The output type of this parser is `U`, the [`Ok`] return value of the function.
386    ///
387    /// # Examples
388    ///
389    /// ```
390    /// # use chumsky::prelude::*;
391    /// let byte = text::int::<_, Simple<char>>(10)
392    ///     .try_map(|s, span| s
393    ///         .parse::<u8>()
394    ///         .map_err(|e| Simple::custom(span, format!("{}", e))));
395    ///
396    /// assert!(byte.parse("255").is_ok());
397    /// assert!(byte.parse("256").is_err()); // Out of range
398    /// ```
399    fn try_map<U, F>(self, f: F) -> TryMap<Self, F, O>
400    where
401        Self: Sized,
402        F: Fn(O, <Self::Error as Error<I>>::Span) -> Result<U, Self::Error>,
403    {
404        TryMap(self, f, PhantomData)
405    }
406
407    /// Validate an output, producing non-terminal errors if it does not fulfil certain criteria.
408    ///
409    /// This function also permits mapping the output to a value of another type, similar to [`Parser::map`].
410    ///
411    /// If you wish parsing of this pattern to halt when an error is generated instead of continuing, consider using
412    /// [`Parser::try_map`] instead.
413    ///
414    /// The output type of this parser is `O`, the same as the original parser.
415    ///
416    /// # Examples
417    ///
418    /// ```
419    /// # use chumsky::prelude::*;
420    /// let large_int = text::int::<char, _>(10)
421    ///     .from_str()
422    ///     .unwrapped()
423    ///     .validate(|x: u32, span, emit| {
424    ///         if x < 256 { emit(Simple::custom(span, format!("{} must be 256 or higher.", x))) }
425    ///         x
426    ///     });
427    ///
428    /// assert_eq!(large_int.parse("537"), Ok(537));
429    /// assert!(large_int.parse("243").is_err());
430    /// ```
431    fn validate<F, U>(self, f: F) -> Validate<Self, O, F>
432    where
433        Self: Sized,
434        F: Fn(O, <Self::Error as Error<I>>::Span, &mut dyn FnMut(Self::Error)) -> U,
435    {
436        Validate(self, f, PhantomData)
437    }
438
439    /// Label the pattern parsed by this parser for more useful error messages.
440    ///
441    /// This is useful when you want to give users a more useful description of an expected pattern than simply a list
442    /// of possible initial tokens. For example, it's common to use the term "expression" at a catch-all for a number
443    /// of different constructs in many languages.
444    ///
445    /// This does not label recovered errors generated by sub-patterns within the parser, only error *directly* emitted
446    /// by the parser.
447    ///
448    /// This does not label errors where the labelled pattern consumed input (i.e: in unambiguous cases).
449    ///
450    /// The output type of this parser is `O`, the same as the original parser.
451    ///
452    /// *Note: There is a chance that this method will be deprecated in favour of a more general solution in later
453    /// versions of the crate.*
454    ///
455    /// # Examples
456    ///
457    /// ```
458    /// # use chumsky::{prelude::*, error::Cheap};
459    /// let frac = text::digits(10)
460    ///     .chain(just('.'))
461    ///     .chain::<char, _, _>(text::digits(10))
462    ///     .collect::<String>()
463    ///     .then_ignore(end())
464    ///     .labelled("number");
465    ///
466    /// assert_eq!(frac.parse("42.3"), Ok("42.3".to_string()));
467    /// assert_eq!(frac.parse("hello"), Err(vec![Cheap::expected_input_found(0..1, Vec::new(), Some('h')).with_label("number")]));
468    /// assert_eq!(frac.parse("42!"), Err(vec![Cheap::expected_input_found(2..3, vec![Some('.')], Some('!')).with_label("number")]));
469    /// ```
470    fn labelled<L>(self, label: L) -> Label<Self, L>
471    where
472        Self: Sized,
473        L: Into<<Self::Error as Error<I>>::Label> + Clone,
474    {
475        Label(self, label)
476    }
477
478    /// Transform all outputs of this parser to a pretermined value.
479    ///
480    /// The output type of this parser is `U`, the type of the predetermined value.
481    ///
482    /// # Examples
483    ///
484    /// ```
485    /// # use chumsky::{prelude::*, error::Cheap};
486    /// #[derive(Clone, Debug, PartialEq)]
487    /// enum Op { Add, Sub, Mul, Div }
488    ///
489    /// let op = just::<_, _, Cheap<char>>('+').to(Op::Add)
490    ///     .or(just('-').to(Op::Sub))
491    ///     .or(just('*').to(Op::Mul))
492    ///     .or(just('/').to(Op::Div));
493    ///
494    /// assert_eq!(op.parse("+"), Ok(Op::Add));
495    /// assert_eq!(op.parse("/"), Ok(Op::Div));
496    /// ```
497    fn to<U>(self, x: U) -> To<Self, O, U>
498    where
499        Self: Sized,
500        U: Clone,
501    {
502        To(self, x, PhantomData)
503    }
504
505    /// Left-fold the output of the parser into a single value.
506    ///
507    /// The output of the original parser must be of type `(A, impl IntoIterator<Item = B>)`.
508    ///
509    /// The output type of this parser is `A`, the left-hand component of the original parser's output.
510    ///
511    /// # Examples
512    ///
513    /// ```
514    /// # use chumsky::{prelude::*, error::Cheap};
515    /// let int = text::int::<char, Cheap<char>>(10)
516    ///     .from_str()
517    ///     .unwrapped();
518    ///
519    /// let sum = int
520    ///     .then(just('+').ignore_then(int).repeated())
521    ///     .foldl(|a, b| a + b);
522    ///
523    /// assert_eq!(sum.parse("1+12+3+9"), Ok(25));
524    /// assert_eq!(sum.parse("6"), Ok(6));
525    /// ```
526    fn foldl<A, B, F>(self, f: F) -> Foldl<Self, F, A, B>
527    where
528        Self: Parser<I, (A, B)> + Sized,
529        B: IntoIterator,
530        F: Fn(A, B::Item) -> A,
531    {
532        Foldl(self, f, PhantomData)
533    }
534
535    /// Right-fold the output of the parser into a single value.
536    ///
537    /// The output of the original parser must be of type `(impl IntoIterator<Item = A>, B)`. Because right-folds work
538    /// backwards, the iterator must implement [`DoubleEndedIterator`] so that it can be reversed.
539    ///
540    /// The output type of this parser is `B`, the right-hand component of the original parser's output.
541    ///
542    /// # Examples
543    ///
544    /// ```
545    /// # use chumsky::{prelude::*, error::Cheap};
546    /// let int = text::int::<char, Cheap<char>>(10)
547    ///     .from_str()
548    ///     .unwrapped();
549    ///
550    /// let signed = just('+').to(1)
551    ///     .or(just('-').to(-1))
552    ///     .repeated()
553    ///     .then(int)
554    ///     .foldr(|a, b| a * b);
555    ///
556    /// assert_eq!(signed.parse("3"), Ok(3));
557    /// assert_eq!(signed.parse("-17"), Ok(-17));
558    /// assert_eq!(signed.parse("--+-+-5"), Ok(5));
559    /// ```
560    fn foldr<'a, A, B, F>(self, f: F) -> Foldr<Self, F, A, B>
561    where
562        Self: Parser<I, (A, B)> + Sized,
563        A: IntoIterator,
564        A::IntoIter: DoubleEndedIterator,
565        F: Fn(A::Item, B) -> B + 'a,
566    {
567        Foldr(self, f, PhantomData)
568    }
569
570    /// Ignore the output of this parser, yielding `()` as an output instead.
571    ///
572    /// This can be used to reduce the cost of parsing by avoiding unnecessary allocations (most collections containing
573    /// [ZSTs](https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts)
574    /// [do not allocate](https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees)). For example, it's common to
575    /// want to ignore whitespace in many grammars (see [`text::whitespace`]).
576    ///
577    /// The output type of this parser is `()`.
578    ///
579    /// # Examples
580    ///
581    /// ```
582    /// # use chumsky::{prelude::*, error::Cheap};
583    /// // A parser that parses any number of whitespace characters without allocating
584    /// let whitespace = filter::<_, _, Cheap<char>>(|c: &char| c.is_whitespace())
585    ///     .ignored()
586    ///     .repeated();
587    ///
588    /// assert_eq!(whitespace.parse("    "), Ok(vec![(); 4]));
589    /// assert_eq!(whitespace.parse("  hello"), Ok(vec![(); 2]));
590    /// ```
591    fn ignored(self) -> Ignored<Self, O>
592    where
593        Self: Sized,
594    {
595        To(self, (), PhantomData)
596    }
597
598    /// Collect the output of this parser into a type implementing [`FromIterator`].
599    ///
600    /// This is commonly useful for collecting [`Vec<char>`] outputs into [`String`]s, or [`(T, U)`] into a
601    /// [`HashMap`] and is analogous to [`Iterator::collect`].
602    ///
603    /// The output type of this parser is `C`, the type being collected into.
604    ///
605    /// # Examples
606    ///
607    /// ```
608    /// # use chumsky::{prelude::*, error::Cheap};
609    /// let word = filter::<_, _, Cheap<char>>(|c: &char| c.is_alphabetic()) // This parser produces an output of `char`
610    ///     .repeated() // This parser produces an output of `Vec<char>`
611    ///     .collect::<String>(); // But `Vec<char>` is less useful than `String`, so convert to the latter
612    ///
613    /// assert_eq!(word.parse("hello"), Ok("hello".to_string()));
614    /// ```
615    // TODO: Make `Parser::repeated` generic over an `impl FromIterator` to reduce required allocations
616    fn collect<C>(self) -> Map<Self, fn(O) -> C, O>
617    where
618        Self: Sized,
619        O: IntoIterator,
620        C: core::iter::FromIterator<O::Item>,
621    {
622        self.map(|items| C::from_iter(items.into_iter()))
623    }
624
625    /// Parse one thing and then another thing, yielding a tuple of the two outputs.
626    ///
627    /// The output type of this parser is `(O, U)`, a combination of the outputs of both parsers.
628    ///
629    /// # Examples
630    ///
631    /// ```
632    /// # use chumsky::{prelude::*, error::Cheap};
633    /// let word = filter::<_, _, Cheap<char>>(|c: &char| c.is_alphabetic())
634    ///     .repeated().at_least(1)
635    ///     .collect::<String>();
636    /// let two_words = word.then_ignore(just(' ')).then(word);
637    ///
638    /// assert_eq!(two_words.parse("dog cat"), Ok(("dog".to_string(), "cat".to_string())));
639    /// assert!(two_words.parse("hedgehog").is_err());
640    /// ```
641    fn then<U, P>(self, other: P) -> Then<Self, P>
642    where
643        Self: Sized,
644        P: Parser<I, U, Error = Self::Error>,
645    {
646        Then(self, other)
647    }
648
649    /// Parse one thing and then another thing, creating the second parser from the result of
650    /// the first. If you only have a couple cases to handle, prefer [`Parser::or`].
651    ///
652    /// The output of this parser is `U`, the result of the second parser
653    ///
654    /// Error recovery for this parser may be sub-optimal, as if the first parser succeeds on
655    /// recovery then the second produces an error, the primary error will point to the location in
656    /// the second parser which failed, ignoring that the first parser may be the root cause. There
657    /// may be other pathological errors cases as well.
658    ///
659    /// # Examples
660    ///
661    /// ```
662    /// # use chumsky::{prelude::*, error::Cheap};
663    /// // A parser that parses a single letter and then its successor
664    /// let successive_letters = one_of::<_, _, Cheap<u8>>((b'a'..=b'z').collect::<Vec<u8>>())
665    ///     .then_with(|letter: u8| just(letter + 1));
666    ///
667    /// assert_eq!(successive_letters.parse(*b"ab"), Ok(b'b')); // 'b' follows 'a'
668    /// assert!(successive_letters.parse(*b"ac").is_err()); // 'c' does not follow 'a'
669    /// ```
670    fn then_with<U, P, F: Fn(O) -> P>(self, other: F) -> ThenWith<I, O, U, Self, P, F>
671    where
672        Self: Sized,
673        P: Parser<I, U, Error = Self::Error>,
674    {
675        ThenWith(self, other, PhantomData)
676    }
677
678    /// Parse one thing and then another thing, attempting to chain the two outputs into a [`Vec`].
679    ///
680    /// The output type of this parser is `Vec<T>`, composed of the elements of the outputs of both parsers.
681    ///
682    /// # Examples
683    ///
684    /// ```
685    /// # use chumsky::{prelude::*, error::Cheap};
686    /// let int = just('-').or_not()
687    ///     .chain(filter::<_, _, Cheap<char>>(|c: &char| c.is_ascii_digit() && *c != '0')
688    ///         .chain(filter::<_, _, Cheap<char>>(|c: &char| c.is_ascii_digit()).repeated()))
689    ///     .or(just('0').map(|c| vec![c]))
690    ///     .then_ignore(end())
691    ///     .collect::<String>()
692    ///     .from_str()
693    ///     .unwrapped();
694    ///
695    /// assert_eq!(int.parse("0"), Ok(0));
696    /// assert_eq!(int.parse("415"), Ok(415));
697    /// assert_eq!(int.parse("-50"), Ok(-50));
698    /// assert!(int.parse("-0").is_err());
699    /// assert!(int.parse("05").is_err());
700    /// ```
701    fn chain<T, U, P>(self, other: P) -> Map<Then<Self, P>, fn((O, U)) -> Vec<T>, (O, U)>
702    where
703        Self: Sized,
704        U: Chain<T>,
705        O: Chain<T>,
706        P: Parser<I, U, Error = Self::Error>,
707    {
708        self.then(other).map(|(a, b)| {
709            let mut v = Vec::with_capacity(a.len() + b.len());
710            a.append_to(&mut v);
711            b.append_to(&mut v);
712            v
713        })
714    }
715
716    /// Flatten a nested collection.
717    ///
718    /// This use-cases of this method are broadly similar to those of [`Iterator::flatten`].
719    ///
720    /// The output type of this parser is `Vec<T>`, where the original parser output was
721    /// `impl IntoIterator<Item = impl IntoIterator<Item = T>>`.
722    fn flatten<T, Inner>(self) -> Map<Self, fn(O) -> Vec<T>, O>
723    where
724        Self: Sized,
725        O: IntoIterator<Item = Inner>,
726        Inner: IntoIterator<Item = T>,
727    {
728        self.map(|xs| xs.into_iter().flat_map(|xs| xs.into_iter()).collect())
729    }
730
731    /// Parse one thing and then another thing, yielding only the output of the latter.
732    ///
733    /// The output type of this parser is `U`, the same as the second parser.
734    ///
735    /// # Examples
736    ///
737    /// ```
738    /// # use chumsky::{prelude::*, error::Cheap};
739    /// let zeroes = filter::<_, _, Cheap<char>>(|c: &char| *c == '0').ignored().repeated();
740    /// let digits = filter(|c: &char| c.is_ascii_digit()).repeated();
741    /// let integer = zeroes
742    ///     .ignore_then(digits)
743    ///     .collect::<String>()
744    ///     .from_str()
745    ///     .unwrapped();
746    ///
747    /// assert_eq!(integer.parse("00064"), Ok(64));
748    /// assert_eq!(integer.parse("32"), Ok(32));
749    /// ```
750    fn ignore_then<U, P>(self, other: P) -> IgnoreThen<Self, P, O, U>
751    where
752        Self: Sized,
753        P: Parser<I, U, Error = Self::Error>,
754    {
755        Map(Then(self, other), |(_, u)| u, PhantomData)
756    }
757
758    /// Parse one thing and then another thing, yielding only the output of the former.
759    ///
760    /// The output type of this parser is `O`, the same as the original parser.
761    ///
762    /// # Examples
763    ///
764    /// ```
765    /// # use chumsky::{prelude::*, error::Cheap};
766    /// let word = filter::<_, _, Cheap<char>>(|c: &char| c.is_alphabetic())
767    ///     .repeated().at_least(1)
768    ///     .collect::<String>();
769    ///
770    /// let punctuated = word
771    ///     .then_ignore(just('!').or(just('?')).or_not());
772    ///
773    /// let sentence = punctuated
774    ///     .padded() // Allow for whitespace gaps
775    ///     .repeated();
776    ///
777    /// assert_eq!(
778    ///     sentence.parse("hello! how are you?"),
779    ///     Ok(vec![
780    ///         "hello".to_string(),
781    ///         "how".to_string(),
782    ///         "are".to_string(),
783    ///         "you".to_string(),
784    ///     ]),
785    /// );
786    /// ```
787    fn then_ignore<U, P>(self, other: P) -> ThenIgnore<Self, P, O, U>
788    where
789        Self: Sized,
790        P: Parser<I, U, Error = Self::Error>,
791    {
792        Map(Then(self, other), |(o, _)| o, PhantomData)
793    }
794
795    /// Parse a pattern, but with an instance of another pattern on either end, yielding the output of the inner.
796    ///
797    /// The output type of this parser is `O`, the same as the original parser.
798    ///
799    /// # Examples
800    ///
801    /// ```
802    /// # use chumsky::{prelude::*, error::Cheap};
803    /// let ident = text::ident::<_, Simple<char>>()
804    ///     .padded_by(just('!'));
805    ///
806    /// assert_eq!(ident.parse("!hello!"), Ok("hello".to_string()));
807    /// assert!(ident.parse("hello!").is_err());
808    /// assert!(ident.parse("!hello").is_err());
809    /// assert!(ident.parse("hello").is_err());
810    /// ```
811    fn padded_by<U, P>(self, other: P) -> ThenIgnore<IgnoreThen<P, Self, U, O>, P, O, U>
812    where
813        Self: Sized,
814        P: Parser<I, U, Error = Self::Error> + Clone,
815    {
816        other.clone().ignore_then(self).then_ignore(other)
817    }
818
819    /// Parse the pattern surrounded by the given delimiters.
820    ///
821    /// The output type of this parser is `O`, the same as the original parser.
822    ///
823    /// # Examples
824    ///
825    /// ```
826    /// # use chumsky::{prelude::*, error::Cheap};
827    /// // A LISP-style S-expression
828    /// #[derive(Debug, PartialEq)]
829    /// enum SExpr {
830    ///     Ident(String),
831    ///     Num(u64),
832    ///     List(Vec<SExpr>),
833    /// }
834    ///
835    /// let ident = filter::<_, _, Cheap<char>>(|c: &char| c.is_alphabetic())
836    ///     .repeated().at_least(1)
837    ///     .collect::<String>();
838    ///
839    /// let num = text::int(10)
840    ///     .from_str()
841    ///     .unwrapped();
842    ///
843    /// let s_expr = recursive(|s_expr| s_expr
844    ///     .padded()
845    ///     .repeated()
846    ///     .map(SExpr::List)
847    ///     .delimited_by(just('('), just(')'))
848    ///     .or(ident.map(SExpr::Ident))
849    ///     .or(num.map(SExpr::Num)));
850    ///
851    /// // A valid input
852    /// assert_eq!(
853    ///     s_expr.parse_recovery("(add (mul 42 3) 15)"),
854    ///     (
855    ///         Some(SExpr::List(vec![
856    ///             SExpr::Ident("add".to_string()),
857    ///             SExpr::List(vec![
858    ///                 SExpr::Ident("mul".to_string()),
859    ///                 SExpr::Num(42),
860    ///                 SExpr::Num(3),
861    ///             ]),
862    ///             SExpr::Num(15),
863    ///         ])),
864    ///         Vec::new(), // No errors!
865    ///     ),
866    /// );
867    /// ```
868    fn delimited_by<U, V, L, R>(self, start: L, end: R) -> DelimitedBy<Self, L, R, U, V>
869    where
870        Self: Sized,
871        L: Parser<I, U, Error = Self::Error>,
872        R: Parser<I, V, Error = Self::Error>,
873    {
874        DelimitedBy {
875            item: self,
876            start,
877            end,
878            phantom: PhantomData,
879        }
880    }
881
882    /// Parse one thing or, on failure, another thing.
883    ///
884    /// The output of both parsers must be of the same type, because either output can be produced.
885    ///
886    /// If both parser succeed, the output of the first parser is guaranteed to be prioritised over the output of the
887    /// second.
888    ///
889    /// If both parsers produce errors, the combinator will attempt to select from or combine the errors to produce an
890    /// error that is most likely to be useful to a human attempting to understand the problem. The exact algorithm
891    /// used is left unspecified, and is not part of the crate's semver guarantees, although regressions in error
892    /// quality should be reported in the issue tracker of the main repository.
893    ///
894    /// Please note that long chains of [`Parser::or`] combinators have been known to result in poor compilation times.
895    /// If you feel you are experiencing this, consider using [`choice`] instead.
896    ///
897    /// The output type of this parser is `O`, the output of both parsers.
898    ///
899    /// # Examples
900    ///
901    /// ```
902    /// # use chumsky::{prelude::*, error::Cheap};
903    /// let op = just::<_, _, Cheap<char>>('+')
904    ///     .or(just('-'))
905    ///     .or(just('*'))
906    ///     .or(just('/'));
907    ///
908    /// assert_eq!(op.parse("+"), Ok('+'));
909    /// assert_eq!(op.parse("/"), Ok('/'));
910    /// assert!(op.parse("!").is_err());
911    /// ```
912    fn or<P>(self, other: P) -> Or<Self, P>
913    where
914        Self: Sized,
915        P: Parser<I, O, Error = Self::Error>,
916    {
917        Or(self, other)
918    }
919
920    /// Apply a fallback recovery strategy to this parser should it fail.
921    ///
922    /// There is no silver bullet for error recovery, so this function allows you to specify one of several different
923    /// strategies at the location of your choice. Prefer an error recovery strategy that more precisely mirrors valid
924    /// syntax where possible to make error recovery more reliable.
925    ///
926    /// Because chumsky is a [PEG](https://en.m.wikipedia.org/wiki/Parsing_expression_grammar) parser, which always
927    /// take the first successful parsing route through a grammar, recovering from an error may cause the parser to
928    /// erroneously miss alternative valid routes through the grammar that do not generate recoverable errors. If you
929    /// run into cases where valid syntax fails to parse without errors, this might be happening: consider removing
930    /// error recovery or switching to a more specific error recovery strategy.
931    ///
932    /// The output type of this parser is `O`, the same as the original parser.
933    ///
934    /// # Examples
935    ///
936    /// ```
937    /// # use chumsky::{prelude::*, error::Cheap};
938    /// #[derive(Debug, PartialEq)]
939    /// enum Expr {
940    ///     Error,
941    ///     Int(String),
942    ///     List(Vec<Expr>),
943    /// }
944    ///
945    /// let expr = recursive::<_, _, _, _, Simple<char>>(|expr| expr
946    ///     .separated_by(just(','))
947    ///     .delimited_by(just('['), just(']'))
948    ///     .map(Expr::List)
949    ///     // If parsing a list expression fails, recover at the next delimiter, generating an error AST node
950    ///     .recover_with(nested_delimiters('[', ']', [], |_| Expr::Error))
951    ///     .or(text::int(10).map(Expr::Int))
952    ///     .padded());
953    ///
954    /// assert!(expr.parse("five").is_err()); // Text is not a valid expression in this language...
955    /// assert!(expr.parse("[1, 2, 3]").is_ok()); // ...but lists and numbers are!
956    ///
957    /// // This input has two syntax errors...
958    /// let (ast, errors) = expr.parse_recovery("[[1, two], [3, four]]");
959    /// // ...and error recovery allows us to catch both of them!
960    /// assert_eq!(errors.len(), 2);
961    /// // Additionally, the AST we get back still has useful information.
962    /// assert_eq!(ast, Some(Expr::List(vec![Expr::Error, Expr::Error])));
963    /// ```
964    fn recover_with<S>(self, strategy: S) -> Recovery<Self, S>
965    where
966        Self: Sized,
967        S: Strategy<I, O, Self::Error>,
968    {
969        Recovery(self, strategy)
970    }
971
972    /// Attempt to parse something, but only if it exists.
973    ///
974    /// If parsing of the pattern is successful, the output is `Some(_)`. Otherwise, the output is `None`.
975    ///
976    /// The output type of this parser is `Option<O>`.
977    ///
978    /// # Examples
979    ///
980    /// ```
981    /// # use chumsky::{prelude::*, error::Cheap};
982    /// let word = filter::<_, _, Cheap<char>>(|c: &char| c.is_alphabetic())
983    ///     .repeated().at_least(1)
984    ///     .collect::<String>();
985    ///
986    /// let word_or_question = word
987    ///     .then(just('?').or_not());
988    ///
989    /// assert_eq!(word_or_question.parse("hello?"), Ok(("hello".to_string(), Some('?'))));
990    /// assert_eq!(word_or_question.parse("wednesday"), Ok(("wednesday".to_string(), None)));
991    /// ```
992    fn or_not(self) -> OrNot<Self>
993    where
994        Self: Sized,
995    {
996        OrNot(self)
997    }
998
999    /// Parses a single token if, and only if, the pattern fails to parse.
1000    ///
1001    /// The output type of this parser is `I`.
1002    ///
1003    /// # Examples
1004    ///
1005    /// ```
1006    /// # use chumsky::{prelude::*, error::Cheap};
1007    ///
1008    /// #[derive(Debug, PartialEq)]
1009    /// enum Tree {
1010    ///     Text(String),
1011    ///     Group(Vec<Self>),
1012    /// }
1013    ///
1014    /// // Arbitrary text, nested in a tree with { ... } delimiters
1015    /// let tree = recursive::<_, _, _, _, Cheap<char>>(|tree| {
1016    ///     let text = one_of("{}")
1017    ///         .not()
1018    ///         .repeated()
1019    ///         .at_least(1)
1020    ///         .collect()
1021    ///         .map(Tree::Text);
1022    ///
1023    ///     let group = tree
1024    ///         .repeated()
1025    ///         .delimited_by(just('{'), just('}'))
1026    ///         .map(Tree::Group);
1027    ///
1028    ///     text.or(group)
1029    /// });
1030    ///
1031    /// assert_eq!(
1032    ///     tree.parse("{abcd{efg{hijk}lmn{opq}rs}tuvwxyz}"),
1033    ///     Ok(Tree::Group(vec![
1034    ///         Tree::Text("abcd".to_string()),
1035    ///         Tree::Group(vec![
1036    ///             Tree::Text("efg".to_string()),
1037    ///             Tree::Group(vec![
1038    ///                 Tree::Text("hijk".to_string()),
1039    ///             ]),
1040    ///             Tree::Text("lmn".to_string()),
1041    ///             Tree::Group(vec![
1042    ///                 Tree::Text("opq".to_string()),
1043    ///             ]),
1044    ///             Tree::Text("rs".to_string()),
1045    ///         ]),
1046    ///         Tree::Text("tuvwxyz".to_string()),
1047    ///     ])),
1048    /// );
1049    /// ```
1050    fn not(self) -> Not<Self, O>
1051    where
1052        Self: Sized,
1053    {
1054        Not(self, PhantomData)
1055    }
1056
1057    /// Parse a pattern any number of times (including zero times).
1058    ///
1059    /// Input is eagerly parsed. Be aware that the parser will accept no occurrences of the pattern too. Consider using
1060    /// [`Repeated::at_least`] instead if it better suits your use-case.
1061    ///
1062    /// The output type of this parser is `Vec<O>`.
1063    ///
1064    /// # Examples
1065    ///
1066    /// ```
1067    /// # use chumsky::{prelude::*, error::Cheap};
1068    /// let num = filter::<_, _, Cheap<char>>(|c: &char| c.is_ascii_digit())
1069    ///     .repeated().at_least(1)
1070    ///     .collect::<String>()
1071    ///     .from_str()
1072    ///     .unwrapped();
1073    ///
1074    /// let sum = num.then(just('+').ignore_then(num).repeated())
1075    ///     .foldl(|a, b| a + b);
1076    ///
1077    /// assert_eq!(sum.parse("2+13+4+0+5"), Ok(24));
1078    /// ```
1079    fn repeated(self) -> Repeated<Self>
1080    where
1081        Self: Sized,
1082    {
1083        Repeated(self, 0, None)
1084    }
1085
1086    /// Parse a pattern, separated by another, any number of times.
1087    ///
1088    /// You can use [`SeparatedBy::allow_leading`] or [`SeparatedBy::allow_trailing`] to allow leading or trailing
1089    /// separators.
1090    ///
1091    /// The output type of this parser is `Vec<O>`.
1092    ///
1093    /// # Examples
1094    ///
1095    /// ```
1096    /// # use chumsky::{prelude::*, error::Cheap};
1097    /// let shopping = text::ident::<_, Simple<char>>()
1098    ///     .padded()
1099    ///     .separated_by(just(','));
1100    ///
1101    /// assert_eq!(shopping.parse("eggs"), Ok(vec!["eggs".to_string()]));
1102    /// assert_eq!(shopping.parse("eggs, flour, milk"), Ok(vec!["eggs".to_string(), "flour".to_string(), "milk".to_string()]));
1103    /// ```
1104    ///
1105    /// See [`SeparatedBy::allow_leading`] and [`SeparatedBy::allow_trailing`] for more examples.
1106    fn separated_by<U, P>(self, other: P) -> SeparatedBy<Self, P, U>
1107    where
1108        Self: Sized,
1109        P: Parser<I, U, Error = Self::Error>,
1110    {
1111        SeparatedBy {
1112            item: self,
1113            delimiter: other,
1114            at_least: 0,
1115            at_most: None,
1116            allow_leading: false,
1117            allow_trailing: false,
1118            phantom: PhantomData,
1119        }
1120    }
1121
1122    /// Parse a pattern. Afterwards, the input stream will be rewound to its original state, as if parsing had not
1123    /// occurred.
1124    ///
1125    /// This combinator is useful for cases in which you wish to avoid a parser accidentally consuming too much input,
1126    /// causing later parsers to fail as a result. A typical use-case of this is that you want to parse something that
1127    /// is not followed by something else.
1128    ///
1129    /// The output type of this parser is `O`, the same as the original parser.
1130    ///
1131    /// # Examples
1132    ///
1133    /// ```
1134    /// # use chumsky::prelude::*;
1135    /// let just_numbers = text::digits::<_, Simple<char>>(10)
1136    ///     .padded()
1137    ///     .then_ignore(none_of("+-*/").rewind())
1138    ///     .separated_by(just(','));
1139    /// // 3 is not parsed because it's followed by '+'.
1140    /// assert_eq!(just_numbers.parse("1, 2, 3 + 4"), Ok(vec!["1".to_string(), "2".to_string()]));
1141    /// ```
1142    fn rewind(self) -> Rewind<Self>
1143    where
1144        Self: Sized,
1145    {
1146        Rewind(self)
1147    }
1148
1149    /// Box the parser, yielding a parser that performs parsing through dynamic dispatch.
1150    ///
1151    /// Boxing a parser might be useful for:
1152    ///
1153    /// - Dynamically building up parsers at runtime
1154    ///
1155    /// - Improving compilation times (Rust can struggle to compile code containing very long types)
1156    ///
1157    /// - Passing a parser over an FFI boundary
1158    ///
1159    /// - Getting around compiler implementation problems with long types such as
1160    ///   [this](https://github.com/rust-lang/rust/issues/54540).
1161    ///
1162    /// - Places where you need to name the type of a parser
1163    ///
1164    /// Boxing a parser is broadly equivalent to boxing other combinators via dynamic dispatch, such as [`Iterator`].
1165    ///
1166    /// The output type of this parser is `O`, the same as the original parser.
1167    fn boxed<'a>(self) -> BoxedParser<'a, I, O, Self::Error>
1168    where
1169        Self: Sized + 'a,
1170    {
1171        BoxedParser(Rc::new(self))
1172    }
1173
1174    /// Attempt to convert the output of this parser into something else using Rust's [`FromStr`] trait.
1175    ///
1176    /// This is most useful when wanting to convert literal values into their corresponding Rust type, such as when
1177    /// parsing integers.
1178    ///
1179    /// The output type of this parser is `Result<U, U::Err>`, the result of attempting to parse the output, `O`, into
1180    /// the value `U`.
1181    ///
1182    /// # Examples
1183    ///
1184    /// ```
1185    /// # use chumsky::prelude::*;
1186    /// let uint64 = text::int::<_, Simple<char>>(10)
1187    ///     .from_str::<u64>()
1188    ///     .unwrapped();
1189    ///
1190    /// assert_eq!(uint64.parse("7"), Ok(7));
1191    /// assert_eq!(uint64.parse("42"), Ok(42));
1192    /// ```
1193    #[allow(clippy::wrong_self_convention)]
1194    fn from_str<U>(self) -> Map<Self, fn(O) -> Result<U, U::Err>, O>
1195    where
1196        Self: Sized,
1197        U: FromStr,
1198        O: AsRef<str>,
1199    {
1200        self.map(|o| o.as_ref().parse())
1201    }
1202
1203    /// For parsers that produce a [`Result`] as their output, unwrap the result (panicking if an [`Err`] is
1204    /// encountered).
1205    ///
1206    /// In general, this method should be avoided except in cases where all possible that the parser might produce can
1207    /// by parsed using [`FromStr`] without producing an error.
1208    ///
1209    /// This combinator is not named `unwrap` to avoid confusion: it unwraps *during parsing*, not immediately.
1210    ///
1211    /// The output type of this parser is `U`, the [`Ok`] value of the [`Result`].
1212    ///
1213    /// # Examples
1214    ///
1215    /// ```
1216    /// # use chumsky::prelude::*;
1217    /// let boolean = just::<_, _, Simple<char>>("true")
1218    ///     .or(just("false"))
1219    ///     .from_str::<bool>()
1220    ///     .unwrapped(); // Cannot panic: the only possible outputs generated by the parser are "true" or "false"
1221    ///
1222    /// assert_eq!(boolean.parse("true"), Ok(true));
1223    /// assert_eq!(boolean.parse("false"), Ok(false));
1224    /// // Does not panic, because the original parser only accepts "true" or "false"
1225    /// assert!(boolean.parse("42").is_err());
1226    /// ```
1227    #[track_caller]
1228    fn unwrapped<U, E>(self) -> Unwrapped<Self, E, <Self as Parser<I, O>>::Error>
1229    where
1230        Self: Sized + Parser<I, Result<U, E>>,
1231        E: fmt::Debug,
1232    {
1233        Unwrapped(Location::caller(), self, PhantomData)
1234    }
1235}
1236
1237impl<'a, I: Clone, O, T: Parser<I, O> + ?Sized> Parser<I, O> for &'a T {
1238    type Error = T::Error;
1239
1240    fn parse_inner<D: Debugger>(
1241        &self,
1242        debugger: &mut D,
1243        stream: &mut StreamOf<I, Self::Error>,
1244    ) -> PResult<I, O, Self::Error> {
1245        debugger.invoke::<_, _, T>(*self, stream)
1246    }
1247
1248    fn parse_inner_verbose(
1249        &self,
1250        d: &mut Verbose,
1251        s: &mut StreamOf<I, Self::Error>,
1252    ) -> PResult<I, O, Self::Error> {
1253        #[allow(deprecated)]
1254        self.parse_inner(d, s)
1255    }
1256    fn parse_inner_silent(
1257        &self,
1258        d: &mut Silent,
1259        s: &mut StreamOf<I, Self::Error>,
1260    ) -> PResult<I, O, Self::Error> {
1261        #[allow(deprecated)]
1262        self.parse_inner(d, s)
1263    }
1264}
1265
1266impl<I: Clone, O, T: Parser<I, O> + ?Sized> Parser<I, O> for Box<T> {
1267    type Error = T::Error;
1268
1269    fn parse_inner<D: Debugger>(
1270        &self,
1271        debugger: &mut D,
1272        stream: &mut StreamOf<I, Self::Error>,
1273    ) -> PResult<I, O, Self::Error> {
1274        debugger.invoke::<_, _, T>(&*self, stream)
1275    }
1276
1277    fn parse_inner_verbose(
1278        &self,
1279        d: &mut Verbose,
1280        s: &mut StreamOf<I, Self::Error>,
1281    ) -> PResult<I, O, Self::Error> {
1282        #[allow(deprecated)]
1283        self.parse_inner(d, s)
1284    }
1285    fn parse_inner_silent(
1286        &self,
1287        d: &mut Silent,
1288        s: &mut StreamOf<I, Self::Error>,
1289    ) -> PResult<I, O, Self::Error> {
1290        #[allow(deprecated)]
1291        self.parse_inner(d, s)
1292    }
1293}
1294
1295impl<I: Clone, O, T: Parser<I, O> + ?Sized> Parser<I, O> for Rc<T> {
1296    type Error = T::Error;
1297
1298    fn parse_inner<D: Debugger>(
1299        &self,
1300        debugger: &mut D,
1301        stream: &mut StreamOf<I, Self::Error>,
1302    ) -> PResult<I, O, Self::Error> {
1303        debugger.invoke::<_, _, T>(&*self, stream)
1304    }
1305
1306    fn parse_inner_verbose(
1307        &self,
1308        d: &mut Verbose,
1309        s: &mut StreamOf<I, Self::Error>,
1310    ) -> PResult<I, O, Self::Error> {
1311        #[allow(deprecated)]
1312        self.parse_inner(d, s)
1313    }
1314    fn parse_inner_silent(
1315        &self,
1316        d: &mut Silent,
1317        s: &mut StreamOf<I, Self::Error>,
1318    ) -> PResult<I, O, Self::Error> {
1319        #[allow(deprecated)]
1320        self.parse_inner(d, s)
1321    }
1322}
1323
1324impl<I: Clone, O, T: Parser<I, O> + ?Sized> Parser<I, O> for Arc<T> {
1325    type Error = T::Error;
1326
1327    fn parse_inner<D: Debugger>(
1328        &self,
1329        debugger: &mut D,
1330        stream: &mut StreamOf<I, Self::Error>,
1331    ) -> PResult<I, O, Self::Error> {
1332        debugger.invoke::<_, _, T>(&*self, stream)
1333    }
1334
1335    fn parse_inner_verbose(
1336        &self,
1337        d: &mut Verbose,
1338        s: &mut StreamOf<I, Self::Error>,
1339    ) -> PResult<I, O, Self::Error> {
1340        #[allow(deprecated)]
1341        self.parse_inner(d, s)
1342    }
1343    fn parse_inner_silent(
1344        &self,
1345        d: &mut Silent,
1346        s: &mut StreamOf<I, Self::Error>,
1347    ) -> PResult<I, O, Self::Error> {
1348        #[allow(deprecated)]
1349        self.parse_inner(d, s)
1350    }
1351}
1352
1353/// See [`Parser::boxed`].
1354///
1355/// This type is a [`repr(transparent)`](https://doc.rust-lang.org/nomicon/other-reprs.html#reprtransparent) wrapper
1356/// around its inner value.
1357///
1358/// Due to current implementation details, the inner value is not, in fact, a [`Box`], but is an [`Rc`] to facilitate
1359/// efficient cloning. This is likely to change in the future. Unlike [`Box`], [`Rc`] has no size guarantees: although
1360/// it is *currently* the same size as a raw pointer.
1361// TODO: Don't use an Rc
1362#[must_use]
1363#[repr(transparent)]
1364pub struct BoxedParser<'a, I, O, E: Error<I>>(Rc<dyn Parser<I, O, Error = E> + 'a>);
1365
1366impl<'a, I, O, E: Error<I>> Clone for BoxedParser<'a, I, O, E> {
1367    fn clone(&self) -> Self {
1368        Self(self.0.clone())
1369    }
1370}
1371
1372impl<'a, I: Clone, O, E: Error<I>> Parser<I, O> for BoxedParser<'a, I, O, E> {
1373    type Error = E;
1374
1375    fn parse_inner<D: Debugger>(
1376        &self,
1377        debugger: &mut D,
1378        stream: &mut StreamOf<I, Self::Error>,
1379    ) -> PResult<I, O, Self::Error> {
1380        #[allow(deprecated)]
1381        debugger.invoke(&self.0, stream)
1382    }
1383
1384    fn parse_inner_verbose(
1385        &self,
1386        d: &mut Verbose,
1387        s: &mut StreamOf<I, Self::Error>,
1388    ) -> PResult<I, O, Self::Error> {
1389        #[allow(deprecated)]
1390        self.parse_inner(d, s)
1391    }
1392    fn parse_inner_silent(
1393        &self,
1394        d: &mut Silent,
1395        s: &mut StreamOf<I, Self::Error>,
1396    ) -> PResult<I, O, Self::Error> {
1397        #[allow(deprecated)]
1398        self.parse_inner(d, s)
1399    }
1400
1401    fn boxed<'b>(self) -> BoxedParser<'b, I, O, Self::Error>
1402    where
1403        Self: Sized + 'b,
1404    {
1405        // Avoid boxing twice.
1406        self
1407    }
1408}
1409
1410/// Create a parser that selects one or more input patterns and map them to an output value.
1411///
1412/// This is most useful when turning the tokens of a previous compilation pass (such as lexing) into data that can be
1413/// used for parsing, although it can also generally be used to select inputs and map them to outputs. Any unmapped
1414/// input patterns will become syntax errors, just as with [`filter`].
1415///
1416/// The macro is semantically similar to a `match` expression and so supports
1417/// [pattern guards](https://doc.rust-lang.org/reference/expressions/match-expr.html#match-guards) too.
1418///
1419/// ```ignore
1420/// select! {
1421///     Token::Bool(x) if x => Expr::True,
1422///     Token::Bool(x) if !x => Expr::False,
1423/// }
1424/// ```
1425///
1426/// If you require access to the input's span, you may add an argument before the patterns to gain access to it.
1427///
1428/// ```ignore
1429/// select! { |span|
1430///     Token::Num(x) => Expr::Num(x).spanned(span),
1431///     Token::Str(s) => Expr::Str(s).spanned(span),
1432/// }
1433/// ```
1434///
1435/// Internally, [`select!`] is a loose wrapper around [`filter_map`] and thinking of it as such might make it less
1436/// confusing.
1437///
1438/// # Examples
1439///
1440/// ```
1441/// # use chumsky::{prelude::*, error::Cheap};
1442/// // The type of our parser's input (tokens like this might be emitted by your compiler's lexer)
1443/// #[derive(Clone, Debug, PartialEq)]
1444/// enum Token {
1445///     Num(u64),
1446///     Bool(bool),
1447///     LParen,
1448///     RParen,
1449/// }
1450///
1451/// // The type of our parser's output, a syntax tree
1452/// #[derive(Debug, PartialEq)]
1453/// enum Ast {
1454///     Num(u64),
1455///     Bool(bool),
1456///     List(Vec<Ast>),
1457/// }
1458///
1459/// // Our parser converts a stream of input tokens into an AST
1460/// // `select!` is used to deconstruct some of the tokens and turn them into AST nodes
1461/// let ast = recursive::<_, _, _, _, Cheap<Token>>(|ast| {
1462///     let literal = select! {
1463///         Token::Num(x) => Ast::Num(x),
1464///         Token::Bool(x) => Ast::Bool(x),
1465///     };
1466///
1467///     literal.or(ast
1468///         .repeated()
1469///         .delimited_by(just(Token::LParen), just(Token::RParen))
1470///         .map(Ast::List))
1471/// });
1472///
1473/// use Token::*;
1474/// assert_eq!(
1475///     ast.parse(vec![LParen, Num(5), LParen, Bool(false), Num(42), RParen, RParen]),
1476///     Ok(Ast::List(vec![
1477///         Ast::Num(5),
1478///         Ast::List(vec![
1479///             Ast::Bool(false),
1480///             Ast::Num(42),
1481///         ]),
1482///     ])),
1483/// );
1484/// ```
1485#[macro_export]
1486macro_rules! select {
1487    (|$span:ident| $($p:pat $(if $guard:expr)? => $out:expr),+ $(,)?) => ({
1488        $crate::primitive::filter_map(move |$span, x| match x {
1489            $($p $(if $guard)? => ::core::result::Result::Ok($out)),+,
1490            _ => ::core::result::Result::Err($crate::error::Error::expected_input_found($span, ::core::option::Option::None, ::core::option::Option::Some(x))),
1491        })
1492    });
1493
1494    ($($p:pat $(if $guard:expr)? => $out:expr),+ $(,)?) => (select!(|_span| $($p $(if $guard)? => $out),+));
1495}