diff options
| -rw-r--r-- | compiler/rustc_ast/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_hir/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_index/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_index/src/vec.rs | 7 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_mir/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_mir_build/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_passes/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_query_system/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_span/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_target/src/lib.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_type_ir/src/lib.rs | 3 | ||||
| -rw-r--r-- | library/core/src/iter/mod.rs | 2 | ||||
| -rw-r--r-- | library/core/src/iter/range.rs | 468 | ||||
| -rw-r--r-- | library/core/src/iter/traits/marker.rs | 17 | ||||
| -rw-r--r-- | library/core/src/iter/traits/mod.rs | 2 | ||||
| -rw-r--r-- | library/core/tests/lib.rs | 1 | ||||
| -rw-r--r-- | src/test/mir-opt/remove_storage_markers.main.RemoveStorageMarkers.diff | 25 | ||||
| -rw-r--r-- | src/test/ui/impl-trait/example-calendar.rs | 3 |
20 files changed, 423 insertions, 122 deletions
diff --git a/compiler/rustc_ast/src/lib.rs b/compiler/rustc_ast/src/lib.rs index 0f6e0fb8825..14ecf27813d 100644 --- a/compiler/rustc_ast/src/lib.rs +++ b/compiler/rustc_ast/src/lib.rs @@ -17,6 +17,8 @@ #![feature(iter_zip)] #![feature(label_break_value)] #![feature(nll)] +#![feature(min_specialization)] +#![feature(trusted_step)] #![recursion_limit = "256"] #[macro_use] diff --git a/compiler/rustc_hir/src/lib.rs b/compiler/rustc_hir/src/lib.rs index 6a12c917436..7f3c410b1ec 100644 --- a/compiler/rustc_hir/src/lib.rs +++ b/compiler/rustc_hir/src/lib.rs @@ -7,6 +7,8 @@ #![cfg_attr(bootstrap, feature(extended_key_value_attributes))] #![feature(in_band_lifetimes)] #![feature(once_cell)] +#![feature(min_specialization)] +#![feature(trusted_step)] #![recursion_limit = "256"] #[macro_use] diff --git a/compiler/rustc_index/src/lib.rs b/compiler/rustc_index/src/lib.rs index 4c73b7bf612..04d62391c02 100644 --- a/compiler/rustc_index/src/lib.rs +++ b/compiler/rustc_index/src/lib.rs @@ -6,6 +6,7 @@ #![feature(unboxed_closures)] #![feature(test)] #![feature(fn_traits)] +#![feature(trusted_step)] pub mod bit_set; pub mod vec; diff --git a/compiler/rustc_index/src/vec.rs b/compiler/rustc_index/src/vec.rs index 1b1a59a254e..3f759f4023b 100644 --- a/compiler/rustc_index/src/vec.rs +++ b/compiler/rustc_index/src/vec.rs @@ -65,7 +65,7 @@ impl Idx for u32 { /// `u32::MAX`. You can also customize things like the `Debug` impl, /// what traits are derived, and so forth via the macro. #[macro_export] -#[allow_internal_unstable(step_trait, step_trait_ext, rustc_attrs)] +#[allow_internal_unstable(step_trait, rustc_attrs)] macro_rules! newtype_index { // ---- public rules ---- @@ -184,7 +184,7 @@ macro_rules! newtype_index { } } - unsafe impl ::std::iter::Step for $type { + impl ::std::iter::Step for $type { #[inline] fn steps_between(start: &Self, end: &Self) -> Option<usize> { <usize as ::std::iter::Step>::steps_between( @@ -204,6 +204,9 @@ macro_rules! newtype_index { } } + // Safety: The implementation of `Step` upholds all invariants. + unsafe impl ::std::iter::TrustedStep for $type {} + impl From<$type> for u32 { #[inline] fn from(v: $type) -> u32 { diff --git a/compiler/rustc_infer/src/lib.rs b/compiler/rustc_infer/src/lib.rs index f3e5830c198..6b452bca8e7 100644 --- a/compiler/rustc_infer/src/lib.rs +++ b/compiler/rustc_infer/src/lib.rs @@ -22,6 +22,8 @@ #![feature(never_type)] #![feature(in_band_lifetimes)] #![feature(control_flow_enum)] +#![feature(min_specialization)] +#![feature(trusted_step)] #![recursion_limit = "512"] // For rustdoc #[macro_use] diff --git a/compiler/rustc_middle/src/lib.rs b/compiler/rustc_middle/src/lib.rs index 7e85f5d5de2..6f97716e2e0 100644 --- a/compiler/rustc_middle/src/lib.rs +++ b/compiler/rustc_middle/src/lib.rs @@ -50,6 +50,7 @@ #![feature(associated_type_defaults)] #![feature(iter_zip)] #![feature(thread_local_const_init)] +#![feature(trusted_step)] #![recursion_limit = "512"] #[macro_use] diff --git a/compiler/rustc_mir/src/lib.rs b/compiler/rustc_mir/src/lib.rs index 010da247b2e..647c368d2bb 100644 --- a/compiler/rustc_mir/src/lib.rs +++ b/compiler/rustc_mir/src/lib.rs @@ -31,6 +31,7 @@ Rust MIR: a lowered representation of Rust. #![feature(option_get_or_insert_default)] #![feature(once_cell)] #![feature(control_flow_enum)] +#![feature(trusted_step)] #![recursion_limit = "256"] #[macro_use] diff --git a/compiler/rustc_mir_build/src/lib.rs b/compiler/rustc_mir_build/src/lib.rs index e4a71b52b78..99b854ff066 100644 --- a/compiler/rustc_mir_build/src/lib.rs +++ b/compiler/rustc_mir_build/src/lib.rs @@ -10,6 +10,8 @@ #![feature(bool_to_option)] #![feature(iter_zip)] #![feature(once_cell)] +#![feature(min_specialization)] +#![feature(trusted_step)] #![recursion_limit = "256"] #[macro_use] diff --git a/compiler/rustc_passes/src/lib.rs b/compiler/rustc_passes/src/lib.rs index fdcb2293a41..4803148eba9 100644 --- a/compiler/rustc_passes/src/lib.rs +++ b/compiler/rustc_passes/src/lib.rs @@ -10,6 +10,8 @@ #![feature(in_band_lifetimes)] #![feature(iter_zip)] #![feature(nll)] +#![feature(min_specialization)] +#![feature(trusted_step)] #![recursion_limit = "256"] #[macro_use] diff --git a/compiler/rustc_query_system/src/lib.rs b/compiler/rustc_query_system/src/lib.rs index be72baefb9e..7df3804c986 100644 --- a/compiler/rustc_query_system/src/lib.rs +++ b/compiler/rustc_query_system/src/lib.rs @@ -6,6 +6,7 @@ #![feature(iter_zip)] #![feature(min_specialization)] #![feature(stmt_expr_attributes)] +#![feature(trusted_step)] #[macro_use] extern crate tracing; diff --git a/compiler/rustc_span/src/lib.rs b/compiler/rustc_span/src/lib.rs index 0301b364591..39b7b36b853 100644 --- a/compiler/rustc_span/src/lib.rs +++ b/compiler/rustc_span/src/lib.rs @@ -21,6 +21,7 @@ #![feature(nll)] #![feature(min_specialization)] #![feature(thread_local_const_init)] +#![feature(trusted_step)] #[macro_use] extern crate rustc_macros; diff --git a/compiler/rustc_target/src/lib.rs b/compiler/rustc_target/src/lib.rs index 48ace9b65b6..a40de5ef18e 100644 --- a/compiler/rustc_target/src/lib.rs +++ b/compiler/rustc_target/src/lib.rs @@ -14,6 +14,8 @@ #![feature(never_type)] #![feature(associated_type_bounds)] #![feature(exhaustive_patterns)] +#![feature(min_specialization)] +#![feature(trusted_step)] use std::path::{Path, PathBuf}; diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs index 0dbcd483c45..3f4c8a72f1d 100644 --- a/compiler/rustc_type_ir/src/lib.rs +++ b/compiler/rustc_type_ir/src/lib.rs @@ -1,3 +1,6 @@ +#![feature(min_specialization)] +#![feature(trusted_step)] + #[macro_use] extern crate bitflags; #[macro_use] diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs index 2a179f0b1d7..bfb27da505e 100644 --- a/library/core/src/iter/mod.rs +++ b/library/core/src/iter/mod.rs @@ -384,6 +384,8 @@ pub use self::traits::FusedIterator; pub use self::traits::InPlaceIterable; #[unstable(feature = "trusted_len", issue = "37572")] pub use self::traits::TrustedLen; +#[unstable(feature = "trusted_step", issue = "85731")] +pub use self::traits::TrustedStep; #[stable(feature = "rust1", since = "1.0.0")] pub use self::traits::{ DoubleEndedIterator, ExactSizeIterator, Extend, FromIterator, IntoIterator, Product, Sum, diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs index 8d0b2b9f55c..de5d77e96ee 100644 --- a/library/core/src/iter/range.rs +++ b/library/core/src/iter/range.rs @@ -3,21 +3,23 @@ use crate::convert::TryFrom; use crate::mem; use crate::ops::{self, Try}; -use super::{FusedIterator, TrustedLen, TrustedRandomAccess}; +use super::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedStep}; + +// Safety: All invariants are upheld. +macro_rules! unsafe_impl_trusted_step { + ($($type:ty)*) => {$( + #[unstable(feature = "trusted_step", issue = "85731")] + unsafe impl TrustedStep for $type {} + )*}; +} +unsafe_impl_trusted_step![char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize]; /// Objects that have a notion of *successor* and *predecessor* operations. /// /// The *successor* operation moves towards values that compare greater. /// The *predecessor* operation moves towards values that compare lesser. -/// -/// # Safety -/// -/// This trait is `unsafe` because its implementation must be correct for -/// the safety of `unsafe trait TrustedLen` implementations, and the results -/// of using this trait can otherwise be trusted by `unsafe` code to be correct -/// and fulfill the listed obligations. #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] -pub unsafe trait Step: Clone + PartialOrd + Sized { +pub trait Step: Clone + PartialOrd + Sized { /// Returns the number of *successor* steps required to get from `start` to `end`. /// /// Returns `None` if the number of steps would overflow `usize` @@ -55,7 +57,6 @@ pub unsafe trait Step: Clone + PartialOrd + Sized { /// /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))` /// * Corollary: `Step::forward_checked(&a, 0) == Some(a)` - #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] fn forward_checked(start: Self, count: usize) -> Option<Self>; /// Returns the value that would be obtained by taking the *successor* @@ -81,7 +82,6 @@ pub unsafe trait Step: Clone + PartialOrd + Sized { /// * Corollary: `Step::forward(a, 0) == a` /// * `Step::forward(a, n) >= a` /// * `Step::backward(Step::forward(a, n), n) == a` - #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] fn forward(start: Self, count: usize) -> Self { Step::forward_checked(start, count).expect("overflow in `Step::forward`") } @@ -106,7 +106,6 @@ pub unsafe trait Step: Clone + PartialOrd + Sized { /// For any `a` and `n`, where no overflow occurs: /// /// * `Step::forward_unchecked(a, n)` is equivalent to `Step::forward(a, n)` - #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] unsafe fn forward_unchecked(start: Self, count: usize) -> Self { Step::forward(start, count) } @@ -127,7 +126,6 @@ pub unsafe trait Step: Clone + PartialOrd + Sized { /// /// * `Step::backward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::backward_checked(&x, 1))` /// * Corollary: `Step::backward_checked(&a, 0) == Some(a)` - #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] fn backward_checked(start: Self, count: usize) -> Option<Self>; /// Returns the value that would be obtained by taking the *predecessor* @@ -153,7 +151,6 @@ pub unsafe trait Step: Clone + PartialOrd + Sized { /// * Corollary: `Step::backward(a, 0) == a` /// * `Step::backward(a, n) <= a` /// * `Step::forward(Step::backward(a, n), n) == a` - #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] fn backward(start: Self, count: usize) -> Self { Step::backward_checked(start, count).expect("overflow in `Step::backward`") } @@ -178,7 +175,6 @@ pub unsafe trait Step: Clone + PartialOrd + Sized { /// For any `a` and `n`, where no overflow occurs: /// /// * `Step::backward_unchecked(a, n)` is equivalent to `Step::backward(a, n)` - #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] unsafe fn backward_unchecked(start: Self, count: usize) -> Self { Step::backward(start, count) } @@ -237,7 +233,7 @@ macro_rules! step_integer_impls { $( #[allow(unreachable_patterns)] #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] - unsafe impl Step for $u_narrower { + impl Step for $u_narrower { step_identical_methods!(); #[inline] @@ -269,7 +265,7 @@ macro_rules! step_integer_impls { #[allow(unreachable_patterns)] #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] - unsafe impl Step for $i_narrower { + impl Step for $i_narrower { step_identical_methods!(); #[inline] @@ -333,7 +329,7 @@ macro_rules! step_integer_impls { $( #[allow(unreachable_patterns)] #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] - unsafe impl Step for $u_wider { + impl Step for $u_wider { step_identical_methods!(); #[inline] @@ -358,7 +354,7 @@ macro_rules! step_integer_impls { #[allow(unreachable_patterns)] #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] - unsafe impl Step for $i_wider { + impl Step for $i_wider { step_identical_methods!(); #[inline] @@ -408,7 +404,7 @@ step_integer_impls! { } #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] -unsafe impl Step for char { +impl Step for char { #[inline] fn steps_between(&start: &char, &end: &char) -> Option<usize> { let start = start as u32; @@ -512,15 +508,27 @@ macro_rules! range_incl_exact_iter_impl { )*) } -#[stable(feature = "rust1", since = "1.0.0")] -impl<A: Step> Iterator for ops::Range<A> { +/// Specialization implementations for `Range`. +trait RangeIteratorImpl { + type Item; + + // Iterator + fn spec_next(&mut self) -> Option<Self::Item>; + fn spec_nth(&mut self, n: usize) -> Option<Self::Item>; + + // DoubleEndedIterator + fn spec_next_back(&mut self) -> Option<Self::Item>; + fn spec_nth_back(&mut self, n: usize) -> Option<Self::Item>; +} + +impl<A: Step> RangeIteratorImpl for ops::Range<A> { type Item = A; #[inline] - fn next(&mut self) -> Option<A> { + default fn spec_next(&mut self) -> Option<A> { if self.start < self.end { - // SAFETY: just checked precondition - let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; + let n = + Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld"); Some(mem::replace(&mut self.start, n)) } else { None @@ -528,17 +536,59 @@ impl<A: Step> Iterator for ops::Range<A> { } #[inline] - fn size_hint(&self) -> (usize, Option<usize>) { + default fn spec_nth(&mut self, n: usize) -> Option<A> { + if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { + if plus_n < self.end { + self.start = + Step::forward_checked(plus_n.clone(), 1).expect("`Step` invariants not upheld"); + return Some(plus_n); + } + } + + self.start = self.end.clone(); + None + } + + #[inline] + default fn spec_next_back(&mut self) -> Option<A> { if self.start < self.end { - let hint = Step::steps_between(&self.start, &self.end); - (hint.unwrap_or(usize::MAX), hint) + self.end = + Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld"); + Some(self.end.clone()) } else { - (0, Some(0)) + None } } #[inline] - fn nth(&mut self, n: usize) -> Option<A> { + default fn spec_nth_back(&mut self, n: usize) -> Option<A> { + if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { + if minus_n > self.start { + self.end = + Step::backward_checked(minus_n, 1).expect("`Step` invariants not upheld"); + return Some(self.end.clone()); + } + } + + self.end = self.start.clone(); + None + } +} + +impl<T: TrustedStep> RangeIteratorImpl for ops::Range<T> { + #[inline] + fn spec_next(&mut self) -> Option<T> { + if self.start < self.end { + // SAFETY: just checked precondition + let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; + Some(mem::replace(&mut self.start, n)) + } else { + None + } + } + + #[inline] + fn spec_nth(&mut self, n: usize) -> Option<T> { if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { if plus_n < self.end { // SAFETY: just checked precondition @@ -552,6 +602,56 @@ impl<A: Step> Iterator for ops::Range<A> { } #[inline] + fn spec_next_back(&mut self) -> Option<T> { + if self.start < self.end { + // SAFETY: just checked precondition + self.end = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; + Some(self.end.clone()) + } else { + None + } + } + + #[inline] + fn spec_nth_back(&mut self, n: usize) -> Option<T> { + if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { + if minus_n > self.start { + // SAFETY: just checked precondition + self.end = unsafe { Step::backward_unchecked(minus_n, 1) }; + return Some(self.end.clone()); + } + } + + self.end = self.start.clone(); + None + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<A: Step> Iterator for ops::Range<A> { + type Item = A; + + #[inline] + fn next(&mut self) -> Option<A> { + self.spec_next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + if self.start < self.end { + let hint = Step::steps_between(&self.start, &self.end); + (hint.unwrap_or(usize::MAX), hint) + } else { + (0, Some(0)) + } + } + + #[inline] + fn nth(&mut self, n: usize) -> Option<A> { + self.spec_nth(n) + } + + #[inline] fn last(mut self) -> Option<A> { self.next_back() } @@ -631,32 +731,36 @@ range_incl_exact_iter_impl! { impl<A: Step> DoubleEndedIterator for ops::Range<A> { #[inline] fn next_back(&mut self) -> Option<A> { - if self.start < self.end { - // SAFETY: just checked precondition - self.end = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; - Some(self.end.clone()) - } else { - None - } + self.spec_next_back() } #[inline] fn nth_back(&mut self, n: usize) -> Option<A> { - if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { - if minus_n > self.start { - // SAFETY: just checked precondition - self.end = unsafe { Step::backward_unchecked(minus_n, 1) }; - return Some(self.end.clone()); - } - } - - self.end = self.start.clone(); - None + self.spec_nth_back(n) } } +// Safety: +// The following invariants for `Step::steps_between` exist: +// +// > * `steps_between(&a, &b) == Some(n)` only if `a <= b` +// > * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`; +// > this is the case when it would require more than `usize::MAX` steps to +// > get to `b` +// > * `steps_between(&a, &b) == None` if `a > b` +// +// The first invariant is what is generally required for `TrustedLen` to be +// sound. The note addendum satisfies an additional `TrustedLen` invariant. +// +// > The upper bound must only be `None` if the actual iterator length is larger +// > than `usize::MAX` +// +// The second invariant logically follows the first so long as the `PartialOrd` +// implementation is correct; regardless it is explicitly stated. If `a < b` +// then `(0, Some(0))` is returned by `ops::Range<A: Step>::size_hint`. As such +// the second invariant is upheld. #[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<A: Step> TrustedLen for ops::Range<A> {} +unsafe impl<A: TrustedStep> TrustedLen for ops::Range<A> {} #[stable(feature = "fused", since = "1.26.0")] impl<A: Step> FusedIterator for ops::Range<A> {} @@ -684,18 +788,130 @@ impl<A: Step> Iterator for ops::RangeFrom<A> { } } +// Safety: See above implementation for `ops::Range<A>` +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl<A: TrustedStep> TrustedLen for ops::RangeFrom<A> {} + #[stable(feature = "fused", since = "1.26.0")] impl<A: Step> FusedIterator for ops::RangeFrom<A> {} -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {} +trait RangeInclusiveIteratorImpl { + type Item; -#[stable(feature = "inclusive_range", since = "1.26.0")] -impl<A: Step> Iterator for ops::RangeInclusive<A> { + // Iterator + fn spec_next(&mut self) -> Option<Self::Item>; + fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>; + + // DoubleEndedIterator + fn spec_next_back(&mut self) -> Option<Self::Item>; + fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>; +} + +impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> { type Item = A; #[inline] - fn next(&mut self) -> Option<A> { + default fn spec_next(&mut self) -> Option<A> { + if self.is_empty() { + return None; + } + let is_iterating = self.start < self.end; + Some(if is_iterating { + let n = + Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld"); + mem::replace(&mut self.start, n) + } else { + self.exhausted = true; + self.start.clone() + }) + } + + #[inline] + default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, A) -> R, + R: Try<Output = B>, + { + if self.is_empty() { + return try { init }; + } + + let mut accum = init; + + while self.start < self.end { + let n = + Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld"); + let n = mem::replace(&mut self.start, n); + accum = f(accum, n)?; + } + + self.exhausted = true; + + if self.start == self.end { + accum = f(accum, self.start.clone())?; + } + + try { accum } + } + + #[inline] + default fn spec_next_back(&mut self) -> Option<A> { + if self.is_empty() { + return None; + } + let is_iterating = self.start < self.end; + Some(if is_iterating { + let n = + Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld"); + mem::replace(&mut self.end, n) + } else { + self.exhausted = true; + self.end.clone() + }) + } + + #[inline] + default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, A) -> R, + R: Try<Output = B>, + { + if self.is_empty() { + return try { init }; + } + + let mut accum = init; + + while self.start < self.end { + let n = + Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld"); + let n = mem::replace(&mut self.end, n); + accum = f(accum, n)?; + } + + self.exhausted = true; + + if self.start == self.end { + accum = f(accum, self.start.clone())?; + } + + try { accum } + } +} + +impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> { + #[inline] + fn spec_next(&mut self) -> Option<T> { if self.is_empty() { return None; } @@ -711,6 +927,90 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> { } #[inline] + fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, T) -> R, + R: Try<Output = B>, + { + if self.is_empty() { + return try { init }; + } + + let mut accum = init; + + while self.start < self.end { + // SAFETY: just checked precondition + let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; + let n = mem::replace(&mut self.start, n); + accum = f(accum, n)?; + } + + self.exhausted = true; + + if self.start == self.end { + accum = f(accum, self.start.clone())?; + } + + try { accum } + } + + #[inline] + fn spec_next_back(&mut self) -> Option<T> { + if self.is_empty() { + return None; + } + let is_iterating = self.start < self.end; + Some(if is_iterating { + // SAFETY: just checked precondition + let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; + mem::replace(&mut self.end, n) + } else { + self.exhausted = true; + self.end.clone() + }) + } + + #[inline] + fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, T) -> R, + R: Try<Output = B>, + { + if self.is_empty() { + return try { init }; + } + + let mut accum = init; + + while self.start < self.end { + // SAFETY: just checked precondition + let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; + let n = mem::replace(&mut self.end, n); + accum = f(accum, n)?; + } + + self.exhausted = true; + + if self.start == self.end { + accum = f(accum, self.start.clone())?; + } + + try { accum } + } +} + +#[stable(feature = "inclusive_range", since = "1.26.0")] +impl<A: Step> Iterator for ops::RangeInclusive<A> { + type Item = A; + + #[inline] + fn next(&mut self) -> Option<A> { + self.spec_next() + } + + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { if self.is_empty() { return (0, Some(0)); @@ -751,32 +1051,13 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> { } #[inline] - fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R + fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Output = B>, { - if self.is_empty() { - return try { init }; - } - - let mut accum = init; - - while self.start < self.end { - // SAFETY: just checked precondition - let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; - let n = mem::replace(&mut self.start, n); - accum = f(accum, n)?; - } - - self.exhausted = true; - - if self.start == self.end { - accum = f(accum, self.start.clone())?; - } - - try { accum } + self.spec_try_fold(init, f) } #[inline] @@ -813,18 +1094,7 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> { impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> { #[inline] fn next_back(&mut self) -> Option<A> { - if self.is_empty() { - return None; - } - let is_iterating = self.start < self.end; - Some(if is_iterating { - // SAFETY: just checked precondition - let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; - mem::replace(&mut self.end, n) - } else { - self.exhausted = true; - self.end.clone() - }) + self.spec_next_back() } #[inline] @@ -856,32 +1126,13 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> { } #[inline] - fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R + fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Output = B>, { - if self.is_empty() { - return try { init }; - } - - let mut accum = init; - - while self.start < self.end { - // SAFETY: just checked precondition - let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) }; - let n = mem::replace(&mut self.end, n); - accum = f(accum, n)?; - } - - self.exhausted = true; - - if self.start == self.end { - accum = f(accum, self.start.clone())?; - } - - try { accum } + self.spec_try_rfold(init, f) } #[inline] @@ -899,8 +1150,9 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> { } } +// Safety: See above implementation for `ops::Range<A>` #[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<A: Step> TrustedLen for ops::RangeInclusive<A> {} +unsafe impl<A: TrustedStep> TrustedLen for ops::RangeInclusive<A> {} #[stable(feature = "fused", since = "1.26.0")] impl<A: Step> FusedIterator for ops::RangeInclusive<A> {} diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index 22b5ffdf886..ebf37f97bc6 100644 --- a/library/core/src/iter/traits/marker.rs +++ b/library/core/src/iter/traits/marker.rs @@ -1,3 +1,5 @@ +use crate::iter::Step; + /// An iterator that always continues to yield `None` when exhausted. /// /// Calling next on a fused iterator that has returned `None` once is guaranteed @@ -55,3 +57,18 @@ unsafe impl<I: TrustedLen + ?Sized> TrustedLen for &mut I {} #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] pub unsafe trait InPlaceIterable: Iterator {} + +/// A type that upholds all invariants of [`Step`]. +/// +/// The invariants of [`Step::steps_between()`] are a superset of the invariants +/// of [`TrustedLen`]. As such, [`TrustedLen`] is implemented for all range +/// types with the same generic type argument. +/// +/// # Safety +/// +/// The implementation of [`Step`] for the given type must guarantee all +/// invariants of all methods are upheld. See the [`Step`] trait's documentation +/// for details. Consumers are free to rely on the invariants in unsafe code. +#[unstable(feature = "trusted_step", issue = "85731")] +#[rustc_specialization_trait] +pub unsafe trait TrustedStep: Step {} diff --git a/library/core/src/iter/traits/mod.rs b/library/core/src/iter/traits/mod.rs index 880f8d831fd..ffd745a46b1 100644 --- a/library/core/src/iter/traits/mod.rs +++ b/library/core/src/iter/traits/mod.rs @@ -13,5 +13,7 @@ pub use self::exact_size::ExactSizeIterator; pub use self::iterator::Iterator; #[unstable(issue = "none", feature = "inplace_iteration")] pub use self::marker::InPlaceIterable; +#[unstable(feature = "trusted_step", issue = "85731")] +pub use self::marker::TrustedStep; #[stable(feature = "rust1", since = "1.0.0")] pub use self::marker::{FusedIterator, TrustedLen}; diff --git a/library/core/tests/lib.rs b/library/core/tests/lib.rs index 16bce6e35fe..16051b3bc36 100644 --- a/library/core/tests/lib.rs +++ b/library/core/tests/lib.rs @@ -40,7 +40,6 @@ #![feature(maybe_uninit_write_slice)] #![feature(min_specialization)] #![feature(step_trait)] -#![feature(step_trait_ext)] #![feature(str_internals)] #![feature(test)] #![feature(trusted_len)] diff --git a/src/test/mir-opt/remove_storage_markers.main.RemoveStorageMarkers.diff b/src/test/mir-opt/remove_storage_markers.main.RemoveStorageMarkers.diff index dd8a9251042..80024124dc5 100644 --- a/src/test/mir-opt/remove_storage_markers.main.RemoveStorageMarkers.diff +++ b/src/test/mir-opt/remove_storage_markers.main.RemoveStorageMarkers.diff @@ -32,6 +32,10 @@ scope 5 { debug i => _15; // in scope 5 at $DIR/remove_storage_markers.rs:8:9: 8:10 } + scope 7 (inlined iter::range::<impl Iterator for std::ops::Range<i32>>::next) { // at $DIR/remove_storage_markers.rs:8:14: 8:19 + debug self => _9; // in scope 7 at $DIR/remove_storage_markers.rs:8:14: 8:19 + let mut _18: &mut std::ops::Range<i32>; // in scope 7 at $DIR/remove_storage_markers.rs:8:14: 8:19 + } } } scope 6 (inlined <std::ops::Range<i32> as IntoIterator>::into_iter) { // at $DIR/remove_storage_markers.rs:8:14: 8:19 @@ -61,19 +65,15 @@ - StorageLive(_10); // scope 3 at $DIR/remove_storage_markers.rs:8:14: 8:19 _10 = &mut _4; // scope 3 at $DIR/remove_storage_markers.rs:8:14: 8:19 _9 = &mut (*_10); // scope 3 at $DIR/remove_storage_markers.rs:8:14: 8:19 - _8 = <std::ops::Range<i32> as Iterator>::next(move _9) -> bb2; // scope 3 at $DIR/remove_storage_markers.rs:8:14: 8:19 +- StorageLive(_18); // scope 7 at $DIR/remove_storage_markers.rs:8:14: 8:19 + _18 = &mut (*_9); // scope 7 at $DIR/remove_storage_markers.rs:8:14: 8:19 + _8 = <std::ops::Range<i32> as iter::range::RangeIteratorImpl>::spec_next(move _18) -> bb4; // scope 7 at $DIR/remove_storage_markers.rs:8:14: 8:19 // mir::Constant // + span: $DIR/remove_storage_markers.rs:8:14: 8:19 - // + literal: Const { ty: for<'r> fn(&'r mut std::ops::Range<i32>) -> std::option::Option<<std::ops::Range<i32> as std::iter::Iterator>::Item> {<std::ops::Range<i32> as std::iter::Iterator>::next}, val: Value(Scalar(<ZST>)) } + // + literal: Const { ty: for<'r> fn(&'r mut std::ops::Range<i32>) -> std::option::Option<<std::ops::Range<i32> as std::iter::range::RangeIteratorImpl>::Item> {<std::ops::Range<i32> as std::iter::range::RangeIteratorImpl>::spec_next}, val: Value(Scalar(<ZST>)) } } bb2: { -- StorageDead(_9); // scope 3 at $DIR/remove_storage_markers.rs:8:18: 8:19 - _11 = discriminant(_8); // scope 3 at $DIR/remove_storage_markers.rs:8:9: 8:10 - switchInt(move _11) -> [0_isize: bb3, otherwise: bb4]; // scope 3 at $DIR/remove_storage_markers.rs:8:9: 8:10 - } - - bb3: { _0 = const (); // scope 3 at $DIR/remove_storage_markers.rs:8:5: 10:6 - StorageDead(_10); // scope 3 at $DIR/remove_storage_markers.rs:8:18: 8:19 - StorageDead(_8); // scope 3 at $DIR/remove_storage_markers.rs:8:18: 8:19 @@ -85,7 +85,7 @@ return; // scope 0 at $DIR/remove_storage_markers.rs:11:2: 11:2 } - bb4: { + bb3: { - StorageLive(_12); // scope 3 at $DIR/remove_storage_markers.rs:8:9: 8:10 _12 = ((_8 as Some).0: i32); // scope 3 at $DIR/remove_storage_markers.rs:8:9: 8:10 - StorageLive(_13); // scope 4 at $DIR/remove_storage_markers.rs:8:9: 8:10 @@ -111,5 +111,12 @@ - StorageDead(_6); // scope 2 at $DIR/remove_storage_markers.rs:10:5: 10:6 goto -> bb1; // scope 2 at $DIR/remove_storage_markers.rs:8:5: 10:6 } + + bb4: { +- StorageDead(_18); // scope 7 at $DIR/remove_storage_markers.rs:8:14: 8:19 +- StorageDead(_9); // scope 3 at $DIR/remove_storage_markers.rs:8:18: 8:19 + _11 = discriminant(_8); // scope 3 at $DIR/remove_storage_markers.rs:8:9: 8:10 + switchInt(move _11) -> [0_isize: bb2, otherwise: bb3]; // scope 3 at $DIR/remove_storage_markers.rs:8:9: 8:10 + } } diff --git a/src/test/ui/impl-trait/example-calendar.rs b/src/test/ui/impl-trait/example-calendar.rs index 238f3fa31ed..45dcb74a6e0 100644 --- a/src/test/ui/impl-trait/example-calendar.rs +++ b/src/test/ui/impl-trait/example-calendar.rs @@ -3,7 +3,6 @@ #![feature(fn_traits, step_trait, - step_trait_ext, unboxed_closures, )] @@ -157,7 +156,7 @@ impl<'a, 'b> std::ops::Add<&'b NaiveDate> for &'a NaiveDate { } } -unsafe impl std::iter::Step for NaiveDate { +impl std::iter::Step for NaiveDate { fn steps_between(_: &Self, _: &Self) -> Option<usize> { unimplemented!() } |