diff options
Diffstat (limited to 'library/core/src/iter/adapters/zip.rs')
| -rw-r--r-- | library/core/src/iter/adapters/zip.rs | 585 |
1 files changed, 585 insertions, 0 deletions
diff --git a/library/core/src/iter/adapters/zip.rs b/library/core/src/iter/adapters/zip.rs new file mode 100644 index 000000000..8153c8cfe --- /dev/null +++ b/library/core/src/iter/adapters/zip.rs @@ -0,0 +1,585 @@ +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) } + } +} |