Integer overflow on String::drain() with an inclusive range

[bodil]

I would expect this code to panic at the drain() because usize::max_value() is an out of bounds index:

fn string_drain_overflow() {
    let mut string = String::new();
    string.drain(..=usize::max_value());
}

Instead, it succeeds and returns an empty iterator. Looking at the implementation for String::drain(), I'm assuming an integer overflow happens at line 1542 Included(&n) => n + 1 and the range is taken to be 0..0. Honestly, I expected the add operation itself to panic on overflow so I'm not entirely sure what the correct behaviour is here.

Meta

rustc 1.43.1 (8d69840ab 2020-05-04)
binary: rustc
commit-hash: 8d69840ab92ea7f4d323420088dd8c9775f180cd
commit-date: 2020-05-04
host: x86_64-unknown-linux-gnu
release: 1.43.1
LLVM version: 9.0

Update: the same bug exists in String::replace_range.

[hanna-kruppe]

Since no allocation (String or otherwise) can be usize::MAX bytes long, this range is necessarily out of bounds and should panic. It's probably hard to match the panic message of other out-of-bounds conditions, but for a start we could use n.checked_add(1).unwrap() instead of n + 1 to get overflow checking (which is disabled by default in release mode, and users basically always get a release libstd).

BTW, the same overflow is lurking in the computation of start, e.g. when draining (Bound::Excluded(usize::MAX), Bound::Unbounded).

[bodil]

I've also just encountered it in String::replace_range.

[estebank]

The same bug is present in String, Vec, VecDeque and proc_macro_server.

[estebank]

Nominating for discussion to see how we want to fix this (there are two or three alternatives).

[spastorino]

Assigning P-high as discussed as part of the Prioritization Working Group process and removing I-prioritize.

[spastorino]

This was discussed during today's weekly meeting. It was decided that now is @rust-lang/libs call. Tagging again as T-libs, leaving I-nomination for libs team and removing T-compiler and libs-impl.

[pnkfelix]

also, I started a topic on the #t-libs zulip stream for this.

[Shnatsel]

Since no allocation (String or otherwise) can be usize::MAX bytes long, this range is necessarily out of bounds and should panic.

Using .saturating_add(1) instead of +1 would still panic without introducing an extra branch. Are there any blockers still, or should I go ahead and open a PR with this change?

[hanna-kruppe]

I don't think saturating_add(1) will compile to something branch-free in most mainstream architectures (with the notable exception of ARM/AArch64 and only referring to scalar code, in SIMD ISAs it's more common). As for blockers, as far as I can see @estebank never really spelled out what non-panicky "DWIM" semantics they have in mind exactly, but I suppose if they still care then they can also bring it up on the PR. Everyone else seemed on board with panicking?

[KodrAus]

We discussed this in the recent Libs meeting and felt that treating this case like an out-of-bounds panic was the most appropriate direction.

[tmiasko]

This was fixed in that manner by #75207.