Tracking issue for `step_trait` stabilization

Opened by scottmcm at 2024-07-28 00:51:23

Split off from https://github.com/rust-lang/rust/issues/27741 because the stabilization path for step_by has moved to being on iterators (https://github.com/rust-lang/rust/pull/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: https://github.com/rust-lang/rfcs/pull/1980#issuecomment-301348126)
[ ] 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 https://github.com/rust-lang/rust/issues/48117

(and probably more)

Some progress on this in https://github.com/rust-lang/rust/pull/42534
scottmcm at 2017-06-09 07:40:00
PR #43077 does items 1 <s>and 3</s> in the original message of this issue.
Simon Sapin at 2017-07-05 23:27:25

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}.

Simon Sapin at 2017-07-06 09:46:14

I’ve tweaked this design some more and opened https://github.com/rust-lang/rust/pull/43127. I believe that PR fixes every issue I know of around the Step trait.
Simon Sapin at 2017-07-08 20:11:24
I’ve closed that PR since it needs more work that I’m not planning to do soon: https://github.com/rust-lang/rust/pull/43127#issuecomment-318518145. Hopefully someone else can take over.
Simon Sapin at 2017-07-27 23:53:58
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...)
Felix S Klock II at 2018-07-25 10:28:46
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.
Nathan West at 2019-05-06 09:03:12
Nearly two years on from the most recent comment, what's the status of this? It looks like the only outstanding issue (per the original post) is the removal of steps_between. The API seems quite clean and thorough enough otherwise. Personally, I don't see the need for the removal of steps_between, either.
Jacob Pratt at 2021-03-23 05:35:17
The API seems quite clean and thorough enough otherwise.

Really? To me this trait looks like nothing more than an internal implementation detail of std::ops::Range iteration. I would point out that notably, if this were stabilized as is, then it would never be possible to write a Range<MyCustomIdx> that can be iterated over without the use of unsafe.

It seems to me that this is definitely a big enough thing to deserve going through the RFC process, and I don't see a link to any RFC from here.
Michael Lamparski at 2021-03-31 01:54:46
@ExpHP A user iterating over some type would not need unsafe, if that's what you're saying. unsafe would only be required to implement the trait, and even then only because of the number of invariants that need to be upheld — there doesn't actually need to be anything unsafe being used.

Edit: After quickly looking at things again, I think it would make sense to decouple the TrustedLen impls from the Step trait. I'll look into this further and submit a PR if desired.
Jacob Pratt at 2021-03-31 02:05:52
I was, of course, referring to the fact that unsafe is required to implement the trait. I do not think this is an unrealistic thing to want to be able to do in safe code; in fact, I would rather think there should be a fair overlap between the kind of projects that would want to use a custom-typed range, and the kind of projects that would #![deny(unsafe)]; but this is conjecture. (all I know for certain is that I myself wanted to do this today, and that my current project has avoided all unsafe code)

Though one can't be certain without actually trying to implement it, I'd imagine that it could perhaps be possible to split this into a Step and a TrustedStep trait. This would be a nicer outcome, but honestly even then I'd still be surprised to see anything in this area get stabilized without going through the RFC process...

As I see it, Step is the dust that was swept under the rug when it was determined that it was possible to stabilize step_by without having to stabilize custom ranges.
Michael Lamparski at 2021-03-31 02:48:00
I wasn't quite sure which you were referring to.

There's a TrustedLen trait, which is already separate. It just has a blanket impl for all Range<T> where T: Step. I've asked on Zulip to see if there is any technical reason this blanket impl is necessary or if it could be switched to a number of specific impls (leaving the behavior of stdlib the same).

Ultimately the decision to require a formal RFC is up to the libs team — not e everything needs one. Imo it's not necessary, but I have no say.
Jacob Pratt at 2021-03-31 02:53:48
The Step trait has been made safe to implement. A new TrustedStep trait has been introduced to indicate that the Step implementation upholds all stated invariants, allowing performance optimizations (and adding the TrustedLen impl). These changes will be present in the next nightly.
Jacob Pratt at 2021-05-30 06:57:06

Is there any chance of a derive macro for Step for C-like enums (probably requiring derived Ord) being added? This would allow for iterating over a range of variants of an enum with these derives. I recently wanted this for an enum with variants representing numbers from 0 to 15 (in my particular case as identifiers for CHIP-8 registers). To me it seems this is generally useful for enums representing a limited range of consecutive numbers.

<details> <summary> My example (with code as I would want to write it) with a possible implementation of Step for my case: </summary>

/// Variable register of the CHIP-8 processor
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Step, TryFromPrimitive)]
#[repr(u8)]
pub enum VarRegister {
    /// Used as the offset in [`Instruction::JumpOffset`].
    V0,
    V1,
    V2,
    V3,
    V4,
    V5,
    V6,
    V7,
    V8,
    V9,
    VA,
    VB,
    VC,
    VD,
    VE,
    /// Used for carry/borrow flags and set to the shifted-out bit after bit shifts.
    /// See [`Instruction::AddAssign`], [`Instruction::SubAssign`],
    /// [`Instruction::RevSubAssign`], [`Instruction::ShrAssign`]
    /// and [`Instruction::ShlAssign`].
    VF,
}
// -- snip --
        match instruction {
            // -- snip --
            Instruction::StoreRegisterValues { last_register } => {
                for register in VarRegister::V0..=last_register {
                    self.memory[self.address_register as usize + register as u8 as usize] =
                        self.get_register(register);
                }
            }
            Instruction::LoadRegisterValues { last_register } => {
                for register in VarRegister::V0..=last_register {
                    self.set_register(
                        register,
                        self.memory[self.address_register as usize + register as u8 as usize],
                    );
                }
            }
            // -- snip --
        }
// -- snip --

How I implemented Step for my case:

impl Step for VarRegister {
    fn steps_between(start: &Self, end: &Self) -> Option<usize> {
        (*end as u8 as usize).checked_sub(*start as u8 as usize)
    }

    fn forward_checked(start: Self, count: usize) -> Option<Self> {
        u8::try_from(count)
            .ok()
            .and_then(|count| (start as u8).checked_add(count))
            .and_then(|i| Self::try_from(i).ok())
    }

    fn backward_checked(start: Self, count: usize) -> Option<Self> {
        u8::try_from(count)
            .ok()
            .and_then(|count| (start as u8).checked_sub(count))
            .and_then(|i| Self::try_from(i).ok())
    }
}

Here I used num_enum's TryFromPrimitive derive, but this could also be solved without that in the derive macro for Step, or by requiring a separate derive macro like TryFromPrimitive.

</details>

(I'm not quite sure this is the right place to suggest this, do tell if it isn't. I can also imagine this being out of scope for now and that this should rather be in a crate like num_enum, but nonetheless I wanted to hear some opinions.)

Hans Christian Schmitz at 2021-06-06 04:13:56

It seems like it would be a good idea for a forward_with_endpoint & backward_with_endpoint that could be used for fully bounded ranges that would pass in the endpoint along with the startpoint, That way more complex areas can be represented, such as Vector 2s.
```
for cord in Point(0, 0)..Point(10, 2) {
    ...
}
```
For anything requiring this wouldn't be any intrinsic order to the values in between, but I think that Range iteration is still a meaningful full notion that could be useful.

(sorry if I didn't format this well, first time contributing)
Felix Moses at 2021-07-02 22:59:56
That's an interesting thought. I don't think it would be possible to backwards compatibly add support for this later, so it might be worth discussing now. So I guess the idea is having methods like
```
fn forward_with_endpoints(current: Self, count: usize, start: &Bound<Self>, end: &Bound<Self>) -> Self;
```
making it possible to implement the above loop?

I see numerous disadvantages:
- Step already has 6 methods. This could potentially bring the number up to 12. (or perhaps they would replace the six)
- The new methods would be required to be implemented, even though many types won't care about the endpoints. (most notably, nothing in the standard library impls would care)
- It could interfere with prior, repeated and heroic efforts to optimize performance of ranges in the standard library (which AFAICT are part of why this trait has been unstable for so long)
- Using the Step trait to achieve this offers the library no control over which range types are supported. Does Point(0, 0).. make sense?
To me, these disadvantages seem to outweigh the benefits; perhaps such a library should consider providing this functionality as Point(0..10, 0..2) (or perhaps e.g. Grid(0..10, 0..2)) instead.
Michael Lamparski at 2021-07-02 23:45:15
Actually, I just realized. Beyond even all of that: It's impossible!

The fields of Range are public. When Iterator::next is called, it updates the start field in-place. The original lower bound of the range is not recorded or saved anywhere.
Michael Lamparski at 2021-07-02 23:57:50
It's annoying to require nightly to be able to do:
```
impl<Idx: Step> Foo for Range<Idx>
```
Stargateur at 2021-11-11 13:26:01
I wouldn't mind seeing a move towards stabilization here. It's up to T-libs-api. cc @m-ou-se as team leader: thoughts?
Jacob Pratt at 2021-11-12 04:52:15
@Stargateur One trick that can sometimes help is to use impl<Idx> Foo for Range<Idx> where Self: Iterator.

A thought here: if people aren't sure that the trait have exactly the right set of methods (I'm not confident we won't want more, but other may feel otherwise) then maybe this could take the SliceIndex approach of "the trait is stable so you can name it, but none of the methods are so you can't call them or implement it".
scottmcm at 2021-11-12 05:18:27
@scottmcm I want to use Range as Bounds, use it as min and max, so the user do 2..3 I do two loop 0..2 and 2..3, one for the min behavior, one for the max behavior, so I don't use self as Iterator directly. That why unless I miss something I need Step to be able to create new Range iterator. This allow my user to express the bounds of what my fonction should run in a user friendly way. min: Some(2), max: Some(3) for 2..3 or min: Some(4), max: None for 4.. etc.

Thus I know my case is very specific and most user can use your tips. I simply just implement only for Range<usize> that what all my user should use anyway so that not a big problem for me.
Stargateur at 2021-11-12 13:47:26
Adding more methods shouldn't be an issue so long as there's a Default implementation. This should be doable I think.
Jacob Pratt at 2021-11-13 01:25:49
Trying to use somebody else's code from 2017 which has been successfully compiled by the author, I get a bunch of errors like
```
method `add_usize` is not a member of trait `Step`
method `add_one` is not a member of trait `Step`
no method named `add_one` found for type `u8` in the current scope
```
and many others.

Is there a way I can repair this?

Update by trial-and-error I managed to make it work with the 2019-07-03 nightly toolchain (tried several earlier and later ones before that).

How do I find out from the files which toolchain to use?
jibnew at 2022-08-08 13:30:15
Would it be possible to add an implementation of Step for *const T and *mut T safely (perhaps via wrapping_offset)? That would mean that slice::get_{mut_,}ptr_range would then be returning an iterator over the slice’s element pointers, which can make certain unsafe access patterns simpler to write.

cf. This IRLO topic, which contains an example of such code.
e2-71828 at 2022-10-07 06:16:37
@e2-71828 See https://github.com/rust-lang/rust/pull/91000#issuecomment-982001655 for my thoughts on why a Step for pointers is probably not the right API. And in addition to the unsafe factors, unaligned pointers are safely representable, so it's not incredibly obvious to me whether *const i32 should step by wrapping_byte_add(1) or wrapping_add(1), and questions like that discourage trait implementations, like how String isn't IntoIterator. (char skips some bit patterns but that's because they're invalid in terms of validity invariant. It's not that they're just discouraged.)

If you're interested in getting something for iterating over pointers, I suggest reviving #91390, which IMHO is just about ready to go.
scottmcm at 2022-10-07 18:06:42
Is there a specific reason that Step as it currently exists does not have methods but only functions (that don’t take self)?
Anselm Schüler at 2023-04-16 18:45:13
Is there a specific reason that Step as it currently exists does not have methods but only functions (that don’t take self)?

Is there a specific reason that Step as it currently exists does not have methods but only functions (that don’t take self)?

Could you please provide examples of that? I'm curious to know more about what exactly you're thinking about 😮
Ivan Borgia Dardi at 2023-05-24 15:57:39
@ivandardi they don't take self, they take Self. That means they can't be used with the . operator.
Anselm Schüler at 2023-05-28 10:09:56
Edit

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

Original I am a little confused about two things regarding this trait:
1. 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. Is it that we want to allow for elements to not be equivalent to themselves (i.e., allow types that implement a total order per the <= and >= operators to not have to implement == to be reflexive (e.g., f64 is not an example since <= is not reflexive nor strongly connected, but some sort of weird type that has elements like f64::NAN which are not equivalent to themselves but are strictly less than or strictly greater than another element))? Put differently, is it due to the lack of a trait that has the requirements of Ord without the Eq supertrait requirement (i.e., a true total order trait that doesn't conflate equivalence) that PartialOrd<Self> is used?
2. Is it actually OK for elements to be successors of themselves even outside of overflow? A type is allowed to implement forward by cloneing start for example?
Clarification on the first point

It seems bizarre that we want to force additional structure (i.e., PartialOrd<Self>) on types that implement Step but don't want to go all the way and force Ord. It's more consistent to either allow types to implement Step without implementing PartialOrd<Self> or to force types to implement Ord. In the former situation, the description for forward need be only amended slightly to state that if a type implements PartialOrd<Self> it must also implement Ord and successors must be >=. Forcing types to implement PartialOrd<Self> seems likes a bizarre middle ground.
philomathic_life at 2023-08-25 15:08:11
As I noticed, the trait requires Sized
```
pub trait Step: Clone + PartialOrd<Self> + Sized {/***/}
```
What is the need for this, if Clone already implies Sized?
```
pub trait Clone: Sized {/***/}
```
Nano at 2023-08-27 14:49:36
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.
Ken Hoover at 2023-09-06 17:59:50
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>.
philomathic_life at 2023-09-06 20:31:57
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.
Ken Hoover at 2023-09-06 20:46:25
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.
philomathic_life at 2023-09-06 21:03:10
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.
Anselm Schüler at 2023-09-06 21:37:42
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.
philomathic_life at 2023-09-06 21:47:58
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.
Anselm Schüler at 2023-09-06 22:17:00
Although I agree that just leaving out any *Ord bound is an option
Anselm Schüler at 2023-09-06 22:25:51
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()
    }
}
```
philomathic_life at 2023-09-06 22:28:13
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.
philomathic_life at 2023-09-06 22:30:47

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))
    })
  }
}

Ken Hoover at 2023-09-06 22:57:02

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.
philomathic_life at 2023-09-06 23:13:54
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.
Ken Hoover at 2023-09-06 23:22:40

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.
}

philomathic_life at 2023-09-06 23:25:27

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.
Ken Hoover at 2023-09-06 23:33:58
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.
philomathic_life at 2023-09-06 23:48:34
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.
philomathic_life at 2023-09-07 00:45:42

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.

Ken Hoover at 2023-09-07 01:14:59

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.
philomathic_life at 2023-09-07 16:06:33
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.
Ken Hoover at 2023-09-07 17:34:34
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.
philomathic_life at 2023-09-07 20:13:39
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".
TurtlePU at 2024-02-13 22:28:24
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.
Ken Hoover at 2024-07-03 00:41:46
Please mark the forward and backward methods #[must_use]
Navid Vahdat at 2024-07-22 08:57:48
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.
Sunshine40 at 2024-07-28 00:51:23