diff options
Diffstat (limited to 'library/core/src/iter')
-rw-r--r-- | library/core/src/iter/adapters/chain.rs | 2 | ||||
-rw-r--r-- | library/core/src/iter/adapters/filter.rs | 55 | ||||
-rw-r--r-- | library/core/src/iter/adapters/filter_map.rs | 62 | ||||
-rw-r--r-- | library/core/src/iter/adapters/flatten.rs | 68 | ||||
-rw-r--r-- | library/core/src/iter/range.rs | 20 | ||||
-rw-r--r-- | library/core/src/iter/sources/empty.rs | 3 | ||||
-rw-r--r-- | library/core/src/iter/traits/collect.rs | 13 | ||||
-rw-r--r-- | library/core/src/iter/traits/iterator.rs | 1 |
8 files changed, 179 insertions, 45 deletions
diff --git a/library/core/src/iter/adapters/chain.rs b/library/core/src/iter/adapters/chain.rs index 75727c3a2..26aa959e6 100644 --- a/library/core/src/iter/adapters/chain.rs +++ b/library/core/src/iter/adapters/chain.rs @@ -15,7 +15,7 @@ use crate::ops::Try; /// /// let a1 = [1, 2, 3]; /// let a2 = [4, 5, 6]; -/// let iter: Chain<Iter<_>, Iter<_>> = a1.iter().chain(a2.iter()); +/// let iter: Chain<Iter<'_, _>, Iter<'_, _>> = a1.iter().chain(a2.iter()); /// ``` #[derive(Clone, Debug)] #[must_use = "iterators are lazy and do nothing unless consumed"] diff --git a/library/core/src/iter/adapters/filter.rs b/library/core/src/iter/adapters/filter.rs index a0afaa326..723657b9e 100644 --- a/library/core/src/iter/adapters/filter.rs +++ b/library/core/src/iter/adapters/filter.rs @@ -1,6 +1,9 @@ use crate::fmt; use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; use crate::ops::Try; +use core::array; +use core::mem::{ManuallyDrop, MaybeUninit}; +use core::ops::ControlFlow; /// An iterator that filters the elements of `iter` with `predicate`. /// @@ -57,6 +60,58 @@ where } #[inline] + fn next_chunk<const N: usize>( + &mut self, + ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> { + let mut array: [MaybeUninit<Self::Item>; N] = MaybeUninit::uninit_array(); + + struct Guard<'a, T> { + array: &'a mut [MaybeUninit<T>], + initialized: usize, + } + + impl<T> Drop for Guard<'_, T> { + #[inline] + fn drop(&mut self) { + if const { crate::mem::needs_drop::<T>() } { + // SAFETY: self.initialized is always <= N, which also is the length of the array. + unsafe { + core::ptr::drop_in_place(MaybeUninit::slice_assume_init_mut( + self.array.get_unchecked_mut(..self.initialized), + )); + } + } + } + } + + let mut guard = Guard { array: &mut array, initialized: 0 }; + + let result = self.iter.try_for_each(|element| { + let idx = guard.initialized; + guard.initialized = idx + (self.predicate)(&element) as usize; + + // SAFETY: Loop conditions ensure the index is in bounds. + unsafe { guard.array.get_unchecked_mut(idx) }.write(element); + + if guard.initialized < N { ControlFlow::Continue(()) } else { ControlFlow::Break(()) } + }); + + let guard = ManuallyDrop::new(guard); + + match result { + ControlFlow::Break(()) => { + // SAFETY: The loop above is only explicitly broken when the array has been fully initialized + Ok(unsafe { MaybeUninit::array_assume_init(array) }) + } + ControlFlow::Continue(()) => { + let initialized = guard.initialized; + // SAFETY: The range is in bounds since the loop breaks when reaching N elements. + Err(unsafe { array::IntoIter::new_unchecked(array, 0..initialized) }) + } + } + } + + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { let (_, upper) = self.iter.size_hint(); (0, upper) // can't know a lower bound, due to the predicate diff --git a/library/core/src/iter/adapters/filter_map.rs b/library/core/src/iter/adapters/filter_map.rs index 6bdf53f7f..693479977 100644 --- a/library/core/src/iter/adapters/filter_map.rs +++ b/library/core/src/iter/adapters/filter_map.rs @@ -1,6 +1,7 @@ -use crate::fmt; use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; +use crate::mem::{ManuallyDrop, MaybeUninit}; use crate::ops::{ControlFlow, Try}; +use crate::{array, fmt}; /// An iterator that uses `f` to both filter and map elements from `iter`. /// @@ -62,6 +63,65 @@ where } #[inline] + fn next_chunk<const N: usize>( + &mut self, + ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> { + let mut array: [MaybeUninit<Self::Item>; N] = MaybeUninit::uninit_array(); + + struct Guard<'a, T> { + array: &'a mut [MaybeUninit<T>], + initialized: usize, + } + + impl<T> Drop for Guard<'_, T> { + #[inline] + fn drop(&mut self) { + if const { crate::mem::needs_drop::<T>() } { + // SAFETY: self.initialized is always <= N, which also is the length of the array. + unsafe { + core::ptr::drop_in_place(MaybeUninit::slice_assume_init_mut( + self.array.get_unchecked_mut(..self.initialized), + )); + } + } + } + } + + let mut guard = Guard { array: &mut array, initialized: 0 }; + + let result = self.iter.try_for_each(|element| { + let idx = guard.initialized; + let val = (self.f)(element); + guard.initialized = idx + val.is_some() as usize; + + // SAFETY: Loop conditions ensure the index is in bounds. + + unsafe { + let opt_payload_at = core::intrinsics::option_payload_ptr(&val); + let dst = guard.array.as_mut_ptr().add(idx); + crate::ptr::copy_nonoverlapping(opt_payload_at.cast(), dst, 1); + crate::mem::forget(val); + }; + + if guard.initialized < N { ControlFlow::Continue(()) } else { ControlFlow::Break(()) } + }); + + let guard = ManuallyDrop::new(guard); + + match result { + ControlFlow::Break(()) => { + // SAFETY: The loop above is only explicitly broken when the array has been fully initialized + Ok(unsafe { MaybeUninit::array_assume_init(array) }) + } + ControlFlow::Continue(()) => { + let initialized = guard.initialized; + // SAFETY: The range is in bounds since the loop breaks when reaching N elements. + Err(unsafe { array::IntoIter::new_unchecked(array, 0..initialized) }) + } + } + } + + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { let (_, upper) = self.iter.size_hint(); (0, upper) // can't know a lower bound, due to the predicate diff --git a/library/core/src/iter/adapters/flatten.rs b/library/core/src/iter/adapters/flatten.rs index 2fd8a5c1d..2568aaf34 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -136,26 +136,12 @@ where } #[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<T, I, F, const N: usize> TrustedLen for FlatMap<I, [T; N], F> +unsafe impl<I, U, F> TrustedLen for FlatMap<I, U, F> where - I: TrustedLen, - F: FnMut(I::Item) -> [T; N], -{ -} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<'a, T, I, F, const N: usize> TrustedLen for FlatMap<I, &'a [T; N], F> -where - I: TrustedLen, - F: FnMut(I::Item) -> &'a [T; N], -{ -} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<'a, T, I, F, const N: usize> TrustedLen for FlatMap<I, &'a mut [T; N], F> -where - I: TrustedLen, - F: FnMut(I::Item) -> &'a mut [T; N], + I: Iterator, + U: IntoIterator, + F: FnMut(I::Item) -> U, + FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>: TrustedLen, { } @@ -298,8 +284,8 @@ where #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<I> TrustedLen for Flatten<I> where - I: TrustedLen, - <I as Iterator>::Item: TrustedConstSize, + I: Iterator<Item: IntoIterator>, + FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>: TrustedLen, { } @@ -324,6 +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")] struct FlattenCompat<I, U> { iter: Fuse<I>, frontiter: Option<U>, @@ -477,6 +464,7 @@ where } } +#[unstable(feature = "trusted_len", issue = "37572")] impl<I, U> Iterator for FlattenCompat<I, U> where I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, @@ -591,6 +579,7 @@ where } } +#[unstable(feature = "trusted_len", issue = "37572")] impl<I, U> DoubleEndedIterator for FlattenCompat<I, U> where I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, @@ -660,6 +649,30 @@ where } } +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl<const N: usize, I, T> TrustedLen + for FlattenCompat<I, <[T; N] as IntoIterator>::IntoIter> +where + I: TrustedLen<Item = [T; N]>, +{ +} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl<'a, const N: usize, I, T> TrustedLen + for FlattenCompat<I, <&'a [T; N] as IntoIterator>::IntoIter> +where + I: TrustedLen<Item = &'a [T; N]>, +{ +} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl<'a, const N: usize, I, T> TrustedLen + for FlattenCompat<I, <&'a mut [T; N] as IntoIterator>::IntoIter> +where + I: TrustedLen<Item = &'a mut [T; N]>, +{ +} + trait ConstSizeIntoIterator: IntoIterator { // FIXME(#31844): convert to an associated const once specialization supports that fn size() -> Option<usize>; @@ -696,19 +709,6 @@ impl<T, const N: usize> ConstSizeIntoIterator for &mut [T; N] { } } -#[doc(hidden)] -#[unstable(feature = "std_internals", issue = "none")] -// FIXME(#20400): Instead of this helper trait there should be multiple impl TrustedLen for Flatten<> -// blocks with different bounds on Iterator::Item but the compiler erroneously considers them overlapping -pub unsafe trait TrustedConstSize: IntoIterator {} - -#[unstable(feature = "std_internals", issue = "none")] -unsafe impl<T, const N: usize> TrustedConstSize for [T; N] {} -#[unstable(feature = "std_internals", issue = "none")] -unsafe impl<T, const N: usize> TrustedConstSize for &'_ [T; N] {} -#[unstable(feature = "std_internals", issue = "none")] -unsafe impl<T, const N: usize> TrustedConstSize for &'_ mut [T; N] {} - #[inline] fn and_then_or_clear<T, U>(opt: &mut Option<T>, f: impl FnOnce(&mut T) -> Option<U>) -> Option<U> { let x = f(opt.as_mut()?); diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs index 37db07429..0171d8981 100644 --- a/library/core/src/iter/range.rs +++ b/library/core/src/iter/range.rs @@ -732,12 +732,18 @@ impl<A: Step> Iterator for ops::Range<A> { } #[inline] - fn min(mut self) -> Option<A> { + fn min(mut self) -> Option<A> + where + A: Ord, + { self.next() } #[inline] - fn max(mut self) -> Option<A> { + fn max(mut self) -> Option<A> + where + A: Ord, + { self.next_back() } @@ -1158,12 +1164,18 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> { } #[inline] - fn min(mut self) -> Option<A> { + fn min(mut self) -> Option<A> + where + A: Ord, + { self.next() } #[inline] - fn max(mut self) -> Option<A> { + fn max(mut self) -> Option<A> + where + A: Ord, + { self.next_back() } diff --git a/library/core/src/iter/sources/empty.rs b/library/core/src/iter/sources/empty.rs index 617dfd123..243df015f 100644 --- a/library/core/src/iter/sources/empty.rs +++ b/library/core/src/iter/sources/empty.rs @@ -81,8 +81,7 @@ impl<T> Clone for Empty<T> { // not #[derive] because that adds a Default bound on T, // which isn't necessary. #[stable(feature = "iter_empty", since = "1.2.0")] -#[rustc_const_unstable(feature = "const_default_impls", issue = "87864")] -impl<T> const Default for Empty<T> { +impl<T> Default for Empty<T> { fn default() -> Empty<T> { Empty(marker::PhantomData) } diff --git a/library/core/src/iter/traits/collect.rs b/library/core/src/iter/traits/collect.rs index e099700e3..0675e5635 100644 --- a/library/core/src/iter/traits/collect.rs +++ b/library/core/src/iter/traits/collect.rs @@ -95,6 +95,16 @@ #[stable(feature = "rust1", since = "1.0.0")] #[rustc_on_unimplemented( on( + _Self = "&[{A}]", + message = "a slice of type `{Self}` cannot be built since we need to store the elements somewhere", + label = "try explicitly collecting into a `Vec<{A}>`", + ), + on( + all(A = "{integer}", any(_Self = "&[{integral}]",)), + message = "a slice of type `{Self}` cannot be built since we need to store the elements somewhere", + label = "try explicitly collecting into a `Vec<{A}>`", + ), + on( _Self = "[{A}]", message = "a slice of type `{Self}` cannot be built since `{Self}` has no definite size", label = "try explicitly collecting into a `Vec<{A}>`", @@ -228,7 +238,6 @@ pub trait FromIterator<A>: Sized { #[rustc_diagnostic_item = "IntoIterator"] #[rustc_skip_array_during_method_dispatch] #[stable(feature = "rust1", since = "1.0.0")] -#[const_trait] pub trait IntoIterator { /// The type of the elements being iterated over. #[stable(feature = "rust1", since = "1.0.0")] @@ -264,7 +273,7 @@ pub trait IntoIterator { #[rustc_const_unstable(feature = "const_intoiterator_identity", issue = "90603")] #[stable(feature = "rust1", since = "1.0.0")] -impl<I: Iterator> const IntoIterator for I { +impl<I: Iterator> IntoIterator for I { type Item = I::Item; type IntoIter = I; diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index 028776042..dabfce144 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -70,7 +70,6 @@ fn _assert_is_object_safe(_: &dyn Iterator<Item = ()>) {} #[doc(notable_trait)] #[rustc_diagnostic_item = "Iterator"] #[must_use = "iterators are lazy and do nothing unless consumed"] -#[const_trait] pub trait Iterator { /// The type of the elements being iterated over. #[rustc_diagnostic_item = "IteratorItem"] |