NLL Problem Case #3, the entry API, and the limits of today's checker

pub fn word_counts(words: &[String]) -> Vec<(String, i64)>

// mandated helper — keep this signature
fn bump<'m>(map: &'m mut HashMap<String, i64>, key: &str) -> &'m mut i64

Count how many times each word appears, and return the pairs sorted by count descending, then key ascending. Comparison is exact and case-sensitive; "Ap" and "ap" are different words.

[]                    -> []
["a","b","c"]         -> [("a",1),("b",1),("c",1)]
["x","x","x"]         -> [("x",3)]
["b","a","b"]         -> [("b",2),("a",1)]
["z","y","z","y","q"] -> [("y",2),("z",2),("q",1)]     <- tie broken by key

bump must return an exclusive reference to the counter for key, inserting a zero counter if the key is not there yet. The obvious implementation is given in the starter. It does not compile, and it is not your fault.

The honest answer to “is the borrow checker ever just wrong?”

Here is the starter’s bump:

match map.get_mut(key) {
    Some(v) => v,                        // borrow #1
    None => {
        map.insert(key.to_string(), 0);  // error[E0499]: second mutable borrow
        map.get_mut(key).unwrap()
    }
}

Trace it by hand. On the None arm, get_mut returned nothing, so there is no reference to anything. The borrow it took is dead. Reborrowing the map is obviously fine.

The compiler rejects it anyway, and this is not a case where you are missing something. This is NLL Problem Case #3, named in RFC 2094 in 2017, documented, acknowledged, and still rejected in 2026.

Why: today’s borrow checker computes, for each loan, a region — a set of program points where it is live — and the return value of get_mut is tied to a loan whose region must cover every point where the function’s return value could be used. Because one arm of the match returns that reference, the region is forced to extend to the end of the function, on all paths, including the None arm where the reference does not exist. The analysis is flow-sensitive about where borrows end; it is not flow-sensitive enough about a borrow whose result flows into a return value on only some paths.

So the model to carry away is: the checker is incomplete, not unsound. It rejects some correct programs. It never accepts an incorrect one. Learners told “the compiler is always right” build a much less durable model than learners told “the compiler is a conservative prover with one famous known gap, and here it is”.

The fix, which is also the best HashMap idiom in the language

map.entry(key.to_string()).or_insert(0)

entry performs one lookup and returns an Entry — a value that owns the right to occupy that slot, whether or not something is there yet. or_insert turns it into a &mut V, filling the slot first if it was vacant.

One lookup, one borrow, one exit path. The pattern that defeated the checker never arises, because the “is it there?” question and the “give me a mutable reference” question are answered by a single operation instead of two.

This is item 3.16’s thesis again: the API’s signature encodes the proof the checker could not construct. Somebody wrote it down once.

The Entry family is worth knowing beyond or_insert:

• or_insert_with(|| expensive()) — lazily builds the default only when vacant. Use it whenever the default is not free; or_insert(vec![]) allocates on every call, and clippy’s or_fun_call will say so.
• or_default() — for V: Default.
• and_modify(|v| *v += 1).or_insert(1) — the counting idiom in one expression.

Clippy is actively pushing you here: map_entry (style, warn-by-default) fires on the if !map.contains_key(k) { map.insert(...) } shape and tells you to use entry. It is pattern-sensitive and does not catch every variant, so do not treat its silence as approval.

The randomised-iteration trap

HashMap iteration order is randomised by design — Rust seeds its hasher per-process specifically to make hash-flooding attacks impractical, and the documentation explicitly refuses to guarantee any order. Two runs of the same binary on the same input will emit the map in different orders.

So a solution that iterates the map and emits pairs in whatever order they come out will pass sometimes and fail sometimes. Your output must be totally ordered. “Count descending” alone is not a total order — the ties in the test cases would flap. The tie-break on the key is what makes the answer deterministic, and that is why the spec has one.

sort_by with b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)) reads exactly like the specification: compare counts backwards, and if equal, compare keys forwards.

If you ever want ordered iteration for free, BTreeMap gives it to you — sorted by key, O(log n) instead of O(1) lookup, no hashing. It would have been a perfectly good choice here; the sort would still be needed for the count-descending part. (Clippy has an allow-by-default restriction lint, iter_over_hash_type, for codebases that want to ban iterating a HashMap entirely.)

Polonius, precisely

The fix for Problem Case #3 exists and has a name.

Polonius is a reformulation of the borrow checker that computes, for each loan, the set of points where it is live, rather than computing a region per reference — which is exactly the direction of the fix. It accepts Problem Case #3.

Where it actually stands, as of 2026: it is a nightly prototype behind -Zpolonius. It passes crater and the performance suite. There is one open soundness question around dead regions and opaque types. There is an explicit 10–20% compile-time budget for it. Full flow-sensitivity is out of scope for the alpha. Stabilisation is a Rust project goal for 2026, which is a statement of intent, not a shipped feature.

Use entry. Do not write code that depends on Polonius, and do not describe it to anyone as done.

Remember the grade is compile + tests + clippy -D warnings.