Tracking issue for step_trait stabilization

View all comments

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
Should this live in core::iter or core::range?

(and probably more)

Rollup merge of rust-lang#42169 - scottmcm:new-step-trait-issue, r=al…

Some progress on this in #42534

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

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

Auto merge of #43077 - SimonSapin:ranges, r=alexcrichton

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

Rollup merge of rust-lang#154825 - Lars-Schumann:non-zero-const-step,…

Unrolled build for #154825

Rollup merge of #154825 - Lars-Schumann:non-zero-const-step, r=jhpratt

Rollup merge of rust-lang#156629 - tgross35:range-module-stabilizatio…

Unrolled build for #156629

Auto merge of #153821 - Lars-Schumann:const-step, r=Mark-Simulacrum

Do we really want to allow forward to saturate? I think that is very confusing and semantically wrong. There is no sense in which 255 is the successor of 255 (on NonZero<u8>). There is a sense in which 0 is the successor of 255 (on u8), so wrapping makes sense -- but saturating does not.

If 255 has a successor on NonZero<u8>, it would be 1 (that'd be my interpretation of "wrapping" for this type). That would be strictly better than saturating, IMO. But really I think forward should just always panic for such cases where there's no "good" successor: we should allow panic and wrapping, but nothing else. Asking for the successor of 255 on NonZero<u8> is clearly buggy code (it panics in debug builds after all). Falling back to wrapping arithmetic is an accepted trade-off when the performance cost of detecting the bug is too high, but falling back to pretty much nonsensical behavior (such as saturation) is so much worse that I don't think this is a good trade-off.

Do we really want to allow forward to saturate? I think that is very confusing and semantically wrong. There is no sense in which 255 is the successor of 255 (on NonZero<u8>). There is a sense in which 0 is the successor of 255 (on u8), so wrapping makes sense -- but saturating does not.
[...]

I was worried about the performance impact of this, but at least on x86, wrapping behavior takes the same number of instructions as saturating behavior (and both are branchless):

#[unsafe(no_mangle)]
fn sat_add_nonzero(x: u32, y: u32) -> u32 {
    // add     edi, esi
    // mov     eax, -1
    // cmovae  eax, edi
    // ret
    x.saturating_add(y)
}

#[unsafe(no_mangle)]
fn wrapping_add_nonzero(x: u32, y: u32) -> u32 {
    // mov     eax, edi
    // add     eax, esi
    // adc     eax, 0
    // ret
    let (res, ovfl) = x.overflowing_add(y);
    // an if branch here generates the same code
    core::hint::select_unpredictable(ovfl, res.wrapping_add(1), res)
}

See on godbolt: https://godbolt.org/z/qbxdfoGWG

I think it's overly strict on the allowed behaviours when given an invalid increment. To me, it's a safe forward_unchecked more than an unwrapped forward_checked, where you replace "UB" in the definition of forward_unchecked with "panics or returns an arbitrary value."

In defense of saturation, though, for NonZero<u8> the addc works if the increment is at most 256. But it can be any usize, what happens when it wraps two or three times? Rather than figuring out mod 255, if forward always saturates it doesn't matter how many times your increment would wrap, the answer is always 255. This holds for other bounded integer types too, e.g. a GridIndex(u8) that validates the input number is in [0, 99]; rather than calculate mod 100, can just saturate at 99 with a sub and cmov.

"returns an arbitrary value" is a great way to break programs. That feels like a gross violation of the usual principles of API design that the standard library follows.

Lucky enough, the spec is nowhere near as permissive as that. But it allows "saturation", and that's already going too far IMO.

Navigation Menu

Repository navigation

Tracking issue for `step_trait` stabilization #42168

72 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Tracking issue for step_trait stabilization #42168

Description

Activity

scottmcm commented on Jun 9, 2017

SimonSapin commented on Jul 5, 2017

SimonSapin commented on Jul 6, 2017

SimonSapin commented on Jul 8, 2017

72 remaining items

RalfJung commented on Sep 1, 2026

Techcable commented on Sep 5, 2026

khoover commented on Sep 5, 2026

RalfJung commented on Sep 6, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Tracking issue for `step_trait` stabilization #42168