References and Borrows

A shared clipboard sits in the middle of the kitchen table. Anyone in the house can pick it up and read what is on it. Anyone can take it back to their room and write on it. The one rule the family agreed on, after years of fights, is this — if someone is writing on the clipboard, nobody else can be holding it. Not even to peek. If two people are reading it at the same time, that is fine, because reading does not change a single mark. But the moment one person picks up a pen, every reader has to hand their copy back. This is the entire rule that runs the Rust borrow checker. Many readers, or one writer, never both.

The rule came out of a fight that happened in every C and C++ program for forty years. In 1972 Dennis Ritchie shipped C with raw pointers — any function could be handed the address of a value and read it, write it, or hold onto the address for later. By the mid-1990s the Microsoft and Mozilla codebases had grown to tens of millions of lines of C and C++, and a class of bug called the iterator invalidation bug was eating engineering time. The story was always the same. One thread would be walking a list to print it. Another thread, or even another loop in the same thread, would push something onto the same list. Pushing made the list grow, which forced it to move to a new chunk of memory, which left the first walker pointing at freed memory. The crash was random, the cause was invisible, the fix took a senior engineer a week. Graydon Hoare started Rust at Mozilla in 2006 because Firefox shipped a critical security bug of exactly this shape every few months and the team was tired.

Hoare's idea, which Niko Matsakis turned into the borrow checker by 2014, was to refuse the bug at compile time instead of debugging it at run time. Every value in a Rust program has one owner. When a function needs to look at the value without taking it, the owner hands out a reference — a temporary card that points to the value. Two flavors of card exist. A &T is a look-card. Many can be out at once. A &mut T is an edit-card. Only one can be out at a time, and no look-cards can be out alongside it. The compiler counts the cards in its head every time it reads a function and refuses to build the program if the count ever breaks the rule.

Here is the look-card in code. The function takes a reference to a Vec and reads it. Two callers can hold a look-card to the same Vec at the same moment and nothing goes wrong, because reading does not move the marks on the page.

fn read_clipboard(items: &Vec<i32>) {
    print!("  reader sees [");
    for (i, n) in items.iter().enumerate() {
        if i > 0 {
            print!(" ");
        }
        print!("{n}");
    }
    println!("]");
}

The edit-card looks almost the same, except the &mut lets the function reach in and change values. The owner has to mark the original let with mut before they will hand out an edit-card at all, which is Rust's way of making mutation visible from a mile away. While that one edit-card is out, the owner cannot read the value themselves, cannot hand out a look-card to anyone else, and cannot hand out a second edit-card. The clipboard is in the editor's hands and the room is silent.

fn double_each(items: &mut Vec<i32>) {
    for n in items.iter_mut() {
        *n *= 2;
    }
}

The bug Hoare built Rust to kill is the one where a single loop tries to read and write the same Vec at the same time. Imagine you want to walk a list of numbers and, for every number bigger than five, push the same number onto the end. The naive code looks like this — for n in &nums { if *n > 5 { nums.push(*n); } }. The for loop holds a look-card on nums for the entire walk. The push call needs an edit-card. Two cards out at once, one look and one edit, and the compiler stops you cold before the program ever runs. In C++ this loop compiles, runs, then crashes the third time you hit it in production at 3am.

The fix is to never hold both cards at the same moment. Walk the list with the look-card, write down what you want to add into a separate Vec, hand the look-card back, then take an edit-card and push everything in one pass. Two phases, no overlap.

fn copy_big_then_push(items: &mut Vec<i32>, threshold: i32) {
    let mut to_add: Vec<i32> = Vec::new();
    for n in items.iter() {
        if *n > threshold {
            to_add.push(*n);
        }
    }
    for n in to_add {
        items.push(n);
    }
}

Pull it all together in main and watch the clipboard get passed around. Two readers borrow at once. One writer borrows alone. The illegal overlap gets named and skipped. The legal fix runs and the clipboard grows.

fn main() {
    let mut nums = vec![1, 2, 3, 4, 5];
    println!("clipboard starts: {:?}", nums);

    println!();
    println!("step 1 -- two readers borrow at the same time");
    let look_a = &nums;
    let look_b = &nums;
    read_clipboard(look_a);
    read_clipboard(look_b);
    println!("  both look-cards handed back");

    println!();
    println!("step 2 -- one writer borrows alone");
    double_each(&mut nums);
    println!("  writer handed back: {:?}", nums);

    println!();
    println!("step 3 -- naive scan-and-push would alias");
    println!("  for n in &nums {{ if *n > 5 {{ nums.push(*n); }} }}");
    println!("  the compiler refuses: one reader, one writer, same moment");

    println!();
    println!("step 4 -- copy first, mutate second, no overlap");
    copy_big_then_push(&mut nums, 5);
    println!("  clipboard now: {:?}", nums);

    println!();
    println!("borrow timeline (lower line = later moment):");
    println!("  t1  [&nums]----[&nums]                          two readers ok");
    println!("  t2                       [&mut nums]            one writer ok");
    println!("  t3  [&nums]------------[&mut nums]   ILLEGAL    reader + writer overlap");
    println!("  t4  [&nums----][&mut nums----]                  sequential, legal");
}

clipboard starts: [1, 2, 3, 4, 5]

step 1 -- two readers borrow at the same time
  reader sees [1 2 3 4 5]
  reader sees [1 2 3 4 5]
  both look-cards handed back

step 2 -- one writer borrows alone
  writer handed back: [2, 4, 6, 8, 10]

step 3 -- naive scan-and-push would alias
  for n in &nums { if *n > 5 { nums.push(*n); } }
  the compiler refuses: one reader, one writer, same moment

step 4 -- copy first, mutate second, no overlap
  clipboard now: [2, 4, 6, 8, 10, 6, 8, 10]

borrow timeline (lower line = later moment):
  t1  [&nums]----[&nums]                          two readers ok
  t2                       [&mut nums]            one writer ok
  t3  [&nums]------------[&mut nums]   ILLEGAL    reader + writer overlap
  t4  [&nums----][&mut nums----]                  sequential, legal

The four rows at the bottom are the borrow timeline. Row t1 shows two look-cards alive on the same line of time, which the compiler allows. Row t2 shows one edit-card alone, which the compiler allows. Row t3 shows a look-card and an edit-card overlapping in the same instant, which is the line the compiler refuses to cross. Row t4 is the fix — the look-card finishes before the edit-card starts, so the moments touch but never overlap. Every Rust program is a careful arrangement of these four shapes, and the borrow checker reads your code like a librarian counting cards at the door.

There is one wrinkle worth knowing about. A reference is only useful for as long as the value it points to exists. Hand someone a card pointing at a piece of paper, then burn the paper, and the card is now a lie. The compiler refuses to let that happen, but the rule it uses to track how long each card stays valid is its own topic — lifetimes — and that is the next lesson.