Two-phase borrows: why v.push(v.len()) compiles

pub fn build_ledger(n: i64) -> Vec<i64>

Build a vector with these four steps, in this order:

1. Start with an empty Vec<i64>.
2. Repeat n times: push the vector's current length. If n <= 0, do nothing in this step.
3. Push the current length once more.
4. Overwrite the last element with the current length.

n = 0  -> [1]
n = 1  -> [0, 2]
n = 2  -> [0, 1, 3]
n = 5  -> [0, 1, 2, 3, 4, 6]
n = -3 -> [1]

Worked example for n = 2: step 2 gives [0, 1], step 3 pushes the length 2 and gives [0, 1, 2], and step 4 replaces the last element with the length, which is now 3, giving [0, 1, 3]. In general, for k = max(n, 0) the result is 0, 1, ..., k - 1 followed by k + 1, so it always has k + 1 elements. Lengths are usize values, so convert them with as i64 before storing them. Every test uses a small n, so the vector size is never a concern.

The starter performs these steps on three lines marked (A), (B) and (C). Line (A) compiles. Lines (B) and (C) are each rejected with error E0502 ("cannot borrow v as immutable because it is also borrowed as mutable"). The point of the exercise is to understand why (A) is accepted, then fix (B) and (C) without changing what the function returns.

The puzzle

Rust's basic borrowing rule says that while a mutable (exclusive) borrow &mut v is in use, no other borrow of v may be used. See aliasing XOR mutability for that rule. Now look at this line:

v.push(v.len());

Vec::push takes &mut self, so the call needs a mutable borrow of v. v.len() takes &self, so it needs a shared borrow of v. Read naively, the two borrows overlap, yet the line compiles. The mechanism that allows it is called a two-phase borrow.

Two-phase borrows

Two-phase borrows were proposed in RFC 2025 and are implemented in the borrow checker. Before they existed, v.push(v.len()) was rejected.

A method call evaluates its receiver first, then its arguments, then makes the call. When the receiver needs &mut self, the compiler inserts the &mut v itself; this is called an autoref. A two-phase borrow splits that inserted &mut v into two phases:

• Reservation. The borrow is created when the receiver is evaluated, but until it is used it is treated like a shared borrow. Other code may read v during this phase. Writing to v or borrowing it mutably is still an error.
• Activation. When the borrow is first used, here when push is actually called, it becomes an ordinary exclusive borrow. Any shared borrow taken during the reservation must have ended by then.

The rustc developer guide explains this with a desugaring like the one below. It is pseudo-code: &two_phase is not real syntax.

let tmp = &two_phase v;   // reservation: acts like a shared borrow
let n = v.len();          // a read during the reservation is allowed
Vec::push(tmp, n);        // activation: tmp is now exclusive

The shared borrow inside v.len() ends when len returns, before activation, so nothing overlaps with the exclusive use. Two examples show the limits of the reservation phase:

// E0499: the argument writes to `v` during the reservation.
v.push({ v.push(1); 2 });

// E0502: `r` is a shared borrow that is still used after the call,
// so it is alive when the mutable borrow activates.
let r = &v;
v.push(r.len());
println!("{}", r.len());

Where two-phase borrows apply

The rustc developer guide lists three places where the compiler creates a two-phase borrow:

1. the autoref for a &mut self method call, as in v.push(v.len());
2. an implicit reborrow of a &mut variable passed as a function argument, as in g(r, r.len()) where r: &mut Vec<i64> and g takes &mut Vec<i64> first;
3. the implicit borrow of the left operand in an overloaded compound assignment such as w += w.get(), where w's type implements AddAssign.

Borrows created anywhere else are ordinary borrows. This explains both failing lines in the starter.

• (B) An &mut written in the source is not two-phase. Vec::push(&mut v, v.len() as i64) calls the same function as v.push(v.len() as i64), but the &mut v is written by hand rather than inserted by an autoref, so it is exclusive from the moment it is created. The argument v.len() then reads v while that exclusive borrow is alive: E0502. The same applies to writing g(&mut *r, r.len()) instead of g(r, r.len()).
• (C) Overloaded indexing is not two-phase. For a Vec, v[i] = x calls IndexMut::index_mut(&mut v, i) and writes through the returned reference. In v[v.len() - 1] = ..., the mutable borrow for index_mut is taken before the index v.len() - 1 is computed, and indexing is not one of the three places listed above, so the read in the index is E0502. Built-in indexing of arrays and slices does not go through IndexMut, and v[v.len() - 1] = 7 compiles when v is an array or a &mut [i64].

One similar-looking line does compile: v[0] = v.len() as i64;. This has nothing to do with two-phase borrows. In an assignment place = value, Rust evaluates the right-hand value first and the left-hand place second, so v.len() has finished before index_mut borrows v. In line (C) the read of v is inside the place itself, so evaluation order does not help.

How to fix it

Two-phase borrows explain why some lines compile. They are not a rule to design code around. The Rust Reference does not specify them in detail, so the compiler's documentation is the main description of the current behavior.

When a line is rejected like this, compute the value into a local variable first. A usize result such as v.len() does not keep v borrowed, so the shared borrow ends before the mutable one begins. For line (C) the compiler's E0502 diagnostic suggests the same approach ("try adding a local storing this", pointing at v.len()). Hoisting the whole index works too:

let last = v.len() - 1;
v[last] = v.len() as i64;

Line (B) can be fixed the same way, or by writing it with method-call syntax.

Your submission must compile, pass the tests and pass cargo clippy -- -D warnings.