core/iter/adapters/
zip.rs

1use crate::cmp;
2use crate::fmt::{self, Debug};
3use crate::iter::{
4    FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen, UncheckedIterator,
5};
6use crate::num::NonZero;
7
8/// An iterator that iterates two other iterators simultaneously.
9///
10/// This `struct` is created by [`zip`] or [`Iterator::zip`].
11/// See their documentation for more.
12#[derive(Clone)]
13#[must_use = "iterators are lazy and do nothing unless consumed"]
14#[stable(feature = "rust1", since = "1.0.0")]
15pub struct Zip<A, B> {
16    a: A,
17    b: B,
18    // index, len and a_len are only used by the specialized version of zip
19    index: usize,
20    len: usize,
21    a_len: usize,
22}
23impl<A: Iterator, B: Iterator> Zip<A, B> {
24    pub(in crate::iter) fn new(a: A, b: B) -> Zip<A, B> {
25        ZipImpl::new(a, b)
26    }
27    fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> {
28        while let Some(x) = Iterator::next(self) {
29            if n == 0 {
30                return Some(x);
31            }
32            n -= 1;
33        }
34        None
35    }
36}
37
38/// Converts the arguments to iterators and zips them.
39///
40/// See the documentation of [`Iterator::zip`] for more.
41///
42/// # Examples
43///
44/// ```
45/// use std::iter::zip;
46///
47/// let xs = [1, 2, 3];
48/// let ys = [4, 5, 6];
49///
50/// let mut iter = zip(xs, ys);
51///
52/// assert_eq!(iter.next().unwrap(), (1, 4));
53/// assert_eq!(iter.next().unwrap(), (2, 5));
54/// assert_eq!(iter.next().unwrap(), (3, 6));
55/// assert!(iter.next().is_none());
56///
57/// // Nested zips are also possible:
58/// let zs = [7, 8, 9];
59///
60/// let mut iter = zip(zip(xs, ys), zs);
61///
62/// assert_eq!(iter.next().unwrap(), ((1, 4), 7));
63/// assert_eq!(iter.next().unwrap(), ((2, 5), 8));
64/// assert_eq!(iter.next().unwrap(), ((3, 6), 9));
65/// assert!(iter.next().is_none());
66/// ```
67#[stable(feature = "iter_zip", since = "1.59.0")]
68pub fn zip<A, B>(a: A, b: B) -> Zip<A::IntoIter, B::IntoIter>
69where
70    A: IntoIterator,
71    B: IntoIterator,
72{
73    ZipImpl::new(a.into_iter(), b.into_iter())
74}
75
76#[stable(feature = "rust1", since = "1.0.0")]
77impl<A, B> Iterator for Zip<A, B>
78where
79    A: Iterator,
80    B: Iterator,
81{
82    type Item = (A::Item, B::Item);
83
84    #[inline]
85    fn next(&mut self) -> Option<Self::Item> {
86        ZipImpl::next(self)
87    }
88
89    #[inline]
90    fn size_hint(&self) -> (usize, Option<usize>) {
91        ZipImpl::size_hint(self)
92    }
93
94    #[inline]
95    fn nth(&mut self, n: usize) -> Option<Self::Item> {
96        ZipImpl::nth(self, n)
97    }
98
99    #[inline]
100    fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
101    where
102        F: FnMut(Acc, Self::Item) -> Acc,
103    {
104        ZipImpl::fold(self, init, f)
105    }
106
107    #[inline]
108    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
109    where
110        Self: TrustedRandomAccessNoCoerce,
111    {
112        // SAFETY: `ZipImpl::__iterator_get_unchecked` has same safety
113        // requirements as `Iterator::__iterator_get_unchecked`.
114        unsafe { ZipImpl::get_unchecked(self, idx) }
115    }
116}
117
118#[stable(feature = "rust1", since = "1.0.0")]
119impl<A, B> DoubleEndedIterator for Zip<A, B>
120where
121    A: DoubleEndedIterator + ExactSizeIterator,
122    B: DoubleEndedIterator + ExactSizeIterator,
123{
124    #[inline]
125    fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
126        ZipImpl::next_back(self)
127    }
128}
129
130// Zip specialization trait
131#[doc(hidden)]
132trait ZipImpl<A, B> {
133    type Item;
134    fn new(a: A, b: B) -> Self;
135    fn next(&mut self) -> Option<Self::Item>;
136    fn size_hint(&self) -> (usize, Option<usize>);
137    fn nth(&mut self, n: usize) -> Option<Self::Item>;
138    fn next_back(&mut self) -> Option<Self::Item>
139    where
140        A: DoubleEndedIterator + ExactSizeIterator,
141        B: DoubleEndedIterator + ExactSizeIterator;
142    fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
143    where
144        F: FnMut(Acc, Self::Item) -> Acc;
145    // This has the same safety requirements as `Iterator::__iterator_get_unchecked`
146    unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
147    where
148        Self: Iterator + TrustedRandomAccessNoCoerce;
149}
150
151// Work around limitations of specialization, requiring `default` impls to be repeated
152// in intermediary impls.
153macro_rules! zip_impl_general_defaults {
154    () => {
155        default fn new(a: A, b: B) -> Self {
156            Zip {
157                a,
158                b,
159                index: 0, // unused
160                len: 0,   // unused
161                a_len: 0, // unused
162            }
163        }
164
165        #[inline]
166        default fn next(&mut self) -> Option<(A::Item, B::Item)> {
167            let x = self.a.next()?;
168            let y = self.b.next()?;
169            Some((x, y))
170        }
171
172        #[inline]
173        default fn nth(&mut self, n: usize) -> Option<Self::Item> {
174            self.super_nth(n)
175        }
176
177        #[inline]
178        default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
179        where
180            A: DoubleEndedIterator + ExactSizeIterator,
181            B: DoubleEndedIterator + ExactSizeIterator,
182        {
183            // The function body below only uses `self.a/b.len()` and `self.a/b.next_back()`
184            // and doesn’t call `next_back` too often, so this implementation is safe in
185            // the `TrustedRandomAccessNoCoerce` specialization
186
187            let a_sz = self.a.len();
188            let b_sz = self.b.len();
189            if a_sz != b_sz {
190                // Adjust a, b to equal length
191                if a_sz > b_sz {
192                    for _ in 0..a_sz - b_sz {
193                        self.a.next_back();
194                    }
195                } else {
196                    for _ in 0..b_sz - a_sz {
197                        self.b.next_back();
198                    }
199                }
200            }
201            match (self.a.next_back(), self.b.next_back()) {
202                (Some(x), Some(y)) => Some((x, y)),
203                (None, None) => None,
204                _ => unreachable!(),
205            }
206        }
207    };
208}
209
210// General Zip impl
211#[doc(hidden)]
212impl<A, B> ZipImpl<A, B> for Zip<A, B>
213where
214    A: Iterator,
215    B: Iterator,
216{
217    type Item = (A::Item, B::Item);
218
219    zip_impl_general_defaults! {}
220
221    #[inline]
222    default fn size_hint(&self) -> (usize, Option<usize>) {
223        let (a_lower, a_upper) = self.a.size_hint();
224        let (b_lower, b_upper) = self.b.size_hint();
225
226        let lower = cmp::min(a_lower, b_lower);
227
228        let upper = match (a_upper, b_upper) {
229            (Some(x), Some(y)) => Some(cmp::min(x, y)),
230            (Some(x), None) => Some(x),
231            (None, Some(y)) => Some(y),
232            (None, None) => None,
233        };
234
235        (lower, upper)
236    }
237
238    default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item
239    where
240        Self: TrustedRandomAccessNoCoerce,
241    {
242        unreachable!("Always specialized");
243    }
244
245    #[inline]
246    default fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
247    where
248        F: FnMut(Acc, Self::Item) -> Acc,
249    {
250        SpecFold::spec_fold(self, init, f)
251    }
252}
253
254#[doc(hidden)]
255impl<A, B> ZipImpl<A, B> for Zip<A, B>
256where
257    A: TrustedRandomAccessNoCoerce + Iterator,
258    B: TrustedRandomAccessNoCoerce + Iterator,
259{
260    zip_impl_general_defaults! {}
261
262    #[inline]
263    default fn size_hint(&self) -> (usize, Option<usize>) {
264        let size = cmp::min(self.a.size(), self.b.size());
265        (size, Some(size))
266    }
267
268    #[inline]
269    unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item {
270        let idx = self.index + idx;
271        // SAFETY: the caller must uphold the contract for
272        // `Iterator::__iterator_get_unchecked`.
273        unsafe { (self.a.__iterator_get_unchecked(idx), self.b.__iterator_get_unchecked(idx)) }
274    }
275
276    #[inline]
277    fn fold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
278    where
279        F: FnMut(Acc, Self::Item) -> Acc,
280    {
281        let mut accum = init;
282        let len = ZipImpl::size_hint(&self).0;
283        for i in 0..len {
284            // SAFETY: since Self: TrustedRandomAccessNoCoerce we can trust the size-hint to
285            // calculate the length and then use that to do unchecked iteration.
286            // fold consumes the iterator so we don't need to fixup any state.
287            unsafe {
288                accum = f(accum, self.get_unchecked(i));
289            }
290        }
291        accum
292    }
293}
294
295#[doc(hidden)]
296impl<A, B> ZipImpl<A, B> for Zip<A, B>
297where
298    A: TrustedRandomAccess + Iterator,
299    B: TrustedRandomAccess + Iterator,
300{
301    fn new(a: A, b: B) -> Self {
302        let a_len = a.size();
303        let len = cmp::min(a_len, b.size());
304        Zip { a, b, index: 0, len, a_len }
305    }
306
307    #[inline]
308    fn next(&mut self) -> Option<(A::Item, B::Item)> {
309        if self.index < self.len {
310            let i = self.index;
311            // since get_unchecked executes code which can panic we increment the counters beforehand
312            // so that the same index won't be accessed twice, as required by TrustedRandomAccess
313            self.index += 1;
314            // SAFETY: `i` is smaller than `self.len`, thus smaller than `self.a.len()` and `self.b.len()`
315            unsafe {
316                Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
317            }
318        } else if A::MAY_HAVE_SIDE_EFFECT && self.index < self.a_len {
319            let i = self.index;
320            // as above, increment before executing code that may panic
321            self.index += 1;
322            self.len += 1;
323            // match the base implementation's potential side effects
324            // SAFETY: we just checked that `i` < `self.a.len()`
325            unsafe {
326                self.a.__iterator_get_unchecked(i);
327            }
328            None
329        } else {
330            None
331        }
332    }
333
334    #[inline]
335    fn size_hint(&self) -> (usize, Option<usize>) {
336        let len = self.len - self.index;
337        (len, Some(len))
338    }
339
340    #[inline]
341    fn nth(&mut self, n: usize) -> Option<Self::Item> {
342        let delta = cmp::min(n, self.len - self.index);
343        let end = self.index + delta;
344        while self.index < end {
345            let i = self.index;
346            // since get_unchecked executes code which can panic we increment the counters beforehand
347            // so that the same index won't be accessed twice, as required by TrustedRandomAccess
348            self.index += 1;
349            if A::MAY_HAVE_SIDE_EFFECT {
350                // SAFETY: the usage of `cmp::min` to calculate `delta`
351                // ensures that `end` is smaller than or equal to `self.len`,
352                // so `i` is also smaller than `self.len`.
353                unsafe {
354                    self.a.__iterator_get_unchecked(i);
355                }
356            }
357            if B::MAY_HAVE_SIDE_EFFECT {
358                // SAFETY: same as above.
359                unsafe {
360                    self.b.__iterator_get_unchecked(i);
361                }
362            }
363        }
364
365        self.super_nth(n - delta)
366    }
367
368    #[inline]
369    fn next_back(&mut self) -> Option<(A::Item, B::Item)>
370    where
371        A: DoubleEndedIterator + ExactSizeIterator,
372        B: DoubleEndedIterator + ExactSizeIterator,
373    {
374        if A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT {
375            let sz_a = self.a.size();
376            let sz_b = self.b.size();
377            // Adjust a, b to equal length, make sure that only the first call
378            // of `next_back` does this, otherwise we will break the restriction
379            // on calls to `self.next_back()` after calling `get_unchecked()`.
380            if sz_a != sz_b {
381                let sz_a = self.a.size();
382                if A::MAY_HAVE_SIDE_EFFECT && sz_a > self.len {
383                    for _ in 0..sz_a - self.len {
384                        // since next_back() may panic we increment the counters beforehand
385                        // to keep Zip's state in sync with the underlying iterator source
386                        self.a_len -= 1;
387                        self.a.next_back();
388                    }
389                    debug_assert_eq!(self.a_len, self.len);
390                }
391                let sz_b = self.b.size();
392                if B::MAY_HAVE_SIDE_EFFECT && sz_b > self.len {
393                    for _ in 0..sz_b - self.len {
394                        self.b.next_back();
395                    }
396                }
397            }
398        }
399        if self.index < self.len {
400            // since get_unchecked executes code which can panic we increment the counters beforehand
401            // so that the same index won't be accessed twice, as required by TrustedRandomAccess
402            self.len -= 1;
403            self.a_len -= 1;
404            let i = self.len;
405            // SAFETY: `i` is smaller than the previous value of `self.len`,
406            // which is also smaller than or equal to `self.a.len()` and `self.b.len()`
407            unsafe {
408                Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
409            }
410        } else {
411            None
412        }
413    }
414}
415
416#[stable(feature = "rust1", since = "1.0.0")]
417impl<A, B> ExactSizeIterator for Zip<A, B>
418where
419    A: ExactSizeIterator,
420    B: ExactSizeIterator,
421{
422}
423
424#[doc(hidden)]
425#[unstable(feature = "trusted_random_access", issue = "none")]
426unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
427where
428    A: TrustedRandomAccess,
429    B: TrustedRandomAccess,
430{
431}
432
433#[doc(hidden)]
434#[unstable(feature = "trusted_random_access", issue = "none")]
435unsafe impl<A, B> TrustedRandomAccessNoCoerce for Zip<A, B>
436where
437    A: TrustedRandomAccessNoCoerce,
438    B: TrustedRandomAccessNoCoerce,
439{
440    const MAY_HAVE_SIDE_EFFECT: bool = A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT;
441}
442
443#[stable(feature = "fused", since = "1.26.0")]
444impl<A, B> FusedIterator for Zip<A, B>
445where
446    A: FusedIterator,
447    B: FusedIterator,
448{
449}
450
451#[unstable(issue = "none", feature = "trusted_fused")]
452unsafe impl<A, B> TrustedFused for Zip<A, B>
453where
454    A: TrustedFused,
455    B: TrustedFused,
456{
457}
458
459#[unstable(feature = "trusted_len", issue = "37572")]
460unsafe impl<A, B> TrustedLen for Zip<A, B>
461where
462    A: TrustedLen,
463    B: TrustedLen,
464{
465}
466
467impl<A, B> UncheckedIterator for Zip<A, B>
468where
469    A: UncheckedIterator,
470    B: UncheckedIterator,
471{
472}
473
474// Arbitrarily selects the left side of the zip iteration as extractable "source"
475// it would require negative trait bounds to be able to try both
476#[unstable(issue = "none", feature = "inplace_iteration")]
477unsafe impl<A, B> SourceIter for Zip<A, B>
478where
479    A: SourceIter,
480{
481    type Source = A::Source;
482
483    #[inline]
484    unsafe fn as_inner(&mut self) -> &mut A::Source {
485        // SAFETY: unsafe function forwarding to unsafe function with the same requirements
486        unsafe { SourceIter::as_inner(&mut self.a) }
487    }
488}
489
490// Since SourceIter forwards the left hand side we do the same here
491#[unstable(issue = "none", feature = "inplace_iteration")]
492unsafe impl<A: InPlaceIterable, B> InPlaceIterable for Zip<A, B> {
493    const EXPAND_BY: Option<NonZero<usize>> = A::EXPAND_BY;
494    const MERGE_BY: Option<NonZero<usize>> = A::MERGE_BY;
495}
496
497#[stable(feature = "rust1", since = "1.0.0")]
498impl<A: Debug, B: Debug> Debug for Zip<A, B> {
499    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
500        ZipFmt::fmt(self, f)
501    }
502}
503
504trait ZipFmt<A, B> {
505    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
506}
507
508impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> {
509    default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
510        f.debug_struct("Zip").field("a", &self.a).field("b", &self.b).finish()
511    }
512}
513
514impl<A: Debug + TrustedRandomAccessNoCoerce, B: Debug + TrustedRandomAccessNoCoerce> ZipFmt<A, B>
515    for Zip<A, B>
516{
517    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
518        // It's *not safe* to call fmt on the contained iterators, since once
519        // we start iterating they're in strange, potentially unsafe, states.
520        f.debug_struct("Zip").finish()
521    }
522}
523
524/// An iterator whose items are random-accessible efficiently
525///
526/// # Safety
527///
528/// The iterator's `size_hint` must be exact and cheap to call.
529///
530/// `TrustedRandomAccessNoCoerce::size` may not be overridden.
531///
532/// All subtypes and all supertypes of `Self` must also implement `TrustedRandomAccess`.
533/// In particular, this means that types with non-invariant parameters usually can not have
534/// an impl for `TrustedRandomAccess` that depends on any trait bounds on such parameters, except
535/// for bounds that come from the respective struct/enum definition itself, or bounds involving
536/// traits that themselves come with a guarantee similar to this one.
537///
538/// If `Self: ExactSizeIterator` then `self.len()` must always produce results consistent
539/// with `self.size()`.
540///
541/// If `Self: Iterator`, then `<Self as Iterator>::__iterator_get_unchecked(&mut self, idx)`
542/// must be safe to call provided the following conditions are met.
543///
544/// 1. `0 <= idx` and `idx < self.size()`.
545/// 2. If `Self: !Clone`, then `self.__iterator_get_unchecked(idx)` is never called with the same
546///    index on `self` more than once.
547/// 3. After `self.__iterator_get_unchecked(idx)` has been called, then `self.next_back()` will
548///    only be called at most `self.size() - idx - 1` times. If `Self: Clone` and `self` is cloned,
549///    then this number is calculated for `self` and its clone individually,
550///    but `self.next_back()` calls that happened before the cloning count for both `self` and the clone.
551/// 4. After `self.__iterator_get_unchecked(idx)` has been called, then only the following methods
552///    will be called on `self` or on any new clones of `self`:
553///     * `std::clone::Clone::clone`
554///     * `std::iter::Iterator::size_hint`
555///     * `std::iter::DoubleEndedIterator::next_back`
556///     * `std::iter::ExactSizeIterator::len`
557///     * `std::iter::Iterator::__iterator_get_unchecked`
558///     * `std::iter::TrustedRandomAccessNoCoerce::size`
559/// 5. If `T` is a subtype of `Self`, then `self` is allowed to be coerced
560///    to `T`. If `self` is coerced to `T` after `self.__iterator_get_unchecked(idx)` has already
561///    been called, then no methods except for the ones listed under 4. are allowed to be called
562///    on the resulting value of type `T`, either. Multiple such coercion steps are allowed.
563///    Regarding 2. and 3., the number of times `__iterator_get_unchecked(idx)` or `next_back()` is
564///    called on `self` and the resulting value of type `T` (and on further coercion results with
565///    sub-subtypes) are added together and their sums must not exceed the specified bounds.
566///
567/// Further, given that these conditions are met, it must guarantee that:
568///
569/// * It does not change the value returned from `size_hint`
570/// * It must be safe to call the methods listed above on `self` after calling
571///   `self.__iterator_get_unchecked(idx)`, assuming that the required traits are implemented.
572/// * It must also be safe to drop `self` after calling `self.__iterator_get_unchecked(idx)`.
573/// * If `T` is a subtype of `Self`, then it must be safe to coerce `self` to `T`.
574//
575// FIXME: Clarify interaction with SourceIter/InPlaceIterable. Calling `SourceIter::as_inner`
576// after `__iterator_get_unchecked` is supposed to be allowed.
577#[doc(hidden)]
578#[unstable(feature = "trusted_random_access", issue = "none")]
579#[rustc_specialization_trait]
580pub unsafe trait TrustedRandomAccess: TrustedRandomAccessNoCoerce {}
581
582/// Like [`TrustedRandomAccess`] but without any of the requirements / guarantees around
583/// coercions to subtypes after `__iterator_get_unchecked` (they aren’t allowed here!), and
584/// without the requirement that subtypes / supertypes implement `TrustedRandomAccessNoCoerce`.
585///
586/// This trait was created in PR #85874 to fix soundness issue #85873 without performance regressions.
587/// It is subject to change as we might want to build a more generally useful (for performance
588/// optimizations) and more sophisticated trait or trait hierarchy that replaces or extends
589/// [`TrustedRandomAccess`] and `TrustedRandomAccessNoCoerce`.
590#[doc(hidden)]
591#[unstable(feature = "trusted_random_access", issue = "none")]
592#[rustc_specialization_trait]
593pub unsafe trait TrustedRandomAccessNoCoerce: Sized {
594    // Convenience method.
595    fn size(&self) -> usize
596    where
597        Self: Iterator,
598    {
599        self.size_hint().0
600    }
601    /// `true` if getting an iterator element may have side effects.
602    /// Remember to take inner iterators into account.
603    const MAY_HAVE_SIDE_EFFECT: bool;
604}
605
606/// Like `Iterator::__iterator_get_unchecked`, but doesn't require the compiler to
607/// know that `U: TrustedRandomAccess`.
608///
609/// ## Safety
610///
611/// Same requirements calling `get_unchecked` directly.
612#[doc(hidden)]
613#[inline]
614pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item
615where
616    I: Iterator,
617{
618    // SAFETY: the caller must uphold the contract for
619    // `Iterator::__iterator_get_unchecked`.
620    unsafe { it.try_get_unchecked(idx) }
621}
622
623unsafe trait SpecTrustedRandomAccess: Iterator {
624    /// If `Self: TrustedRandomAccess`, it must be safe to call
625    /// `Iterator::__iterator_get_unchecked(self, index)`.
626    unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item;
627}
628
629unsafe impl<I: Iterator> SpecTrustedRandomAccess for I {
630    default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item {
631        panic!("Should only be called on TrustedRandomAccess iterators");
632    }
633}
634
635unsafe impl<I: Iterator + TrustedRandomAccessNoCoerce> SpecTrustedRandomAccess for I {
636    #[inline]
637    unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
638        // SAFETY: the caller must uphold the contract for
639        // `Iterator::__iterator_get_unchecked`.
640        unsafe { self.__iterator_get_unchecked(index) }
641    }
642}
643
644trait SpecFold: Iterator {
645    fn spec_fold<B, F>(self, init: B, f: F) -> B
646    where
647        Self: Sized,
648        F: FnMut(B, Self::Item) -> B;
649}
650
651impl<A: Iterator, B: Iterator> SpecFold for Zip<A, B> {
652    // Adapted from default impl from the Iterator trait
653    #[inline]
654    default fn spec_fold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
655    where
656        F: FnMut(Acc, Self::Item) -> Acc,
657    {
658        let mut accum = init;
659        while let Some(x) = ZipImpl::next(&mut self) {
660            accum = f(accum, x);
661        }
662        accum
663    }
664}
665
666impl<A: TrustedLen, B: TrustedLen> SpecFold for Zip<A, B> {
667    #[inline]
668    fn spec_fold<Acc, F>(mut self, init: Acc, mut f: F) -> Acc
669    where
670        F: FnMut(Acc, Self::Item) -> Acc,
671    {
672        let mut accum = init;
673        loop {
674            let (upper, more) = if let Some(upper) = ZipImpl::size_hint(&self).1 {
675                (upper, false)
676            } else {
677                // Per TrustedLen contract a None upper bound means more than usize::MAX items
678                (usize::MAX, true)
679            };
680
681            for _ in 0..upper {
682                let pair =
683                    // SAFETY: TrustedLen guarantees that at least `upper` many items are available
684                    // therefore we know they can't be None
685                    unsafe { (self.a.next().unwrap_unchecked(), self.b.next().unwrap_unchecked()) };
686                accum = f(accum, pair);
687            }
688
689            if !more {
690                break;
691            }
692        }
693        accum
694    }
695}