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