diff options
Diffstat (limited to '')
-rw-r--r-- | library/core/src/iter/adapters/array_chunks.rs | 20 | ||||
-rw-r--r-- | library/core/src/iter/adapters/by_ref_sized.rs | 19 | ||||
-rw-r--r-- | library/core/src/iter/adapters/cloned.rs | 15 | ||||
-rw-r--r-- | library/core/src/iter/adapters/filter_map.rs | 2 | ||||
-rw-r--r-- | library/core/src/iter/adapters/flatten.rs | 4 | ||||
-rw-r--r-- | library/core/src/iter/adapters/map.rs | 15 | ||||
-rw-r--r-- | library/core/src/iter/adapters/zip.rs | 9 | ||||
-rw-r--r-- | library/core/src/iter/mod.rs | 8 | ||||
-rw-r--r-- | library/core/src/iter/range.rs | 1 | ||||
-rw-r--r-- | library/core/src/iter/traits/double_ended.rs | 2 | ||||
-rw-r--r-- | library/core/src/iter/traits/exact_size.rs | 10 | ||||
-rw-r--r-- | library/core/src/iter/traits/iterator.rs | 121 | ||||
-rw-r--r-- | library/core/src/iter/traits/marker.rs | 11 | ||||
-rw-r--r-- | library/core/src/iter/traits/mod.rs | 3 | ||||
-rw-r--r-- | library/core/src/iter/traits/unchecked_iterator.rs | 36 |
15 files changed, 223 insertions, 53 deletions
diff --git a/library/core/src/iter/adapters/array_chunks.rs b/library/core/src/iter/adapters/array_chunks.rs index 5e4211058..13719c727 100644 --- a/library/core/src/iter/adapters/array_chunks.rs +++ b/library/core/src/iter/adapters/array_chunks.rs @@ -1,7 +1,5 @@ use crate::array; -use crate::const_closure::ConstFnMutClosure; use crate::iter::{ByRefSized, FusedIterator, Iterator, TrustedRandomAccessNoCoerce}; -use crate::mem::{self, MaybeUninit}; use crate::ops::{ControlFlow, NeverShortCircuit, Try}; /// An iterator over `N` elements of the iterator at a time. @@ -189,13 +187,12 @@ where I: Iterator, { #[inline] - default fn fold<B, F>(mut self, init: B, mut f: F) -> B + default fn fold<B, F>(mut self, init: B, f: F) -> B where Self: Sized, F: FnMut(B, Self::Item) -> B, { - let fold = ConstFnMutClosure::new(&mut f, NeverShortCircuit::wrap_mut_2_imp); - self.try_fold(init, fold).0 + self.try_fold(init, NeverShortCircuit::wrap_mut_2(f)).0 } } @@ -214,19 +211,14 @@ where let mut i = 0; // Use a while loop because (0..len).step_by(N) doesn't optimize well. while inner_len - i >= N { - let mut chunk = MaybeUninit::uninit_array(); - let mut guard = array::Guard { array_mut: &mut chunk, initialized: 0 }; - while guard.initialized < N { + let chunk = crate::array::from_fn(|local| { // SAFETY: The method consumes the iterator and the loop condition ensures that // all accesses are in bounds and only happen once. unsafe { - let idx = i + guard.initialized; - guard.push_unchecked(self.iter.__iterator_get_unchecked(idx)); + let idx = i + local; + self.iter.__iterator_get_unchecked(idx) } - } - mem::forget(guard); - // SAFETY: The loop above initialized all elements - let chunk = unsafe { MaybeUninit::array_assume_init(chunk) }; + }); accum = f(accum, chunk); i += N; } diff --git a/library/core/src/iter/adapters/by_ref_sized.rs b/library/core/src/iter/adapters/by_ref_sized.rs index 1945e402f..477e7117c 100644 --- a/library/core/src/iter/adapters/by_ref_sized.rs +++ b/library/core/src/iter/adapters/by_ref_sized.rs @@ -1,7 +1,4 @@ -use crate::{ - const_closure::ConstFnMutClosure, - ops::{NeverShortCircuit, Try}, -}; +use crate::ops::{NeverShortCircuit, Try}; /// Like `Iterator::by_ref`, but requiring `Sized` so it can forward generics. /// @@ -39,13 +36,12 @@ impl<I: Iterator> Iterator for ByRefSized<'_, I> { } #[inline] - fn fold<B, F>(self, init: B, mut f: F) -> B + fn fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B, { // `fold` needs ownership, so this can't forward directly. - I::try_fold(self.0, init, ConstFnMutClosure::new(&mut f, NeverShortCircuit::wrap_mut_2_imp)) - .0 + I::try_fold(self.0, init, NeverShortCircuit::wrap_mut_2(f)).0 } #[inline] @@ -76,17 +72,12 @@ impl<I: DoubleEndedIterator> DoubleEndedIterator for ByRefSized<'_, I> { } #[inline] - fn rfold<B, F>(self, init: B, mut f: F) -> B + fn rfold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B, { // `rfold` needs ownership, so this can't forward directly. - I::try_rfold( - self.0, - init, - ConstFnMutClosure::new(&mut f, NeverShortCircuit::wrap_mut_2_imp), - ) - .0 + I::try_rfold(self.0, init, NeverShortCircuit::wrap_mut_2(f)).0 } #[inline] diff --git a/library/core/src/iter/adapters/cloned.rs b/library/core/src/iter/adapters/cloned.rs index aba24a79d..914ff86c1 100644 --- a/library/core/src/iter/adapters/cloned.rs +++ b/library/core/src/iter/adapters/cloned.rs @@ -1,7 +1,7 @@ use crate::iter::adapters::{ zip::try_get_unchecked, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, TrustedLen}; +use crate::iter::{FusedIterator, TrustedLen, UncheckedIterator}; use crate::ops::Try; /// An iterator that clones the elements of an underlying iterator. @@ -140,3 +140,16 @@ where T: Clone, { } + +impl<'a, I, T: 'a> UncheckedIterator for Cloned<I> +where + I: UncheckedIterator<Item = &'a T>, + T: Clone, +{ + unsafe fn next_unchecked(&mut self) -> T { + // SAFETY: `Cloned` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let item = unsafe { self.it.next_unchecked() }; + item.clone() + } +} diff --git a/library/core/src/iter/adapters/filter_map.rs b/library/core/src/iter/adapters/filter_map.rs index e0d665c9e..6bdf53f7f 100644 --- a/library/core/src/iter/adapters/filter_map.rs +++ b/library/core/src/iter/adapters/filter_map.rs @@ -99,7 +99,7 @@ where ) -> impl FnMut((), T) -> ControlFlow<B> + '_ { move |(), x| match f(x) { Some(x) => ControlFlow::Break(x), - None => ControlFlow::CONTINUE, + None => ControlFlow::Continue(()), } } diff --git a/library/core/src/iter/adapters/flatten.rs b/library/core/src/iter/adapters/flatten.rs index 307016c26..b040a0ea9 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -539,7 +539,7 @@ where #[rustc_inherit_overflow_checks] fn advance<U: Iterator>(n: usize, iter: &mut U) -> ControlFlow<(), usize> { match iter.advance_by(n) { - Ok(()) => ControlFlow::BREAK, + Ok(()) => ControlFlow::Break(()), Err(advanced) => ControlFlow::Continue(n - advanced), } } @@ -629,7 +629,7 @@ where #[rustc_inherit_overflow_checks] fn advance<U: DoubleEndedIterator>(n: usize, iter: &mut U) -> ControlFlow<(), usize> { match iter.advance_back_by(n) { - Ok(()) => ControlFlow::BREAK, + Ok(()) => ControlFlow::Break(()), Err(advanced) => ControlFlow::Continue(n - advanced), } } diff --git a/library/core/src/iter/adapters/map.rs b/library/core/src/iter/adapters/map.rs index 9e25dbe46..31d02a4da 100644 --- a/library/core/src/iter/adapters/map.rs +++ b/library/core/src/iter/adapters/map.rs @@ -2,7 +2,7 @@ use crate::fmt; use crate::iter::adapters::{ zip::try_get_unchecked, SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen}; +use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen, UncheckedIterator}; use crate::ops::Try; /// An iterator that maps the values of `iter` with `f`. @@ -187,6 +187,19 @@ where { } +impl<B, I, F> UncheckedIterator for Map<I, F> +where + I: UncheckedIterator, + F: FnMut(I::Item) -> B, +{ + unsafe fn next_unchecked(&mut self) -> B { + // SAFETY: `Map` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let item = unsafe { self.iter.next_unchecked() }; + (self.f)(item) + } +} + #[doc(hidden)] #[unstable(feature = "trusted_random_access", issue = "none")] unsafe impl<I, F> TrustedRandomAccess for Map<I, F> where I: TrustedRandomAccess {} diff --git a/library/core/src/iter/adapters/zip.rs b/library/core/src/iter/adapters/zip.rs index 8153c8cfe..b6b0c90cb 100644 --- a/library/core/src/iter/adapters/zip.rs +++ b/library/core/src/iter/adapters/zip.rs @@ -1,7 +1,7 @@ use crate::cmp; use crate::fmt::{self, Debug}; use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator}; -use crate::iter::{InPlaceIterable, SourceIter, TrustedLen}; +use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator}; /// An iterator that iterates two other iterators simultaneously. /// @@ -417,6 +417,13 @@ where { } +impl<A, B> UncheckedIterator for Zip<A, B> +where + A: UncheckedIterator, + B: UncheckedIterator, +{ +} + // Arbitrarily selects the left side of the zip iteration as extractable "source" // it would require negative trait bounds to be able to try both #[unstable(issue = "none", feature = "inplace_iteration")] diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs index bb35d50b4..ae00232c1 100644 --- a/library/core/src/iter/mod.rs +++ b/library/core/src/iter/mod.rs @@ -278,6 +278,7 @@ //! //! ``` //! # #![allow(unused_must_use)] +//! # #![cfg_attr(not(bootstrap), allow(map_unit_fn))] //! let v = vec![1, 2, 3, 4, 5]; //! v.iter().map(|x| println!("{x}")); //! ``` @@ -362,15 +363,13 @@ macro_rules! impl_fold_via_try_fold { }; (@internal $fold:ident -> $try_fold:ident) => { #[inline] - fn $fold<AAA, FFF>(mut self, init: AAA, mut fold: FFF) -> AAA + fn $fold<AAA, FFF>(mut self, init: AAA, fold: FFF) -> AAA where FFF: FnMut(AAA, Self::Item) -> AAA, { - use crate::const_closure::ConstFnMutClosure; use crate::ops::NeverShortCircuit; - let fold = ConstFnMutClosure::new(&mut fold, NeverShortCircuit::wrap_mut_2_imp); - self.$try_fold(init, fold).0 + self.$try_fold(init, NeverShortCircuit::wrap_mut_2(fold)).0 } }; } @@ -452,6 +451,7 @@ pub use self::adapters::{ pub use self::adapters::{Intersperse, IntersperseWith}; pub(crate) use self::adapters::try_process; +pub(crate) use self::traits::UncheckedIterator; mod adapters; mod range; diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs index b5739f2f3..78e27d730 100644 --- a/library/core/src/iter/range.rs +++ b/library/core/src/iter/range.rs @@ -1,4 +1,3 @@ -use crate::char; use crate::convert::TryFrom; use crate::mem; use crate::ops::{self, Try}; diff --git a/library/core/src/iter/traits/double_ended.rs b/library/core/src/iter/traits/double_ended.rs index bdf94c792..ed23873cd 100644 --- a/library/core/src/iter/traits/double_ended.rs +++ b/library/core/src/iter/traits/double_ended.rs @@ -352,7 +352,7 @@ pub trait DoubleEndedIterator: Iterator { #[inline] fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> { move |(), x| { - if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::CONTINUE } + if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) } } } diff --git a/library/core/src/iter/traits/exact_size.rs b/library/core/src/iter/traits/exact_size.rs index 1757e37ec..908830d8a 100644 --- a/library/core/src/iter/traits/exact_size.rs +++ b/library/core/src/iter/traits/exact_size.rs @@ -21,6 +21,16 @@ /// /// [`len`]: ExactSizeIterator::len /// +/// # When *shouldn't* an adapter be `ExactSizeIterator`? +/// +/// If an adapter makes an iterator *longer*, then it's usually incorrect for +/// that adapter to implement `ExactSizeIterator`. The inner exact-sized +/// iterator might already be `usize::MAX`-long, and thus the length of the +/// longer adapted iterator would no longer be exactly representable in `usize`. +/// +/// This is why [`Chain<A, B>`](crate::iter::Chain) isn't `ExactSizeIterator`, +/// even when `A` and `B` are both `ExactSizeIterator`. +/// /// # Examples /// /// Basic usage: diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index a4a665d48..b8e7d0a68 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -69,6 +69,7 @@ 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"] +#[cfg_attr(not(bootstrap), const_trait)] pub trait Iterator { /// The type of the elements being iterated over. #[rustc_diagnostic_item = "IteratorItem"] @@ -141,6 +142,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "iter_next_chunk", reason = "recently added", issue = "98326")] + #[rustc_do_not_const_check] fn next_chunk<const N: usize>( &mut self, ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> @@ -218,6 +220,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn size_hint(&self) -> (usize, Option<usize>) { (0, None) } @@ -255,6 +258,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn count(self) -> usize where Self: Sized, @@ -285,6 +289,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn last(self) -> Option<Self::Item> where Self: Sized, @@ -331,6 +336,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "iter_advance_by", reason = "recently added", issue = "77404")] + #[rustc_do_not_const_check] fn advance_by(&mut self, n: usize) -> Result<(), usize> { for i in 0..n { self.next().ok_or(i)?; @@ -379,6 +385,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn nth(&mut self, n: usize) -> Option<Self::Item> { self.advance_by(n).ok()?; self.next() @@ -431,6 +438,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_step_by", since = "1.28.0")] + #[rustc_do_not_const_check] fn step_by(self, step: usize) -> StepBy<Self> where Self: Sized, @@ -502,6 +510,7 @@ pub trait Iterator { /// [`OsStr`]: ../../std/ffi/struct.OsStr.html #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter> where Self: Sized, @@ -620,6 +629,7 @@ pub trait Iterator { /// [`zip`]: crate::iter::zip #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter> where Self: Sized, @@ -662,6 +672,7 @@ pub trait Iterator { /// [`intersperse_with`]: Iterator::intersperse_with #[inline] #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")] + #[rustc_do_not_const_check] fn intersperse(self, separator: Self::Item) -> Intersperse<Self> where Self: Sized, @@ -720,6 +731,7 @@ pub trait Iterator { /// [`intersperse`]: Iterator::intersperse #[inline] #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")] + #[rustc_do_not_const_check] fn intersperse_with<G>(self, separator: G) -> IntersperseWith<Self, G> where Self: Sized, @@ -777,8 +789,10 @@ pub trait Iterator { /// println!("{x}"); /// } /// ``` + #[rustc_diagnostic_item = "IteratorMap"] #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn map<B, F>(self, f: F) -> Map<Self, F> where Self: Sized, @@ -824,6 +838,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_for_each", since = "1.21.0")] + #[rustc_do_not_const_check] fn for_each<F>(self, f: F) where Self: Sized, @@ -899,6 +914,7 @@ pub trait Iterator { /// Note that `iter.filter(f).next()` is equivalent to `iter.find(f)`. #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn filter<P>(self, predicate: P) -> Filter<Self, P> where Self: Sized, @@ -944,6 +960,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where Self: Sized, @@ -990,6 +1007,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn enumerate(self) -> Enumerate<Self> where Self: Sized, @@ -1061,6 +1079,7 @@ pub trait Iterator { /// [`next`]: Iterator::next #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn peekable(self) -> Peekable<Self> where Self: Sized, @@ -1126,6 +1145,7 @@ pub trait Iterator { #[inline] #[doc(alias = "drop_while")] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where Self: Sized, @@ -1207,6 +1227,7 @@ pub trait Iterator { /// the iteration should stop, but wasn't placed back into the iterator. #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where Self: Sized, @@ -1295,6 +1316,7 @@ pub trait Iterator { /// [`fuse`]: Iterator::fuse #[inline] #[stable(feature = "iter_map_while", since = "1.57.0")] + #[rustc_do_not_const_check] fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P> where Self: Sized, @@ -1326,6 +1348,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn skip(self, n: usize) -> Skip<Self> where Self: Sized, @@ -1379,6 +1402,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn take(self, n: usize) -> Take<Self> where Self: Sized, @@ -1428,6 +1452,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F> where Self: Sized, @@ -1468,6 +1493,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F> where Self: Sized, @@ -1552,6 +1578,7 @@ pub trait Iterator { /// [`flat_map()`]: Iterator::flat_map #[inline] #[stable(feature = "iterator_flatten", since = "1.29.0")] + #[rustc_do_not_const_check] fn flatten(self) -> Flatten<Self> where Self: Sized, @@ -1620,6 +1647,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn fuse(self) -> Fuse<Self> where Self: Sized, @@ -1704,6 +1732,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn inspect<F>(self, f: F) -> Inspect<Self, F> where Self: Sized, @@ -1734,6 +1763,7 @@ pub trait Iterator { /// assert_eq!(of_rust, vec!["of", "Rust"]); /// ``` #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn by_ref(&mut self) -> &mut Self where Self: Sized, @@ -1853,6 +1883,7 @@ pub trait Iterator { #[stable(feature = "rust1", since = "1.0.0")] #[must_use = "if you really need to exhaust the iterator, consider `.for_each(drop)` instead"] #[cfg_attr(not(test), rustc_diagnostic_item = "iterator_collect_fn")] + #[rustc_do_not_const_check] fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized, @@ -1931,6 +1962,7 @@ pub trait Iterator { /// [`collect`]: Iterator::collect #[inline] #[unstable(feature = "iterator_try_collect", issue = "94047")] + #[rustc_do_not_const_check] fn try_collect<B>(&mut self) -> ChangeOutputType<Self::Item, B> where Self: Sized, @@ -2004,6 +2036,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "iter_collect_into", reason = "new API", issue = "94780")] + #[rustc_do_not_const_check] fn collect_into<E: Extend<Self::Item>>(self, collection: &mut E) -> &mut E where Self: Sized, @@ -2038,6 +2071,7 @@ pub trait Iterator { /// assert_eq!(odd, vec![1, 3]); /// ``` #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn partition<B, F>(self, f: F) -> (B, B) where Self: Sized, @@ -2100,6 +2134,7 @@ pub trait Iterator { /// assert!(a[i..].iter().all(|&n| n % 2 == 1)); // odds /// ``` #[unstable(feature = "iter_partition_in_place", reason = "new API", issue = "62543")] + #[rustc_do_not_const_check] fn partition_in_place<'a, T: 'a, P>(mut self, ref mut predicate: P) -> usize where Self: Sized + DoubleEndedIterator<Item = &'a mut T>, @@ -2157,6 +2192,7 @@ pub trait Iterator { /// assert!(!"IntoIterator".chars().is_partitioned(char::is_uppercase)); /// ``` #[unstable(feature = "iter_is_partitioned", reason = "new API", issue = "62544")] + #[rustc_do_not_const_check] fn is_partitioned<P>(mut self, mut predicate: P) -> bool where Self: Sized, @@ -2251,6 +2287,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_try_fold", since = "1.27.0")] + #[rustc_do_not_const_check] fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where Self: Sized, @@ -2309,6 +2346,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_try_fold", since = "1.27.0")] + #[rustc_do_not_const_check] fn try_for_each<F, R>(&mut self, f: F) -> R where Self: Sized, @@ -2428,6 +2466,7 @@ pub trait Iterator { #[doc(alias = "inject", alias = "foldl")] #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn fold<B, F>(mut self, init: B, mut f: F) -> B where Self: Sized, @@ -2465,6 +2504,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_fold_self", since = "1.51.0")] + #[rustc_do_not_const_check] fn reduce<F>(mut self, f: F) -> Option<Self::Item> where Self: Sized, @@ -2536,6 +2576,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "iterator_try_reduce", reason = "new API", issue = "87053")] + #[rustc_do_not_const_check] fn try_reduce<F, R>(&mut self, f: F) -> ChangeOutputType<R, Option<R::Output>> where Self: Sized, @@ -2593,6 +2634,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn all<F>(&mut self, f: F) -> bool where Self: Sized, @@ -2601,10 +2643,10 @@ pub trait Iterator { #[inline] fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut((), T) -> ControlFlow<()> { move |(), x| { - if f(x) { ControlFlow::CONTINUE } else { ControlFlow::BREAK } + if f(x) { ControlFlow::Continue(()) } else { ControlFlow::Break(()) } } } - self.try_fold((), check(f)) == ControlFlow::CONTINUE + self.try_fold((), check(f)) == ControlFlow::Continue(()) } /// Tests if any element of the iterator matches a predicate. @@ -2646,6 +2688,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn any<F>(&mut self, f: F) -> bool where Self: Sized, @@ -2654,11 +2697,11 @@ pub trait Iterator { #[inline] fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut((), T) -> ControlFlow<()> { move |(), x| { - if f(x) { ControlFlow::BREAK } else { ControlFlow::CONTINUE } + if f(x) { ControlFlow::Break(()) } else { ControlFlow::Continue(()) } } } - self.try_fold((), check(f)) == ControlFlow::BREAK + self.try_fold((), check(f)) == ControlFlow::Break(()) } /// Searches for an element of an iterator that satisfies a predicate. @@ -2709,6 +2752,7 @@ pub trait Iterator { /// Note that `iter.find(f)` is equivalent to `iter.filter(f).next()`. #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where Self: Sized, @@ -2717,7 +2761,7 @@ pub trait Iterator { #[inline] fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> { move |(), x| { - if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::CONTINUE } + if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) } } } @@ -2740,6 +2784,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iterator_find_map", since = "1.30.0")] + #[rustc_do_not_const_check] fn find_map<B, F>(&mut self, f: F) -> Option<B> where Self: Sized, @@ -2749,7 +2794,7 @@ pub trait Iterator { fn check<T, B>(mut f: impl FnMut(T) -> Option<B>) -> impl FnMut((), T) -> ControlFlow<B> { move |(), x| match f(x) { Some(x) => ControlFlow::Break(x), - None => ControlFlow::CONTINUE, + None => ControlFlow::Continue(()), } } @@ -2796,6 +2841,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "try_find", reason = "new API", issue = "63178")] + #[rustc_do_not_const_check] fn try_find<F, R>(&mut self, f: F) -> ChangeOutputType<R, Option<Self::Item>> where Self: Sized, @@ -2812,7 +2858,7 @@ pub trait Iterator { R: Residual<Option<I>>, { move |(), x| match f(&x).branch() { - ControlFlow::Continue(false) => ControlFlow::CONTINUE, + ControlFlow::Continue(false) => ControlFlow::Continue(()), ControlFlow::Continue(true) => ControlFlow::Break(Try::from_output(Some(x))), ControlFlow::Break(r) => ControlFlow::Break(FromResidual::from_residual(r)), } @@ -2878,6 +2924,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn position<P>(&mut self, predicate: P) -> Option<usize> where Self: Sized, @@ -2935,6 +2982,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn rposition<P>(&mut self, predicate: P) -> Option<usize> where P: FnMut(Self::Item) -> bool, @@ -2986,6 +3034,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn max(self) -> Option<Self::Item> where Self: Sized, @@ -3024,6 +3073,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn min(self) -> Option<Self::Item> where Self: Sized, @@ -3046,6 +3096,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_cmp_by_key", since = "1.6.0")] + #[rustc_do_not_const_check] fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item> where Self: Sized, @@ -3079,6 +3130,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_max_by", since = "1.15.0")] + #[rustc_do_not_const_check] fn max_by<F>(self, compare: F) -> Option<Self::Item> where Self: Sized, @@ -3106,6 +3158,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_cmp_by_key", since = "1.6.0")] + #[rustc_do_not_const_check] fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item> where Self: Sized, @@ -3139,6 +3192,7 @@ pub trait Iterator { /// ``` #[inline] #[stable(feature = "iter_min_by", since = "1.15.0")] + #[rustc_do_not_const_check] fn min_by<F>(self, compare: F) -> Option<Self::Item> where Self: Sized, @@ -3176,6 +3230,7 @@ pub trait Iterator { #[inline] #[doc(alias = "reverse")] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn rev(self) -> Rev<Self> where Self: Sized + DoubleEndedIterator, @@ -3214,6 +3269,7 @@ pub trait Iterator { /// assert_eq!(z, [3, 6]); /// ``` #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where FromA: Default + Extend<A>, @@ -3246,6 +3302,7 @@ pub trait Iterator { /// assert_eq!(v_map, vec![1, 2, 3]); /// ``` #[stable(feature = "iter_copied", since = "1.36.0")] + #[rustc_do_not_const_check] fn copied<'a, T: 'a>(self) -> Copied<Self> where Self: Sized + Iterator<Item = &'a T>, @@ -3293,6 +3350,7 @@ pub trait Iterator { /// assert_eq!(&[vec![23]], &faster[..]); /// ``` #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_do_not_const_check] fn cloned<'a, T: 'a>(self) -> Cloned<Self> where Self: Sized + Iterator<Item = &'a T>, @@ -3327,6 +3385,7 @@ pub trait Iterator { /// ``` #[stable(feature = "rust1", since = "1.0.0")] #[inline] + #[rustc_do_not_const_check] fn cycle(self) -> Cycle<Self> where Self: Sized + Clone, @@ -3370,6 +3429,7 @@ pub trait Iterator { /// ``` #[track_caller] #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")] + #[rustc_do_not_const_check] fn array_chunks<const N: usize>(self) -> ArrayChunks<Self, N> where Self: Sized, @@ -3400,6 +3460,7 @@ pub trait Iterator { /// assert_eq!(sum, 6); /// ``` #[stable(feature = "iter_arith", since = "1.11.0")] + #[rustc_do_not_const_check] fn sum<S>(self) -> S where Self: Sized, @@ -3429,6 +3490,7 @@ pub trait Iterator { /// assert_eq!(factorial(5), 120); /// ``` #[stable(feature = "iter_arith", since = "1.11.0")] + #[rustc_do_not_const_check] fn product<P>(self) -> P where Self: Sized, @@ -3450,6 +3512,7 @@ pub trait Iterator { /// assert_eq!([1, 2].iter().cmp([1].iter()), Ordering::Greater); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn cmp<I>(self, other: I) -> Ordering where I: IntoIterator<Item = Self::Item>, @@ -3479,6 +3542,7 @@ pub trait Iterator { /// assert_eq!(xs.iter().cmp_by(&ys, |&x, &y| (2 * x).cmp(&y)), Ordering::Greater); /// ``` #[unstable(feature = "iter_order_by", issue = "64295")] + #[rustc_do_not_const_check] fn cmp_by<I, F>(self, other: I, cmp: F) -> Ordering where Self: Sized, @@ -3491,7 +3555,7 @@ pub trait Iterator { F: FnMut(X, Y) -> Ordering, { move |x, y| match cmp(x, y) { - Ordering::Equal => ControlFlow::CONTINUE, + Ordering::Equal => ControlFlow::Continue(()), non_eq => ControlFlow::Break(non_eq), } } @@ -3502,8 +3566,10 @@ pub trait Iterator { } } - /// [Lexicographically](Ord#lexicographical-comparison) compares the elements of this [`Iterator`] with those - /// of another. + /// [Lexicographically](Ord#lexicographical-comparison) compares the [`PartialOrd`] elements of + /// this [`Iterator`] with those of another. The comparison works like short-circuit + /// evaluation, returning a result without comparing the remaining elements. + /// As soon as an order can be determined, the evaluation stops and a result is returned. /// /// # Examples /// @@ -3513,10 +3579,27 @@ pub trait Iterator { /// assert_eq!([1.].iter().partial_cmp([1.].iter()), Some(Ordering::Equal)); /// assert_eq!([1.].iter().partial_cmp([1., 2.].iter()), Some(Ordering::Less)); /// assert_eq!([1., 2.].iter().partial_cmp([1.].iter()), Some(Ordering::Greater)); + /// ``` /// + /// For floating-point numbers, NaN does not have a total order and will result + /// in `None` when compared: + /// + /// ``` /// assert_eq!([f64::NAN].iter().partial_cmp([1.].iter()), None); /// ``` + /// + /// The results are determined by the order of evaluation. + /// + /// ``` + /// use std::cmp::Ordering; + /// + /// assert_eq!([1.0, f64::NAN].iter().partial_cmp([2.0, f64::NAN].iter()), Some(Ordering::Less)); + /// assert_eq!([2.0, f64::NAN].iter().partial_cmp([1.0, f64::NAN].iter()), Some(Ordering::Greater)); + /// assert_eq!([f64::NAN, 1.0].iter().partial_cmp([f64::NAN, 2.0].iter()), None); + /// ``` + /// #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn partial_cmp<I>(self, other: I) -> Option<Ordering> where I: IntoIterator, @@ -3555,6 +3638,7 @@ pub trait Iterator { /// ); /// ``` #[unstable(feature = "iter_order_by", issue = "64295")] + #[rustc_do_not_const_check] fn partial_cmp_by<I, F>(self, other: I, partial_cmp: F) -> Option<Ordering> where Self: Sized, @@ -3567,7 +3651,7 @@ pub trait Iterator { F: FnMut(X, Y) -> Option<Ordering>, { move |x, y| match partial_cmp(x, y) { - Some(Ordering::Equal) => ControlFlow::CONTINUE, + Some(Ordering::Equal) => ControlFlow::Continue(()), non_eq => ControlFlow::Break(non_eq), } } @@ -3588,6 +3672,7 @@ pub trait Iterator { /// assert_eq!([1].iter().eq([1, 2].iter()), false); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn eq<I>(self, other: I) -> bool where I: IntoIterator, @@ -3613,6 +3698,7 @@ pub trait Iterator { /// assert!(xs.iter().eq_by(&ys, |&x, &y| x * x == y)); /// ``` #[unstable(feature = "iter_order_by", issue = "64295")] + #[rustc_do_not_const_check] fn eq_by<I, F>(self, other: I, eq: F) -> bool where Self: Sized, @@ -3625,7 +3711,7 @@ pub trait Iterator { F: FnMut(X, Y) -> bool, { move |x, y| { - if eq(x, y) { ControlFlow::CONTINUE } else { ControlFlow::BREAK } + if eq(x, y) { ControlFlow::Continue(()) } else { ControlFlow::Break(()) } } } @@ -3645,6 +3731,7 @@ pub trait Iterator { /// assert_eq!([1].iter().ne([1, 2].iter()), true); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn ne<I>(self, other: I) -> bool where I: IntoIterator, @@ -3666,6 +3753,7 @@ pub trait Iterator { /// assert_eq!([1, 2].iter().lt([1, 2].iter()), false); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn lt<I>(self, other: I) -> bool where I: IntoIterator, @@ -3687,6 +3775,7 @@ pub trait Iterator { /// assert_eq!([1, 2].iter().le([1, 2].iter()), true); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn le<I>(self, other: I) -> bool where I: IntoIterator, @@ -3708,6 +3797,7 @@ pub trait Iterator { /// assert_eq!([1, 2].iter().gt([1, 2].iter()), false); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn gt<I>(self, other: I) -> bool where I: IntoIterator, @@ -3729,6 +3819,7 @@ pub trait Iterator { /// assert_eq!([1, 2].iter().ge([1, 2].iter()), true); /// ``` #[stable(feature = "iter_order", since = "1.5.0")] + #[rustc_do_not_const_check] fn ge<I>(self, other: I) -> bool where I: IntoIterator, @@ -3760,6 +3851,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")] + #[rustc_do_not_const_check] fn is_sorted(self) -> bool where Self: Sized, @@ -3788,6 +3880,7 @@ pub trait Iterator { /// /// [`is_sorted`]: Iterator::is_sorted #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")] + #[rustc_do_not_const_check] fn is_sorted_by<F>(mut self, compare: F) -> bool where Self: Sized, @@ -3834,6 +3927,7 @@ pub trait Iterator { /// ``` #[inline] #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")] + #[rustc_do_not_const_check] fn is_sorted_by_key<F, K>(self, f: F) -> bool where Self: Sized, @@ -3849,6 +3943,7 @@ pub trait Iterator { #[inline] #[doc(hidden)] #[unstable(feature = "trusted_random_access", issue = "none")] + #[rustc_do_not_const_check] unsafe fn __iterator_get_unchecked(&mut self, _idx: usize) -> Self::Item where Self: TrustedRandomAccessNoCoerce, @@ -3859,7 +3954,7 @@ pub trait Iterator { /// Compares two iterators element-wise using the given function. /// -/// If `ControlFlow::CONTINUE` is returned from the function, the comparison moves on to the next +/// If `ControlFlow::Continue(())` is returned from the function, the comparison moves on to the next /// elements of both iterators. Returning `ControlFlow::Break(x)` short-circuits the iteration and /// returns `ControlFlow::Break(x)`. If one of the iterators runs out of elements, /// `ControlFlow::Continue(ord)` is returned where `ord` is the result of comparing the lengths of diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index da7537457..af0284823 100644 --- a/library/core/src/iter/traits/marker.rs +++ b/library/core/src/iter/traits/marker.rs @@ -31,6 +31,17 @@ impl<I: FusedIterator + ?Sized> FusedIterator for &mut I {} /// The iterator must produce exactly the number of elements it reported /// or diverge before reaching the end. /// +/// # When *shouldn't* an adapter be `TrustedLen`? +/// +/// If an adapter makes an iterator *shorter* by a given amount, then it's +/// usually incorrect for that adapter to implement `TrustedLen`. The inner +/// iterator might return more than `usize::MAX` items, but there's no way to +/// know what `k` elements less than that will be, since the `size_hint` from +/// the inner iterator has already saturated and lost that information. +/// +/// This is why [`Skip<I>`](crate::iter::Skip) isn't `TrustedLen`, even when +/// `I` implements `TrustedLen`. +/// /// # Safety /// /// This trait must only be implemented when the contract is upheld. Consumers diff --git a/library/core/src/iter/traits/mod.rs b/library/core/src/iter/traits/mod.rs index ed0fb634d..41ea29e6a 100644 --- a/library/core/src/iter/traits/mod.rs +++ b/library/core/src/iter/traits/mod.rs @@ -4,6 +4,7 @@ mod double_ended; mod exact_size; mod iterator; mod marker; +mod unchecked_iterator; #[stable(feature = "rust1", since = "1.0.0")] pub use self::{ @@ -19,3 +20,5 @@ pub use self::{ pub use self::marker::InPlaceIterable; #[unstable(feature = "trusted_step", issue = "85731")] pub use self::marker::TrustedStep; + +pub(crate) use self::unchecked_iterator::UncheckedIterator; diff --git a/library/core/src/iter/traits/unchecked_iterator.rs b/library/core/src/iter/traits/unchecked_iterator.rs new file mode 100644 index 000000000..ae4bfcad4 --- /dev/null +++ b/library/core/src/iter/traits/unchecked_iterator.rs @@ -0,0 +1,36 @@ +use crate::iter::TrustedLen; + +/// [`TrustedLen`] cannot have methods, so this allows augmenting it. +/// +/// It currently requires `TrustedLen` because it's unclear whether it's +/// reasonably possible to depend on the `size_hint` of anything else. +pub(crate) trait UncheckedIterator: TrustedLen { + /// Gets the next item from a non-empty iterator. + /// + /// Because there's always a value to return, that means it can return + /// the `Item` type directly, without wrapping it in an `Option`. + /// + /// # Safety + /// + /// This can only be called if `size_hint().0 != 0`, guaranteeing that + /// there's at least one item available. + /// + /// Otherwise (aka when `size_hint().1 == Some(0)`), this is UB. + /// + /// # Note to Implementers + /// + /// This has a default implementation using [`Option::unwrap_unchecked`]. + /// That's probably sufficient if your `next` *always* returns `Some`, + /// such as for infinite iterators. In more complicated situations, however, + /// sometimes there can still be `insertvalue`/`assume`/`extractvalue` + /// instructions remaining in the IR from the `Option` handling, at which + /// point you might want to implement this manually instead. + #[unstable(feature = "trusted_len_next_unchecked", issue = "37572")] + #[inline] + unsafe fn next_unchecked(&mut self) -> Self::Item { + let opt = self.next(); + // SAFETY: The caller promised that we're not empty, and + // `Self: TrustedLen` so we can actually trust the `size_hint`. + unsafe { opt.unwrap_unchecked() } + } +} |