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_6]).
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, recognizes 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(name:"alt", parser:move |i: &mut Input| alternatives.choice(input: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_6]).
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 recognizes 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(name:"permutation", parser:move |i: &mut I| l.permutation(input: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: ::Checkpoint = input.checkpoint();
132 for branch: &mut P in self {
133 input.reset(&start);
134 match branch.parse_next(input) {
135 Err(ErrMode::Backtrack(e: E)) => {
136 error = match error {
137 Some(error: E) => Some(error.or(e)),
138 None => Some(e),
139 };
140 }
141 res: Result> => return res,
142 }
143 }
144
145 match error {
146 Some(e: E) => Err(ErrMode::Backtrack(e.append(input, &start, kind:ErrorKind::Alt))),
147 None => Err(ErrMode::assert(input, _message:"`alt` needs at least one parser")),
148 }
149 }
150}
151
152macro_rules! alt_trait(
153 ($first:ident $second:ident $($id: ident)+) => (
154 alt_trait!(__impl $first $second; $($id)+);
155 );
156 (__impl $($current:ident)*; $head:ident $($id: ident)+) => (
157 alt_trait_impl!($($current)*);
158
159 alt_trait!(__impl $($current)* $head; $($id)+);
160 );
161 (__impl $($current:ident)*; $head:ident) => (
162 alt_trait_impl!($($current)*);
163 alt_trait_impl!($($current)* $head);
164 );
165);
166
167macro_rules! alt_trait_impl(
168 ($($id:ident)+) => (
169 impl<
170 I: Stream, Output, Error: ParserError<I>,
171 $($id: Parser<I, Output, Error>),+
172 > Alt<I, Output, Error> for ( $($id),+ ) {
173
174 fn choice(&mut self, input: &mut I) -> PResult<Output, Error> {
175 let start = input.checkpoint();
176 match self.0.parse_next(input) {
177 Err(ErrMode::Backtrack(e)) => alt_trait_inner!(1, self, input, start, e, $($id)+),
178 res => res,
179 }
180 }
181 }
182 );
183);
184
185macro_rules! succ (
186 (0, $submac:ident ! ($($rest:tt)*)) => ($submac!(1, $($rest)*));
187 (1, $submac:ident ! ($($rest:tt)*)) => ($submac!(2, $($rest)*));
188 (2, $submac:ident ! ($($rest:tt)*)) => ($submac!(3, $($rest)*));
189 (3, $submac:ident ! ($($rest:tt)*)) => ($submac!(4, $($rest)*));
190 (4, $submac:ident ! ($($rest:tt)*)) => ($submac!(5, $($rest)*));
191 (5, $submac:ident ! ($($rest:tt)*)) => ($submac!(6, $($rest)*));
192 (6, $submac:ident ! ($($rest:tt)*)) => ($submac!(7, $($rest)*));
193 (7, $submac:ident ! ($($rest:tt)*)) => ($submac!(8, $($rest)*));
194 (8, $submac:ident ! ($($rest:tt)*)) => ($submac!(9, $($rest)*));
195 (9, $submac:ident ! ($($rest:tt)*)) => ($submac!(10, $($rest)*));
196 (10, $submac:ident ! ($($rest:tt)*)) => ($submac!(11, $($rest)*));
197 (11, $submac:ident ! ($($rest:tt)*)) => ($submac!(12, $($rest)*));
198 (12, $submac:ident ! ($($rest:tt)*)) => ($submac!(13, $($rest)*));
199 (13, $submac:ident ! ($($rest:tt)*)) => ($submac!(14, $($rest)*));
200 (14, $submac:ident ! ($($rest:tt)*)) => ($submac!(15, $($rest)*));
201 (15, $submac:ident ! ($($rest:tt)*)) => ($submac!(16, $($rest)*));
202 (16, $submac:ident ! ($($rest:tt)*)) => ($submac!(17, $($rest)*));
203 (17, $submac:ident ! ($($rest:tt)*)) => ($submac!(18, $($rest)*));
204 (18, $submac:ident ! ($($rest:tt)*)) => ($submac!(19, $($rest)*));
205 (19, $submac:ident ! ($($rest:tt)*)) => ($submac!(20, $($rest)*));
206 (20, $submac:ident ! ($($rest:tt)*)) => ($submac!(21, $($rest)*));
207);
208
209macro_rules! alt_trait_inner(
210 ($it:tt, $self:expr, $input:expr, $start:ident, $err:expr, $head:ident $($id:ident)+) => ({
211 $input.reset(&$start);
212 match $self.$it.parse_next($input) {
213 Err(ErrMode::Backtrack(e)) => {
214 let err = $err.or(e);
215 succ!($it, alt_trait_inner!($self, $input, $start, err, $($id)+))
216 }
217 res => res,
218 }
219 });
220 ($it:tt, $self:expr, $input:expr, $start:ident, $err:expr, $head:ident) => ({
221 Err(ErrMode::Backtrack($err.append($input, &$start, ErrorKind::Alt)))
222 });
223);
224
225alt_trait!(Alt2 Alt3 Alt4 Alt5 Alt6 Alt7 Alt8 Alt9 Alt10 Alt11 Alt12 Alt13 Alt14 Alt15 Alt16 Alt17 Alt18 Alt19 Alt20 Alt21 Alt22);
226
227// Manually implement Alt for (A,), the 1-tuple type
228impl<I: Stream, O, E: ParserError<I>, A: Parser<I, O, E>> Alt<I, O, E> for (A,) {
229 fn choice(&mut self, input: &mut I) -> PResult<O, E> {
230 self.0.parse_next(input)
231 }
232}
233
234macro_rules! permutation_trait(
235 (
236 $name1:ident $ty1:ident $item1:ident
237 $name2:ident $ty2:ident $item2:ident
238 $($name3:ident $ty3:ident $item3:ident)*
239 ) => (
240 permutation_trait!(__impl $name1 $ty1 $item1, $name2 $ty2 $item2; $($name3 $ty3 $item3)*);
241 );
242 (
243 __impl $($name:ident $ty:ident $item:ident),+;
244 $name1:ident $ty1:ident $item1:ident $($name2:ident $ty2:ident $item2:ident)*
245 ) => (
246 permutation_trait_impl!($($name $ty $item),+);
247 permutation_trait!(__impl $($name $ty $item),+ , $name1 $ty1 $item1; $($name2 $ty2 $item2)*);
248 );
249 (__impl $($name:ident $ty:ident $item:ident),+;) => (
250 permutation_trait_impl!($($name $ty $item),+);
251 );
252);
253
254macro_rules! permutation_trait_impl(
255 ($($name:ident $ty:ident $item:ident),+) => (
256 impl<
257 I: Stream, $($ty),+ , Error: ParserError<I>,
258 $($name: Parser<I, $ty, Error>),+
259 > Permutation<I, ( $($ty),+ ), Error> for ( $($name),+ ) {
260
261 fn permutation(&mut self, input: &mut I) -> PResult<( $($ty),+ ), Error> {
262 let mut res = ($(Option::<$ty>::None),+);
263
264 loop {
265 let mut err: Option<Error> = None;
266 let start = input.checkpoint();
267 permutation_trait_inner!(0, self, input, start, res, err, $($name)+);
268
269 // If we reach here, every iterator has either been applied before,
270 // or errored on the remaining input
271 if let Some(err) = err {
272 // There are remaining parsers, and all errored on the remaining input
273 input.reset(&start);
274 return Err(ErrMode::Backtrack(err.append(input, &start, ErrorKind::Alt)));
275 }
276
277 // All parsers were applied
278 match res {
279 ($(Some($item)),+) => return Ok(($($item),+)),
280 _ => unreachable!(),
281 }
282 }
283 }
284 }
285 );
286);
287
288macro_rules! permutation_trait_inner(
289 ($it:tt, $self:expr, $input:ident, $start:ident, $res:expr, $err:expr, $head:ident $($id:ident)*) => (
290 if $res.$it.is_none() {
291 $input.reset(&$start);
292 match $self.$it.parse_next($input) {
293 Ok(o) => {
294 $res.$it = Some(o);
295 continue;
296 }
297 Err(ErrMode::Backtrack(e)) => {
298 $err = Some(match $err {
299 Some(err) => err.or(e),
300 None => e,
301 });
302 }
303 Err(e) => return Err(e),
304 };
305 }
306 succ!($it, permutation_trait_inner!($self, $input, $start, $res, $err, $($id)*));
307 );
308 ($it:tt, $self:expr, $input:ident, $start:ident, $res:expr, $err:expr,) => ();
309);
310
311permutation_trait!(
312 P1 O1 o1
313 P2 O2 o2
314 P3 O3 o3
315 P4 O4 o4
316 P5 O5 o5
317 P6 O6 o6
318 P7 O7 o7
319 P8 O8 o8
320 P9 O9 o9
321 P10 O10 o10
322 P11 O11 o11
323 P12 O12 o12
324 P13 O13 o13
325 P14 O14 o14
326 P15 O15 o15
327 P16 O16 o16
328 P17 O17 o17
329 P18 O18 o18
330 P19 O19 o19
331 P20 O20 o20
332 P21 O21 o21
333);
334