chumsky/
primitive.rs

1//! Parser primitives that accept specific token patterns.
2//!
3//! *“These creatures you call mice, you see, they are not quite as they appear. They are merely the protrusion into
4//! our dimension of vastly hyperintelligent pandimensional beings.”*
5//!
6//! Chumsky parsers are created by combining together smaller parsers. Right at the bottom of the pile are the parser
7//! primitives, a parser developer's bread & butter. Each of these primitives are very easy to understand in isolation,
8//! usually only doing one thing.
9//!
10//! ## The Important Ones
11//!
12//! - [`just`]: parses a specific input or sequence of inputs
13//! - [`filter`]: parses a single input, if the given filter function returns `true`
14//! - [`end`]: parses the end of input (i.e: if there any more inputs, this parse fails)
15
16use super::*;
17use core::panic::Location;
18
19/// See [`custom`].
20#[must_use]
21pub struct Custom<F, E>(F, PhantomData<E>);
22
23impl<F: Copy, E> Copy for Custom<F, E> {}
24impl<F: Clone, E> Clone for Custom<F, E> {
25    fn clone(&self) -> Self {
26        Self(self.0.clone(), PhantomData)
27    }
28}
29
30impl<I: Clone, O, F: Fn(&mut StreamOf<I, E>) -> PResult<I, O, E>, E: Error<I>> Parser<I, O>
31    for Custom<F, E>
32{
33    type Error = E;
34
35    fn parse_inner<D: Debugger>(
36        &self,
37        _debugger: &mut D,
38        stream: &mut StreamOf<I, E>,
39    ) -> PResult<I, O, E> {
40        (self.0)(stream)
41    }
42
43    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, O, E> {
44        #[allow(deprecated)]
45        self.parse_inner(d, s)
46    }
47    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, O, E> {
48        #[allow(deprecated)]
49        self.parse_inner(d, s)
50    }
51}
52
53/// A parser primitive that allows you to define your own custom parsers.
54///
55/// In theory you shouldn't need to use this unless you have particularly bizarre requirements, but it's a cleaner and
56/// more sustainable alternative to implementing [`Parser`] by hand.
57///
58/// The output type of this parser is determined by the parse result of the function.
59pub fn custom<F, E>(f: F) -> Custom<F, E> {
60    Custom(f, PhantomData)
61}
62
63/// See [`end`].
64#[must_use]
65pub struct End<E>(PhantomData<E>);
66
67impl<E> Clone for End<E> {
68    fn clone(&self) -> Self {
69        Self(PhantomData)
70    }
71}
72
73impl<I: Clone, E: Error<I>> Parser<I, ()> for End<E> {
74    type Error = E;
75
76    fn parse_inner<D: Debugger>(
77        &self,
78        _debugger: &mut D,
79        stream: &mut StreamOf<I, E>,
80    ) -> PResult<I, (), E> {
81        match stream.next() {
82            (_, _, None) => (Vec::new(), Ok(((), None))),
83            (at, span, found) => (
84                Vec::new(),
85                Err(Located::at(
86                    at,
87                    E::expected_input_found(span, Some(None), found),
88                )),
89            ),
90        }
91    }
92
93    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, (), E> {
94        #[allow(deprecated)]
95        self.parse_inner(d, s)
96    }
97    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, (), E> {
98        #[allow(deprecated)]
99        self.parse_inner(d, s)
100    }
101}
102
103/// A parser that accepts only the end of input.
104///
105/// This parser is very useful when you wish to force a parser to consume *all* of the input. It is typically combined
106/// with [`Parser::then_ignore`].
107///
108/// The output type of this parser is `()`.
109///
110/// # Examples
111///
112/// ```
113/// # use chumsky::prelude::*;
114/// assert_eq!(end::<Simple<char>>().parse(""), Ok(()));
115/// assert!(end::<Simple<char>>().parse("hello").is_err());
116/// ```
117///
118/// ```
119/// # use chumsky::prelude::*;
120/// let digits = text::digits::<_, Simple<char>>(10);
121///
122/// // This parser parses digits!
123/// assert_eq!(digits.parse("1234"), Ok("1234".to_string()));
124///
125/// // However, parsers are lazy and do not consume trailing input.
126/// // This can be inconvenient if we want to validate all of the input.
127/// assert_eq!(digits.parse("1234AhasjADSJAlaDJKSDAK"), Ok("1234".to_string()));
128///
129/// // To fix this problem, we require that the end of input follows any successfully parsed input
130/// let only_digits = digits.then_ignore(end());
131///
132/// // Now our parser correctly produces an error if any trailing input is found...
133/// assert!(only_digits.parse("1234AhasjADSJAlaDJKSDAK").is_err());
134/// // ...while still behaving correctly for inputs that only consist of valid patterns
135/// assert_eq!(only_digits.parse("1234"), Ok("1234".to_string()));
136/// ```
137pub fn end<E>() -> End<E> {
138    End(PhantomData)
139}
140
141mod private {
142    pub trait Sealed<T> {}
143
144    impl<T> Sealed<T> for T {}
145    impl Sealed<char> for alloc::string::String {}
146    impl<'a> Sealed<char> for &'a str {}
147    impl<'a, T> Sealed<T> for &'a [T] {}
148    impl<T, const N: usize> Sealed<T> for [T; N] {}
149    impl<'a, T, const N: usize> Sealed<T> for &'a [T; N] {}
150    impl<T> Sealed<T> for alloc::vec::Vec<T> {}
151    impl<T> Sealed<T> for alloc::collections::LinkedList<T> {}
152    impl<T> Sealed<T> for alloc::collections::VecDeque<T> {}
153    impl<T> Sealed<T> for alloc::collections::BTreeSet<T> {}
154    impl<T> Sealed<T> for alloc::collections::BinaryHeap<T> {}
155
156    #[cfg(feature = "std")]
157    impl<T> Sealed<T> for std::collections::HashSet<T> {}
158    #[cfg(not(feature = "std"))]
159    impl<T> Sealed<T> for hashbrown::HashSet<T> {}
160}
161
162/// A utility trait to abstract over container-like things.
163///
164/// This trait is sealed and an implementation detail - its internals should not be relied on by users.
165pub trait Container<T>: private::Sealed<T> {
166    /// An iterator over the items within this container, by value.
167    type Iter: Iterator<Item = T>;
168    /// Iterate over the elements of the container (using internal iteration because GATs are unstable).
169    fn get_iter(&self) -> Self::Iter;
170}
171
172impl<T: Clone> Container<T> for T {
173    type Iter = core::iter::Once<T>;
174    fn get_iter(&self) -> Self::Iter {
175        core::iter::once(self.clone())
176    }
177}
178
179impl Container<char> for String {
180    type Iter = alloc::vec::IntoIter<char>;
181    fn get_iter(&self) -> Self::Iter {
182        self.chars().collect::<Vec<_>>().into_iter()
183    }
184}
185
186impl<'a> Container<char> for &'a str {
187    type Iter = alloc::str::Chars<'a>;
188    fn get_iter(&self) -> Self::Iter {
189        self.chars()
190    }
191}
192
193impl<'a, T: Clone> Container<T> for &'a [T] {
194    type Iter = core::iter::Cloned<core::slice::Iter<'a, T>>;
195    fn get_iter(&self) -> Self::Iter {
196        self.iter().cloned()
197    }
198}
199
200impl<'a, T: Clone, const N: usize> Container<T> for &'a [T; N] {
201    type Iter = core::iter::Cloned<core::slice::Iter<'a, T>>;
202    fn get_iter(&self) -> Self::Iter {
203        self.iter().cloned()
204    }
205}
206
207impl<T: Clone, const N: usize> Container<T> for [T; N] {
208    type Iter = core::array::IntoIter<T, N>;
209    fn get_iter(&self) -> Self::Iter {
210        core::array::IntoIter::new(self.clone())
211    }
212}
213
214impl<T: Clone> Container<T> for Vec<T> {
215    type Iter = alloc::vec::IntoIter<T>;
216    fn get_iter(&self) -> Self::Iter {
217        self.clone().into_iter()
218    }
219}
220
221impl<T: Clone> Container<T> for alloc::collections::LinkedList<T> {
222    type Iter = alloc::collections::linked_list::IntoIter<T>;
223    fn get_iter(&self) -> Self::Iter {
224        self.clone().into_iter()
225    }
226}
227
228impl<T: Clone> Container<T> for alloc::collections::VecDeque<T> {
229    type Iter = alloc::collections::vec_deque::IntoIter<T>;
230    fn get_iter(&self) -> Self::Iter {
231        self.clone().into_iter()
232    }
233}
234
235#[cfg(feature = "std")]
236impl<T: Clone> Container<T> for std::collections::HashSet<T> {
237    type Iter = std::collections::hash_set::IntoIter<T>;
238    fn get_iter(&self) -> Self::Iter {
239        self.clone().into_iter()
240    }
241}
242
243#[cfg(not(feature = "std"))]
244impl<T: Clone> Container<T> for hashbrown::HashSet<T> {
245    type Iter = hashbrown::hash_set::IntoIter<T>;
246    fn get_iter(&self) -> Self::Iter {
247        self.clone().into_iter()
248    }
249}
250
251impl<T: Clone> Container<T> for alloc::collections::BTreeSet<T> {
252    type Iter = alloc::collections::btree_set::IntoIter<T>;
253    fn get_iter(&self) -> Self::Iter {
254        self.clone().into_iter()
255    }
256}
257
258impl<T: Clone> Container<T> for alloc::collections::BinaryHeap<T> {
259    type Iter = alloc::collections::binary_heap::IntoIter<T>;
260    fn get_iter(&self) -> Self::Iter {
261        self.clone().into_iter()
262    }
263}
264
265/// A utility trait to abstract over linear and ordered container-like things, excluding things such
266/// as sets and heaps.
267///
268/// This trait is sealed and an implementation detail - its internals should not be relied on by users.
269pub trait OrderedContainer<T>: Container<T> {}
270
271impl<T: Clone> OrderedContainer<T> for T {}
272impl OrderedContainer<char> for String {}
273impl<'a> OrderedContainer<char> for &'a str {}
274impl<'a, T: Clone> OrderedContainer<T> for &'a [T] {}
275impl<'a, T: Clone, const N: usize> OrderedContainer<T> for &'a [T; N] {}
276impl<T: Clone, const N: usize> OrderedContainer<T> for [T; N] {}
277impl<T: Clone> OrderedContainer<T> for Vec<T> {}
278impl<T: Clone> OrderedContainer<T> for alloc::collections::LinkedList<T> {}
279impl<T: Clone> OrderedContainer<T> for alloc::collections::VecDeque<T> {}
280
281/// See [`just`].
282#[must_use]
283pub struct Just<I, C: OrderedContainer<I>, E>(C, PhantomData<(I, E)>);
284
285impl<I, C: Copy + OrderedContainer<I>, E> Copy for Just<I, C, E> {}
286impl<I, C: Clone + OrderedContainer<I>, E> Clone for Just<I, C, E> {
287    fn clone(&self) -> Self {
288        Self(self.0.clone(), PhantomData)
289    }
290}
291
292impl<I: Clone + PartialEq, C: OrderedContainer<I> + Clone, E: Error<I>> Parser<I, C>
293    for Just<I, C, E>
294{
295    type Error = E;
296
297    fn parse_inner<D: Debugger>(
298        &self,
299        _debugger: &mut D,
300        stream: &mut StreamOf<I, E>,
301    ) -> PResult<I, C, E> {
302        for expected in self.0.get_iter() {
303            match stream.next() {
304                (_, _, Some(tok)) if tok == expected => {}
305                (at, span, found) => {
306                    return (
307                        Vec::new(),
308                        Err(Located::at(
309                            at,
310                            E::expected_input_found(span, Some(Some(expected)), found),
311                        )),
312                    )
313                }
314            }
315        }
316
317        (Vec::new(), Ok((self.0.clone(), None)))
318    }
319
320    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, C, E> {
321        #[allow(deprecated)]
322        self.parse_inner(d, s)
323    }
324    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, C, E> {
325        #[allow(deprecated)]
326        self.parse_inner(d, s)
327    }
328}
329
330/// A parser that accepts only the given input.
331///
332/// The output type of this parser is `C`, the input or sequence that was provided.
333///
334/// # Examples
335///
336/// ```
337/// # use chumsky::{prelude::*, error::Cheap};
338/// let question = just::<_, _, Cheap<char>>('?');
339///
340/// assert_eq!(question.parse("?"), Ok('?'));
341/// assert!(question.parse("!").is_err());
342/// // This works because parsers do not eagerly consume input, so the '!' is not parsed
343/// assert_eq!(question.parse("?!"), Ok('?'));
344/// // This fails because the parser expects an end to the input after the '?'
345/// assert!(question.then(end()).parse("?!").is_err());
346/// ```
347pub fn just<I, C: OrderedContainer<I>, E: Error<I>>(inputs: C) -> Just<I, C, E> {
348    Just(inputs, PhantomData)
349}
350
351/// See [`seq`].
352#[must_use]
353pub struct Seq<I, E>(Vec<I>, PhantomData<E>);
354
355impl<I: Clone, E> Clone for Seq<I, E> {
356    fn clone(&self) -> Self {
357        Self(self.0.clone(), PhantomData)
358    }
359}
360
361impl<I: Clone + PartialEq, E: Error<I>> Parser<I, ()> for Seq<I, E> {
362    type Error = E;
363
364    fn parse_inner<D: Debugger>(
365        &self,
366        _debugger: &mut D,
367        stream: &mut StreamOf<I, E>,
368    ) -> PResult<I, (), E> {
369        for expected in &self.0 {
370            match stream.next() {
371                (_, _, Some(tok)) if &tok == expected => {}
372                (at, span, found) => {
373                    return (
374                        Vec::new(),
375                        Err(Located::at(
376                            at,
377                            E::expected_input_found(span, Some(Some(expected.clone())), found),
378                        )),
379                    )
380                }
381            }
382        }
383
384        (Vec::new(), Ok(((), None)))
385    }
386
387    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, (), E> {
388        #[allow(deprecated)]
389        self.parse_inner(d, s)
390    }
391    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, (), E> {
392        #[allow(deprecated)]
393        self.parse_inner(d, s)
394    }
395}
396
397/// A parser that accepts only a sequence of specific inputs.
398///
399/// The output type of this parser is `()`.
400///
401/// # Examples
402///
403/// ```
404/// # use chumsky::{prelude::*, error::Cheap};
405/// let hello = seq::<_, _, Cheap<char>>("Hello".chars());
406///
407/// assert_eq!(hello.parse("Hello"), Ok(()));
408/// assert_eq!(hello.parse("Hello, world!"), Ok(()));
409/// assert!(hello.parse("Goodbye").is_err());
410///
411/// let onetwothree = seq::<_, _, Cheap<i32>>([1, 2, 3]);
412///
413/// assert_eq!(onetwothree.parse([1, 2, 3]), Ok(()));
414/// assert_eq!(onetwothree.parse([1, 2, 3, 4, 5]), Ok(()));
415/// assert!(onetwothree.parse([2, 1, 3]).is_err());
416/// ```
417#[deprecated(
418    since = "0.7.0",
419    note = "Use `just` instead: it now works for many sequence-like types!"
420)]
421pub fn seq<I: Clone + PartialEq, Iter: IntoIterator<Item = I>, E>(xs: Iter) -> Seq<I, E> {
422    Seq(xs.into_iter().collect(), PhantomData)
423}
424
425/// See [`one_of`].
426#[must_use]
427pub struct OneOf<I, C, E>(C, PhantomData<(I, E)>);
428
429impl<I, C: Clone, E> Clone for OneOf<I, C, E> {
430    fn clone(&self) -> Self {
431        Self(self.0.clone(), PhantomData)
432    }
433}
434
435impl<I: Clone + PartialEq, C: Container<I>, E: Error<I>> Parser<I, I> for OneOf<I, C, E> {
436    type Error = E;
437
438    fn parse_inner<D: Debugger>(
439        &self,
440        _debugger: &mut D,
441        stream: &mut StreamOf<I, E>,
442    ) -> PResult<I, I, E> {
443        match stream.next() {
444            (_, _, Some(tok)) if self.0.get_iter().any(|not| not == tok) => {
445                (Vec::new(), Ok((tok, None)))
446            }
447            (at, span, found) => (
448                Vec::new(),
449                Err(Located::at(
450                    at,
451                    E::expected_input_found(span, self.0.get_iter().map(Some), found),
452                )),
453            ),
454        }
455    }
456
457    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, I, E> {
458        #[allow(deprecated)]
459        self.parse_inner(d, s)
460    }
461    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, I, E> {
462        #[allow(deprecated)]
463        self.parse_inner(d, s)
464    }
465}
466
467/// A parser that accepts one of a sequence of specific inputs.
468///
469/// The output type of this parser is `I`, the input that was found.
470///
471/// # Examples
472///
473/// ```
474/// # use chumsky::{prelude::*, error::Cheap};
475/// let digits = one_of::<_, _, Cheap<char>>("0123456789")
476///     .repeated().at_least(1)
477///     .then_ignore(end())
478///     .collect::<String>();
479///
480/// assert_eq!(digits.parse("48791"), Ok("48791".to_string()));
481/// assert!(digits.parse("421!53").is_err());
482/// ```
483pub fn one_of<I, C: Container<I>, E: Error<I>>(inputs: C) -> OneOf<I, C, E> {
484    OneOf(inputs, PhantomData)
485}
486
487/// See [`empty`].
488#[must_use]
489pub struct Empty<E>(PhantomData<E>);
490
491impl<E> Clone for Empty<E> {
492    fn clone(&self) -> Self {
493        Self(PhantomData)
494    }
495}
496
497impl<I: Clone, E: Error<I>> Parser<I, ()> for Empty<E> {
498    type Error = E;
499
500    fn parse_inner<D: Debugger>(
501        &self,
502        _debugger: &mut D,
503        _: &mut StreamOf<I, E>,
504    ) -> PResult<I, (), E> {
505        (Vec::new(), Ok(((), None)))
506    }
507
508    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, (), E> {
509        #[allow(deprecated)]
510        self.parse_inner(d, s)
511    }
512    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, (), E> {
513        #[allow(deprecated)]
514        self.parse_inner(d, s)
515    }
516}
517
518/// A parser that parses no inputs.
519///
520/// The output type of this parser is `()`.
521pub fn empty<E>() -> Empty<E> {
522    Empty(PhantomData)
523}
524
525/// See [`none_of`].
526#[must_use]
527pub struct NoneOf<I, C, E>(C, PhantomData<(I, E)>);
528
529impl<I, C: Clone, E> Clone for NoneOf<I, C, E> {
530    fn clone(&self) -> Self {
531        Self(self.0.clone(), PhantomData)
532    }
533}
534
535impl<I: Clone + PartialEq, C: Container<I>, E: Error<I>> Parser<I, I> for NoneOf<I, C, E> {
536    type Error = E;
537
538    fn parse_inner<D: Debugger>(
539        &self,
540        _debugger: &mut D,
541        stream: &mut StreamOf<I, E>,
542    ) -> PResult<I, I, E> {
543        match stream.next() {
544            (_, _, Some(tok)) if self.0.get_iter().all(|not| not != tok) => {
545                (Vec::new(), Ok((tok, None)))
546            }
547            (at, span, found) => (
548                Vec::new(),
549                Err(Located::at(
550                    at,
551                    E::expected_input_found(span, Vec::new(), found),
552                )),
553            ),
554        }
555    }
556
557    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, I, E> {
558        #[allow(deprecated)]
559        self.parse_inner(d, s)
560    }
561    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, I, E> {
562        #[allow(deprecated)]
563        self.parse_inner(d, s)
564    }
565}
566
567/// A parser that accepts any input that is *not* in a sequence of specific inputs.
568///
569/// The output type of this parser is `I`, the input that was found.
570///
571/// # Examples
572///
573/// ```
574/// # use chumsky::{prelude::*, error::Cheap};
575/// let string = one_of::<_, _, Cheap<char>>("\"'")
576///     .ignore_then(none_of("\"'").repeated())
577///     .then_ignore(one_of("\"'"))
578///     .then_ignore(end())
579///     .collect::<String>();
580///
581/// assert_eq!(string.parse("'hello'"), Ok("hello".to_string()));
582/// assert_eq!(string.parse("\"world\""), Ok("world".to_string()));
583/// assert!(string.parse("\"421!53").is_err());
584/// ```
585pub fn none_of<I, C: Container<I>, E: Error<I>>(inputs: C) -> NoneOf<I, C, E> {
586    NoneOf(inputs, PhantomData)
587}
588
589/// See [`take_until`].
590#[must_use]
591#[derive(Copy, Clone)]
592pub struct TakeUntil<A>(A);
593
594impl<I: Clone, O, A: Parser<I, O>> Parser<I, (Vec<I>, O)> for TakeUntil<A> {
595    type Error = A::Error;
596
597    fn parse_inner<D: Debugger>(
598        &self,
599        debugger: &mut D,
600        stream: &mut StreamOf<I, A::Error>,
601    ) -> PResult<I, (Vec<I>, O), A::Error> {
602        let mut outputs = Vec::new();
603        let mut alt = None;
604
605        loop {
606            let (errors, err) = match stream.try_parse(|stream| {
607                #[allow(deprecated)]
608                self.0.parse_inner(debugger, stream)
609            }) {
610                (errors, Ok((out, a_alt))) => {
611                    break (errors, Ok(((outputs, out), merge_alts(alt, a_alt))))
612                }
613                (errors, Err(err)) => (errors, err),
614            };
615
616            match stream.next() {
617                (_, _, Some(tok)) => outputs.push(tok),
618                (_, _, None) => break (errors, Err(err)),
619            }
620
621            alt = merge_alts(alt.take(), Some(err));
622        }
623    }
624
625    fn parse_inner_verbose(
626        &self,
627        d: &mut Verbose,
628        s: &mut StreamOf<I, A::Error>,
629    ) -> PResult<I, (Vec<I>, O), A::Error> {
630        #[allow(deprecated)]
631        self.parse_inner(d, s)
632    }
633    fn parse_inner_silent(
634        &self,
635        d: &mut Silent,
636        s: &mut StreamOf<I, A::Error>,
637    ) -> PResult<I, (Vec<I>, O), A::Error> {
638        #[allow(deprecated)]
639        self.parse_inner(d, s)
640    }
641}
642
643/// A parser that accepts any number of inputs until a terminating pattern is reached.
644///
645/// The output type of this parser is `(Vec<I>, O)`, a combination of the preceding inputs and the output of the
646/// final patterns.
647///
648/// # Examples
649///
650/// ```
651/// # use chumsky::{prelude::*, error::Cheap};
652/// let single_line = just::<_, _, Simple<char>>("//")
653///     .then(take_until(text::newline()))
654///     .ignored();
655///
656/// let multi_line = just::<_, _, Simple<char>>("/*")
657///     .then(take_until(just("*/")))
658///     .ignored();
659///
660/// let comment = single_line.or(multi_line);
661///
662/// let tokens = text::ident()
663///     .padded()
664///     .padded_by(comment
665///         .padded()
666///         .repeated())
667///     .repeated();
668///
669/// assert_eq!(tokens.parse(r#"
670///     // These tokens...
671///     these are
672///     /*
673///         ...have some
674///         multi-line...
675///     */
676///     // ...and single-line...
677///     tokens
678///     // ...comments between them
679/// "#), Ok(vec!["these".to_string(), "are".to_string(), "tokens".to_string()]));
680/// ```
681pub fn take_until<A>(until: A) -> TakeUntil<A> {
682    TakeUntil(until)
683}
684
685/// See [`filter`].
686#[must_use]
687pub struct Filter<F, E>(F, PhantomData<E>);
688
689impl<F: Copy, E> Copy for Filter<F, E> {}
690impl<F: Clone, E> Clone for Filter<F, E> {
691    fn clone(&self) -> Self {
692        Self(self.0.clone(), PhantomData)
693    }
694}
695
696impl<I: Clone, F: Fn(&I) -> bool, E: Error<I>> Parser<I, I> for Filter<F, E> {
697    type Error = E;
698
699    fn parse_inner<D: Debugger>(
700        &self,
701        _debugger: &mut D,
702        stream: &mut StreamOf<I, E>,
703    ) -> PResult<I, I, E> {
704        match stream.next() {
705            (_, _, Some(tok)) if (self.0)(&tok) => (Vec::new(), Ok((tok, None))),
706            (at, span, found) => (
707                Vec::new(),
708                Err(Located::at(
709                    at,
710                    E::expected_input_found(span, Vec::new(), found),
711                )),
712            ),
713        }
714    }
715
716    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, I, E> {
717        #[allow(deprecated)]
718        self.parse_inner(d, s)
719    }
720    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, I, E> {
721        #[allow(deprecated)]
722        self.parse_inner(d, s)
723    }
724}
725
726/// A parser that accepts only inputs that match the given predicate.
727///
728/// The output type of this parser is `I`, the input that was found.
729///
730/// # Examples
731///
732/// ```
733/// # use chumsky::{prelude::*, error::Cheap};
734/// let lowercase = filter::<_, _, Cheap<char>>(char::is_ascii_lowercase)
735///     .repeated().at_least(1)
736///     .then_ignore(end())
737///     .collect::<String>();
738///
739/// assert_eq!(lowercase.parse("hello"), Ok("hello".to_string()));
740/// assert!(lowercase.parse("Hello").is_err());
741/// ```
742pub fn filter<I, F: Fn(&I) -> bool, E>(f: F) -> Filter<F, E> {
743    Filter(f, PhantomData)
744}
745
746/// See [`filter_map`].
747#[must_use]
748pub struct FilterMap<F, E>(F, PhantomData<E>);
749
750impl<F: Copy, E> Copy for FilterMap<F, E> {}
751impl<F: Clone, E> Clone for FilterMap<F, E> {
752    fn clone(&self) -> Self {
753        Self(self.0.clone(), PhantomData)
754    }
755}
756
757impl<I: Clone, O, F: Fn(E::Span, I) -> Result<O, E>, E: Error<I>> Parser<I, O> for FilterMap<F, E> {
758    type Error = E;
759
760    fn parse_inner<D: Debugger>(
761        &self,
762        _debugger: &mut D,
763        stream: &mut StreamOf<I, E>,
764    ) -> PResult<I, O, E> {
765        let (at, span, tok) = stream.next();
766        match tok.map(|tok| (self.0)(span.clone(), tok)) {
767            Some(Ok(tok)) => (Vec::new(), Ok((tok, None))),
768            Some(Err(err)) => (Vec::new(), Err(Located::at(at, err))),
769            None => (
770                Vec::new(),
771                Err(Located::at(
772                    at,
773                    E::expected_input_found(span, Vec::new(), None),
774                )),
775            ),
776        }
777    }
778
779    fn parse_inner_verbose(&self, d: &mut Verbose, s: &mut StreamOf<I, E>) -> PResult<I, O, E> {
780        #[allow(deprecated)]
781        self.parse_inner(d, s)
782    }
783    fn parse_inner_silent(&self, d: &mut Silent, s: &mut StreamOf<I, E>) -> PResult<I, O, E> {
784        #[allow(deprecated)]
785        self.parse_inner(d, s)
786    }
787}
788
789/// A parser that accepts a input and tests it against the given fallible function.
790///
791/// This function allows integration with custom error types to allow for custom parser errors.
792///
793/// Before using this function, consider whether the [`select`] macro would serve you better.
794///
795/// The output type of this parser is `I`, the input that was found.
796///
797/// # Examples
798///
799/// ```
800/// # use chumsky::{prelude::*, error::Cheap};
801/// let numeral = filter_map(|span, c: char| match c.to_digit(10) {
802///     Some(x) => Ok(x),
803///     None => Err(Simple::custom(span, format!("'{}' is not a digit", c))),
804/// });
805///
806/// assert_eq!(numeral.parse("3"), Ok(3));
807/// assert_eq!(numeral.parse("7"), Ok(7));
808/// assert_eq!(numeral.parse("f"), Err(vec![Simple::custom(0..1, "'f' is not a digit")]));
809/// ```
810pub fn filter_map<I, O, F: Fn(E::Span, I) -> Result<O, E>, E: Error<I>>(f: F) -> FilterMap<F, E> {
811    FilterMap(f, PhantomData)
812}
813
814/// See [`any`].
815pub type Any<I, E> = Filter<fn(&I) -> bool, E>;
816
817/// A parser that accepts any input (but not the end of input).
818///
819/// The output type of this parser is `I`, the input that was found.
820///
821/// # Examples
822///
823/// ```
824/// # use chumsky::{prelude::*, error::Cheap};
825/// let any = any::<char, Cheap<char>>();
826///
827/// assert_eq!(any.parse("a"), Ok('a'));
828/// assert_eq!(any.parse("7"), Ok('7'));
829/// assert_eq!(any.parse("\t"), Ok('\t'));
830/// assert!(any.parse("").is_err());
831/// ```
832pub fn any<I, E>() -> Any<I, E> {
833    Filter(|_| true, PhantomData)
834}
835
836/// See [`fn@todo`].
837#[must_use]
838pub struct Todo<I, O, E>(&'static Location<'static>, PhantomData<(I, O, E)>);
839
840/// A parser that can be used wherever you need to implement a parser later.
841///
842/// This parser is analogous to the [`todo!`] and [`unimplemented!`] macros, but will produce a panic when used to
843/// parse input, not immediately when invoked.
844///
845/// This function is useful when developing your parser, allowing you to prototype and run parts of your parser without
846/// committing to implementing the entire thing immediately.
847///
848/// The output type of this parser is whatever you want it to be: it'll never produce output!
849///
850/// # Examples
851///
852/// ```should_panic
853/// # use chumsky::prelude::*;
854/// let int = just::<_, _, Simple<char>>("0x").ignore_then(todo())
855///     .or(just("0b").ignore_then(text::digits(2)))
856///     .or(text::int(10));
857///
858/// // Decimal numbers are parsed
859/// assert_eq!(int.parse("12"), Ok("12".to_string()));
860/// // Binary numbers are parsed
861/// assert_eq!(int.parse("0b00101"), Ok("00101".to_string()));
862/// // Parsing hexadecimal numbers results in a panic because the parser is unimplemented
863/// int.parse("0xd4");
864/// ```
865#[track_caller]
866pub fn todo<I, O, E>() -> Todo<I, O, E> {
867    Todo(Location::caller(), PhantomData)
868}
869
870impl<I, O, E> Copy for Todo<I, O, E> {}
871impl<I, O, E> Clone for Todo<I, O, E> {
872    fn clone(&self) -> Self {
873        Self(self.0, PhantomData)
874    }
875}
876
877impl<I: Clone, O, E: Error<I>> Parser<I, O> for Todo<I, O, E> {
878    type Error = E;
879
880    fn parse_inner<D: Debugger>(
881        &self,
882        _debugger: &mut D,
883        _stream: &mut StreamOf<I, Self::Error>,
884    ) -> PResult<I, O, Self::Error> {
885        todo!(
886            "Attempted to use an unimplemented parser. Parser defined at {}",
887            self.0
888        )
889    }
890
891    fn parse_inner_verbose(
892        &self,
893        d: &mut Verbose,
894        s: &mut StreamOf<I, Self::Error>,
895    ) -> PResult<I, O, Self::Error> {
896        #[allow(deprecated)]
897        self.parse_inner(d, s)
898    }
899    fn parse_inner_silent(
900        &self,
901        d: &mut Silent,
902        s: &mut StreamOf<I, Self::Error>,
903    ) -> PResult<I, O, Self::Error> {
904        #[allow(deprecated)]
905        self.parse_inner(d, s)
906    }
907}
908
909/// See [`choice`].
910#[must_use]
911pub struct Choice<T, E>(pub(crate) T, pub(crate) PhantomData<E>);
912
913impl<T: Copy, E> Copy for Choice<T, E> {}
914impl<T: Clone, E> Clone for Choice<T, E> {
915    fn clone(&self) -> Self {
916        Self(self.0.clone(), PhantomData)
917    }
918}
919
920impl<I: Clone, O, E: Error<I>, A: Parser<I, O, Error = E>, const N: usize> Parser<I, O>
921    for Choice<[A; N], E>
922{
923    type Error = E;
924
925    fn parse_inner<D: Debugger>(
926        &self,
927        debugger: &mut D,
928        stream: &mut StreamOf<I, Self::Error>,
929    ) -> PResult<I, O, Self::Error> {
930        let Choice(parsers, _) = self;
931        let mut alt = None;
932
933        for parser in parsers {
934            match stream.try_parse(|stream| {
935                #[allow(deprecated)]
936                debugger.invoke(parser, stream)
937            }) {
938                (errors, Ok(out)) => return (errors, Ok(out)),
939                (_, Err(a_alt)) => {
940                    alt = merge_alts(alt.take(), Some(a_alt));
941                }
942            };
943        }
944
945        (Vec::new(), Err(alt.unwrap()))
946    }
947
948    fn parse_inner_verbose(
949        &self,
950        d: &mut Verbose,
951        s: &mut StreamOf<I, Self::Error>,
952    ) -> PResult<I, O, Self::Error> {
953        #[allow(deprecated)]
954        self.parse_inner(d, s)
955    }
956
957    fn parse_inner_silent(
958        &self,
959        d: &mut Silent,
960        s: &mut StreamOf<I, Self::Error>,
961    ) -> PResult<I, O, Self::Error> {
962        #[allow(deprecated)]
963        self.parse_inner(d, s)
964    }
965}
966
967impl<I: Clone, O, E: Error<I>, A: Parser<I, O, Error = E>> Parser<I, O> for Choice<Vec<A>, E> {
968    type Error = E;
969
970    fn parse_inner<D: Debugger>(
971        &self,
972        debugger: &mut D,
973        stream: &mut StreamOf<I, Self::Error>,
974    ) -> PResult<I, O, Self::Error> {
975        let Choice(parsers, _) = self;
976        let mut alt = None;
977
978        for parser in parsers {
979            match stream.try_parse(|stream| {
980                #[allow(deprecated)]
981                debugger.invoke(parser, stream)
982            }) {
983                (errors, Ok(out)) => return (errors, Ok(out)),
984                (_, Err(a_alt)) => {
985                    alt = merge_alts(alt.take(), Some(a_alt));
986                }
987            };
988        }
989
990        (Vec::new(), Err(alt.unwrap()))
991    }
992
993    fn parse_inner_verbose(
994        &self,
995        d: &mut Verbose,
996        s: &mut StreamOf<I, Self::Error>,
997    ) -> PResult<I, O, Self::Error> {
998        #[allow(deprecated)]
999        self.parse_inner(d, s)
1000    }
1001
1002    fn parse_inner_silent(
1003        &self,
1004        d: &mut Silent,
1005        s: &mut StreamOf<I, Self::Error>,
1006    ) -> PResult<I, O, Self::Error> {
1007        #[allow(deprecated)]
1008        self.parse_inner(d, s)
1009    }
1010}
1011
1012macro_rules! impl_for_tuple {
1013    () => {};
1014    ($head:ident $($X:ident)*) => {
1015        impl_for_tuple!($($X)*);
1016        impl_for_tuple!(~ $head $($X)*);
1017    };
1018    (~ $($X:ident)*) => {
1019        #[allow(unused_variables, non_snake_case)]
1020        impl<I: Clone, O, E: Error<I>, $($X: Parser<I, O, Error = E>),*> Parser<I, O> for Choice<($($X,)*), E> {
1021            type Error = E;
1022
1023            fn parse_inner<D: Debugger>(
1024                &self,
1025                debugger: &mut D,
1026                stream: &mut StreamOf<I, Self::Error>,
1027            ) -> PResult<I, O, Self::Error> {
1028                let Choice(($($X,)*), _) = self;
1029                let mut alt = None;
1030                $(
1031                    match stream.try_parse(|stream| {
1032                        #[allow(deprecated)]
1033                        debugger.invoke($X, stream)
1034                    }) {
1035                        (errors, Ok(out)) => return (errors, Ok(out)),
1036                        (errors, Err(a_alt)) => {
1037                            alt = merge_alts(alt.take(), Some(a_alt));
1038                        },
1039                    };
1040                )*
1041                (Vec::new(), Err(alt.unwrap()))
1042            }
1043
1044            fn parse_inner_verbose(
1045                &self,
1046                d: &mut Verbose,
1047                s: &mut StreamOf<I, Self::Error>,
1048            ) -> PResult<I, O, Self::Error> {
1049                #[allow(deprecated)]
1050                self.parse_inner(d, s)
1051            }
1052            fn parse_inner_silent(
1053                &self,
1054                d: &mut Silent,
1055                s: &mut StreamOf<I, Self::Error>,
1056            ) -> PResult<I, O, Self::Error> {
1057                #[allow(deprecated)]
1058                self.parse_inner(d, s)
1059            }
1060        }
1061    };
1062}
1063
1064impl_for_tuple!(A_ B_ C_ D_ E_ F_ G_ H_ I_ J_ K_ L_ M_ N_ O_ P_ Q_ S_ T_ U_ V_ W_ X_ Y_ Z_);
1065
1066/// Parse using a tuple or array of many parsers, producing the output of the first to successfully parse.
1067///
1068/// This primitive has a twofold improvement over a chain of [`Parser::or`] calls:
1069///
1070/// - Rust's trait solver seems to resolve the [`Parser`] impl for this type much faster, significantly reducing
1071///   compilation times.
1072///
1073/// - Parsing is likely a little faster in some cases because the resulting parser is 'less careful' about error
1074///   routing, and doesn't perform the same fine-grained error prioritisation that [`Parser::or`] does.
1075///
1076/// These qualities make this parser ideal for lexers.
1077///
1078/// The output type of this parser is the output type of the inner parsers.
1079///
1080/// # Examples
1081/// ```
1082/// # use chumsky::prelude::*;
1083/// #[derive(Clone, Debug, PartialEq)]
1084/// enum Token {
1085///     If,
1086///     For,
1087///     While,
1088///     Fn,
1089///     Int(u64),
1090///     Ident(String),
1091/// }
1092///
1093/// let tokens = choice::<_, Simple<char>>((
1094///     text::keyword("if").to(Token::If),
1095///     text::keyword("for").to(Token::For),
1096///     text::keyword("while").to(Token::While),
1097///     text::keyword("fn").to(Token::Fn),
1098///     text::int(10).from_str().unwrapped().map(Token::Int),
1099///     text::ident().map(Token::Ident),
1100/// ))
1101///     .padded()
1102///     .repeated();
1103///
1104/// use Token::*;
1105/// assert_eq!(
1106///     tokens.parse("if 56 for foo while 42 fn bar"),
1107///     Ok(vec![If, Int(56), For, Ident("foo".to_string()), While, Int(42), Fn, Ident("bar".to_string())]),
1108/// );
1109/// ```
1110///
1111/// If you have more than 26 choices, the array-form of choice will work for any length. The downside
1112/// being that the contained parsers must all be of the same type.
1113/// ```
1114/// # use chumsky::prelude::*;
1115/// #[derive(Clone, Debug, PartialEq)]
1116/// enum Token {
1117///     If,
1118///     For,
1119///     While,
1120///     Fn,
1121///     Def,
1122/// }
1123///
1124/// let tokens = choice::<_, Simple<char>>([
1125///     text::keyword("if").to(Token::If),
1126///     text::keyword("for").to(Token::For),
1127///     text::keyword("while").to(Token::While),
1128///     text::keyword("fn").to(Token::Fn),
1129///     text::keyword("def").to(Token::Def),
1130/// ])
1131///     .padded()
1132///     .repeated();
1133///
1134/// use Token::*;
1135/// assert_eq!(
1136///     tokens.parse("def fn while if for"),
1137///     Ok(vec![Def, Fn, While, If, For]),
1138/// );
1139/// ```
1140pub fn choice<T, E>(parsers: T) -> Choice<T, E> {
1141    Choice(parsers, PhantomData)
1142}