"cannot borrow as immutable because it is also borrowed as mutable"

This innocent snippet does not compile:

fn main() {
    let mut v = vec![1,2,3];
    v[v.len() - 1] = 42;
    println!("{:?}", v);
}

I tried to do some investigation and found a thread about NLL non-lexical lifetimes. I thought that this applies here and tried #![feature(nll)], but the compiler just says that nll is part of stable since 1.63. Is this not an NLL issue? Why does it not work?

1 Like

I am also curious why that can not be compiled. But this can workd fine:

let mut v = vec![1,2,3];
let index = v.len() - 1;
v[index] = 42;
println!("{:?}", v);

I thought v[v.len() - 1] deprocessed by

let index = v.len() - 1;
v[index] = 42;

but it seems not. It seems the compiler handle the v[v.len() - 1] as a whole.
Look foreward to more reply.

It doesn't work because the method call is implicitly creating an &mut to v. Here the method call is hidden behind the index operator, but the same process occurs

The line

v[v.len() - 1] = 42;

could be desugared as

*std::ops::IndexMut::index_mut(&mut v, v.len() - 1) = 42;

which hopefully makes the problem more obvious.


Interestingly, if you create a function with arguments in the opposite order it does work!

use std::ops::IndexMut;

fn main() {
    let mut v = vec![1, 2, 3];
    *backwards_index(v.len() - 1, &mut v) = 42;
    println!("{:?}", v);
}

fn backwards_index<I, T>(index: T, col: &mut I) -> &mut I::Output
where
    I: IndexMut<T>,
{
    col.index_mut(index)
}

That's because the reference to v from calling len doesn't stick around after the expression ends. In contrast, the reference created by &mut v is passed into the function so must live at least as long as the reference returned by index_mut

11 Likes

The desugaring of the [] to a function call is interesting.

Here is a simplified version:

fn foo(a: i32, b: &mut i32) { *b = a; }
fn bar(b: &mut i32, a: i32) { *b = a; }

fn main() {
    let mut x = 4;
    foo(x, &mut x);  // OK
    bar(&mut x, x);  // ERR
    println!("{:?}", x);
}

I am not in the technical details of the borrow checker, but from an outside perspective it does not make sense to me that foo works, but bar does not. Why should the order of function arguments matter?

I would understand cases with more complicated argument expressions like this: zoo(some(&mut x), x). Here the order matters because some might change x. However if arguments are on the same "level" it is trivial that &mut x is not actually used to change or even access x before the function is called.

3 Likes

The order matters because the order of the arguments is also an order of operations the program will perform.

With foo(x, &mut x) we are copying a value from x, and then creating a &mut to x. The binding x is no longer referenced by the value that was copied in the first step, so there's no conflict there.

bar(&mut x, x) creates that &mut to x first, which means that nothing else can touch x for as long as that &mut exists[1]. There's no way to access the value of x in order to create that copy anymore because we've just given away the permission to do that as far as the borrow checker is concerned.


  1. except by going through that same reference ↩︎

4 Likes

Yes I can see that argument, but as the program is obviously valid it smells like overzealous borrow checker. The borrow checker should be able to see that in foo(&mut x, x) that "pointer" to x is not used in any way before the function is called - not to write and not even to read the value of x.

2 Likes

The borrow checker should be able to see that …

The compiler does actually make an analysis like that — it is called “two-phase borrows”. That is why this program works, even though it seems like it should have the same problem:

let mut v = Vec::new();
v.push(v.len());

However, they have very narrow applicability (a specific set of cases listed in the page I linked). I don't know what the rationale is for the exact list, but I think it might be only cases where an &mut is implicitly, not explicitly, created. But the Index usage that started this thread is one of those.

So, the path forward from here would be to make the case that v[v.len() - 1] should also have the two-phase borrows feature.

10 Likes

That is a great link - thank you!

Now I am puzzled. It looks like operator[] is implemented via the IndexMut trait which seems to get some special handling.

Consider this snippet which does NOT compile:

#[derive(Debug)]
struct MyVec {
    u: Vec<i32>,
}
impl MyVec {
    fn len(&self) -> usize { self.u.len() }
}

use core::ops::{Index, IndexMut};
impl Index<usize> for MyVec {
    type Output = i32;
    fn index(&self, i: usize) -> &i32 { &self.u[i] }
}
impl IndexMut<usize> for MyVec {
    fn index_mut(&mut self, i: usize) -> &mut i32 { &mut self.u[i] }
}
fn main() {
    let mut f = MyVec{u : vec![1,2,3]};
    f[f.len() - 1] = 5;  // ERR
    println!("{:?}", f);
}

However using a custom trait with identical implementation like in this snippet does compile:

trait MyIndex {
    fn my_index_mut(&mut self, i: usize) -> &mut i32;
}
impl MyIndex for MyVec {
    fn my_index_mut(&mut self, i: usize) -> &mut i32 { &mut self.u[i] }
}

fn main() {
    let mut f = MyVec{u : vec![1,2,3]};
    *f.my_index_mut(f.len() - 1) = 5;  // OK
    println!("{:?}", f);
}

I have no idea why the Index trait does not need the dereferencing *, and even less why it is rejected by the borrow checker. Feels like a bug at this point.

3 Likes

While thinking about this, it's worth keeping the implications of Rice's theorem in mind: for any non-trivial property of code (such as those checked by the borrow checker), there are undecidable cases. An undecidable case is one where the checker can neither confirm that you breach the rules, nor can it show that you comply with the rules.

Rust handles this by having a conservative borrow checker; if the borrow checker can't prove you comply with the rules, it errors out and asks you to rewrite in a way that it can understand - which means it'll error on valid code as well as invalid code. This appears to you as an "overzealous borrow checker" - because it's approximating correctness by saying "things that are definitely correct by my rules are correct, things that I cannot show are correct are treated as incorrect".

As a consequence, you should expect to be able to find perfectly valid and correct code by Rust's rules that the borrow checker rejects - the hard part is working out how you'd change the borrow checker to only permit the valid code it currently rejects, and not either reject valid code it currently accepts, or accept invalid code.

In this specific case, fixing the borrow checker to accept this code becomes a fun exercise, because you still want it to reject the following code:

let mut v = vec![1,2,3];
let mutref = &mut v; // this currently gets an exclusive reference to v
println!("v has {} elements", v.len()); // This should fail because `mutref` exists
v.push(4); // This should fail, because it also wants an exclusive reference to v
mutref.push(5); // This is the first use of `mutref`

This means that it's not enough to delay the start of the region until the first use of the reference, because that would allow the block above to compile - but you might well have structured it this way to stop code after let mutref = from having access to v at all, except via mutref. Either that, or we need to confirm that this way of doing things doesn't exist in the wild, and change the definition of a borrow region to allow it to exist.

It's also not enough to have the borrow checker check arguments in both orders (front-to-back and back-to-front), since with 4 or more arguments, both could fail on valid code. You'd need the borrow checker to determine if there is an arrangement of the arguments that passes borrow checking - but you also don't want the time taken in borrow checking to hit a combinatorial explosion.

There's almost certainly a way to make the borrow checker identify this specific set of cases (where argument order affects borrow checking) cleanly, but I hope I've convinced you that this isn't as trivial as it looks at first glance.

7 Likes

Yes indeed, it can look trivial from the outside, but hard to implement correctly and performantly. However, from a user/dev perspective I would expect foo(&mut x, x) to work, particularly as the equivalent foo(x, &mut x) works just fine. Can't say I am a compiler expert, but for that particular case of "taking a &mut to pass as a function argument" it looks innocently enough to proof that the &mut is not actually accessed before the function "starts" and thus other uses of & to compute other function arguments can be allowed.

That being said, I still don't understand the following:

Why is v[v.len()-1]=5; rejected, but v.push(v.len()); is accepted? Both look like identical cases of "syntactically &mut is taken before a &, but that &mut isn't used just yet so it's ok". In particular as a "manual" implementation with traits is working fine. There is something specifically about operator[] which messes this up. What is it, and what could be done to allow it?

Let me also add a real-world example where this is particularly annoying:

#[derive(Debug)]
struct Matrix {
  elements: Vec<f32>,
  rows: usize,
  cols: usize,
}

impl Matrix {
  pub fn set(&mut self, row: usize, col: usize, value: f32) {
    self.elements[self.idx(row, col)] = value;  // ERR
  }
  
  fn idx(&self, row: usize, col: usize) -> usize {
    row * self.cols + col
  }
}

fn main() {
  let mut mat = Matrix { elements: vec![1.0,2.0,3.0,4.0,5.0,6.0], rows: 2, cols: 3 };
  mat.set(1,2, 3.0);
  println!("{:?}", mat);
}

One might say this case is even "worse" as the &mut is applied blanket to the whole Self object although the failing expression needs &mut and & for different fields.

And wrt to your example: I am not sure this should be rejected. It looks like another case of &mut being created significantly before use. Maybe I have a wrong mental model, but I am thinking about &mut as the "key which gives permission to write the value". However there is no reason to disallow other keys until that "write key" is actually used to write the value. The begin and end of the exclusiveness could be tailed to first and last use of the key, and at the very least in special cases like foo(&mut x, x). A related real-life example of this is instruction reordering which most compilers perform to improve performance.

1 Like

Your mental model is subtly wrong. &mut is doesn't give you permission to write the value but assures that nobody else can watch on your while you are touching that object. There was even discussion to replace &mut with &my, &only, or &uniq.

When mutable reference exist we must guarantee that none other other ways to access the object exist (and then we may modify it while nobody is looking).

Uniqueness leads to mutability, not the other way around.

Yeah, but that's you looking “throught” the implementation and understanding that it's okay to calculate things in different order.

That's much subtler issue than compiler is willing to reason about.

It's not even the problem of combinatorial explosion. It's worse.

This would mean that foo(bar(&mut v), baz(&v)); would call baz before bar.

And if bar and baz have visible side-effect this would cause a lot of frustration.

Rust prefers to ask you for clarifications in complex cases instead of assuming wrongly and producing subtle bugs.

This would mean that you would need to move these out from the function call, if you want predictability (that's what you have to do in C++, where order is unspecified, anyway).

But now you don't have a situation where if compiler understands me then everything works but if compiler misunderstands me then it's compile-time error, but if compiler understands me then everything works but if compiler misunderstands me then it's bug in my program which I would need to debug.

That is the reason, not the fact that this is hard to do, computionally.

4 Likes

Just want to mention that allowing foo(&mut x, x) doesn't mean we also have to allow foo(bar(&mut x), baz(x));. I would say that the latter should most definitely not be allowed as the order of operations matters. 1) bar(&mut x) and 2) baz(x) does not necessarily produce the same result as 1) baz(x) and 2) bar(&mut x). However if the order does not matter, for example in foo(&mut x, x) imho a "reordering" of instructions should be allowed, in particular if it is a quite trivial reordering. Meaning the burrow checker could see that &mut x -> x -> foo(_,_) is identical to x -> &mut x -> foo(_,_). This could extend to things like foo(baz(x), &mut x, taz(x)). As long as the &mut x can be moved right in front of the function call without changing the program, the program should be permissible.

The problem in that approach lies with the fact that since you only have result in one case but not in the other it's very hard to define when order does and doesn't matter.

That's a bit more actionable. But even that can lead to confusion. E.g. it would enable the example from the RFC: x.increment(x.increment(1)).

Is it really obvious that second increment happens before first? I'm not so sure.

You can read more explanations in the RFC itself.

Rust tries to keep the balance between what's possible to teach to the compiler and what's possible to teach to a human. You can explain to the compiler how eighteen types of initialization work together, but can you teach that to a human?

I'm not sure slight simplification of code in some rare cases is worth the added complexity… but you may discuss that on IRLO if you have same statistic about how useful that change would be.

5 Likes

Those rules read like you're trying to suggest an extension to two-phase borrow rules. The tendency in Rust is to start with very conservative rules, and relax them over time as we come up with good reasons to do so.

In this case, it looks like you have a decent motivating example, complete with an inconsistency with the existing rules, and I'd encourage you to go through the contribution process to the best of your ability to get this resolved.

1 Like

Just want to mention that I filed this as a bug and the issue is discussed here:

4 Likes

I guess the problem we are in is that v[v.len()-1] might need additional rules to be permissible which lead to mental load, however not allowing it also leads to mental load because now people have a really hard time understanding what the difference to v.push(v.len()) is. By partially opening up that door with two-phase borrow the demons are already through. I am not an expert to say how far that door should be opened, but it seems to be discussed on that ticket. A possible solution seem to be to allow a small exception for IndexMut for exactly that case.

Some people would always be confused, no matter what the rules are.

Yes. The question is always about what's the worst thing that may happen when someone will misunderstand the rules. Currently the choice is very safe even if not convenient. But the more complicated rules are becoming the more problematic are potential consequences of not understanding them.

IndexMut is kinda special because documentation was always preaching one thing yet implementation always used the other thing.

It's possible that fix to the implementation is better in that case. And IndexMut with side-effects is rare enough thing that it's probably not dangerous.

But general rule is not so easy to accept as improvement.

2 Likes

I'll say that before thinking about it I would probably assume the receiver borrow happens last, but that would be inconsistent with fully qualified syntax (or fully qualified methods would be inconsistent with free functions). Since the borrow checker has no runtime behavior this doesn't seem likely to cause issues directly, but if want a nice clear rule about when it was valid.

So in short: good thread!

2 Likes

I know this isn't in the spirit of the discussion, but I would probably just do this instead:

fn main() {
    let mut v = vec![1,2,3];
    *v.last_mut().unwrap() = 42;
    println!("{:?}", v);
}
1 Like