Slice indexing panics with valid "backwards" ranges

[clarfonthey]

I tried this code:

use core::ops::Bound;
fn main() {
    let buf: [u32; 0] = [];
    println!("{:?}", &buf[(Bound::Excluded(0), Bound::Included(0))]);
}

This feels perfectly valid, since the indices for the start and end of the range are both in-bounds, just with the backwards order that you'd expect. However, Rust internally converts this range into 1..1 and fails:

thread 'main' panicked at src/main.rs:4:26:
range end index 1 out of range for slice of length 0

Meta

rustc --version --verbose:

rustc 1.85.0-nightly (a4cb3c831 2024-12-17)
binary: rustc
commit-hash: a4cb3c831823d9baa56c3d90514b75b2660116fa
commit-date: 2024-12-17
host: x86_64-unknown-linux-gnu
release: 1.85.0-nightly
LLVM version: 19.1.5

Backtrace

stack backtrace:
   0: rust_begin_unwind
             at /rustc/90b35a6239c3d8bdabc530a6a0816f7ff89a0aaf/library/std/src/panicking.rs:665:5
   1: core::panicking::panic_fmt
             at /rustc/90b35a6239c3d8bdabc530a6a0816f7ff89a0aaf/library/core/src/panicking.rs:74:14
   2: core::slice::index::slice_end_index_len_fail_rt
             at /rustc/90b35a6239c3d8bdabc530a6a0816f7ff89a0aaf/library/core/src/slice/index.rs:64:5
   3: core::slice::index::slice_end_index_len_fail
             at /rustc/90b35a6239c3d8bdabc530a6a0816f7ff89a0aaf/library/core/src/slice/index.rs:58:5
   4: <core::ops::range::Range<usize> as core::slice::index::SliceIndex<[T]>>::index
             at ./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/index.rs:465:13
   5: <(core::ops::range::Bound<usize>,core::ops::range::Bound<usize>) as core::slice::index::SliceIndex<[T]>>::index
             at ./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/index.rs:1050:9
   6: core::slice::index::<impl core::ops::index::Index<I> for [T]>::index
             at ./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/index.rs:16:9
   7: core::array::<impl core::ops::index::Index<I> for [T; N]>::index
             at ./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/array/mod.rs:375:9
   8: playground::main
             at ./src/main.rs:4:26
   9: core::ops::function::FnOnce::call_once
             at ./.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5

Reason for emitting these "weird" ranges

I'm trying to create a data structure which stores a series of sorted, disjoint ranges in a Vec. When you determine where a provided range might fall into this vec, it's very natural to use the included/excluded bounds: you effectively have a similar API to that of binary_search, where "Included" means that an endpoint of a range overlaps with the range stored at an index, and "Excluded" means that the range does not overlap with the range stored at an index, but could be inserted after that index.

In this case, both the "normal" lopsided ranges (inclusive, then exclusive) happen, but also these "backwards" ones with exclusive, then inclusive. So, I think that supporting these "backward" ranges would be nice, even if it complicates the code a bit here.

[hanna-kruppe]

Trying to think about the meaning of (Excluded(n), Included(n)) hurts my brain, but looking only at the end half, I don’t see how Included(0) is in-bounds? There is no element at index 0 that could be included.

[clarfonthey]

There is an element that could be included, but excluded always overrides included: it's why 0..0 is a valid range for empty slices even though the initial "included" zero is technically referring to something that can't be in the range. And, in the code, you can swap the two arguments to see that there isn't a panic.

[hanna-kruppe]

I don’t know what “excluded overrides included” means. The way I think about slicing of arrays and slices, a..b ranges are the most natural and most general form, with both start and end referring to fence posts between elements. From that POV, it’s obvious why 0..0 is valid without pitting included/excluded against each other. Sometimes it’s convenient to specify bounds differently, but when in doubt I go back to the fence post POV (even if the fence post after element uN::MAX isn’t representable in uN).

In general (Excluded(a), Included(b)) translates into this model as (a+1)..(b+1) modulo overflow. This doesn’t give the result you want in this case, but it is internally consistent. Is there another internally consistent model that matches current behavior in all other cases? For example, 2..1 isn’t a valid range for slicing even though 1..2 is (for [T; 2]). With fenceposts, this can be explained by saying the end can’t be before the start, though they can be equal.

For ordered collections of keys, inclusive/exclusive bounds have a different meaning, related to the actual elements and not just their positions. But in these cases there’s rarely (never?) a concept of a bound being out-of-bounds (in an empty BTreeSet<char>, range('a'..='z') is valid and just has no elements). So I don’t know if this is relevant at all.

[clarfonthey]

I forgot to comment with this case, but here's another one that feels like it should pass: [][Bound::Excluded(0), Bound::Excluded(0)]. Since both sides are exactly the same, and we're excluding the zero index, this feels like it should pass, but since it desugars to 1..0, it fails.

To comment more explicitly on what I think the behaviour should be:

• The "start > end" check should only ever fail if the actual index included in the start bound is greater than the index included in the end bound.
• Excluded bounds should be considered in-bounds as long as they're within the range 0..=len.

I don't think that this would actually affect performance that much, but it's worth probably doing a benchmark just to be sure.