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

core/iter/adapters/
zip.rs
