x86_64/usr/lib/rustlib/src/rust/library/core/src/iter/adapters/zip.rs - manifest_repos/toolchain - Git at Google

 use crate::cmp;
 use crate::fmt::{self, Debug};
 use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator};
 use crate::iter::{InPlaceIterable, SourceIter, TrustedLen};

 /// An iterator that iterates two other iterators simultaneously.
 ///
 /// This `struct` is created by [`zip`] or [`Iterator::zip`].
 /// See their documentation for more.
 #[derive(Clone)]
 #[must_use = "iterators are lazy and do nothing unless consumed"]
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Zip<A, B> {
     a: A,
     b: B,
     // index, len and a_len are only used by the specialized version of zip
     index: usize,
     len: usize,
     a_len: usize,
 }
 impl<A: Iterator, B: Iterator> Zip<A, B> {
     pub(in crate::iter) fn new(a: A, b: B) -> Zip<A, B> {
         ZipImpl::new(a, b)
     }
     fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> {
         while let Some(x) = Iterator::next(self) {
             if n == 0 {
                 return Some(x);
             }
             n -= 1;
         }
         None
     }
 }

 /// Converts the arguments to iterators and zips them.
 ///
 /// See the documentation of [`Iterator::zip`] for more.
 ///
 /// # Examples
 ///
 /// ```
 /// use std::iter::zip;
 ///
 /// let xs = [1, 2, 3];
 /// let ys = [4, 5, 6];
 ///
 /// let mut iter = zip(xs, ys);
 ///
 /// assert_eq!(iter.next().unwrap(), (1, 4));
 /// assert_eq!(iter.next().unwrap(), (2, 5));
 /// assert_eq!(iter.next().unwrap(), (3, 6));
 /// assert!(iter.next().is_none());
 ///
 /// // Nested zips are also possible:
 /// let zs = [7, 8, 9];
 ///
 /// let mut iter = zip(zip(xs, ys), zs);
 ///
 /// assert_eq!(iter.next().unwrap(), ((1, 4), 7));
 /// assert_eq!(iter.next().unwrap(), ((2, 5), 8));
 /// assert_eq!(iter.next().unwrap(), ((3, 6), 9));
 /// assert!(iter.next().is_none());
 /// ```
 #[stable(feature = "iter_zip", since = "1.59.0")]
 pub fn zip<A, B>(a: A, b: B) -> Zip<A::IntoIter, B::IntoIter>
 where
     A: IntoIterator,
     B: IntoIterator,
 {
     ZipImpl::new(a.into_iter(), b.into_iter())
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A, B> Iterator for Zip<A, B>
 where
     A: Iterator,
     B: Iterator,
 {
     type Item = (A::Item, B::Item);

     #[inline]
     fn next(&mut self) -> Option<Self::Item> {
         ZipImpl::next(self)
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         ZipImpl::size_hint(self)
     }

     #[inline]
     fn nth(&mut self, n: usize) -> Option<Self::Item> {
         ZipImpl::nth(self, n)
     }

     #[inline]
     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
     where
         Self: TrustedRandomAccessNoCoerce,
     {
         // SAFETY: `ZipImpl::__iterator_get_unchecked` has same safety
         // requirements as `Iterator::__iterator_get_unchecked`.
         unsafe { ZipImpl::get_unchecked(self, idx) }
     }
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A, B> DoubleEndedIterator for Zip<A, B>
 where
     A: DoubleEndedIterator + ExactSizeIterator,
     B: DoubleEndedIterator + ExactSizeIterator,
 {
     #[inline]
     fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
         ZipImpl::next_back(self)
     }
 }

 // Zip specialization trait
 #[doc(hidden)]
 trait ZipImpl<A, B> {
     type Item;
     fn new(a: A, b: B) -> Self;
     fn next(&mut self) -> Option<Self::Item>;
     fn size_hint(&self) -> (usize, Option<usize>);
     fn nth(&mut self, n: usize) -> Option<Self::Item>;
     fn next_back(&mut self) -> Option<Self::Item>
     where
         A: DoubleEndedIterator + ExactSizeIterator,
         B: DoubleEndedIterator + ExactSizeIterator;
     // This has the same safety requirements as `Iterator::__iterator_get_unchecked`
     unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
     where
         Self: Iterator + TrustedRandomAccessNoCoerce;
 }

 // Work around limitations of specialization, requiring `default` impls to be repeated
 // in intermediary impls.
 macro_rules! zip_impl_general_defaults {
     () => {
         default fn new(a: A, b: B) -> Self {
             Zip {
                 a,
                 b,
                 index: 0, // unused
                 len: 0,   // unused
                 a_len: 0, // unused
             }
         }

         #[inline]
         default fn next(&mut self) -> Option<(A::Item, B::Item)> {
             let x = self.a.next()?;
             let y = self.b.next()?;
             Some((x, y))
         }

         #[inline]
         default fn nth(&mut self, n: usize) -> Option<Self::Item> {
             self.super_nth(n)
         }

         #[inline]
         default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
         where
             A: DoubleEndedIterator + ExactSizeIterator,
             B: DoubleEndedIterator + ExactSizeIterator,
         {
             // The function body below only uses `self.a/b.len()` and `self.a/b.next_back()`
             // and doesn’t call `next_back` too often, so this implementation is safe in
             // the `TrustedRandomAccessNoCoerce` specialization

             let a_sz = self.a.len();
             let b_sz = self.b.len();
             if a_sz != b_sz {
                 // Adjust a, b to equal length
                 if a_sz > b_sz {
                     for _ in 0..a_sz - b_sz {
                         self.a.next_back();
                     }
                 } else {
                     for _ in 0..b_sz - a_sz {
                         self.b.next_back();
                     }
                 }
             }
             match (self.a.next_back(), self.b.next_back()) {
                 (Some(x), Some(y)) => Some((x, y)),
                 (None, None) => None,
                 _ => unreachable!(),
             }
         }
     };
 }

 // General Zip impl
 #[doc(hidden)]
 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 where
     A: Iterator,
     B: Iterator,
 {
     type Item = (A::Item, B::Item);

     zip_impl_general_defaults! {}

     #[inline]
     default fn size_hint(&self) -> (usize, Option<usize>) {
         let (a_lower, a_upper) = self.a.size_hint();
         let (b_lower, b_upper) = self.b.size_hint();

         let lower = cmp::min(a_lower, b_lower);

         let upper = match (a_upper, b_upper) {
             (Some(x), Some(y)) => Some(cmp::min(x, y)),
             (Some(x), None) => Some(x),
             (None, Some(y)) => Some(y),
             (None, None) => None,
         };

         (lower, upper)
     }

     default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item
     where
         Self: TrustedRandomAccessNoCoerce,
     {
         unreachable!("Always specialized");
     }
 }

 #[doc(hidden)]
 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 where
     A: TrustedRandomAccessNoCoerce + Iterator,
     B: TrustedRandomAccessNoCoerce + Iterator,
 {
     zip_impl_general_defaults! {}

     #[inline]
     default fn size_hint(&self) -> (usize, Option<usize>) {
         let size = cmp::min(self.a.size(), self.b.size());
         (size, Some(size))
     }

     #[inline]
     unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item {
         let idx = self.index + idx;
         // SAFETY: the caller must uphold the contract for
         // `Iterator::__iterator_get_unchecked`.
         unsafe { (self.a.__iterator_get_unchecked(idx), self.b.__iterator_get_unchecked(idx)) }
     }
 }

 #[doc(hidden)]
 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 where
     A: TrustedRandomAccess + Iterator,
     B: TrustedRandomAccess + Iterator,
 {
     fn new(a: A, b: B) -> Self {
         let a_len = a.size();
         let len = cmp::min(a_len, b.size());
         Zip { a, b, index: 0, len, a_len }
     }

     #[inline]
     fn next(&mut self) -> Option<(A::Item, B::Item)> {
         if self.index < self.len {
             let i = self.index;
             // since get_unchecked executes code which can panic we increment the counters beforehand
             // so that the same index won't be accessed twice, as required by TrustedRandomAccess
             self.index += 1;
             // SAFETY: `i` is smaller than `self.len`, thus smaller than `self.a.len()` and `self.b.len()`
             unsafe {
                 Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
             }
         } else if A::MAY_HAVE_SIDE_EFFECT && self.index < self.a_len {
             let i = self.index;
             // as above, increment before executing code that may panic
             self.index += 1;
             self.len += 1;
             // match the base implementation's potential side effects
             // SAFETY: we just checked that `i` < `self.a.len()`
             unsafe {
                 self.a.__iterator_get_unchecked(i);
             }
             None
         } else {
             None
         }
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         let len = self.len - self.index;
         (len, Some(len))
     }

     #[inline]
     fn nth(&mut self, n: usize) -> Option<Self::Item> {
         let delta = cmp::min(n, self.len - self.index);
         let end = self.index + delta;
         while self.index < end {
             let i = self.index;
             // since get_unchecked executes code which can panic we increment the counters beforehand
             // so that the same index won't be accessed twice, as required by TrustedRandomAccess
             self.index += 1;
             if A::MAY_HAVE_SIDE_EFFECT {
                 // SAFETY: the usage of `cmp::min` to calculate `delta`
                 // ensures that `end` is smaller than or equal to `self.len`,
                 // so `i` is also smaller than `self.len`.
                 unsafe {
                     self.a.__iterator_get_unchecked(i);
                 }
             }
             if B::MAY_HAVE_SIDE_EFFECT {
                 // SAFETY: same as above.
                 unsafe {
                     self.b.__iterator_get_unchecked(i);
                 }
             }
         }

         self.super_nth(n - delta)
     }

     #[inline]
     fn next_back(&mut self) -> Option<(A::Item, B::Item)>
     where
         A: DoubleEndedIterator + ExactSizeIterator,
         B: DoubleEndedIterator + ExactSizeIterator,
     {
         if A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT {
             let sz_a = self.a.size();
             let sz_b = self.b.size();
             // Adjust a, b to equal length, make sure that only the first call
             // of `next_back` does this, otherwise we will break the restriction
             // on calls to `self.next_back()` after calling `get_unchecked()`.
             if sz_a != sz_b {
                 let sz_a = self.a.size();
                 if A::MAY_HAVE_SIDE_EFFECT && sz_a > self.len {
                     for _ in 0..sz_a - self.len {
                         // since next_back() may panic we increment the counters beforehand
                         // to keep Zip's state in sync with the underlying iterator source
                         self.a_len -= 1;
                         self.a.next_back();
                     }
                     debug_assert_eq!(self.a_len, self.len);
                 }
                 let sz_b = self.b.size();
                 if B::MAY_HAVE_SIDE_EFFECT && sz_b > self.len {
                     for _ in 0..sz_b - self.len {
                         self.b.next_back();
                     }
                 }
             }
         }
         if self.index < self.len {
             // since get_unchecked executes code which can panic we increment the counters beforehand
             // so that the same index won't be accessed twice, as required by TrustedRandomAccess
             self.len -= 1;
             self.a_len -= 1;
             let i = self.len;
             // SAFETY: `i` is smaller than the previous value of `self.len`,
             // which is also smaller than or equal to `self.a.len()` and `self.b.len()`
             unsafe {
                 Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
             }
         } else {
             None
         }
     }
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A, B> ExactSizeIterator for Zip<A, B>
 where
     A: ExactSizeIterator,
     B: ExactSizeIterator,
 {
 }

 #[doc(hidden)]
 #[unstable(feature = "trusted_random_access", issue = "none")]
 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
 where
     A: TrustedRandomAccess,
     B: TrustedRandomAccess,
 {
 }

 #[doc(hidden)]
 #[unstable(feature = "trusted_random_access", issue = "none")]
 unsafe impl<A, B> TrustedRandomAccessNoCoerce for Zip<A, B>
 where
     A: TrustedRandomAccessNoCoerce,
     B: TrustedRandomAccessNoCoerce,
 {
     const MAY_HAVE_SIDE_EFFECT: bool = A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT;
 }

 #[stable(feature = "fused", since = "1.26.0")]
 impl<A, B> FusedIterator for Zip<A, B>
 where
     A: FusedIterator,
     B: FusedIterator,
 {
 }

 #[unstable(feature = "trusted_len", issue = "37572")]
 unsafe impl<A, B> TrustedLen for Zip<A, B>
 where
     A: TrustedLen,
     B: TrustedLen,
 {
 }

 // Arbitrarily selects the left side of the zip iteration as extractable "source"
 // it would require negative trait bounds to be able to try both
 #[unstable(issue = "none", feature = "inplace_iteration")]
 unsafe impl<A, B> SourceIter for Zip<A, B>
 where
     A: SourceIter,
 {
     type Source = A::Source;

     #[inline]
     unsafe fn as_inner(&mut self) -> &mut A::Source {
         // SAFETY: unsafe function forwarding to unsafe function with the same requirements
         unsafe { SourceIter::as_inner(&mut self.a) }
     }
 }

 // Since SourceIter forwards the left hand side we do the same here
 #[unstable(issue = "none", feature = "inplace_iteration")]
 unsafe impl<A: InPlaceIterable, B: Iterator> InPlaceIterable for Zip<A, B> {}

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A: Debug, B: Debug> Debug for Zip<A, B> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         ZipFmt::fmt(self, f)
     }
 }

 trait ZipFmt<A, B> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
 }

 impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> {
     default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         f.debug_struct("Zip").field("a", &self.a).field("b", &self.b).finish()
     }
 }

 impl<A: Debug + TrustedRandomAccessNoCoerce, B: Debug + TrustedRandomAccessNoCoerce> ZipFmt<A, B>
     for Zip<A, B>
 {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         // It's *not safe* to call fmt on the contained iterators, since once
         // we start iterating they're in strange, potentially unsafe, states.
         f.debug_struct("Zip").finish()
     }
 }

 /// An iterator whose items are random-accessible efficiently
 ///
 /// # Safety
 ///
 /// The iterator's `size_hint` must be exact and cheap to call.
 ///
 /// `TrustedRandomAccessNoCoerce::size` may not be overridden.
 ///
 /// All subtypes and all supertypes of `Self` must also implement `TrustedRandomAccess`.
 /// In particular, this means that types with non-invariant parameters usually can not have
 /// an impl for `TrustedRandomAccess` that depends on any trait bounds on such parameters, except
 /// for bounds that come from the respective struct/enum definition itself, or bounds involving
 /// traits that themselves come with a guarantee similar to this one.
 ///
 /// If `Self: ExactSizeIterator` then `self.len()` must always produce results consistent
 /// with `self.size()`.
 ///
 /// If `Self: Iterator`, then `<Self as Iterator>::__iterator_get_unchecked(&mut self, idx)`
 /// must be safe to call provided the following conditions are met.
 ///
 /// 1. `0 <= idx` and `idx < self.size()`.
 /// 2. If `Self: !Clone`, then `self.__iterator_get_unchecked(idx)` is never called with the same
 ///    index on `self` more than once.
 /// 3. After `self.__iterator_get_unchecked(idx)` has been called, then `self.next_back()` will
 ///    only be called at most `self.size() - idx - 1` times. If `Self: Clone` and `self` is cloned,
 ///    then this number is calculated for `self` and its clone individually,
 ///    but `self.next_back()` calls that happened before the cloning count for both `self` and the clone.
 /// 4. After `self.__iterator_get_unchecked(idx)` has been called, then only the following methods
 ///    will be called on `self` or on any new clones of `self`:
 ///     * `std::clone::Clone::clone`
 ///     * `std::iter::Iterator::size_hint`
 ///     * `std::iter::DoubleEndedIterator::next_back`
 ///     * `std::iter::ExactSizeIterator::len`
 ///     * `std::iter::Iterator::__iterator_get_unchecked`
 ///     * `std::iter::TrustedRandomAccessNoCoerce::size`
 /// 5. If `T` is a subtype of `Self`, then `self` is allowed to be coerced
 ///    to `T`. If `self` is coerced to `T` after `self.__iterator_get_unchecked(idx)` has already
 ///    been called, then no methods except for the ones listed under 4. are allowed to be called
 ///    on the resulting value of type `T`, either. Multiple such coercion steps are allowed.
 ///    Regarding 2. and 3., the number of times `__iterator_get_unchecked(idx)` or `next_back()` is
 ///    called on `self` and the resulting value of type `T` (and on further coercion results with
 ///    sub-subtypes) are added together and their sums must not exceed the specified bounds.
 ///
 /// Further, given that these conditions are met, it must guarantee that:
 ///
 /// * It does not change the value returned from `size_hint`
 /// * It must be safe to call the methods listed above on `self` after calling
 ///   `self.__iterator_get_unchecked(idx)`, assuming that the required traits are implemented.
 /// * It must also be safe to drop `self` after calling `self.__iterator_get_unchecked(idx)`.
 /// * If `T` is a subtype of `Self`, then it must be safe to coerce `self` to `T`.
 //
 // FIXME: Clarify interaction with SourceIter/InPlaceIterable. Calling `SourceIter::as_inner`
 // after `__iterator_get_unchecked` is supposed to be allowed.
 #[doc(hidden)]
 #[unstable(feature = "trusted_random_access", issue = "none")]
 #[rustc_specialization_trait]
 pub unsafe trait TrustedRandomAccess: TrustedRandomAccessNoCoerce {}

 /// Like [`TrustedRandomAccess`] but without any of the requirements / guarantees around
 /// coercions to subtypes after `__iterator_get_unchecked` (they aren’t allowed here!), and
 /// without the requirement that subtypes / supertypes implement `TrustedRandomAccessNoCoerce`.
 ///
 /// This trait was created in PR #85874 to fix soundness issue #85873 without performance regressions.
 /// It is subject to change as we might want to build a more generally useful (for performance
 /// optimizations) and more sophisticated trait or trait hierarchy that replaces or extends
 /// [`TrustedRandomAccess`] and `TrustedRandomAccessNoCoerce`.
 #[doc(hidden)]
 #[unstable(feature = "trusted_random_access", issue = "none")]
 #[rustc_specialization_trait]
 pub unsafe trait TrustedRandomAccessNoCoerce: Sized {
     // Convenience method.
     fn size(&self) -> usize
     where
         Self: Iterator,
     {
         self.size_hint().0
     }
     /// `true` if getting an iterator element may have side effects.
     /// Remember to take inner iterators into account.
     const MAY_HAVE_SIDE_EFFECT: bool;
 }

 /// Like `Iterator::__iterator_get_unchecked`, but doesn't require the compiler to
 /// know that `U: TrustedRandomAccess`.
 ///
 /// ## Safety
 ///
 /// Same requirements calling `get_unchecked` directly.
 #[doc(hidden)]
 #[inline]
 pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item
 where
     I: Iterator,
 {
     // SAFETY: the caller must uphold the contract for
     // `Iterator::__iterator_get_unchecked`.
     unsafe { it.try_get_unchecked(idx) }
 }

 unsafe trait SpecTrustedRandomAccess: Iterator {
     /// If `Self: TrustedRandomAccess`, it must be safe to call
     /// `Iterator::__iterator_get_unchecked(self, index)`.
     unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item;
 }

 unsafe impl<I: Iterator> SpecTrustedRandomAccess for I {
     default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item {
         panic!("Should only be called on TrustedRandomAccess iterators");
     }
 }

 unsafe impl<I: Iterator + TrustedRandomAccessNoCoerce> SpecTrustedRandomAccess for I {
     #[inline]
     unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
         // SAFETY: the caller must uphold the contract for
         // `Iterator::__iterator_get_unchecked`.
         unsafe { self.__iterator_get_unchecked(index) }
     }
 }
	use crate::cmp;
	use crate::fmt::{self, Debug};
	use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator};
	use crate::iter::{InPlaceIterable, SourceIter, TrustedLen};

	/// An iterator that iterates two other iterators simultaneously.
	///
	/// This `struct` is created by [`zip`] or [`Iterator::zip`].
	/// See their documentation for more.
	#[derive(Clone)]
	#[must_use = "iterators are lazy and do nothing unless consumed"]
	#[stable(feature = "rust1", since = "1.0.0")]
	pub struct Zip<A, B> {
	a: A,
	b: B,
	// index, len and a_len are only used by the specialized version of zip
	index: usize,
	len: usize,
	a_len: usize,
	}
	impl<A: Iterator, B: Iterator> Zip<A, B> {
	pub(in crate::iter) fn new(a: A, b: B) -> Zip<A, B> {
	ZipImpl::new(a, b)
	}
	fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> {
	while let Some(x) = Iterator::next(self) {
	if n == 0 {
	return Some(x);
	}
	n -= 1;
	}
	None
	}
	}

	/// Converts the arguments to iterators and zips them.
	///
	/// See the documentation of [`Iterator::zip`] for more.
	///
	/// # Examples
	///
	/// ```
	/// use std::iter::zip;
	///
	/// let xs = [1, 2, 3];
	/// let ys = [4, 5, 6];
	///
	/// let mut iter = zip(xs, ys);
	///
	/// assert_eq!(iter.next().unwrap(), (1, 4));
	/// assert_eq!(iter.next().unwrap(), (2, 5));
	/// assert_eq!(iter.next().unwrap(), (3, 6));
	/// assert!(iter.next().is_none());
	///
	/// // Nested zips are also possible:
	/// let zs = [7, 8, 9];
	///
	/// let mut iter = zip(zip(xs, ys), zs);
	///
	/// assert_eq!(iter.next().unwrap(), ((1, 4), 7));
	/// assert_eq!(iter.next().unwrap(), ((2, 5), 8));
	/// assert_eq!(iter.next().unwrap(), ((3, 6), 9));
	/// assert!(iter.next().is_none());
	/// ```
	#[stable(feature = "iter_zip", since = "1.59.0")]
	pub fn zip<A, B>(a: A, b: B) -> Zip<A::IntoIter, B::IntoIter>
	where
	A: IntoIterator,
	B: IntoIterator,
	{
	ZipImpl::new(a.into_iter(), b.into_iter())
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A, B> Iterator for Zip<A, B>
	where
	A: Iterator,
	B: Iterator,
	{
	type Item = (A::Item, B::Item);

	#[inline]
	fn next(&mut self) -> Option<Self::Item> {
	ZipImpl::next(self)
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	ZipImpl::size_hint(self)
	}

	#[inline]
	fn nth(&mut self, n: usize) -> Option<Self::Item> {
	ZipImpl::nth(self, n)
	}

	#[inline]
	unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
	where
	Self: TrustedRandomAccessNoCoerce,
	{
	// SAFETY: `ZipImpl::__iterator_get_unchecked` has same safety
	// requirements as `Iterator::__iterator_get_unchecked`.
	unsafe { ZipImpl::get_unchecked(self, idx) }
	}
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A, B> DoubleEndedIterator for Zip<A, B>
	where
	A: DoubleEndedIterator + ExactSizeIterator,
	B: DoubleEndedIterator + ExactSizeIterator,
	{
	#[inline]
	fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
	ZipImpl::next_back(self)
	}
	}

	// Zip specialization trait
	#[doc(hidden)]
	trait ZipImpl<A, B> {
	type Item;
	fn new(a: A, b: B) -> Self;
	fn next(&mut self) -> Option<Self::Item>;
	fn size_hint(&self) -> (usize, Option<usize>);
	fn nth(&mut self, n: usize) -> Option<Self::Item>;
	fn next_back(&mut self) -> Option<Self::Item>
	where
	A: DoubleEndedIterator + ExactSizeIterator,
	B: DoubleEndedIterator + ExactSizeIterator;
	// This has the same safety requirements as `Iterator::__iterator_get_unchecked`
	unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
	where
	Self: Iterator + TrustedRandomAccessNoCoerce;
	}

	// Work around limitations of specialization, requiring `default` impls to be repeated
	// in intermediary impls.
	macro_rules! zip_impl_general_defaults {
	() => {
	default fn new(a: A, b: B) -> Self {
	Zip {
	a,
	b,
	index: 0, // unused
	len: 0, // unused
	a_len: 0, // unused
	}
	}

	#[inline]
	default fn next(&mut self) -> Option<(A::Item, B::Item)> {
	let x = self.a.next()?;
	let y = self.b.next()?;
	Some((x, y))
	}

	#[inline]
	default fn nth(&mut self, n: usize) -> Option<Self::Item> {
	self.super_nth(n)
	}

	#[inline]
	default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
	where
	A: DoubleEndedIterator + ExactSizeIterator,
	B: DoubleEndedIterator + ExactSizeIterator,
	{
	// The function body below only uses `self.a/b.len()` and `self.a/b.next_back()`
	// and doesn’t call `next_back` too often, so this implementation is safe in
	// the `TrustedRandomAccessNoCoerce` specialization

	let a_sz = self.a.len();
	let b_sz = self.b.len();
	if a_sz != b_sz {
	// Adjust a, b to equal length
	if a_sz > b_sz {
	for _ in 0..a_sz - b_sz {
	self.a.next_back();
	}
	} else {
	for _ in 0..b_sz - a_sz {
	self.b.next_back();
	}
	}
	}
	match (self.a.next_back(), self.b.next_back()) {
	(Some(x), Some(y)) => Some((x, y)),
	(None, None) => None,
	_ => unreachable!(),
	}
	}
	};
	}

	// General Zip impl
	#[doc(hidden)]
	impl<A, B> ZipImpl<A, B> for Zip<A, B>
	where
	A: Iterator,
	B: Iterator,
	{
	type Item = (A::Item, B::Item);

	zip_impl_general_defaults! {}

	#[inline]
	default fn size_hint(&self) -> (usize, Option<usize>) {
	let (a_lower, a_upper) = self.a.size_hint();
	let (b_lower, b_upper) = self.b.size_hint();

	let lower = cmp::min(a_lower, b_lower);

	let upper = match (a_upper, b_upper) {
	(Some(x), Some(y)) => Some(cmp::min(x, y)),
	(Some(x), None) => Some(x),
	(None, Some(y)) => Some(y),
	(None, None) => None,
	};

	(lower, upper)
	}

	default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item
	where
	Self: TrustedRandomAccessNoCoerce,
	{
	unreachable!("Always specialized");
	}
	}

	#[doc(hidden)]
	impl<A, B> ZipImpl<A, B> for Zip<A, B>
	where
	A: TrustedRandomAccessNoCoerce + Iterator,
	B: TrustedRandomAccessNoCoerce + Iterator,
	{
	zip_impl_general_defaults! {}

	#[inline]
	default fn size_hint(&self) -> (usize, Option<usize>) {
	let size = cmp::min(self.a.size(), self.b.size());
	(size, Some(size))
	}

	#[inline]
	unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item {
	let idx = self.index + idx;
	// SAFETY: the caller must uphold the contract for
	// `Iterator::__iterator_get_unchecked`.
	unsafe { (self.a.__iterator_get_unchecked(idx), self.b.__iterator_get_unchecked(idx)) }
	}
	}

	#[doc(hidden)]
	impl<A, B> ZipImpl<A, B> for Zip<A, B>
	where
	A: TrustedRandomAccess + Iterator,
	B: TrustedRandomAccess + Iterator,
	{
	fn new(a: A, b: B) -> Self {
	let a_len = a.size();
	let len = cmp::min(a_len, b.size());
	Zip { a, b, index: 0, len, a_len }
	}

	#[inline]
	fn next(&mut self) -> Option<(A::Item, B::Item)> {
	if self.index < self.len {
	let i = self.index;
	// since get_unchecked executes code which can panic we increment the counters beforehand
	// so that the same index won't be accessed twice, as required by TrustedRandomAccess
	self.index += 1;
	// SAFETY: `i` is smaller than `self.len`, thus smaller than `self.a.len()` and `self.b.len()`
	unsafe {
	Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
	}
	} else if A::MAY_HAVE_SIDE_EFFECT && self.index < self.a_len {
	let i = self.index;
	// as above, increment before executing code that may panic
	self.index += 1;
	self.len += 1;
	// match the base implementation's potential side effects
	// SAFETY: we just checked that `i` < `self.a.len()`
	unsafe {
	self.a.__iterator_get_unchecked(i);
	}
	None
	} else {
	None
	}
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	let len = self.len - self.index;
	(len, Some(len))
	}

	#[inline]
	fn nth(&mut self, n: usize) -> Option<Self::Item> {
	let delta = cmp::min(n, self.len - self.index);
	let end = self.index + delta;
	while self.index < end {
	let i = self.index;
	// since get_unchecked executes code which can panic we increment the counters beforehand
	// so that the same index won't be accessed twice, as required by TrustedRandomAccess
	self.index += 1;
	if A::MAY_HAVE_SIDE_EFFECT {
	// SAFETY: the usage of `cmp::min` to calculate `delta`
	// ensures that `end` is smaller than or equal to `self.len`,
	// so `i` is also smaller than `self.len`.
	unsafe {
	self.a.__iterator_get_unchecked(i);
	}
	}
	if B::MAY_HAVE_SIDE_EFFECT {
	// SAFETY: same as above.
	unsafe {
	self.b.__iterator_get_unchecked(i);
	}
	}
	}

	self.super_nth(n - delta)
	}

	#[inline]
	fn next_back(&mut self) -> Option<(A::Item, B::Item)>
	where
	A: DoubleEndedIterator + ExactSizeIterator,
	B: DoubleEndedIterator + ExactSizeIterator,
	{
	if A::MAY_HAVE_SIDE_EFFECT \|\| B::MAY_HAVE_SIDE_EFFECT {
	let sz_a = self.a.size();
	let sz_b = self.b.size();
	// Adjust a, b to equal length, make sure that only the first call
	// of `next_back` does this, otherwise we will break the restriction
	// on calls to `self.next_back()` after calling `get_unchecked()`.
	if sz_a != sz_b {
	let sz_a = self.a.size();
	if A::MAY_HAVE_SIDE_EFFECT && sz_a > self.len {
	for _ in 0..sz_a - self.len {
	// since next_back() may panic we increment the counters beforehand
	// to keep Zip's state in sync with the underlying iterator source
	self.a_len -= 1;
	self.a.next_back();
	}
	debug_assert_eq!(self.a_len, self.len);
	}
	let sz_b = self.b.size();
	if B::MAY_HAVE_SIDE_EFFECT && sz_b > self.len {
	for _ in 0..sz_b - self.len {
	self.b.next_back();
	}
	}
	}
	}
	if self.index < self.len {
	// since get_unchecked executes code which can panic we increment the counters beforehand
	// so that the same index won't be accessed twice, as required by TrustedRandomAccess
	self.len -= 1;
	self.a_len -= 1;
	let i = self.len;
	// SAFETY: `i` is smaller than the previous value of `self.len`,
	// which is also smaller than or equal to `self.a.len()` and `self.b.len()`
	unsafe {
	Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
	}
	} else {
	None
	}
	}
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A, B> ExactSizeIterator for Zip<A, B>
	where
	A: ExactSizeIterator,
	B: ExactSizeIterator,
	{
	}

	#[doc(hidden)]
	#[unstable(feature = "trusted_random_access", issue = "none")]
	unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
	where
	A: TrustedRandomAccess,
	B: TrustedRandomAccess,
	{
	}

	#[doc(hidden)]
	#[unstable(feature = "trusted_random_access", issue = "none")]
	unsafe impl<A, B> TrustedRandomAccessNoCoerce for Zip<A, B>
	where
	A: TrustedRandomAccessNoCoerce,
	B: TrustedRandomAccessNoCoerce,
	{
	const MAY_HAVE_SIDE_EFFECT: bool = A::MAY_HAVE_SIDE_EFFECT \|\| B::MAY_HAVE_SIDE_EFFECT;
	}

	#[stable(feature = "fused", since = "1.26.0")]
	impl<A, B> FusedIterator for Zip<A, B>
	where
	A: FusedIterator,
	B: FusedIterator,
	{
	}

	#[unstable(feature = "trusted_len", issue = "37572")]
	unsafe impl<A, B> TrustedLen for Zip<A, B>
	where
	A: TrustedLen,
	B: TrustedLen,
	{
	}

	// Arbitrarily selects the left side of the zip iteration as extractable "source"
	// it would require negative trait bounds to be able to try both
	#[unstable(issue = "none", feature = "inplace_iteration")]
	unsafe impl<A, B> SourceIter for Zip<A, B>
	where
	A: SourceIter,
	{
	type Source = A::Source;

	#[inline]
	unsafe fn as_inner(&mut self) -> &mut A::Source {
	// SAFETY: unsafe function forwarding to unsafe function with the same requirements
	unsafe { SourceIter::as_inner(&mut self.a) }
	}
	}

	// Since SourceIter forwards the left hand side we do the same here
	#[unstable(issue = "none", feature = "inplace_iteration")]
	unsafe impl<A: InPlaceIterable, B: Iterator> InPlaceIterable for Zip<A, B> {}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A: Debug, B: Debug> Debug for Zip<A, B> {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	ZipFmt::fmt(self, f)
	}
	}

	trait ZipFmt<A, B> {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
	}

	impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> {
	default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	f.debug_struct("Zip").field("a", &self.a).field("b", &self.b).finish()
	}
	}

	impl<A: Debug + TrustedRandomAccessNoCoerce, B: Debug + TrustedRandomAccessNoCoerce> ZipFmt<A, B>
	for Zip<A, B>
	{
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	// It's not safe to call fmt on the contained iterators, since once
	// we start iterating they're in strange, potentially unsafe, states.
	f.debug_struct("Zip").finish()
	}
	}

	/// An iterator whose items are random-accessible efficiently
	///
	/// # Safety
	///
	/// The iterator's `size_hint` must be exact and cheap to call.
	///
	/// `TrustedRandomAccessNoCoerce::size` may not be overridden.
	///
	/// All subtypes and all supertypes of `Self` must also implement `TrustedRandomAccess`.
	/// In particular, this means that types with non-invariant parameters usually can not have
	/// an impl for `TrustedRandomAccess` that depends on any trait bounds on such parameters, except
	/// for bounds that come from the respective struct/enum definition itself, or bounds involving
	/// traits that themselves come with a guarantee similar to this one.
	///
	/// If `Self: ExactSizeIterator` then `self.len()` must always produce results consistent
	/// with `self.size()`.
	///
	/// If `Self: Iterator`, then `<Self as Iterator>::__iterator_get_unchecked(&mut self, idx)`
	/// must be safe to call provided the following conditions are met.
	///
	/// 1. `0 <= idx` and `idx < self.size()`.
	/// 2. If `Self: !Clone`, then `self.__iterator_get_unchecked(idx)` is never called with the same
	/// index on `self` more than once.
	/// 3. After `self.__iterator_get_unchecked(idx)` has been called, then `self.next_back()` will
	/// only be called at most `self.size() - idx - 1` times. If `Self: Clone` and `self` is cloned,
	/// then this number is calculated for `self` and its clone individually,
	/// but `self.next_back()` calls that happened before the cloning count for both `self` and the clone.
	/// 4. After `self.__iterator_get_unchecked(idx)` has been called, then only the following methods
	/// will be called on `self` or on any new clones of `self`:
	/// * `std::clone::Clone::clone`
	/// * `std::iter::Iterator::size_hint`
	/// * `std::iter::DoubleEndedIterator::next_back`
	/// * `std::iter::ExactSizeIterator::len`
	/// * `std::iter::Iterator::__iterator_get_unchecked`
	/// * `std::iter::TrustedRandomAccessNoCoerce::size`
	/// 5. If `T` is a subtype of `Self`, then `self` is allowed to be coerced
	/// to `T`. If `self` is coerced to `T` after `self.__iterator_get_unchecked(idx)` has already
	/// been called, then no methods except for the ones listed under 4. are allowed to be called
	/// on the resulting value of type `T`, either. Multiple such coercion steps are allowed.
	/// Regarding 2. and 3., the number of times `__iterator_get_unchecked(idx)` or `next_back()` is
	/// called on `self` and the resulting value of type `T` (and on further coercion results with
	/// sub-subtypes) are added together and their sums must not exceed the specified bounds.
	///
	/// Further, given that these conditions are met, it must guarantee that:
	///
	/// * It does not change the value returned from `size_hint`
	/// * It must be safe to call the methods listed above on `self` after calling
	/// `self.__iterator_get_unchecked(idx)`, assuming that the required traits are implemented.
	/// * It must also be safe to drop `self` after calling `self.__iterator_get_unchecked(idx)`.
	/// * If `T` is a subtype of `Self`, then it must be safe to coerce `self` to `T`.
	//
	// FIXME: Clarify interaction with SourceIter/InPlaceIterable. Calling `SourceIter::as_inner`
	// after `__iterator_get_unchecked` is supposed to be allowed.
	#[doc(hidden)]
	#[unstable(feature = "trusted_random_access", issue = "none")]
	#[rustc_specialization_trait]
	pub unsafe trait TrustedRandomAccess: TrustedRandomAccessNoCoerce {}

	/// Like [`TrustedRandomAccess`] but without any of the requirements / guarantees around
	/// coercions to subtypes after `__iterator_get_unchecked` (they aren’t allowed here!), and
	/// without the requirement that subtypes / supertypes implement `TrustedRandomAccessNoCoerce`.
	///
	/// This trait was created in PR #85874 to fix soundness issue #85873 without performance regressions.
	/// It is subject to change as we might want to build a more generally useful (for performance
	/// optimizations) and more sophisticated trait or trait hierarchy that replaces or extends
	/// [`TrustedRandomAccess`] and `TrustedRandomAccessNoCoerce`.
	#[doc(hidden)]
	#[unstable(feature = "trusted_random_access", issue = "none")]
	#[rustc_specialization_trait]
	pub unsafe trait TrustedRandomAccessNoCoerce: Sized {
	// Convenience method.
	fn size(&self) -> usize
	where
	Self: Iterator,
	{
	self.size_hint().0
	}
	/// `true` if getting an iterator element may have side effects.
	/// Remember to take inner iterators into account.
	const MAY_HAVE_SIDE_EFFECT: bool;
	}

	/// Like `Iterator::__iterator_get_unchecked`, but doesn't require the compiler to
	/// know that `U: TrustedRandomAccess`.
	///
	/// ## Safety
	///
	/// Same requirements calling `get_unchecked` directly.
	#[doc(hidden)]
	#[inline]
	pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item
	where
	I: Iterator,
	{
	// SAFETY: the caller must uphold the contract for
	// `Iterator::__iterator_get_unchecked`.
	unsafe { it.try_get_unchecked(idx) }
	}

	unsafe trait SpecTrustedRandomAccess: Iterator {
	/// If `Self: TrustedRandomAccess`, it must be safe to call
	/// `Iterator::__iterator_get_unchecked(self, index)`.
	unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item;
	}

	unsafe impl<I: Iterator> SpecTrustedRandomAccess for I {
	default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item {
	panic!("Should only be called on TrustedRandomAccess iterators");
	}
	}

	unsafe impl<I: Iterator + TrustedRandomAccessNoCoerce> SpecTrustedRandomAccess for I {
	#[inline]
	unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
	// SAFETY: the caller must uphold the contract for
	// `Iterator::__iterator_get_unchecked`.
	unsafe { self.__iterator_get_unchecked(index) }
	}
	}