`Cell<T>`: mutation by moving values in and out

Count arrivals during a fixed graph walk.

pub fn visit_counts(edges: Vec<(usize, usize)>, start: usize) -> Vec<u32>

The node count is 1 + max(start, every index appearing in edges). Edges are directed and kept in input order, which is what makes the walk deterministic.

The walk is a depth-first traversal from start with one twist:

• every arrival at a node increments its counter, revisits included;
• a node recurses into its neighbours only on its first arrival.

Return the counter of every node in index order. Nodes never reached stay at 0. Self-loops and cycles are allowed and must terminate — the “recurse only on first arrival” rule is what guarantees that.

The constraint that makes this a Cell problem

The traversal function is handed &[Node] — a shared reference to the whole graph — and it recurses into itself while that reference is live. You cannot change it to &mut [Node], because the recursive call would then need a second exclusive borrow of the same slice, and the borrow checker will not give you one. That is not a puzzle to route around; it is the shape of every graph traversal ever written.

So the starter’s field is a plain u32, and the starter does not compile:

error[E0594]: cannot assign to `nodes[_].visits`, which is behind a `&` reference
  |     nodes[i].visits += 1;
  |     ^^^^^^^^^^^^^^^^^^^^ `nodes` is a `&` reference, so it cannot be written to
help: consider changing this to be a mutable reference

Ignore that help: line. It is the compiler’s usual first guess and it is wrong here — following it just moves the error to the recursive call. The fix is to change the type of the field, not the type of the reference.

Cell<T>: the one that cannot panic

Cell<T> is the simplest interior-mutability type in the language, and it is sound with zero ceremony for one reason that is worth stating precisely:

Cell never hands out a reference to its contents at all.

There is no &T to the inside, ever. You put a value in, you take a value out, you swap one for another. Since no reference to the interior can escape, there is nothing for a second borrow to conflict with, so there is nothing to check — no flags, no counters, no branch, and no way to panic. A Cell<u32> is exactly as big as a u32 and exactly as fast.

The API follows from that design:

Note that get requires Copy — and note which error you get if you forget that, because it is not the one you would guess:

error[E0599]: the method `get` exists for struct `Cell<String>`,
              but its trait bounds were not satisfied
  = note: the following trait bounds were not satisfied:
          `String: Copy`

That is E0599 — method not found — not E0277. get is defined in an impl<T: Copy> Cell<T> block, so for a non-Copy T the method genuinely does not exist on that type. Getting used to reading E0599 as “you are inside the wrong impl block” will save you a lot of time.

update is stable as of Rust 1.88, and c.update(|v| v + 1) says what a counter increment means more clearly than c.set(c.get() + 1).

When Cell is the right answer — which is more often than you think

Counters. Flags. Dirty bits. Memoised scalars. Generation numbers. Anything small and Copy that gets swapped wholesale rather than edited in place.

For all of those, Cell is strictly better than RefCell: same expressive power for this shape of data, smaller, faster, and — the part that matters — it removes an entire class of runtime failure. Learners who meet RefCell first tend to use it for everything, then get a BorrowMutError on a counter increment. Meeting Cell first makes RefCell‘s runtime bookkeeping feel like something you buy when you need it.

Two facts about Cell that folklore gets wrong

You will read that “Cell doesn’t implement the comparison traits”. Half of that is true and the half people repeat is the wrong half.

• Cell<T> does not implement Hash. So it cannot be a HashMap key, and the attempt fails with a trait error long before clippy’s mutable_key_type gets involved. That restriction is real and it is the right call — a key whose hash can change is a key you can never find again.
• Cell<T> does implement Ord and PartialOrd when T: Ord + Copy / T: PartialOrd + Copy. Cell::new(1) < Cell::new(2) is true, and vec![Cell::new(3), Cell::new(1)].sort() compiles and works.

And one genuine hazard: you cannot mutate a Cell<Vec<T>> in place. There is no &mut to the interior, so the only route is take(), mutate the owned vector, set() it back — and between those two calls the cell holds an empty vector. Any re-entrant code that reads it in that window sees nothing. That is a real bug shape, and it is the point at which RefCell stops being optional.