The pattern I wanted was the most natural thing in the world, which is usually the warning sign. I was iterating over a Vec of work items, and for some of those items the processing produced more work items that I wanted to add to the same Vec and process in the same loop. A worklist that grows as you chew through it. I've written it in a dozen languages without a thought. Rust stopped me dead.
error[E0502]: cannot borrow `queue` as mutable because it is also borrowed as immutable
And once again my first reaction was that the compiler was being precious, and once again it was protecting me from a bug I'd have shipped.
what the borrow actually conflicts with
Iterating a Vec with for item in &queue holds an immutable borrow of the whole vector for the duration of the loop. Pushing to it needs a mutable borrow. You can't have both at once, and the reason isn't bureaucratic: pushing to a Vec can reallocate its backing buffer, and if it does, the iterator I'm holding is now pointing into freed memory. This is the same class of bug as modifying a list while a Python iterator is walking it, except Python finds out at runtime and Rust finds out at compile time. In C++ it's an invalidated iterator and a segfault on a customer's machine.
So the thing I wrote so casually was a use-after-free dressed up as a worklist.
losing gracefully, twice over
The first fix I tried was the stubborn one: index by position instead of borrowing, while i < queue.len(), reading queue[i] and pushing as I go. It compiles, because each access is a fresh, short borrow rather than one long one held across the loop. But it felt like I'd argued my way past the checker rather than understood it, and it had a subtle property I hadn't thought through: it processes the newly-added items too, in the same pass, which for my actual problem could loop forever if the work generated more work generated more work.
The borrow error had been quietly pointing at a design question I hadn't answered, which is "do items added during a pass get processed in that pass or the next one". That's not a syntax problem. That's the real behaviour of my worklist, and I'd never decided what I wanted it to be.
So the second fix was the honest one. Drain the current generation into a fresh vector of new work, swap it in, and repeat until nothing new is produced:
let mut queue = initial;
while !queue.is_empty() {
let mut next = Vec::new();
for item in &queue {
next.extend(process(item));
}
queue = next;
}
Now each pass reads a vector it never mutates, and the new work lands in a separate vector that becomes next time's input. The borrow conflict is gone because the read and the write are on different vectors, and more importantly the generations are explicit. I can reason about termination now, because I can see the work shrinking pass over pass instead of all blurring into one ever-growing loop.
The borrow checker cost me twenty minutes and gave me back a design decision I'd skipped. That's the trade most of these fights turn out to be. It won't let you alias-and-mutate, and the place it stops you is almost always a place where you hadn't actually decided what you meant. Losing gracefully means treating the red error as a question rather than an obstacle. I'll have forgotten that again by the next one, but I'm writing it down in hope.