Is mutable index for array considered a special case for borrow-checker

[M4tsuri]

Hello, I wrote a simple program:

struct Arr;

impl core::ops::Index<usize> for Arr {
    type Output = Self;

    fn index(&self, _index: usize) -> &Self::Output {
        &self   
    }
}

impl core::ops::IndexMut<usize> for Arr {
    fn index_mut(&mut self, _index: usize) -> &mut Self::Output {
        self   
    }
}

impl Arr {
    fn len(&self) -> usize {
        
        1
    }
}

fn main() {
    let mut arr = [0, 1, 2];
    increment(&mut arr[arr.len() - 1]); // line 26
    let mut arr = Arr;
    increment(&mut arr[arr.len() - 1])  // line 28
}

fn increment<T>(_arr: &mut T) {}

I think the compiler would fail at line 26 since I tried to get an immutable reference for arr while holding a mutable reference.

However, what happened is the compiler only fails at line 28. I cannot tell any difference between the two invocations. I wonder if there is a special case in borrow check for mutably indexing an array.

You can try it at Rust Playground

Thank you.

Edit 1:

As suggested by @trentj . I checked the MIR generated for each invocation for increment. Here is what I found:

The generated MIR for line 26 looks like this:

bb0: {
        _1 = [const 0_i32, const 1_i32, const 2_i32]; // scope 0 at src/main.rs:27:19: 27:28
        _8 = &_1;                        // scope 1 at src/main.rs:28:24: 28:33
        _7 = move _8 as &[i32] (Pointer(Unsize)); // scope 1 at src/main.rs:28:24: 28:33
        _6 = Len((*_7));                 // scope 1 at src/main.rs:28:24: 28:33
        _9 = CheckedSub(_6, const 1_usize); // scope 1 at src/main.rs:28:24: 28:37
        assert(!move (_9.1: bool), "attempt to compute `{} - {}`, which would overflow", move _6, const 1_usize) -> bb1; // scope 1 at src/main.rs:28:24: 28:37
    }

    bb1: {
        _5 = move (_9.0: usize);         // scope 1 at src/main.rs:28:24: 28:37
        _10 = const 3_usize;             // scope 1 at src/main.rs:28:20: 28:38
        _11 = Lt(_5, _10);               // scope 1 at src/main.rs:28:20: 28:38
        assert(move _11, "index out of bounds: the length is {} but the index is {}", move _10, _5) -> bb2; // scope 1 at src/main.rs:28:20: 28:38
    }

    // LOOK AT HERE: We take the mutable reference until now
    bb2: {
        _4 = &mut _1[_5];                // scope 1 at src/main.rs:28:15: 28:38
        _3 = &mut (*_4);                 // scope 1 at src/main.rs:28:15: 28:38
        _2 = increment::<i32>(move _3) -> bb3; // scope 1 at src/main.rs:28:5: 28:39
    }

The compiler choose to take the mutable reference just before the invocation of increment.

However, as for line 28, we have:

    // LOOK AT THIS (corresponds to line 28)
    bb3: {
        _15 = &mut _12;                  // scope 2 at src/main.rs:30:15: 30:43
        _18 = &_12;                      // scope 2 at src/main.rs:30:29: 30:38
        _17 = Arr::len(move _18) -> bb4; // scope 2 at src/main.rs:30:29: 30:38
    }

    bb4: {
        _19 = CheckedSub(_17, const 1_usize); // scope 2 at src/main.rs:30:29: 30:42
        assert(!move (_19.1: bool), "attempt to compute `{} - {}`, which would overflow", move _17, const 1_usize) -> bb5; // scope 2 at src/main.rs:30:29: 30:42
    }

    bb5: {
        _16 = move (_19.0: usize);       // scope 2 at src/main.rs:30:29: 30:42
        _14 = <Arr as IndexMut<usize>>::index_mut(move _15, move _16) -> bb6; // scope 2 at src/main.rs:30:15: 30:43
    }

    bb6: {
        _13 = &mut (*_14);               // scope 2 at src/main.rs:30:15: 30:43
        _0 = increment::<Arr>(move _13) -> bb7; // scope 2 at src/main.rs:30:5: 30:44
    }

We can see the mutable reference is taken firstly, and then the immutable reference used by calculating length, thus leads to a compilation error.

As is also mentioned by @trentj , the reason of the difference is so called "intrinsic indexing", which means the compiler already knows how to index an array so it does not go through the one in library. I also found another two topics related to it:

What is "intrinsic indexing"?

I'm trying to understand how std::vec::Vec indexing works. I've traced the code to usize's SliceIndex trait implementation. It looks like it first dereferences the slice reference, then indexes it. But there doesn't seem to be index implementation on slice as value. What does "intrinsic indexing" mean?

Why this does not lead to recursion?

@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 compile…

Edit 2:

I originally came up to this question from this meme:

I found that the range operator for array is not intrinsic. This explains why there is a compilation error in the final frame.

[trentj]

The [] operation is built-in for arrays and slices, so line 26 does not actually use the IndexMut trait, which means the mutable reference does not have to be taken until after the index is calculated.

It's not a special case in the borrow checker per se. It's a difference in the MIR produced by each operation, but since borrowck runs on MIR this is about the only way you can observe this difference.

[VorfeedCanal]

That's not difference in borrow-checker, but difference in calculations. You can change you example like this and then it would compile:

fn main() {
    fn take_n<A: core::ops::IndexMut<usize>>(index: usize, a: &mut A) -> &mut A::Output {
        &mut a[index]
    }
    let mut arr = [0, 1, 2];
    increment(take_n(arr.len() - 1, &mut arr)); // line 26
    let mut arr = Arr;
    increment(take_n(arr.len() - 1, &mut arr))  // line 28
}

That's because take_n first calculates index and then takes hold of the “array”, but simple call to index_mut takes them in the opposite order (&mut self comes before index: usize).

That's pretty weird corner case, but not in borrow checker.

[afetisov]

Actually I don't understand why the second example doesn't work. I thought that &mut v[n] desugars to v.index_mut(n), but if we use that form in code, it compiles. That's what is expected from two-phase borrows. So, how does &mut v[n] really work?

[trentj]

It's because of what I mentioned before: &mut v[n] isn't sugar for v.index_mut(n) in this context. It's simply a built-in operation. Most (all?) operators are defined in the compiler for some types, like + - / * for integers and floating-point numbers, and * for references (and raw pointers, which don't even implement Deref).

You can see some of these implementations at work because they are recursive. The implementation of Index<usize> for slices boils down to

    fn index(self, slice: &[T]) -> &T {
        // N.B., use intrinsic indexing
        &(*slice)[self]
    }

which just indexes the slice again - if this were sugar for Index::index, it would be infinitely recursive. But slices are special and don't go through the Index machinery (except in generic code).

[afetisov]

No, you didn't understand me. The second example (with Arr) is supposed to go through index_mut. And if you use index_mut explicitly, like in the snippet I linked, then it works.

[afetisov]

I think I understand the reason. Although &mut v[n] could reasonably be lowered to v.index_mut(n), it is instead lowered as a function call ::core::ops::IndexMut::index_mut(&mut arr, n). Most likely this happens because it's explicit and doesn't have the possibility of calling the wrong method (e.g. an inherent index_mut method, or a similarly named method from a different in-scope trait). But the consequence is that the two-phase borrow no longer works, since it applies exclusively to method calls, thus the confusing error.

Quote from the rustc dev guide:

Operators on all other types get lowered to a function call to their impl of the operator's corresponding trait.

I.e. operators lowered to functions, not methods.

I wonder whether two-phased borrows could be extended to function calls, or whether we could have method call syntax together with an explicit specification of the method to call.

[afetisov]

On the other hand, the op-assign family of operators seems to use yet another desugaring (method-based?), which means that the naive code compiles, but the explicit function call doesn't:

use core::ops::*;

struct Arr;

impl AddAssign<u32> for Arr {
    fn add_assign(&mut self, x: u32) {}
}

impl Arr {
    fn len(&self) -> u32 { 0 }
}

fn main() {
    let mut arr = Arr;
    arr += arr.len();
    arr.add_assign(arr.len());
    // error[E0502]: cannot borrow `arr` as immutable because it is also borrowed as mutable
    AddAssign::add_assign(&mut arr, arr.len());
}

So it seems like there is nothing in principle preventing IndexMut from a more user-friendly desugaring.

Edit: from the description of two-phased borrows:

The cases where we generate a two-phase borrow are:

1. The autoref borrow when calling a method with a mutable reference receiver.
2. A mutable reborrow in function arguments.
3. The implicit mutable borrow in an overloaded compound assignment operator.

So that explains why arr += arr.len() compiles. It seems like there should be added an extra case for &mut v[n] expressions. Since this strictly increases the set of allowed programs and is just as implicit as op-assign, I think it shouldn't cause issues.

[quinedot]

Being able to split borrows through an array or slice or Box, but not via the Index or Deref traits, does come up in other code from time to time.