From dc0db358abe19481e475e10c32149b53370f1a1c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 30 May 2024 05:57:31 +0200 Subject: Merging upstream version 1.72.1+dfsg1. Signed-off-by: Daniel Baumann --- library/core/src/iter/adapters/flatten.rs | 12 +- library/core/src/iter/adapters/step_by.rs | 411 +++++++++++++++++++++++++--- library/core/src/iter/range.rs | 25 +- library/core/src/iter/sources/successors.rs | 2 +- library/core/src/iter/traits/iterator.rs | 8 +- library/core/src/iter/traits/marker.rs | 2 +- 6 files changed, 400 insertions(+), 60 deletions(-) (limited to 'library/core/src/iter') diff --git a/library/core/src/iter/adapters/flatten.rs b/library/core/src/iter/adapters/flatten.rs index 2568aaf34..d3e454563 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -310,7 +310,7 @@ where /// Real logic of both `Flatten` and `FlatMap` which simply delegate to /// this type. #[derive(Clone, Debug)] -#[unstable(feature = "trusted_len", issue = "37572")] +#[cfg_attr(bootstrap, unstable(feature = "trusted_len", issue = "37572"))] struct FlattenCompat { iter: Fuse, frontiter: Option, @@ -464,7 +464,7 @@ where } } -#[unstable(feature = "trusted_len", issue = "37572")] +#[cfg_attr(bootstrap, unstable(feature = "trusted_len", issue = "37572"))] impl Iterator for FlattenCompat where I: Iterator>, @@ -579,7 +579,7 @@ where } } -#[unstable(feature = "trusted_len", issue = "37572")] +#[cfg_attr(bootstrap, unstable(feature = "trusted_len", issue = "37572"))] impl DoubleEndedIterator for FlattenCompat where I: DoubleEndedIterator>, @@ -649,7 +649,7 @@ where } } -#[unstable(feature = "trusted_len", issue = "37572")] +#[cfg_attr(bootstrap, unstable(feature = "trusted_len", issue = "37572"))] unsafe impl TrustedLen for FlattenCompat::IntoIter> where @@ -657,7 +657,7 @@ where { } -#[unstable(feature = "trusted_len", issue = "37572")] +#[cfg_attr(bootstrap, unstable(feature = "trusted_len", issue = "37572"))] unsafe impl<'a, const N: usize, I, T> TrustedLen for FlattenCompat::IntoIter> where @@ -665,7 +665,7 @@ where { } -#[unstable(feature = "trusted_len", issue = "37572")] +#[cfg_attr(bootstrap, unstable(feature = "trusted_len", issue = "37572"))] unsafe impl<'a, const N: usize, I, T> TrustedLen for FlattenCompat::IntoIter> where diff --git a/library/core/src/iter/adapters/step_by.rs b/library/core/src/iter/adapters/step_by.rs index 4252c34a0..7f58f7d17 100644 --- a/library/core/src/iter/adapters/step_by.rs +++ b/library/core/src/iter/adapters/step_by.rs @@ -1,4 +1,9 @@ -use crate::{intrinsics, iter::from_fn, ops::Try}; +use crate::convert::TryFrom; +use crate::{ + intrinsics, + iter::{from_fn, TrustedLen}, + ops::{Range, Try}, +}; /// An iterator for stepping iterators by a custom amount. /// @@ -11,14 +16,22 @@ use crate::{intrinsics, iter::from_fn, ops::Try}; #[stable(feature = "iterator_step_by", since = "1.28.0")] #[derive(Clone, Debug)] pub struct StepBy { + /// This field is guaranteed to be preprocessed by the specialized `SpecRangeSetup::setup` + /// in the constructor. + /// For most iterators that processing is a no-op, but for Range<{integer}> types it is lossy + /// which means the inner iterator cannot be returned to user code. + /// Additionally this type-dependent preprocessing means specialized implementations + /// cannot be used interchangeably. iter: I, step: usize, first_take: bool, } impl StepBy { + #[inline] pub(in crate::iter) fn new(iter: I, step: usize) -> StepBy { assert!(step != 0); + let iter = >::setup(iter, step); StepBy { iter, step: step - 1, first_take: true } } } @@ -32,16 +45,174 @@ where #[inline] fn next(&mut self) -> Option { + self.spec_next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.spec_size_hint() + } + + #[inline] + fn nth(&mut self, n: usize) -> Option { + self.spec_nth(n) + } + + fn try_fold(&mut self, acc: Acc, f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.spec_try_fold(acc, f) + } + + #[inline] + fn fold(self, acc: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.spec_fold(acc, f) + } +} + +impl StepBy +where + I: ExactSizeIterator, +{ + // The zero-based index starting from the end of the iterator of the + // last element. Used in the `DoubleEndedIterator` implementation. + fn next_back_index(&self) -> usize { + let rem = self.iter.len() % (self.step + 1); if self.first_take { - self.first_take = false; - self.iter.next() + if rem == 0 { self.step } else { rem - 1 } } else { - self.iter.nth(self.step) + rem } } +} +#[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")] +impl DoubleEndedIterator for StepBy +where + I: DoubleEndedIterator + ExactSizeIterator, +{ #[inline] - fn size_hint(&self) -> (usize, Option) { + fn next_back(&mut self) -> Option { + self.spec_next_back() + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option { + self.spec_nth_back(n) + } + + fn try_rfold(&mut self, init: Acc, f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.spec_try_rfold(init, f) + } + + #[inline] + fn rfold(self, init: Acc, f: F) -> Acc + where + Self: Sized, + F: FnMut(Acc, Self::Item) -> Acc, + { + self.spec_rfold(init, f) + } +} + +// StepBy can only make the iterator shorter, so the len will still fit. +#[stable(feature = "iterator_step_by", since = "1.28.0")] +impl ExactSizeIterator for StepBy where I: ExactSizeIterator {} + +trait SpecRangeSetup { + fn setup(inner: T, step: usize) -> T; +} + +impl SpecRangeSetup for T { + #[inline] + default fn setup(inner: T, _step: usize) -> T { + inner + } +} + +/// Specialization trait to optimize `StepBy>` iteration. +/// +/// # Safety +/// +/// Technically this is safe to implement (look ma, no unsafe!), but in reality +/// a lot of unsafe code relies on ranges over integers being correct. +/// +/// For correctness *all* public StepBy methods must be specialized +/// because `setup` drastically alters the meaning of the struct fields so that mixing +/// different implementations would lead to incorrect results. +unsafe trait StepByImpl { + type Item; + + fn spec_next(&mut self) -> Option; + + fn spec_size_hint(&self) -> (usize, Option); + + fn spec_nth(&mut self, n: usize) -> Option; + + fn spec_try_fold(&mut self, acc: Acc, f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try; + + fn spec_fold(self, acc: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc; +} + +/// Specialization trait for double-ended iteration. +/// +/// See also: `StepByImpl` +/// +/// # Safety +/// +/// The specializations must be implemented together with `StepByImpl` +/// where applicable. I.e. if `StepBy` does support backwards iteration +/// for a given iterator and that is specialized for forward iteration then +/// it must also be specialized for backwards iteration. +unsafe trait StepByBackImpl { + type Item; + + fn spec_next_back(&mut self) -> Option + where + I: DoubleEndedIterator + ExactSizeIterator; + + fn spec_nth_back(&mut self, n: usize) -> Option + where + I: DoubleEndedIterator + ExactSizeIterator; + + fn spec_try_rfold(&mut self, init: Acc, f: F) -> R + where + I: DoubleEndedIterator + ExactSizeIterator, + F: FnMut(Acc, Self::Item) -> R, + R: Try; + + fn spec_rfold(self, init: Acc, f: F) -> Acc + where + I: DoubleEndedIterator + ExactSizeIterator, + F: FnMut(Acc, Self::Item) -> Acc; +} + +unsafe impl StepByImpl for StepBy { + type Item = I::Item; + + #[inline] + default fn spec_next(&mut self) -> Option { + let step_size = if self.first_take { 0 } else { self.step }; + self.first_take = false; + self.iter.nth(step_size) + } + + #[inline] + default fn spec_size_hint(&self) -> (usize, Option) { #[inline] fn first_size(step: usize) -> impl Fn(usize) -> usize { move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) } @@ -64,7 +235,7 @@ where } #[inline] - fn nth(&mut self, mut n: usize) -> Option { + default fn spec_nth(&mut self, mut n: usize) -> Option { if self.first_take { self.first_take = false; let first = self.iter.next(); @@ -108,7 +279,7 @@ where } } - fn try_fold(&mut self, mut acc: Acc, mut f: F) -> R + default fn spec_try_fold(&mut self, mut acc: Acc, mut f: F) -> R where F: FnMut(Acc, Self::Item) -> R, R: Try, @@ -128,7 +299,7 @@ where from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f) } - fn fold(mut self, mut acc: Acc, mut f: F) -> Acc + default fn spec_fold(mut self, mut acc: Acc, mut f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { @@ -148,34 +319,16 @@ where } } -impl StepBy -where - I: ExactSizeIterator, -{ - // The zero-based index starting from the end of the iterator of the - // last element. Used in the `DoubleEndedIterator` implementation. - fn next_back_index(&self) -> usize { - let rem = self.iter.len() % (self.step + 1); - if self.first_take { - if rem == 0 { self.step } else { rem - 1 } - } else { - rem - } - } -} +unsafe impl StepByBackImpl for StepBy { + type Item = I::Item; -#[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")] -impl DoubleEndedIterator for StepBy -where - I: DoubleEndedIterator + ExactSizeIterator, -{ #[inline] - fn next_back(&mut self) -> Option { + default fn spec_next_back(&mut self) -> Option { self.iter.nth_back(self.next_back_index()) } #[inline] - fn nth_back(&mut self, n: usize) -> Option { + default fn spec_nth_back(&mut self, n: usize) -> Option { // `self.iter.nth_back(usize::MAX)` does the right thing here when `n` // is out of bounds because the length of `self.iter` does not exceed // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is @@ -184,7 +337,7 @@ where self.iter.nth_back(n) } - fn try_rfold(&mut self, init: Acc, mut f: F) -> R + default fn spec_try_rfold(&mut self, init: Acc, mut f: F) -> R where F: FnMut(Acc, Self::Item) -> R, R: Try, @@ -207,10 +360,10 @@ where } #[inline] - fn rfold(mut self, init: Acc, mut f: F) -> Acc + default fn spec_rfold(mut self, init: Acc, mut f: F) -> Acc where Self: Sized, - F: FnMut(Acc, Self::Item) -> Acc, + F: FnMut(Acc, I::Item) -> Acc, { #[inline] fn nth_back( @@ -230,6 +383,192 @@ where } } -// StepBy can only make the iterator shorter, so the len will still fit. -#[stable(feature = "iterator_step_by", since = "1.28.0")] -impl ExactSizeIterator for StepBy where I: ExactSizeIterator {} +/// For these implementations, `SpecRangeSetup` calculates the number +/// of iterations that will be needed and stores that in `iter.end`. +/// +/// The various iterator implementations then rely on that to not need +/// overflow checking, letting loops just be counted instead. +/// +/// These only work for unsigned types, and will need to be reworked +/// if you want to use it to specialize on signed types. +/// +/// Currently these are only implemented for integers up to usize due to +/// correctness issues around ExactSizeIterator impls on 16bit platforms. +/// And since ExactSizeIterator is a prerequisite for backwards iteration +/// and we must consistently specialize backwards and forwards iteration +/// that makes the situation complicated enough that it's not covered +/// for now. +macro_rules! spec_int_ranges { + ($($t:ty)*) => ($( + + const _: () = assert!(usize::BITS >= <$t>::BITS); + + impl SpecRangeSetup> for Range<$t> { + #[inline] + fn setup(mut r: Range<$t>, step: usize) -> Range<$t> { + let inner_len = r.size_hint().0; + // If step exceeds $t::MAX, then the count will be at most 1 and + // thus always fit into $t. + let yield_count = inner_len.div_ceil(step); + // Turn the range end into an iteration counter + r.end = yield_count as $t; + r + } + } + + unsafe impl StepByImpl> for StepBy> { + #[inline] + fn spec_next(&mut self) -> Option<$t> { + // if a step size larger than the type has been specified fall back to + // t::MAX, in which case remaining will be at most 1. + // The `+ 1` can't overflow since the constructor substracted 1 from the original value. + let step = <$t>::try_from(self.step + 1).unwrap_or(<$t>::MAX); + let remaining = self.iter.end; + if remaining > 0 { + let val = self.iter.start; + // this can only overflow during the last step, after which the value + // will not be used + self.iter.start = val.wrapping_add(step); + self.iter.end = remaining - 1; + Some(val) + } else { + None + } + } + + #[inline] + fn spec_size_hint(&self) -> (usize, Option) { + let remaining = self.iter.end as usize; + (remaining, Some(remaining)) + } + + // The methods below are all copied from the Iterator trait default impls. + // We have to repeat them here so that the specialization overrides the StepByImpl defaults + + #[inline] + fn spec_nth(&mut self, n: usize) -> Option { + self.advance_by(n).ok()?; + self.next() + } + + #[inline] + fn spec_try_fold(&mut self, init: Acc, mut f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try + { + let mut accum = init; + while let Some(x) = self.next() { + accum = f(accum, x)?; + } + try { accum } + } + + #[inline] + fn spec_fold(self, init: Acc, mut f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc + { + // if a step size larger than the type has been specified fall back to + // t::MAX, in which case remaining will be at most 1. + let step = <$t>::try_from(self.step + 1).unwrap_or(<$t>::MAX); + let remaining = self.iter.end; + let mut acc = init; + let mut val = self.iter.start; + for _ in 0..remaining { + acc = f(acc, val); + // this can only overflow during the last step, after which the value + // will no longer be used + val = val.wrapping_add(step); + } + acc + } + } + + /// Safety: This macro is only applied to ranges over types <= usize + /// which means the inner length is guaranteed to fit into a usize and so + /// the outer length calculation won't encounter clamped values + #[unstable(feature = "trusted_len", issue = "37572")] + unsafe impl TrustedLen for StepBy> {} + )*) +} + +macro_rules! spec_int_ranges_r { + ($($t:ty)*) => ($( + const _: () = assert!(usize::BITS >= <$t>::BITS); + + unsafe impl StepByBackImpl> for StepBy> { + + #[inline] + fn spec_next_back(&mut self) -> Option + where Range<$t>: DoubleEndedIterator + ExactSizeIterator, + { + let step = (self.step + 1) as $t; + let remaining = self.iter.end; + if remaining > 0 { + let start = self.iter.start; + self.iter.end = remaining - 1; + Some(start + step * (remaining - 1)) + } else { + None + } + } + + // The methods below are all copied from the Iterator trait default impls. + // We have to repeat them here so that the specialization overrides the StepByImplBack defaults + + #[inline] + fn spec_nth_back(&mut self, n: usize) -> Option + where Self: DoubleEndedIterator, + { + if self.advance_back_by(n).is_err() { + return None; + } + self.next_back() + } + + #[inline] + fn spec_try_rfold(&mut self, init: Acc, mut f: F) -> R + where + Self: DoubleEndedIterator, + F: FnMut(Acc, Self::Item) -> R, + R: Try + { + let mut accum = init; + while let Some(x) = self.next_back() { + accum = f(accum, x)?; + } + try { accum } + } + + #[inline] + fn spec_rfold(mut self, init: Acc, mut f: F) -> Acc + where + Self: DoubleEndedIterator, + F: FnMut(Acc, Self::Item) -> Acc + { + let mut accum = init; + while let Some(x) = self.next_back() { + accum = f(accum, x); + } + accum + } + } + )*) +} + +#[cfg(target_pointer_width = "64")] +spec_int_ranges!(u8 u16 u32 u64 usize); +// DoubleEndedIterator requires ExactSizeIterator, which isn't implemented for Range +#[cfg(target_pointer_width = "64")] +spec_int_ranges_r!(u8 u16 u32 usize); + +#[cfg(target_pointer_width = "32")] +spec_int_ranges!(u8 u16 u32 usize); +#[cfg(target_pointer_width = "32")] +spec_int_ranges_r!(u8 u16 u32 usize); + +#[cfg(target_pointer_width = "16")] +spec_int_ranges!(u8 u16 usize); +#[cfg(target_pointer_width = "16")] +spec_int_ranges_r!(u8 u16 usize); diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs index 0171d8981..462f7170a 100644 --- a/library/core/src/iter/range.rs +++ b/library/core/src/iter/range.rs @@ -619,9 +619,10 @@ impl RangeIteratorImpl for ops::Range { #[inline] fn spec_next(&mut self) -> Option { if self.start < self.end { + let old = self.start; // SAFETY: just checked precondition - let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; - Some(mem::replace(&mut self.start, n)) + self.start = unsafe { Step::forward_unchecked(old, 1) }; + Some(old) } else { None } @@ -629,15 +630,15 @@ impl RangeIteratorImpl for ops::Range { #[inline] fn spec_nth(&mut self, n: usize) -> Option { - if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { + if let Some(plus_n) = Step::forward_checked(self.start, n) { if plus_n < self.end { // SAFETY: just checked precondition - self.start = unsafe { Step::forward_unchecked(plus_n.clone(), 1) }; + self.start = unsafe { Step::forward_unchecked(plus_n, 1) }; return Some(plus_n); } } - self.start = self.end.clone(); + self.start = self.end; None } @@ -655,7 +656,7 @@ impl RangeIteratorImpl for ops::Range { // then steps_between either returns a bound to which we clamp or returns None which // together with the initial inequality implies more than usize::MAX steps. // Otherwise 0 is returned which always safe to use. - self.start = unsafe { Step::forward_unchecked(self.start.clone(), taken) }; + self.start = unsafe { Step::forward_unchecked(self.start, taken) }; NonZeroUsize::new(n - taken).map_or(Ok(()), Err) } @@ -664,8 +665,8 @@ impl RangeIteratorImpl for ops::Range { fn spec_next_back(&mut self) -> Option { if self.start < self.end { // SAFETY: just checked precondition - self.end = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; - Some(self.end.clone()) + self.end = unsafe { Step::backward_unchecked(self.end, 1) }; + Some(self.end) } else { None } @@ -673,15 +674,15 @@ impl RangeIteratorImpl for ops::Range { #[inline] fn spec_nth_back(&mut self, n: usize) -> Option { - if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { + if let Some(minus_n) = Step::backward_checked(self.end, n) { if minus_n > self.start { // SAFETY: just checked precondition self.end = unsafe { Step::backward_unchecked(minus_n, 1) }; - return Some(self.end.clone()); + return Some(self.end); } } - self.end = self.start.clone(); + self.end = self.start; None } @@ -696,7 +697,7 @@ impl RangeIteratorImpl for ops::Range { let taken = available.min(n); // SAFETY: same as the spec_advance_by() implementation - self.end = unsafe { Step::backward_unchecked(self.end.clone(), taken) }; + self.end = unsafe { Step::backward_unchecked(self.end, taken) }; NonZeroUsize::new(n - taken).map_or(Ok(()), Err) } diff --git a/library/core/src/iter/sources/successors.rs b/library/core/src/iter/sources/successors.rs index 99f058a90..6a6cbe905 100644 --- a/library/core/src/iter/sources/successors.rs +++ b/library/core/src/iter/sources/successors.rs @@ -22,7 +22,7 @@ where Successors { next: first, succ } } -/// An new iterator where each successive item is computed based on the preceding one. +/// A new iterator where each successive item is computed based on the preceding one. /// /// This `struct` is created by the [`iter::successors()`] function. /// See its documentation for more. diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index dabfce144..988352283 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -26,13 +26,13 @@ fn _assert_is_object_safe(_: &dyn Iterator) {} #[stable(feature = "rust1", since = "1.0.0")] #[rustc_on_unimplemented( on( - _Self = "std::ops::RangeTo", + any(_Self = "core::ops::RangeTo", _Self = "std::ops::RangeTo"), label = "if you meant to iterate until a value, add a starting value", note = "`..end` is a `RangeTo`, which cannot be iterated on; you might have meant to have a \ bounded `Range`: `0..end`" ), on( - _Self = "std::ops::RangeToInclusive", + any(_Self = "core::ops::RangeToInclusive", _Self = "std::ops::RangeToInclusive"), label = "if you meant to iterate until a value (including it), add a starting value", note = "`..=end` is a `RangeToInclusive`, which cannot be iterated on; you might have meant \ to have a bounded `RangeInclusive`: `0..=end`" @@ -43,7 +43,7 @@ fn _assert_is_object_safe(_: &dyn Iterator) {} ), on(_Self = "&[]", label = "`{Self}` is not an iterator; try calling `.iter()`"), on( - _Self = "std::vec::Vec", + any(_Self = "alloc::vec::Vec", _Self = "std::vec::Vec"), label = "`{Self}` is not an iterator; try calling `.into_iter()` or `.iter()`" ), on( @@ -51,7 +51,7 @@ fn _assert_is_object_safe(_: &dyn Iterator) {} label = "`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`" ), on( - _Self = "std::string::String", + any(_Self = "alloc::string::String", _Self = "std::string::String"), label = "`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`" ), on( diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index af0284823..c21a2aac1 100644 --- a/library/core/src/iter/traits/marker.rs +++ b/library/core/src/iter/traits/marker.rs @@ -86,4 +86,4 @@ pub unsafe trait InPlaceIterable: Iterator {} /// for details. Consumers are free to rely on the invariants in unsafe code. #[unstable(feature = "trusted_step", issue = "85731")] #[rustc_specialization_trait] -pub unsafe trait TrustedStep: Step {} +pub unsafe trait TrustedStep: Step + Copy {} -- cgit v1.2.3