Tracking issue for step_trait stabilization

[scottmcm]

Split off from #27741 because the stabilization path for step_by has moved to being on iterators (#41439), and thus not using the Step trait.

• Remove step, steps_between, and is_negative once Range::step_by is deleted
• Replace replace_zero and replace_one with something more useful (some options: Make RangeInclusive just a two-field struct (amend 1192) rfcs#1980 (comment))
• Change steps_between_by_one so that Range<u128> can be TrustedLen (rather than it only working well with types that fit in usize)
• Make a decision on how steps_between should work Step::steps_between does not distinguish overflow and unimplemented (unstable) #48117

(and probably more)

[scottmcm]

Some progress on this in #42534

[SimonSapin]

PR #43077 does items 1 and 3 in the original message of this issue.

[SimonSapin]

I’ve removed the i128/u128 stuff from my PR because I suspect my mixed-signdeness mixed-width interger arithmetic was buggy. I also massaged the Step trait some more and came up with this:

/// Supporting trait for allowing ranges of various different types to be iterators.
#[unstable(feature = "step_trait",
           reason = "recently redesigned",
           issue = "42168")]
pub trait Step: Clone + PartialOrd + Sized {
    /// Returns the number of steps between two step objects. The count is
    /// inclusive of `start` and exclusive of `end`.
    ///
    /// Returns `None` if it is not possible to calculate `steps_between`
    /// without overflow.
    fn steps_between(start: &Self, end: &Self) -> Option<usize>;

    /// “Go forward” (for integers, add) the given number of steps, returning None on overflow.
    fn forward(&self, step_count: usize) -> Option<Self>;

    /// “Go backward” (for integers, subtract) the given number of steps, returning None on overflow.
    fn backward(&self, step_count: usize) -> Option<Self>;

    /// Modify the given inclusive range so that it becomes empty,
    /// for example by setting it to `1...0`.
    fn make_inclusive_range_empty(range: &mut ops::RangeInclusive<Self>);
}

How does it look?

I’m a bit uncertain of the exact impls for integers, there is up to 6 cases to consider: {smaller, same width, larger} than usize/isize × {signed, unsigned}.

[SimonSapin]

I’ve tweaked this design some more and opened #43127. I believe that PR fixes every issue I know of around the Step trait.

[SimonSapin]

I’ve closed that PR since it needs more work that I’m not planning to do soon: #43127 (comment). Hopefully someone else can take over.

[pnkfelix]

I just wanted to leave a note saying that if methods with the behavior of fn replace_one/fn replace_zero stay, I hope they have names that look more like fn replace_with_one/fn replace_with_zero, because the way that my head reads the phrase replace_one is "replace one of these" and replace_zero is as "replace zero of these". (Which are both weird things to say in a method, admittedly, but nonetheless, I'd prefer clearer names.)

Having said that, it sounds like these methods are scheduled to be either removed or replaced with something more generally useful?

Update: (maybe if I care about this, I should spend effort reviving PR #43127...)

[Lucretiel]

Follow up: per this Stack Overflow thread, it might be worth coming up with new names for replace_one and replace_zero, since in practice those methods are only used to create an empty InclusiveRange, and not all rangeable types (for instance, a Date type) have meaningful zero or one values.

[khoover]

Why is PartialOrd<Self> a supertrait and not Ord? If it is required that every successor be >= than its predecessor and every element has a successor, then it is trivial to show that the order is total.

Consider a newtype pub struct StepByTwos(pub u32), which will only ever step by 2 over a given range (or more broadly, any type representing a union of two disjoint ordered groups). We also implement PartialOrd for it, where two values are comparable iff both values are even or both are odd (and otherwise using normal integer comparison). This can be made to have a total order, sure, but in its existing state it is not, while still being able to impl Step in a way compatible with all the invariants. Is the example contrived? Yes, but I can imagine doing this if I want to be sure I'm getting optimal assembly versus trusting step_by will be optimized. Or say I have some enum where I'd like to be able to do MyEnum::VariantA(x)..MyEnum::VariantA(y) or MyEnum::VariantB(x)..MyEnum::VariantB(y), but not a range from VariantA to VariantB. Things like that.

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency.

Original

Consider a newtype pub struct StepByTwos(pub u32), which will only ever step by 2 over a given range (or more broadly, any type representing a union of two disjoint ordered groups). We also implement PartialOrd for it, where two values are comparable iff both values are even or both are odd (and otherwise using normal integer comparison). This can be made to have a total order, sure, but in its existing state it is not, while still being able to impl Step in a way compatible with all the invariants. Is the example contrived? Yes, but I can imagine doing this if I want to be sure I'm getting optimal assembly versus trusting step_by will be optimized. Or say I have some enum where I'd like to be able to do MyEnum::VariantA(x)..MyEnum::VariantA(y) or MyEnum::VariantB(x)..MyEnum::VariantB(y), but not a range from VariantA to VariantB. Things like that.

That still doesn't make sense to me. If you want it to be more flexible, then there shouldn't be a PartialOrd<Self> supertrait at all. Then your StepByTwos type could still implement this as well as even more contrived types that don't implement PartialOrd<Self>. To me it should be maximally flexible and not have a supertrait, or force that the successor function agree with the total order. If one wants to implement an even more restrictive trait like Step, then it makes no sense to not implement a less restrictive trait like Ord.

To me this is like having Group, Ring: Group, and Field: Group traits. That is silly. All fields are rings, so one should require Ring be a supertrait of Field and not Group.

Or to match your contrived type with an even more contrived type, imagine I have a type whose canonical order defined on it via Ord is not well-ordered. By having PartialOrd<Self> be a supertrait, this type can't implement Step; however per the axiom of well-ordering in Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this type has a well-order. So now a type like Real that models the field of real numbers with the canonical total order <= cannot implement this trait.

The point being it should either require Ord since well-ordering implies total ordering or should be more flexible and not require PartialOrd<Self>.

[khoover]

You don't want to be so flexible as to say there's no ordering at all, though. Take Range, which is why we even care about the Step trait. If we don't have PartialOrd, then we have to rely on steps_between to denote whether the start is "before" end, via it returning None. And what's in the invariants for steps_between? A reliance on a partial order for the type. I don't think there's any way to write a useful set of invariants for step_between without relying on a partial order at some point. So even if the Step impl doesn't use anything from PartialOrd, the invariants for the impl only make sense if you have a PartialOrd for the type.

As for your example, if you have Real, and use <= as your total order, plus the willed-into-existence well-order's min function, then as soon as you write some Rust impls for Real::<= and Real::min_in_interval(start: Clopen<Real>, end: Clopen<Real>) I can write you a PartialOrd and Step impl. Neither are going to look particularly complex.

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency; although the claim that the trait would be more generally useful without the PartialOrd<Self> supertrait remains true.

Original

Why not? A successor function need not rely on an existing ordering implementation to work. If one insists on coupling the order that is implied by the successor function to be the same as any existing order via Ord—which is not always desirable—then the documentation can easily say "if a type implements Ord, blah blah blah". This is no different than how Hash doesn't have Eq as a supertrait. While I personally would prefer a marker trait like HashEq: Eq + Hash that mandates two equivalent instances per == hash to the same value, there isn't; instead the library team opted to simply mention those invariants in the documentation. A similar thing can happen here.

Or again, one should require Ord be a supertrait since the order that is defined by the successor function is total, and the decision is already made to conflate the well-ordering with the partial order.

[schuelermine]

I feel that an implementation might want to express that an ordering between two “uncomparable” things has limited meaning even if it can mathematically be constructed from the successor relation.

I also think there are two “styles” of hierarchy at conflict here. Mathematically we want to say that Step: Ord because constructing Ord from Step is trivial, but programmatically we can a) that constructing an Ord implementation (i.e. a consistent PartialOrd one) is not necessarily trivial from a raw code writing labor view, and b) see that a consumer of Step might not rely on the implication that it is Ord, and might be fine with a technically non-canonical PartialOrd implementation. This is distinct from the case of Field: Ring because in that case not having that bound would require duplicating functionality—the interface of Field includes the interface of Ring explicitly, not implicitly, and consumers of Field usually rely on the interface of Ring.

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency; although the claim that the trait would be more generally useful without the PartialOrd<Self> supertrait remains true.

Original

If one implemented PartialOrd<Self> and Step already, then implementing Ord is trivial. So again, I don't see how requiring PartialOrd<Self> makes sense and not Ord.

The first question is whether or not one wants Step to be in agreement with Ord if Ord exists, and that is not always yes. Then even if one wants there to be agreement, one has to ask the question if it should be forced to be implemented. Again, as we see with Hash and Eq, that is not necessarily "yes" either. However even if the answer to that is yes, then that doesn't concern PartialOrd<Self>. I don't see how one can argue that it is not trivial to implement Ord but it is trivial to implement PartialOrd<Self>.

Addendum

A consumer of Step can very easily not require the enumeration of elements to be in agreement with Ord/PartialOrd<Self> or that Ord/PartialOrd<Self> even be implemented which is an argument that Ord/PartialOrd<Self> not be a supertrait. This also reduces how much code a developer writes since one can implement Step without implementing Ord/PartialOrd<Self>.

Even if one wants to require the enumeration to be in agreement, you can offer an "out" by not making Ord/PartialOrd<Self> a supertrait but simply specify in the documentation that "if a type also implements Ord/PartialOrd<Self>, the order agrees" which is exactly what is done with Hash and Eq.

If you do want to force developers to write more code, however, by forcing a supertrait as well as reduce the generality of Step; then you would make Ord (not PartialOrd<Self>) be the supertrait.

[schuelermine]

It seems to me that it is possible to have a PartialOrd implementation that is valid but cannot be an Ord implementation for a type that could have an implementation that would be valid Ord. In other words, we can't show that the PartialOrd impl is valid Ord, but that a valid Ord impl exists. Correct me if I'm wrong.

[schuelermine]

Although I agree that just leaving out any *Ord bound is an option

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency.

Original

I haven't constructed a formal FOL proof yet, but I claim the following is valid:

#![feature(step_trait)]
impl<T: core::iter::Step> Ord for T {
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency; although the claim that the trait would be more generally useful without the PartialOrd<Self> supertrait remains true.

Original

Although I agree that just leaving out any *Ord bound is an option

Exactly. I am not necessarily arguing for Ord as a supertrait. I am arguing that there are only two sensible options: no Ord/PartialOrd<Self> supertrait or Ord.

However that does require proof that for any type T: Step, Ord is trivially implemented based on how Step is documented.

[khoover]

I haven't constructed a formal FOL proof yet, but I claim the following is valid:

#![feature(step_trait)]
impl<T: core::iter::Step> Ord for T {
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

I can tell you, for a fact, this will panic. E.g.

#[derive(Clone, Copy, PartialEq, Eq)]
enum EvenOrOdd {
  Even(u8),
  Odd(u8)
}

impl EvenOrOdd {
  fn map(self, f: impl FnOnce(u8) -> Option<u8>) -> Option<Self> {
    match self {
      Even(x) => f(x).map(Even),
      Odd(x) => f(x).map(Odd)
    }
  }
}

fn matching_evenness(x: EvenOrOdd, y: EvenOrOdd) -> Option<(u8, u8)> {
  match (x, y) {
    (Even(l), Even(r)) => Some((l, r)),
    (Odd(l), Odd(r)) => Some((l, r)),
      _ => None
}

impl PartialOrd<Self> for EvenOrOdd {
  fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
    matching_evenness(*self, *rhs).and_then(|(x, y)| x.partial_cmp(&y))
  }
}

impl Step for EvenOrOdd {
  fn steps_between(start: &Self, other: &Self) -> Option<usize> {
    matching_evenness(*start, *other).and_then(|(x, y)| y.checked_sub(x).map(|diff| (diff / 2) as usize))
  }

  fn forward_checked(start: Self, count: usize) -> Option<Self> {
    start.map(|x| {
      u8::try_from(count * 2).ok()
        .and_then(|y| x.checked_add(y))
    })
  }

  fn backward_checked(start: Self, count: usize) -> Option<Self> {
    start.map(|x| {
      u8::try_from(count * 2).ok()
        .and_then(|y| x.checked_sub(y))
    })
  }
}

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency.

Original

It's a lot nicer if you give code that can compile. Additionally you haven't proven you conform to the requirements mentioned by PartialOrd nor Step, but I will check to see that is the case.

[khoover]

Sorry, writing on my phone so I left the uses out. Also, there's an implicit assumption that Even(x) is always even, Odd(x) is always odd, similar to how bounded-integer newtypes work.

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency.

Original

You also have misplaced } instances, but it is not hard to fix. I assumed that Even required the u8 to be even. To actually prove your code is a counterexample to my code though, it would be nice to have functions that prove the invariants of PartialOrd and Step are met; and finally a function that shows my implementation causes a panic. I am working on doing that now.

Here is code that compiles that needs to have partial_cmp_proof, step_proof, and counterexample written that show EvenOrOdd conforms to the documentation of PartialOrd<EvenOrOdd>, Step, and show EvenOrOdd::ord_impl panics respectively.

#![feature(step_trait)]
use core::cmp::Ordering;
use core::iter::Step;
fn main() {
    partial_cmp_proof();
    step_proof();
    counterexample();
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum EvenOrOdd {
    Even(u8),
    Odd(u8),
}
use EvenOrOdd::{Even, Odd};
impl EvenOrOdd {
    fn map(self, f: impl FnOnce(u8) -> Option<u8>) -> Option<Self> {
        match self {
            Even(x) => f(x).map(Even),
            Odd(x) => f(x).map(Odd),
        }
    }
    fn ord_impl(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}
fn matching_evenness(x: EvenOrOdd, y: EvenOrOdd) -> Option<(u8, u8)> {
    match (x, y) {
        (Even(l), Even(r)) => Some((l, r)),
        (Odd(l), Odd(r)) => Some((l, r)),
        _ => None,
    }
}
impl PartialOrd<Self> for EvenOrOdd {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        matching_evenness(*self, *rhs).and_then(|(x, y)| x.partial_cmp(&y))
    }
}
impl Step for EvenOrOdd {
    fn steps_between(start: &Self, other: &Self) -> Option<usize> {
        matching_evenness(*start, *other)
            .and_then(|(x, y)| y.checked_sub(x).map(|diff| (diff / 2) as usize))
    }

    fn forward_checked(start: Self, count: usize) -> Option<Self> {
        start.map(|x| u8::try_from(count * 2).ok().and_then(|y| x.checked_add(y)))
    }

    fn backward_checked(start: Self, count: usize) -> Option<Self> {
        start.map(|x| u8::try_from(count * 2).ok().and_then(|y| x.checked_sub(y)))
    }
}
fn partial_cmp_proof() {
    // Code to be written.
}
fn step_proof() {
    // Code to be written.
}
fn counterexample() {
    // Code to be written.
}

[khoover]

Well, the panic is easy, EvenOrOdd::Even(0).ord_impl(&EvenOrOdd::Odd(1)).

As for the invariants

• For PartialOrd, we don't override the provided methods, so 2-5 are done. 6 is done via the derive. Finally, for 1, two instances are equal only if they have matching evenness, in which case the PartialOrd impl will compare the internal u8s and return Some(Equal).
• For Step, steps_between requires matching evenness, and when that happens we just use how many 2-steps are between the two numbers using checked arithmetic. In particular, we return an integer only if the evenness matches and the checked sub is Some. forward/backward_checked do count 2-steps in the appropriate direction using checked math, so the invariants there are straightforward.

[zacknewman]

Edit

Please ignore below. My brain was clearly not working properly. I only keep this message in the interest of transparency.

Original

You'll have to forgive my ignorance, but I don't find it obvious that Step is correct. I can look past the panic and PartialOrd implementation though.

For example Step::steps_between requires:

• steps_between(&a, &b) == Some(n) if and only if Step::forward_checked(&a, n) == Some(b)
• steps_between(&a, &b) == Some(n) if and only if Step::backward_checked(&b, 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 when it would require more than usize::MAX steps to get to b
• steps_between(&a, &b) == None if a > b

Maybe I just need to eat, and it'll be obvious to me.

[zacknewman]

Jesus, I am an idiot and am thinking way too hard about this. I clearly missed the forest for the trees here. Your example is extremely obvious and highlights a massive oversight on my part about what Step guaranteed. I retract my claim that it doesn't make sense to require PartialOrd<Self> as a supertrait.

Sorry @khoover for wasting your time and likely frustrating you with my stupidity.

[khoover]

Yep, any implementation is going to induce a partial order via

fn partial_cmp<T: Step>(this: &T, other: &T) -> Option<Ordering> {
  T::steps_between(this, other)
    .map(|n| if n == 0 { Equal } else { Less })
    .or_else(|| T::steps_between(other, self).and(Some(Greater)))
    // That and works because Step guarantees T::steps_between(other, this) == Some(0)
    // iff T::steps_between(this, other) == Some(0), which was already covered in the above map.
}

EDIT: and the important thing is that you can't do any better than a partial order. Step only guarantees a != b => steps_between(&a, &b).is_some() NAND steps_between(&b, &a).is_some(), not XOR like you'd need.

[zacknewman]

Indeed; although that still doesn't "prove" that PartialOrd<Self> need be a supertrait. Step would be more generally useful without it as a supertrait. One may simply want the ability to enumerate something without implementing a canonical partial order or even implement a canonical partial order that doesn't agree with the order that is induced from Step.

The documentation could be made a little clearer as well. For example, "For any a, b, and n" should be re-worded as "For any a and b, there exists n" (i.e., there should be an existential qualifier before "n" not a universal one). Perhaps that is pedantic, but the documentation is trying to be rather precise/mathematical; so "pedantry" is pretty much required.

[khoover]

No, no, it should be for every n too. It's expressing that steps_between(&a, &b).is_some() iff Step::forward_checked(&a, steps_between(&a, &b).unwrap()) == Some(b), and the equivalent for backward_checked. The third and fourth criteria (really, they're the same, just contrapositives) could be relaxed to a == b OR (steps_between(&a, &b).is_some() NAND steps_between(&b, &a).is_some()), but that's just saying "Option::is_some . steps_between is a non-transitive weak partial order, in combination with the forward/backward_checked invariants" (can't be transitive because of the usize::MAX bit).

Or, to make it more explicit, forall a != b.[(exists n.forward_checked(&a, n) == Some(b)) NAND (exists n.forward_checked(&b, n) == Some(a))], and the same for backward_checked. Then you only need the first two constraints for steps_between and you're done.

[zacknewman]

I just need to shut up, lol. The original comment before I edited it also stated that "steps_between(&a, &b) == Some(n) only if a <= b" was wrong because I embarrassingly misinterpreted it as "if a <= b, then steps_between(&a, &b) == Some(n)". I realized my foolishness and removed that; however it was that misinterpretation that led me to claim n should be existentially modified.

Thanks again for holding my hand.

[TurtlePU]

I would like to note an interesting detail about Step implementation for rings $\mathbb{Z}_n$ of residues modulo $n$: as <= has to be antisymmetric, ranges like (x .. (x - Zn::from(1))) would most likely have to be empty, which goes against an intuition one might have about ranges like "increment left border until you reach the right border".

[khoover]

I would like to note an interesting detail about Step implementation for rings Zn of residues modulo n: as <= has to be antisymmetric, ranges like (x .. (x - Zn::from(1))) would most likely have to be empty, which goes against an intuition one might have about ranges like "increment left border until you reach the right border".

I think the more likely approach is to say that any different elements of your modular ring are incomparable, i.e. a.partial_cmp(&b).is_some() <=> a == b. Then you can wrap to your heart's content.^1

^1: Well, by the trait's contract, you have to output None from a.forward/backward_checked if you'd pass a, since the trait mandates a 1:1 map from the n these functions return Some for and the n returned by steps_between.

[NeverGivinUp]

Please mark the forward and backward methods #[must_use]

[Sunshine40]

There're mistakes in forward_checked / backward_checked's doc:

• In the Invariants section under forward_checked, this line:

  Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == try { Step::forward_checked(a, n.checked_add(m)) }

  missed a ? after n.checked_add(m) — its counterpart under backward_checked has that.

• Even with the ?, it's still inconsistent with what's implied by the Invariants section under steps_between which mentioned:

  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

  For example, Step::forward_checked(0u128, usize::MAX).and_then(|x| Step::forward_checked(x, usize::MAX)) should return a Some, but try { Step::forward_checked(0u128, usize::MAX.checked_add(usize::MAX)?) } returns a None because usize::MAX.checked_add(usize::MAX)
  returns a None.

So the line should actually be:

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)

The same goes for its counterpart under backward_checked.