Repository: rust-bakery/nom (language: rust)

Issue:
Support custom containers for `many` functions
## Prerequisites

Here are a few things you should provide to help me understand the issue:

- Rust version : 1.55.0
- nom version : 7.0.0
- nom compilation features used: default

## Test case

I wanted to experiment with porting `toml_edit` to nom, one thing I especially found missing was custom collection support.  If I use `many0`, it only supports `Vec`.  The naive approach in code is to do
```rust
fn ml_body(input: &str) -> IResult<&str, String> {
    many(substr).map(|s| s.join(""))
}
```
Leading me to allocate a `Vec<String>` and then merge them.  `combine` defaults to `Vec` but allows any `Extend` type, allowing
```rust
fn ml_body(input: &str) -> IResult<&str, String> {
    many(substr)
}
```
which will collect directly into the `String`, saving on a lot of allocations

I'm also looking at optimizing a section of my parser where collect into a `Vec` and then turn it into a `HashMap` with errors by creating a custom type that wraps `HashMap` with my error type and stores off errors on `Extend`, allowing me to bypass the `Vec` allocation.

I could do all of this with `fold_` variants but it will be a bit messier.


Discussion / hints:
I guess this can be link to #1393.

I think we can use https://doc.rust-lang.org/std/iter/trait.Extend.html to allow this for many.

> I could do all of this with fold_ variants but it will be a bit messier.

You can add your own parser for reuse in the waiting, something like that (I'm more used to nom 6 so probably mistake):
```rust
fn many0_string(f: impl Parser) -> impl Parser {
  |input| {
    fold_many0(
      f,
      String::new,
      |mut acc: String, item| {
        string.push_str(item);
        acc
      }
    )(input)
  }
}
```

> combine defaults to Vec but allows any Extend type, allowing

What is combine ? I don't follow here.

> I'm also looking at optimizing a section of my parser where collect into a Vec and then turn it into a HashMap with errors by creating a custom type that wraps HashMap with my error type and stores off errors on Extend, allowing me to bypass the Vec allocation.

Some sort of [`partition_result()`](https://docs.rs/itertools/0.10.1/itertools/trait.Itertools.html#method.partition_result) ?
> What is combine ? I don't follow here.

Sorry, `combine` is another parser combinator.

e.g. https://docs.rs/combine/4.6.1/combine/fn.many.html has the collection set to `F: Extend<P::Output> + Default, `

> Some sort of partition_result() ?

More like [`try_fold`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.try_fold)

So speaking of, maybe we should have `try_fold_many*` :)
I think we can clearly add a `try_fold` and I will try update my PR to include `extend`.
Oh, thanks for looking to include `Extend`!

I've split out `try_fold` into https://github.com/Geal/nom/issues/1411.
oh, using Extend is a great suggestion! I was wondering about doing that too

Fix patch:
diff --git a/benchmarks/benches/ini.rs b/benchmarks/benches/ini.rs
index 95fd95cd0..58c73a167 100644
--- a/benchmarks/benches/ini.rs
+++ b/benchmarks/benches/ini.rs
@@ -32,19 +32,16 @@ fn key_value(i: &[u8]) -> IResult<&[u8], (&str, &str)> {
 }
 
 fn categories(i: &[u8]) -> IResult<&[u8], HashMap<&str, HashMap<&str, &str>>> {
-  map(
-    many(
-      0..,
-      separated_pair(
-        category,
-        opt(multispace),
-        map(
-          many(0.., terminated(key_value, opt(multispace))),
-          |vec: Vec<_>| vec.into_iter().collect(),
-        ),
+  many(
+    0..,
+    separated_pair(
+      category,
+      opt(multispace),
+      map(
+        many(0.., terminated(key_value, opt(multispace))),
+        |vec: Vec<_>| vec.into_iter().collect(),
       ),
     ),
-    |vec: Vec<_>| vec.into_iter().collect(),
   )(i)
 }
 
diff --git a/benchmarks/benches/ini_str.rs b/benchmarks/benches/ini_str.rs
index 82dce2efa..9b944c0f6 100644
--- a/benchmarks/benches/ini_str.rs
+++ b/benchmarks/benches/ini_str.rs
@@ -39,30 +39,16 @@ fn key_value(i: &str) -> IResult<&str, (&str, &str)> {
   Ok((i, (key, val)))
 }
 
-fn keys_and_values_aggregator(i: &str) -> IResult<&str, Vec<(&str, &str)>> {
-  many(0.., key_value)(i)
-}
-
 fn keys_and_values(input: &str) -> IResult<&str, HashMap<&str, &str>> {
-  match keys_and_values_aggregator(input) {
-    Ok((i, tuple_vec)) => Ok((i, tuple_vec.into_iter().collect())),
-    Err(e) => Err(e),
-  }
+  many(0.., key_value)(input)
 }
 
 fn category_and_keys(i: &str) -> IResult<&str, (&str, HashMap<&str, &str>)> {
   pair(category, keys_and_values)(i)
 }
 
-fn categories_aggregator(i: &str) -> IResult<&str, Vec<(&str, HashMap<&str, &str>)>> {
-  many(0.., category_and_keys)(i)
-}
-
 fn categories(input: &str) -> IResult<&str, HashMap<&str, HashMap<&str, &str>>> {
-  match categories_aggregator(input) {
-    Ok((i, tuple_vec)) => Ok((i, tuple_vec.into_iter().collect())),
-    Err(e) => Err(e),
-  }
+  many(0.., category_and_keys)(input)
 }
 
 fn bench_ini_str(c: &mut Criterion) {
diff --git a/src/multi/mod.rs b/src/multi/mod.rs
index 7bbc03dee..1056add83 100644
--- a/src/multi/mod.rs
+++ b/src/multi/mod.rs
@@ -8,8 +8,6 @@ use crate::error::ParseError;
 use crate::internal::{Err, IResult, Needed, Parser};
 use crate::lib::std::num::NonZeroUsize;
 #[cfg(feature = "alloc")]
-use crate::lib::std::ops::Bound;
-#[cfg(feature = "alloc")]
 use crate::lib::std::vec::Vec;
 use crate::Input;
 use crate::{
@@ -1053,7 +1051,7 @@ where
   }
 }
 
-/// Repeats the embedded parser and returns the results in a `Vec`.
+/// Repeats the embedded parser and collects the results in a type implementing `Extend + Default`.
 /// Fails if the amount of time the embedded parser is run is not
 /// within the specified range.
 /// # Arguments
@@ -1062,6 +1060,7 @@ where
 ///   * A single `usize` value is equivalent to `value..=value`.
 ///   * An empty range is invalid.
 /// * `parse` The parser to apply.
+///
 /// ```rust
 /// # #[macro_use] extern crate nom;
 /// # use nom::{Err, error::ErrorKind, Needed, IResult};
@@ -1078,29 +1077,82 @@ where
 /// assert_eq!(parser(""), Ok(("", vec![])));
 /// assert_eq!(parser("abcabcabc"), Ok(("abc", vec!["abc", "abc"])));
 /// ```
+///
+/// This is not limited to `Vec`, other collections like `HashMap`
+/// can be used:
+///
+/// ```rust
+/// # #[macro_use] extern crate nom;
+/// # use nom::{Err, error::ErrorKind, Needed, IResult};
+/// use nom::multi::many;
+/// use nom::bytes::complete::{tag, take_while};
+/// use nom::sequence::{separated_pair, terminated};
+/// use nom::AsChar;
+///
+/// use std::collections::HashMap;
+///
+/// fn key_value(s: &str) -> IResult<&str, HashMap<&str, &str>> {
+///   many(0.., terminated(
+///     separated_pair(
+///       take_while(AsChar::is_alpha),
+///       tag("="),
+///       take_while(AsChar::is_alpha)
+///     ),
+///     tag(";")
+///   ))(s)
+/// }
+///
+/// assert_eq!(
+///   key_value("a=b;c=d;"),
+///   Ok(("", HashMap::from([("a", "b"), ("c", "d")])))
+/// );
+/// ```
+///
+/// If more control is needed on the default value, [fold] can
+/// be used instead:
+///
+/// ```rust
+/// # #[macro_use] extern crate nom;
+/// # use nom::{Err, error::ErrorKind, Needed, IResult};
+/// use nom::multi::fold;
+/// use nom::bytes::complete::tag;
+///
+///
+/// fn parser(s: &str) -> IResult<&str, Vec<&str>> {
+///   fold(
+///     0..=4,
+///     tag("abc"),
+///     // preallocates a vector of the max size
+///     || Vec::with_capacity(4),
+///     |mut acc: Vec<_>, item| {
+///       acc.push(item);
+///       acc
+///     }
+///   )(s)
+/// }
+///
+///
+/// assert_eq!(parser("abcabcabcabc"), Ok(("", vec!["abc", "abc", "abc", "abc"])));
+/// ```
 #[cfg(feature = "alloc")]
 #[cfg_attr(feature = "docsrs", doc(cfg(feature = "alloc")))]
-pub fn many<I, O, E, F, G>(range: G, mut parse: F) -> impl FnMut(I) -> IResult<I, Vec<O>, E>
+pub fn many<I, O, E, Collection, F, G>(
+  range: G,
+  mut parse: F,
+) -> impl FnMut(I) -> IResult<I, Collection, E>
 where
   I: Clone + InputLength,
   F: Parser<I, O, E>,
+  Collection: Extend<O> + Default,
   E: ParseError<I>,
   G: NomRange<usize>,
 {
-  let capacity = match range.bounds() {
-    (Bound::Included(start), _) => start,
-    (Bound::Excluded(start), _) => start + 1,
-    _ => 4,
-  };
-
   move |mut input: I| {
     if range.is_inverted() {
       return Err(Err::Failure(E::from_error_kind(input, ErrorKind::Many)));
     }
 
-    let max_initial_capacity =
-      MAX_INITIAL_CAPACITY_BYTES / crate::lib::std::mem::size_of::<O>().max(1);
-    let mut res = crate::lib::std::vec::Vec::with_capacity(capacity.min(max_initial_capacity));
+    let mut res = Collection::default();
 
     for count in range.bounded_iter() {
       let len = input.input_len();
@@ -1111,7 +1163,7 @@ where
             return Err(Err::Error(E::from_error_kind(input, ErrorKind::Many)));
           }
 
-          res.push(value);
+          res.extend(Some(value));
           input = tail;
         }
         Err(Err::Error(e)) => {
diff --git a/src/str.rs b/src/str.rs
index 1ee7cef9f..93d4c164c 100644
--- a/src/str.rs
+++ b/src/str.rs
@@ -487,11 +487,13 @@ mod test {
   #[test]
   #[cfg(feature = "alloc")]
   fn recognize_is_a() {
+    use crate::lib::std::vec::Vec;
+
     let a = "aabbab";
     let b = "ababcd";
 
     fn f(i: &str) -> IResult<&str, &str> {
-      recognize(many(1.., alt((tag("a"), tag("b")))))(i)
+      recognize::<_, Vec<&str>, _, _>(many(1.., alt((tag("a"), tag("b")))))(i)
     }
 
     assert_eq!(f(a), Ok((&a[6..], a)));


Test patch:
diff --git a/tests/fnmut.rs b/tests/fnmut.rs
index 995faefdf..976a47d7b 100644
--- a/tests/fnmut.rs
+++ b/tests/fnmut.rs
@@ -8,7 +8,7 @@ fn parse() {
   let mut counter = 0;
 
   let res = {
-    let mut parser = many::<_, _, (), _, _>(0.., |i| {
+    let mut parser = many::<_, _, (), Vec<&str>, _, _>(0.., |i| {
       counter += 1;
       tag("abc")(i)
     });
diff --git a/tests/ini.rs b/tests/ini.rs
index 4bd06085f..585bfeca3 100644
--- a/tests/ini.rs
+++ b/tests/ini.rs
@@ -28,9 +28,7 @@ fn key_value(i: &[u8]) -> IResult<&[u8], (&str, &str)> {
 }
 
 fn keys_and_values(i: &[u8]) -> IResult<&[u8], HashMap<&str, &str>> {
-  map(many(0.., terminated(key_value, opt(multispace))), |vec| {
-    vec.into_iter().collect()
-  })(i)
+  many(0.., terminated(key_value, opt(multispace)))(i)
 }
 
 fn category_and_keys(i: &[u8]) -> IResult<&[u8], (&str, HashMap<&str, &str>)> {
diff --git a/tests/issues.rs b/tests/issues.rs
index 8728e9dfb..80d3e4e2e 100644
--- a/tests/issues.rs
+++ b/tests/issues.rs
@@ -172,7 +172,7 @@ fn issue_942() {
 fn issue_many_m_n_with_zeros() {
   use nom::character::complete::char;
   use nom::multi::many;
-  let mut parser = many::<_, _, (), _, _>(0..=0, char('a'));
+  let mut parser = many::<_, _, (), Vec<char>, _, _>(0..=0, char('a'));
   assert_eq!(parser("aaa"), Ok(("aaa", vec!())));
 }