core/iter/adapters/
zip.rs

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

core/iter/adapters/
zip.rs
