🎬 Rust Ownership in 30 seconds Visual walkthrough of ownership, moves, and automatic memory management.

📝 Text version (for readers / accessibility)

• Each value in Rust has exactly one owner — when the owner goes out of scope, the value is dropped

• Assignment moves ownership by default; the original binding becomes invalid

• Borrowing (&T / &mut T) lets you reference data without taking ownership

• The compiler enforces: many shared references OR one mutable reference, never both

• No garbage collector needed — memory is freed deterministically at scope exit

547: Polonius Borrow Checker Concepts

Difficulty: 5 Level: Advanced The next-generation borrow checker that eliminates false positives in NLL.

The Problem This Solves

Rust's current borrow checker (NLL — Non-Lexical Lifetimes) is conservative. In some cases it rejects code that is actually safe. The most famous example is the "get-or-insert" pattern: you try to look up a key in a map, and if it's missing, insert a default. The match arm that found the value holds a borrow, but the arm that didn't find it (and therefore wants to mutate the map) shouldn't need to hold that borrow. NLL can't see the difference. Polonius can. Polonius is a new analysis algorithm based on a richer model of "where does this value come from?" rather than "when is this borrow live?" It can prove that the borrow from a successful `get()` doesn't flow into the `None` branch, so the map can be mutated there safely. Until Polonius ships in stable Rust, you work around NLL's conservatism using patterns like the Entry API (`map.entry(key).or_insert(...)`) or splitting the logic into index-based two-pass operations. Knowing why NLL rejects certain code — and that Polonius would accept it — is essential for designing APIs and choosing workarounds that preserve intent.

The Intuition

NLL thinks in terms of time: "this borrow was created here and is live until here." Polonius thinks in terms of data flow: "this returned value originates from this input." The `None` branch never touches the value that `Some(v)` returned, so the borrow that produced `v` simply doesn't exist in that branch under Polonius's model. Two-phase borrows (already in stable Rust) are a partial version of this idea: the outer mutable borrow is "reserved" while an inner shared borrow completes, enabling `v.push(v.len())` to compile.

How It Works in Rust

1. NLL limitation — `match map.get(&key) { Some(v) => v, None => { map.insert(...); ... } }` is rejected even though the borrow only matters in the `Some` arm. 2. Entry API workaround — `map.entry(key).or_insert_with(|| ...)` is the idiomatic stable solution; it encapsulates the get-or-insert in a single operation. 3. Index-based workaround — compute the index first (`v.iter().position(...)`), then index into `v` with `&mut v[i]`; NLL accepts this because no borrow straddles the mutation. 4. Two-phase borrows — `v.push(v.len())` compiles on stable because the inner `v.len()` is a shared borrow inside a "reserved" mutable borrow. 5. Flow-sensitive — branching code where one arm borrows and the other mutates can compile when NLL can prove the borrows don't overlap.

What This Unlocks

Understand why Rust rejects certain obviously-safe patterns and reach for the right workaround.
Recognize the boundary between NLL limitations and actual unsafety.
Write forward-compatible code that will compile without changes when Polonius lands in stable.

Key Differences

Concept	OCaml	Rust
Borrow model	No borrow checker; GC handles aliasing	NLL: borrow liveness ranges; Polonius: data-flow origins
Get-or-insert	Natural expression; GC prevents dangling	NLL rejects; Entry API or index workaround needed
Mutation in match arms	Allowed freely	NLL: conservative; Polonius: branch-aware
Two-phase borrows	N/A	Stable in NLL: inner shared borrow inside reserved `&mut`

//! # 547. Polonius Borrow Checker Concepts
//! Patterns where current NLL is too conservative vs Polonius.

use std::collections::HashMap;

/// Classic Polonius example: get-or-insert
/// NLL rejects this; Polonius accepts it
/// We show the workaround for stable Rust
fn get_or_insert_nll<'a>(
    map: &'a mut HashMap<String, String>,
    key: String,
) -> &'a str {
    // NLL-friendly version — check then insert
    if !map.contains_key(&key) {
        map.insert(key.clone(), format!("default_{}", key));
    }
    map.get(&key).unwrap()
}

/// The version NLL rejects (but Polonius accepts):
/// fn get_or_insert_polonius<'a>(map: &'a mut HashMap<String, String>, key: String) -> &'a str {
///     match map.get(&key) {  // borrows map as &'a
///         Some(v) => v,      // returns &'a str
///         None => {
///             map.insert(key.clone(), "default".to_string()); // ERROR: map still borrowed!
///             map.get(&key).unwrap()
///         }
///     }
/// }
/// 
/// With Polonius: the borrow from `map.get()` doesn't reach the `None` arm,
/// so inserting there is fine. NLL is too conservative here.

/// Entry API — the idiomatic workaround
fn get_or_insert_entry<'a>(
    map: &'a mut HashMap<String, String>,
    key: String,
) -> &'a str {
    map.entry(key).or_insert_with(|| "default_value".to_string())
}

/// Another Polonius pattern: conditional return with otherwise-mut
fn find_or_last<'a>(v: &'a mut Vec<i32>, target: i32) -> &'a mut i32 {
    // NLL struggles here — workaround: use index
    let pos = v.iter().position(|&x| x == target);
    match pos {
        Some(i) => &mut v[i],
        None    => v.last_mut().unwrap(),
    }
}

/// Two-phase borrows (partial Polonius feature, enabled in NLL)
fn two_phase_example() {
    let mut v = vec![1, 2, 3];
    // Two-phase: &mut v borrow starts "reserved" for the outer call,
    // inner v.len() can still use v as &v
    v.push(v.len() as i32); // works in modern Rust via two-phase borrows!
    println!("two-phase: {:?}", v);
}

/// Flow-sensitive borrow — Polonius understands the branch ends the borrow
fn flow_sensitive(v: &mut Vec<i32>, condition: bool) -> i32 {
    if condition {
        let r = v[0]; // borrow v as &v, read first element
        r             // borrow ends here
    } else {
        v.push(99);   // mutable borrow — valid since condition branch ended
        *v.last().unwrap()
    }
}

fn main() {
    let mut map = HashMap::new();
    let v1 = get_or_insert_nll(&mut map, "hello".to_string());
    println!("v1: {}", v1);
    let v2 = get_or_insert_entry(&mut map, "world".to_string());
    println!("v2: {}", v2);
    println!("map: {:?}", map);

    let mut nums = vec![10, 20, 30, 40, 50];
    let r = find_or_last(&mut nums, 30);
    *r *= 2;
    println!("after find_or_last(30)*2: {:?}", nums);

    let r2 = find_or_last(&mut nums, 99); // not found — use last
    *r2 = 999;
    println!("after find_or_last(99)=999: {:?}", nums);

    two_phase_example();

    println!("flow_sensitive(true): {}", flow_sensitive(&mut vec![1,2,3], true));
    println!("flow_sensitive(false): {}", flow_sensitive(&mut vec![1,2,3], false));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_get_or_insert() {
        let mut m = HashMap::new();
        m.insert("existing".to_string(), "value".to_string());
        let r = get_or_insert_nll(&mut m, "existing".to_string());
        assert_eq!(r, "value");
        let r2 = get_or_insert_nll(&mut m, "new".to_string());
        assert!(r2.starts_with("default_"));
    }

    #[test]
    fn test_find_or_last() {
        let mut v = vec![1, 2, 3, 4, 5];
        let r = find_or_last(&mut v, 3);
        assert_eq!(*r, 3);
    }

    #[test]
    fn test_flow_sensitive() {
        assert_eq!(flow_sensitive(&mut vec![42, 1, 2], true), 42);
    }
}

(* Polonius-style patterns in OCaml — all trivially safe with GC *)
let get_or_insert tbl key default_fn =
  match Hashtbl.find_opt tbl key with
  | Some v -> v
  | None ->
    let v = default_fn () in
    Hashtbl.add tbl key v;
    v

let () =
  let map = Hashtbl.create 4 in
  let v1 = get_or_insert map "key" (fun () -> "new_value") in
  let v2 = get_or_insert map "key" (fun () -> "another") in
  Printf.printf "v1=%s, v2=%s\n" v1 v2;

  (* Pattern that confuses NLL: get-or-insert *)
  let find_or_create arr key value =
    match Array.exists (fun (k, _) -> k = key) arr with
    | true -> arr
    | false -> Array.append arr [| (key, value) |]
  in
  let db = find_or_create [| ("a", 1) |] "b" 2 in
  Array.iter (fun (k, v) -> Printf.printf "%s=%d " k v) db;
  print_newline ()