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

core/iter/adapters/
zip.rs
