diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:03:36 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:03:36 +0000 |
commit | 17d40c6057c88f4c432b0d7bac88e1b84cb7e67f (patch) | |
tree | 3f66c4a5918660bb8a758ab6cda5ff8ee4f6cdcd /library/core/src/iter | |
parent | Adding upstream version 1.64.0+dfsg1. (diff) | |
download | rustc-upstream/1.65.0+dfsg1.tar.xz rustc-upstream/1.65.0+dfsg1.zip |
Adding upstream version 1.65.0+dfsg1.upstream/1.65.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'library/core/src/iter')
-rw-r--r-- | library/core/src/iter/adapters/array_chunks.rs | 182 | ||||
-rw-r--r-- | library/core/src/iter/adapters/by_ref_sized.rs | 29 | ||||
-rw-r--r-- | library/core/src/iter/adapters/flatten.rs | 375 | ||||
-rw-r--r-- | library/core/src/iter/adapters/mod.rs | 4 | ||||
-rw-r--r-- | library/core/src/iter/adapters/skip.rs | 27 | ||||
-rw-r--r-- | library/core/src/iter/mod.rs | 2 | ||||
-rw-r--r-- | library/core/src/iter/traits/iterator.rs | 45 |
7 files changed, 506 insertions, 158 deletions
diff --git a/library/core/src/iter/adapters/array_chunks.rs b/library/core/src/iter/adapters/array_chunks.rs new file mode 100644 index 000000000..9b479a9f8 --- /dev/null +++ b/library/core/src/iter/adapters/array_chunks.rs @@ -0,0 +1,182 @@ +use crate::array; +use crate::iter::{ByRefSized, FusedIterator, Iterator}; +use crate::ops::{ControlFlow, NeverShortCircuit, Try}; + +/// An iterator over `N` elements of the iterator at a time. +/// +/// The chunks do not overlap. If `N` does not divide the length of the +/// iterator, then the last up to `N-1` elements will be omitted. +/// +/// This `struct` is created by the [`array_chunks`][Iterator::array_chunks] +/// method on [`Iterator`]. See its documentation for more. +#[derive(Debug, Clone)] +#[must_use = "iterators are lazy and do nothing unless consumed"] +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +pub struct ArrayChunks<I: Iterator, const N: usize> { + iter: I, + remainder: Option<array::IntoIter<I::Item, N>>, +} + +impl<I, const N: usize> ArrayChunks<I, N> +where + I: Iterator, +{ + #[track_caller] + pub(in crate::iter) fn new(iter: I) -> Self { + assert!(N != 0, "chunk size must be non-zero"); + Self { iter, remainder: None } + } + + /// Returns an iterator over the remaining elements of the original iterator + /// that are not going to be returned by this iterator. The returned + /// iterator will yield at most `N-1` elements. + #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] + #[inline] + pub fn into_remainder(self) -> Option<array::IntoIter<I::Item, N>> { + self.remainder + } +} + +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +impl<I, const N: usize> Iterator for ArrayChunks<I, N> +where + I: Iterator, +{ + type Item = [I::Item; N]; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + self.try_for_each(ControlFlow::Break).break_value() + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + let (lower, upper) = self.iter.size_hint(); + + (lower / N, upper.map(|n| n / N)) + } + + #[inline] + fn count(self) -> usize { + self.iter.count() / N + } + + fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>, + { + let mut acc = init; + loop { + match self.iter.next_chunk() { + Ok(chunk) => acc = f(acc, chunk)?, + Err(remainder) => { + // Make sure to not override `self.remainder` with an empty array + // when `next` is called after `ArrayChunks` exhaustion. + self.remainder.get_or_insert(remainder); + + break try { acc }; + } + } + } + } + + fn fold<B, F>(mut self, init: B, f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.try_fold(init, NeverShortCircuit::wrap_mut_2(f)).0 + } +} + +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +impl<I, const N: usize> DoubleEndedIterator for ArrayChunks<I, N> +where + I: DoubleEndedIterator + ExactSizeIterator, +{ + #[inline] + fn next_back(&mut self) -> Option<Self::Item> { + self.try_rfold((), |(), x| ControlFlow::Break(x)).break_value() + } + + fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>, + { + // We are iterating from the back we need to first handle the remainder. + self.next_back_remainder(); + + let mut acc = init; + let mut iter = ByRefSized(&mut self.iter).rev(); + + // NB remainder is handled by `next_back_remainder`, so + // `next_chunk` can't return `Err` with non-empty remainder + // (assuming correct `I as ExactSizeIterator` impl). + while let Ok(mut chunk) = iter.next_chunk() { + // FIXME: do not do double reverse + // (we could instead add `next_chunk_back` for example) + chunk.reverse(); + acc = f(acc, chunk)? + } + + try { acc } + } + + fn rfold<B, F>(mut self, init: B, f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.try_rfold(init, NeverShortCircuit::wrap_mut_2(f)).0 + } +} + +impl<I, const N: usize> ArrayChunks<I, N> +where + I: DoubleEndedIterator + ExactSizeIterator, +{ + /// Updates `self.remainder` such that `self.iter.len` is divisible by `N`. + fn next_back_remainder(&mut self) { + // Make sure to not override `self.remainder` with an empty array + // when `next_back` is called after `ArrayChunks` exhaustion. + if self.remainder.is_some() { + return; + } + + // We use the `ExactSizeIterator` implementation of the underlying + // iterator to know how many remaining elements there are. + let rem = self.iter.len() % N; + + // Take the last `rem` elements out of `self.iter`. + let mut remainder = + // SAFETY: `unwrap_err` always succeeds because x % N < N for all x. + unsafe { self.iter.by_ref().rev().take(rem).next_chunk().unwrap_err_unchecked() }; + + // We used `.rev()` above, so we need to re-reverse the reminder + remainder.as_mut_slice().reverse(); + self.remainder = Some(remainder); + } +} + +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +impl<I, const N: usize> FusedIterator for ArrayChunks<I, N> where I: FusedIterator {} + +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +impl<I, const N: usize> ExactSizeIterator for ArrayChunks<I, N> +where + I: ExactSizeIterator, +{ + #[inline] + fn len(&self) -> usize { + self.iter.len() / N + } + + #[inline] + fn is_empty(&self) -> bool { + self.iter.len() < N + } +} diff --git a/library/core/src/iter/adapters/by_ref_sized.rs b/library/core/src/iter/adapters/by_ref_sized.rs index cc1e8e8a2..477e7117c 100644 --- a/library/core/src/iter/adapters/by_ref_sized.rs +++ b/library/core/src/iter/adapters/by_ref_sized.rs @@ -1,4 +1,4 @@ -use crate::ops::Try; +use crate::ops::{NeverShortCircuit, Try}; /// Like `Iterator::by_ref`, but requiring `Sized` so it can forward generics. /// @@ -8,28 +8,31 @@ use crate::ops::Try; #[derive(Debug)] pub struct ByRefSized<'a, I>(pub &'a mut I); +// The following implementations use UFCS-style, rather than trusting autoderef, +// to avoid accidentally calling the `&mut Iterator` implementations. + #[unstable(feature = "std_internals", issue = "none")] impl<I: Iterator> Iterator for ByRefSized<'_, I> { type Item = I::Item; #[inline] fn next(&mut self) -> Option<Self::Item> { - self.0.next() + I::next(self.0) } #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - self.0.size_hint() + I::size_hint(self.0) } #[inline] fn advance_by(&mut self, n: usize) -> Result<(), usize> { - self.0.advance_by(n) + I::advance_by(self.0, n) } #[inline] fn nth(&mut self, n: usize) -> Option<Self::Item> { - self.0.nth(n) + I::nth(self.0, n) } #[inline] @@ -37,7 +40,8 @@ impl<I: Iterator> Iterator for ByRefSized<'_, I> { where F: FnMut(B, Self::Item) -> B, { - self.0.fold(init, f) + // `fold` needs ownership, so this can't forward directly. + I::try_fold(self.0, init, NeverShortCircuit::wrap_mut_2(f)).0 } #[inline] @@ -46,7 +50,7 @@ impl<I: Iterator> Iterator for ByRefSized<'_, I> { F: FnMut(B, Self::Item) -> R, R: Try<Output = B>, { - self.0.try_fold(init, f) + I::try_fold(self.0, init, f) } } @@ -54,17 +58,17 @@ impl<I: Iterator> Iterator for ByRefSized<'_, I> { impl<I: DoubleEndedIterator> DoubleEndedIterator for ByRefSized<'_, I> { #[inline] fn next_back(&mut self) -> Option<Self::Item> { - self.0.next_back() + I::next_back(self.0) } #[inline] fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { - self.0.advance_back_by(n) + I::advance_back_by(self.0, n) } #[inline] fn nth_back(&mut self, n: usize) -> Option<Self::Item> { - self.0.nth_back(n) + I::nth_back(self.0, n) } #[inline] @@ -72,7 +76,8 @@ impl<I: DoubleEndedIterator> DoubleEndedIterator for ByRefSized<'_, I> { where F: FnMut(B, Self::Item) -> B, { - self.0.rfold(init, f) + // `rfold` needs ownership, so this can't forward directly. + I::try_rfold(self.0, init, NeverShortCircuit::wrap_mut_2(f)).0 } #[inline] @@ -81,6 +86,6 @@ impl<I: DoubleEndedIterator> DoubleEndedIterator for ByRefSized<'_, I> { F: FnMut(B, Self::Item) -> R, R: Try<Output = B>, { - self.0.try_rfold(init, f) + I::try_rfold(self.0, init, f) } } diff --git a/library/core/src/iter/adapters/flatten.rs b/library/core/src/iter/adapters/flatten.rs index 15a120e35..307016c26 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -1,6 +1,6 @@ use crate::fmt; use crate::iter::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map, TrustedLen}; -use crate::ops::Try; +use crate::ops::{ControlFlow, Try}; /// An iterator that maps each element to an iterator, and yields the elements /// of the produced iterators. @@ -73,6 +73,21 @@ where { self.inner.fold(init, fold) } + + #[inline] + fn advance_by(&mut self, n: usize) -> Result<(), usize> { + self.inner.advance_by(n) + } + + #[inline] + fn count(self) -> usize { + self.inner.count() + } + + #[inline] + fn last(self) -> Option<Self::Item> { + self.inner.last() + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -103,6 +118,11 @@ where { self.inner.rfold(init, fold) } + + #[inline] + fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { + self.inner.advance_back_by(n) + } } #[stable(feature = "fused", since = "1.26.0")] @@ -214,6 +234,21 @@ where { self.inner.fold(init, fold) } + + #[inline] + fn advance_by(&mut self, n: usize) -> Result<(), usize> { + self.inner.advance_by(n) + } + + #[inline] + fn count(self) -> usize { + self.inner.count() + } + + #[inline] + fn last(self) -> Option<Self::Item> { + self.inner.last() + } } #[stable(feature = "iterator_flatten", since = "1.29.0")] @@ -244,6 +279,11 @@ where { self.inner.rfold(init, fold) } + + #[inline] + fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { + self.inner.advance_back_by(n) + } } #[stable(feature = "iterator_flatten", since = "1.29.0")] @@ -280,6 +320,144 @@ where } } +impl<I, U> FlattenCompat<I, U> +where + I: Iterator<Item: IntoIterator<IntoIter = U>>, +{ + /// Folds the inner iterators into an accumulator by applying an operation. + /// + /// Folds over the inner iterators, not over their elements. Is used by the `fold`, `count`, + /// and `last` methods. + #[inline] + fn iter_fold<Acc, Fold>(self, mut acc: Acc, mut fold: Fold) -> Acc + where + Fold: FnMut(Acc, U) -> Acc, + { + #[inline] + fn flatten<T: IntoIterator, Acc>( + fold: &mut impl FnMut(Acc, T::IntoIter) -> Acc, + ) -> impl FnMut(Acc, T) -> Acc + '_ { + move |acc, iter| fold(acc, iter.into_iter()) + } + + if let Some(iter) = self.frontiter { + acc = fold(acc, iter); + } + + acc = self.iter.fold(acc, flatten(&mut fold)); + + if let Some(iter) = self.backiter { + acc = fold(acc, iter); + } + + acc + } + + /// Folds over the inner iterators as long as the given function returns successfully, + /// always storing the most recent inner iterator in `self.frontiter`. + /// + /// Folds over the inner iterators, not over their elements. Is used by the `try_fold` and + /// `advance_by` methods. + #[inline] + fn iter_try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, mut fold: Fold) -> R + where + Fold: FnMut(Acc, &mut U) -> R, + R: Try<Output = Acc>, + { + #[inline] + fn flatten<'a, T: IntoIterator, Acc, R: Try<Output = Acc>>( + frontiter: &'a mut Option<T::IntoIter>, + fold: &'a mut impl FnMut(Acc, &mut T::IntoIter) -> R, + ) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, iter| fold(acc, frontiter.insert(iter.into_iter())) + } + + if let Some(iter) = &mut self.frontiter { + acc = fold(acc, iter)?; + } + self.frontiter = None; + + acc = self.iter.try_fold(acc, flatten(&mut self.frontiter, &mut fold))?; + self.frontiter = None; + + if let Some(iter) = &mut self.backiter { + acc = fold(acc, iter)?; + } + self.backiter = None; + + try { acc } + } +} + +impl<I, U> FlattenCompat<I, U> +where + I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U>>, +{ + /// Folds the inner iterators into an accumulator by applying an operation, starting form the + /// back. + /// + /// Folds over the inner iterators, not over their elements. Is used by the `rfold` method. + #[inline] + fn iter_rfold<Acc, Fold>(self, mut acc: Acc, mut fold: Fold) -> Acc + where + Fold: FnMut(Acc, U) -> Acc, + { + #[inline] + fn flatten<T: IntoIterator, Acc>( + fold: &mut impl FnMut(Acc, T::IntoIter) -> Acc, + ) -> impl FnMut(Acc, T) -> Acc + '_ { + move |acc, iter| fold(acc, iter.into_iter()) + } + + if let Some(iter) = self.backiter { + acc = fold(acc, iter); + } + + acc = self.iter.rfold(acc, flatten(&mut fold)); + + if let Some(iter) = self.frontiter { + acc = fold(acc, iter); + } + + acc + } + + /// Folds over the inner iterators in reverse order as long as the given function returns + /// successfully, always storing the most recent inner iterator in `self.backiter`. + /// + /// Folds over the inner iterators, not over their elements. Is used by the `try_rfold` and + /// `advance_back_by` methods. + #[inline] + fn iter_try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, mut fold: Fold) -> R + where + Fold: FnMut(Acc, &mut U) -> R, + R: Try<Output = Acc>, + { + #[inline] + fn flatten<'a, T: IntoIterator, Acc, R: Try>( + backiter: &'a mut Option<T::IntoIter>, + fold: &'a mut impl FnMut(Acc, &mut T::IntoIter) -> R, + ) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, iter| fold(acc, backiter.insert(iter.into_iter())) + } + + if let Some(iter) = &mut self.backiter { + acc = fold(acc, iter)?; + } + self.backiter = None; + + acc = self.iter.try_rfold(acc, flatten(&mut self.backiter, &mut fold))?; + self.backiter = None; + + if let Some(iter) = &mut self.frontiter { + acc = fold(acc, iter)?; + } + self.frontiter = None; + + try { acc } + } +} + impl<I, U> Iterator for FlattenCompat<I, U> where I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, @@ -323,99 +501,74 @@ where } #[inline] - fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R + fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>, { #[inline] - fn flatten<'a, T: IntoIterator, Acc, R: Try<Output = Acc>>( - frontiter: &'a mut Option<T::IntoIter>, - fold: &'a mut impl FnMut(Acc, T::Item) -> R, - ) -> impl FnMut(Acc, T) -> R + 'a { - move |acc, x| { - let mut mid = x.into_iter(); - let r = mid.try_fold(acc, &mut *fold); - *frontiter = Some(mid); - r - } - } - - if let Some(ref mut front) = self.frontiter { - init = front.try_fold(init, &mut fold)?; + fn flatten<U: Iterator, Acc, R: Try<Output = Acc>>( + mut fold: impl FnMut(Acc, U::Item) -> R, + ) -> impl FnMut(Acc, &mut U) -> R { + move |acc, iter| iter.try_fold(acc, &mut fold) } - self.frontiter = None; - init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?; - self.frontiter = None; - - if let Some(ref mut back) = self.backiter { - init = back.try_fold(init, &mut fold)?; - } - self.backiter = None; - - try { init } + self.iter_try_fold(init, flatten(fold)) } #[inline] - fn fold<Acc, Fold>(self, mut init: Acc, mut fold: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc, { #[inline] - fn flatten<T: IntoIterator, Acc>( - fold: &mut impl FnMut(Acc, T::Item) -> Acc, - ) -> impl FnMut(Acc, T) -> Acc + '_ { - move |acc, x| x.into_iter().fold(acc, &mut *fold) - } - - if let Some(front) = self.frontiter { - init = front.fold(init, &mut fold); - } - - init = self.iter.fold(init, flatten(&mut fold)); - - if let Some(back) = self.backiter { - init = back.fold(init, &mut fold); + fn flatten<U: Iterator, Acc>( + mut fold: impl FnMut(Acc, U::Item) -> Acc, + ) -> impl FnMut(Acc, U) -> Acc { + move |acc, iter| iter.fold(acc, &mut fold) } - init + self.iter_fold(init, flatten(fold)) } #[inline] #[rustc_inherit_overflow_checks] fn advance_by(&mut self, n: usize) -> Result<(), usize> { - let mut rem = n; - loop { - if let Some(ref mut front) = self.frontiter { - match front.advance_by(rem) { - ret @ Ok(_) => return ret, - Err(advanced) => rem -= advanced, - } - } - self.frontiter = match self.iter.next() { - Some(iterable) => Some(iterable.into_iter()), - _ => break, + #[inline] + #[rustc_inherit_overflow_checks] + fn advance<U: Iterator>(n: usize, iter: &mut U) -> ControlFlow<(), usize> { + match iter.advance_by(n) { + Ok(()) => ControlFlow::BREAK, + Err(advanced) => ControlFlow::Continue(n - advanced), } } - self.frontiter = None; - - if let Some(ref mut back) = self.backiter { - match back.advance_by(rem) { - ret @ Ok(_) => return ret, - Err(advanced) => rem -= advanced, - } + match self.iter_try_fold(n, advance) { + ControlFlow::Continue(remaining) if remaining > 0 => Err(n - remaining), + _ => Ok(()), } + } - if rem > 0 { - return Err(n - rem); + #[inline] + fn count(self) -> usize { + #[inline] + #[rustc_inherit_overflow_checks] + fn count<U: Iterator>(acc: usize, iter: U) -> usize { + acc + iter.count() } - self.backiter = None; + self.iter_fold(0, count) + } + + #[inline] + fn last(self) -> Option<Self::Item> { + #[inline] + fn last<U: Iterator>(last: Option<U::Item>, iter: U) -> Option<U::Item> { + iter.last().or(last) + } - Ok(()) + self.iter_fold(None, last) } } @@ -438,105 +591,53 @@ where } #[inline] - fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R + fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Output = Acc>, { #[inline] - fn flatten<'a, T: IntoIterator, Acc, R: Try<Output = Acc>>( - backiter: &'a mut Option<T::IntoIter>, - fold: &'a mut impl FnMut(Acc, T::Item) -> R, - ) -> impl FnMut(Acc, T) -> R + 'a - where - T::IntoIter: DoubleEndedIterator, - { - move |acc, x| { - let mut mid = x.into_iter(); - let r = mid.try_rfold(acc, &mut *fold); - *backiter = Some(mid); - r - } + fn flatten<U: DoubleEndedIterator, Acc, R: Try<Output = Acc>>( + mut fold: impl FnMut(Acc, U::Item) -> R, + ) -> impl FnMut(Acc, &mut U) -> R { + move |acc, iter| iter.try_rfold(acc, &mut fold) } - if let Some(ref mut back) = self.backiter { - init = back.try_rfold(init, &mut fold)?; - } - self.backiter = None; - - init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?; - self.backiter = None; - - if let Some(ref mut front) = self.frontiter { - init = front.try_rfold(init, &mut fold)?; - } - self.frontiter = None; - - try { init } + self.iter_try_rfold(init, flatten(fold)) } #[inline] - fn rfold<Acc, Fold>(self, mut init: Acc, mut fold: Fold) -> Acc + fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc, { #[inline] - fn flatten<T: IntoIterator, Acc>( - fold: &mut impl FnMut(Acc, T::Item) -> Acc, - ) -> impl FnMut(Acc, T) -> Acc + '_ - where - T::IntoIter: DoubleEndedIterator, - { - move |acc, x| x.into_iter().rfold(acc, &mut *fold) - } - - if let Some(back) = self.backiter { - init = back.rfold(init, &mut fold); + fn flatten<U: DoubleEndedIterator, Acc>( + mut fold: impl FnMut(Acc, U::Item) -> Acc, + ) -> impl FnMut(Acc, U) -> Acc { + move |acc, iter| iter.rfold(acc, &mut fold) } - init = self.iter.rfold(init, flatten(&mut fold)); - - if let Some(front) = self.frontiter { - init = front.rfold(init, &mut fold); - } - - init + self.iter_rfold(init, flatten(fold)) } #[inline] #[rustc_inherit_overflow_checks] fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { - let mut rem = n; - loop { - if let Some(ref mut back) = self.backiter { - match back.advance_back_by(rem) { - ret @ Ok(_) => return ret, - Err(advanced) => rem -= advanced, - } - } - match self.iter.next_back() { - Some(iterable) => self.backiter = Some(iterable.into_iter()), - _ => break, - } - } - - self.backiter = None; - - if let Some(ref mut front) = self.frontiter { - match front.advance_back_by(rem) { - ret @ Ok(_) => return ret, - Err(advanced) => rem -= advanced, + #[inline] + #[rustc_inherit_overflow_checks] + fn advance<U: DoubleEndedIterator>(n: usize, iter: &mut U) -> ControlFlow<(), usize> { + match iter.advance_back_by(n) { + Ok(()) => ControlFlow::BREAK, + Err(advanced) => ControlFlow::Continue(n - advanced), } } - if rem > 0 { - return Err(n - rem); + match self.iter_try_rfold(n, advance) { + ControlFlow::Continue(remaining) if remaining > 0 => Err(n - remaining), + _ => Ok(()), } - - self.frontiter = None; - - Ok(()) } } diff --git a/library/core/src/iter/adapters/mod.rs b/library/core/src/iter/adapters/mod.rs index 916a26e24..bf4fabad3 100644 --- a/library/core/src/iter/adapters/mod.rs +++ b/library/core/src/iter/adapters/mod.rs @@ -1,6 +1,7 @@ use crate::iter::{InPlaceIterable, Iterator}; use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, NeverShortCircuit, Residual, Try}; +mod array_chunks; mod by_ref_sized; mod chain; mod cloned; @@ -32,6 +33,9 @@ pub use self::{ scan::Scan, skip::Skip, skip_while::SkipWhile, take::Take, take_while::TakeWhile, zip::Zip, }; +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +pub use self::array_chunks::ArrayChunks; + #[unstable(feature = "std_internals", issue = "none")] pub use self::by_ref_sized::ByRefSized; diff --git a/library/core/src/iter/adapters/skip.rs b/library/core/src/iter/adapters/skip.rs index 2c283100f..dbf0ae9ec 100644 --- a/library/core/src/iter/adapters/skip.rs +++ b/library/core/src/iter/adapters/skip.rs @@ -33,21 +33,32 @@ where #[inline] fn next(&mut self) -> Option<I::Item> { if unlikely(self.n > 0) { - self.iter.nth(crate::mem::take(&mut self.n) - 1)?; + self.iter.nth(crate::mem::take(&mut self.n)) + } else { + self.iter.next() } - self.iter.next() } #[inline] fn nth(&mut self, n: usize) -> Option<I::Item> { - // Can't just add n + self.n due to overflow. if self.n > 0 { - let to_skip = self.n; - self.n = 0; - // nth(n) skips n+1 - self.iter.nth(to_skip - 1)?; + let skip: usize = crate::mem::take(&mut self.n); + // Checked add to handle overflow case. + let n = match skip.checked_add(n) { + Some(nth) => nth, + None => { + // In case of overflow, load skip value, before loading `n`. + // Because the amount of elements to iterate is beyond `usize::MAX`, this + // is split into two `nth` calls where the `skip` `nth` call is discarded. + self.iter.nth(skip - 1)?; + n + } + }; + // Load nth element including skip. + self.iter.nth(n) + } else { + self.iter.nth(n) } - self.iter.nth(n) } #[inline] diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs index d5c6aed5b..9514466bd 100644 --- a/library/core/src/iter/mod.rs +++ b/library/core/src/iter/mod.rs @@ -398,6 +398,8 @@ pub use self::traits::{ #[stable(feature = "iter_zip", since = "1.59.0")] pub use self::adapters::zip; +#[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] +pub use self::adapters::ArrayChunks; #[unstable(feature = "std_internals", issue = "none")] pub use self::adapters::ByRefSized; #[stable(feature = "iter_cloned", since = "1.1.0")] diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index 275412b57..b2d08f4b0 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -5,7 +5,7 @@ use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, Residual, Try}; use super::super::try_process; use super::super::ByRefSized; use super::super::TrustedRandomAccessNoCoerce; -use super::super::{Chain, Cloned, Copied, Cycle, Enumerate, Filter, FilterMap, Fuse}; +use super::super::{ArrayChunks, Chain, Cloned, Copied, Cycle, Enumerate, Filter, FilterMap, Fuse}; use super::super::{FlatMap, Flatten}; use super::super::{FromIterator, Intersperse, IntersperseWith, Product, Sum, Zip}; use super::super::{ @@ -3316,6 +3316,49 @@ pub trait Iterator { Cycle::new(self) } + /// Returns an iterator over `N` elements of the iterator at a time. + /// + /// The chunks do not overlap. If `N` does not divide the length of the + /// iterator, then the last up to `N-1` elements will be omitted and can be + /// retrieved from the [`.into_remainder()`][ArrayChunks::into_remainder] + /// function of the iterator. + /// + /// # Panics + /// + /// Panics if `N` is 0. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(iter_array_chunks)] + /// + /// let mut iter = "lorem".chars().array_chunks(); + /// assert_eq!(iter.next(), Some(['l', 'o'])); + /// assert_eq!(iter.next(), Some(['r', 'e'])); + /// assert_eq!(iter.next(), None); + /// assert_eq!(iter.into_remainder().unwrap().as_slice(), &['m']); + /// ``` + /// + /// ``` + /// #![feature(iter_array_chunks)] + /// + /// let data = [1, 1, 2, -2, 6, 0, 3, 1]; + /// // ^-----^ ^------^ + /// for [x, y, z] in data.iter().array_chunks() { + /// assert_eq!(x + y + z, 4); + /// } + /// ``` + #[track_caller] + #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] + fn array_chunks<const N: usize>(self) -> ArrayChunks<Self, N> + where + Self: Sized, + { + ArrayChunks::new(self) + } + /// Sums the elements of an iterator. /// /// Takes each element, adds them together, and returns the result. |