Add `Step::forward/backward_overflowing` to enable RangeInclusive loop optimizations by pitaj · Pull Request #155114 · rust-lang/rust

pitaj · 2026-04-10T16:20:42Z

This adds new required methods to the Step trait:

trait Step: ... {
    // ... existing functions

    // New required functions
    fn forward_overflowing(start: Self, count: usize) -> (Self, bool);
    fn backward_overflowing(start: Self, count: usize) -> (Self, bool);
}

It was found that using these to implement RangeInclusive's Iterator impl enabled optimizations previously only applicable to the exclusive-ended Range.

This required changing how "exhaustion" works for RangeInclusive. I've nominated this for libs-api discussion because of one insta-stable change:

The new implementations now only set exhausted when overflow occurs, and start is now advanced past end otherwise. I doubt anyone depends on the prior behavior, but it's probably worth a crater run.

The exhaustion changes also affect Debug but my understanding is that debug formatting is never guaranteed stable.

I have now changed the nth impls to use the new functions as well.

r? libs

but RangeInclusive loops do not

and optimize the RangeInclusive iterator implementation with them This changes the `exhausted` field to represent an overflow flag for the bounds, essentially acting as an extra bit for `Idx`. This was found to enable optimizations previously only applicable to the exclusive-ended Range type.

Amanieu · 2026-04-14T17:28:15Z

We discussed this in the @rust-lang/libs-api meeting.

The PartialEq implementation as proposed violates the reflexivity requirement of the Eq trait which states that a == a must always be true. Instead, could equality be computed by ignoring the start field if the range is exhausted? This would treat the combination of start and exhausted as an Option<Idx> for the purposes of comparison.

If the PartialEq implementation can be fixed, we are happy to accept this after a crater run.

pitaj · 2026-04-14T18:06:57Z

Right, I forgot this implements Eq even though I implemented it manually 🤦‍♂️. exhausted.then_some(self.start) could work though it's less meaningful if the range was exhausted by reverse iteration.

@Amanieu I'm not sure it gains much over just going back to the derive, would that be acceptable?

Amanieu · 2026-04-14T22:16:51Z

RangeInclusive doesn't support reverse iteration.

The derive is also acceptable. We explicitly document that start has an unspecified value after exhaustion, so it makes sense for equality to also be unspecified.

pitaj · 2026-04-14T22:51:59Z

RangeInclusive doesn't support reverse iteration.

It implements DoubleEndedIterator but regardless yeah I'll change it back to the derive

pitaj · 2026-04-16T03:55:24Z

@rustbot ready

theemathas · 2026-04-16T07:57:07Z

I found a bug with this PR.

fn main() {
    let mut range = 255_u8..=255_u8;
    let _ = range.next();
    println!("{range:?}");
    println!("{}", range.contains(&100_u8));
}

Output of above code on nightly:

255..=255 (exhausted)
false

Output of above code with this PR:

0..=255 (exhausted)
true

(The desired behavior of the RangeBounds methods also need to be figured out.)

theemathas · 2026-04-16T08:12:33Z

And here's some strange behavior that's possibly a bug:

fn main() {
    let mut range = 0_usize..=0_usize;
    let _ = range.next_back();
    println!("{range:?}");
    let data = [0; 1000];
    println!("{:?}", &data[range]);
}

Output of above code on nightly:

0..=0 (exhausted)
[]

Output of above code with this PR:

0..=18446744073709551615 (exhausted)

thread 'main' (188575) panicked at src/main.rs:6:27:
range end index 18446744073709551615 out of range for slice of length 1000
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

theemathas · 2026-04-16T08:16:22Z

+
+        let (n, o) = Step::forward_overflowing(self.start.clone(), 1);
+
+        self.exhausted |= o;


Suggested change

self.exhausted |= o;

self.exhausted = o;

self.exhausted is always false before this line.

View changes since the review

theemathas · 2026-04-16T08:20:12Z

-            }
-        }
+        self.start = plus_1;
+        self.exhausted |= on | o1;


Suggested change

self.exhausted |= on | o1;

self.exhausted = on | o1;

Same thing here

View changes since the review

change end_bound to return Excluded(start) when exhausted add contains to tests

matches From<legacy::RangeInclusive<T>> for RangeInclusive<T> and expand explanation for into_slice_range

pitaj · 2026-04-16T19:09:05Z

@theemathas

I found a bug with this PR.

Good find on contains, that should be fixed now. Added some tests as well.

And here's some strange behavior that's possibly a bug

This is expected behavior from the new overflowing behavior. Given that the values of start and end have always been unspecified when exhausted, the indexing behavior is also unspecified - so I don't think this is an issue.

(The desired behavior of the RangeBounds methods also need to be figured out.)

I think the end_bound change I just made should resolve this. Now end_bound will return Excluded(start) when exhausted, which ensures (start_bound, end_bound) is always empty. This is fine since the values are unspecified anyways. Excluded(end) no longer works since end is no longer held equal to start on exhaustion.

I also changed into_bounds to panic when converting if exhausted. This matches the behavior of the conversion to the new RangeInclusive type, and is the only viable way of implementing IntoBounds unrestricted with the change. IntoBounds is unstable, so this can still be changed.

Nominating for libs-api approval of those changes

Amanieu · 2026-04-21T17:14:47Z

This was discussed the @rust-lang/libs-api meeting. We're happy with the end_bound change. Let's get a crater run started.

@bors try

Add `Step::forward/backward_overflowing` to enable RangeInclusive loop optimizations

Zalathar · 2026-04-22T05:47:18Z

@bors try

Add `Step::forward/backward_overflowing` to enable RangeInclusive loop optimizations

rust-bors · 2026-04-22T08:01:11Z

☀️ Try build successful (CI)
Build commit: b8e88e5 (b8e88e5ddf5521a9f43ee3f62a702388c713e4bb, parent: f9988fefd3add01f414f52b414308e7872622fee)

tgross35 · 2026-04-22T21:03:27Z

@craterbot run mode=build-and-test

(per #t-libs > crater run for #155114)

craterbot · 2026-04-22T21:03:59Z

👌 Experiment pr-155114 created and queued.
🤖 Automatically detected try build b8e88e5
🔍 You can check out the queue and this experiment's details.

ℹ️ Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

craterbot · 2026-05-03T20:01:43Z

🚧 Experiment pr-155114 is now running

ℹ️ Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

test that Range loops optimize away

a030144

but RangeInclusive loops do not

pitaj added the I-libs-api-nominated Nominated for discussion during a libs-api team meeting. label Apr 10, 2026

rustbot assigned Mark-Simulacrum Apr 10, 2026

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-libs Relevant to the library team, which will review and decide on the PR/issue. labels Apr 10, 2026

This comment has been minimized.

Sign in to view

pitaj force-pushed the rangeinclusiveiter-optimize branch from f26532b to d0c1f8d Compare April 10, 2026 17:02

pitaj mentioned this pull request Apr 10, 2026

Step::forward/backward_overflowing rust-lang/libs-team#767

Closed

This comment has been minimized.

Sign in to view

pitaj force-pushed the rangeinclusiveiter-optimize branch from d0c1f8d to 39e74a3 Compare April 10, 2026 18:01

Amanieu removed the I-libs-api-nominated Nominated for discussion during a libs-api team meeting. label Apr 14, 2026

revert to deriving Eq, add overflowing impls for nth

ddaca0b

theemathas added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Apr 16, 2026

theemathas reviewed Apr 16, 2026

View reviewed changes

theemathas added the needs-crater This change needs a crater run to check for possible breakage in the ecosystem. label Apr 16, 2026

pitaj added 3 commits April 16, 2026 10:32

no need for |=, exhausted must be false

5036075

fix contains via end_bound

34065c2

change end_bound to return Excluded(start) when exhausted add contains to tests

make into_bounds panic when exhausted

805bd01

matches From<legacy::RangeInclusive<T>> for RangeInclusive<T> and expand explanation for into_slice_range

nia-e added I-libs-api-nominated Nominated for discussion during a libs-api team meeting. and removed I-libs-api-nominated Nominated for discussion during a libs-api team meeting. labels Apr 21, 2026

This comment has been minimized.

Sign in to view

rust-bors Bot pushed a commit that referenced this pull request Apr 21, 2026

Auto merge of #155114 - pitaj:rangeinclusiveiter-optimize, r=<try>

6400b14

Add `Step::forward/backward_overflowing` to enable RangeInclusive loop optimizations

Amanieu removed the I-libs-api-nominated Nominated for discussion during a libs-api team meeting. label Apr 21, 2026

rust-bors Bot added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Apr 21, 2026

This comment has been minimized.

Sign in to view

rust-bors Bot pushed a commit that referenced this pull request Apr 22, 2026

Auto merge of #155114 - pitaj:rangeinclusiveiter-optimize, r=<try>

b8e88e5

Add `Step::forward/backward_overflowing` to enable RangeInclusive loop optimizations

theemathas added the relnotes Marks issues that should be documented in the release notes of the next release. label Apr 22, 2026

rustbot mentioned this pull request Apr 22, 2026

Tracking issue for release notes of #155114: Add Step::forward/backward_overflowing to enable RangeInclusive loop optimizations #155633

Open

craterbot added S-waiting-on-crater Status: Waiting on a crater run to be completed. and removed S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. labels Apr 22, 2026


		let (n, o) = Step::forward_overflowing(self.start.clone(), 1);

		self.exhausted \|= o;

Uh oh!

Conversation

pitaj commented Apr 10, 2026 • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

This comment has been minimized.

This comment has been minimized.

Amanieu commented Apr 14, 2026

Uh oh!

pitaj commented Apr 14, 2026

Uh oh!

Amanieu commented Apr 14, 2026

Uh oh!

pitaj commented Apr 14, 2026

Uh oh!

pitaj commented Apr 16, 2026

Uh oh!

theemathas commented Apr 16, 2026

Uh oh!

theemathas commented Apr 16, 2026

Uh oh!

theemathas Apr 16, 2026 • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

theemathas Apr 16, 2026 • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pitaj commented Apr 16, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Amanieu commented Apr 21, 2026

Uh oh!

This comment has been minimized.

This comment has been minimized.

This comment has been minimized.

This comment has been minimized.

Zalathar commented Apr 22, 2026

Uh oh!

This comment has been minimized.

rust-bors Bot commented Apr 22, 2026

Uh oh!

tgross35 commented Apr 22, 2026

Uh oh!

craterbot commented Apr 22, 2026

Uh oh!

craterbot commented May 3, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

10 participants

pitaj commented Apr 10, 2026 •

edited by rustbot

Loading

theemathas Apr 16, 2026 •

edited by rustbot

Loading

theemathas Apr 16, 2026 •

edited by rustbot

Loading

pitaj commented Apr 16, 2026 •

edited

Loading