FerrousPath

Level 5 · Research· Lesson 2 of 9 · 45 min

Inside the borrow checker: NLL and Polonius

MIR, liveness and region inference in non-lexical lifetimes, two-phase borrows, and the loan-based reformulation known as Polonius.

The borrow checker is a static analysis with a precise specification. Understanding that specification turns error messages from oracle pronouncements into derivable facts — and it is the prerequisite for reading any research on Rust’s type system.

The compilation target: MIR

Borrow checking runs on MIR, the mid-level intermediate representation: a control-flow graph whose basic blocks contain simple statements over places (x, x.f, *x, x[i]) and end in a terminator (goto, switch, call, drop, return).

fn first_or_insert(v: &mut Vec<i32>) -> &mut i32 {
    if v.is_empty() {
        v.push(0);
    }
    &mut v[0]
}

fn main() {
    let mut v = vec![];
    *first_or_insert(&mut v) += 5;
    println!("{v:?}");
}

On the Rust Playground, the Show MIR tool prints the MIR for any program; locally use cargo rustc -- -Zunpretty=mir on nightly. Look for: explicit temporaries _1, _2…, StorageLive/StorageDead markers, explicit drop terminators, and reborrows such as _5 = &mut (*_1).

MIR is the right level for the analysis because every implicit thing — autoref, temporaries, drop order, two branches of a match — has become explicit.

What must be proven

A loan is created by each borrow expression &'r p or &'r mut p. The checker must show, for every program point:

  1. No access to a place conflicts with a loan that is live at that point. Reading conflicts with a live mutable loan of an overlapping place; writing, moving or mutably borrowing conflicts with any live loan of an overlapping place.
  2. No loan outlives the storage of its place (no dangling references).
  3. Moves are tracked: no use of a moved-out or uninitialised place (a separate dataflow pass).

Everything hinges on the definition of live loan.

Non-lexical lifetimes (RFC 2094)

Before 2018 a reference’s lifetime was a lexical scope. NLL redefined it:

A lifetime is a set of points in the control-flow graph.

The algorithm:

1. Liveness. Compute, by a standard backward dataflow analysis, where each variable is live (may be used later). If a variable is live at point P, every region appearing in its type must contain P.

2. Subtyping constraints. Each assignment, call and return generates constraints between regions. Assigning a &'a T to a place of type &'b T requires 'a: 'b at that point — the source must outlive the destination. Variance (Level 4) determines which constraints a compound type generates.

3. Reborrow constraints. &'r mut *q where q: &'q mut T adds 'q: 'r, with supporting-prefix rules for nested dereferences.

4. Solve. Start each region empty and grow it to the least fixed point satisfying all constraints: if 'a: 'b, every point in 'b must be in 'a.

5. Check. A loan with region 'r is live at every point in 'r. Walk the MIR; report an error at any access that conflicts with a live loan.

fn main() {
    let mut data = vec![1, 2, 3];
    let first = &data[0];      // loan L1 of `data`, region 'r
    println!("{first}");       // last use of `first`: 'r ends here (liveness)
    data.push(4);              // mutable access to `data`: L1 is not live → accepted
    println!("{data:?}");
}

Under lexical lifetimes 'r would extend to the closing brace and the push would be an error.

Two-phase borrows

vec.push(vec.len()) desugars to: take &mut vec, then evaluate the argument (which reads vec), then call. A naive reading rejects it. Two-phase borrows treat an autoref’d &mut as reserved (acting like a shared borrow) until the call actually activates it.

fn main() {
    let mut v = vec![1, 2, 3];
    v.push(v.len()); // reserve &mut v, read v.len(), then activate
    println!("{v:?}");
}

This small feature has surprisingly deep consequences for the aliasing models in the next lesson — Tree Borrows models reservation directly.

Where NLL is too strict

Region constraints in NLL are location-insensitive: 'a: 'b holds everywhere or nowhere. That rejects a well-known sound pattern, “Problem case #3” from the RFC:

use std::collections::HashMap;

fn get_or_insert(map: &mut HashMap<u32, String>, key: u32) -> &String {
    match map.get(&key) {
        Some(value) => value,          // returned: this loan must live for the whole signature lifetime
        None => {
            map.insert(key, String::new()); // ❌ NLL: error[E0502], `map` is still borrowed here
            &map[&key]
        }
    }
}

fn main() {
    let mut m = HashMap::new();
    println!("{:?}", get_or_insert(&mut m, 1));
}

In the Some arm the loan from map.get flows into the return value, so its region must include the entire rest of the function on that path. NLL has one region, so the loan is considered live in the None arm too, and map.insert conflicts. Run the example: stable Rust 1.100, which this lesson was checked against, rejects it with E0502. A compiler that accepts it is using Polonius-style analysis. (The universal workaround is the entry API, or checking contains_key first.)

Polonius

Polonius (Matsakis, 2018) reformulates the analysis. The key change of perspective:

A region is not a set of points. It is an origin: a set of loans that a reference might have come from.

The question is no longer “at which points is this reference valid?” but “which loans might this reference contain here?” The analysis is naturally expressed as Datalog. Input facts are extracted from MIR:

loan_issued_at(Origin, Loan, Point)      // a borrow expression creates Loan, placing it in Origin
subset_base(Origin1, Origin2, Point)     // subtyping at Point: Origin1's loans flow into Origin2
origin_live_on_entry(Origin, Point)      // some live variable's type mentions Origin
loan_killed_at(Loan, Point)              // the borrowed path is overwritten
loan_invalidated_at(Loan, Point)         // an access here would violate Loan
cfg_edge(Point1, Point2)

and the core rules (the “naive” variant) are:

// Subset relations hold at the point they are introduced, are transitive,
// and propagate along CFG edges only while both origins are live.
subset(O1, O2, P) :- subset_base(O1, O2, P).
subset(O1, O3, P) :- subset(O1, O2, P), subset(O2, O3, P).
subset(O1, O2, Q) :- subset(O1, O2, P), cfg_edge(P, Q),
                     origin_live_on_entry(O1, Q), origin_live_on_entry(O2, Q).

// Which loans does each origin contain at each point?
origin_contains_loan_on_entry(O, L, P) :- loan_issued_at(O, L, P).
origin_contains_loan_on_entry(O2, L, P) :- origin_contains_loan_on_entry(O1, L, P), subset(O1, O2, P).
origin_contains_loan_on_entry(O, L, Q) :- origin_contains_loan_on_entry(O, L, P), cfg_edge(P, Q),
                                          !loan_killed_at(L, P), origin_live_on_entry(O, Q).

// A loan is live if some live origin contains it.
loan_live_at(L, P) :- origin_contains_loan_on_entry(O, L, P), origin_live_on_entry(O, P).

// An error is an invalidation of a live loan.
errors(L, P) :- loan_invalidated_at(L, P), loan_live_at(L, P).

Because subset is indexed by point and propagates along edges only while the origins are live, the relation established in the Some arm above never reaches the None arm. The program is accepted.

Polonius is strictly more permissive than NLL and accepts no unsound program (it is the same soundness argument with a finer analysis). It also aligns the implementation with formal models — Oxide’s provenances are sets of loans — and gives a cleaner foundation for future features such as self-referential borrows.

Status. The original Datalog implementation was too slow for production. The compiler team has been re-implementing the analysis inside rustc’s own dataflow framework, with a location-sensitive pass enabled on nightly through -Zpolonius. Whether it is on by default depends on the version you are running — check the project’s tracking issue and the release notes for your toolchain rather than trusting any tutorial, including this one.

What the borrow checker does not do

  • It is intraprocedural. Each function is checked against the signatures of the functions it calls. That is why lifetime annotations exist, and why changing a function body can never break a caller.
  • It reasons about places, not values: a.x and a.y are disjoint, but v[i] and v[j] are not distinguished, and neither are two method calls that touch different fields.
  • It does not reason about values of conditions: a borrow under if flag conflicts with a use under if !flag.
  • It is sound but incomplete: every accepted program is free of the errors it targets (given sound unsafe code); many safe programs are rejected.

Reading list

  1. RFC 2094, “Non-lexical lifetimes” — unusually readable; contains the full algorithm.
  2. Matsakis, “An alias-based formulation of the borrow checker” (blog, 2018) — the introduction of Polonius.
  3. The Polonius book and the polonius-engine repository.
  4. The rustc dev guide, chapters on MIR and on the borrow checker.
  5. Weiss et al., “Oxide: The Essence of Rust”.
  6. Stjerna, “Modelling Rust’s Reference Ownership Analysis Declaratively in Datalog” (MSc thesis, 2020).

Exercises

  1. Print the MIR for first_or_insert. Identify each loan, the reborrow that produces the returned reference, and the drop terminators.
  2. By hand, compute NLL regions for a five-line function with one shared borrow, one use, and one mutation. Then move the use after the mutation and locate the conflicting point.
  3. For the get_or_insert example, write out the Polonius facts for the two arms informally and show why loan_live_at does not hold at the insert.
  4. On nightly, compile the example with and without -Zpolonius and compare.
  5. Find a sound program that both NLL and Polonius reject because the checker reasons about places rather than values. Explain what additional analysis would be needed to accept it.

Check your understanding

Pick an answer to see the explanation.

  1. 1.On what representation does the borrow checker run?

  2. 2.In NLL, what is a lifetime (region)?

  3. 3.What does Polonius track that location-insensitive NLL does not?

Key terms in this lesson

Finished the lesson and the exercises?