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

Run two depth-first traversals of a directed graph: the supplied buggy traversal and a repaired one. Return the repaired visit order and whether the buggy traversal panicked.

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

Nodes are numbered 0..adj.len(). Each row lists that node's outgoing neighbors in traversal order. Every neighbor index is valid. Self-loops, repeated edges and disconnected components are allowed. Inputs are small enough for the supplied recursive traversal.

If start is outside the graph, return ([], false). Otherwise, record each node when first reached and expand it at most once. Use separate Graph instances for the two traversals so the buggy run's partial changes do not affect the repaired run.

Preserve the traversal's behavior

Keep naive and prune unchanged. Complete walk, and make the existing catch_unwind call compile. The graph stores adjacency lists, seen flags and visit order in three separate RefCells.

Before visiting a node's neighbors, the repaired walk must take an owned snapshot of that node's row. For each neighbor in the snapshot:

• If it is unseen, visit it recursively.
• If it is already seen, call prune(g, n) for the current node n.

prune clears the current node's entire stored row, not just one edge. Continue processing the snapshot after pruning. Clearing the stored row must not skip its remaining snapshot entries.

In the last example, the self-loop triggers pruning, but the snapshot still contains node 1, so the repaired traversal visits it.

Find both sides of the borrow conflict

The buggy walk holds a shared adjacency guard across its loop:

let adj = g.adj.borrow();
for &m in &adj[n] {
    if g.seen.borrow()[m] {
        prune(g, n);
    } else {
        naive(g, m);
    }
}

prune calls g.adj.borrow_mut(), which panics while that shared guard is alive. The panic points to the new borrow request; the explanation also involves the earlier guard that is still held. Check both the caller and the called function when diagnosing this kind of failure.

The RefCell protects the whole adjacency vector, so borrowing a different row would still conflict. Recursive calls can hold several shared guards at once, but none permits a mutable borrow of that same cell.

Release the guard before the calls

let neighbours: Vec<usize> = g.adj.borrow()[n].clone();
for m in neighbours {
    // Check seen, then prune or recurse.
}

This statement copies the row's node IDs into an owned vector. The temporary Ref guard is dropped at the end of the statement. The loop then owns its data and holds no adjacency borrow across prune or recursion.

Cloning alone does not drop a separately named guard. If you first bind let adj = g.adj.borrow(), that guard remains until it is explicitly dropped or its scope ends. The short statement above avoids retaining such a guard. The temporary borrow in the ordinary condition if g.seen.borrow()[m] ends before its branch runs, so it does not remain across the recursive call.

Observe the intentional panic

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

Import both names from std::panic. Without the wrapper, the closure's captured &Graph does not satisfy the unwind-safety requirement because of its interior-mutability fields. The starter reports E0277.

AssertUnwindSafe asserts that the caller has considered the state left by unwinding. It does not restore the graph, prevent panics or make arbitrary recovery safe. Here the only result retained from the probe is whether it unwound; the repaired walk uses a fresh graph.

During ordinary unwinding in this example, live borrow guards are dropped and release their borrows. RefCell has no mutex-style poisoning, but the seen flags and visit order still contain partial traversal state.

catch_unwind catches unwinding panics, not aborts. The exercise's panic observation therefore requires an unwinding build. A panic hook normally runs before the panic is caught; the supplied harness suppresses its output because these probe panics are intentional.

Predict the boolean

For valid inputs, the buggy walk panics when it first processes an edge to an already-seen node. A reachable self-loop, directed cycle, duplicate edge or converging path can cause this. A cycle in an unreachable component does not affect the result. A directed tree traversed from its root has no such repeated encounter and returns false.

Check both outputs and the snapshot behavior. Passing requires compilation, correct results and Clippy with warnings treated as errors.