Beyond NLL: 5 Surprising Truths About Polonius, Rust’s Next-Gen Borrow Checker

Discover how Polonius solves Rust's false-positive borrow errors using Datalog and loan origins. Learn 5 surprising truths about Rust's next-gen borrow checker.

Beyond NLL: 5 Surprising Truths About Polonius, Rust’s Next-Gen Borrow Checker

Key Takeaways (Quick Summary)

  • Solves the Conditional Return Paradox: Polonius eliminates "Problem Case #3", allowing developers to mutate a container in one conditional branch even if a reference was returned in another.
  • The 60% Short-Circuit Rule: Empirical research on over 3 million Rust functions reveals that 60% create no references and 47% have no loans, allowing a hybrid compiler pass to bypass heavy analysis for most code.
  • Flashlights vs. Permission Slips: Polonius shifts the borrow checker's paradigm from NLL's "sets of points in a Control-Flow Graph" (flashlights) to origin-based "sets of loans" (permission slips).
  • Declarative Datalog Core: By replacing tedious manual graph traversals with Datafrog-backed Datalog rules, Polonius treats borrow checking as a logic problem solved via fixpoint iteration.
  • Minimal Performance Cost: Despite initial prototypes being up to 5,000x slower, modern optimizations have brought average compile-time regressions down to just 1.4%.

Every Rust developer has hit the dreaded "False Positive" wall. It is that frustrating moment when you write code that is clearly safe—logical, sound, and free of data races—yet the compiler rejects it with a cryptic borrow checker error.

Despite the massive ergonomics leap brought by Non-Lexical Lifetimes (NLL) in Rust 2018, certain safe patterns remain "hard nuts to crack." To solve these remaining edge cases, the Rust core team spun off a research project called Polonius. Polonius is not just a patch; it is a fundamental rethink of how the compiler tracks the life of a loan.

Featured Snippet Bait: Polonius is Rust's next-generation borrow checker designed to eliminate Non-Lexical Lifetimes (NLL) false positives, such as conditional return borrow errors. Formulated declaratively in Datalog using the Datafrog engine, Polonius replaces continuous control-flow graph lifetimes with loan origins and subset relationships. This flow-sensitive approach validates safe borrowing patterns while incurring an average compile-time regression of only 1.4%.

1. It Solves the "Conditional Return" Paradox (Problem Case #3)

The most famous limitation of the current borrow checker occurs when you attempt to return a reference from one conditional branch while performing a separate action in another. Under NLL, returning a reference inside a Some match arm forces that loan to lock the entire structure for the rest of the function—even along the None execution path where the reference was never created.

Consider this classic HashMap pattern that fails on stable Rust today:

fn get_default<'r, K, V: Default>(map: &'r mut HashMap<K, V>, key: K) -> &'r mut V {
    match map.get_mut(&key) { 
        Some(value) => value,              
        None => {                          
            map.insert(key, V::default()); 
            // ERROR: map is still considered borrowed here!
            map.get_mut(&key).unwrap()     
        }                                  
    }                                      
}

NLL rejects this because it cannot distinguish that the mutable loan of map in the Some path should not affect the None path. Polonius uses a flow-sensitive analysis to evaluate execution paths on a case-by-case basis. It understands that if execution flows through the None path, the initial borrow is dead, making it completely safe to call map.insert(...).

As the Polonius development team noted regarding this long-standing issue:

"Fixing this borrowck issue requires more precision about flow-sensitivity. It also hints at limitations in our modeling of lifetimes... Issues like 'NLL problem case #3', issue #47680 and others, were therefore deferred from NLLs, and left as future work, Polonius."

2. The "60% Rule": Most Functions Are Surprisingly Simple

When discussing borrow checker complexity, we tend to focus on dense concurrent code and intricate graph structures. However, large-scale empirical data shows that the average Rust function is surprisingly simple from a memory ownership standpoint.

A landmark study led by Albin Stjerna analyzed over 20,000 Rust repositories—encompassing more than 3 million functions. The findings contained a major revelation for compiler performance:

  • 60% of all functions do not create any references whatsoever.
  • 47% of functions contain zero loans throughout their execution body.
Total Rust Functions Analyzed (~3,000,000)
├── 60% No References Created ──► [ Bypass Polonius Entirely ]
└── 40% Active References
    ├── 47% Total Functions w/ Zero Loans ──► [ Fast Pre-pass ]
    └── Heavy Borrowing Code ───────────────► [ Full Polonius Solver ]

This is incredible news for build performance. It means the compiler can "short-circuit" the analysis for nearly half of all functions in a codebase. By deploying a hybrid mode, the compiler runs a lightweight check first, reserving the full Polonius engine strictly for functions with complex borrowing logic.

"Indeed, surprisingly many functions (circa 60%) actually do not create any references at all, and therefore does not need (most of) the Polonius analysis."

3. Flashlights vs. Permission Slips: The Shift to "Sets of Loans"

Polonius fundamentally changes the internal language rustc uses to reason about memory. To grasp this shift, think of NLL as a flashlight and Polonius as a permission slip.

In the NLL model, a lifetime is defined as a set of points in the Control-Flow Graph (CFG)—like a flashlight illuminating specific lines of code where a reference is active. If your code enters an illuminated line, NLL assumes the borrow is active.

Polonius shifts this model to Origins and Loans:

| Dimension | NLL Model (Old) | Polonius Model (New) | | :--- | :--- | :--- | | Core Concept | Lifetimes as continuous regions | Origins as sets of active loans | | Mental Model | Flashlight illuminating CFG lines | Permission slips traveling with data | | Validation Rule | Region outlives constraint | Subset relationships ($R_1 \subseteq R_2$) | | Precision | Conservative (location-bound) | Flow-sensitive (path-bound) |

Here, the compiler tracks permission slips that travel directly with the data. It does not care which line of code you are executing; it cares which loans (permissions) your reference currently holds. By checking subset relationships ($R_1 \subseteq R_2$) at every instruction, Polonius approves safe reborrows and complex loop assignments that NLL misinterprets.

"The key ideas being: switching from a model of lifetimes as sets of points in the CFG (with outlives relationships), to a model of origins as sets of loans (with subset relationships)."

4. The 1.4% Performance Surprise: Crushing the 5,000x Myth

A common myth in the Rust community is that Polonius is far too slow for real-world production. This rumor originated during early research prototypes, where initial implementations ran up to 5,000x slower than the stable borrow checker.

Thanks to Datafrog—a worst-case optimal Datalog engine embedded in Rust—that performance gap has been virtually eliminated.

Compile-Time Impact Across 20,000 Crates:
┌─────────────────────────────────────────────────────────┐
│ Average Regresson:  1.4%                                │
│ 75th Percentile:    < 2.0%                              │
│ Worst Outlier:      2.5x (Isolated edge cases)          │
└─────────────────────────────────────────────────────────┘

Empirical benchmarks across 20,000 popular crates demonstrate an average compile-time increase of only 1.4%, with 75% of projects experiencing less than a 2% regression. While extreme structural outliers can see regressions up to 2.5x (or 36% in isolated crates), the transition to Polonius will be virtually imperceptible to most developers while delivering massive gains in code expressiveness.

"On the 20,000 most popular crates that were tested the average compile time increase was just 1.4% with 75% of cases seeing less than a 2% regression in compile times."

5. Declarative Logic: Moving Borrow Checking to Datalog

The most radical architectural change in Polonius is the move toward declarative compiler design.

Stabilizing NLL was a tedious, painstaking process because developers had to manually write procedural graph-traversal algorithms and handle edge-case regressions one by one. Polonius replaces these manual graph searches with Datalog logic rules.

During compilation, rustc lowers code into Mid-Level Intermediate Representation (MIR) and emits simple relational facts:

// A MIR-style relational fact generated for Polonius
// Represents: _1 = _2 (Variable 1 assigned value of Variable 2 at point P)
assign(_1, _2, point_index).

A logic engine evaluates these facts against declared borrowing rules. If a bug or unsoundness edge case is discovered, compiler engineers do not need to rewrite complex graph traversal passes—they simply update a Datalog rule. This fixpoint-solving architecture makes Rust's safety guarantees far easier to formally verify and maintain.

"The intention was to use Datalog to allow for a more advanced, flow-sensitive analysis while also allowing for better compile-time performance through the advances done centrally to the fixpoint solving provided by the Datalog engine."

Conclusion: Sculpting Rust's Shiny Future

The roadmap toward Rust 2024 and beyond follows a structured rollout. The core team is currently finalizing a location-insensitive pass—validating global origin rules—before introducing the full location-sensitive pass that permanently solves the conditional return paradox.

As compiler intelligence evolves, Rust is transitioning from a strict gatekeeper into a truly collaborative partner. To quote Michelangelo, as the Polonius team fondly references:

"I saw the angel in the marble and carved until I set him free."

What safe coding patterns are you most excited to unlock once Polonius lands in stable Rust? Let us know in the comments below!

FAQ (Frequently Asked Questions)

:::details How does Polonius fix the HashMap get_default compile error? Under NLL, returning a reference in the Some branch locks the map across the entire match expression. Polonius uses flow-sensitive analysis to recognize that the borrow dies along the None path, allowing map.insert(...) to run safely. :::

:::details Will Polonius make my Rust builds significantly slower? No. Empirical tests across 20,000 crates show an average compile-time regression of only 1.4%. Thanks to Datafrog optimization and hybrid pre-passes, 75% of projects see under a 2% change. :::

:::details What is the difference between lifetime points and loan origins? NLL models lifetimes as physical regions of code (Control-Flow Graph points). Polonius models origins as sets of active loan permissions that travel with variables, evaluating subset relationships ($R_1 \subseteq R_2$) independently of code location. :::