2 use crate::fmt::{self, Debug};
4 use super::super::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator, TrustedLen};
6 /// An iterator that iterates two other iterators simultaneously.
8 /// This `struct` is created by the [`zip`] method on [`Iterator`]. See its
9 /// documentation for more.
11 /// [`zip`]: trait.Iterator.html#method.zip
12 /// [`Iterator`]: trait.Iterator.html
14 #[must_use = "iterators are lazy and do nothing unless consumed"]
15 #[stable(feature = "rust1", since = "1.0.0")]
16 pub struct Zip<A, B> {
19 // index and len are only used by the specialized version of zip
23 impl<A: Iterator, B: Iterator> Zip<A, B> {
24 pub(in super::super) fn new(a: A, b: B) -> Zip<A, B> {
27 fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> {
28 while let Some(x) = Iterator::next(self) {
38 #[stable(feature = "rust1", since = "1.0.0")]
39 impl<A, B> Iterator for Zip<A, B>
44 type Item = (A::Item, B::Item);
47 fn next(&mut self) -> Option<Self::Item> {
52 fn size_hint(&self) -> (usize, Option<usize>) {
53 ZipImpl::size_hint(self)
57 fn nth(&mut self, n: usize) -> Option<Self::Item> {
62 unsafe fn get_unchecked(&mut self, idx: usize) -> Self::Item
64 Self: TrustedRandomAccess,
66 // SAFETY: `ZipImpl::get_unchecked` has same safety requirements as
67 // `Iterator::get_unchecked`.
68 unsafe { ZipImpl::get_unchecked(self, idx) }
72 #[stable(feature = "rust1", since = "1.0.0")]
73 impl<A, B> DoubleEndedIterator for Zip<A, B>
75 A: DoubleEndedIterator + ExactSizeIterator,
76 B: DoubleEndedIterator + ExactSizeIterator,
79 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
80 ZipImpl::next_back(self)
84 // Zip specialization trait
88 fn new(a: A, b: B) -> Self;
89 fn next(&mut self) -> Option<Self::Item>;
90 fn size_hint(&self) -> (usize, Option<usize>);
91 fn nth(&mut self, n: usize) -> Option<Self::Item>;
92 fn next_back(&mut self) -> Option<Self::Item>
94 A: DoubleEndedIterator + ExactSizeIterator,
95 B: DoubleEndedIterator + ExactSizeIterator;
96 // This has the same safety requirements as `Iterator::get_unchecked`
97 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
99 Self: Iterator + TrustedRandomAccess;
104 impl<A, B> ZipImpl<A, B> for Zip<A, B>
109 type Item = (A::Item, B::Item);
110 default fn new(a: A, b: B) -> Self {
120 default fn next(&mut self) -> Option<(A::Item, B::Item)> {
121 let x = self.a.next()?;
122 let y = self.b.next()?;
127 default fn nth(&mut self, n: usize) -> Option<Self::Item> {
132 default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
134 A: DoubleEndedIterator + ExactSizeIterator,
135 B: DoubleEndedIterator + ExactSizeIterator,
137 let a_sz = self.a.len();
138 let b_sz = self.b.len();
140 // Adjust a, b to equal length
142 for _ in 0..a_sz - b_sz {
146 for _ in 0..b_sz - a_sz {
151 match (self.a.next_back(), self.b.next_back()) {
152 (Some(x), Some(y)) => Some((x, y)),
153 (None, None) => None,
159 default fn size_hint(&self) -> (usize, Option<usize>) {
160 let (a_lower, a_upper) = self.a.size_hint();
161 let (b_lower, b_upper) = self.b.size_hint();
163 let lower = cmp::min(a_lower, b_lower);
165 let upper = match (a_upper, b_upper) {
166 (Some(x), Some(y)) => Some(cmp::min(x, y)),
167 (Some(x), None) => Some(x),
168 (None, Some(y)) => Some(y),
169 (None, None) => None,
175 default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item
177 Self: TrustedRandomAccess,
179 unreachable!("Always specialized");
184 impl<A, B> ZipImpl<A, B> for Zip<A, B>
186 A: TrustedRandomAccess + Iterator,
187 B: TrustedRandomAccess + Iterator,
189 fn new(a: A, b: B) -> Self {
190 let len = cmp::min(a.size(), b.size());
191 Zip { a, b, index: 0, len }
195 fn next(&mut self) -> Option<(A::Item, B::Item)> {
196 if self.index < self.len {
199 // SAFETY: `i` is smaller than `self.len`, thus smaller than `self.a.len()` and `self.b.len()`
200 unsafe { Some((self.a.get_unchecked(i), self.b.get_unchecked(i))) }
201 } else if A::may_have_side_effect() && self.index < self.a.size() {
202 // match the base implementation's potential side effects
203 // SAFETY: we just checked that `self.index` < `self.a.len()`
205 self.a.get_unchecked(self.index);
215 fn size_hint(&self) -> (usize, Option<usize>) {
216 let len = self.len - self.index;
221 fn nth(&mut self, n: usize) -> Option<Self::Item> {
222 let delta = cmp::min(n, self.len - self.index);
223 let end = self.index + delta;
224 while self.index < end {
227 if A::may_have_side_effect() {
228 // SAFETY: the usage of `cmp::min` to calculate `delta`
229 // ensures that `end` is smaller than or equal to `self.len`,
230 // so `i` is also smaller than `self.len`.
232 self.a.get_unchecked(i);
235 if B::may_have_side_effect() {
236 // SAFETY: same as above.
238 self.b.get_unchecked(i);
243 self.super_nth(n - delta)
247 fn next_back(&mut self) -> Option<(A::Item, B::Item)>
249 A: DoubleEndedIterator + ExactSizeIterator,
250 B: DoubleEndedIterator + ExactSizeIterator,
252 let a_side_effect = A::may_have_side_effect();
253 let b_side_effect = B::may_have_side_effect();
254 if a_side_effect || b_side_effect {
255 let sz_a = self.a.size();
256 let sz_b = self.b.size();
257 // Adjust a, b to equal length, make sure that only the first call
258 // of `next_back` does this, otherwise we will break the restriction
259 // on calls to `self.next_back()` after calling `get_unchecked()`.
261 let sz_a = self.a.size();
262 if a_side_effect && sz_a > self.len {
263 for _ in 0..sz_a - cmp::max(self.len, self.index) {
267 let sz_b = self.b.size();
268 if b_side_effect && sz_b > self.len {
269 for _ in 0..sz_b - self.len {
275 if self.index < self.len {
278 // SAFETY: `i` is smaller than the previous value of `self.len`,
279 // which is also smaller than or equal to `self.a.len()` and `self.b.len()`
280 unsafe { Some((self.a.get_unchecked(i), self.b.get_unchecked(i))) }
287 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item {
288 // SAFETY: the caller must uphold the contract for
289 // `Iterator::get_unchecked`.
290 unsafe { (self.a.get_unchecked(idx), self.b.get_unchecked(idx)) }
294 #[stable(feature = "rust1", since = "1.0.0")]
295 impl<A, B> ExactSizeIterator for Zip<A, B>
297 A: ExactSizeIterator,
298 B: ExactSizeIterator,
303 #[unstable(feature = "trusted_random_access", issue = "none")]
304 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
306 A: TrustedRandomAccess,
307 B: TrustedRandomAccess,
309 fn may_have_side_effect() -> bool {
310 A::may_have_side_effect() || B::may_have_side_effect()
314 #[stable(feature = "fused", since = "1.26.0")]
315 impl<A, B> FusedIterator for Zip<A, B>
322 #[unstable(feature = "trusted_len", issue = "37572")]
323 unsafe impl<A, B> TrustedLen for Zip<A, B>
330 #[stable(feature = "rust1", since = "1.0.0")]
331 impl<A: Debug, B: Debug> Debug for Zip<A, B> {
332 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
338 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
341 impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> {
342 default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
343 f.debug_struct("Zip").field("a", &self.a).field("b", &self.b).finish()
347 impl<A: Debug + TrustedRandomAccess, B: Debug + TrustedRandomAccess> ZipFmt<A, B> for Zip<A, B> {
348 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
349 // It's *not safe* to call fmt on the contained iterators, since once
350 // we start iterating they're in strange, potentially unsafe, states.
351 f.debug_struct("Zip").finish()
355 /// An iterator whose items are random-accessible efficiently
359 /// The iterator's `size_hint` must be exact and cheap to call.
361 /// `size` may not be overridden.
363 /// `<Self as Iterator>::get_unchecked` must be safe to call provided the
364 /// following conditions are met.
366 /// 1. `0 <= idx` and `idx < self.size()`.
367 /// 2. If `self: !Clone`, then `get_unchecked` is never called with the same
368 /// index on `self` more than once.
369 /// 3. After `self.get_unchecked(idx)` has been called then `next_back` will
370 /// only be called at most `self.size() - idx - 1` times.
371 /// 4. After `get_unchecked` is called, then only the following methods will be
372 /// called on `self`:
373 /// * `std::clone::Clone::clone`
374 /// * `std::iter::Iterator::size_hint()`
375 /// * `std::iter::Iterator::next_back()`
376 /// * `std::iter::Iterator::get_unchecked()`
377 /// * `std::iter::TrustedRandomAccess::size()`
379 /// Further, given that these conditions are met, it must guarantee that:
381 /// * It does not change the value returned from `size_hint`
382 /// * It must be safe to call the methods listed above on `self` after calling
383 /// `get_unchecked`, assuming that the required traits are implemented.
384 /// * It must also be safe to drop `self` after calling `get_unchecked`.
386 #[unstable(feature = "trusted_random_access", issue = "none")]
387 #[rustc_specialization_trait]
388 pub unsafe trait TrustedRandomAccess: Sized {
389 // Convenience method.
390 fn size(&self) -> usize
396 /// Returns `true` if getting an iterator element may have
397 /// side effects. Remember to take inner iterators into account.
398 fn may_have_side_effect() -> bool;
401 /// Like `Iterator::get_unchecked`, but doesn't require the compiler to
402 /// know that `U: TrustedRandomAccess`.
406 /// Same requirements calling `get_unchecked` directly.
408 pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item
412 // SAFETY: the caller must uphold the contract for
413 // `Iterator::get_unchecked`.
414 unsafe { it.try_get_unchecked(idx) }
417 unsafe trait SpecTrustedRandomAccess: Iterator {
418 /// If `Self: TrustedRandomAccess`, it must be safe to call a
419 /// `Iterator::get_unchecked(self, index)`.
420 unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item;
423 unsafe impl<I: Iterator> SpecTrustedRandomAccess for I {
424 default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item {
425 panic!("Should only be called on TrustedRandomAccess iterators");
429 unsafe impl<I: Iterator + TrustedRandomAccess> SpecTrustedRandomAccess for I {
430 unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
431 // SAFETY: the caller must uphold the contract for
432 // `Iterator::get_unchecked`.
433 unsafe { self.get_unchecked(index) }