core/iter/adapters/
zip.rs

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

core/iter/adapters/
zip.rs
