core/iter/adapters/
zip.rs

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

core/iter/adapters/
zip.rs
