winnow/combinator/
branch.rs

1use crate::combinator::trace;
2use crate::error::{ErrMode, ErrorKind, ParserError};
3use crate::stream::Stream;
4use crate::*;
5
6#[doc(inline)]
7pub use crate::dispatch;
8
9/// Helper trait for the [`alt()`] combinator.
10///
11/// This trait is implemented for tuples of up to 21 elements
12pub trait Alt<I, O, E> {
13    /// Tests each parser in the tuple and returns the result of the first one that succeeds
14    fn choice(&mut self, input: &mut I) -> PResult<O, E>;
15}
16
17/// Pick the first successful parser
18///
19/// To stop on an error, rather than trying further cases, see
20/// [`cut_err`][crate::combinator::cut_err] ([example][crate::_tutorial::chapter_7]).
21///
22/// For tight control over the error when no match is found, add a final case using [`fail`][crate::combinator::fail].
23/// Alternatively, with a [custom error type][crate::_topic::error], it is possible to track all
24/// errors or return the error of the parser that went the farthest in the input data.
25///
26/// When the alternative cases have unique prefixes, [`dispatch`] can offer better performance.
27///
28/// # Example
29///
30/// ```rust
31/// # use winnow::{error::ErrMode, error::InputError,error::ErrorKind, error::Needed};
32/// # use winnow::prelude::*;
33/// use winnow::ascii::{alpha1, digit1};
34/// use winnow::combinator::alt;
35/// # fn main() {
36/// fn parser(input: &str) -> IResult<&str, &str> {
37///   alt((alpha1, digit1)).parse_peek(input)
38/// };
39///
40/// // the first parser, alpha1, takes the input
41/// assert_eq!(parser("abc"), Ok(("", "abc")));
42///
43/// // the first parser returns an error, so alt tries the second one
44/// assert_eq!(parser("123456"), Ok(("", "123456")));
45///
46/// // both parsers failed, and with the default error type, alt will return the last error
47/// assert_eq!(parser(" "), Err(ErrMode::Backtrack(InputError::new(" ", ErrorKind::Slice))));
48/// # }
49/// ```
50#[doc(alias = "choice")]
51pub fn alt<Input: Stream, Output, Error, Alternatives>(
52    mut alternatives: Alternatives,
53) -> impl Parser<Input, Output, Error>
54where
55    Alternatives: Alt<Input, Output, Error>,
56    Error: ParserError<Input>,
57{
58    trace("alt", move |i: &mut Input| alternatives.choice(i))
59}
60
61/// Helper trait for the [`permutation()`] combinator.
62///
63/// This trait is implemented for tuples of up to 21 elements
64pub trait Permutation<I, O, E> {
65    /// Tries to apply all parsers in the tuple in various orders until all of them succeed
66    fn permutation(&mut self, input: &mut I) -> PResult<O, E>;
67}
68
69/// Applies a list of parsers in any order.
70///
71/// Permutation will succeed if all of the child parsers succeeded.
72/// It takes as argument a tuple of parsers, and returns a
73/// tuple of the parser results.
74///
75/// To stop on an error, rather than trying further permutations, see
76/// [`cut_err`][crate::combinator::cut_err] ([example][crate::_tutorial::chapter_7]).
77///
78/// # Example
79///
80/// ```rust
81/// # use winnow::{error::ErrMode,error::{InputError, ErrorKind}, error::Needed};
82/// # use winnow::prelude::*;
83/// use winnow::ascii::{alpha1, digit1};
84/// use winnow::combinator::permutation;
85/// # fn main() {
86/// fn parser(input: &str) -> IResult<&str, (&str, &str)> {
87///   permutation((alpha1, digit1)).parse_peek(input)
88/// }
89///
90/// // permutation takes alphabetic characters then digit
91/// assert_eq!(parser("abc123"), Ok(("", ("abc", "123"))));
92///
93/// // but also in inverse order
94/// assert_eq!(parser("123abc"), Ok(("", ("abc", "123"))));
95///
96/// // it will fail if one of the parsers failed
97/// assert_eq!(parser("abc;"), Err(ErrMode::Backtrack(InputError::new(";", ErrorKind::Slice))));
98/// # }
99/// ```
100///
101/// The parsers are applied greedily: if there are multiple unapplied parsers
102/// that could parse the next slice of input, the first one is used.
103/// ```rust
104/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}};
105/// # use winnow::prelude::*;
106/// use winnow::combinator::permutation;
107/// use winnow::token::any;
108///
109/// fn parser(input: &str) -> IResult<&str, (char, char)> {
110///   permutation((any, 'a')).parse_peek(input)
111/// }
112///
113/// // any parses 'b', then char('a') parses 'a'
114/// assert_eq!(parser("ba"), Ok(("", ('b', 'a'))));
115///
116/// // any parses 'a', then char('a') fails on 'b',
117/// // even though char('a') followed by any would succeed
118/// assert_eq!(parser("ab"), Err(ErrMode::Backtrack(InputError::new("b", ErrorKind::Tag))));
119/// ```
120///
121pub fn permutation<I: Stream, O, E: ParserError<I>, List: Permutation<I, O, E>>(
122    mut l: List,
123) -> impl Parser<I, O, E> {
124    trace("permutation", move |i: &mut I| l.permutation(i))
125}
126
127impl<const N: usize, I: Stream, O, E: ParserError<I>, P: Parser<I, O, E>> Alt<I, O, E> for [P; N] {
128    fn choice(&mut self, input: &mut I) -> PResult<O, E> {
129        let mut error: Option<E> = None;
130
131        let start = input.checkpoint();
132        for branch in self {
133            input.reset(&start);
134            match branch.parse_next(input) {
135                Err(ErrMode::Backtrack(e)) => {
136                    error = match error {
137                        Some(error) => Some(error.or(e)),
138                        None => Some(e),
139                    };
140                }
141                res => return res,
142            }
143        }
144
145        match error {
146            Some(e) => Err(ErrMode::Backtrack(e.append(input, &start, ErrorKind::Alt))),
147            None => Err(ErrMode::assert(input, "`alt` needs at least one parser")),
148        }
149    }
150}
151
152impl<I: Stream, O, E: ParserError<I>, P: Parser<I, O, E>> Alt<I, O, E> for &mut [P] {
153    fn choice(&mut self, input: &mut I) -> PResult<O, E> {
154        let mut error: Option<E> = None;
155
156        let start = input.checkpoint();
157        for branch in self.iter_mut() {
158            input.reset(&start);
159            match branch.parse_next(input) {
160                Err(ErrMode::Backtrack(e)) => {
161                    error = match error {
162                        Some(error) => Some(error.or(e)),
163                        None => Some(e),
164                    };
165                }
166                res => return res,
167            }
168        }
169
170        match error {
171            Some(e) => Err(ErrMode::Backtrack(e.append(input, &start, ErrorKind::Alt))),
172            None => Err(ErrMode::assert(input, "`alt` needs at least one parser")),
173        }
174    }
175}
176
177macro_rules! alt_trait(
178  ($first:ident $second:ident $($id: ident)+) => (
179    alt_trait!(__impl $first $second; $($id)+);
180  );
181  (__impl $($current:ident)*; $head:ident $($id: ident)+) => (
182    alt_trait_impl!($($current)*);
183
184    alt_trait!(__impl $($current)* $head; $($id)+);
185  );
186  (__impl $($current:ident)*; $head:ident) => (
187    alt_trait_impl!($($current)*);
188    alt_trait_impl!($($current)* $head);
189  );
190);
191
192macro_rules! alt_trait_impl(
193  ($($id:ident)+) => (
194    impl<
195      I: Stream, Output, Error: ParserError<I>,
196      $($id: Parser<I, Output, Error>),+
197    > Alt<I, Output, Error> for ( $($id),+ ) {
198
199      fn choice(&mut self, input: &mut I) -> PResult<Output, Error> {
200        let start = input.checkpoint();
201        match self.0.parse_next(input) {
202          Err(ErrMode::Backtrack(e)) => alt_trait_inner!(1, self, input, start, e, $($id)+),
203          res => res,
204        }
205      }
206    }
207  );
208);
209
210macro_rules! succ (
211  (0, $submac:ident ! ($($rest:tt)*)) => ($submac!(1, $($rest)*));
212  (1, $submac:ident ! ($($rest:tt)*)) => ($submac!(2, $($rest)*));
213  (2, $submac:ident ! ($($rest:tt)*)) => ($submac!(3, $($rest)*));
214  (3, $submac:ident ! ($($rest:tt)*)) => ($submac!(4, $($rest)*));
215  (4, $submac:ident ! ($($rest:tt)*)) => ($submac!(5, $($rest)*));
216  (5, $submac:ident ! ($($rest:tt)*)) => ($submac!(6, $($rest)*));
217  (6, $submac:ident ! ($($rest:tt)*)) => ($submac!(7, $($rest)*));
218  (7, $submac:ident ! ($($rest:tt)*)) => ($submac!(8, $($rest)*));
219  (8, $submac:ident ! ($($rest:tt)*)) => ($submac!(9, $($rest)*));
220  (9, $submac:ident ! ($($rest:tt)*)) => ($submac!(10, $($rest)*));
221  (10, $submac:ident ! ($($rest:tt)*)) => ($submac!(11, $($rest)*));
222  (11, $submac:ident ! ($($rest:tt)*)) => ($submac!(12, $($rest)*));
223  (12, $submac:ident ! ($($rest:tt)*)) => ($submac!(13, $($rest)*));
224  (13, $submac:ident ! ($($rest:tt)*)) => ($submac!(14, $($rest)*));
225  (14, $submac:ident ! ($($rest:tt)*)) => ($submac!(15, $($rest)*));
226  (15, $submac:ident ! ($($rest:tt)*)) => ($submac!(16, $($rest)*));
227  (16, $submac:ident ! ($($rest:tt)*)) => ($submac!(17, $($rest)*));
228  (17, $submac:ident ! ($($rest:tt)*)) => ($submac!(18, $($rest)*));
229  (18, $submac:ident ! ($($rest:tt)*)) => ($submac!(19, $($rest)*));
230  (19, $submac:ident ! ($($rest:tt)*)) => ($submac!(20, $($rest)*));
231  (20, $submac:ident ! ($($rest:tt)*)) => ($submac!(21, $($rest)*));
232);
233
234macro_rules! alt_trait_inner(
235  ($it:tt, $self:expr, $input:expr, $start:ident, $err:expr, $head:ident $($id:ident)+) => ({
236    $input.reset(&$start);
237    match $self.$it.parse_next($input) {
238      Err(ErrMode::Backtrack(e)) => {
239        let err = $err.or(e);
240        succ!($it, alt_trait_inner!($self, $input, $start, err, $($id)+))
241      }
242      res => res,
243    }
244  });
245  ($it:tt, $self:expr, $input:expr, $start:ident, $err:expr, $head:ident) => ({
246    Err(ErrMode::Backtrack($err.append($input, &$start, ErrorKind::Alt)))
247  });
248);
249
250alt_trait!(Alt2 Alt3 Alt4 Alt5 Alt6 Alt7 Alt8 Alt9 Alt10 Alt11 Alt12 Alt13 Alt14 Alt15 Alt16 Alt17 Alt18 Alt19 Alt20 Alt21 Alt22);
251
252// Manually implement Alt for (A,), the 1-tuple type
253impl<I: Stream, O, E: ParserError<I>, A: Parser<I, O, E>> Alt<I, O, E> for (A,) {
254    fn choice(&mut self, input: &mut I) -> PResult<O, E> {
255        self.0.parse_next(input)
256    }
257}
258
259macro_rules! permutation_trait(
260  (
261    $name1:ident $ty1:ident $item1:ident
262    $name2:ident $ty2:ident $item2:ident
263    $($name3:ident $ty3:ident $item3:ident)*
264  ) => (
265    permutation_trait!(__impl $name1 $ty1 $item1, $name2 $ty2 $item2; $($name3 $ty3 $item3)*);
266  );
267  (
268    __impl $($name:ident $ty:ident $item:ident),+;
269    $name1:ident $ty1:ident $item1:ident $($name2:ident $ty2:ident $item2:ident)*
270  ) => (
271    permutation_trait_impl!($($name $ty $item),+);
272    permutation_trait!(__impl $($name $ty $item),+ , $name1 $ty1 $item1; $($name2 $ty2 $item2)*);
273  );
274  (__impl $($name:ident $ty:ident $item:ident),+;) => (
275    permutation_trait_impl!($($name $ty $item),+);
276  );
277);
278
279macro_rules! permutation_trait_impl(
280  ($($name:ident $ty:ident $item:ident),+) => (
281    impl<
282      I: Stream, $($ty),+ , Error: ParserError<I>,
283      $($name: Parser<I, $ty, Error>),+
284    > Permutation<I, ( $($ty),+ ), Error> for ( $($name),+ ) {
285
286      fn permutation(&mut self, input: &mut I) -> PResult<( $($ty),+ ), Error> {
287        let mut res = ($(Option::<$ty>::None),+);
288
289        loop {
290          let mut err: Option<Error> = None;
291          let start = input.checkpoint();
292          permutation_trait_inner!(0, self, input, start, res, err, $($name)+);
293
294          // If we reach here, every iterator has either been applied before,
295          // or errored on the remaining input
296          if let Some(err) = err {
297            // There are remaining parsers, and all errored on the remaining input
298            input.reset(&start);
299            return Err(ErrMode::Backtrack(err.append(input, &start, ErrorKind::Alt)));
300          }
301
302          // All parsers were applied
303          match res {
304            ($(Some($item)),+) => return Ok(($($item),+)),
305            _ => unreachable!(),
306          }
307        }
308      }
309    }
310  );
311);
312
313macro_rules! permutation_trait_inner(
314  ($it:tt, $self:expr, $input:ident, $start:ident, $res:expr, $err:expr, $head:ident $($id:ident)*) => (
315    if $res.$it.is_none() {
316      $input.reset(&$start);
317      match $self.$it.parse_next($input) {
318        Ok(o) => {
319          $res.$it = Some(o);
320          continue;
321        }
322        Err(ErrMode::Backtrack(e)) => {
323          $err = Some(match $err {
324            Some(err) => err.or(e),
325            None => e,
326          });
327        }
328        Err(e) => return Err(e),
329      };
330    }
331    succ!($it, permutation_trait_inner!($self, $input, $start, $res, $err, $($id)*));
332  );
333  ($it:tt, $self:expr, $input:ident, $start:ident, $res:expr, $err:expr,) => ();
334);
335
336permutation_trait!(
337  P1 O1 o1
338  P2 O2 o2
339  P3 O3 o3
340  P4 O4 o4
341  P5 O5 o5
342  P6 O6 o6
343  P7 O7 o7
344  P8 O8 o8
345  P9 O9 o9
346  P10 O10 o10
347  P11 O11 o11
348  P12 O12 o12
349  P13 O13 o13
350  P14 O14 o14
351  P15 O15 o15
352  P16 O16 o16
353  P17 O17 o17
354  P18 O18 o18
355  P19 O19 o19
356  P20 O20 o20
357  P21 O21 o21
358);
winnow/combinator/branch.rs

winnow/combinator/
branch.rs
