551 Intermediate

Rc and Weak for Shared Ownership

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Rc and Weak for Shared Ownership" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Tree and graph structures require nodes to reference each other, but reference cycles prevent reference-counted memory from being freed. Key difference from OCaml: 1. **Cycle handling**: Rust `Rc` cannot collect cycles — `Weak` breaks them; OCaml's tracing GC collects cycles of regular references without special handling.

Tutorial

The Problem

Tree and graph structures require nodes to reference each other, but reference cycles prevent reference-counted memory from being freed. A tree node holding a strong Rc reference to its parent and the parent holding a strong Rc to its children creates a cycle — the counts never reach zero. The solution: break cycles with Weak<T> — a non-owning reference that does not prevent deallocation. Rc::downgrade creates a Weak; weak.upgrade() returns Option<Rc<T>> — None if the target has been freed. This pattern is fundamental in GUI widget trees, DOM implementations, and doubly-linked lists.

🎯 Learning Outcomes

• How Rc<T> provides shared ownership with reference counting in single-threaded code

• Why Weak<T> breaks cycles: it does not increment the strong reference count

• How Rc::downgrade(parent) and weak.upgrade() work together

• How Rc<RefCell<T>> combines shared ownership with interior mutability for tree nodes

• Where this pattern appears: GUI trees, DOM, doubly-linked lists, observer patterns

Code Example

#![allow(clippy::all)]
//! Rc and Weak for Shared Ownership
//!
//! Reference counting with weak references.

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

/// Node in a tree with parent backpointer.
pub struct Node {
    pub value: i32,
    pub parent: RefCell<Weak<Node>>,
    pub children: RefCell<Vec<Rc<Node>>>,
}

impl Node {
    pub fn new(value: i32) -> Rc<Self> {
        Rc::new(Node {
            value,
            parent: RefCell::new(Weak::new()),
            children: RefCell::new(Vec::new()),
        })
    }

    pub fn add_child(parent: &Rc<Node>, child: Rc<Node>) {
        *child.parent.borrow_mut() = Rc::downgrade(parent);
        parent.children.borrow_mut().push(child);
    }

    pub fn parent(&self) -> Option<Rc<Node>> {
        self.parent.borrow().upgrade()
    }
}

/// Simple shared data.
pub fn shared_data_demo() -> (Rc<String>, Rc<String>) {
    let data = Rc::new(String::from("shared"));
    let clone1 = Rc::clone(&data);
    let clone2 = Rc::clone(&data);
    (clone1, clone2)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_shared_data() {
        let (a, b) = shared_data_demo();
        assert_eq!(*a, "shared");
        assert_eq!(*b, "shared");
        assert!(Rc::ptr_eq(&a, &b));
    }

    #[test]
    fn test_node_tree() {
        let root = Node::new(1);
        let child = Node::new(2);
        Node::add_child(&root, child.clone());

        assert_eq!(root.children.borrow().len(), 1);
        assert_eq!(child.parent().unwrap().value, 1);
    }

    #[test]
    fn test_weak_upgrade() {
        let strong = Rc::new(42);
        let weak = Rc::downgrade(&strong);
        assert_eq!(*weak.upgrade().unwrap(), 42);
        drop(strong);
        assert!(weak.upgrade().is_none());
    }
}

(* Rc/Weak analog in OCaml — GC handles cycles automatically *)
(* Tree with parent pointers — OCaml GC handles the cycle *)
type tree_node = {
  value: int;
  children: tree_node list ref;
  (* parent: tree_node option ref would create cycle — GC handles it *)
}

let make_node v = { value = v; children = ref [] }
let add_child parent child =
  parent.children := child :: !(parent.children)

let () =
  let root = make_node 1 in
  let child1 = make_node 2 in
  let child2 = make_node 3 in
  add_child root child1;
  add_child root child2;
  Printf.printf "root has %d children\n" (List.length !(root.children));
  List.iter (fun c -> Printf.printf "  child value: %d\n" c.value) !(root.children)

Key Differences

Cycle handling: Rust Rc cannot collect cycles — Weak breaks them; OCaml's tracing GC collects cycles of regular references without special handling.

Upgrade cost: weak.upgrade() is an atomic compare-and-increment; OCaml Weak.get checks liveness via the GC; both are O(1) but with different overhead.

Explicit cycle breaking: Rust programs must consciously choose which direction of a bidirectional relationship uses Weak; OCaml programs can use strong references in both directions.

Arc vs Rc: For multi-threaded code, Rust uses Arc<Mutex<T>> with Arc::downgrade; OCaml uses Mutex.t and GC-managed values in OCaml 5.x domains.

OCaml Approach

OCaml's GC handles cycles automatically — no weak references needed for simple tree structures. The GC can collect cycles of ref-connected values. Weak references exist in OCaml (Weak module) for cache-like use cases where you want GC to collect entries:

type 'a node = { value: 'a; parent: 'a node option ref; children: 'a node list ref }
(* Cycles are handled by GC — no Weak needed for correctness *)

Full Source

#![allow(clippy::all)]
//! Rc and Weak for Shared Ownership
//!
//! Reference counting with weak references.

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

/// Node in a tree with parent backpointer.
pub struct Node {
    pub value: i32,
    pub parent: RefCell<Weak<Node>>,
    pub children: RefCell<Vec<Rc<Node>>>,
}

impl Node {
    pub fn new(value: i32) -> Rc<Self> {
        Rc::new(Node {
            value,
            parent: RefCell::new(Weak::new()),
            children: RefCell::new(Vec::new()),
        })
    }

    pub fn add_child(parent: &Rc<Node>, child: Rc<Node>) {
        *child.parent.borrow_mut() = Rc::downgrade(parent);
        parent.children.borrow_mut().push(child);
    }

    pub fn parent(&self) -> Option<Rc<Node>> {
        self.parent.borrow().upgrade()
    }
}

/// Simple shared data.
pub fn shared_data_demo() -> (Rc<String>, Rc<String>) {
    let data = Rc::new(String::from("shared"));
    let clone1 = Rc::clone(&data);
    let clone2 = Rc::clone(&data);
    (clone1, clone2)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_shared_data() {
        let (a, b) = shared_data_demo();
        assert_eq!(*a, "shared");
        assert_eq!(*b, "shared");
        assert!(Rc::ptr_eq(&a, &b));
    }

    #[test]
    fn test_node_tree() {
        let root = Node::new(1);
        let child = Node::new(2);
        Node::add_child(&root, child.clone());

        assert_eq!(root.children.borrow().len(), 1);
        assert_eq!(child.parent().unwrap().value, 1);
    }

    #[test]
    fn test_weak_upgrade() {
        let strong = Rc::new(42);
        let weak = Rc::downgrade(&strong);
        assert_eq!(*weak.upgrade().unwrap(), 42);
        drop(strong);
        assert!(weak.upgrade().is_none());
    }
}

(* Rc/Weak analog in OCaml — GC handles cycles automatically *)
(* Tree with parent pointers — OCaml GC handles the cycle *)
type tree_node = {
  value: int;
  children: tree_node list ref;
  (* parent: tree_node option ref would create cycle — GC handles it *)
}

let make_node v = { value = v; children = ref [] }
let add_child parent child =
  parent.children := child :: !(parent.children)

let () =
  let root = make_node 1 in
  let child1 = make_node 2 in
  let child2 = make_node 3 in
  add_child root child1;
  add_child root child2;
  Printf.printf "root has %d children\n" (List.length !(root.children));
  List.iter (fun c -> Printf.printf "  child value: %d\n" c.value) !(root.children)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_shared_data() {
        let (a, b) = shared_data_demo();
        assert_eq!(*a, "shared");
        assert_eq!(*b, "shared");
        assert!(Rc::ptr_eq(&a, &b));
    }

    #[test]
    fn test_node_tree() {
        let root = Node::new(1);
        let child = Node::new(2);
        Node::add_child(&root, child.clone());

        assert_eq!(root.children.borrow().len(), 1);
        assert_eq!(child.parent().unwrap().value, 1);
    }

    #[test]
    fn test_weak_upgrade() {
        let strong = Rc::new(42);
        let weak = Rc::downgrade(&strong);
        assert_eq!(*weak.upgrade().unwrap(), 42);
        drop(strong);
        assert!(weak.upgrade().is_none());
    }
}

Deep Comparison

OCaml vs Rust: lifetime rc weak

See example.rs and example.ml for implementations.

Key Differences

OCaml uses garbage collection

Rust uses ownership and borrowing

Both support the core concept

Exercises

Graph with cycles: Implement a directed graph using HashMap<usize, Rc<RefCell<GraphNode>>> where each node holds Vec<Weak<RefCell<GraphNode>>> edges to prevent retain cycles.

Observer cleanup: Build an observable value using Vec<Weak<dyn Fn(&T)>> for listeners — when the listener is dropped, its Weak returns None and is automatically removed from the list.

Drop order verification: Create a parent node and two children, then drop the parent first — verify (using a Drop impl with println!) that the children are also dropped despite the parent backpointer.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust