Non-Lexical Lifetimes (NLL) & Control Flow Graph Analysis

In early versions of Rust, lifetimes were strictly tied to the lexical curly-brace blocks ({ ... }) of the Abstract Syntax Tree. This produced frustrating false-positive compiler rejections even when code was completely memory safe.

With the introduction of Non-Lexical Lifetimes (NLL), the borrow checker shifted from analyzing static syntax blocks to analyzing the Control Flow Graph (CFG) of Mid-Level Intermediate Representation (MIR).

1. The Lexical Scope Limitation#

Under old lexical borrow checking, a reference remained active until the closing curly brace } of its enclosing block, even if it was never touched again:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn main() {
    let mut data = vec![1, 2, 3];

    // Reference 'slice' borrows 'data'
    let slice = &data[0];
    println!("First element: {}", slice); 
    // Under old lexical rules: 'slice' lived until the end of main()!
    // Calling data.push(4) here was an ERROR!

    // Under Non-Lexical Lifetimes (NLL):
    // 'slice' is never used again after the println! statement.
    // The borrow checker ends the lifetime immediately right here:
    data.push(4); // Perfectly VALID in modern Rust!
}

2. Formal Mechanics: CFG Liveness Sets#

Let $CFG = (N, E)$ represent the program control flow graph consisting of basic blocks $N$ and directed control flow edges $E$.

A variable $x$ is defined as live at point $p \in N$ if there exists an execution path starting at $p$ that leads to a future use of $x$ without intermediate reassignment or drop. The NLL region $R_{\text{NLL}}(x)$ is defined as the set of program points where $x$ is live:

A borrow violation occurs if and only if an invalidating action (such as mutating data while an immutable borrow exists) occurs at a program point $p \in R_{\text{NLL}}(\text{borrow})$.

3. The 4-Stage MIR NLL Pipeline#

The modern rustc borrow checking engine operates through four rigorous stages:

4. Real-World Ergonomics: Hash Map Entry#

The power of NLL is readily apparent in common collection patterns like checking and inserting into a HashMap:

1
2
3
4
5
6
7
8
9
10
11
12
13
use std::collections::HashMap;

fn process_cache(cache: &mut HashMap<String, u32>, key: String) -> u32 {
    // Under lexical lifetimes, borrowing from cache in 'get'
    // would lock the entire cache for the rest of the function!
    if let Some(&val) = cache.get(&key) {
        return val;
    }

    // With NLL, the borrow from cache.get() dies before this line!
    cache.insert(key, 100);
    100
}

5. Concept Verification#

Test your understanding of Non-Lexical Lifetimes and Control Flow Graph analysis: