Tracking issue for `step_by` stabilization

[aturon]

Update (@SimonSapin): this is now the tracking issue for an iterator adaptor based on Iterator::nth:

pub trait Iterator {
    fn step_by(self, step: usize) -> StepBy<Self>
}

The Step trait used for making ranges iterators is now tracked at #42168.

Original issue:

---

The step_by method makes it possible to step through ranges with arbitrary-sized steps. There are several issues that need to be addressed before we can stabilize it:

• The design/stabiliztion of the Step trait, which is currently a bit of a mess
• The behavior on negative steps (see this thread)
• Likely the design/stabilization of Zero/One, tracked here

[aturon]

Nominating for P-High.

[alexcrichton]

triage: P-high

[huonw]

cc #23588

[sfackler]

We should probably start moving on this in the next cycle or drop the P-high.

[aturon]

Would definitely like some help getting this over the finish line. I'm happy to mentor!

[alexcrichton]

The library subteam decided to not move this to FCP this cycle. The API is pretty likely to need revision in one form or another and that should be taken care of before a FCP happens. I believe discussion is still going on in the internals post though!

Also moving to P-medium

[dschatzberg]

It seems odd to me that the by type is Self. It seems similar to the Add trait where I can choose the RHS and the sum type separately. It seems like the type of the steps should similarly be potentially different from the elements themselves (steps are effectively differences).

[shssoichiro]

Where do we stand on this at the moment? This is a feature I'd very much like to use in stable, and am willing to provide help to get this finalized (with some mentoring).

[ranma42]

Based on the documentation, I would expect (0u8..).step_by(1).count() to be 256, but currently it diverges. Is this a bug in the documentation or in the implementation?

[SimonSapin]

Why do you expect that? Overflowing the range of an integer type is an error (it panics in debug mode), it’s not the expected end of a RangeFrom iterator (which doesn’t have an end).

[ranma42]

@SimonSapin The example for RangeFrom::step_by is

for i in (0u8..).step_by(2) {
    println!("{}", i);
}

I think that this example is misleading: its explanation says "This prints all even u8 values.", but instead it overflows on panic in debug and loops forever in release.

[SimonSapin]

Indeed, that example is wrong. How does this look? #31172

[comex]

Ditto @dschatzberg's comment. Imagine something like stepping through a range of two Instants by a Duration.

[nodakai]

A sequence of floats like 0.1, 0.2, ..., 0.5 is so common in numerical codes that Matlab has a built-in operator for it:

• http://www.mathworks.com/help/matlab/ref/colon.html

But Step is only implemented for integer types, perhaps in the fear of a numerical error around the endpoint.

• https://doc.rust-lang.org/nightly/std/iter/trait.Step.html

I understand your rigorous approach but it would be handy to have step_by() for floats (perhaps as an optional trait?)

[nodakai]

Also, I think we should consider inclusion of Itertools::step(usize) into the stdlib as well (thanks u/levansfg on Reddit for letting me know)

• http://bluss.github.io/rust-itertools/doc/itertools/trait.Itertools.html#method.step

which, to my eyes, is more generic (applicable to all iterators)

[yigal100]

IMHO, step_by should be a general abstraction for all iterators as mentioned by @nodakai and the current implementation that uses addition must be at most a specialization for efficiency sake for integral types (now that Rust has specialization implemented).

[dhardy]

yigal100's approach seems sensible, in which case step_by should take a usize regardless of the iterator type and just call next a configurable number of times (>= 0).

Another option would be to drop step_by and instead allow a Range to be multiplied by something; e.g. (1..3) * -2 would return -2, -4. In this case it would be nice to be able to write (0..10) * 0.1, however, where would the (int->float) conversions come in? Also, it might be nice to be able to use other operators: (0..101) / 100.0 + 1.0 for 101 values from 1 to 2.

Neither of these options requires a One trait really; it depends how Rust converts from the a..b syntax to an iterator (if this is restricted to integer types, as seems to be the case, then 1 as TYPE is sufficient).

The questions which I think need answering are:

1 What are the main use-cases?

In my mind these are:

a. producing a sequential list of array indices (i.e. non-negative integers), usually stepping by +1 but possibly also -1, 2, etc., and
b. producing an evenly spaced set of sample points, usually floating-point and with any spacing. This doesn't need to be accommodated by the standard library.
c. (possibly) skipping some items in a general iterator (Itertools::step(usize) that nodaki mentioned)

2 What restrictions are there on syntax / implementation?

As far as I am aware, the a..b syntax must be kept for integers and must be usable as an iterator.

Is there a fundamental reason that -20..20 or 0.5..2.5 or "a".."z" cannot be implemented? Is there already a commitment to enable (0..8).step_by(2) in this form?

3 Flexibility, optimizability and intuitiveness

Which is clearer, (0..100).step_by(10) or (0..10) * 10? ` Or some other way?

Is there any point allowing negative steps? Maybe not for indices since .reverse() is clearer but possibly for a range of sample points (e.g. (0..11) / -100 to yield 0, -100, -200, ..., -1000).

One thing I like about the RANGE * SCALAR syntax is that it might enable type-conversions to floats or user-defined types without requiring support for those types in the a..b syntax.

[SimonSapin]

I agree that Iterator::step_by is good, regardless of whether it is the solution for ranges. Let’s stabilize it.

@rfcbot fcp merge

The tracking issue for range (stepped) iterator is #42168

[rfcbot]

Team member @SimonSapin has proposed to merge this. The next step is review by the rest of the tagged teams:

• @Kimundi
• @SimonSapin
• @alexcrichton
• @aturon
• @dtolnay
• @sfackler
• @withoutboats

No concerns currently listed.

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[gnzlbg]

Is there an RFC or post or something that documents the behavior being proposed for stabilization?

I find it extremely hard to extract from this issue what is exactly being proposed for stabilization, what is the rationale, alternatives that have been explored, etc.

I am not suggesting that this needs an RFC, but at least a summary of the work done and why what we have now is better and suitable for stabilization that what we had before. As a maintainer of collections implement step_by I would find such information useful to update my collections accordingly.

[SimonSapin]

@gnzlbg Yeah, this issue has a lot of history and can be hard to read now. Iterator::step_by(self, n: usize) -> StepBy<Self> returns a new iterator that is based on the inner iterator’s nth method:

https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.step_by

Creates an iterator starting at the same point, but stepping by
the given amount at each iteration.

Note that it will always return the first element of the iterator,
regardless of the step given.

Panics

The method will panic if the given step is 0.

Examples

Basic usage:

#![feature(iterator_step_by)]
let a = [0, 1, 2, 3, 4, 5];
let mut iter = a.into_iter().step_by(2);

assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&4));
assert_eq!(iter.next(), None);

[gnzlbg]

@SimonSapin thanks for the summary, that is really helpful.

[bluss]

I agree that step_by is good for iterators in general, but we risk a situation where we have to advise not using .step_by on ranges, which is going to be uphill ergonomically. I had hopes .step_by(usize) would be straightforward for ranges, but it's a bit complicated.

With the right tooling and right method name, a “increment type matching” stepping adaptor for ranges might still be easy to find for users.

Problems with step_by for ranges include such things as:

• Can't use u64 steps for an u64 range
• How do we implement a for example i16 range with usize step, in a way that is efficient, ideally “zero cost”.
  • Maybe we can do most of the work already in the constructor of the stepping adaptor for an Range<i16>. We figure out what an "equivalent" step that fits inside an i16 is and adjust the step accordingly.

[leonardo-m]

Could two different named methods ("step" and step_by"?) solve this issue, having one for ranges that takes an usize, and one for intervals that takes the same type as the interval?

[ivandardi]

Can't we have the step parameter be an associated type? Then on the generic Iterator we can have it be usize and for ranges we override it with Idx? Like

trait Iterator {
    type Item;
    type Idx = usize;
   
    /// ...
}

impl Iterator for Range<Idx=u16> {
    type Idx = Self::Idx;
    
    /// ...
}

Or something similar is this doesn't work out or if it's not desirable to add a new associated type to the Iterator trait.

[sfackler]

@ivandardi If we did that Range<u16> wouldn't implement Iterator<Item = u16> anymore.

[letheed]

@bluss How about renaming step_by to every or every_nth since it relies on nth. I agree the word "step" could bring confusion. The method is valuable on its own though even if it's not the solution for number ranges.

[SimonSapin]

I’m ok with every_nth / EveryNth.

[cuviper]

Semantics and naming choices like every_nth were discussed in PR #41439. I think it would be confusing to name this similar to nth, since they're off by one -- step_by(x) is the same as next() then repeating nth(x-1).

[letheed]

Then how about every.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period is now complete.

[scottmcm]

I looked at overriding StepBy::try_fold to see if it would help. It does seem to help, but the biggest thing for me was that it clarified what made it hard for LLVM: the inner loop for (a..b).step_by(7).map(|x| x ^ (x - 1)).sum() is:

	mov	r8d, eax
	lea	r9d, [rcx - 1]
	lea	eax, [rcx - 2]
	xor	eax, r9d
	add	eax, r8d
	mov	r9d, ecx
	add	r9d, 6
	setb	r8b
	cmp	r9d, edx
	jae	.LBB1_6
	add	ecx, 7
	test	r8b, r8b
	je	.LBB1_4

which doesn't simplify further because of the slightly-awkward semantics of nth. It needs to return the 6th item and step by 7. (So the Range iterator is doing both Step::add_usize(6) and Step::add_one().)

I think this'd be perfectly efficient in terms of a "return next and also step forward" method, since the Range iterator for that would just return start and replace it with start.add_usize(7). I dunno if there'd be an appetite for such a thing, though...

[Emerentius]

Could we amend a note to step_by allowing us to use the pre-stepping semantics that @scottmcm spoke of? Given that iteration can have side-effects, I fear we may be overconstraining ourselves with regards to range iterators. While the current side-effect free integer ranges can deal with this, RangeFrom would already be changing semantics with pre-stepping because of overflow. It could affect additional situations when the Step trait will be stabilized.

While specializations of StepBy<Range*<_>> catch the most common case performance issues, they miss all the more complicated ones where the Range is hidden within an adapter.