Having Multiple Mutable References via Iterators

help
1

In section 8.1 of Brown Rust Book, there is the following question:

Determine whether the program will pass the compiler.
If it passes, write the expected output of the program if it were executed.

fn main() {
  let mut v: Vec<i32> = vec![1, 2, 3];
  let mut v2: Vec<&mut i32> = Vec::new();
  for i in &mut v {
    v2.push(i);
  }
  *v2[0] = 5;

  let a = *v2[0];
  let b = v[0];
  println!("{a} {b}");
}

I thought that this obviously doesn't compile because we are taking multiple mutable references to v. But it turns out I was wrong. The program compiles fine.

Which is weird because in section 4.3 of the same book, they say the following:

Rust’s borrow checker does not contain different places for a[0], a[1], and so on. It uses a single place a[_] that represents all indexes of a.

They were talking about arrays in that section, but the same applies to vectors.

For example, this doesn't compile:

fn main() {
    let mut v = vec![0, 1, 2, 3];
    let x = &mut v[1];
    let y = &mut v[2];
    *x += *y;
    println!("{v:?}");
}

Output:

error[E0499]: cannot borrow `v` as mutable more than once at a time
 --> src/main.rs:4:18
  |
3 |     let x = &mut v[1];
  |                  - first mutable borrow occurs here
4 |     let y = &mut v[2];
  |                  ^ second mutable borrow occurs here
5 |     *x += *y;
  |     -------- first borrow later used here
  |
  = help: use `.split_at_mut(position)` to obtain two mutable non-overlapping sub-slices

For more information about this error, try `rustc --explain E0499`.

But this totally compiles:

fn main() {
    let mut v = vec![0, 1, 2, 3];
    let mut iter = v.iter_mut();
    let x = iter.next().unwrap();
    let y = iter.next().unwrap();
    *x += *y;
    *y += *x;
    println!("{v:?}");
}

Output:

[1, 2, 2, 3]

So my question is:
How does this work?
Is the iterator doing something similar to split_at_mut for each element under the hood?

Disclaimer:
I'm a Rust beginner so sorry if the question is stupid or was answered before.

1 Like
2

that is indeed what it is doing. you should prob not look at the way it is doing it in practice because it is done in a very messy and unsafe way for optimization purposes, but what it does in spirit is roughly this :

struct IterMut<'slice, T> {
    slice: &'slice mut [T],
}

impl<'slice, T> Iterator for IterMut<'slice, T> {
    type Item = &'slice mut T;
    fn next<'short>(self: &'short mut IterMut<'slice, T>)
      -> Option<&'slice mut T>
    {
       let [hd, tl @ ..] = ::core::mem::replace(&mut self.slice, &mut [])
       else {
           return None;
       };
       self.slice = tl;
       Some(hd)
    }
}

stolen from @Yandros on discord cause i couldn't find my old impls and i am lazy

10 Likes
3

Thank you for the elaborate response!

4

Here's the same safe approach in slow-motion.

4 Likes
6

That's not how the standard library iteration works. What you're describing is a so-called lending, or streaming, iterator, which is able to borrow from itself, because all these borrows are guaranteed to end before they become dangling or aliasing. The standard Iterator doesn't allow this, since it can be collected into something that contains all its items (here, references) at once.

1 Like
7

Incidentally, this statement is wrong, at least in a lies-to-children way. When you use the indexing operator, that borrows the entire array (I would say that this should be described as a, not a[_], because there is no difference), but you can have the borrow checker track borrows of part of the array, as long as you do not take them using the indexing operator or any use of &mut [...] borrows of the whole array.

fn main() {
    let mut a = ['w', 'x', 'y', 'z'];
    
    // these do not overlap so they can exist simultaneously
    let [ref mut w, _,         ref mut y, _        ] = a;
    let [_,         ref mut x, _,         ref mut z] = a;
    
    *w = '<';
    *z = '>';
    
    println!("{a:?}"); // ['<', 'x', 'y', '>']
}

The same works for slices, such as those you can borrow from a Vec, though it gets harder to demonstrate with unknown lengths:

let mut v = vec!['w', 'x', 'y', 'z'];
let s = &mut v[..];

let [ref mut w, _,         ref mut y, _        , ..] = *s else { panic!() };
let [_,         ref mut x, _,         ref mut z, ..] = *s else { panic!() };
// rest of the program as above
5 Likes
8

Under the hood, this is implemented using unsafe pointer manipulation, closer to low-level C-style iteration than purely “safe-looking” Rust code.

image
image717Ă—410 50.3 KB

However, the key point is that this unsafety is fully encapsulated within the standard library.

The iterator still upholds Rust’s aliasing guarantees. From the user’s perspective, the semantics remain safe: each call to next() yields a unique mutable reference, and the iterator enforces forward-only traversal, preventing overlapping borrows.

1 Like
9

Regarding the original issue:

The reason this works is that after b is created v2 is no longer used, nor are there borrows of v2 alive. Hence the borrows in v2 can be considered "dead".

Note that a does not borrow from v2: the expression *v2[0] created a copy of the value pointed by v2[0], which is simply 1.

3 Likes
10

@quinedot thanks for the detailed explanation. Also thanks for sharing a bunch of resources and advice. I will keep a reference to it and check all of it after finishing The Rust Book.

1 Like
11

@kpreid thanks for sharing this is very cool. It also helps me set my expectations for my level of understanding after reading The Rust Book. I initially thought I will have a deep understanding of the language after finishing the book lol.

12

Please correct me if I'm wrong, but I heard that the Rust compiler allows us to write a proof to convince it that an unsafe block is actually safe.

Does the standard library include such proofs for its unsafe blocks? Or is it too difficult to write proofs for such heavily optimized code (as mentioned by @Morgane55440)?

13

This part I figured out when I tried to solve the quiz. But I answered "code won't compile" because of the loop that stores multiple mutable references to v. I thought the compiler will complain about that part. I was wrong, the compiler doesn't complain about that part.

But the later parts made sense to me. It also makes sense that if we switch the order of a and b:

let b = v[0];
let a = *v2[0];
println!("{a} {b}");

The program doesn't compile because we're using v while the v2 mutable reference is still alive.

14

This is not true. The amount of proof-checking the compiler can do is already expressed in types and lifetimes, and when you write unsafe code you are presenting the compiler with something it cannot prove and must take as an axiom.

There are efforts to improve on this situation by adding some amount of machine checking to safety requirements, and it’s possible to apply more powerful tools, but there is no such thing as an unsafe-specific proof in standard Rust.

1 Like
15

Never heard of any compiler feature where you can provide a proof that an unsafe block is safe.

If the compiler could fully verify that a piece of code is safe, then unsafe block would not be needed there in the first place.

In practice, a lot of safe Rust is built on top of unsafe. Many low-level primitives, like raw pointers and direct memory manipulation, cannot be expressed in purely safe Rust.

These ultimately come from hardware realities, where concepts like pointers are inherently outside the guarantees that hardware can guarantee, but Rust can build safe primitives on top.

So “proving” safety is really the responsibility of the developer: you establish and uphold certain invariants, and then build safe abstractions on top of unsafe code. This is exactly how much of the standard library is implemented and rust compilation itself.

2 Likes
16

Thanks for the correction @kpreid and @amid.ukr. Now I get the idea. The connection to mathematical proofs and axioms makes a lot of sense.

1 Like