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#[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: 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#[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 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#[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 unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
147 where
148 Self: Iterator + TrustedRandomAccessNoCoerce;
149}
150
151macro_rules! zip_impl_general_defaults {
154 () => {
155 default fn new(a: A, b: B) -> Self {
156 Zip {
157 a,
158 b,
159 index: 0, len: 0, a_len: 0, }
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 let a_sz = self.a.len();
188 let b_sz = self.b.len();
189 if a_sz != b_sz {
190 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#[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 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 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 self.index += 1;
314 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 self.index += 1;
322 self.len += 1;
323 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 self.index += 1;
349 if A::MAY_HAVE_SIDE_EFFECT {
350 unsafe {
354 self.a.__iterator_get_unchecked(i);
355 }
356 }
357 if B::MAY_HAVE_SIDE_EFFECT {
358 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 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 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 self.len -= 1;
403 self.a_len -= 1;
404 let i = self.len;
405 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#[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 unsafe { SourceIter::as_inner(&mut self.a) }
487 }
488}
489
490#[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 f.debug_struct("Zip").finish()
521 }
522}
523
524#[doc(hidden)]
578#[unstable(feature = "trusted_random_access", issue = "none")]
579#[rustc_specialization_trait]
580pub unsafe trait TrustedRandomAccess: TrustedRandomAccessNoCoerce {}
581
582#[doc(hidden)]
591#[unstable(feature = "trusted_random_access", issue = "none")]
592#[rustc_specialization_trait]
593pub unsafe trait TrustedRandomAccessNoCoerce: Sized {
594 fn size(&self) -> usize
596 where
597 Self: Iterator,
598 {
599 self.size_hint().0
600 }
601 const MAY_HAVE_SIDE_EFFECT: bool;
604}
605
606#[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 unsafe { it.try_get_unchecked(idx) }
621}
622
623unsafe trait SpecTrustedRandomAccess: Iterator {
624 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 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 #[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 (usize::MAX, true)
679 };
680
681 for _ in 0..upper {
682 let pair =
683 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}