The borrow checker — liveness on the control-flow graph

Lesson 06 defined a borrow's region as the set of points at which the borrow, or anything made from it, may still be used, and then drew it as a stretch of nested blocks. This lesson computes it. Two short programs show that "later in the file" is neither necessary nor sufficient for "later in time", so the function becomes a graph of points and "may still be used" a question about paths: can a path from here reach a use? That is liveness. With it the whole check is one test at one point, an access meeting a loan that is in scope, and every borrow error has the same three points. One exception makes v.push(v.len()) legal, and the price of soundness is a short list of safe programs the test must still refuse.

1 · "Later" is not "below"

The law of Lesson 05 and the region of Lesson 06 lean on one word. A borrow matters while it may still be used; the compiler's third label reads "borrow later used here". The natural reading of "later" is "further down the file", and two short programs show that the reading fails in both directions. In the first, the only use of the borrow is above the write that the compiler objects to:

fn main() {
    let mut log = vec![1];
    let first = &log[0];
    for i in 0..3 {
        println!("{}", first);        // the use is written above the write...
        log.push(i);                  // ...and runs after it, on the next pass
    }
}

Read top to bottom, first is last used on line 5 and the push on line 6 comes after it. The compiler rejects the program, and its third label points up the page:

5 |         println!("{}", first);        // the use is written above the write...
  |                        ----- immutable borrow later used here
6 |         log.push(i);                  // ...and runs after it, on the next pass
  |         ^^^^^^^^^^^ mutable borrow occurs here

The loop is why. The body runs three times, so after the push on line 6 control goes back to line 4 and then to line 5, where the old borrow is used again, after whatever the push did to the vector. In the second program the write is above the use, and the compiler accepts:

fn main() {
    let mut log = vec![1];
    let first = &log[0];
    if log.len() > 1 {
        log.push(2);                  // written above the use...
    } else {
        println!("{}", first);        // ...but no path leads from there to here
    }
}

1

When the test on line 4 is true, control reaches the push and then the end of the function, and first is never used again on that path. When it is false, control reaches the use and the push never happens. No path leads from the push to the use, so the borrow cannot be used after the write. Together the two programs say that the order of the file is neither necessary nor sufficient for "later".

A compiler that trusted the file's order would accept the first program, and C++ shows what that means: a pointer to an element, kept across a call that may reallocate the vector.

std::vector<int> log{1};
const int* first = &log[0];
for (int i = 0; i < 3; i++) {
    std::cout << *first << '\n';     // pass 2 reads the old buffer if push_back moved it
    log.push_back(i);                // the first push does: capacity 1, length 1
}

Built with Apple clang 21 at -Wall -Wextra it compiles without a warning; it printed 1, 2, 1 on this machine, the last two reads being of freed memory, and AddressSanitizer stops it at the second read with heap-use-after-free. So "later" needs a definition that does not mention the page. Later than a point has to mean what can run after it, a fact about paths, and paths live in a graph.

2 · The function as a graph of points

Take a point to be a place in a function's control flow: in this lesson's pictures, a line. Draw an edge from a point to each point that may run right after it. A plain statement has one edge. An if has two, one per branch. The last statement of a loop body has an edge back to the loop's test, and the test has an edge past the loop. A return has none. The result is the function's control-flow graph; the compiler builds one for every function body before it checks anything. The first program of §1 is this graph, by line:

A path is a walk along edges, and later than p now has a definition that does not look at the page: reachable from p by a path. Line 5 is later than line 6, because 6 → 7 → 4 → 5 is a path. In the second program of §1 the use in the else is not later than the push in the then, because no walk along edges leads from one branch to the other.

With the graph in hand the question about a borrow becomes a search: from this point, is there a path that reaches a use of the thing that holds it? The next section makes that search exact.

3 · Liveness: is this name still needed?

A name is live at a point if some path from that point reaches a use of the name before anything overwrites it. The clause about overwriting matters: after r = &b the old value of r is dead even though the name will be used again, because the value that later use reads is the new one. We track liveness for the names that can hold a borrow (references, iterators, structs with a lifetime); an owner such as log holds no loan.

The definition says search forward from p, but it is computed the other way. A use makes a name live at its own point, and a point is live for whatever its successors need, except what it overwrites:

live(p) = used at p ∪ ( live(s₁) ∪ live(s₂) ∪ … − written whole at p ), where s₁, s₂, … are the successors of p

Start with nothing live anywhere and apply the rule to every point, from the last to the first. On straight-line code one sweep settles everything. A loop needs more. On the first program of §1 the sweep reaches line 5 (a use of first), then line 4, which leads to it, but it has visited lines 7 and 6 before line 4 had anything to pass back around the loop. The second sweep carries it over the back edge. The third changes nothing, so the iteration stops:

That is why first is live at the push, a statement that does not mention it. The procedure is a fixed-point iteration: the sets only ever grow and are bounded by the number of names, so it must stop, and the last sweep is the one that finds nothing to change. Nothing in it looks at the order of the text except to choose which point to visit first.

struct Guard<'a>(&'a i32);

impl Drop for Guard<'_> {
    fn drop(&mut self) {}
}

fn main() {
    let guard;
    let n = 5;
    guard = Guard(&n);
}

Liveness answers the question for a name. The law protects a loan, and a loan is held by more names than the one written after let.

4 · From a name to a loan

let first = &scores[0] makes one loan and puts it in first. If first is then copied into shown, the loan is in two names; if a call returns a reference made from it, the result carries it; a for loop over names.iter() keeps it in an iterator the program never names. Whichever name is used later, the loan must still be in force. So the region of a loan is not the liveness of one name; it is the liveness of every name the loan has flowed into.

fn main() {
    let mut scores = vec![90, 72, 85];
    let first = &scores[0];
    let shown = first;                // a copy: the loan is now in `shown` too
    scores.push(60);
    println!("{}", shown);
}

Here first is dead after line 4, which is its last use, and the push comes after that. A check that asked only about the name in the let would accept the program. But shown is live through line 6 and holds the same loan, so the loan is live at the push. The compiler records each flow as an outlives constraint: the region of the loan must contain the region of every name it flows into, written 'loan: 'shown. It collects one for every assignment, reborrow and call, seeds each name's region with the points where the name is live (§3), and propagates along the constraints until nothing grows. This is the solving that Lesson 06 left to this lesson.

The loop is the same story with an unnamed holder. The iterator of for n in names.iter() is used by the test at the top of every pass, so by §3 it is live at every point of the body, and the loan it holds with it: the push in the body is inside the region because the back edge leads to a use of the iterator. This is the iterator invalidation of Lesson 05, derived now instead of observed.

The checker cannot see inside a call. For let t = f(&x) it reads f's signature, never its body, and the signature has to say whether the result is made from the argument. Until Lesson 08 says how, the examples use calls whose result is made from the argument, like &scores[0] and names.iter().

5 · One test at one point

Everything the checker needs is now computed. Each loan is in scope at the points reachable from the borrow at which its region holds, and each point performs effects on places, the read, write and end of Lesson 01. The check is one comparison per pair: if an access at a point overlaps the place of a loan in scope there, and the two are not both reads, the program is rejected, with the code Lesson 05's table assigns to the pair. In full:

1. Build the graph of points for the function (§2).
2. Sweep backwards for liveness to a fixed point (§3).
3. Give each loan the liveness of every name it flows into (§4), and mark the points where it is in scope.
4. At every point, compare each access with each loan in scope there.

Each rejection has the same three points. B is where the borrow is made, A the access the law forbids, and U the later use that keeps the borrow live at A. Along some path B reaches A and A reaches U, and each is necessary: without B there is no loan, without A nothing meets it, and without U the borrow is not live at A and the access is fine (the first program of Lesson 06 §6). The compiler reports the error at A, because A is the act that would cause the undefined behavior, and A is only forbidden because of U.

error[E0502]: cannot borrow `scores` as mutable because it is also borrowed as immutable
 --> src/main.rs:5:5
  |
3 |     let first = &scores[0];
  |                  ------ immutable borrow occurs here
5 |     scores.push(60);
  |     ^^^^^^^^^^^^^^^ mutable borrow occurs here
6 |     println!("{}", shown);
  |                    ----- immutable borrow later used here

Any one of the three edits removes the error, and each has a cost:

fn by_copy(scores: &mut Vec<u32>) {
    let first = scores[0];            // B gone: a copy of the number, no borrow left
    scores.push(60);
    println!("{}", first);
}

fn by_order(scores: &mut Vec<u32>) {
    let first = &scores[0];
    println!("{}", first);            // U moved up: the borrow ends before the push
    scores.push(60);
}

fn by_position(scores: &mut Vec<u32>) {
    scores.push(60);                  // A moved up: the push comes before the borrow
    let first = &scores[0];
    println!("{}", first);
}

The first changes what is stored (a copy, or a .clone() for a type that is not Copy, which costs a copy and can change the meaning); the others change the order of effects. The widget runs the four steps and draws the results.

// 1 · liveness: sweep the points last to first until nothing changes (u = read at i, d = written whole at i)
var changed = true, livePasses = 0, liveSnaps = [];
while (changed) {
  changed = false; livePasses++;
  for (var i = N - 1; i >= 0; i--) {
    if (!reach[i]) continue;
    var out = new Set();
    F.nodes[i].succ.forEach(function (s) { liveIn[s].forEach(function (v) { out.add(v); }); });
    var cur = new Set(usesN[i].u);
    out.forEach(function (v) { if (!usesN[i].d.has(v)) cur.add(v); });
    if (cur.size !== liveIn[i].size) { liveIn[i] = cur; changed = true; }
    else { var same = true; cur.forEach(function (v) { if (!liveIn[i].has(v)) same = false; }); if (!same) { liveIn[i] = cur; changed = true; } }
  }
  liveSnaps.push(liveIn.map(function (st) { return Array.from(st); }));
}

// 2 · a region starts as the points where its name is live, then grows along the outlives constraints
F.locals.forEach(function (l) {
  if (l.rv < 0) return;
  for (var k = 0; k < N; k++) if (reach[k] && liveIn[k].has(l.id)) pts[l.rv][k] = 1;
});
    // … (universal regions: Lesson 08)
changed = true;
var guard = 0;
while (changed && guard++ < 1000) {
  changed = false;
  F.edges.forEach(function (e) {
    var a = pts[e[0]], b = pts[e[1]];
    for (var k = 0; k < N; k++) if (b[k] && !a[k]) { a[k] = 1; changed = true; }
  });
}

// 3 · the law at one point: does this access meet this loan, which is in scope here?
function accessVerdict(F, a, L, nid) {
  var mutNow = L.mut && (!L.twoPhase || F.activeAt[L.id][nid]);
  switch (a.kind) {
    case 'copy': return mutNow ? 'E0503' : null;
    case 'sborrow': return mutNow ? 'E0502' : null;
    case 'reserve': return L.mut ? 'E0499' : null;                          // a reservation may coexist with shared loans, never with an exclusive one
    case 'mborrow': case 'activate': return L.mut ? 'E0499' : 'E0502';
    case 'write': case 'replace': return 'E0506';
    case 'move': return 'E0505';
    case 'drop': case 'sdead': return 'S';
  }
  return null;
}

What to try. Load a use written above the write and move the point from line 4 to line 7: first is live on entry to each of those lines, line 6 too although it never mentions it, and the bar of &log covers lines 3–7. B is line 3, A line 6 and U line 5, above A, and there are 3 sweeps; the straight-line programs take 2, and the extra sweep is what the back edge costs. In a use on the other branch, first is live on entry to lines 4 and 7 only, the bar has a hole at line 5, and the checker accepts. In a copy carries the loan, first is live only on line 4 and shown on lines 5 and 6, but the bar runs to line 6. In a loop keeps its iterator alive, the unnamed iterator is live on entry to lines 3–5 and U is line 3, the loop's own test.

One program in the widget's list, v.push(v.len()), is accepted although the four steps as stated would reject it. The next section finds what lets it through.

6 · Two-phase borrows: an exclusive borrow that starts late

Written out, v.push(v.len()) is Vec::push(&mut v, v.len()), and the receiver is evaluated before the argument. So the exclusive borrow is made first, v.len() reads v while it exists, and the call uses it. By §5 that is an error, and it is what the compiler says about the written-out form:

fn main() {
    let mut v = vec![0, 1, 2];
    Vec::push(&mut v, v.len());
}

error[E0502]: cannot borrow `v` as immutable because it is also borrowed as mutable
3 |     Vec::push(&mut v, v.len());
  |     --------- ------  ^ immutable borrow occurs here
  |     |         |
  |     |         mutable borrow occurs here
  |     mutable borrow later used by call

The three points are all on one line, B and U at the start of the statement and A in its middle. The method-call form is accepted:

fn main() {
    let mut v = vec![0, 1, 2];
    v.push(v.len());                  // the same call, with the borrow made by the method syntax
    println!("{:?}", v);
}

[0, 1, 2, 3]

The difference is how the borrow is made. The exclusive borrow that method syntax inserts is two-phase. Where it is made it is only reserved: until the call it behaves like a shared borrow, so reads are allowed and writes and other exclusive borrows are not. At the call it is activated, and the test of §5 runs again with the borrow exclusive. This is sound because between the two nothing holds the new reference yet, so a read through another name invalidates nothing; a write would fall between the reference's creation and its first use, the pattern the law exists to exclude, and stays refused. A shared borrow that is still live at activation is caught there:

fn main() {
    let mut v = vec![1, 2, 3];
    v.extend(&v);                     // the shared borrow is still live when the call activates
}

The widget's checkbox switches the reservation off: untick two-phase borrows on v.push(v.len()) and it becomes the error above, with B, A and U all on line 3. Only three implicit forms are two-phase: the borrow a method call inserts for a &mut self receiver, the implicit reborrow of an existing &mut passed as an argument, and the borrow of an overloaded compound assignment such as +=. A &mut written in source never is.

Two-phase borrows removed a rejection that protected nothing: the reference could not be observed, so nothing was being kept from it. The rejections in the next section are of another kind: the program is safe, and the test cannot show it.

7 · Sound, therefore incomplete

The test is sound: a program it accepts never has a conflicting access to a place while a loan on it is in scope. The converse does not hold, and cannot. Whether a program is safe is a question about all of its runs, and a checker that always stops cannot answer such questions exactly for every program (the argument behind the halting problem). So a checker that promises soundness must reject some programs that would have run safely, and the design question is which ones: those whose safety rests on a fact the checker does not track. Two such facts have names.

Which path. A loan that flows into a returned reference must be valid for the region the caller chose for that reference, and inside the function that region covers every point of the body, since the caller uses the result after the call. The compiler's analysis does not ask on which path such a constraint was made (as of 2026-09). So a borrow returned on one path is in scope on all of them:

fn first_or_add(names: &mut Vec<String>) -> &mut String {
    let first = &mut names[0];
    if first.len() > 3 {
        return first;                 // on this path the borrow leaves the function
    }
    names.push(String::from("new"));  // on this path `first` is never used again
    &mut names[0]
}

error[E0499]: cannot borrow `*names` as mutable more than once at a time
1 | fn first_or_add(names: &mut Vec<String>) -> &mut String {
  |                        - let's call the lifetime of this reference `'1`
2 |     let first = &mut names[0];
  |                      ----- first mutable borrow occurs here
4 |         return first;                 // on this path the borrow leaves the function
  |                ----- returning this value requires that `*names` is borrowed for `'1`
6 |     names.push(String::from("new"));  // on this path `first` is never used again
  |     ^^^^^ second mutable borrow occurs here

On the path that does not return, first is dead and the program is safe. But the loan flows into the result on the other path, so it is in scope at line 6: the widget's a borrow returned on one path draws the bar over a line where the live column shows only names. The third label is the return, not a use in the body; the loan is live because the caller will use it. This is the shape the NLL proposal called "problem case #3". Stable 1.98.1 rejects it, as the snippet shows. A 2026 project goal aims to stabilise a successor analysis, Polonius Alpha, before the end of the year, and as of 2026-09 it is on by default on nightly. The point does not depend on which checker ships.

use std::collections::HashMap;

fn get_or_insert(map: &mut HashMap<u32, u32>, k: u32) -> &mut u32 {
    match map.get_mut(&k) {
        Some(v) => v,                 // the reference escapes to the caller
        None => {
            map.insert(k, 0);         // but this arm never had one
            map.get_mut(&k).unwrap()
        }
    }
}

use std::collections::HashMap;

fn get_or_insert(map: &mut HashMap<u32, u32>, k: u32) -> &mut u32 {
    map.entry(k).or_insert(0)         // one borrow; the library decides inside
}

Which element. The checker compares places by path: a field is a place of its own, so p.left and p.right may be borrowed at once. An index is a call with a run-time value: names[0] is *IndexMut::index_mut(&mut names, 0), and all the checker knows of that call is a signature saying the result borrows all of names. It cannot know that 0 and 1 differ:

fn main() {
    let mut names = vec![String::from("ada"), String::from("bob")];
    let a = &mut names[0];            // index_mut borrows all of `names`
    let b = &names[1];                // so this read meets that loan
    a.push_str(b);
}

struct Pair {
    left: String,
    right: String,
}

fn main() {
    let mut p = Pair { left: String::from("ada"), right: String::from("bob") };
    let a = &mut p.left;              // a field is a place of its own
    let b = &p.right;                 // and this one is a different place
    a.push_str(b);
    println!("{} {}", p.left, p.right);
}

adabob bob

The repair the compiler suggests is a library call whose signature says what the checker needs to hear, that the two halves are disjoint. Lesson 20 builds it, with the one unsafe block it needs:

fn main() {
    let mut names = vec![String::from("ada"), String::from("bob")];
    let (left, right) = names.split_at_mut(1);   // two slices, disjoint by construction
    left[0].push_str(&right[0]);
    println!("{:?}", names);
}

["adabob", "bob"]

Both rejections turn on a signature. index_mut is declared to borrow all of its receiver, and that is all the checker knows of the call. The result of first_or_add has a region the caller chose, which covers the whole body. Inside one function the checker has the graph; across a call it has only signatures.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

The checker is a procedure over one function's graph, and it costs nothing at run time. Both rejections of §7 turn on signatures: across a call it learns what the callee does only from the callee's signature. If it read bodies, checking a program would mean checking the whole program every time, and an edit deep inside a library could change errors far from it. So the relation between a function's inputs and its output has to be written in the signature, and the caller has to trust it the way it trusts types. When a function takes references and returns one, how does a caller learn which input the result borrows from, and for how long? That is Lesson 08.

Interview prompts

• What does the borrow checker actually compute? (§5 — a control-flow graph; liveness to a fixed point; each loan's region as the liveness of everything made from it; the loans in scope at each point; one test of each access against them.)
• What is liveness, and why is it computed backwards and iterated? (§3 — a name is live where a path reaches a use before an overwrite; uses are the source, so information flows against the edges, and a loop's back edge needs another sweep.)
• Why does a borrow used only above a write in the file still conflict with it? (§1, §2 — "later" means reachable along edges, and a loop's back edge leads from the write to the use on the next pass.)
• In cannot borrow as mutable because it is also borrowed as immutable, what are the three points, and which is reported? (§5 — B the borrow, A the forbidden access, U the later use that keeps it live; the error is reported at A.)
• Why does v.push(v.len()) compile while Vec::push(&mut v, v.len()) does not? (§6 — method syntax makes a two-phase borrow, reserved like a shared borrow until the call activates it; a written &mut is exclusive from the start.)
• Give a safe program the checker rejects, and say why a smarter check is not free. (§7 — &mut names[0] with &names[1], or a borrow returned on one path; telling them apart needs reasoning about values or paths, no longer a fast check per function.)

Companion reads: C++ · 13 STL containers (iterator invalidation, unchecked), C++ · 19 Undefined behavior, and C++ · 03 Pointers and references.