Reference cycles leak memory

Build the supplied graph of strong Rc links, release its external owners, and return the sorted IDs of nodes whose destructors ran.

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

Complete impl Drop for Node: when a node is destroyed, append its id to the shared log. Keep the supplied graph construction and strong links so the exercise can demonstrate a reference cycle. Do not replace this observation with a graph algorithm or change the links to Weak.

Graph and output rules

The node count is one more than the largest index in links, or zero for an empty list. Create every ID from 0 to that count, including IDs that never appear in a link. Inputs are small enough for the allocation and recursive destruction of this graph; adding one to an index does not overflow.

A pair (a, b) makes node a own a strong Rc<Node> handle to node b. Repeated links add repeated handles. Each node also owns a handle to the shared log, which contains only IDs and does not point back to the nodes.

After constructing all links, drop the vector of external node handles. Read the log and sort its IDs in ascending order. Each destroyed node appears once. Do not rely on the vector's element-drop order, which is not guaranteed.

Empty links return an empty list. A node that points into a cycle can still be destroyed if nothing retains it; link direction matters.

Why strong cycles retain nodes

In the two-node cycle, each node initially has two strong owners: its external vector entry and the other node's link. Dropping the external entries reduces each count to one. Neither reaches zero, so neither node's destructor runs to release its outgoing link.

With the graph left unchanged, nodes on a strong cycle remain allocated. So do all nodes reachable from that cycle through strong links. A chain leading into a cycle is different: destroying its first node can release the chain while leaving the cycle intact.

The supplied Drop method logs the node's ID. After that method returns, Rust drops the node's fields, including its outgoing handles. Those releases may bring other nodes' strong counts to zero and start their destruction.

A leak does not require unsafe code

Rust's memory-safety guarantees do not guarantee that every allocation is reclaimed or every destructor runs. Safe code can create a strong reference cycle, and functions such as mem::forget can deliberately prevent a drop. A leak by itself is not undefined behavior, though it can retain memory or other resources the application needs to release.

This exercise intentionally leaves cycles intact to observe which nodes survive. In this implementation, surviving nodes also retain handles to the shared log. Do not treat a clean build or a passing lint check as proof that an ownership graph releases all its resources.

Separate ownership from navigation

A parent owning its children through Rc links can form a cycle if every child also owns its parent. A common design uses a Weak back-reference: the child can try to reach the parent without keeping the parent value alive. Weak::upgrade() returns None after the value has been dropped.

The right direction for weak links depends on which objects should own which others. Replacing an arbitrary edge is not enough if other strong cycles remain. Keep the strong links for this exercise; weak links are a way to change the ownership design in real code.

Inspect without recursively printing the graph

A derived Debug implementation that follows every link of a cyclic graph can recurse without reaching a base case and may overflow the stack. Prefer a summary of node IDs and link IDs, or use a visited set to limit a graph printer.

Reference counts are useful observations, but account for the handle used to inspect them. An Rc handle is itself a strong owner, so inspecting it cannot demonstrate a zero strong count. A retained Weak observer can check the strong count or attempt an upgrade after external owners are released. A successful upgrade creates another temporary strong owner.

For this task, the destructor log is the measurement. Verify the sorted output for chains, cycles and nodes reachable from cycles, then run the compile, test and Clippy gates.