Auto merge of #69659 - CAD97:step-rework-take-3, r=Amanieu

Rework the std::iter::Step trait

Previous attempts: #43127 #62886 #68807
Tracking issue: #42168

This PR reworks the `Step` trait to be phrased in terms of the *successor* and *predecessor* operations. With this, `Step` hopefully has a consistent identity that can have a path towards stabilization. The proposed trait:

```rust
/// 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 fulful the listed obligations.
pub unsafe 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`
    /// (or is infinite, or if `end` would never be reached).
    ///
    /// # Invariants
    ///
    /// For any `a`, `b`, and `n`:
    ///
    /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::forward(&a, n) == Some(b)`
    /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::backward(&a, n) == Some(a)`
    /// * `steps_between(&a, &b) == Some(n)` only if `a <= b`
    ///   * Corollary: `steps_between(&a, &b) == Some(0)` if and only if `a == b`
    ///   * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`;
    ///     this is the case wheen it would require more than `usize::MAX` steps to get to `b`
    /// * `steps_between(&a, &b) == None` if `a > b`
    fn steps_between(start: &Self, end: &Self) -> Option<usize>;

    /// Returns the value that would be obtained by taking the *successor*
    /// of `self` `count` times.
    ///
    /// If this would overflow the range of values supported by `Self`, returns `None`.
    ///
    /// # Invariants
    ///
    /// For any `a`, `n`, and `m`:
    ///
    /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, m).and_then(|x| Step::forward_checked(x, n))`
    ///
    /// For any `a`, `n`, and `m` where `n + m` does not overflow:
    ///
    /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, n + m)`
    ///
    /// For any `a` and `n`:
    ///
    /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))`
    ///   * Corollary: `Step::forward_checked(&a, 0) == Some(a)`
    fn forward_checked(start: Self, count: usize) -> Option<Self>;

    /// Returns the value that would be obtained by taking the *successor*
    /// of `self` `count` times.
    ///
    /// If this would overflow the range of values supported by `Self`,
    /// this function is allowed to panic, wrap, or saturate.
    /// The suggested behavior is to panic when debug assertions are enabled,
    /// and to wrap or saturate otherwise.
    ///
    /// Unsafe code should not rely on the correctness of behavior after overflow.
    ///
    /// # Invariants
    ///
    /// For any `a`, `n`, and `m`, where no overflow occurs:
    ///
    /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)`
    ///
    /// For any `a` and `n`, where no overflow occurs:
    ///
    /// * `Step::forward_checked(a, n) == Some(Step::forward(a, n))`
    /// * `Step::forward(a, n) == (0..n).fold(a, |x, _| Step::forward(x, 1))`
    ///   * Corollary: `Step::forward(a, 0) == a`
    /// * `Step::forward(a, n) >= a`
    /// * `Step::backward(Step::forward(a, n), n) == a`
    fn forward(start: Self, count: usize) -> Self {
        Step::forward_checked(start, count).expect("overflow in `Step::forward`")
    }

    /// Returns the value that would be obtained by taking the *successor*
    /// of `self` `count` times.
    ///
    /// # Safety
    ///
    /// It is undefined behavior for this operation to overflow the
    /// range of values supported by `Self`. If you cannot guarantee that this
    /// will not overflow, use `forward` or `forward_checked` instead.
    ///
    /// # Invariants
    ///
    /// For any `a`:
    ///
    /// * if there exists `b` such that `b > a`, it is safe to call `Step::forward_unchecked(a, 1)`
    /// * if there exists `b`, `n` such that `steps_between(&a, &b) == Some(n)`,
    ///   it is safe to call `Step::forward_unchecked(a, m)` for any `m <= n`.
    ///
    /// For any `a` and `n`, where no overflow occurs:
    ///
    /// * `Step::forward_unchecked(a, n)` is equivalent to `Step::forward(a, n)`
    #[unstable(feature = "unchecked_math", reason = "niche optimization path", issue = "none")]
    unsafe fn forward_unchecked(start: Self, count: usize) -> Self {
        Step::forward(start, count)
    }

    /// Returns the value that would be obtained by taking the *successor*
    /// of `self` `count` times.
    ///
    /// If this would overflow the range of values supported by `Self`, returns `None`.
    ///
    /// # Invariants
    ///
    /// For any `a`, `n`, and `m`:
    ///
    /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == n.checked_add(m).and_then(|x| Step::backward_checked(a, x))`
    /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == try { Step::backward_checked(a, n.checked_add(m)?) }`
    ///
    /// For any `a` and `n`:
    ///
    /// * `Step::backward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::backward_checked(&x, 1))`
    ///   * Corollary: `Step::backward_checked(&a, 0) == Some(a)`
    fn backward_checked(start: Self, count: usize) -> Option<Self>;

    /// Returns the value that would be obtained by taking the *predecessor*
    /// of `self` `count` times.
    ///
    /// If this would overflow the range of values supported by `Self`,
    /// this function is allowed to panic, wrap, or saturate.
    /// The suggested behavior is to panic when debug assertions are enabled,
    /// and to wrap or saturate otherwise.
    ///
    /// Unsafe code should not rely on the correctness of behavior after overflow.
    ///
    /// # Invariants
    ///
    /// For any `a`, `n`, and `m`, where no overflow occurs:
    ///
    /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)`
    ///
    /// For any `a` and `n`, where no overflow occurs:
    ///
    /// * `Step::backward_checked(a, n) == Some(Step::backward(a, n))`
    /// * `Step::backward(a, n) == (0..n).fold(a, |x, _| Step::backward(x, 1))`
    ///   * Corollary: `Step::backward(a, 0) == a`
    /// * `Step::backward(a, n) <= a`
    /// * `Step::forward(Step::backward(a, n), n) == a`
    fn backward(start: Self, count: usize) -> Self {
        Step::backward_checked(start, count).expect("overflow in `Step::backward`")
    }

    /// Returns the value that would be obtained by taking the *predecessor*
    /// of `self` `count` times.
    ///
    /// # Safety
    ///
    /// It is undefined behavior for this operation to overflow the
    /// range of values supported by `Self`. If you cannot guarantee that this
    /// will not overflow, use `backward` or `backward_checked` instead.
    ///
    /// # Invariants
    ///
    /// For any `a`:
    ///
    /// * if there exists `b` such that `b < a`, it is safe to call `Step::backward_unchecked(a, 1)`
    /// * if there exists `b`, `n` such that `steps_between(&b, &a) == Some(n)`,
    ///   it is safe to call `Step::backward_unchecked(a, m)` for any `m <= n`.
    ///
    /// For any `a` and `n`, where no overflow occurs:
    ///
    /// * `Step::backward_unchecked(a, n)` is equivalent to `Step::backward(a, n)`
    #[unstable(feature = "unchecked_math", reason = "niche optimization path", issue = "none")]
    unsafe fn backward_unchecked(start: Self, count: usize) -> Self {
        Step::backward(start, count)
    }
}
```

Note that all of these are associated functions and not callable via method syntax; the calling syntax is always `Step::forward(start, n)`. This version of the trait additionally changes the stepping functions to talk their arguments by value.

As opposed to previous attempts which provided a "step by one" method directly, this version of the trait only exposes "step by n". There are a few reasons for this:

- `Range*`, the primary consumer of `Step`, assumes that the "step by n" operation is cheap. If a single step function is provided, it will be a lot more enticing to implement "step by n" as n repeated calls to "step by one". While this is not strictly incorrect, this behavior would be surprising for anyone used to using `Range<{primitive integer}>`.
- With a trivial default impl, this can be easily added backwards-compatibly later.
- The debug-wrapping "step by n" needs to exist for `RangeFrom` to be consistent between "step by n" and "step by one" operation. (Note: the behavior is not changed by this PR, but making the behavior consistent is made tenable by this PR.)

Three "kinds" of step are provided: `_checked`, which returns an `Option` indicating attempted overflow; (unsuffixed), which provides "safe overflow" behavior (is allowed to panic, wrap, or saturate, depending on what is most convenient for a given type); and `_unchecked`, which is a version which assumes overflow does not happen.

Review is appreciated to check that:

- The invariants as described on the `Step` functions are enough to specify the "common sense" consistency for successor/predecessor.
- Implementation of `Step` functions is correct in the face of overflow and the edges of representable integers.
- Added tests of `Step` functions are asserting the correct behavior (and not just the implemented behavior).

2 files changed, 95 insertions, 27 deletions

diff --git a/src/libcore/tests/iter.rs b/src/libcore/tests/iter.rs
index 7da02b11676..52cf068f0a5 100644
--- a/src/libcore/tests/iter.rs
+++ b/src/libcore/tests/iter.rs
@@ -2140,6 +2140,24 @@ fn test_range_inclusive_nth_back() {
 }
 
 #[test]
+fn test_range_len() {
+    assert_eq!((0..10_u8).len(), 10);
+    assert_eq!((9..10_u8).len(), 1);
+    assert_eq!((10..10_u8).len(), 0);
+    assert_eq!((11..10_u8).len(), 0);
+    assert_eq!((100..10_u8).len(), 0);
+}
+
+#[test]
+fn test_range_inclusive_len() {
+    assert_eq!((0..=10_u8).len(), 11);
+    assert_eq!((9..=10_u8).len(), 2);
+    assert_eq!((10..=10_u8).len(), 1);
+    assert_eq!((11..=10_u8).len(), 0);
+    assert_eq!((100..=10_u8).len(), 0);
+}
+
+#[test]
 fn test_range_step() {
     #![allow(deprecated)]
 
@@ -2509,42 +2527,91 @@ fn test_chain_fold() {
 }
 
 #[test]
-fn test_step_replace_unsigned() {
-    let mut x = 4u32;
-    let y = x.replace_zero();
-    assert_eq!(x, 0);
-    assert_eq!(y, 4);
+fn test_steps_between() {
+    assert_eq!(Step::steps_between(&20_u8, &200_u8), Some(180_usize));
+    assert_eq!(Step::steps_between(&-20_i8, &80_i8), Some(100_usize));
+    assert_eq!(Step::steps_between(&-120_i8, &80_i8), Some(200_usize));
+    assert_eq!(Step::steps_between(&20_u32, &4_000_100_u32), Some(4_000_080_usize));
+    assert_eq!(Step::steps_between(&-20_i32, &80_i32), Some(100_usize));
+    assert_eq!(Step::steps_between(&-2_000_030_i32, &2_000_050_i32), Some(4_000_080_usize));
 
-    x = 5;
-    let y = x.replace_one();
-    assert_eq!(x, 1);
-    assert_eq!(y, 5);
+    // Skip u64/i64 to avoid differences with 32-bit vs 64-bit platforms
+
+    assert_eq!(Step::steps_between(&20_u128, &200_u128), Some(180_usize));
+    assert_eq!(Step::steps_between(&-20_i128, &80_i128), Some(100_usize));
+    if cfg!(target_pointer_width = "64") {
+        assert_eq!(Step::steps_between(&10_u128, &0x1_0000_0000_0000_0009_u128), Some(usize::MAX));
+    }
+    assert_eq!(Step::steps_between(&10_u128, &0x1_0000_0000_0000_000a_u128), None);
+    assert_eq!(Step::steps_between(&10_i128, &0x1_0000_0000_0000_000a_i128), None);
+    assert_eq!(
+        Step::steps_between(&-0x1_0000_0000_0000_0000_i128, &0x1_0000_0000_0000_0000_i128,),
+        None,
+    );
 }
 
 #[test]
-fn test_step_replace_signed() {
-    let mut x = 4i32;
-    let y = x.replace_zero();
-    assert_eq!(x, 0);
-    assert_eq!(y, 4);
+fn test_step_forward() {
+    assert_eq!(Step::forward_checked(55_u8, 200_usize), Some(255_u8));
+    assert_eq!(Step::forward_checked(252_u8, 200_usize), None);
+    assert_eq!(Step::forward_checked(0_u8, 256_usize), None);
+    assert_eq!(Step::forward_checked(-110_i8, 200_usize), Some(90_i8));
+    assert_eq!(Step::forward_checked(-110_i8, 248_usize), None);
+    assert_eq!(Step::forward_checked(-126_i8, 256_usize), None);
+
+    assert_eq!(Step::forward_checked(35_u16, 100_usize), Some(135_u16));
+    assert_eq!(Step::forward_checked(35_u16, 65500_usize), Some(u16::MAX));
+    assert_eq!(Step::forward_checked(36_u16, 65500_usize), None);
+    assert_eq!(Step::forward_checked(-110_i16, 200_usize), Some(90_i16));
+    assert_eq!(Step::forward_checked(-20_030_i16, 50_050_usize), Some(30_020_i16));
+    assert_eq!(Step::forward_checked(-10_i16, 40_000_usize), None);
+    assert_eq!(Step::forward_checked(-10_i16, 70_000_usize), None);
 
-    x = 5;
-    let y = x.replace_one();
-    assert_eq!(x, 1);
-    assert_eq!(y, 5);
+    assert_eq!(Step::forward_checked(10_u128, 70_000_usize), Some(70_010_u128));
+    assert_eq!(Step::forward_checked(10_i128, 70_030_usize), Some(70_040_i128));
+    assert_eq!(
+        Step::forward_checked(0xffff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_u128, 0xff_usize),
+        Some(u128::MAX),
+    );
+    assert_eq!(
+        Step::forward_checked(0xffff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_u128, 0x100_usize),
+        None
+    );
+    assert_eq!(
+        Step::forward_checked(0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0xff_usize),
+        Some(i128::MAX),
+    );
+    assert_eq!(
+        Step::forward_checked(0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0x100_usize),
+        None
+    );
 }
 
 #[test]
-fn test_step_replace_no_between() {
-    let mut x = 4u128;
-    let y = x.replace_zero();
-    assert_eq!(x, 0);
-    assert_eq!(y, 4);
+fn test_step_backward() {
+    assert_eq!(Step::backward_checked(255_u8, 200_usize), Some(55_u8));
+    assert_eq!(Step::backward_checked(100_u8, 200_usize), None);
+    assert_eq!(Step::backward_checked(255_u8, 256_usize), None);
+    assert_eq!(Step::backward_checked(90_i8, 200_usize), Some(-110_i8));
+    assert_eq!(Step::backward_checked(110_i8, 248_usize), None);
+    assert_eq!(Step::backward_checked(127_i8, 256_usize), None);
+
+    assert_eq!(Step::backward_checked(135_u16, 100_usize), Some(35_u16));
+    assert_eq!(Step::backward_checked(u16::MAX, 65500_usize), Some(35_u16));
+    assert_eq!(Step::backward_checked(10_u16, 11_usize), None);
+    assert_eq!(Step::backward_checked(90_i16, 200_usize), Some(-110_i16));
+    assert_eq!(Step::backward_checked(30_020_i16, 50_050_usize), Some(-20_030_i16));
+    assert_eq!(Step::backward_checked(-10_i16, 40_000_usize), None);
+    assert_eq!(Step::backward_checked(-10_i16, 70_000_usize), None);
 
-    x = 5;
-    let y = x.replace_one();
-    assert_eq!(x, 1);
-    assert_eq!(y, 5);
+    assert_eq!(Step::backward_checked(70_010_u128, 70_000_usize), Some(10_u128));
+    assert_eq!(Step::backward_checked(70_020_i128, 70_030_usize), Some(-10_i128));
+    assert_eq!(Step::backward_checked(10_u128, 7_usize), Some(3_u128));
+    assert_eq!(Step::backward_checked(10_u128, 11_usize), None);
+    assert_eq!(
+        Step::backward_checked(-0x7fff_ffff_ffff_ffff__ffff_ffff_ffff_ff00_i128, 0x100_usize),
+        Some(i128::MIN)
+    );
 }
 
 #[test]
diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs
index e7d36d327cd..d636542d699 100644
--- a/src/libcore/tests/lib.rs
+++ b/src/libcore/tests/lib.rs
@@ -22,6 +22,7 @@
 #![feature(slice_partition_at_index)]
 #![feature(specialization)]
 #![feature(step_trait)]
+#![feature(step_trait_ext)]
 #![feature(str_internals)]
 #![feature(test)]
 #![feature(trusted_len)]