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

Build a tree with parent pointers that does not leak, and prove both halves of that claim.

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>)

A TreeNode holds kids: RefCell<Vec<Rc<TreeNode>>> pointing down, parent: RefCell<Weak<TreeNode>> pointing up, an id, and a handle to a shared drop log. Each edge is (parent, child). The input is a forest: no node has two parents and there are no cycles.

ancestry returns, for each query, the root-first path down to that node — so [1, 2, 3] for node 3 in the chain 1→2→3. An unknown id gives an empty path.

lifetime_probe does this, in order:

1. build the tree and keep every node in a registry;
2. save a handle to leaf, and — only if keep_root — a handle to its root;
3. drop the registry;
4. record the path leaf can still walk upward, and whether its immediate parent still upgrades;
5. drop the saved handles;
6. return (path, parent_alive, the sorted ids that reached their destructor).

Strong down, weak up

The previous problem left you with a leak and a diagnosis: a tree where children hold Rc handles to their parents is a cycle at every edge, and the whole tree becomes immortal.

The fix is a direction rule, and it is one of the few genuinely transferable design ideas in this track:

Ownership points one way. The other way is non-owning.

In a tree, the parent owns the children, so kids is Rc and parent is Weak. There are no cycles in the strong graph, so the counts reach zero and everything dies. lifetime_probe‘s third return value asserts exactly that: every id appears, every time.

Getting the direction backwards — weak down, strong up — compiles and runs and is a disaster. The children would have no owner, so they would be freed the instant the builder’s registry went away, and every kid.upgrade() would return None. Worth deliberately trying once.

What Weak actually is

A Weak<T> is a handle to the same allocation, counted in a separate weak counter. Two facts follow, and both matter:

• A Weak keeps the allocation alive but not the value. When the last Rc goes, T is dropped — the destructor runs, the data is gone — but the little block holding the two counters survives until the last Weak goes too, because otherwise the remaining Weaks would have nowhere to read “am I still valid?” from.
• Weak<T> does not Deref. There is no weak.field and no weak.method(); learners try both and get E0609 or E0599. You must upgrade(), which returns Option<Rc<T>> — Some while the value lives, None after. Handling that None is not ceremony. It is the entire difference between this and a dangling pointer.

Weak::new() builds a permanently-dangling weak handle that always upgrades to None. That is the natural “no parent yet” placeholder, and it is why the root’s parent field needs no Option.

Why the parent field needs a RefCell

You cannot set a child’s parent while constructing the child, because the parent may not exist yet — and even when it does, you would need to hand out a Weak to a value you are still building. So the field starts as Weak::new() and is patched afterwards, which requires mutating a node you only have a shared handle to. Hence RefCell<Weak<TreeNode>>.

That two-step dance is annoying enough that std provides a way to avoid it for self-references, which is the next problem.

The compile error in the starter

The obvious upward walk does not compile:

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

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 …
   |         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<'_, Weak<TreeNode>>`

Read the last note. The Ref guard produced by borrow() is a temporary in the while let scrutinee, and a while let scrutinee’s temporaries live for the whole loop body — so the guard is still alive, still borrowing cur, when you try to reassign it.

This is the same lesson as the re-entrancy problem, in a new costume: the guard’s extent is the problem, not the borrow itself. The cleanest fix is to put the borrow inside a small function so the guard dies at the return:

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

Now the scrutinee is parent_of(&cur), which produces an owned Option<Rc<_>> and holds nothing.

What the probe proves

With keep_root = true, something upstream still owns the chain, so the leaf can walk all the way home: full path, parent_alive == true.

With keep_root = false, the registry was the only owner of the interior nodes. Dropping it kills them immediately, and the surviving leaf — which you are holding — finds upgrade() returning None: path [leaf], parent_alive == false. No crash, no dangling pointer, just an honest None. That is what Weak buys, and it is worth pausing on: in C++ this is a dangling Node* and undefined behaviour.

And in both cases the drop log lists every id. Nothing leaked.