Smart Pointers · about 40 min

Weak References and Reference Cycles

Why this matters

Rust's ownership rules prevent dangling pointers and double frees, but they do not make memory leaks impossible. With Rc, two values that point at each other keep each other's count above zero forever, and neither is ever freed. This happens naturally in trees with parent pointers, doubly linked lists and graphs. The tool for breaking such cycles is Weak<T>: a reference that can see a value without keeping it alive.

Creating a leak on purpose

use std::cell::RefCell;
use std::rc::Rc;

struct Node {
    name: &'static str,
    next: RefCell<Option<Rc<Node>>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("dropping {}", self.name);
    }
}

fn main() {
    let a = Rc::new(Node { name: "a", next: RefCell::new(None) });
    let b = Rc::new(Node { name: "b", next: RefCell::new(Some(Rc::clone(&a))) });
    *a.next.borrow_mut() = Some(Rc::clone(&b));
    println!("a strong = {}, b strong = {}", Rc::strong_count(&a), Rc::strong_count(&b));
    println!("end of main");
}
a strong = 2, b strong = 2
end of main

No "dropping" lines: neither node is ever freed. At the end of main, the variables a and b are dropped, which takes each count from 2 to 1, but the remaining count comes from the other node, which is itself alive only because of the first:

 variable a --X  (dropped at end of main)
                 Node a [strong 1] --next--> Node b [strong 1]
                     ^                          |
                     +-----------next-----------+
 variable b --X

Rust considers leaking memory safe (it cannot cause undefined behavior), so the compiler does not stop this. In a long-running program, such leaks accumulate.

Weak: a non-owning reference

Rc::downgrade(&rc) creates a Weak<T>. It points at the same allocation but increments a separate weak count, which does not keep the value alive. To use it, call upgrade(), which returns Option<Rc<T>>: Some if the value is still alive, None if it has been dropped:

use std::rc::Rc;

fn main() {
    let strong = Rc::new(String::from("data"));
    let weak = Rc::downgrade(&strong);
    println!("strong {}, weak {}", Rc::strong_count(&strong), Rc::weak_count(&strong));
    match weak.upgrade() {
        Some(s) => println!("still here: {s}"),
        None => println!("gone"),
    }
    drop(strong);
    println!("after drop: {:?}", weak.upgrade());
}
strong 1, weak 1
still here: data
after drop: None

When the strong count reaches zero the value is dropped, even if weak references remain. (The allocation holding the counts stays until the weak count reaches zero too, so upgrade can safely report None.) A Weak can never dangle: you cannot reach the value without upgrading, and upgrading checks.

Breaking cycles: decide who owns whom

The fix for cycles is a design decision: in each pair of mutual references, one direction owns (Rc) and the other merely refers (Weak). In a tree, parents own their children, and children refer weakly to their parent:

use std::cell::RefCell;
use std::rc::{Rc, Weak};

struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("dropping {}", self.value);
    }
}

fn main() {
    let leaf = Rc::new(Node { value: 3, parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]) });
    {
        let branch = Rc::new(Node { value: 5, parent: RefCell::new(Weak::new()), children: RefCell::new(vec![Rc::clone(&leaf)]) });
        *leaf.parent.borrow_mut() = Rc::downgrade(&branch);
        let parent_value = leaf.parent.borrow().upgrade().map(|p| p.value);
        println!("leaf's parent = {:?}", parent_value);
        println!("branch strong {}, weak {}", Rc::strong_count(&branch), Rc::weak_count(&branch));
        println!("leaf strong {}, weak {}", Rc::strong_count(&leaf), Rc::weak_count(&leaf));
    }
    println!("after branch scope: leaf's parent = {:?}", leaf.parent.borrow().upgrade().map(|p| p.value));
    println!("leaf strong {}", Rc::strong_count(&leaf));
}
leaf's parent = Some(5)
branch strong 1, weak 1
leaf strong 2, weak 0
dropping 5
after branch scope: leaf's parent = None
leaf strong 1
dropping 3

When branch goes out of scope, its strong count drops to zero (the leaf's reference to it is weak), so the branch is dropped, which drops its children vector, which decrements the leaf's count. The leaf survives because the variable leaf still owns it, and its parent link now upgrades to None. Everything is freed in the end.

 branch (Rc, owns) --children--> leaf
    ^                              |
    +------ parent (Weak) ---------+

The same rule applies elsewhere: in a doubly linked list, next is strong and prev is weak; in an observer pattern, the subject holds Weak references to observers so it does not keep them alive.

Alternatives worth knowing

Rc<RefCell<...>> graphs work, but they are verbose and push errors to run time. Many Rust programs instead store all nodes in a Vec and refer to them by index (usize): no reference counting, no cycles to leak, cache-friendly, and borrow-checker friendly. For graphs with many cross-links, an arena with indexes is often the cleaner design.

Common mistakes

Recap

Going further: read the Rust Book chapter 15.6, "Reference Cycles Can Leak Memory". Then build a three-level tree and print strong_count/weak_count for each node as you drop levels.

Exercises

Exercise 1 · write code

Children that know their parent

Build a tree where each node owns its children (Rc) and refers to its parent weakly (Weak):

struct Node {
    name: String,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

Write fn add_child(parent: &Rc<Node>, name: &str) -> Rc<Node> (creates the child, sets its parent with Rc::downgrade, pushes it into the parent's children) and fn path(node: &Rc<Node>) -> String that walks up the parents and returns the names joined by / from the root down. The given main reads lines parent child from stdin (the root is called root) and prints the path of every node, in the order created:

root/etc
root/etc/ssh
root/home

File: main.rs

Starting point

use std::cell::RefCell;
use std::collections::HashMap;
use std::io;
use std::rc::{Rc, Weak};

fn main() {
    let root = Rc::new(Node { name: String::from("root"), parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]) });
    let mut by_name: HashMap<String, Rc<Node>> = HashMap::new();
    by_name.insert(String::from("root"), Rc::clone(&root));
    let mut order = Vec::new();
    for line in io::stdin().lines() {
        let line = line.unwrap();
        let (p, c) = line.trim().split_once(' ').unwrap();
        let parent = Rc::clone(&by_name[p]);
        let child = add_child(&parent, c);
        by_name.insert(c.to_string(), Rc::clone(&child));
        order.push(child);
    }
    for n in &order {
        println!("{}", path(n));
    }
}

Example

input

root etc
etc ssh
root home

expected output

root/etc
root/etc/ssh
root/home
Hint 1

In add_child: build the child with parent: RefCell::new(Rc::downgrade(parent)), then parent.children.borrow_mut().push(Rc::clone(&child)).

Hint 2

In path: node.parent.borrow().upgrade() gives Option<Rc<Node>>; loop while it is Some, collecting names, then reverse and join.

Reference solution
use std::cell::RefCell;
use std::collections::HashMap;
use std::io;
use std::rc::{Rc, Weak};

struct Node {
    name: String,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

fn add_child(parent: &Rc<Node>, name: &str) -> Rc<Node> {
    let child = Rc::new(Node {
        name: name.to_string(),
        parent: RefCell::new(Rc::downgrade(parent)),
        children: RefCell::new(vec![]),
    });
    parent.children.borrow_mut().push(Rc::clone(&child));
    child
}

fn path(node: &Rc<Node>) -> String {
    let mut names = vec![node.name.clone()];
    let mut cur = node.parent.borrow().upgrade();
    while let Some(p) = cur {
        names.push(p.name.clone());
        cur = p.parent.borrow().upgrade();
    }
    names.reverse();
    names.join("/")
}

fn main() {
    let root = Rc::new(Node { name: String::from("root"), parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]) });
    let mut by_name: HashMap<String, Rc<Node>> = HashMap::new();
    by_name.insert(String::from("root"), Rc::clone(&root));
    let mut order = Vec::new();
    for line in io::stdin().lines() {
        let line = line.unwrap();
        let (p, c) = line.trim().split_once(' ').unwrap();
        let parent = Rc::clone(&by_name[p]);
        let child = add_child(&parent, c);
        by_name.insert(c.to_string(), Rc::clone(&child));
        order.push(child);
    }
    for n in &order {
        println!("{}", path(n));
    }
}

Exercise 2 · quiz

Count the references

let a = Rc::new(5);
let b = Rc::clone(&a);
let w1 = Rc::downgrade(&a);
let w2 = Weak::clone(&w1);
drop(b);

What are Rc::strong_count(&a) and Rc::weak_count(&a) now?

Answer

  • 1 and 2

Strong references: a and b; dropping b leaves 1. Weak references: w1 and w2, so 2. Only strong references keep the value alive: when the strong count reaches 0 the value is dropped even if weak references remain; their upgrade() then returns None.

Exercise 3 · write code

Observing a dropped value

A cache holds Weak references to documents so it never keeps them alive by itself. Complete fn describe(entry: &Weak<String>) -> String returning "alive: TEXT" if the document still exists and "gone" otherwise (use upgrade). The given main prints:

alive: report
alive: notes
gone
alive: notes

File: main.rs

Starting point

use std::rc::{Rc, Weak};

fn describe(entry: &Weak<String>) -> String {
    String::new()
}

fn main() {
    let report = Rc::new(String::from("report"));
    let notes = Rc::new(String::from("notes"));
    let cache = vec![Rc::downgrade(&report), Rc::downgrade(&notes)];
    for e in &cache {
        println!("{}", describe(e));
    }
    drop(report);
    for e in &cache {
        println!("{}", describe(e));
    }
}

Example

expected output

alive: report
alive: notes
gone
alive: notes
Hint 1

match entry.upgrade() { Some(doc) => ..., None => ... }

Reference solution
use std::rc::{Rc, Weak};

fn describe(entry: &Weak<String>) -> String {
    match entry.upgrade() {
        Some(doc) => format!("alive: {doc}"),
        None => String::from("gone"),
    }
}

fn main() {
    let report = Rc::new(String::from("report"));
    let notes = Rc::new(String::from("notes"));
    let cache = vec![Rc::downgrade(&report), Rc::downgrade(&notes)];
    for e in &cache {
        println!("{}", describe(e));
    }
    drop(report);
    for e in &cache {
        println!("{}", describe(e));
    }
}