diff options
25 files changed, 391 insertions, 63 deletions
diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs index 66573b90db9..ad2c4e483a3 100644 --- a/library/alloc/src/collections/binary_heap/mod.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -145,7 +145,7 @@ use core::alloc::Allocator; use core::fmt; -use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; +use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; use core::num::NonZeroUsize; use core::ops::{Deref, DerefMut}; @@ -1540,6 +1540,10 @@ impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> { #[stable(feature = "fused", since = "1.26.0")] impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<T, A: Allocator> TrustedFused for IntoIter<T, A> {} + #[stable(feature = "default_iters", since = "1.70.0")] impl<T> Default for IntoIter<T> { /// Creates an empty `binary_heap::IntoIter`. @@ -1569,7 +1573,10 @@ unsafe impl<T, A: Allocator> SourceIter for IntoIter<T, A> { #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl<I, A: Allocator> InPlaceIterable for IntoIter<I, A> {} +unsafe impl<I, A: Allocator> InPlaceIterable for IntoIter<I, A> { + const EXPAND_BY: Option<NonZeroUsize> = NonZeroUsize::new(1); + const MERGE_BY: Option<NonZeroUsize> = NonZeroUsize::new(1); +} unsafe impl<I> AsVecIntoIter for IntoIter<I> { type Item = I; diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index e43b6ac4039..c9fee435f1e 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -155,6 +155,7 @@ #![feature(std_internals)] #![feature(str_internals)] #![feature(strict_provenance)] +#![feature(trusted_fused)] #![feature(trusted_len)] #![feature(trusted_random_access)] #![feature(try_trait_v2)] diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 5ecd0479971..d174074902a 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -137,44 +137,73 @@ //! } //! vec.truncate(write_idx); //! ``` +use crate::alloc::{handle_alloc_error, Global}; +use core::alloc::Allocator; +use core::alloc::Layout; use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce}; use core::mem::{self, ManuallyDrop, SizedTypeProperties}; -use core::ptr::{self}; +use core::num::NonZeroUsize; +use core::ptr::{self, NonNull}; use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec}; -/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the -/// source allocation, i.e. executing the pipeline in place. -#[rustc_unsafe_specialization_marker] -pub(super) trait InPlaceIterableMarker {} +const fn in_place_collectible<DEST, SRC>( + step_merge: Option<NonZeroUsize>, + step_expand: Option<NonZeroUsize>, +) -> bool { + if DEST::IS_ZST || mem::align_of::<SRC>() != mem::align_of::<DEST>() { + return false; + } + + match (step_merge, step_expand) { + (Some(step_merge), Some(step_expand)) => { + // At least N merged source items -> at most M expanded destination items + // e.g. + // - 1 x [u8; 4] -> 4x u8, via flatten + // - 4 x u8 -> 1x [u8; 4], via array_chunks + mem::size_of::<SRC>() * step_merge.get() == mem::size_of::<DEST>() * step_expand.get() + } + // Fall back to other from_iter impls if an overflow occured in the step merge/expansion + // tracking. + _ => false, + } +} -impl<T> InPlaceIterableMarker for T where T: InPlaceIterable {} +/// This provides a shorthand for the source type since local type aliases aren't a thing. +#[rustc_specialization_trait] +trait InPlaceCollect: SourceIter<Source: AsVecIntoIter> + InPlaceIterable { + type Src; +} + +impl<T> InPlaceCollect for T +where + T: SourceIter<Source: AsVecIntoIter> + InPlaceIterable, +{ + type Src = <<T as SourceIter>::Source as AsVecIntoIter>::Item; +} impl<T, I> SpecFromIter<T, I> for Vec<T> where - I: Iterator<Item = T> + SourceIter<Source: AsVecIntoIter> + InPlaceIterableMarker, + I: Iterator<Item = T> + InPlaceCollect, + <I as SourceIter>::Source: AsVecIntoIter, { default fn from_iter(mut iterator: I) -> Self { // See "Layout constraints" section in the module documentation. We rely on const // optimization here since these conditions currently cannot be expressed as trait bounds - if T::IS_ZST - || mem::size_of::<T>() - != mem::size_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>() - || mem::align_of::<T>() - != mem::align_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>() - { + if const { !in_place_collectible::<T, I::Src>(I::MERGE_BY, I::EXPAND_BY) } { // fallback to more generic implementations return SpecFromIterNested::from_iter(iterator); } - let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe { + let (src_buf, src_ptr, src_cap, mut dst_buf, dst_end, dst_cap) = unsafe { let inner = iterator.as_inner().as_into_iter(); ( inner.buf.as_ptr(), inner.ptr, + inner.cap, inner.buf.as_ptr() as *mut T, inner.end as *const T, - inner.cap, + inner.cap * mem::size_of::<I::Src>() / mem::size_of::<T>(), ) }; @@ -203,11 +232,31 @@ where // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the // module documentation why this is ok anyway. - let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap }; + let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap: dst_cap }; src.forget_allocation_drop_remaining(); mem::forget(dst_guard); - let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) }; + // Adjust the allocation size if the source had a capacity in bytes that wasn't a multiple + // of the destination type size. + // Since the discrepancy should generally be small this should only result in some + // bookkeeping updates and no memmove. + if const { mem::size_of::<T>() > mem::size_of::<I::Src>() } + && src_cap * mem::size_of::<I::Src>() != dst_cap * mem::size_of::<T>() + { + let alloc = Global; + unsafe { + let new_layout = Layout::array::<T>(dst_cap).unwrap(); + let result = alloc.shrink( + NonNull::new_unchecked(dst_buf as *mut u8), + Layout::array::<I::Src>(src_cap).unwrap(), + new_layout, + ); + let Ok(reallocated) = result else { handle_alloc_error(new_layout) }; + dst_buf = reallocated.as_ptr() as *mut T; + } + } + + let vec = unsafe { Vec::from_raw_parts(dst_buf, len, dst_cap) }; vec } diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index b2db2fdfd18..40b93b34e18 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -7,7 +7,8 @@ use crate::raw_vec::RawVec; use core::array; use core::fmt; use core::iter::{ - FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce, + FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen, + TrustedRandomAccessNoCoerce, }; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; @@ -339,6 +340,10 @@ impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> { #[stable(feature = "fused", since = "1.26.0")] impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<T, A: Allocator> TrustedFused for IntoIter<T, A> {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {} @@ -423,7 +428,10 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter<T, A> { // also refer to the vec::in_place_collect module documentation to get an overview #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> {} +unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> { + const EXPAND_BY: Option<NonZeroUsize> = NonZeroUsize::new(1); + const MERGE_BY: Option<NonZeroUsize> = NonZeroUsize::new(1); +} #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs index aa7a331b368..5bb531f0e62 100644 --- a/library/alloc/tests/lib.rs +++ b/library/alloc/tests/lib.rs @@ -1,5 +1,6 @@ #![feature(allocator_api)] #![feature(alloc_layout_extra)] +#![feature(iter_array_chunks)] #![feature(assert_matches)] #![feature(btree_extract_if)] #![feature(cow_is_borrowed)] diff --git a/library/alloc/tests/vec.rs b/library/alloc/tests/vec.rs index 9cb27899f10..33dd2658e1e 100644 --- a/library/alloc/tests/vec.rs +++ b/library/alloc/tests/vec.rs @@ -1,6 +1,7 @@ +use alloc::vec::Vec; use core::alloc::{Allocator, Layout}; -use core::assert_eq; -use core::iter::IntoIterator; +use core::{assert_eq, assert_ne}; +use core::iter::{IntoIterator, Iterator}; use core::num::NonZeroUsize; use core::ptr::NonNull; use std::alloc::System; @@ -1185,6 +1186,35 @@ fn test_from_iter_specialization_with_iterator_adapters() { } #[test] +fn test_in_place_specialization_step_up_down() { + fn assert_in_place_trait<T: InPlaceIterable>(_: &T) {} + let src = vec![[0u8; 4]; 256]; + let srcptr = src.as_ptr(); + let src_cap = src.capacity(); + let iter = src.into_iter().flatten(); + assert_in_place_trait(&iter); + let sink = iter.collect::<Vec<_>>(); + let sinkptr = sink.as_ptr(); + assert_eq!(srcptr as *const u8, sinkptr); + assert_eq!(src_cap * 4, sink.capacity()); + + let iter = sink.into_iter().array_chunks::<4>(); + assert_in_place_trait(&iter); + let sink = iter.collect::<Vec<_>>(); + let sinkptr = sink.as_ptr(); + assert_eq!(srcptr, sinkptr); + assert_eq!(src_cap, sink.capacity()); + + let mut src: Vec<u8> = Vec::with_capacity(17); + let src_bytes = src.capacity(); + src.resize(8, 0u8); + let sink: Vec<[u8; 4]> = src.into_iter().array_chunks::<4>().collect(); + let sink_bytes = sink.capacity() * 4; + assert_ne!(src_bytes, sink_bytes); + assert_eq!(sink.len(), 2); +} + +#[test] fn test_from_iter_specialization_head_tail_drop() { let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect(); let src: Vec<_> = drop_count.iter().cloned().collect(); diff --git a/library/core/src/iter/adapters/array_chunks.rs b/library/core/src/iter/adapters/array_chunks.rs index 13719c727e9..319af4408d7 100644 --- a/library/core/src/iter/adapters/array_chunks.rs +++ b/library/core/src/iter/adapters/array_chunks.rs @@ -1,5 +1,9 @@ use crate::array; -use crate::iter::{ByRefSized, FusedIterator, Iterator, TrustedRandomAccessNoCoerce}; +use crate::iter::adapters::SourceIter; +use crate::iter::{ + ByRefSized, FusedIterator, InPlaceIterable, Iterator, TrustedFused, TrustedRandomAccessNoCoerce, +}; +use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, NeverShortCircuit, Try}; /// An iterator over `N` elements of the iterator at a time. @@ -159,6 +163,9 @@ where #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] impl<I, const N: usize> FusedIterator for ArrayChunks<I, N> where I: FusedIterator {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I, const N: usize> TrustedFused for ArrayChunks<I, N> where I: TrustedFused + Iterator {} + #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] impl<I, const N: usize> ExactSizeIterator for ArrayChunks<I, N> where @@ -229,3 +236,28 @@ where accum } } + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I, const N: usize> SourceIter for ArrayChunks<I, N> +where + I: SourceIter + Iterator, +{ + type Source = I::Source; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut I::Source { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I: InPlaceIterable + Iterator, const N: usize> InPlaceIterable for ArrayChunks<I, N> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = const { + match (I::MERGE_BY, NonZeroUsize::new(N)) { + (Some(m), Some(n)) => m.checked_mul(n), + _ => None, + } + }; +} diff --git a/library/core/src/iter/adapters/enumerate.rs b/library/core/src/iter/adapters/enumerate.rs index 00c1c377bf9..92f465ccdb4 100644 --- a/library/core/src/iter/adapters/enumerate.rs +++ b/library/core/src/iter/adapters/enumerate.rs @@ -1,7 +1,7 @@ use crate::iter::adapters::{ zip::try_get_unchecked, SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen}; +use crate::iter::{FusedIterator, InPlaceIterable, TrustedFused, TrustedLen}; use crate::num::NonZeroUsize; use crate::ops::Try; @@ -243,6 +243,9 @@ where #[stable(feature = "fused", since = "1.26.0")] impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused> TrustedFused for Enumerate<I> {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<I> TrustedLen for Enumerate<I> where I: TrustedLen {} @@ -261,7 +264,10 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable> InPlaceIterable for Enumerate<I> {} +unsafe impl<I: InPlaceIterable> InPlaceIterable for Enumerate<I> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} #[stable(feature = "default_iters", since = "1.70.0")] impl<I: Default> Default for Enumerate<I> { diff --git a/library/core/src/iter/adapters/filter.rs b/library/core/src/iter/adapters/filter.rs index 723657b9e43..882f3e3bc60 100644 --- a/library/core/src/iter/adapters/filter.rs +++ b/library/core/src/iter/adapters/filter.rs @@ -1,5 +1,6 @@ use crate::fmt; -use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; +use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedFused}; +use crate::num::NonZeroUsize; use crate::ops::Try; use core::array; use core::mem::{ManuallyDrop, MaybeUninit}; @@ -189,6 +190,9 @@ where #[stable(feature = "fused", since = "1.26.0")] impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused, F> TrustedFused for Filter<I, F> {} + #[unstable(issue = "none", feature = "inplace_iteration")] unsafe impl<P, I> SourceIter for Filter<I, P> where @@ -204,4 +208,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable, P> InPlaceIterable for Filter<I, P> where P: FnMut(&I::Item) -> bool {} +unsafe impl<I: InPlaceIterable, P> InPlaceIterable for Filter<I, P> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} diff --git a/library/core/src/iter/adapters/filter_map.rs b/library/core/src/iter/adapters/filter_map.rs index 693479977db..c0bdc065b05 100644 --- a/library/core/src/iter/adapters/filter_map.rs +++ b/library/core/src/iter/adapters/filter_map.rs @@ -1,5 +1,6 @@ -use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; +use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedFused}; use crate::mem::{ManuallyDrop, MaybeUninit}; +use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; use crate::{array, fmt}; @@ -188,6 +189,9 @@ where #[stable(feature = "fused", since = "1.26.0")] impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B> {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused, F> TrustedFused for FilterMap<I, F> {} + #[unstable(issue = "none", feature = "inplace_iteration")] unsafe impl<I, F> SourceIter for FilterMap<I, F> where @@ -203,7 +207,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<B, I: InPlaceIterable, F> InPlaceIterable for FilterMap<I, F> where - F: FnMut(I::Item) -> Option<B> -{ +unsafe impl<I: InPlaceIterable, F> InPlaceIterable for FilterMap<I, F> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; } diff --git a/library/core/src/iter/adapters/flatten.rs b/library/core/src/iter/adapters/flatten.rs index eee6e5bccec..60d5418716b 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -1,7 +1,12 @@ -use crate::fmt; -use crate::iter::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map, TrustedLen}; +use crate::iter::adapters::SourceIter; +use crate::iter::{ + DoubleEndedIterator, Fuse, FusedIterator, InPlaceIterable, Iterator, Map, TrustedFused, + TrustedLen, +}; use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; +use crate::{fmt, option}; +use core::iter::Once; /// An iterator that maps each element to an iterator, and yields the elements /// of the produced iterators. @@ -145,6 +150,48 @@ where { } +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I, U, F> InPlaceIterable for FlatMap<I, U, F> +where + I: InPlaceIterable, + U: KnownExpansionFactor + IntoIterator, +{ + const EXPAND_BY: Option<NonZeroUsize> = const { + match (I::EXPAND_BY, U::FACTOR) { + (Some(m), Some(n)) => m.checked_mul(n), + _ => None, + } + }; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I, U, F> SourceIter for FlatMap<I, U, F> +where + I: SourceIter + TrustedFused, + U: IntoIterator, +{ + type Source = I::Source; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut I::Source { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.inner.iter) } + } +} + +#[rustc_specialization_trait] +trait KnownExpansionFactor { + const FACTOR: Option<NonZeroUsize> = NonZeroUsize::new(1); +} + +impl<T> KnownExpansionFactor for Option<T> {} +impl<T> KnownExpansionFactor for option::IntoIter<T> {} +impl<T> KnownExpansionFactor for Once<T> {} +impl<T, const N: usize> KnownExpansionFactor for [T; N] { + const FACTOR: Option<NonZeroUsize> = NonZeroUsize::new(N); +} + /// An iterator that flattens one level of nesting in an iterator of things /// that can be turned into iterators. /// @@ -289,6 +336,36 @@ where { } +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I> InPlaceIterable for Flatten<I> +where + I: InPlaceIterable + Iterator, + <I as Iterator>::Item: IntoIterator + KnownExpansionFactor, +{ + const EXPAND_BY: Option<NonZeroUsize> = const { + match (I::EXPAND_BY, I::Item::FACTOR) { + (Some(m), Some(n)) => m.checked_mul(n), + _ => None, + } + }; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I> SourceIter for Flatten<I> +where + I: SourceIter + TrustedFused + Iterator, + <I as Iterator>::Item: IntoIterator, +{ + type Source = I::Source; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut I::Source { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.inner.iter) } + } +} + #[stable(feature = "default_iters", since = "1.70.0")] impl<I> Default for Flatten<I> where diff --git a/library/core/src/iter/adapters/fuse.rs b/library/core/src/iter/adapters/fuse.rs index b1fa4f92117..3234cade50d 100644 --- a/library/core/src/iter/adapters/fuse.rs +++ b/library/core/src/iter/adapters/fuse.rs @@ -1,8 +1,9 @@ use crate::intrinsics; use crate::iter::adapters::zip::try_get_unchecked; +use crate::iter::adapters::SourceIter; use crate::iter::{ - DoubleEndedIterator, ExactSizeIterator, FusedIterator, TrustedLen, TrustedRandomAccess, - TrustedRandomAccessNoCoerce, + DoubleEndedIterator, ExactSizeIterator, FusedIterator, TrustedFused, TrustedLen, + TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; use crate::ops::Try; @@ -29,6 +30,9 @@ impl<I> Fuse<I> { #[stable(feature = "fused", since = "1.26.0")] impl<I> FusedIterator for Fuse<I> where I: Iterator {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I> TrustedFused for Fuse<I> where I: TrustedFused {} + // Any specialized implementation here is made internal // to avoid exposing default fns outside this trait. #[stable(feature = "rust1", since = "1.0.0")] @@ -418,6 +422,23 @@ where } } +// This is used by Flatten's SourceIter impl +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I> SourceIter for Fuse<I> +where + I: SourceIter + TrustedFused, +{ + type Source = I::Source; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut I::Source { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements. + // TrustedFused guarantees that we'll never encounter a case where `self.iter` would + // be set to None. + unsafe { SourceIter::as_inner(self.iter.as_mut().unwrap_unchecked()) } + } +} + #[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/adapters/inspect.rs b/library/core/src/iter/adapters/inspect.rs index 19839fdfe5b..fd2d830b693 100644 --- a/library/core/src/iter/adapters/inspect.rs +++ b/library/core/src/iter/adapters/inspect.rs @@ -1,5 +1,6 @@ use crate::fmt; -use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; +use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedFused}; +use crate::num::NonZeroUsize; use crate::ops::Try; /// An iterator that calls a function with a reference to each element before @@ -148,6 +149,9 @@ where #[stable(feature = "fused", since = "1.26.0")] impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> where F: FnMut(&I::Item) {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused, F> TrustedFused for Inspect<I, F> {} + #[unstable(issue = "none", feature = "inplace_iteration")] unsafe impl<I, F> SourceIter for Inspect<I, F> where @@ -163,4 +167,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable, F> InPlaceIterable for Inspect<I, F> where F: FnMut(&I::Item) {} +unsafe impl<I: InPlaceIterable, F> InPlaceIterable for Inspect<I, F> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} diff --git a/library/core/src/iter/adapters/map.rs b/library/core/src/iter/adapters/map.rs index 31d02a4da6e..e27fc7257f6 100644 --- a/library/core/src/iter/adapters/map.rs +++ b/library/core/src/iter/adapters/map.rs @@ -2,7 +2,8 @@ use crate::fmt; use crate::iter::adapters::{ zip::try_get_unchecked, SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen, UncheckedIterator}; +use crate::iter::{FusedIterator, InPlaceIterable, TrustedFused, TrustedLen, UncheckedIterator}; +use crate::num::NonZeroUsize; use crate::ops::Try; /// An iterator that maps the values of `iter` with `f`. @@ -179,6 +180,9 @@ where #[stable(feature = "fused", since = "1.26.0")] impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> where F: FnMut(I::Item) -> B {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused, F> TrustedFused for Map<I, F> {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<B, I, F> TrustedLen for Map<I, F> where @@ -228,4 +232,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<B, I: InPlaceIterable, F> InPlaceIterable for Map<I, F> where F: FnMut(I::Item) -> B {} +unsafe impl<I: InPlaceIterable, F> InPlaceIterable for Map<I, F> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} diff --git a/library/core/src/iter/adapters/map_while.rs b/library/core/src/iter/adapters/map_while.rs index fbdeca4d4ee..bcae73cbe09 100644 --- a/library/core/src/iter/adapters/map_while.rs +++ b/library/core/src/iter/adapters/map_while.rs @@ -1,5 +1,6 @@ use crate::fmt; use crate::iter::{adapters::SourceIter, InPlaceIterable}; +use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; /// An iterator that only accepts elements while `predicate` returns `Some(_)`. @@ -82,7 +83,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<B, I: InPlaceIterable, P> InPlaceIterable for MapWhile<I, P> where - P: FnMut(I::Item) -> Option<B> -{ +unsafe impl<I: InPlaceIterable, P> InPlaceIterable for MapWhile<I, P> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; } diff --git a/library/core/src/iter/adapters/mod.rs b/library/core/src/iter/adapters/mod.rs index 6f4fa7010f4..a691039c789 100644 --- a/library/core/src/iter/adapters/mod.rs +++ b/library/core/src/iter/adapters/mod.rs @@ -1,4 +1,5 @@ use crate::iter::{InPlaceIterable, Iterator}; +use crate::num::NonZeroUsize; use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, Residual, Try}; mod array_chunks; @@ -119,8 +120,9 @@ pub unsafe trait SourceIter { /// /// # Safety /// - /// Implementations of must return the same mutable reference for their lifetime, unless + /// Implementations must return the same mutable reference for their lifetime, unless /// replaced by a caller. + /// /// Callers may only replace the reference when they stopped iteration and drop the /// iterator pipeline after extracting the source. /// @@ -228,7 +230,10 @@ where // in order to return `Some(_)`. Since `iter` has type `I: InPlaceIterable` it's // guaranteed that at least one item will be moved out from the underlying source. #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I, T, R> InPlaceIterable for GenericShunt<'_, I, R> where - I: Iterator<Item: Try<Output = T, Residual = R>> + InPlaceIterable +unsafe impl<I, R> InPlaceIterable for GenericShunt<'_, I, R> +where + I: InPlaceIterable, { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; } diff --git a/library/core/src/iter/adapters/scan.rs b/library/core/src/iter/adapters/scan.rs index 62470512cc7..635bad199ff 100644 --- a/library/core/src/iter/adapters/scan.rs +++ b/library/core/src/iter/adapters/scan.rs @@ -1,5 +1,6 @@ use crate::fmt; use crate::iter::{adapters::SourceIter, InPlaceIterable}; +use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; /// An iterator to maintain state while iterating another iterator. @@ -92,7 +93,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<St, F, B, I: InPlaceIterable> InPlaceIterable for Scan<I, St, F> where - F: FnMut(&mut St, I::Item) -> Option<B> -{ +unsafe impl<St, F, I: InPlaceIterable> InPlaceIterable for Scan<I, St, F> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; } diff --git a/library/core/src/iter/adapters/skip.rs b/library/core/src/iter/adapters/skip.rs index 306338bc7cc..e6c946e7f88 100644 --- a/library/core/src/iter/adapters/skip.rs +++ b/library/core/src/iter/adapters/skip.rs @@ -1,4 +1,5 @@ use crate::intrinsics::unlikely; +use crate::iter::TrustedFused; use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; @@ -214,6 +215,9 @@ where #[stable(feature = "fused", since = "1.26.0")] impl<I> FusedIterator for Skip<I> where I: FusedIterator {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused> TrustedFused for Skip<I> {} + #[unstable(issue = "none", feature = "inplace_iteration")] unsafe impl<I> SourceIter for Skip<I> where @@ -229,4 +233,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable> InPlaceIterable for Skip<I> {} +unsafe impl<I: InPlaceIterable> InPlaceIterable for Skip<I> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} diff --git a/library/core/src/iter/adapters/skip_while.rs b/library/core/src/iter/adapters/skip_while.rs index f29661779c0..3a661973e5f 100644 --- a/library/core/src/iter/adapters/skip_while.rs +++ b/library/core/src/iter/adapters/skip_while.rs @@ -1,5 +1,6 @@ use crate::fmt; -use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; +use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedFused}; +use crate::num::NonZeroUsize; use crate::ops::Try; /// An iterator that rejects elements while `predicate` returns `true`. @@ -104,6 +105,9 @@ where { } +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused, P> TrustedFused for SkipWhile<I, P> {} + #[unstable(issue = "none", feature = "inplace_iteration")] unsafe impl<P, I> SourceIter for SkipWhile<I, P> where @@ -119,7 +123,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable, F> InPlaceIterable for SkipWhile<I, F> where - F: FnMut(&I::Item) -> bool -{ +unsafe impl<I: InPlaceIterable, F> InPlaceIterable for SkipWhile<I, F> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; } diff --git a/library/core/src/iter/adapters/take.rs b/library/core/src/iter/adapters/take.rs index c1d8cc4ff57..80e06066d28 100644 --- a/library/core/src/iter/adapters/take.rs +++ b/library/core/src/iter/adapters/take.rs @@ -1,6 +1,7 @@ use crate::cmp; use crate::iter::{ - adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedLen, TrustedRandomAccess, + adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedFused, TrustedLen, + TrustedRandomAccess, }; use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; @@ -143,7 +144,10 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable> InPlaceIterable for Take<I> {} +unsafe impl<I: InPlaceIterable> InPlaceIterable for Take<I> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; +} #[stable(feature = "double_ended_take_iterator", since = "1.38.0")] impl<I> DoubleEndedIterator for Take<I> @@ -241,6 +245,9 @@ impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {} #[stable(feature = "fused", since = "1.26.0")] impl<I> FusedIterator for Take<I> where I: FusedIterator {} +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused> TrustedFused for Take<I> {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<I: TrustedLen> TrustedLen for Take<I> {} diff --git a/library/core/src/iter/adapters/take_while.rs b/library/core/src/iter/adapters/take_while.rs index ec66dc3aec3..e55d55a6d23 100644 --- a/library/core/src/iter/adapters/take_while.rs +++ b/library/core/src/iter/adapters/take_while.rs @@ -1,5 +1,6 @@ use crate::fmt; -use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}; +use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedFused}; +use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; /// An iterator that only accepts elements while `predicate` returns `true`. @@ -105,6 +106,9 @@ where { } +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<I: TrustedFused, P> TrustedFused for TakeWhile<I, P> {} + #[unstable(issue = "none", feature = "inplace_iteration")] unsafe impl<P, I> SourceIter for TakeWhile<I, P> where @@ -120,7 +124,7 @@ where } #[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl<I: InPlaceIterable, F> InPlaceIterable for TakeWhile<I, F> where - F: FnMut(&I::Item) -> bool -{ +unsafe impl<I: InPlaceIterable, F> InPlaceIterable for TakeWhile<I, F> { + const EXPAND_BY: Option<NonZeroUsize> = I::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY; } diff --git a/library/core/src/iter/adapters/zip.rs b/library/core/src/iter/adapters/zip.rs index b6b0c90cb7d..5993c1e3045 100644 --- a/library/core/src/iter/adapters/zip.rs +++ b/library/core/src/iter/adapters/zip.rs @@ -1,7 +1,8 @@ use crate::cmp; use crate::fmt::{self, Debug}; -use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator}; +use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator, TrustedFused}; use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator}; +use crate::num::NonZeroUsize; /// An iterator that iterates two other iterators simultaneously. /// @@ -409,6 +410,14 @@ where { } +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<A, B> TrustedFused for Zip<A, B> +where + A: TrustedFused, + B: TrustedFused, +{ +} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<A, B> TrustedLen for Zip<A, B> where @@ -442,7 +451,10 @@ where // 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> {} +unsafe impl<A: InPlaceIterable, B> InPlaceIterable for Zip<A, B> { + const EXPAND_BY: Option<NonZeroUsize> = A::EXPAND_BY; + const MERGE_BY: Option<NonZeroUsize> = A::MERGE_BY; +} #[stable(feature = "rust1", since = "1.0.0")] impl<A: Debug, B: Debug> Debug for Zip<A, B> { diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs index ca977d1ef82..a727a97ed50 100644 --- a/library/core/src/iter/mod.rs +++ b/library/core/src/iter/mod.rs @@ -417,6 +417,8 @@ pub use self::sources::{successors, Successors}; pub use self::traits::FusedIterator; #[unstable(issue = "none", feature = "inplace_iteration")] pub use self::traits::InPlaceIterable; +#[unstable(issue = "none", feature = "trusted_fused")] +pub use self::traits::TrustedFused; #[unstable(feature = "trusted_len", issue = "37572")] pub use self::traits::TrustedLen; #[unstable(feature = "trusted_step", issue = "85731")] diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index c21a2aac1c9..e7c1f195aac 100644 --- a/library/core/src/iter/traits/marker.rs +++ b/library/core/src/iter/traits/marker.rs @@ -1,4 +1,16 @@ use crate::iter::Step; +use crate::num::NonZeroUsize; + +/// Same as FusedIterator +/// +/// # Safety +/// +/// This is used for specialization. Therefore implementations must not +/// be lifetime-dependent. +#[unstable(issue = "none", feature = "trusted_fused")] +#[doc(hidden)] +#[rustc_specialization_trait] +pub unsafe trait TrustedFused {} /// An iterator that always continues to yield `None` when exhausted. /// @@ -14,6 +26,8 @@ use crate::iter::Step; /// [`Fuse`]: crate::iter::Fuse #[stable(feature = "fused", since = "1.26.0")] #[rustc_unsafe_specialization_marker] +// FIXME: this should be a #[marker] and have another blanket impl for T: TrustedFused +// but that ICEs iter::Fuse specializations. pub trait FusedIterator: Iterator {} #[stable(feature = "fused", since = "1.26.0")] @@ -71,7 +85,19 @@ unsafe impl<I: TrustedLen + ?Sized> TrustedLen for &mut I {} /// [`try_fold()`]: Iterator::try_fold #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -pub unsafe trait InPlaceIterable: Iterator {} +#[rustc_specialization_trait] +pub unsafe trait InPlaceIterable { + /// The product of one-to-many item expansions that happen throughout the iterator pipeline. + /// E.g. [[u8; 4]; 4].iter().flatten().flatten() would have a `EXPAND_BY` of 16. + /// This is an upper bound, i.e. the transformations will produce at most this many items per + /// input. It's meant for layout calculations. + const EXPAND_BY: Option<NonZeroUsize>; + /// The product of many-to-one item reductions that happen throughout the iterator pipeline. + /// E.g. [u8].iter().array_chunks::<4>().array_chunks::<4>() would have a `MERGE_BY` of 16. + /// This is a lower bound, i.e. the transformations will consume at least this many items per + /// output. + const MERGE_BY: Option<NonZeroUsize>; +} /// A type that upholds all invariants of [`Step`]. /// diff --git a/library/core/src/iter/traits/mod.rs b/library/core/src/iter/traits/mod.rs index 41ea29e6a84..d4c9cc4b160 100644 --- a/library/core/src/iter/traits/mod.rs +++ b/library/core/src/iter/traits/mod.rs @@ -18,6 +18,8 @@ pub use self::{ #[unstable(issue = "none", feature = "inplace_iteration")] pub use self::marker::InPlaceIterable; +#[unstable(issue = "none", feature = "trusted_fused")] +pub use self::marker::TrustedFused; #[unstable(feature = "trusted_step", issue = "85731")] pub use self::marker::TrustedStep; |