NLL Limitations and Polonius

Non-lexical lifetimes (NLL) accept most sound code, but a few well-known shapes are still rejected even though they are memory-safe. Recognise them quickly so you do not waste time "fixing" code that is correct in principle: apply the standard workaround and move on.

#Contents

• How NLL decides
• Problem case #3: conditional return of a borrow
• Get-or-insert on maps
• Cursor loops over linked structures
• Borrows that flow into a loop's next iteration
• Two-phase borrows: what is already accepted
• Destructors and liveness
• Polonius status
• How to tell an NLL limitation from a real bug

#How NLL decides

NLL computes, for every borrow, the set of program points where it may still be used ("live"). A conflicting access at a point inside that set is an error. The weakness: when a borrow is returned from the function on some path, its lifetime must cover the entire rest of the function (the caller's region), so NLL treats it as live on every path after the borrow was created, including paths where it was not returned.

The newer analysis, Polonius, tracks which loans flow into which origins along each control-flow path, so it sees that on the non-returning path the loan is dead.

#Problem case #3: conditional return of a borrow

use std::collections::HashMap;

// Rejected today (E0499 on the insert), accepted by Polonius:
//
// fn get_default<'m>(map: &'m mut HashMap<u32, String>, key: u32) -> &'m mut String {
//     match map.get_mut(&key) {
//         Some(v) => v,                       // borrow returned on this path...
//         None => {
//             map.insert(key, String::new()); // ...so it is "live" here too: E0499
//             map.get_mut(&key).unwrap()
//         }
//     }
// }

fn get_default<'m>(map: &'m mut HashMap<u32, String>, key: u32) -> &'m mut String {
    map.entry(key).or_default()
}

The compiler's tell-tale label: "returning this value requires that *map is borrowed for 'm" (or '1). parse_diagnostics reports it as BCK002.

Workarounds, in order:

1. A purpose-built API: entry, get_or_insert_with on Option, Vec::last_mut().unwrap() after a push.
2. Test first, borrow second: if map.contains_key(&k) { return map.get_mut(&k).unwrap(); }. Two lookups, no clone of the key on hits.
3. Return something that is not a borrow: an index, a key, a bool "found".
4. The polonius-the-crab crate, which wraps the pattern in a macro that is sound under today's checker.

#Get-or-insert on maps

With String keys and &str lookups, entry(key.to_owned()) allocates on every call even when the key exists. Options:

use std::collections::HashMap;

fn bucket<'m>(map: &'m mut HashMap<String, Vec<u32>>, key: &str) -> &'m mut Vec<u32> {
    if !map.contains_key(key) {
        map.insert(key.to_owned(), Vec::new()); // allocate only on a miss
    }
    map.get_mut(key).expect("just inserted")
}

hashbrown::HashMap::entry_ref(&str) does a single lookup and clones the key only when inserting.

#Cursor loops over linked structures

Walking a linked list or tree with a &mut cursor and stopping at a node is another case NLL rejects when the loop may return the cursor:

struct Node { value: i32, next: Option<Box<Node>> }

// Rejected (E0499/E0506): `cur` is reassigned while the loan from `cur.next.as_mut()` may be returned.
//
// fn last_mut(mut cur: &mut Node) -> &mut Node {
//     while let Some(next) = cur.next.as_mut() {
//         cur = next;
//     }
//     cur
// }

fn last_mut(mut cur: &mut Node) -> &mut Node {
    while cur.next.is_some() {
        cur = cur.next.as_mut().unwrap(); // test first, then borrow unconditionally
    }
    cur
}

fn find_mut(mut cur: &mut Node, target: i32) -> Option<&mut Node> {
    loop {
        if cur.value == target {
            return Some(cur);
        }
        cur = cur.next.as_deref_mut()?;   // `?` returns None at the end of the list
    }
}

The trick is the same as problem case #3: decide with a check that does not keep a borrow alive, then take the borrow on a path where it is always used.

#Borrows that flow into a loop's next iteration

fn longest<'a>(words: &[&'a str]) -> &'a str {
    let mut best = "";
    for &w in words {
        if w.len() > best.len() {
            best = w;          // fine: `best` holds a borrow of the input, not of a local
        }
    }
    best
}

Errors here usually mean a reference to a value created inside the loop is stored outside it (E0597 "does not live long enough"). Move the owner out of the loop or store owned data:

fn collect_upper(words: &[&str]) -> Vec<String> {
    let mut out = Vec::new();
    for w in words {
        let up = w.to_uppercase();   // owned inside the loop
        out.push(up);                // move it out; a `&up` would die at the end of the iteration
    }
    out
}

#Two-phase borrows: what is already accepted

Some code that looks like it should conflict compiles because of two-phase borrows: the &mut for a method receiver is "reserved" first and only "activated" when the call runs, so the arguments may read the same value.

fn grow(v: &mut Vec<usize>) {
    v.push(v.len());          // OK: `&mut *v` reserved, `v.len()` reads, then push activates
    let n = v[0];
    // v[n % v.len()] += 1;   // E0502: `IndexMut` borrows `*v` before the index reads `v.len()`
    let i = n % v.len();      // compute the index first
    v[i] += 1;
}

Two-phase borrows apply to autoref method calls (v.push(v.len())), not to indexing with IndexMut (v[v.len() - 1] += 1 on a Vec is E0502; compute the index into a local first) and not to an explicit &mut taken into a variable first (let r = &mut v; r.push(v.len()); is E0502).

#Destructors and liveness

NLL ends a borrow at its last use, and dropping a value whose type has a destructor counts as a use. A MutexGuard, Ref, RefMut, Peekable<Iter> or any struct holding a reference with a Drop impl keeps its borrow alive to the end of the scope.

use std::sync::Mutex;

fn total(m: &Mutex<Vec<u32>>) -> u32 {
    let sum = {
        let g = m.lock().unwrap();
        g.iter().sum()          // guard dropped at the end of this block
    };
    m.lock().unwrap().push(sum);
    sum
}

The compiler label is "borrow might be used here, when x is dropped and runs the Drop code". Drop it explicitly (drop(g)) or scope it with a block.

#Polonius status

• Polonius is the reformulated borrow checker (origins as sets of loans, flow-sensitive). A first version runs on nightly with -Zpolonius (the older datalog prototype) / -Zpolonius=next (the in-tree "location sensitive" implementation).
• The Rust project's goal is to stabilise the subset that accepts problem case #3 and the cursor loops above; as of this writing it is not on stable. Do not rely on it for production code; write the workaround.
• When it lands, the workarounds stay correct; they only become unnecessary.

#How to tell an NLL limitation from a real bug

If you are unsure, write the code with indices or owned data first; if that version is obviously correct and the borrowing version is the same logic, it was the limitation.