skip to content

In Rust, building a DOM-like tree of `Rc` nodes with parent links, why must the parent field be a `Weak`, and what does `Weak::upgrade` return?

level: middleimportance: must knowfreq 66%

answer

  1. ownership points down the tree
  2. a strong back-edge never reaches zero
  3. std::rc::Weak does not own
  4. upgrade gives Option<Rc<T>>
  5. Rc::new_cyclic hands out &Weak

basics

~20 s

Children are owned through Rc and point back through std::rc::Weak, because a strong parent link forms a cycle whose counts never reach zero, so nothing is dropped. Weak::upgrade returns Some(Rc) while the parent lives and None afterwards.

solid answer

~40 s

Ownership should run one way: a parent holds `Vec<Rc<Element>>`, and each child holds `parent: Weak<Element>`. If the child held an `Rc` instead, parent and child would keep each other's strong count at one or more after every outside handle is gone, so neither `Drop` runs and the memory leaks; rustc accepts that, because Rust does not count leaks as unsafe. A `Weak` from `Rc::downgrade` adds to the weak count only, which never keeps the value alive, and it has no `Deref`. To use the parent you call `Weak::upgrade`, which returns `Option<Rc<Element>>`: `Some` with a temporary strong handle while any `Rc` survives, `None` once the parent has been dropped. `Rc::new_cyclic` lets a node give its children that `Weak` while it is still being built.

code

rust · 29 lines
rust
use std::rc::{Rc, Weak};

struct Element {
    tag: &'static str,
    parent: Weak<Element>,
    children: Vec<Rc<Element>>,
}

fn leaf(tag: &'static str, parent: &Weak<Element>) -> Rc<Element> {
    Rc::new(Element { tag, parent: parent.clone(), children: Vec::new() })
}

fn main() {
    // new_cyclic hands the closure a Weak to the allocation being built.
    let body = Rc::new_cyclic(|me: &Weak<Element>| Element {
        tag: "body",
        parent: Weak::new(),
        children: vec![leaf("h1", me), leaf("p", me)],
    });
    let p = Rc::clone(&body.children[1]);

    let parent_tag = p.parent.upgrade().map(|e| e.tag);
    println!("parent of {}: {:?}", p.tag, parent_tag);
    println!("body strong = {}, weak = {}", Rc::strong_count(&body), Rc::weak_count(&body));

    drop(body); // the only strong handle to body
    println!("after drop: {:?}", p.parent.upgrade().map(|e| e.tag));
    println!("p strong = {}", Rc::strong_count(&p));
}

go deeper

for a junior

Recall that a child points to its parent with Weak, not Rc, and that Weak::upgrade gives Some while the parent lives and None after.

for a middle

Walk through why strong edges in both directions keep both counts above zero, how Rc::downgrade and upgrade move between handle kinds, and how Rc::new_cyclic wires a parent link during construction.

for a senior

Explain how you would find such a leak in a running program, with Drop logging and strong_count checks, and that Rust accepts a leak because destructors running is not a safety guarantee.

for a principal

Weigh Rc and Weak pointer trees against an arena with indices for a large editable tree, where parent links are plain integers and a cycle cannot leak memory at all.

## The shape of the problem A DOM-like tree needs navigation in both directions: a `body` element lists its children, and a `p` element must find its parent to resolve inherited styles or bubble an event. In Rust the natural first draft gives every edge an `Rc<Element>`, and it is the one draft that silently leaks. `Rc<T>` frees its value when the **strong count** reaches zero. With strong edges both ways: 1. `body` holds an `Rc` to `p`, so `p`'s strong count is at least 1. 2. `p` holds an `Rc` to `body`, so `body`'s strong count is at least 1. 3. When the local variables go out of scope, each count falls to 1 and stays there. No `Drop` runs, and the memory is never returned. This is a **reference cycle**, and in safe code it is usually built through a field that can be changed after construction, such as a `RefCell` (covered with Cell and RefCell). rustc does not reject it: the `mem::forget` docs state that Rust's safety guarantees do not include destructors always running, and name an `Rc` cycle as an example. A leak is a bug, not undefined behaviour. ## `Weak`: a handle that does not own `std::rc::Weak<T>` (not to be confused with the thread-safe `std::sync::Weak`) is created by `Rc::downgrade(&rc)`. It differs from `Rc` in four ways: - it adds to the **weak count**, which does not keep the inner value alive; - it does **not** implement `Deref`, because the value may already be gone; - it keeps the **allocation** alive until the last `Weak` is dropped, but not the value inside it; - `Weak::new()` makes one that points at no allocation at all, handy for a root's empty `parent` field. The rule for a tree is that **ownership points down**: parents own children through `Rc`, children refer up through `Weak`. Dropping the root then cascades: its strong count reaches zero, its `Vec<Rc<Element>>` is dropped, each child's strong count falls, and so on down. ## `Weak::upgrade` and the `Option` it returns | State of the parent | `child.parent.upgrade()` | `Weak::strong_count` | |---|---|---| | at least one `Rc` alive | `Some(Rc<Element>)`, strong count bumped by one | 1 or more | | last `Rc` dropped | `None` | 0 | | created with `Weak::new()` | `None` | 0 | | inside `Rc::new_cyclic`'s closure | `None` | 0 | Because the result is an `Option`, the compiler makes you handle the `None` case: `if let Some(parent) = child.parent.upgrade() { ... }`. The `Some` holds a real `Rc`, so the parent cannot be dropped while you are using it; once that temporary handle goes out of scope the count drops back. ## Building the links: `Rc::new_cyclic` A child needs a `Weak` to a parent that does not exist yet. `Rc::new_cyclic` solves that ordering problem: 1. it allocates the parent's block first; 2. it calls your closure with `&Weak<T>` pointing at that block; 3. it moves the value your closure returns into the block and hands back the `Rc<T>`. Inside the closure, `upgrade` returns `None` because the value is not built yet, but you can clone the `Weak` into every child you create. The first code example builds a `body` with two children this way and needs no interior mutability. Trees that are edited after construction (re-parenting, inserting children later) usually store `RefCell<Weak<Element>>` and `RefCell<Vec<Rc<Element>>>` instead, which is the pattern the Rust Book uses. ## Diagnosing a leak in a tree - Implement `Drop` with a log line on the node type, or count drops in a test; a cycle shows up as destructors that never run. - Keep a `Weak` to a suspect node and read `Weak::strong_count` after every outside handle is gone. A count above 0 means something inside the structure still owns it. - Look for every field typed `Rc` that points **up** or **sideways**; each is a candidate for `Weak`. - Remember that a long-lived `Weak` keeps a large node's allocation reserved after its value is dropped, so trimming dead `Weak` handles from caches matters too. ## Using a parent link well - Upgrade, use, let go: keep the `Rc` returned by `upgrade` only for the work at hand. Storing it in a field turns the weak edge back into a strong one. - Compare parents with `Weak::ptr_eq` or `Rc::ptr_eq` rather than `==`, which compares the values. - Treat `None` from `upgrade` as a normal outcome, for example a detached subtree, not as a bug to `unwrap` away.

  • Why does `Weak<T>` not implement `Deref` the way `Rc<T>` does?
    Because the value behind a `Weak` may already have been dropped, and `Deref` must return a `&T` unconditionally. `Weak::upgrade` makes the check explicit: it returns `Option<Rc<T>>`, and the `Some` case holds a strong handle so the value cannot be dropped while you use it.
  • After the parent is dropped, its children still hold `Weak` handles to it; is the parent's memory freed?
    Its value is dropped as soon as the strong count reaches zero, so the parent's fields and their own heap buffers are released. The block holding the counts and the value's slot stays reserved until the last `Weak` is dropped, which is why a huge `T` stored inline behind many stale `Weak` handles can still hold memory.
  • Can you build a strong `Rc` cycle without `RefCell`, `Cell` or `unsafe`?
    Not in the ordinary way. One node must exist before the other can hold it, so the first node's field has to be changed afterwards, and an `Rc` gives out only `&T`. `Rc::get_mut` refuses once a second handle exists, and `Rc::new_cyclic` hands out only a `Weak`, so in practice a cycle in safe code is built through interior mutability.

  • Rust's borrow checker refuses to compile an Rc reference cycle.
  • A leaked Rc cycle is undefined behaviour in Rust.
  • Weak::upgrade returns a dangling pointer once the parent is dropped.
  • A Weak handle keeps its target alive until the Weak is dropped.
  • Rc::downgrade increments the strong count of the target.
  • A Weak can be dereferenced directly like an Rc.