Why this does not lead to recursion?

#1

When indexing a slice by usize:

// impl Index for [T]
// F
fn index(&self, index: I) -> &I::Output {
  index.index(self)     // A
}
// when I is usize A will be
fn index(self, slice: &[T]) -> &T {
  // N.B., use intrinsic indexing
 &(*slice)[self]       // B
}

It seems B will call F again, what I have missed ? many thanks!

#2

This comment calls it out -- the language knows about slices, so this one doesn't actually go through the Index trait.

You can see this in MIR https://rust.godbolt.org/z/hasM8M -- the slice indexing is directly (*_1)[_2], whereas on a Vec it goes through a function call (<Vec<i32> as Index<usize>>::index(move _3, const 1_usize)).

1 Like
#3

Do you know why they made it an intrinsic instead of using pointer math?

impl Index for [T] {
  fn index(&self, index: I) -> &T {
    unsafe {
      assert!(index < self.len(), "index out of bounds");
      &*self.as_ptr().offset(index)
    }
  }
}
#4

@scottmcm has the right answer here. The compiler intrinsically knows how to index into slices. So in a way, implementing Index on slices seems redundant. In fact, you'll find this behavior for many of the traits in std::ops. The implementation for impl Add<i32> for i32 is basically

impl Add for i32 {
    type Output = i32;

    #[inline]
    #[rustc_inherit_overflow_checks]
    fn add(self, other: i32) -> i32 { self + other }
}

Why does this not recurse? Same reason as for Index. The compiler intrinsically knows how to add two i32s.
(Source here, it uses macros because this impl is the same for all the primitive numeric types.)

So why does rust have these seemingly redundant impls? Because they make generic code possible. Here's a (very contrived) example where you want a function that always adds 2 to an index before doing the operation.

use std::ops::Add;
use std::ops::Index;

fn main() {
    let vec: Vec<_> = vec![9, 8, 7, 6, 5];
    let slice: &[_] = &vec[..];
    dbg!(foo(&vec, 1));  // equivalent to vec[3]
    dbg!(foo(slice, 2)); // equivalent to slice[4]
}

// Takes any collection, including slices, that can be indexed into by `Ind`
fn foo<Out, Ind, C>(collection: &C, index: Ind) -> &Out
where
    C: Index<Ind, Output = Out> + ?Sized,
    Ind: From<u8> + Add<Output = Ind>,
{
    let i = index + 2.into();
    &collection[i]
}

Playground

1 Like
#5

One reason might be so the compiler can give correct line numbers for panicking? That would be possible today with your implementation using the #[track_caller] annotation, but #[track_caller] only exists as of Rust 1.46.0.

I could definitely imagine making this an intrinsic for the sake of having index-out-of-bound panics show the line of the access, rather than the internals of the compiler codebase.

#6

Otherwise inlining would be essential for runtime performance. This doesn't happen in debug mode, so not making it an intrinsic would cause a significant unnecessary slowdown in debug mode.

#7

Others have suggested explanations, but I suspect the real reason is just that slices and indexing predate the Index traits, and there's never been a compelling reason to do otherwise.

It also matches the implementations of the other ops traits, which (mostly?) can't be implemented without intrinsics.

#8

I get that there are a lot of places where you need intrinsics so LLVM will generate the right machine code, but why would they write a + b in the function body instead of a call to std::intrinsics::add_with_overflow()?

Intrinsics are known by the compiler and calls will often be replaced by the corresponding LLVM instruction(s), so I don't think this would add runtime overhead in debug builds.

#9

There is no intrinsic that has an equivalent behavior to a + b on integers. All integer intrinsics are fixed to either wrapping, returning if there was an overflow or causing UB on overflow. There doesn't exist one that chooses between wrapping and panicking depending on -Cdebug-assertions.

If a + b were to lower to Add::add for integers too, it would require inlining to get rid of the call at runtime. If a + b is special cased for integers, you may just as well use a + b as content of the Add::add impl for integers.

#10

Operator lowering

Operators on builtin types are not lowered to function calls (which would end up being infinite recursion calls, because the trait impls just contain the operation itself again). Instead there are Rvalue s for binary and unary operators and index operations. These Rvalue s later get codegened to llvm primitive operations or llvm intrinsics.

#11

See also Rust Tidbits: Box Is Special

#12

this code will never get called, that breaks the recursion : the compiler will detect case of scalar(u8,u16,etc.) addition and use builtin addition instead of calling add.

It is the same for indexing : when indexing an array or slice by usize, compiler will use builtin index operation instead of calling index