diff options
Diffstat (limited to 'library/core/src/iter')
25 files changed, 326 insertions, 54 deletions
diff --git a/library/core/src/iter/adapters/array_chunks.rs b/library/core/src/iter/adapters/array_chunks.rs index 13719c727..946d0051c 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, 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/chain.rs b/library/core/src/iter/adapters/chain.rs index 26aa959e6..c748336cd 100644 --- a/library/core/src/iter/adapters/chain.rs +++ b/library/core/src/iter/adapters/chain.rs @@ -1,4 +1,4 @@ -use crate::iter::{DoubleEndedIterator, FusedIterator, Iterator, TrustedLen}; +use crate::iter::{FusedIterator, TrustedLen}; use crate::num::NonZeroUsize; use crate::ops::Try; diff --git a/library/core/src/iter/adapters/copied.rs b/library/core/src/iter/adapters/copied.rs index 8f6b2904e..7a2c9d839 100644 --- a/library/core/src/iter/adapters/copied.rs +++ b/library/core/src/iter/adapters/copied.rs @@ -193,7 +193,7 @@ where T: Copy, { default fn spec_next_chunk(&mut self) -> Result<[T; N], array::IntoIter<T, N>> { - array::iter_next_chunk(&mut self.map(|e| *e)) + array::iter_next_chunk(&mut self.copied()) } } diff --git a/library/core/src/iter/adapters/enumerate.rs b/library/core/src/iter/adapters/enumerate.rs index 00c1c377b..92f465ccd 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 723657b9e..882f3e3bc 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 693479977..81ac0eaa6 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}; @@ -97,9 +98,11 @@ where // SAFETY: Loop conditions ensure the index is in bounds. unsafe { - let opt_payload_at = core::intrinsics::option_payload_ptr(&val); + let opt_payload_at: *const MaybeUninit<B> = (&val as *const Option<B>) + .byte_add(core::mem::offset_of!(Option<B>, Some.0)) + .cast(); let dst = guard.array.as_mut_ptr().add(idx); - crate::ptr::copy_nonoverlapping(opt_payload_at.cast(), dst, 1); + crate::ptr::copy_nonoverlapping(opt_payload_at, dst, 1); crate::mem::forget(val); }; @@ -188,6 +191,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 +209,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 eee6e5bcc..6122332da 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -1,7 +1,13 @@ -use crate::fmt; -use crate::iter::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map, TrustedLen}; +use crate::iter::adapters::SourceIter; +use crate::iter::{ + Cloned, Copied, Filter, FilterMap, Fuse, FusedIterator, InPlaceIterable, Map, TrustedFused, + TrustedLen, +}; +use crate::iter::{Once, OnceWith}; use crate::num::NonZeroUsize; use crate::ops::{ControlFlow, Try}; +use crate::result; +use crate::{array, fmt, option}; /// An iterator that maps each element to an iterator, and yields the elements /// of the produced iterators. @@ -145,6 +151,91 @@ where { } +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I, U, F> InPlaceIterable for FlatMap<I, U, F> +where + I: InPlaceIterable, + U: BoundedSize + IntoIterator, +{ + const EXPAND_BY: Option<NonZeroUsize> = const { + match (I::EXPAND_BY, U::UPPER_BOUND) { + (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) } + } +} + +/// Marker trait for iterators/iterables which have a statically known upper +/// bound of the number of items they can produce. +/// +/// # Safety +/// +/// Implementations must not yield more elements than indicated by UPPER_BOUND if it is `Some`. +/// Used in specializations. Implementations must not be conditional on lifetimes or +/// user-implementable traits. +#[rustc_specialization_trait] +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe trait BoundedSize { + const UPPER_BOUND: Option<NonZeroUsize> = NonZeroUsize::new(1); +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T> BoundedSize for Option<T> {} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T> BoundedSize for option::IntoIter<T> {} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T, U> BoundedSize for Result<T, U> {} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T> BoundedSize for result::IntoIter<T> {} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T> BoundedSize for Once<T> {} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T> BoundedSize for OnceWith<T> {} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T, const N: usize> BoundedSize for [T; N] { + const UPPER_BOUND: Option<NonZeroUsize> = NonZeroUsize::new(N); +} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<T, const N: usize> BoundedSize for array::IntoIter<T, N> { + const UPPER_BOUND: Option<NonZeroUsize> = NonZeroUsize::new(N); +} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I: BoundedSize, P> BoundedSize for Filter<I, P> { + const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND; +} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I: BoundedSize, P> BoundedSize for FilterMap<I, P> { + const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND; +} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I: BoundedSize, F> BoundedSize for Map<I, F> { + const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND; +} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I: BoundedSize> BoundedSize for Copied<I> { + const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND; +} +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I: BoundedSize> BoundedSize for Cloned<I> { + const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND; +} + /// An iterator that flattens one level of nesting in an iterator of things /// that can be turned into iterators. /// @@ -289,6 +380,36 @@ where { } +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl<I> InPlaceIterable for Flatten<I> +where + I: InPlaceIterable + Iterator, + <I as Iterator>::Item: IntoIterator + BoundedSize, +{ + const EXPAND_BY: Option<NonZeroUsize> = const { + match (I::EXPAND_BY, I::Item::UPPER_BOUND) { + (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 b1fa4f921..462a7e877 100644 --- a/library/core/src/iter/adapters/fuse.rs +++ b/library/core/src/iter/adapters/fuse.rs @@ -1,8 +1,8 @@ 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, + FusedIterator, TrustedFused, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; use crate::ops::Try; @@ -29,6 +29,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 +421,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 19839fdfe..fd2d830b6 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 31d02a4da..e27fc7257 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 fbdeca4d4..bcae73cbe 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/map_windows.rs b/library/core/src/iter/adapters/map_windows.rs index 3c0e80b25..5f39b2458 100644 --- a/library/core/src/iter/adapters/map_windows.rs +++ b/library/core/src/iter/adapters/map_windows.rs @@ -1,6 +1,6 @@ use crate::{ fmt, - iter::{ExactSizeIterator, FusedIterator}, + iter::FusedIterator, mem::{self, MaybeUninit}, ptr, }; diff --git a/library/core/src/iter/adapters/mod.rs b/library/core/src/iter/adapters/mod.rs index 6f4fa7010..4037e2e28 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::iter::InPlaceIterable; +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 62470512c..635bad199 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 306338bc7..e6c946e7f 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 f29661779..3a661973e 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/step_by.rs b/library/core/src/iter/adapters/step_by.rs index 7f58f7d17..9e83584e3 100644 --- a/library/core/src/iter/adapters/step_by.rs +++ b/library/core/src/iter/adapters/step_by.rs @@ -83,11 +83,7 @@ where // 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 - } + if self.first_take { if rem == 0 { self.step } else { rem - 1 } } else { rem } } } diff --git a/library/core/src/iter/adapters/take.rs b/library/core/src/iter/adapters/take.rs index c1d8cc4ff..80e06066d 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 ec66dc3ae..e55d55a6d 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 77ccf5085..b33400fab 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::{FusedIterator, TrustedFused}; use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator}; +use crate::num::NonZeroUsize; /// An iterator that iterates two other iterators simultaneously. /// @@ -446,6 +447,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 @@ -479,7 +488,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 937a149ac..44fef3e14 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/sources/from_coroutine.rs b/library/core/src/iter/sources/from_coroutine.rs index 16fbca9b6..bf413b24d 100644 --- a/library/core/src/iter/sources/from_coroutine.rs +++ b/library/core/src/iter/sources/from_coroutine.rs @@ -11,8 +11,7 @@ use crate::pin::Pin; /// # Examples /// /// ``` -/// #![cfg_attr(bootstrap, feature(generators))] -/// #![cfg_attr(not(bootstrap), feature(coroutines))] +/// #![feature(coroutines)] /// #![feature(iter_from_coroutine)] /// /// let it = std::iter::from_coroutine(|| { diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index 6adea4442..8e2c887a1 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -69,7 +69,7 @@ fn _assert_is_object_safe(_: &dyn Iterator<Item = ()>) {} message = "`{Self}` is not an iterator" )] #[doc(notable_trait)] -#[cfg_attr(not(bootstrap), lang = "iterator")] +#[lang = "iterator"] #[rustc_diagnostic_item = "Iterator"] #[must_use = "iterators are lazy and do nothing unless consumed"] pub trait Iterator { diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index c21a2aac1..e7c1f195a 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 41ea29e6a..d4c9cc4b1 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; |