Merging upstream version 1.76.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 406 insertions, 329 deletions

diff --git a/vendor/itertools/src/adaptors/mod.rs b/vendor/itertools/src/adaptors/mod.rs
index 1695bbd65..e925db51d 100644
--- a/vendor/itertools/src/adaptors/mod.rs
+++ b/vendor/itertools/src/adaptors/mod.rs
@@ -8,16 +8,16 @@ mod coalesce;
 mod map;
 mod multi_product;
 pub use self::coalesce::*;
-pub use self::map::{map_into, map_ok, MapInto, MapOk};
 #[allow(deprecated)]
 pub use self::map::MapResults;
+pub use self::map::{map_into, map_ok, MapInto, MapOk};
 #[cfg(feature = "use_alloc")]
 pub use self::multi_product::*;
 
+use crate::size_hint::{self, SizeHint};
 use std::fmt;
-use std::iter::{Fuse, Peekable, FromIterator, FusedIterator};
+use std::iter::{FromIterator, Fuse, FusedIterator};
 use std::marker::PhantomData;
-use crate::size_hint;
 
 /// An iterator adaptor that alternates elements from two iterators until both
 /// run out.
@@ -36,9 +36,13 @@ pub struct Interleave<I, J> {
 /// Create an iterator that interleaves elements in `i` and `j`.
 ///
 /// [`IntoIterator`] enabled version of `[Itertools::interleave]`.
-pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
-    where I: IntoIterator,
-          J: IntoIterator<Item = I::Item>
+pub fn interleave<I, J>(
+    i: I,
+    j: J,
+) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
+where
+    I: IntoIterator,
+    J: IntoIterator<Item = I::Item>,
 {
     Interleave {
         a: i.into_iter().fuse(),
@@ -48,8 +52,9 @@ pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter,
 }
 
 impl<I, J> Iterator for Interleave<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
+where
+    I: Iterator,
+    J: Iterator<Item = I::Item>,
 {
     type Item = I::Item;
     #[inline]
@@ -74,9 +79,11 @@ impl<I, J> Iterator for Interleave<I, J>
 }
 
 impl<I, J> FusedIterator for Interleave<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
-{}
+where
+    I: Iterator,
+    J: Iterator<Item = I::Item>,
+{
+}
 
 /// An iterator adaptor that alternates elements from the two iterators until
 /// one of them runs out.
@@ -88,8 +95,9 @@ impl<I, J> FusedIterator for Interleave<I, J>
 #[derive(Clone, Debug)]
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct InterleaveShortest<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
+where
+    I: Iterator,
+    J: Iterator<Item = I::Item>,
 {
     it0: I,
     it1: J,
@@ -98,8 +106,9 @@ pub struct InterleaveShortest<I, J>
 
 /// Create a new `InterleaveShortest` iterator.
 pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
+where
+    I: Iterator,
+    J: Iterator<Item = I::Item>,
 {
     InterleaveShortest {
         it0: a,
@@ -109,14 +118,19 @@ pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J>
 }
 
 impl<I, J> Iterator for InterleaveShortest<I, J>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
+where
+    I: Iterator,
+    J: Iterator<Item = I::Item>,
 {
     type Item = I::Item;
 
     #[inline]
     fn next(&mut self) -> Option<Self::Item> {
-        let e = if self.phase { self.it1.next() } else { self.it0.next() };
+        let e = if self.phase {
+            self.it1.next()
+        } else {
+            self.it0.next()
+        };
         if e.is_some() {
             self.phase = !self.phase;
         }
@@ -138,12 +152,11 @@ impl<I, J> Iterator for InterleaveShortest<I, J>
         let (next_lower, next_upper) = next_hint;
         let (combined_lower, combined_upper) =
             size_hint::mul_scalar(size_hint::min(curr_hint, next_hint), 2);
-        let lower =
-            if curr_lower > next_lower {
-                combined_lower + 1
-            } else {
-                combined_lower
-            };
+        let lower = if curr_lower > next_lower {
+            combined_lower + 1
+        } else {
+            combined_lower
+        };
         let upper = {
             let extra_elem = match (curr_upper, next_upper) {
                 (_, None) => false,
@@ -161,17 +174,21 @@ impl<I, J> Iterator for InterleaveShortest<I, J>
 }
 
 impl<I, J> FusedIterator for InterleaveShortest<I, J>
-    where I: FusedIterator,
-          J: FusedIterator<Item = I::Item>
-{}
+where
+    I: FusedIterator,
+    J: FusedIterator<Item = I::Item>,
+{
+}
 
 #[derive(Clone, Debug)]
 /// An iterator adaptor that allows putting back a single
 /// item to the front of the iterator.
 ///
 /// Iterator element type is `I::Item`.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct PutBack<I>
-    where I: Iterator
+where
+    I: Iterator,
 {
     top: Option<I::Item>,
     iter: I,
@@ -179,7 +196,8 @@ pub struct PutBack<I>
 
 /// Create an iterator where you can put back a single item
 pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter>
-    where I: IntoIterator
+where
+    I: IntoIterator,
 {
     PutBack {
         top: None,
@@ -188,7 +206,8 @@ pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter>
 }
 
 impl<I> PutBack<I>
-    where I: Iterator
+where
+    I: Iterator,
 {
     /// put back value `value` (builder method)
     pub fn with_value(mut self, value: I::Item) -> Self {
@@ -199,7 +218,7 @@ impl<I> PutBack<I>
     /// Split the `PutBack` into its parts.
     #[inline]
     pub fn into_parts(self) -> (Option<I::Item>, I) {
-        let PutBack{top, iter} = self;
+        let PutBack { top, iter } = self;
         (top, iter)
     }
 
@@ -213,7 +232,8 @@ impl<I> PutBack<I>
 }
 
 impl<I> Iterator for PutBack<I>
-    where I: Iterator
+where
+    I: Iterator,
 {
     type Item = I::Item;
     #[inline]
@@ -252,7 +272,8 @@ impl<I> Iterator for PutBack<I>
     }
 
     fn all<G>(&mut self, mut f: G) -> bool
-        where G: FnMut(Self::Item) -> bool
+    where
+        G: FnMut(Self::Item) -> bool,
     {
         if let Some(elt) = self.top.take() {
             if !f(elt) {
@@ -263,7 +284,8 @@ impl<I> Iterator for PutBack<I>
     }
 
     fn fold<Acc, G>(mut self, init: Acc, mut f: G) -> Acc
-        where G: FnMut(Acc, Self::Item) -> Acc,
+    where
+        G: FnMut(Acc, Self::Item) -> Acc,
     {
         let mut accum = init;
         if let Some(elt) = self.top.take() {
@@ -282,10 +304,14 @@ impl<I> Iterator for PutBack<I>
 /// See [`.cartesian_product()`](crate::Itertools::cartesian_product) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct Product<I, J>
-    where I: Iterator
+where
+    I: Iterator,
 {
     a: I,
-    a_cur: Option<I::Item>,
+    /// `a_cur` is `None` while no item have been taken out of `a` (at definition).
+    /// Then `a_cur` will be `Some(Some(item))` until `a` is exhausted,
+    /// in which case `a_cur` will be `Some(None)`.
+    a_cur: Option<Option<I::Item>>,
     b: J,
     b_orig: J,
 }
@@ -293,13 +319,14 @@ pub struct Product<I, J>
 /// Create a new cartesian product iterator
 ///
 /// Iterator element type is `(I::Item, J::Item)`.
-pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J>
-    where I: Iterator,
-          J: Clone + Iterator,
-          I::Item: Clone
+pub fn cartesian_product<I, J>(i: I, j: J) -> Product<I, J>
+where
+    I: Iterator,
+    J: Clone + Iterator,
+    I::Item: Clone,
 {
     Product {
-        a_cur: i.next(),
+        a_cur: None,
         a: i,
         b: j.clone(),
         b_orig: j,
@@ -307,54 +334,69 @@ pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J>
 }
 
 impl<I, J> Iterator for Product<I, J>
-    where I: Iterator,
-          J: Clone + Iterator,
-          I::Item: Clone
+where
+    I: Iterator,
+    J: Clone + Iterator,
+    I::Item: Clone,
 {
     type Item = (I::Item, J::Item);
 
     fn next(&mut self) -> Option<Self::Item> {
-        let elt_b = match self.b.next() {
+        let Self {
+            a,
+            a_cur,
+            b,
+            b_orig,
+        } = self;
+        let elt_b = match b.next() {
             None => {
-                self.b = self.b_orig.clone();
-                match self.b.next() {
+                *b = b_orig.clone();
+                match b.next() {
                     None => return None,
                     Some(x) => {
-                        self.a_cur = self.a.next();
+                        *a_cur = Some(a.next());
                         x
                     }
                 }
             }
-            Some(x) => x
+            Some(x) => x,
         };
-        self.a_cur.as_ref().map(|a| (a.clone(), elt_b))
+        a_cur
+            .get_or_insert_with(|| a.next())
+            .as_ref()
+            .map(|a| (a.clone(), elt_b))
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let has_cur = self.a_cur.is_some() as usize;
         // Not ExactSizeIterator because size may be larger than usize
-        let (b_min, b_max) = self.b.size_hint();
-
         // Compute a * b_orig + b for both lower and upper bound
-        size_hint::add(
-            size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()),
-            (b_min * has_cur, b_max.map(move |x| x * has_cur)))
+        let mut sh = size_hint::mul(self.a.size_hint(), self.b_orig.size_hint());
+        if matches!(self.a_cur, Some(Some(_))) {
+            sh = size_hint::add(sh, self.b.size_hint());
+        }
+        sh
     }
 
-    fn fold<Acc, G>(mut self, mut accum: Acc, mut f: G) -> Acc
-        where G: FnMut(Acc, Self::Item) -> Acc,
+    fn fold<Acc, G>(self, mut accum: Acc, mut f: G) -> Acc
+    where
+        G: FnMut(Acc, Self::Item) -> Acc,
     {
         // use a split loop to handle the loose a_cur as well as avoiding to
         // clone b_orig at the end.
-        if let Some(mut a) = self.a_cur.take() {
-            let mut b = self.b;
+        let Self {
+            mut a,
+            a_cur,
+            mut b,
+            b_orig,
+        } = self;
+        if let Some(mut elt_a) = a_cur.unwrap_or_else(|| a.next()) {
             loop {
-                accum = b.fold(accum, |acc, elt| f(acc, (a.clone(), elt)));
+                accum = b.fold(accum, |acc, elt| f(acc, (elt_a.clone(), elt)));
 
                 // we can only continue iterating a if we had a first element;
-                if let Some(next_a) = self.a.next() {
-                    b = self.b_orig.clone();
-                    a = next_a;
+                if let Some(next_elt_a) = a.next() {
+                    b = b_orig.clone();
+                    elt_a = next_elt_a;
                 } else {
                     break;
                 }
@@ -365,10 +407,12 @@ impl<I, J> Iterator for Product<I, J>
 }
 
 impl<I, J> FusedIterator for Product<I, J>
-    where I: FusedIterator,
-          J: Clone + FusedIterator,
-          I::Item: Clone
-{}
+where
+    I: FusedIterator,
+    J: Clone + FusedIterator,
+    I::Item: Clone,
+{
+}
 
 /// A “meta iterator adaptor”. Its closure receives a reference to the iterator
 /// and may pick off as many elements as it likes, to produce the next iterator element.
@@ -383,7 +427,10 @@ pub struct Batching<I, F> {
     iter: I,
 }
 
-impl<I, F> fmt::Debug for Batching<I, F> where I: fmt::Debug {
+impl<I, F> fmt::Debug for Batching<I, F>
+where
+    I: fmt::Debug,
+{
     debug_fmt_fields!(Batching, iter);
 }
 
@@ -393,8 +440,9 @@ pub fn batching<I, F>(iter: I, f: F) -> Batching<I, F> {
 }
 
 impl<B, F, I> Iterator for Batching<I, F>
-    where I: Iterator,
-          F: FnMut(&mut I) -> Option<B>
+where
+    I: Iterator,
+    F: FnMut(&mut I) -> Option<B>,
 {
     type Item = B;
     #[inline]
@@ -410,7 +458,7 @@ impl<B, F, I> Iterator for Batching<I, F>
 /// then skipping forward *n-1* elements.
 ///
 /// See [`.step()`](crate::Itertools::step) for more information.
-#[deprecated(note="Use std .step_by() instead", since="0.8.0")]
+#[deprecated(note = "Use std .step_by() instead", since = "0.8.0")]
 #[allow(deprecated)]
 #[derive(Clone, Debug)]
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
@@ -424,7 +472,8 @@ pub struct Step<I> {
 /// **Panics** if the step is 0.
 #[allow(deprecated)]
 pub fn step<I>(iter: I, step: usize) -> Step<I>
-    where I: Iterator
+where
+    I: Iterator,
 {
     assert!(step != 0);
     Step {
@@ -435,7 +484,8 @@ pub fn step<I>(iter: I, step: usize) -> Step<I>
 
 #[allow(deprecated)]
 impl<I> Iterator for Step<I>
-    where I: Iterator
+where
+    I: Iterator,
 {
     type Item = I::Item;
     #[inline]
@@ -462,145 +512,7 @@ impl<I> Iterator for Step<I>
 
 // known size
 #[allow(deprecated)]
-impl<I> ExactSizeIterator for Step<I>
-    where I: ExactSizeIterator
-{}
-
-pub trait MergePredicate<T> {
-    fn merge_pred(&mut self, a: &T, b: &T) -> bool;
-}
-
-#[derive(Clone, Debug)]
-pub struct MergeLte;
-
-impl<T: PartialOrd> MergePredicate<T> for MergeLte {
-    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
-        a <= b
-    }
-}
-
-/// An iterator adaptor that merges the two base iterators in ascending order.
-/// If both base iterators are sorted (ascending), the result is sorted.
-///
-/// Iterator element type is `I::Item`.
-///
-/// See [`.merge()`](crate::Itertools::merge_by) for more information.
-pub type Merge<I, J> = MergeBy<I, J, MergeLte>;
-
-/// Create an iterator that merges elements in `i` and `j`.
-///
-/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge).
-///
-/// ```
-/// use itertools::merge;
-///
-/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
-///     /* loop body */
-/// }
-/// ```
-pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
-    where I: IntoIterator,
-          J: IntoIterator<Item = I::Item>,
-          I::Item: PartialOrd
-{
-    merge_by_new(i, j, MergeLte)
-}
-
-/// An iterator adaptor that merges the two base iterators in ascending order.
-/// If both base iterators are sorted (ascending), the result is sorted.
-///
-/// Iterator element type is `I::Item`.
-///
-/// See [`.merge_by()`](crate::Itertools::merge_by) for more information.
-#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct MergeBy<I, J, F>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>
-{
-    a: Peekable<I>,
-    b: Peekable<J>,
-    fused: Option<bool>,
-    cmp: F,
-}
-
-impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
-    where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug,
-          I::Item: fmt::Debug,
-{
-    debug_fmt_fields!(MergeBy, a, b);
-}
-
-impl<T, F: FnMut(&T, &T)->bool> MergePredicate<T> for F {
-    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
-        self(a, b)
-    }
-}
-
-/// Create a `MergeBy` iterator.
-pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F>
-    where I: IntoIterator,
-          J: IntoIterator<Item = I::Item>,
-          F: MergePredicate<I::Item>,
-{
-    MergeBy {
-        a: a.into_iter().peekable(),
-        b: b.into_iter().peekable(),
-        fused: None,
-        cmp,
-    }
-}
-
-impl<I, J, F> Clone for MergeBy<I, J, F>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>,
-          Peekable<I>: Clone,
-          Peekable<J>: Clone,
-          F: Clone
-{
-    clone_fields!(a, b, fused, cmp);
-}
-
-impl<I, J, F> Iterator for MergeBy<I, J, F>
-    where I: Iterator,
-          J: Iterator<Item = I::Item>,
-          F: MergePredicate<I::Item>
-{
-    type Item = I::Item;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        let less_than = match self.fused {
-            Some(lt) => lt,
-            None => match (self.a.peek(), self.b.peek()) {
-                (Some(a), Some(b)) => self.cmp.merge_pred(a, b),
-                (Some(_), None) => {
-                    self.fused = Some(true);
-                    true
-                }
-                (None, Some(_)) => {
-                    self.fused = Some(false);
-                    false
-                }
-                (None, None) => return None,
-            }
-        };
-        if less_than {
-            self.a.next()
-        } else {
-            self.b.next()
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        // Not ExactSizeIterator because size may be larger than usize
-        size_hint::add(self.a.size_hint(), self.b.size_hint())
-    }
-}
-
-impl<I, J, F> FusedIterator for MergeBy<I, J, F>
-    where I: FusedIterator,
-          J: FusedIterator<Item = I::Item>,
-          F: MergePredicate<I::Item>
-{}
+impl<I> ExactSizeIterator for Step<I> where I: ExactSizeIterator {}
 
 /// An iterator adaptor that borrows from a `Clone`-able iterator
 /// to only pick off elements while the predicate returns `true`.
@@ -613,21 +525,24 @@ pub struct TakeWhileRef<'a, I: 'a, F> {
 }
 
 impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F>
-    where I: Iterator + fmt::Debug,
+where
+    I: Iterator + fmt::Debug,
 {
     debug_fmt_fields!(TakeWhileRef, iter);
 }
 
 /// Create a new `TakeWhileRef` from a reference to clonable iterator.
 pub fn take_while_ref<I, F>(iter: &mut I, f: F) -> TakeWhileRef<I, F>
-    where I: Iterator + Clone
+where
+    I: Iterator + Clone,
 {
     TakeWhileRef { iter, f }
 }
 
 impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F>
-    where I: Iterator + Clone,
-          F: FnMut(&I::Item) -> bool
+where
+    I: Iterator + Clone,
+    F: FnMut(&I::Item) -> bool,
 {
     type Item = I::Item;
 
@@ -667,7 +582,8 @@ pub fn while_some<I>(iter: I) -> WhileSome<I> {
 }
 
 impl<I, A> Iterator for WhileSome<I>
-    where I: Iterator<Item = Option<A>>
+where
+    I: Iterator<Item = Option<A>>,
 {
     type Item = A;
 
@@ -681,6 +597,22 @@ impl<I, A> Iterator for WhileSome<I>
     fn size_hint(&self) -> (usize, Option<usize>) {
         (0, self.iter.size_hint().1)
     }
+
+    fn fold<B, F>(mut self, acc: B, mut f: F) -> B
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> B,
+    {
+        let res = self.iter.try_fold(acc, |acc, item| match item {
+            Some(item) => Ok(f(acc, item)),
+            None => Err(acc),
+        });
+        let res = match res {
+            Ok(val) => val,
+            Err(val) => val,
+        };
+        res
+    }
 }
 
 /// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples
@@ -691,8 +623,9 @@ impl<I, A> Iterator for WhileSome<I>
 #[derive(Clone, Debug)]
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct TupleCombinations<I, T>
-    where I: Iterator,
-          T: HasCombination<I>
+where
+    I: Iterator,
+    T: HasCombination<I>,
 {
     iter: T::Combination,
     _mi: PhantomData<I>,
@@ -704,9 +637,10 @@ pub trait HasCombination<I>: Sized {
 
 /// Create a new `TupleCombinations` from a clonable iterator.
 pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T>
-    where I: Iterator + Clone,
-          I::Item: Clone,
-          T: HasCombination<I>,
+where
+    I: Iterator + Clone,
+    I::Item: Clone,
+    T: HasCombination<I>,
 {
     TupleCombinations {
         iter: T::Combination::from(iter),
@@ -715,20 +649,38 @@ pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T>
 }
 
 impl<I, T> Iterator for TupleCombinations<I, T>
-    where I: Iterator,
-          T: HasCombination<I>,
+where
+    I: Iterator,
+    T: HasCombination<I>,
 {
     type Item = T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.iter.next()
     }
+
+    fn size_hint(&self) -> SizeHint {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn fold<B, F>(self, init: B, f: F) -> B
+    where
+        F: FnMut(B, Self::Item) -> B,
+    {
+        self.iter.fold(init, f)
+    }
 }
 
 impl<I, T> FusedIterator for TupleCombinations<I, T>
-    where I: FusedIterator,
-          T: HasCombination<I>,
-{}
+where
+    I: FusedIterator,
+    T: HasCombination<I>,
+{
+}
 
 #[derive(Clone, Debug)]
 pub struct Tuple1Combination<I> {
@@ -747,6 +699,21 @@ impl<I: Iterator> Iterator for Tuple1Combination<I> {
     fn next(&mut self) -> Option<Self::Item> {
         self.iter.next().map(|x| (x,))
     }
+
+    fn size_hint(&self) -> SizeHint {
+        self.iter.size_hint()
+    }
+
+    fn count(self) -> usize {
+        self.iter.count()
+    }
+
+    fn fold<B, F>(self, init: B, f: F) -> B
+    where
+        F: FnMut(B, Self::Item) -> B,
+    {
+        self.iter.map(|x| (x,)).fold(init, f)
+    }
 }
 
 impl<I: Iterator> HasCombination<I> for (I::Item,) {
@@ -780,22 +747,55 @@ macro_rules! impl_tuple_combination {
 
         impl<I, A> Iterator for $C<I>
             where I: Iterator<Item = A> + Clone,
-                  I::Item: Clone
+                  A: Clone,
         {
             type Item = (A, $(ignore_ident!($X, A)),*);
 
             fn next(&mut self) -> Option<Self::Item> {
-                if let Some(($($X),*,)) = self.c.next() {
+                if let Some(($($X,)*)) = self.c.next() {
                     let z = self.item.clone().unwrap();
                     Some((z, $($X),*))
                 } else {
                     self.item = self.iter.next();
                     self.item.clone().and_then(|z| {
                         self.c = self.iter.clone().into();
-                        self.c.next().map(|($($X),*,)| (z, $($X),*))
+                        self.c.next().map(|($($X,)*)| (z, $($X),*))
                     })
                 }
             }
+
+            fn size_hint(&self) -> SizeHint {
+                const K: usize = 1 + count_ident!($($X)*);
+                let (mut n_min, mut n_max) = self.iter.size_hint();
+                n_min = checked_binomial(n_min, K).unwrap_or(usize::MAX);
+                n_max = n_max.and_then(|n| checked_binomial(n, K));
+                size_hint::add(self.c.size_hint(), (n_min, n_max))
+            }
+
+            fn count(self) -> usize {
+                const K: usize = 1 + count_ident!($($X)*);
+                let n = self.iter.count();
+                checked_binomial(n, K).unwrap() + self.c.count()
+            }
+
+            fn fold<B, F>(self, mut init: B, mut f: F) -> B
+            where
+                F: FnMut(B, Self::Item) -> B,
+            {
+                let Self { c, item, mut iter } = self;
+                if let Some(z) = item.as_ref() {
+                    init = c
+                        .map(|($($X,)*)| (z.clone(), $($X),*))
+                        .fold(init, &mut f);
+                }
+                while let Some(z) = iter.next() {
+                    let c: $P<I> = iter.clone().into();
+                    init = c
+                        .map(|($($X,)*)| (z.clone(), $($X),*))
+                        .fold(init, &mut f);
+                }
+                init
+            }
         }
 
         impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*)
@@ -831,6 +831,42 @@ impl_tuple_combination!(Tuple10Combination Tuple9Combination; a b c d e f g h i)
 impl_tuple_combination!(Tuple11Combination Tuple10Combination; a b c d e f g h i j);
 impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i j k);
 
+// https://en.wikipedia.org/wiki/Binomial_coefficient#In_programming_languages
+pub(crate) fn checked_binomial(mut n: usize, mut k: usize) -> Option<usize> {
+    if n < k {
+        return Some(0);
+    }
+    // `factorial(n) / factorial(n - k) / factorial(k)` but trying to avoid it overflows:
+    k = (n - k).min(k); // symmetry
+    let mut c = 1;
+    for i in 1..=k {
+        c = (c / i)
+            .checked_mul(n)?
+            .checked_add((c % i).checked_mul(n)? / i)?;
+        n -= 1;
+    }
+    Some(c)
+}
+
+#[test]
+fn test_checked_binomial() {
+    // With the first row: [1, 0, 0, ...] and the first column full of 1s, we check
+    // row by row the recurrence relation of binomials (which is an equivalent definition).
+    // For n >= 1 and k >= 1 we have:
+    //   binomial(n, k) == binomial(n - 1, k - 1) + binomial(n - 1, k)
+    const LIMIT: usize = 500;
+    let mut row = vec![Some(0); LIMIT + 1];
+    row[0] = Some(1);
+    for n in 0..=LIMIT {
+        for k in 0..=LIMIT {
+            assert_eq!(row[k], checked_binomial(n, k));
+        }
+        row = std::iter::once(Some(1))
+            .chain((1..=LIMIT).map(|k| row[k - 1]?.checked_add(row[k]?)))
+            .collect();
+    }
+}
+
 /// An iterator adapter to filter values within a nested `Result::Ok`.
 ///
 /// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information.
@@ -838,7 +874,7 @@ impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct FilterOk<I, F> {
     iter: I,
-    f: F
+    f: F,
 }
 
 impl<I, F> fmt::Debug for FilterOk<I, F>
@@ -850,18 +886,17 @@ where
 
 /// Create a new `FilterOk` iterator.
 pub fn filter_ok<I, F, T, E>(iter: I, f: F) -> FilterOk<I, F>
-    where I: Iterator<Item = Result<T, E>>,
-          F: FnMut(&T) -> bool,
+where
+    I: Iterator<Item = Result<T, E>>,
+    F: FnMut(&T) -> bool,
 {
-    FilterOk {
-        iter,
-        f,
-    }
+    FilterOk { iter, f }
 }
 
 impl<I, F, T, E> Iterator for FilterOk<I, F>
-    where I: Iterator<Item = Result<T, E>>,
-          F: FnMut(&T) -> bool,
+where
+    I: Iterator<Item = Result<T, E>>,
+    F: FnMut(&T) -> bool,
 {
     type Item = Result<T, E>;
 
@@ -872,7 +907,7 @@ impl<I, F, T, E> Iterator for FilterOk<I, F>
                     if (self.f)(&v) {
                         return Some(Ok(v));
                     }
-                },
+                }
                 Some(Err(e)) => return Some(Err(e)),
                 None => return None,
             }
@@ -884,36 +919,41 @@ impl<I, F, T, E> Iterator for FilterOk<I, F>
     }
 
     fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
-        where Fold: FnMut(Acc, Self::Item) -> Acc,
+    where
+        Fold: FnMut(Acc, Self::Item) -> Acc,
     {
         let mut f = self.f;
-        self.iter.filter(|v| {
-            v.as_ref().map(&mut f).unwrap_or(true)
-        }).fold(init, fold_f)
+        self.iter
+            .filter(|v| v.as_ref().map(&mut f).unwrap_or(true))
+            .fold(init, fold_f)
     }
 
     fn collect<C>(self) -> C
-        where C: FromIterator<Self::Item>
+    where
+        C: FromIterator<Self::Item>,
     {
         let mut f = self.f;
-        self.iter.filter(|v| {
-            v.as_ref().map(&mut f).unwrap_or(true)
-        }).collect()
+        self.iter
+            .filter(|v| v.as_ref().map(&mut f).unwrap_or(true))
+            .collect()
     }
 }
 
 impl<I, F, T, E> FusedIterator for FilterOk<I, F>
-    where I: FusedIterator<Item = Result<T, E>>,
-          F: FnMut(&T) -> bool,
-{}
+where
+    I: FusedIterator<Item = Result<T, E>>,
+    F: FnMut(&T) -> bool,
+{
+}
 
 /// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`.
 ///
 /// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+#[derive(Clone)]
 pub struct FilterMapOk<I, F> {
     iter: I,
-    f: F
+    f: F,
 }
 
 impl<I, F> fmt::Debug for FilterMapOk<I, F>
@@ -933,18 +973,17 @@ fn transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>>
 
 /// Create a new `FilterOk` iterator.
 pub fn filter_map_ok<I, F, T, U, E>(iter: I, f: F) -> FilterMapOk<I, F>
-    where I: Iterator<Item = Result<T, E>>,
-          F: FnMut(T) -> Option<U>,
+where
+    I: Iterator<Item = Result<T, E>>,
+    F: FnMut(T) -> Option<U>,
 {
-    FilterMapOk {
-        iter,
-        f,
-    }
+    FilterMapOk { iter, f }
 }
 
 impl<I, F, T, U, E> Iterator for FilterMapOk<I, F>
-    where I: Iterator<Item = Result<T, E>>,
-          F: FnMut(T) -> Option<U>,
+where
+    I: Iterator<Item = Result<T, E>>,
+    F: FnMut(T) -> Option<U>,
 {
     type Item = Result<U, E>;
 
@@ -955,7 +994,7 @@ impl<I, F, T, U, E> Iterator for FilterMapOk<I, F>
                     if let Some(v) = (self.f)(v) {
                         return Some(Ok(v));
                     }
-                },
+                }
                 Some(Err(e)) => return Some(Err(e)),
                 None => return None,
             }
@@ -967,28 +1006,32 @@ impl<I, F, T, U, E> Iterator for FilterMapOk<I, F>
     }
 
     fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
-        where Fold: FnMut(Acc, Self::Item) -> Acc,
+    where
+        Fold: FnMut(Acc, Self::Item) -> Acc,
     {
         let mut f = self.f;
-        self.iter.filter_map(|v| {
-            transpose_result(v.map(&mut f))
-        }).fold(init, fold_f)
+        self.iter
+            .filter_map(|v| transpose_result(v.map(&mut f)))
+            .fold(init, fold_f)
     }
 
     fn collect<C>(self) -> C
-        where C: FromIterator<Self::Item>
+    where
+        C: FromIterator<Self::Item>,
     {
         let mut f = self.f;
-        self.iter.filter_map(|v| {
-            transpose_result(v.map(&mut f))
-        }).collect()
+        self.iter
+            .filter_map(|v| transpose_result(v.map(&mut f)))
+            .collect()
     }
 }
 
 impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F>
-    where I: FusedIterator<Item = Result<T, E>>,
-          F: FnMut(T) -> Option<U>,
-{}
+where
+    I: FusedIterator<Item = Result<T, E>>,
+    F: FnMut(T) -> Option<U>,
+{
+}
 
 /// An iterator adapter to get the positions of each element that matches a predicate.
 ///
@@ -1010,19 +1053,17 @@ where
 
 /// Create a new `Positions` iterator.
 pub fn positions<I, F>(iter: I, f: F) -> Positions<I, F>
-    where I: Iterator,
-          F: FnMut(I::Item) -> bool,
+where
+    I: Iterator,
+    F: FnMut(I::Item) -> bool,
 {
-    Positions {
-        iter,
-        f,
-        count: 0
-    }
+    Positions { iter, f, count: 0 }
 }
 
 impl<I, F> Iterator for Positions<I, F>
-    where I: Iterator,
-          F: FnMut(I::Item) -> bool,
+where
+    I: Iterator,
+    F: FnMut(I::Item) -> bool,
 {
     type Item = usize;
 
@@ -1043,13 +1084,14 @@ impl<I, F> Iterator for Positions<I, F>
 }
 
 impl<I, F> DoubleEndedIterator for Positions<I, F>
-    where I: DoubleEndedIterator + ExactSizeIterator,
-          F: FnMut(I::Item) -> bool,
+where
+    I: DoubleEndedIterator + ExactSizeIterator,
+    F: FnMut(I::Item) -> bool,
 {
     fn next_back(&mut self) -> Option<Self::Item> {
         while let Some(v) = self.iter.next_back() {
             if (self.f)(v) {
-                return Some(self.count + self.iter.len())
+                return Some(self.count + self.iter.len());
             }
         }
         None
@@ -1057,9 +1099,11 @@ impl<I, F> DoubleEndedIterator for Positions<I, F>
 }
 
 impl<I, F> FusedIterator for Positions<I, F>
-    where I: FusedIterator,
-          F: FnMut(I::Item) -> bool,
-{}
+where
+    I: FusedIterator,
+    F: FnMut(I::Item) -> bool,
+{
+}
 
 /// An iterator adapter to apply a mutating function to each element before yielding it.
 ///
@@ -1108,18 +1152,28 @@ where
     }
 
     fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
-        where G: FnMut(Acc, Self::Item) -> Acc,
+    where
+        G: FnMut(Acc, Self::Item) -> Acc,
     {
         let mut f = self.f;
-        self.iter.fold(init, move |acc, mut v| { f(&mut v); g(acc, v) })
+        self.iter.fold(init, move |acc, mut v| {
+            f(&mut v);
+            g(acc, v)
+        })
     }
 
     // if possible, re-use inner iterator specializations in collect
     fn collect<C>(self) -> C
-        where C: FromIterator<Self::Item>
+    where
+        C: FromIterator<Self::Item>,
     {
         let mut f = self.f;
-        self.iter.map(move |mut v| { f(&mut v); v }).collect()
+        self.iter
+            .map(move |mut v| {
+                f(&mut v);
+                v
+            })
+            .collect()
     }
 }
 
@@ -1127,7 +1181,8 @@ impl<I, F> ExactSizeIterator for Update<I, F>
 where
     I: ExactSizeIterator,
     F: FnMut(&mut I::Item),
-{}
+{
+}
 
 impl<I, F> DoubleEndedIterator for Update<I, F>
 where
@@ -1148,4 +1203,5 @@ impl<I, F> FusedIterator for Update<I, F>
 where
     I: FusedIterator,
     F: FnMut(&mut I::Item),
-{}
+{
+}
diff --git a/vendor/itertools/src/adaptors/multi_product.rs b/vendor/itertools/src/adaptors/multi_product.rs
index 0b3840698..ef7fadba8 100644
--- a/vendor/itertools/src/adaptors/multi_product.rs
+++ b/vendor/itertools/src/adaptors/multi_product.rs
@@ -15,8 +15,9 @@ use alloc::vec::Vec;
 /// for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct MultiProduct<I>(Vec<MultiProductIter<I>>)
-    where I: Iterator + Clone,
-          I::Item: Clone;
+where
+    I: Iterator + Clone,
+    I::Item: Clone;
 
 impl<I> std::fmt::Debug for MultiProduct<I>
 where
@@ -31,19 +32,25 @@ where
 ///
 /// Iterator element is of type `Vec<H::Item::Item>`.
 pub fn multi_cartesian_product<H>(iters: H) -> MultiProduct<<H::Item as IntoIterator>::IntoIter>
-    where H: Iterator,
-          H::Item: IntoIterator,
-          <H::Item as IntoIterator>::IntoIter: Clone,
-          <H::Item as IntoIterator>::Item: Clone
+where
+    H: Iterator,
+    H::Item: IntoIterator,
+    <H::Item as IntoIterator>::IntoIter: Clone,
+    <H::Item as IntoIterator>::Item: Clone,
 {
-    MultiProduct(iters.map(|i| MultiProductIter::new(i.into_iter())).collect())
+    MultiProduct(
+        iters
+            .map(|i| MultiProductIter::new(i.into_iter()))
+            .collect(),
+    )
 }
 
 #[derive(Clone, Debug)]
 /// Holds the state of a single iterator within a `MultiProduct`.
 struct MultiProductIter<I>
-    where I: Iterator + Clone,
-          I::Item: Clone
+where
+    I: Iterator + Clone,
+    I::Item: Clone,
 {
     cur: Option<I::Item>,
     iter: I,
@@ -58,8 +65,9 @@ enum MultiProductIterState {
 }
 
 impl<I> MultiProduct<I>
-    where I: Iterator + Clone,
-          I::Item: Clone
+where
+    I: Iterator + Clone,
+    I::Item: Clone,
 {
     /// Iterates the rightmost iterator, then recursively iterates iterators
     /// to the left if necessary.
@@ -67,7 +75,7 @@ impl<I> MultiProduct<I>
     /// Returns true if the iteration succeeded, else false.
     fn iterate_last(
         multi_iters: &mut [MultiProductIter<I>],
-        mut state: MultiProductIterState
+        mut state: MultiProductIterState,
     ) -> bool {
         use self::MultiProductIterState::*;
 
@@ -77,8 +85,8 @@ impl<I> MultiProduct<I>
                     let on_first_iter = !last.in_progress();
                     state = MidIter { on_first_iter };
                     on_first_iter
-                },
-                MidIter { on_first_iter } => on_first_iter
+                }
+                MidIter { on_first_iter } => on_first_iter,
             };
 
             if !on_first_iter {
@@ -101,16 +109,17 @@ impl<I> MultiProduct<I>
             // At end of iteration (final iterator finishes), finish.
             match state {
                 StartOfIter => false,
-                MidIter { on_first_iter } => on_first_iter
+                MidIter { on_first_iter } => on_first_iter,
             }
         }
     }
 
     /// Returns the unwrapped value of the next iteration.
     fn curr_iterator(&self) -> Vec<I::Item> {
-        self.0.iter().map(|multi_iter| {
-            multi_iter.cur.clone().unwrap()
-        }).collect()
+        self.0
+            .iter()
+            .map(|multi_iter| multi_iter.cur.clone().unwrap())
+            .collect()
     }
 
     /// Returns true if iteration has started and has not yet finished; false
@@ -125,14 +134,15 @@ impl<I> MultiProduct<I>
 }
 
 impl<I> MultiProductIter<I>
-    where I: Iterator + Clone,
-          I::Item: Clone
+where
+    I: Iterator + Clone,
+    I::Item: Clone,
 {
     fn new(iter: I) -> Self {
         MultiProductIter {
             cur: None,
             iter: iter.clone(),
-            iter_orig: iter
+            iter_orig: iter,
         }
     }
 
@@ -154,16 +164,14 @@ impl<I> MultiProductIter<I>
 }
 
 impl<I> Iterator for MultiProduct<I>
-    where I: Iterator + Clone,
-          I::Item: Clone
+where
+    I: Iterator + Clone,
+    I::Item: Clone,
 {
     type Item = Vec<I::Item>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        if MultiProduct::iterate_last(
-            &mut self.0,
-            MultiProductIterState::StartOfIter
-        ) {
+        if MultiProduct::iterate_last(&mut self.0, MultiProductIterState::StartOfIter) {
             Some(self.curr_iterator())
         } else {
             None
@@ -176,18 +184,24 @@ impl<I> Iterator for MultiProduct<I>
         }
 
         if !self.in_progress() {
-            return self.0.into_iter().fold(1, |acc, multi_iter| {
-                acc * multi_iter.iter.count()
-            });
+            return self
+                .0
+                .into_iter()
+                .fold(1, |acc, multi_iter| acc * multi_iter.iter.count());
         }
 
         self.0.into_iter().fold(
             0,
-            |acc, MultiProductIter { iter, iter_orig, cur: _ }| {
+            |acc,
+             MultiProductIter {
+                 iter,
+                 iter_orig,
+                 cur: _,
+             }| {
                 let total_count = iter_orig.count();
                 let cur_count = iter.count();
                 acc * total_count + cur_count
-            }
+            },
         )
     }
 
@@ -205,18 +219,25 @@ impl<I> Iterator for MultiProduct<I>
 
         self.0.iter().fold(
             (0, Some(0)),
-            |acc, &MultiProductIter { ref iter, ref iter_orig, cur: _ }| {
+            |acc,
+             &MultiProductIter {
+                 ref iter,
+                 ref iter_orig,
+                 cur: _,
+             }| {
                 let cur_size = iter.size_hint();
                 let total_size = iter_orig.size_hint();
                 size_hint::add(size_hint::mul(acc, total_size), cur_size)
-            }
+            },
         )
     }
 
     fn last(self) -> Option<Self::Item> {
         let iter_count = self.0.len();
 
-        let lasts: Self::Item = self.0.into_iter()
+        let lasts: Self::Item = self
+            .0
+            .into_iter()
             .map(|multi_iter| multi_iter.iter.last())
             .while_some()
             .collect();