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