Weak<T>: non-owning references that break cycles

Build a tree whose nodes point both down to their children and up to their parent, without the parent pointers keeping anything alive. Then show that every node is freed and that a surviving node can detect that its parent is gone.

pub fn ancestry(edges: Vec<(u32, u32)>, queries: Vec<u32>) -> Vec<Vec<u32>>
pub fn lifetime_probe(edges: Vec<(u32, u32)>, leaf: u32, keep_root: bool)
    -> (Vec<u32>, bool, Vec<u32>)

The node type

The starter defines TreeNode for you. Each node has:

• id: u32;
• kids: RefCell<Vec<Rc<TreeNode>>>, owning handles to its children;
• parent: RefCell<Weak<TreeNode>>, a non-owning handle to its parent;
• log, a shared Rc<RefCell<Vec<u32>>>. The Drop implementation pushes the node's id onto this log when the node is destroyed, so the log records exactly which nodes were freed.

The starter's build function creates one node per id that appears in edges, stores an Rc to each in a registry (a BTreeMap<u32, Rc<TreeNode>>) and then wires up the edges. build is already correct; you do not need to change it.

Input

Each edge is (parent, child). The edges describe a forest (one or more separate trees):

• every id appears as the child in at most one edge, so no node has two parents and no edge is repeated;
• there are no cycles, including no self-edge such as (1, 1);
• edges may arrive in any order, so a child's edge can come before its parent's own edge;
• a node exists only if its id appears in some edge. With no edges there are no nodes.

Ids are arbitrary u32 values; they need not be consecutive or start at 1.

ancestry

For each id in queries, in query order, return the path from that node's root down to the node itself, root first. In the chain 1 -> 2 -> 3, the query 3 gives [1, 2, 3] and the query 1 gives [1]. A query for an id that is not in the forest gives []. Queries may repeat.

lifetime_probe

This function performs these steps in order:

1. Build the forest with build, so the registry holds an Rc to every node.
2. Save an Rc to the node leaf. If keep_root is true, also save an Rc to the root of leaf's tree (which is leaf itself if leaf is a root). Find the root now, while every node is still alive.
3. Drop the registry.
4. From the saved leaf handle, record path: the root-first path it can still reach by following parent upward, ending at leaf. Also record parent_alive: whether leaf's own parent handle still upgrades.
5. Drop every saved handle.
6. Return (path, parent_alive, dropped), where dropped is the list of ids that the Drop implementation logged, sorted ascending.

Despite its name, leaf may be any node, not only one without children. If leaf is not in the forest, nothing is saved, and the result is path = [] and parent_alive = false. Because every node is freed exactly once by step 6, dropped always lists every id in the forest exactly once.

Strong handles down, weak handles up

An Rc<T> is an owning ("strong") handle: the value inside stays alive while at least one Rc to it exists. If a child held an Rc to its parent while the parent held an Rc to the child, the two would keep each other alive forever. That reference cycle is a memory leak: no destructor runs, even after the rest of the program has let go of both nodes.

The fix is to choose one direction for ownership. In a tree the parent owns its children, so kids holds Rc and parent holds Weak, which does not own. Because the input has no cycles, the strong handles form no cycle either. When the last outside handle goes away, each node's strong count reaches zero, its destructor runs, and it releases its children in turn.

Choosing the opposite direction (weak handles down, strong handles up) also compiles, but then nothing owns a node except the registry and the node's own children. Once the registry is dropped, every node without children is freed, which releases its parent, and so on up the tree. Even if you kept an outside Rc to the root, its children would all be freed, and the root's Weak handles to them would upgrade to None.

What Weak is

Rc::downgrade(&rc) creates a Weak<T> that refers to the same allocation as rc. The allocation keeps two counters: a strong count for Rc handles and a weak count for Weak handles. Two consequences matter here:

• A Weak does not keep the value alive. When the strong count reaches zero, the value is dropped (its destructor runs), even if Weak handles remain. The memory block that held the value and the counters is freed later, once the weak count also reaches zero, so a remaining Weak can still read the counters and see that the value is gone.
• You cannot reach the value through a Weak directly. Weak<T> does not implement Deref, so weak.id fails with error E0609 (no field on Weak<T>) and calling a method of T on it fails with E0599. Call weak.upgrade() instead. It returns Option<Rc<T>>: Some(rc) while the value is alive, None after it has been dropped. The Some result is a new strong handle, so the value cannot be freed while you use it.

Weak::new() creates a Weak that refers to no value at all and does not allocate. Upgrading it always gives None. That makes it the natural "no parent" value for a root, which is why parent needs no extra Option.

Why the parent field needs a RefCell

build creates every node first and only then reads the edges. At creation time a node's parent is not known yet, so parent starts as Weak::new() and is set later. By then the node is already inside an Rc, and an Rc only gives shared (&) access to its contents. Changing a field through a shared reference requires interior mutability, hence RefCell<Weak<TreeNode>>. The same reasoning applies to kids. (For a value that must hold a Weak to itself from the moment it is created, std provides Rc::new_cyclic; this exercise does not need it.)

The compile error in the starter

The starter's upward walk in path_to_root does not compile:

while let Some(p) = cur.parent.borrow().upgrade() {
    path.push(p.id);
    cur = p;
}

With Rust 1.98.1 (edition 2024) the error is, in shortened form:

error[E0506]: cannot assign to `cur` because it is borrowed
   |     while let Some(p) = cur.parent.borrow().upgrade() {
   |                         -------------------
   |                         |
   |                         `cur` is borrowed here
   |                         a temporary with access to the borrow is created here ...
   |         path.push(p.id);
   |         cur = p;
   |         ^^^ `cur` is assigned to here but it was already borrowed
   |     }
   |     - ... and the borrow might be used here, when that temporary is dropped
   |       and runs the destructor for type `Ref<'_, std::rc::Weak<TreeNode>>`

The last note explains it. cur.parent.borrow() returns a Ref guard, a temporary value that borrows cur.parent and therefore cur. Temporaries created in a while let condition are not dropped until the end of that loop iteration, so the guard is still alive at cur = p;, and Rust will not let you replace cur while something borrows it. The compiler may also suggest adding a semicolon after the loop; that does not fix this case.

The fix is to end the guard before the assignment. One way is a small helper function. The guard is dropped when the function returns, and the caller receives an owned Option<Rc<TreeNode>> that borrows nothing:

fn parent_of(node: &Rc<TreeNode>) -> Option<Rc<TreeNode>> {
    node.parent.borrow().upgrade()
}

The loop condition then becomes while let Some(p) = parent_of(&cur). Storing the result with a separate let statement inside a loop also works, because temporaries in a let statement are dropped at the end of that statement.

What the probe shows

With keep_root = true, the saved root handle keeps the root alive after the registry is gone, and the root owns its children, which own theirs, so leaf's whole tree survives. The leaf can walk all the way up: path is the full root-first path, and parent_alive is true unless leaf is itself a root.

With keep_root = false, the only strong handles left after step 3 are the saved leaf handle and the kids handles inside leaf's subtree (from leaf to its children, from them to theirs, and so on). Every ancestor of leaf, and every node outside leaf's subtree, is freed when the registry is dropped. The saved leaf is still valid, but its parent.upgrade() returns None, so path is [leaf] and parent_alive is false. The program detects the missing parent safely. A raw pointer kept to the freed parent would instead dangle, and dereferencing it would be undefined behavior.

In both cases dropped lists every id, which shows that nothing leaked.