When `RefCell` panics: re-entrancy and borrows held too long

Traverse a graph twice — once with a deliberate bug, once without — and report both results.

pub fn traverse(adj: Vec<Vec<usize>>, start: usize) -> (Vec<usize>, bool)

Return (the visit order, whether the buggy traversal panicked).

The graph lives in a Graph struct whose fields are all RefCells: the adjacency lists, a seen-flag per node, and the visit order. The traversal is a depth-first walk from start that also calls a bookkeeping function, prune, which mutates the adjacency lists — it clears the row of any node whose neighbour turned out to be already seen.

A node’s neighbours are visited in adjacency order. Each node is expanded at most once. If start is out of range, the answer is ([], false).

The starter contains the buggy traversal already written. Do not fix it — it is the specimen. Your jobs are:

1. get catch_unwind to compile so the panic becomes an observable bool;
2. write the same traversal without the bug, and return its visit order.

Run the two on separate Graph instances: after the buggy one unwinds, its state is half-finished.

The bug

let adj = g.adj.borrow();          // <- guard bound to a variable
for &m in &adj[n] {
    if g.seen.borrow()[m] {
        prune(g, n);               // <- borrow_mut() in here. Panic.
    } else {
        naive(g, m);
    }
}

thread 'main' panicked at src/lib.rs:23:15:
RefCell already borrowed

The most important sentence in this problem

The panic location is the SECOND borrow. The bug is at the FIRST.

Every learner reads that backtrace, goes to the borrow_mut() line inside prune, and stares at it. There is nothing wrong with that line. prune is correct, it is used correctly, and it will work perfectly the next time you call it. The defect is nine lines earlier, in a function that did not appear in the panic message: somebody took a shared borrow and held it longer than they needed to.

Internalising that inversion is the difference between debugging a BorrowMutError in ten seconds and losing an afternoon.

The three shapes this bug comes in

1. A borrow held across a call that re-enters. Exactly this problem. prune is innocent; the caller is not.
2. Binding a guard to a variable where a statement would have done. let adj = c.borrow(); lives to the end of the scope. c.borrow()[n].clone() lives to the end of the statement. That is the whole fix here.
3. Iterating a borrowed collection while a callback mutates it. The iterator holds the guard for the entire loop.

The robust form for all three is collect, then apply: take what you need out of the cell as an owned value, let the guard die, then do the work.

let neighbours: Vec<usize> = g.adj.borrow()[n].clone();
for m in neighbours { … }

Yes, that clones. Clippy’s redundant_clone complains about clones that were not needed; this one is load-bearing — it is the mechanism that ends the borrow. Recognising the difference between a wasteful clone and a scope-shortening one is a real skill, and a reviewer who cannot tell them apart will make your code panic.

Making a panic into an assertion

let panicked = catch_unwind(AssertUnwindSafe(|| naive(&probe, start))).is_err();

catch_unwind runs a closure and returns Err if it unwound. It is not a general-purpose try/catch — do not build control flow out of it — but for observing that something panicked it is exactly right, and it is what makes “prove this panics” a deterministic test rather than a story.

Without AssertUnwindSafe the starter does not compile, and the error is worth reading in full:

error[E0277]: the type `UnsafeCell<Vec<Vec<usize>>>` may contain interior
              mutability and a reference may not be safely transferable
              across a catch_unwind boundary
  = help: within `Graph`, the trait `RefUnwindSafe` is not implemented for
          `UnsafeCell<Vec<Vec<usize>>>`

There is the UnsafeCell from the interior-mutability article, surfacing in a diagnostic. The concern is real: a panic can unwind out of the middle of an operation and leave a cell holding a half-updated value, which the catcher then observes. AssertUnwindSafe is you telling the compiler you have thought about that. Here you have — the probe graph is thrown away immediately.

Note also that the panic during unwinding does run every guard’s Drop, so the borrow flags are correctly restored on the way out. The cell is not poisoned; it is just holding whatever state the traversal had reached.

Where the bool actually comes from

The buggy walk panics the first time it meets an already-seen neighbour — so panicked is really the question “does the reachable part of this graph contain a cycle or a shared node?” A pure tree never reaches prune while the guard is live, so it never panics. Work through the cases and you can predict every answer before you run it, which is the point.