1//! Combinators applying their child parser multiple times
2
3use crate::combinator::trace;
4use crate::error::ErrMode;
5use crate::error::ErrorKind;
6use crate::error::ParserError;
7use crate::stream::Accumulate;
8use crate::stream::Range;
9use crate::stream::Stream;
10use crate::PResult;
11use crate::Parser;
12
13/// [`Accumulate`] the output of a parser into a container, like `Vec`
14///
15/// This stops before `n` when the parser returns [`ErrMode::Backtrack`]. To instead chain an error up, see
16/// [`cut_err`][crate::combinator::cut_err].
17///
18/// To recognize a series of tokens, [`Accumulate`] into a `()` and then [`Parser::recognize`].
19///
20/// **Warning:** If the parser passed to `repeat` accepts empty inputs
21/// (like `alpha0` or `digit0`), `repeat` will return an error,
22/// to prevent going into an infinite loop.
23///
24/// # Example
25///
26/// Zero or more repetitions:
27/// ```rust
28/// # #[cfg(feature = "std")] {
29/// # use winnow::{error::ErrMode, error::ErrorKind, error::Needed};
30/// # use winnow::prelude::*;
31/// use winnow::combinator::repeat;
32///
33/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
34/// repeat(0.., "abc").parse_peek(s)
35/// }
36///
37/// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
38/// assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
39/// assert_eq!(parser("123123"), Ok(("123123", vec![])));
40/// assert_eq!(parser(""), Ok(("", vec![])));
41/// # }
42/// ```
43///
44/// One or more repetitions:
45/// ```rust
46/// # #[cfg(feature = "std")] {
47/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
48/// # use winnow::prelude::*;
49/// use winnow::combinator::repeat;
50///
51/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
52/// repeat(1.., "abc").parse_peek(s)
53/// }
54///
55/// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
56/// assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
57/// assert_eq!(parser("123123"), Err(ErrMode::Backtrack(InputError::new("123123", ErrorKind::Tag))));
58/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Tag))));
59/// # }
60/// ```
61///
62/// Fixed number of repetitions:
63/// ```rust
64/// # #[cfg(feature = "std")] {
65/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
66/// # use winnow::prelude::*;
67/// use winnow::combinator::repeat;
68///
69/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
70/// repeat(2, "abc").parse_peek(s)
71/// }
72///
73/// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
74/// assert_eq!(parser("abc123"), Err(ErrMode::Backtrack(InputError::new("123", ErrorKind::Tag))));
75/// assert_eq!(parser("123123"), Err(ErrMode::Backtrack(InputError::new("123123", ErrorKind::Tag))));
76/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Tag))));
77/// assert_eq!(parser("abcabcabc"), Ok(("abc", vec!["abc", "abc"])));
78/// # }
79/// ```
80///
81/// Arbitrary repetitions:
82/// ```rust
83/// # #[cfg(feature = "std")] {
84/// # use winnow::{error::ErrMode, error::ErrorKind, error::Needed};
85/// # use winnow::prelude::*;
86/// use winnow::combinator::repeat;
87///
88/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
89/// repeat(0..=2, "abc").parse_peek(s)
90/// }
91///
92/// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
93/// assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
94/// assert_eq!(parser("123123"), Ok(("123123", vec![])));
95/// assert_eq!(parser(""), Ok(("", vec![])));
96/// assert_eq!(parser("abcabcabc"), Ok(("abc", vec!["abc", "abc"])));
97/// # }
98/// ```
99#[doc(alias = "many0")]
100#[doc(alias = "count")]
101#[doc(alias = "many0_count")]
102#[doc(alias = "many1")]
103#[doc(alias = "many1_count")]
104#[doc(alias = "many_m_n")]
105#[doc(alias = "repeated")]
106#[doc(alias = "skip_many")]
107#[doc(alias = "skip_many1")]
108#[inline(always)]
109pub fn repeat<Input, Output, Accumulator, Error, ParseNext>(
110 occurrences: impl Into<Range>,
111 parser: ParseNext,
112) -> Repeat<ParseNext, Input, Output, Accumulator, Error>
113where
114 Input: Stream,
115 Accumulator: Accumulate<Output>,
116 ParseNext: Parser<Input, Output, Error>,
117 Error: ParserError<Input>,
118{
119 Repeat {
120 occurrences: occurrences.into(),
121 parser,
122 i: Default::default(),
123 o: Default::default(),
124 c: Default::default(),
125 e: Default::default(),
126 }
127}
128
129/// Implementation of [`repeat`]
130#[cfg_attr(nightly, warn(rustdoc::missing_doc_code_examples))]
131pub struct Repeat<P, I, O, C, E>
132where
133 P: Parser<I, O, E>,
134 I: Stream,
135 C: Accumulate<O>,
136 E: ParserError<I>,
137{
138 occurrences: Range,
139 parser: P,
140 i: core::marker::PhantomData<I>,
141 o: core::marker::PhantomData<O>,
142 c: core::marker::PhantomData<C>,
143 e: core::marker::PhantomData<E>,
144}
145
146impl<ParseNext, Input, Output, Error> Repeat<ParseNext, Input, Output, (), Error>
147where
148 ParseNext: Parser<Input, Output, Error>,
149 Input: Stream,
150 Error: ParserError<Input>,
151{
152 /// Repeats the embedded parser, calling `g` to gather the results
153 ///
154 /// This stops before `n` when the parser returns [`ErrMode::Backtrack`]. To instead chain an error up, see
155 /// [`cut_err`][crate::combinator::cut_err].
156 ///
157 /// # Arguments
158 /// * `init` A function returning the initial value.
159 /// * `g` The function that combines a result of `f` with
160 /// the current accumulator.
161 ///
162 /// **Warning:** If the parser passed to `fold` accepts empty inputs
163 /// (like `alpha0` or `digit0`), `fold_repeat` will return an error,
164 /// to prevent going into an infinite loop.
165 ///
166 /// # Example
167 ///
168 /// Zero or more repetitions:
169 /// ```rust
170 /// # use winnow::{error::ErrMode, error::ErrorKind, error::Needed};
171 /// # use winnow::prelude::*;
172 /// use winnow::combinator::repeat;
173 ///
174 /// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
175 /// repeat(
176 /// 0..,
177 /// "abc"
178 /// ).fold(
179 /// Vec::new,
180 /// |mut acc: Vec<_>, item| {
181 /// acc.push(item);
182 /// acc
183 /// }
184 /// ).parse_peek(s)
185 /// }
186 ///
187 /// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
188 /// assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
189 /// assert_eq!(parser("123123"), Ok(("123123", vec![])));
190 /// assert_eq!(parser(""), Ok(("", vec![])));
191 /// ```
192 ///
193 /// One or more repetitions:
194 /// ```rust
195 /// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
196 /// # use winnow::prelude::*;
197 /// use winnow::combinator::repeat;
198 ///
199 /// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
200 /// repeat(
201 /// 1..,
202 /// "abc",
203 /// ).fold(
204 /// Vec::new,
205 /// |mut acc: Vec<_>, item| {
206 /// acc.push(item);
207 /// acc
208 /// }
209 /// ).parse_peek(s)
210 /// }
211 ///
212 /// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
213 /// assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
214 /// assert_eq!(parser("123123"), Err(ErrMode::Backtrack(InputError::new("123123", ErrorKind::Many))));
215 /// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Many))));
216 /// ```
217 ///
218 /// Arbitrary number of repetitions:
219 /// ```rust
220 /// # use winnow::{error::ErrMode, error::ErrorKind, error::Needed};
221 /// # use winnow::prelude::*;
222 /// use winnow::combinator::repeat;
223 ///
224 /// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
225 /// repeat(
226 /// 0..=2,
227 /// "abc",
228 /// ).fold(
229 /// Vec::new,
230 /// |mut acc: Vec<_>, item| {
231 /// acc.push(item);
232 /// acc
233 /// }
234 /// ).parse_peek(s)
235 /// }
236 ///
237 /// assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
238 /// assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
239 /// assert_eq!(parser("123123"), Ok(("123123", vec![])));
240 /// assert_eq!(parser(""), Ok(("", vec![])));
241 /// assert_eq!(parser("abcabcabc"), Ok(("abc", vec!["abc", "abc"])));
242 /// ```
243 #[doc(alias = "fold_many0")]
244 #[doc(alias = "fold_many1")]
245 #[doc(alias = "fold_many_m_n")]
246 #[doc(alias = "fold_repeat")]
247 #[inline(always)]
248 pub fn fold<Init, Op, Result>(
249 mut self,
250 mut init: Init,
251 mut op: Op,
252 ) -> impl Parser<Input, Result, Error>
253 where
254 Init: FnMut() -> Result,
255 Op: FnMut(Result, Output) -> Result,
256 {
257 let Range {
258 start_inclusive,
259 end_inclusive,
260 } = self.occurrences;
261 trace("repeat_fold", move |i: &mut Input| {
262 match (start_inclusive, end_inclusive) {
263 (0, None) => fold_repeat0_(&mut self.parser, &mut init, &mut op, i),
264 (1, None) => fold_repeat1_(&mut self.parser, &mut init, &mut op, i),
265 (start, end) => fold_repeat_m_n_(
266 start,
267 end.unwrap_or(usize::MAX),
268 &mut self.parser,
269 &mut init,
270 &mut op,
271 i,
272 ),
273 }
274 })
275 }
276}
277
278impl<P, I, O, C, E> Parser<I, C, E> for Repeat<P, I, O, C, E>
279where
280 P: Parser<I, O, E>,
281 I: Stream,
282 C: Accumulate<O>,
283 E: ParserError<I>,
284{
285 #[inline(always)]
286 fn parse_next(&mut self, i: &mut I) -> PResult<C, E> {
287 let Range {
288 start_inclusive: usize,
289 end_inclusive: Option,
290 } = self.occurrences;
291 trace("repeat", move |i: &mut I| {
292 match (start_inclusive, end_inclusive) {
293 (0, None) => repeat0_(&mut self.parser, i),
294 (1, None) => repeat1_(&mut self.parser, i),
295 (start, end) if Some(start) == end => repeat_n_(start, &mut self.parser, i),
296 (start, end) => repeat_m_n_(start, end.unwrap_or(usize::MAX), &mut self.parser, i),
297 }
298 })
299 .parse_next(input:i)
300 }
301}
302
303fn repeat0_<I, O, C, E, F>(f: &mut F, i: &mut I) -> PResult<C, E>
304where
305 I: Stream,
306 C: Accumulate<O>,
307 F: Parser<I, O, E>,
308 E: ParserError<I>,
309{
310 let mut acc: C = C::initial(capacity:None);
311 loop {
312 let start: ::Checkpoint = i.checkpoint();
313 let len: usize = i.eof_offset();
314 match f.parse_next(input:i) {
315 Err(ErrMode::Backtrack(_)) => {
316 i.reset(&start);
317 return Ok(acc);
318 }
319 Err(e: ErrMode) => return Err(e),
320 Ok(o: O) => {
321 // infinite loop check: the parser must always consume
322 if i.eof_offset() == len {
323 return Err(ErrMode::assert(input:i, _message:"`repeat` parsers must always consume"));
324 }
325
326 acc.accumulate(acc:o);
327 }
328 }
329 }
330}
331
332fn repeat1_<I, O, C, E, F>(f: &mut F, i: &mut I) -> PResult<C, E>
333where
334 I: Stream,
335 C: Accumulate<O>,
336 F: Parser<I, O, E>,
337 E: ParserError<I>,
338{
339 let start = i.checkpoint();
340 match f.parse_next(i) {
341 Err(e) => Err(e.append(i, &start, ErrorKind::Many)),
342 Ok(o) => {
343 let mut acc = C::initial(None);
344 acc.accumulate(o);
345
346 loop {
347 let start = i.checkpoint();
348 let len = i.eof_offset();
349 match f.parse_next(i) {
350 Err(ErrMode::Backtrack(_)) => {
351 i.reset(&start);
352 return Ok(acc);
353 }
354 Err(e) => return Err(e),
355 Ok(o) => {
356 // infinite loop check: the parser must always consume
357 if i.eof_offset() == len {
358 return Err(ErrMode::assert(i, "`repeat` parsers must always consume"));
359 }
360
361 acc.accumulate(o);
362 }
363 }
364 }
365 }
366 }
367}
368
369fn repeat_n_<I, O, C, E, F>(count: usize, f: &mut F, i: &mut I) -> PResult<C, E>
370where
371 I: Stream,
372 C: Accumulate<O>,
373 F: Parser<I, O, E>,
374 E: ParserError<I>,
375{
376 let mut res: C = C::initial(capacity:Some(count));
377
378 for _ in 0..count {
379 let start: ::Checkpoint = i.checkpoint();
380 let len: usize = i.eof_offset();
381 match f.parse_next(input:i) {
382 Ok(o: O) => {
383 // infinite loop check: the parser must always consume
384 if i.eof_offset() == len {
385 return Err(ErrMode::assert(input:i, _message:"`repeat` parsers must always consume"));
386 }
387
388 res.accumulate(acc:o);
389 }
390 Err(e: ErrMode) => {
391 return Err(e.append(input:i, &start, kind:ErrorKind::Many));
392 }
393 }
394 }
395
396 Ok(res)
397}
398
399fn repeat_m_n_<I, O, C, E, F>(min: usize, max: usize, parse: &mut F, input: &mut I) -> PResult<C, E>
400where
401 I: Stream,
402 C: Accumulate<O>,
403 F: Parser<I, O, E>,
404 E: ParserError<I>,
405{
406 if min > max {
407 return Err(ErrMode::assert(
408 input,
409 "range should be ascending, rather than descending",
410 ));
411 }
412
413 let mut res = C::initial(Some(min));
414 for count in 0..max {
415 let start = input.checkpoint();
416 let len = input.eof_offset();
417 match parse.parse_next(input) {
418 Ok(value) => {
419 // infinite loop check: the parser must always consume
420 if input.eof_offset() == len {
421 return Err(ErrMode::assert(
422 input,
423 "`repeat` parsers must always consume",
424 ));
425 }
426
427 res.accumulate(value);
428 }
429 Err(ErrMode::Backtrack(e)) => {
430 if count < min {
431 return Err(ErrMode::Backtrack(e.append(input, &start, ErrorKind::Many)));
432 } else {
433 input.reset(&start);
434 return Ok(res);
435 }
436 }
437 Err(e) => {
438 return Err(e);
439 }
440 }
441 }
442
443 Ok(res)
444}
445
446/// [`Accumulate`] the output of parser `f` into a container, like `Vec`, until the parser `g`
447/// produces a result.
448///
449/// Returns a tuple of the results of `f` in a `Vec` and the result of `g`.
450///
451/// `f` keeps going so long as `g` produces [`ErrMode::Backtrack`]. To instead chain an error up, see [`cut_err`][crate::combinator::cut_err].
452///
453/// To recognize a series of tokens, [`Accumulate`] into a `()` and then [`Parser::recognize`].
454///
455/// See also
456/// - [`take_till`][crate::token::take_till] for recognizing up-to a member of a [set of tokens][crate::stream::ContainsToken]
457/// - [`take_until`][crate::token::take_until] for recognizing up-to a [`literal`][crate::token::literal] (w/ optional simd optimizations)
458///
459/// # Example
460///
461/// ```rust
462/// # #[cfg(feature = "std")] {
463/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
464/// # use winnow::prelude::*;
465/// use winnow::combinator::repeat_till;
466///
467/// fn parser(s: &str) -> IResult<&str, (Vec<&str>, &str)> {
468/// repeat_till(0.., "abc", "end").parse_peek(s)
469/// };
470///
471/// assert_eq!(parser("abcabcend"), Ok(("", (vec!["abc", "abc"], "end"))));
472/// assert_eq!(parser("abc123end"), Err(ErrMode::Backtrack(InputError::new("123end", ErrorKind::Tag))));
473/// assert_eq!(parser("123123end"), Err(ErrMode::Backtrack(InputError::new("123123end", ErrorKind::Tag))));
474/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Tag))));
475/// assert_eq!(parser("abcendefg"), Ok(("efg", (vec!["abc"], "end"))));
476/// # }
477/// ```
478#[doc(alias = "many_till0")]
479pub fn repeat_till<Input, Output, Accumulator, Terminator, Error, ParseNext, TerminatorParser>(
480 occurrences: impl Into<Range>,
481 mut parse: ParseNext,
482 mut terminator: TerminatorParser,
483) -> impl Parser<Input, (Accumulator, Terminator), Error>
484where
485 Input: Stream,
486 Accumulator: Accumulate<Output>,
487 ParseNext: Parser<Input, Output, Error>,
488 TerminatorParser: Parser<Input, Terminator, Error>,
489 Error: ParserError<Input>,
490{
491 let Range {
492 start_inclusive: usize,
493 end_inclusive: Option,
494 } = occurrences.into();
495 trace(name:"repeat_till", parser:move |i: &mut Input| {
496 match (start_inclusive, end_inclusive) {
497 (0, None) => repeat_till0_(&mut parse, &mut terminator, i),
498 (start: usize, end: Option) => repeat_till_m_n_(
499 min:start,
500 max:end.unwrap_or(usize::MAX),
501 &mut parse,
502 &mut terminator,
503 i,
504 ),
505 }
506 })
507}
508
509fn repeat_till0_<I, O, C, P, E, F, G>(f: &mut F, g: &mut G, i: &mut I) -> PResult<(C, P), E>
510where
511 I: Stream,
512 C: Accumulate<O>,
513 F: Parser<I, O, E>,
514 G: Parser<I, P, E>,
515 E: ParserError<I>,
516{
517 let mut res = C::initial(None);
518 loop {
519 let start = i.checkpoint();
520 let len = i.eof_offset();
521 match g.parse_next(i) {
522 Ok(o) => return Ok((res, o)),
523 Err(ErrMode::Backtrack(_)) => {
524 i.reset(&start);
525 match f.parse_next(i) {
526 Err(e) => return Err(e.append(i, &start, ErrorKind::Many)),
527 Ok(o) => {
528 // infinite loop check: the parser must always consume
529 if i.eof_offset() == len {
530 return Err(ErrMode::assert(i, "`repeat` parsers must always consume"));
531 }
532
533 res.accumulate(o);
534 }
535 }
536 }
537 Err(e) => return Err(e),
538 }
539 }
540}
541
542fn repeat_till_m_n_<I, O, C, P, E, F, G>(
543 min: usize,
544 max: usize,
545 f: &mut F,
546 g: &mut G,
547 i: &mut I,
548) -> PResult<(C, P), E>
549where
550 I: Stream,
551 C: Accumulate<O>,
552 F: Parser<I, O, E>,
553 G: Parser<I, P, E>,
554 E: ParserError<I>,
555{
556 if min > max {
557 return Err(ErrMode::assert(
558 i,
559 "range should be ascending, rather than descending",
560 ));
561 }
562
563 let mut res = C::initial(Some(min));
564
565 let start = i.checkpoint();
566 for _ in 0..min {
567 match f.parse_next(i) {
568 Ok(o) => {
569 res.accumulate(o);
570 }
571 Err(e) => {
572 return Err(e.append(i, &start, ErrorKind::Many));
573 }
574 }
575 }
576 for count in min..=max {
577 let start = i.checkpoint();
578 let len = i.eof_offset();
579 match g.parse_next(i) {
580 Ok(o) => return Ok((res, o)),
581 Err(ErrMode::Backtrack(err)) => {
582 if count == max {
583 return Err(ErrMode::Backtrack(err));
584 }
585 i.reset(&start);
586 match f.parse_next(i) {
587 Err(e) => {
588 return Err(e.append(i, &start, ErrorKind::Many));
589 }
590 Ok(o) => {
591 // infinite loop check: the parser must always consume
592 if i.eof_offset() == len {
593 return Err(ErrMode::assert(i, "`repeat` parsers must always consume"));
594 }
595
596 res.accumulate(o);
597 }
598 }
599 }
600 Err(e) => return Err(e),
601 }
602 }
603 unreachable!()
604}
605
606/// [`Accumulate`] the output of a parser, interleaved with `sep`
607///
608/// This stops when either parser returns [`ErrMode::Backtrack`]. To instead chain an error up, see
609/// [`cut_err`][crate::combinator::cut_err].
610///
611/// **Warning:** If the separator parser accepts empty inputs
612/// (like `alpha0` or `digit0`), `separated` will return an error,
613/// to prevent going into an infinite loop.
614///
615/// # Example
616///
617/// Zero or more repetitions:
618/// ```rust
619/// # #[cfg(feature = "std")] {
620/// # use winnow::{error::ErrMode, error::ErrorKind, error::Needed};
621/// # use winnow::prelude::*;
622/// use winnow::combinator::separated;
623///
624/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
625/// separated(0.., "abc", "|").parse_peek(s)
626/// }
627///
628/// assert_eq!(parser("abc|abc|abc"), Ok(("", vec!["abc", "abc", "abc"])));
629/// assert_eq!(parser("abc123abc"), Ok(("123abc", vec!["abc"])));
630/// assert_eq!(parser("abc|def"), Ok(("|def", vec!["abc"])));
631/// assert_eq!(parser(""), Ok(("", vec![])));
632/// assert_eq!(parser("def|abc"), Ok(("def|abc", vec![])));
633/// # }
634/// ```
635///
636/// One or more repetitions:
637/// ```rust
638/// # #[cfg(feature = "std")] {
639/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
640/// # use winnow::prelude::*;
641/// use winnow::combinator::separated;
642///
643/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
644/// separated(1.., "abc", "|").parse_peek(s)
645/// }
646///
647/// assert_eq!(parser("abc|abc|abc"), Ok(("", vec!["abc", "abc", "abc"])));
648/// assert_eq!(parser("abc123abc"), Ok(("123abc", vec!["abc"])));
649/// assert_eq!(parser("abc|def"), Ok(("|def", vec!["abc"])));
650/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Tag))));
651/// assert_eq!(parser("def|abc"), Err(ErrMode::Backtrack(InputError::new("def|abc", ErrorKind::Tag))));
652/// # }
653/// ```
654///
655/// Fixed number of repetitions:
656/// ```rust
657/// # #[cfg(feature = "std")] {
658/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
659/// # use winnow::prelude::*;
660/// use winnow::combinator::separated;
661///
662/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
663/// separated(2, "abc", "|").parse_peek(s)
664/// }
665///
666/// assert_eq!(parser("abc|abc|abc"), Ok(("|abc", vec!["abc", "abc"])));
667/// assert_eq!(parser("abc123abc"), Err(ErrMode::Backtrack(InputError::new("123abc", ErrorKind::Tag))));
668/// assert_eq!(parser("abc|def"), Err(ErrMode::Backtrack(InputError::new("def", ErrorKind::Tag))));
669/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Tag))));
670/// assert_eq!(parser("def|abc"), Err(ErrMode::Backtrack(InputError::new("def|abc", ErrorKind::Tag))));
671/// # }
672/// ```
673///
674/// Arbitrary repetitions:
675/// ```rust
676/// # #[cfg(feature = "std")] {
677/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
678/// # use winnow::prelude::*;
679/// use winnow::combinator::separated;
680///
681/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
682/// separated(0..=2, "abc", "|").parse_peek(s)
683/// }
684///
685/// assert_eq!(parser("abc|abc|abc"), Ok(("|abc", vec!["abc", "abc"])));
686/// assert_eq!(parser("abc123abc"), Ok(("123abc", vec!["abc"])));
687/// assert_eq!(parser("abc|def"), Ok(("|def", vec!["abc"])));
688/// assert_eq!(parser(""), Ok(("", vec![])));
689/// assert_eq!(parser("def|abc"), Ok(("def|abc", vec![])));
690/// # }
691/// ```
692#[doc(alias = "sep_by")]
693#[doc(alias = "sep_by1")]
694#[doc(alias = "separated_list0")]
695#[doc(alias = "separated_list1")]
696#[doc(alias = "separated_m_n")]
697#[inline(always)]
698pub fn separated<Input, Output, Accumulator, Sep, Error, ParseNext, SepParser>(
699 occurrences: impl Into<Range>,
700 mut parser: ParseNext,
701 mut separator: SepParser,
702) -> impl Parser<Input, Accumulator, Error>
703where
704 Input: Stream,
705 Accumulator: Accumulate<Output>,
706 ParseNext: Parser<Input, Output, Error>,
707 SepParser: Parser<Input, Sep, Error>,
708 Error: ParserError<Input>,
709{
710 let Range {
711 start_inclusive: usize,
712 end_inclusive: Option,
713 } = occurrences.into();
714 trace(name:"separated", parser:move |input: &mut Input| {
715 match (start_inclusive, end_inclusive) {
716 (0, None) => separated0_(&mut parser, &mut separator, input),
717 (1, None) => separated1_(&mut parser, &mut separator, input),
718 (start: usize, end: Option) if Some(start) == end => {
719 separated_n_(count:start, &mut parser, &mut separator, input)
720 }
721 (start: usize, end: Option) => separated_m_n_(
722 min:start,
723 max:end.unwrap_or(default:usize::MAX),
724 &mut parser,
725 &mut separator,
726 input,
727 ),
728 }
729 })
730}
731
732fn separated0_<I, O, C, O2, E, P, S>(
733 parser: &mut P,
734 separator: &mut S,
735 input: &mut I,
736) -> PResult<C, E>
737where
738 I: Stream,
739 C: Accumulate<O>,
740 P: Parser<I, O, E>,
741 S: Parser<I, O2, E>,
742 E: ParserError<I>,
743{
744 let mut acc = C::initial(None);
745
746 let start = input.checkpoint();
747 match parser.parse_next(input) {
748 Err(ErrMode::Backtrack(_)) => {
749 input.reset(&start);
750 return Ok(acc);
751 }
752 Err(e) => return Err(e),
753 Ok(o) => {
754 acc.accumulate(o);
755 }
756 }
757
758 loop {
759 let start = input.checkpoint();
760 let len = input.eof_offset();
761 match separator.parse_next(input) {
762 Err(ErrMode::Backtrack(_)) => {
763 input.reset(&start);
764 return Ok(acc);
765 }
766 Err(e) => return Err(e),
767 Ok(_) => {
768 // infinite loop check
769 if input.eof_offset() == len {
770 return Err(ErrMode::assert(
771 input,
772 "`separated` separator parser must always consume",
773 ));
774 }
775
776 match parser.parse_next(input) {
777 Err(ErrMode::Backtrack(_)) => {
778 input.reset(&start);
779 return Ok(acc);
780 }
781 Err(e) => return Err(e),
782 Ok(o) => {
783 acc.accumulate(o);
784 }
785 }
786 }
787 }
788 }
789}
790
791fn separated1_<I, O, C, O2, E, P, S>(
792 parser: &mut P,
793 separator: &mut S,
794 input: &mut I,
795) -> PResult<C, E>
796where
797 I: Stream,
798 C: Accumulate<O>,
799 P: Parser<I, O, E>,
800 S: Parser<I, O2, E>,
801 E: ParserError<I>,
802{
803 let mut acc = C::initial(None);
804
805 // Parse the first element
806 match parser.parse_next(input) {
807 Err(e) => return Err(e),
808 Ok(o) => {
809 acc.accumulate(o);
810 }
811 }
812
813 loop {
814 let start = input.checkpoint();
815 let len = input.eof_offset();
816 match separator.parse_next(input) {
817 Err(ErrMode::Backtrack(_)) => {
818 input.reset(&start);
819 return Ok(acc);
820 }
821 Err(e) => return Err(e),
822 Ok(_) => {
823 // infinite loop check
824 if input.eof_offset() == len {
825 return Err(ErrMode::assert(
826 input,
827 "`separated` separator parser must always consume",
828 ));
829 }
830
831 match parser.parse_next(input) {
832 Err(ErrMode::Backtrack(_)) => {
833 input.reset(&start);
834 return Ok(acc);
835 }
836 Err(e) => return Err(e),
837 Ok(o) => {
838 acc.accumulate(o);
839 }
840 }
841 }
842 }
843 }
844}
845
846fn separated_n_<I, O, C, O2, E, P, S>(
847 count: usize,
848 parser: &mut P,
849 separator: &mut S,
850 input: &mut I,
851) -> PResult<C, E>
852where
853 I: Stream,
854 C: Accumulate<O>,
855 P: Parser<I, O, E>,
856 S: Parser<I, O2, E>,
857 E: ParserError<I>,
858{
859 let mut acc = C::initial(Some(count));
860
861 if count == 0 {
862 return Ok(acc);
863 }
864
865 let start = input.checkpoint();
866 match parser.parse_next(input) {
867 Err(e) => {
868 return Err(e.append(input, &start, ErrorKind::Many));
869 }
870 Ok(o) => {
871 acc.accumulate(o);
872 }
873 }
874
875 for _ in 1..count {
876 let start = input.checkpoint();
877 let len = input.eof_offset();
878 match separator.parse_next(input) {
879 Err(e) => {
880 return Err(e.append(input, &start, ErrorKind::Many));
881 }
882 Ok(_) => {
883 // infinite loop check
884 if input.eof_offset() == len {
885 return Err(ErrMode::assert(
886 input,
887 "`separated` separator parser must always consume",
888 ));
889 }
890
891 match parser.parse_next(input) {
892 Err(e) => {
893 return Err(e.append(input, &start, ErrorKind::Many));
894 }
895 Ok(o) => {
896 acc.accumulate(o);
897 }
898 }
899 }
900 }
901 }
902
903 Ok(acc)
904}
905
906fn separated_m_n_<I, O, C, O2, E, P, S>(
907 min: usize,
908 max: usize,
909 parser: &mut P,
910 separator: &mut S,
911 input: &mut I,
912) -> PResult<C, E>
913where
914 I: Stream,
915 C: Accumulate<O>,
916 P: Parser<I, O, E>,
917 S: Parser<I, O2, E>,
918 E: ParserError<I>,
919{
920 if min > max {
921 return Err(ErrMode::assert(
922 input,
923 "range should be ascending, rather than descending",
924 ));
925 }
926
927 let mut acc = C::initial(Some(min));
928
929 let start = input.checkpoint();
930 match parser.parse_next(input) {
931 Err(ErrMode::Backtrack(e)) => {
932 if min == 0 {
933 input.reset(&start);
934 return Ok(acc);
935 } else {
936 return Err(ErrMode::Backtrack(e.append(input, &start, ErrorKind::Many)));
937 }
938 }
939 Err(e) => return Err(e),
940 Ok(o) => {
941 acc.accumulate(o);
942 }
943 }
944
945 for index in 1..max {
946 let start = input.checkpoint();
947 let len = input.eof_offset();
948 match separator.parse_next(input) {
949 Err(ErrMode::Backtrack(e)) => {
950 if index < min {
951 return Err(ErrMode::Backtrack(e.append(input, &start, ErrorKind::Many)));
952 } else {
953 input.reset(&start);
954 return Ok(acc);
955 }
956 }
957 Err(e) => {
958 return Err(e);
959 }
960 Ok(_) => {
961 // infinite loop check
962 if input.eof_offset() == len {
963 return Err(ErrMode::assert(
964 input,
965 "`separated` separator parser must always consume",
966 ));
967 }
968
969 match parser.parse_next(input) {
970 Err(ErrMode::Backtrack(e)) => {
971 if index < min {
972 return Err(ErrMode::Backtrack(e.append(
973 input,
974 &start,
975 ErrorKind::Many,
976 )));
977 } else {
978 input.reset(&start);
979 return Ok(acc);
980 }
981 }
982 Err(e) => {
983 return Err(e);
984 }
985 Ok(o) => {
986 acc.accumulate(o);
987 }
988 }
989 }
990 }
991 }
992
993 Ok(acc)
994}
995
996/// Alternates between two parsers, merging the results (left associative)
997///
998/// This stops when either parser returns [`ErrMode::Backtrack`]. To instead chain an error up, see
999/// [`cut_err`][crate::combinator::cut_err].
1000///
1001/// # Example
1002///
1003/// ```rust
1004/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
1005/// # use winnow::prelude::*;
1006/// use winnow::combinator::separated_foldl1;
1007/// use winnow::ascii::dec_int;
1008///
1009/// fn parser(s: &str) -> IResult<&str, i32> {
1010/// separated_foldl1(dec_int, "-", |l, _, r| l - r).parse_peek(s)
1011/// }
1012///
1013/// assert_eq!(parser("9-3-5"), Ok(("", 1)));
1014/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Token))));
1015/// assert_eq!(parser("def|abc"), Err(ErrMode::Backtrack(InputError::new("def|abc", ErrorKind::Verify))));
1016/// ```
1017pub fn separated_foldl1<Input, Output, Sep, Error, ParseNext, SepParser, Op>(
1018 mut parser: ParseNext,
1019 mut sep: SepParser,
1020 mut op: Op,
1021) -> impl Parser<Input, Output, Error>
1022where
1023 Input: Stream,
1024 ParseNext: Parser<Input, Output, Error>,
1025 SepParser: Parser<Input, Sep, Error>,
1026 Error: ParserError<Input>,
1027 Op: FnMut(Output, Sep, Output) -> Output,
1028{
1029 trace("separated_foldl1", move |i: &mut Input| {
1030 let mut ol = parser.parse_next(i)?;
1031
1032 loop {
1033 let start = i.checkpoint();
1034 let len = i.eof_offset();
1035 match sep.parse_next(i) {
1036 Err(ErrMode::Backtrack(_)) => {
1037 i.reset(&start);
1038 return Ok(ol);
1039 }
1040 Err(e) => return Err(e),
1041 Ok(s) => {
1042 // infinite loop check: the parser must always consume
1043 if i.eof_offset() == len {
1044 return Err(ErrMode::assert(i, "`repeat` parsers must always consume"));
1045 }
1046
1047 match parser.parse_next(i) {
1048 Err(ErrMode::Backtrack(_)) => {
1049 i.reset(&start);
1050 return Ok(ol);
1051 }
1052 Err(e) => return Err(e),
1053 Ok(or) => {
1054 ol = op(ol, s, or);
1055 }
1056 }
1057 }
1058 }
1059 }
1060 })
1061}
1062
1063/// Alternates between two parsers, merging the results (right associative)
1064///
1065/// This stops when either parser returns [`ErrMode::Backtrack`]. To instead chain an error up, see
1066/// [`cut_err`][crate::combinator::cut_err].
1067///
1068/// # Example
1069///
1070/// ```
1071/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
1072/// # use winnow::prelude::*;
1073/// use winnow::combinator::separated_foldr1;
1074/// use winnow::ascii::dec_uint;
1075///
1076/// fn parser(s: &str) -> IResult<&str, u32> {
1077/// separated_foldr1(dec_uint, "^", |l: u32, _, r: u32| l.pow(r)).parse_peek(s)
1078/// }
1079///
1080/// assert_eq!(parser("2^3^2"), Ok(("", 512)));
1081/// assert_eq!(parser("2"), Ok(("", 2)));
1082/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Token))));
1083/// assert_eq!(parser("def|abc"), Err(ErrMode::Backtrack(InputError::new("def|abc", ErrorKind::Verify))));
1084/// ```
1085#[cfg(feature = "alloc")]
1086pub fn separated_foldr1<Input, Output, Sep, Error, ParseNext, SepParser, Op>(
1087 mut parser: ParseNext,
1088 mut sep: SepParser,
1089 mut op: Op,
1090) -> impl Parser<Input, Output, Error>
1091where
1092 Input: Stream,
1093 ParseNext: Parser<Input, Output, Error>,
1094 SepParser: Parser<Input, Sep, Error>,
1095 Error: ParserError<Input>,
1096 Op: FnMut(Output, Sep, Output) -> Output,
1097{
1098 trace(name:"separated_foldr1", parser:move |i: &mut Input| {
1099 let ol: Output = parser.parse_next(input:i)?;
1100 let all: crate::lib::std::vec::Vec<(Sep, Output)> =
1101 repeat(0.., (sep.by_ref(), parser.by_ref())).parse_next(input:i)?;
1102 if let Some((s: Sep, or: Output)) = allimpl Iterator
1103 .into_iter()
1104 .rev()
1105 .reduce(|(sr: Sep, or: Output), (sl: Sep, ol: Output)| (sl, op(ol, sr, or)))
1106 {
1107 let merged: Output = op(ol, s, or);
1108 Ok(merged)
1109 } else {
1110 Ok(ol)
1111 }
1112 })
1113}
1114
1115/// Repeats the embedded parser, filling the given slice with results.
1116///
1117/// This parser fails if the input runs out before the given slice is full.
1118///
1119/// # Example
1120///
1121/// ```rust
1122/// # use winnow::{error::ErrMode, error::{InputError, ErrorKind}, error::Needed};
1123/// # use winnow::prelude::*;
1124/// use winnow::combinator::fill;
1125///
1126/// fn parser(s: &str) -> IResult<&str, [&str; 2]> {
1127/// let mut buf = ["", ""];
1128/// let (rest, ()) = fill("abc", &mut buf).parse_peek(s)?;
1129/// Ok((rest, buf))
1130/// }
1131///
1132/// assert_eq!(parser("abcabc"), Ok(("", ["abc", "abc"])));
1133/// assert_eq!(parser("abc123"), Err(ErrMode::Backtrack(InputError::new("123", ErrorKind::Tag))));
1134/// assert_eq!(parser("123123"), Err(ErrMode::Backtrack(InputError::new("123123", ErrorKind::Tag))));
1135/// assert_eq!(parser(""), Err(ErrMode::Backtrack(InputError::new("", ErrorKind::Tag))));
1136/// assert_eq!(parser("abcabcabc"), Ok(("abc", ["abc", "abc"])));
1137/// ```
1138pub fn fill<'i, Input, Output, Error, ParseNext>(
1139 mut parser: ParseNext,
1140 buf: &'i mut [Output],
1141) -> impl Parser<Input, (), Error> + 'i
1142where
1143 Input: Stream + 'i,
1144 ParseNext: Parser<Input, Output, Error> + 'i,
1145 Error: ParserError<Input> + 'i,
1146{
1147 trace(name:"fill", parser:move |i: &mut Input| {
1148 for elem: &mut Output in buf.iter_mut() {
1149 let start: ::Checkpoint = i.checkpoint();
1150 match parser.parse_next(input:i) {
1151 Ok(o: Output) => {
1152 *elem = o;
1153 }
1154 Err(e: ErrMode) => {
1155 return Err(e.append(input:i, &start, kind:ErrorKind::Many));
1156 }
1157 }
1158 }
1159
1160 Ok(())
1161 })
1162}
1163
1164fn fold_repeat0_<I, O, E, F, G, H, R>(
1165 f: &mut F,
1166 init: &mut H,
1167 g: &mut G,
1168 input: &mut I,
1169) -> PResult<R, E>
1170where
1171 I: Stream,
1172 F: Parser<I, O, E>,
1173 G: FnMut(R, O) -> R,
1174 H: FnMut() -> R,
1175 E: ParserError<I>,
1176{
1177 let mut res = init();
1178
1179 loop {
1180 let start = input.checkpoint();
1181 let len = input.eof_offset();
1182 match f.parse_next(input) {
1183 Ok(o) => {
1184 // infinite loop check: the parser must always consume
1185 if input.eof_offset() == len {
1186 return Err(ErrMode::assert(
1187 input,
1188 "`repeat` parsers must always consume",
1189 ));
1190 }
1191
1192 res = g(res, o);
1193 }
1194 Err(ErrMode::Backtrack(_)) => {
1195 input.reset(&start);
1196 return Ok(res);
1197 }
1198 Err(e) => {
1199 return Err(e);
1200 }
1201 }
1202 }
1203}
1204
1205fn fold_repeat1_<I, O, E, F, G, H, R>(
1206 f: &mut F,
1207 init: &mut H,
1208 g: &mut G,
1209 input: &mut I,
1210) -> PResult<R, E>
1211where
1212 I: Stream,
1213 F: Parser<I, O, E>,
1214 G: FnMut(R, O) -> R,
1215 H: FnMut() -> R,
1216 E: ParserError<I>,
1217{
1218 let init = init();
1219 match f.parse_next(input) {
1220 Err(ErrMode::Backtrack(_)) => Err(ErrMode::from_error_kind(input, ErrorKind::Many)),
1221 Err(e) => Err(e),
1222 Ok(o1) => {
1223 let mut acc = g(init, o1);
1224
1225 loop {
1226 let start = input.checkpoint();
1227 let len = input.eof_offset();
1228 match f.parse_next(input) {
1229 Err(ErrMode::Backtrack(_)) => {
1230 input.reset(&start);
1231 break;
1232 }
1233 Err(e) => return Err(e),
1234 Ok(o) => {
1235 // infinite loop check: the parser must always consume
1236 if input.eof_offset() == len {
1237 return Err(ErrMode::assert(
1238 input,
1239 "`repeat` parsers must always consume",
1240 ));
1241 }
1242
1243 acc = g(acc, o);
1244 }
1245 }
1246 }
1247
1248 Ok(acc)
1249 }
1250 }
1251}
1252
1253fn fold_repeat_m_n_<I, O, E, F, G, H, R>(
1254 min: usize,
1255 max: usize,
1256 parse: &mut F,
1257 init: &mut H,
1258 fold: &mut G,
1259 input: &mut I,
1260) -> PResult<R, E>
1261where
1262 I: Stream,
1263 F: Parser<I, O, E>,
1264 G: FnMut(R, O) -> R,
1265 H: FnMut() -> R,
1266 E: ParserError<I>,
1267{
1268 if min > max {
1269 return Err(ErrMode::assert(
1270 input,
1271 "range should be ascending, rather than descending",
1272 ));
1273 }
1274
1275 let mut acc = init();
1276 for count in 0..max {
1277 let start = input.checkpoint();
1278 let len = input.eof_offset();
1279 match parse.parse_next(input) {
1280 Ok(value) => {
1281 // infinite loop check: the parser must always consume
1282 if input.eof_offset() == len {
1283 return Err(ErrMode::assert(
1284 input,
1285 "`repeat` parsers must always consume",
1286 ));
1287 }
1288
1289 acc = fold(acc, value);
1290 }
1291 //FInputXMError: handle failure properly
1292 Err(ErrMode::Backtrack(err)) => {
1293 if count < min {
1294 return Err(ErrMode::Backtrack(err.append(
1295 input,
1296 &start,
1297 ErrorKind::Many,
1298 )));
1299 } else {
1300 input.reset(&start);
1301 break;
1302 }
1303 }
1304 Err(e) => return Err(e),
1305 }
1306 }
1307
1308 Ok(acc)
1309}
1310