Rust is a cool language. But a small misconception can happen due a misunderstanding of borrowing and scoping rules for the language. Let me illustrate.

For those unfamiliar, a big feature of Rust is its borrowing and ownership rules. The rules are quite elegant, and are enforced at compile-time with the compiler’s borrow checker to ensure memory safety. I will summarise the rules here briefly:

Rule 1, Ownership:
One and only one owner can exist for any data that is allocated.
Assignment ‘=’ and move moves ownership of the data unless the datatype implements the Copy trait, but that’s not really relevant for the puzzle later on.

0
1
2

let x = String::from("hello");
let y = x; // ownership moves to y
println!("{}", x); // Error: borrow of moved value `x`

Rule 2, Multiple immutable references:
Multiple immutable references can exist.

0
1
2
3

let mut x = 1;
let y = &x; // immutable reference to x
let z = &x; // immutable reference to x
print!("{},{},{}", x,y,z); // OK!

Rule 3, One mutable reference:
Only one mutable reference can exist at a time.
This prevents a ‘multiple writer’ problem.

0
1
2
3
4

let mut x = 1;
let mut y = &mut x; 
let mut z = &mut x; // error!
*y += 1;
*z += 1; // error!

Rule 4, (Rule 2) XOR (Rule 3):
i.e. shared-xor-mutable.
Only 1 mutable reference can exist, or
Only N immutable references can exist.

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

let mut x = 1;
{
    let mut y = &mut x;
    *y += 1;
}
{
    let z = &x;
    let q = &x;
    let r = &x; 
}
// never a combination of &mut and &x!
{
    let y = &mut x;
    let z = &x;
    *y += 1; // error!
}

Rule 5, Every reference in Rust has a lifetime:
The lifetime is the scope for which that reference is valid. References must not live longer than the resource they refer to.

0
1
2
3
4
5

let x: &i32; // x is an uninitialized immutable reference to an i32
{
    let y = 1;
    x = &y;
}
print!("{}", x) ; // error! x lives longer than y.

These rules help ensure that at compile time, potential data races, dangling references and use-after-free never happen. Awesome.

Now that we understand the basic rules, let’s try this puzzle out:

A simple(?) borrow checking puzzle

0
1
2
3

let mut x = 1;
let mut y = &mut x;
let z = &x;
x += 1

What will be the value of x?

A: 2
B: Compile error
C: Panics

Answer: x will successfully increment to 2!

Huh?

I hope that the puzzle felt unintuitive to you.

If you don’t believe the output, run it on the rust playground.

You might not believe it, but this is perfectly in line with the borrow-checker rules.

A closer look

We know via rule 4 we can either have one mutable reference XOR multiple immutable references.

y is a mutable reference to x. So, according to rule 4, we cannot have any more immutable references. Yet, we can still add let z = &x and it compiles.

Why is that the case? Let’s create a slightly different version of our program to see what’s going on.

0
1
2
3
4

// NOTOK.rs
let mut x = 1;
let mut y = &mut x;
let z = &x;
y += 1

In this case, the compiler will complain and give the error we expect:

0
1
2
3
4
5
6
7
8

error[E0502]: cannot borrow `x` as immutable because it is also borrowed as mutable
 --> nok.rs:4:13
  |
3 |     let mut y = &mut x;
  |                 ------ mutable borrow occurs here
4 |     let z = &x;
  |             ^^ immutable borrow occurs here
5 |     *y += 1;
  |     ------- mutable borrow later used here

Why is this the case?

Lifetimes

Rust docs tells us that the borrow check happens in Mid-Level Intermediate Representation (MIR) of the code. MIR is a simplified representation of Rust in middle of the compile process to use for safety checks.

We must therefore, gaze into the abyss (MIR files) to gain insight.

To simplify things, let’s say that in a given scope, the shared-xor-mutable rule must be adhered to.

The MIR of both programs will give us information about the lifetimes of each variable.

We can do this by compiling our code with the nightly compiler:
$ rustc +nightly -Zdump-mir=all main.rs

This generates a bunch of MIR files to let us see the program in the compile process. One artefact that MIR gives us is the lexical scope of the program.

Funnily, the lexical scope generated by the MIR is the same for both programs:

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

scope 1 {
    debug x => _1;
    let mut _2: &mut i32;
    scope 2 {
        debug y => _2;
        let _3: &i32;
        scope 3 {
            debug z => _3;
        }
    }
}

So, this does not tell us anything useful. In fact, it seems to suggest that z bleeds into y’s scope which violates the shared-xor-mutable rule!

Wait, what is _1, _2, _3? We can think of these as handles to the actual data.

The MIR tells us much more regarding this. The following block of operations generated by rust allows us to attach meaning to the lifetimes of the variables. For the version that compiles:

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// COMPILES
bb0: {
    StorageLive(_1);  // (x = _1) life starts
    _1 = const 1_i32;
    StorageLive(_2); // (y = &mut x) life starts
    _2 = &mut _1;
    StorageLive(_3); // (z = &x) life starts
    _3 = &_1;
    _4 = AddWithOverflow(copy _1, const 1_i32);
    assert(!move (_4.1: bool), "attempt to compute `{} + {}`, which would overflow", copy _1, const 1_i32) -> [success: bb1, unwind continue];
}

bb1: {
    _1 = move (_4.0: i32);
    _0 = const ();
    StorageDead(_3); // z life ends
    StorageDead(_2); // y life ends
    StorageDead(_1); // x life ends
    return;
}

For the version that fails to compile:

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// DOES NOT COMPILE
bb0: {
    StorageLive(_1);  // (x = _1) life starts
    _1 = const 1_i32;
    StorageLive(_2); // (y = &mut x) life starts
    _2 = &mut _1;
    StorageLive(_3); // (z = &x) life starts
    _3 = &_1;
    _4 = AddWithOverflow(copy (*_2), const 1_i32);
    assert(!move (_4.1: bool), "attempt to compute `{} + {}`, which would overflow", copy (*_2), const 1_i32) -> [success: bb1, unwind continue];
}

bb1: {
    (*_2) = move (_4.0: i32);
    _0 = const ();
    StorageDead(_3); // z life ends
    StorageDead(_2); // y life ends
    StorageDead(_1); // x life ends
    return;
}

Damn. Basically the same. Even for the compilable version, the lifetimes of x,y,z dont make sense! The life of mutable reference y overlaps with z, right?

Not really. This is because of non-lexical-lifetimes (NLL).

Non-Lexical-Lifetimes

NLL: The lifetime of a reference is tied to the ‘control-flow-graph’ rather than its lexical scope. The end of a reference’s lifetime is tied to its last use.

The rust book summarises this nicely:

Note that a reference’s scope starts from where it is introduced and continues through the last time that reference is used.

0
1
2
3
4
5
6
7
8
9

// lifted from the rust book
let mut s = String::from("hello");

let r1 = &s; // no problem
let r2 = &s; // no problem
println!("{r1} and {r2}");
// variables r1 and r2 will not be used after this point

let r3 = &mut s; // no problem
println!("{r3}");

This concept tends to be overlooked at when we have discussions about shared-xor-mutable (my personal observation). It is also a source of confusion to people trying to learn about the language.

Ok, so it seems that the MIR does not give us the full picture.

Shared-xor-mutable rule should be applied to the NLL scope rather than lexical scope.

So, going by the definition above, let’s manually annotate the MIR code with the NLL:

0
1
2
3
4
5
6
7
8
9

bb0: {
    StorageLive(_1);  // (x = _1) scope starts
    _1 = const 1_i32;
    StorageLive(_2); // (y = &mut x) scope starts
    _2 = &mut _1;    // y borrow scope ends (no more use of y)
    StorageLive(_3); // (z = &x) scope starts
    _3 = &_1;        // z borrow scope ends (no more use of z)
    _4 = AddWithOverflow(copy _1, const 1_i32);
    assert(!move (_4.1: bool), "attempt to compute `{} + {}`, which would overflow", copy _1, const 1_i32) -> [success: bb1, unwind continue];
}

This makes more sense. If we use the same syntax as the lexical scope block, then the NLL would probably look like this:

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// My take on what the scope will look like
scope 1 {
    debug x => _1;
    let mut _2: &mut i32;
    scope 2 {
        debug y => _2; // OK! 1 owner, 1 mutable borrow
    } // y goes out of scope
    let _3: &i32;
    scope 3 {
        debug z => _3; // OK! 1 owner, 1 immutable borrow
    } // z goes out of scope
}

But for the non-compileable version, we see that y is used in the addition, which extends the scope of y.

0
1
2
3
4
5
6
7
8
9

bb0: {
    StorageLive(_1);  // (x = _1) scope starts
    _1 = const 1_i32;
    StorageLive(_2); // (y = &mut x) scope starts
    _2 = &mut _1;
    StorageLive(_3); // (z = &x)  scope starts
    _3 = &_1;        // z borrow scope ends
    _4 = AddWithOverflow(copy (*_2), const 1_i32); // y is used here, so scope is extended, including this line 
    assert(!move (_4.1: bool), "attempt to compute `{} + {}`, which would overflow", copy (*_2), const 1_i32) -> [success: bb1, unwind continue];
}

This means that it translates to our original:

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

scope 1 {
    debug x => _1;
    let mut _2: &mut i32;
    scope 2 {
        debug y => _2;
        let _3: &i32;
        scope 3 {
            debug z => _3; // NOT OK! mutable & immutable borrows exist simultaneously
        }
    }
}

Which is buggy since z is a immutable borrow but in that scope, the scope of mutable borrow y exists. This violates the shared-xor-mutable rule.

Applying Scoping

Ok, maybe using MIR to explain is unnecessarily verbose.

Let’s make it more readable. Because of NLL, the scoping is as such:

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

{   // compiles
    let mut x = 1;      // x scope start
    let mut y = &mut x; // y scope start and end (since no other use)
    let z = &x;         // z scope start and end (since no other use)
                        // x scope end
}
{   // fail
    let mut x = 1;      // x scope start
    let mut y = &mut x; // y scope start
    let z = &x;         // z scope start and end (since no other use)
    y += 1              // y scope end
                        // x scope end
}

For the failed section, we see clearly that z is stuck between y’s scope. The existence of z violates shared-xor-mutable, therefore it fails the borrow checker.

Now that we know that NLL is a thing, this resolves the main confusion about having compilable programs where it seems that the shared-xor-mutable constraints are violated.

More puzzles for you

To end off, here are some extra puzzles for you to test your understanding of NLL and shared-xor-mutable. Disclaimer: Some of these are generated by LLMs (because I have better things to do) but their answers were tested and reasoned with the author’s human brain and rust compiler.

Enjoy!

0
1
2
3
4

let mut x = 10;
let a = &x;
let b = &mut x;
println!("{}", a);
*b += 1;

0
1
2
3

let mut x = 7;
let y = &mut x;
let x = 42;
println!("{}", x);

0
1
2
3

let mut x = 7;
let mut y = &mut x;
let x = 42;
println!("{}", x);

0
1
2
3
4
5
6
7

let mut val = 3;
{
    let r = &val;
    print!("{},", r);
}
let m = &mut val;
*m += 1;
print!("{}", val);

0
1
2
3

let mut v = vec![1, 2, 3];
let a = &v[0];
v.push(4);
println!("{}", a);

0
1
2
3

let mut v = vec![1, 2, 3];
let a = &v[0];
println!("{a}");
v.push(4);

0
1
2
3
4
5
6
7

let mut v = vec![10, 20, 30];
let first = &v[0];

for i in 1..v.len() {
    v[i] += 1;
}

println!("{}", first);

You have come to the end of the puzzles. Hope you enjoyed your stay!