Reference cycles leak memory

Build a graph out of Rc links, drop every external handle, and report which nodes actually died.

pub fn leak_detector(links: Vec<(usize, usize)>) -> Vec<usize>

The node count is 1 + max index appearing in links, or zero when there are no links. A link (a, b) makes node a hold an Rc handle to node b; a node may hold several.

Each node’s Drop pushes its id onto a shared log. After the links are wired up, drop the vector of external handles, then return the sorted list of ids that reached their destructor.

The assertion is the absence of drops. Nodes caught in a cycle never appear in the answer — and that is the whole lesson.

The one failure mode with no diagnostic at all

Every mistake in this track so far has announced itself. E0072 was a compile error. large_enum_variant was a lint. BorrowMutError was a panic with a line number.

This one is silent.

Two nodes that hold Rc handles to each other keep each other’s strong count at one forever. Their scope ends, every outside handle is dropped, and their destructors never run. No error. No warning. No lint. No panic. Just memory that is never freed, files that are never closed, connections that are never returned to the pool, and a process whose resident size creeps upward over hours.

Say that plainly, because by this point in the track you have been trained to expect the tooling to have your back: no clippy lint catches reference cycles. mem_forget catches an explicit std::mem::forget, which is not this. type_complexity catches an ugly type, which is not this either. Cycle detection would require whole-program analysis of runtime shape, and neither rustc nor clippy attempts it.

Why Rust allows it

Because a leak is not unsound. This is worth internalising, because it explains a lot of the standard library’s design:

Rust guarantees memory safety — no use-after-free, no data races, no dangling pointers. It does not guarantee that destructors run.

Leaking is safe. Box::leak is a safe function. mem::forget is a safe function. Failing to free memory cannot corrupt anything; it can only exhaust a resource. So the language permits it, and the responsibility for cycles is yours.

The cases, and the one that surprises people

Trace the strong counts by hand before you run anything.

• A chain 0 → 1. Dropping the handle vector releases node 0; node 0’s destructor releases its link to node 1; node 1 dies too. Both logged.
• A 2-cycle 0 ⇄ 1. Each has count 2 — the vector plus the other node. Dropping the vector takes each to 1. Neither dies. Nothing logged.
• A self-loop 0 → 0. The smallest possible cycle, and the easiest to write by accident. Count 2 → 1. Nothing logged.
• A cycle with a tail: 0 ⇄ 1 and 1 → 2. Node 2 is not in the cycle, has no cycle of its own, and is still never dropped — because the thing holding it alive is node 1, and node 1 is immortal. A leaked cycle leaks everything reachable from it, which is how one accidental back-pointer turns into a leak of an entire subtree.

That last case is the one people get wrong on paper, and it is the reason a small cycle in a big graph is a big problem.

How this happens for real

Nobody writes a.next = b; b.next = a; on purpose. What they write is a parent pointer.

A tree where every child holds an Rc to its parent and every parent holds an Rc to its children is a cycle at every single edge. It is the most natural thing in the world to write — you need to walk upward, so you store a handle upward — and the whole tree becomes immortal the moment you build it. If you built anything with a back-reference in the previous item, you have probably already done this.

The fix has a name and it is the next problem in this track.

Debugging note

When you suspect a cycle, do not reach for {:?}. A derived Debug on a cyclic Rc<RefCell<Node>> follows every link it can reach and recurses forever: no error, no stack trace, just unbounded output and a process that never returns. Probe with Rc::strong_count instead — a count that stays above zero when you expect it at zero is the signature you are looking for.