Specialize implementations

Implementations in stdlib are now optimized as they were before.

17 files changed, 399 insertions, 105 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 9cf6756a090..440e0943d6e 100644
--- a/compiler/rustc_index/src/vec.rs
+++ b/compiler/rustc_index/src/vec.rs
@@ -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 63e6181cae2..bb7d3d04806 100644
--- a/library/core/src/iter/range.rs
+++ b/library/core/src/iter/range.rs
@@ -3,7 +3,16 @@ 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.
 ///
@@ -505,12 +514,24 @@ 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 {
             let n =
                 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
@@ -521,21 +542,63 @@ 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 {
-                self.start =
-                    Step::forward_checked(plus_n.clone(), 1).expect("`Step` invariants not upheld");
+                // SAFETY: just checked precondition
+                self.start = unsafe { Step::forward_unchecked(plus_n.clone(), 1) };
                 return Some(plus_n);
             }
         }
@@ -545,6 +608,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()
     }
@@ -624,37 +737,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 {
-            self.end =
-                Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
-            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 {
-                self.end =
-                    Step::backward_checked(minus_n, 1).expect("`Step` invariants not upheld");
-                return Some(self.end.clone());
-            }
-        }
-
-        self.end = self.start.clone();
-        None
+        self.spec_nth_back(n)
     }
 }
 
-macro_rules! impl_trusted_len_for_range {
-    ($($type:ty)*) => {$(
-        #[unstable(feature = "trusted_len", issue = "37572")]
-        unsafe impl TrustedLen for ops::Range<$type> {}
-    )*}
-}
-impl_trusted_len_for_range![char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize];
+// 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: TrustedStep> TrustedLen for ops::Range<A> {}
 
 #[stable(feature = "fused", since = "1.26.0")]
 impl<A: Step> FusedIterator for ops::Range<A> {}
@@ -682,23 +794,38 @@ 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> {}
 
-macro_rules! impl_trusted_len_for_range_from {
-    ($($type:ty)*) => {$(
-        #[unstable(feature = "trusted_len", issue = "37572")]
-        unsafe impl TrustedLen for ops::RangeFrom<$type> {}
-    )*}
+trait RangeInclusiveIteratorImpl {
+    type Item;
+
+    // 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_trusted_len_for_range_from![char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize];
 
-#[stable(feature = "inclusive_range", since = "1.26.0")]
-impl<A: Step> Iterator for ops::RangeInclusive<A> {
+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;
         }
@@ -714,6 +841,182 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
     }
 
     #[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;
+        }
+        let is_iterating = self.start < self.end;
+        Some(if is_iterating {
+            // SAFETY: just checked precondition
+            let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) };
+            mem::replace(&mut self.start, n)
+        } else {
+            self.exhausted = true;
+            self.start.clone()
+        })
+    }
+
+    #[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));
@@ -754,32 +1057,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 {
-            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 }
+        self.spec_try_fold(init, f)
     }
 
     #[inline]
@@ -816,18 +1100,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 {
-            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()
-        })
+        self.spec_next_back()
     }
 
     #[inline]
@@ -859,32 +1132,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 {
-            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 }
+        self.spec_try_rfold(init, f)
     }
 
     #[inline]
@@ -902,13 +1156,9 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
     }
 }
 
-macro_rules! impl_trusted_len_for_range_inclusive {
-    ($($type:ty)*) => {$(
-        #[unstable(feature = "trusted_len", issue = "37572")]
-        unsafe impl TrustedLen for ops::RangeInclusive<$type> {}
-    )*}
-}
-impl_trusted_len_for_range_inclusive![char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize];
+// Safety: See above implementation for `ops::Range<A>`
+#[unstable(feature = "trusted_len", issue = "37572")]
+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};