2 use crate::fmt::{self, Debug};
3 use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator};
4 use crate::iter::{InPlaceIterable, SourceIter, TrustedLen};
6 /// An iterator that iterates two other iterators simultaneously.
8 /// This `struct` is created by [`zip`] or [`Iterator::zip`].
9 /// See their documentation for more.
11 #[must_use = "iterators are lazy and do nothing unless consumed"]
12 #[stable(feature = "rust1", since = "1.0.0")]
13 pub struct Zip<A, B> {
16 // index, len and a_len are only used by the specialized version of zip
21 impl<A: Iterator, B: Iterator> Zip<A, B> {
22 pub(in crate::iter) fn new(a: A, b: B) -> Zip<A, B> {
25 fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> {
26 while let Some(x) = Iterator::next(self) {
36 /// Converts the arguments to iterators and zips them.
38 /// See the documentation of [`Iterator::zip`] for more.
43 /// #![feature(iter_zip)]
44 /// use std::iter::zip;
46 /// let xs = [1, 2, 3];
47 /// let ys = [4, 5, 6];
48 /// for (x, y) in zip(&xs, &ys) {
49 /// println!("x:{}, y:{}", x, y);
52 /// // Nested zips are also possible:
53 /// let zs = [7, 8, 9];
54 /// for ((x, y), z) in zip(zip(&xs, &ys), &zs) {
55 /// println!("x:{}, y:{}, z:{}", x, y, z);
58 #[unstable(feature = "iter_zip", issue = "83574")]
59 pub fn zip<A, B>(a: A, b: B) -> Zip<A::IntoIter, B::IntoIter>
64 ZipImpl::new(a.into_iter(), b.into_iter())
67 #[stable(feature = "rust1", since = "1.0.0")]
68 impl<A, B> Iterator for Zip<A, B>
73 type Item = (A::Item, B::Item);
76 fn next(&mut self) -> Option<Self::Item> {
81 fn size_hint(&self) -> (usize, Option<usize>) {
82 ZipImpl::size_hint(self)
86 fn nth(&mut self, n: usize) -> Option<Self::Item> {
92 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
94 Self: TrustedRandomAccess,
96 // SAFETY: `ZipImpl::__iterator_get_unchecked` has same safety
97 // requirements as `Iterator::__iterator_get_unchecked`.
98 unsafe { ZipImpl::get_unchecked(self, idx) }
102 #[stable(feature = "rust1", since = "1.0.0")]
103 impl<A, B> DoubleEndedIterator for Zip<A, B>
105 A: DoubleEndedIterator + ExactSizeIterator,
106 B: DoubleEndedIterator + ExactSizeIterator,
109 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
110 ZipImpl::next_back(self)
114 // Zip specialization trait
116 trait ZipImpl<A, B> {
118 fn new(a: A, b: B) -> Self;
119 fn next(&mut self) -> Option<Self::Item>;
120 fn size_hint(&self) -> (usize, Option<usize>);
121 fn nth(&mut self, n: usize) -> Option<Self::Item>;
122 fn next_back(&mut self) -> Option<Self::Item>
124 A: DoubleEndedIterator + ExactSizeIterator,
125 B: DoubleEndedIterator + ExactSizeIterator;
126 // This has the same safety requirements as `Iterator::__iterator_get_unchecked`
127 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
129 Self: Iterator + TrustedRandomAccess;
134 impl<A, B> ZipImpl<A, B> for Zip<A, B>
139 type Item = (A::Item, B::Item);
140 default fn new(a: A, b: B) -> Self {
151 default fn next(&mut self) -> Option<(A::Item, B::Item)> {
152 let x = self.a.next()?;
153 let y = self.b.next()?;
158 default fn nth(&mut self, n: usize) -> Option<Self::Item> {
163 default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
165 A: DoubleEndedIterator + ExactSizeIterator,
166 B: DoubleEndedIterator + ExactSizeIterator,
168 let a_sz = self.a.len();
169 let b_sz = self.b.len();
171 // Adjust a, b to equal length
173 for _ in 0..a_sz - b_sz {
177 for _ in 0..b_sz - a_sz {
182 match (self.a.next_back(), self.b.next_back()) {
183 (Some(x), Some(y)) => Some((x, y)),
184 (None, None) => None,
190 default fn size_hint(&self) -> (usize, Option<usize>) {
191 let (a_lower, a_upper) = self.a.size_hint();
192 let (b_lower, b_upper) = self.b.size_hint();
194 let lower = cmp::min(a_lower, b_lower);
196 let upper = match (a_upper, b_upper) {
197 (Some(x), Some(y)) => Some(cmp::min(x, y)),
198 (Some(x), None) => Some(x),
199 (None, Some(y)) => Some(y),
200 (None, None) => None,
206 default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item
208 Self: TrustedRandomAccess,
210 unreachable!("Always specialized");
215 impl<A, B> ZipImpl<A, B> for Zip<A, B>
217 A: TrustedRandomAccess + Iterator,
218 B: TrustedRandomAccess + Iterator,
220 fn new(a: A, b: B) -> Self {
221 let a_len = a.size();
222 let len = cmp::min(a_len, b.size());
223 Zip { a, b, index: 0, len, a_len }
227 fn next(&mut self) -> Option<(A::Item, B::Item)> {
228 if self.index < self.len {
230 // since get_unchecked executes code which can panic we increment the counters beforehand
231 // so that the same index won't be accessed twice, as required by TrustedRandomAccess
233 // SAFETY: `i` is smaller than `self.len`, thus smaller than `self.a.len()` and `self.b.len()`
235 Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
237 } else if A::MAY_HAVE_SIDE_EFFECT && self.index < self.a_len {
239 // as above, increment before executing code that may panic
242 // match the base implementation's potential side effects
243 // SAFETY: we just checked that `i` < `self.a.len()`
245 self.a.__iterator_get_unchecked(i);
254 fn size_hint(&self) -> (usize, Option<usize>) {
255 let len = self.len - self.index;
260 fn nth(&mut self, n: usize) -> Option<Self::Item> {
261 let delta = cmp::min(n, self.len - self.index);
262 let end = self.index + delta;
263 while self.index < end {
265 // since get_unchecked executes code which can panic we increment the counters beforehand
266 // so that the same index won't be accessed twice, as required by TrustedRandomAccess
268 if A::MAY_HAVE_SIDE_EFFECT {
269 // SAFETY: the usage of `cmp::min` to calculate `delta`
270 // ensures that `end` is smaller than or equal to `self.len`,
271 // so `i` is also smaller than `self.len`.
273 self.a.__iterator_get_unchecked(i);
276 if B::MAY_HAVE_SIDE_EFFECT {
277 // SAFETY: same as above.
279 self.b.__iterator_get_unchecked(i);
284 self.super_nth(n - delta)
288 fn next_back(&mut self) -> Option<(A::Item, B::Item)>
290 A: DoubleEndedIterator + ExactSizeIterator,
291 B: DoubleEndedIterator + ExactSizeIterator,
293 if A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT {
294 let sz_a = self.a.size();
295 let sz_b = self.b.size();
296 // Adjust a, b to equal length, make sure that only the first call
297 // of `next_back` does this, otherwise we will break the restriction
298 // on calls to `self.next_back()` after calling `get_unchecked()`.
300 let sz_a = self.a.size();
301 if A::MAY_HAVE_SIDE_EFFECT && sz_a > self.len {
302 for _ in 0..sz_a - self.len {
303 // since next_back() may panic we increment the counters beforehand
304 // to keep Zip's state in sync with the underlying iterator source
308 debug_assert_eq!(self.a_len, self.len);
310 let sz_b = self.b.size();
311 if B::MAY_HAVE_SIDE_EFFECT && sz_b > self.len {
312 for _ in 0..sz_b - self.len {
318 if self.index < self.len {
319 // since get_unchecked executes code which can panic we increment the counters beforehand
320 // so that the same index won't be accessed twice, as required by TrustedRandomAccess
324 // SAFETY: `i` is smaller than the previous value of `self.len`,
325 // which is also smaller than or equal to `self.a.len()` and `self.b.len()`
327 Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
335 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item {
336 let idx = self.index + idx;
337 // SAFETY: the caller must uphold the contract for
338 // `Iterator::__iterator_get_unchecked`.
339 unsafe { (self.a.__iterator_get_unchecked(idx), self.b.__iterator_get_unchecked(idx)) }
343 #[stable(feature = "rust1", since = "1.0.0")]
344 impl<A, B> ExactSizeIterator for Zip<A, B>
346 A: ExactSizeIterator,
347 B: ExactSizeIterator,
352 #[unstable(feature = "trusted_random_access", issue = "none")]
353 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
355 A: TrustedRandomAccess,
356 B: TrustedRandomAccess,
358 const MAY_HAVE_SIDE_EFFECT: bool = A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT;
361 #[stable(feature = "fused", since = "1.26.0")]
362 impl<A, B> FusedIterator for Zip<A, B>
369 #[unstable(feature = "trusted_len", issue = "37572")]
370 unsafe impl<A, B> TrustedLen for Zip<A, B>
377 // Arbitrarily selects the left side of the zip iteration as extractable "source"
378 // it would require negative trait bounds to be able to try both
379 #[unstable(issue = "none", feature = "inplace_iteration")]
380 unsafe impl<S, A, B> SourceIter for Zip<A, B>
382 A: SourceIter<Source = S>,
389 unsafe fn as_inner(&mut self) -> &mut S {
390 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
391 unsafe { SourceIter::as_inner(&mut self.a) }
395 #[unstable(issue = "none", feature = "inplace_iteration")]
396 // Limited to Item: Copy since interaction between Zip's use of TrustedRandomAccess
397 // and Drop implementation of the source is unclear.
399 // An additional method returning the number of times the source has been logically advanced
400 // (without calling next()) would be needed to properly drop the remainder of the source.
401 unsafe impl<A: InPlaceIterable, B: Iterator> InPlaceIterable for Zip<A, B> where A::Item: Copy {}
403 #[stable(feature = "rust1", since = "1.0.0")]
404 impl<A: Debug, B: Debug> Debug for Zip<A, B> {
405 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
411 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
414 impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> {
415 default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
416 f.debug_struct("Zip").field("a", &self.a).field("b", &self.b).finish()
420 impl<A: Debug + TrustedRandomAccess, B: Debug + TrustedRandomAccess> ZipFmt<A, B> for Zip<A, B> {
421 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
422 // It's *not safe* to call fmt on the contained iterators, since once
423 // we start iterating they're in strange, potentially unsafe, states.
424 f.debug_struct("Zip").finish()
428 /// An iterator whose items are random-accessible efficiently
432 /// The iterator's `size_hint` must be exact and cheap to call.
434 /// `size` may not be overridden.
436 /// `<Self as Iterator>::__iterator_get_unchecked` must be safe to call
437 /// provided the following conditions are met.
439 /// 1. `0 <= idx` and `idx < self.size()`.
440 /// 2. If `self: !Clone`, then `get_unchecked` is never called with the same
441 /// index on `self` more than once.
442 /// 3. After `self.get_unchecked(idx)` has been called then `next_back` will
443 /// only be called at most `self.size() - idx - 1` times.
444 /// 4. After `get_unchecked` is called, then only the following methods will be
445 /// called on `self`:
446 /// * `std::clone::Clone::clone()`
447 /// * `std::iter::Iterator::size_hint()`
448 /// * `std::iter::DoubleEndedIterator::next_back()`
449 /// * `std::iter::Iterator::__iterator_get_unchecked()`
450 /// * `std::iter::TrustedRandomAccess::size()`
452 /// Further, given that these conditions are met, it must guarantee that:
454 /// * It does not change the value returned from `size_hint`
455 /// * It must be safe to call the methods listed above on `self` after calling
456 /// `get_unchecked`, assuming that the required traits are implemented.
457 /// * It must also be safe to drop `self` after calling `get_unchecked`.
459 #[unstable(feature = "trusted_random_access", issue = "none")]
460 #[rustc_specialization_trait]
461 pub unsafe trait TrustedRandomAccess: Sized {
462 // Convenience method.
463 fn size(&self) -> usize
469 /// `true` if getting an iterator element may have side effects.
470 /// Remember to take inner iterators into account.
471 const MAY_HAVE_SIDE_EFFECT: bool;
474 /// Like `Iterator::__iterator_get_unchecked`, but doesn't require the compiler to
475 /// know that `U: TrustedRandomAccess`.
479 /// Same requirements calling `get_unchecked` directly.
481 pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item
485 // SAFETY: the caller must uphold the contract for
486 // `Iterator::__iterator_get_unchecked`.
487 unsafe { it.try_get_unchecked(idx) }
490 unsafe trait SpecTrustedRandomAccess: Iterator {
491 /// If `Self: TrustedRandomAccess`, it must be safe to call a
492 /// `Iterator::__iterator_get_unchecked(self, index)`.
493 unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item;
496 unsafe impl<I: Iterator> SpecTrustedRandomAccess for I {
497 default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item {
498 panic!("Should only be called on TrustedRandomAccess iterators");
502 unsafe impl<I: Iterator + TrustedRandomAccess> SpecTrustedRandomAccess for I {
503 unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
504 // SAFETY: the caller must uphold the contract for
505 // `Iterator::__iterator_get_unchecked`.
506 unsafe { self.__iterator_get_unchecked(index) }