108 Intermediate

Rc\<T\> — Shared Ownership

Memory ManagementSmart Pointers

Tutorial Video

Text description (accessibility)

This video demonstrates the "Rc\<T\> — Shared Ownership" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Memory Management, Smart Pointers. Implement data structures (a binary tree and a shared-tail cons list) where multiple owners reference the same node, using `Rc<T>` for explicit, single-threaded reference counting. Key difference from OCaml: 1. **Sharing by default vs opt

Tutorial

The Problem

Implement data structures (a binary tree and a shared-tail cons list) where multiple owners reference the same node, using Rc<T> for explicit, single-threaded reference counting.

🎯 Learning Outcomes

• How Rc<T> provides multiple ownership without a garbage collector

• Rc::clone increments a reference count cheaply — no heap allocation

• Rc::strong_count lets you observe liveness at runtime

• Values are freed automatically when the last Rc drops — deterministic, not GC

🦀 The Rust Way

Rust's default ownership model gives each value exactly one owner and drops it at end of scope. Rc<T> opts into shared ownership: Rc::clone returns a new handle that shares the allocation. When the last handle is dropped, the inner value is freed. This is single-threaded only — use Arc<T> for multi-threaded sharing.

Code Example

use std::rc::Rc;

let shared = Rc::new(Tree::Node(Rc::new(Tree::Leaf), 42, Rc::new(Tree::Leaf)));
// Rc::clone bumps the reference count — O(1), no heap allocation
let tree1 = Tree::Node(Rc::clone(&shared), 1, Rc::new(Tree::Leaf));
let tree2 = Tree::Node(Rc::new(Tree::Leaf), 2, Rc::clone(&shared));
// shared strong_count == 3 here; freed when all three drop

(* Sharing is implicit — no annotation needed *)
type tree = Leaf | Node of tree * int * tree

let shared = Node (Leaf, 42, Leaf)
let tree1  = Node (shared, 1, Leaf)   (* GC keeps shared alive *)
let tree2  = Node (Leaf, 2, shared)   (* GC keeps shared alive *)

(* Shared-tail list — tail is never copied *)
let tail   = [3; 2; 1]
let list_a = 10 :: tail
let list_b = 20 :: tail

Key Differences

Sharing by default vs opt-in: OCaml shares all heap values automatically; Rust requires explicit Rc::new and Rc::clone.

Visibility: OCaml's reference count is invisible; Rust exposes Rc::strong_count for inspection and reasoning.

Drop timing: OCaml's GC may defer collection; Rust's Rc drops deterministically the moment the last owner goes out of scope.

Thread safety: OCaml's GC handles concurrent access; Rust's Rc is intentionally !Send — use Arc across threads.

OCaml Approach

OCaml's GC manages all heap values implicitly. Any binding to a value increments an internal reference count (or marks it live for the major GC). Sharing is the default: let shared = ... followed by two uses is simply two pointers to the same node — no special syntax needed. Liveness is invisible to the programmer.

Full Source

#![allow(clippy::all)]
// Example 108: Rc<T> — Shared Ownership
//
// Rc<T> = Reference Counted pointer. Multiple owners, single-threaded.
// OCaml shares all values implicitly via GC; Rust makes you opt in explicitly.

use std::rc::Rc;

// --- Approach 1: Shared tree nodes ----------------------------------------

// A binary tree where subtrees are shared via Rc.
// Cloning an Rc only bumps a counter — no heap allocation.
#[derive(Debug)]
pub enum Tree {
    Leaf,
    Node(Rc<Tree>, i32, Rc<Tree>),
}

pub fn tree_sum(t: &Tree) -> i32 {
    match t {
        Tree::Leaf => 0,
        Tree::Node(l, v, r) => tree_sum(l) + v + tree_sum(r),
    }
}

/// Build two trees that share a common subtree.
/// Returns (tree1_sum, tree2_sum, strong_count_of_shared_node).
pub fn shared_tree_demo() -> (i32, i32, usize) {
    // shared subtree: Node(Leaf, 42, Leaf)
    let shared = Rc::new(Tree::Node(Rc::new(Tree::Leaf), 42, Rc::new(Tree::Leaf)));

    // tree1 = Node(shared, 1, Leaf)  → sum = 42 + 1 = 43
    let tree1 = Tree::Node(Rc::clone(&shared), 1, Rc::new(Tree::Leaf));
    // tree2 = Node(Leaf, 2, shared)  → sum = 2 + 42 = 44
    let tree2 = Tree::Node(Rc::new(Tree::Leaf), 2, Rc::clone(&shared));

    let s1 = tree_sum(&tree1);
    let s2 = tree_sum(&tree2);
    // shared + tree1's Rc + tree2's Rc = 3 strong references
    let count = Rc::strong_count(&shared);
    (s1, s2, count)
}

// --- Approach 2: Reference-counted linked list (cons list) -----------------

// An immutable singly-linked list where tails are shared.
// Classic functional data structure: O(1) prepend, shared tails.
#[derive(Debug)]
pub enum List<T> {
    Nil,
    Cons(T, Rc<List<T>>),
}

impl<T: Copy> List<T> {
    pub fn nil() -> Rc<Self> {
        Rc::new(List::Nil)
    }

    /// Prepend `head` to `tail`, sharing `tail` without cloning its contents.
    pub fn cons(head: T, tail: Rc<Self>) -> Rc<Self> {
        Rc::new(List::Cons(head, tail))
    }

    pub fn to_vec(list: &Rc<Self>) -> Vec<T> {
        let mut acc = Vec::new();
        let mut cur = Rc::clone(list);
        loop {
            match cur.as_ref() {
                List::Nil => break,
                List::Cons(h, t) => {
                    acc.push(*h);
                    cur = Rc::clone(t);
                }
            }
        }
        acc
    }
}

/// Build a shared-tail cons list demo.
/// Returns (list_a, list_b) where both share the same tail [3, 2, 1].
pub fn shared_list_demo() -> (Vec<i32>, Vec<i32>, usize) {
    //  shared tail: [3, 2, 1]
    let tail = {
        let nil = List::nil();
        let t1 = List::cons(1, nil);
        let t2 = List::cons(2, t1);
        List::cons(3, t2)
    };

    // list_a = [10, 3, 2, 1]
    let list_a = List::cons(10, Rc::clone(&tail));
    // list_b = [20, 3, 2, 1]
    let list_b = List::cons(20, Rc::clone(&tail));

    let count = Rc::strong_count(&tail); // tail + list_a's Rc + list_b's Rc = 3
    (List::to_vec(&list_a), List::to_vec(&list_b), count)
}

// --- Approach 3: Rc drop semantics ----------------------------------------

/// Demonstrates that the value is dropped exactly when the last Rc is gone.
/// Returns strong_count at each stage: (after_clone, after_drop_one).
pub fn rc_drop_demo() -> (usize, usize) {
    let a = Rc::new(vec![1, 2, 3]);
    let b = Rc::clone(&a);
    let count_before = Rc::strong_count(&a); // 2

    drop(b); // decrement — not freed yet
    let count_after = Rc::strong_count(&a); // 1
                                            // `a` drops at end of scope — value is freed here
    (count_before, count_after)
}

// --------------------------------------------------------------------------

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

    #[test]
    fn test_shared_tree_sums() {
        let (s1, s2, _) = shared_tree_demo();
        assert_eq!(s1, 43); // shared(42) + 1
        assert_eq!(s2, 44); // 2 + shared(42)
    }

    #[test]
    fn test_shared_tree_ref_count() {
        let (_, _, count) = shared_tree_demo();
        // `shared` + tree1's Rc::clone + tree2's Rc::clone = 3
        assert_eq!(count, 3);
    }

    #[test]
    fn test_shared_list_contents() {
        let (a, b, _) = shared_list_demo();
        assert_eq!(a, vec![10, 3, 2, 1]);
        assert_eq!(b, vec![20, 3, 2, 1]);
    }

    #[test]
    fn test_shared_list_ref_count() {
        let (_, _, count) = shared_list_demo();
        // tail itself + list_a holds a clone + list_b holds a clone = 3
        assert_eq!(count, 3);
    }

    #[test]
    fn test_rc_drop_semantics() {
        let (before, after) = rc_drop_demo();
        assert_eq!(before, 2);
        assert_eq!(after, 1);
    }

    #[test]
    fn test_tree_leaf_sum_is_zero() {
        assert_eq!(tree_sum(&Tree::Leaf), 0);
    }

    #[test]
    fn test_single_node_tree() {
        let t = Tree::Node(Rc::new(Tree::Leaf), 7, Rc::new(Tree::Leaf));
        assert_eq!(tree_sum(&t), 7);
    }

    #[test]
    fn test_list_nil_is_empty() {
        let nil: Rc<List<i32>> = List::nil();
        assert_eq!(List::to_vec(&nil), Vec::<i32>::new());
    }
}

(* Example 108: Rc<T> — OCaml Default Sharing → Rust Explicit Rc *)

(* In OCaml, all heap values are GC-managed. Multiple bindings to the
   same value is the default — no annotation needed. *)

(* Approach 1: Shared tree nodes — implicit in OCaml *)
type tree = Leaf | Node of tree * int * tree

let rec tree_sum = function
  | Leaf -> 0
  | Node (l, v, r) -> tree_sum l + v + tree_sum r

let shared_tree_demo () =
  let shared = Node (Leaf, 42, Leaf) in
  (* Both trees reference the same `shared` node — GC tracks liveness *)
  let tree1 = Node (shared, 1, Leaf) in
  let tree2 = Node (Leaf, 2, shared) in
  (tree_sum tree1, tree_sum tree2)

(* Approach 2: Shared-tail cons list *)
(* In OCaml, list tails are implicitly shared when you pattern-match *)
let make_shared_lists () =
  let tail = [3; 2; 1] in
  let list_a = 10 :: tail in
  let list_b = 20 :: tail in
  (list_a, list_b)

let () =
  let (s1, s2) = shared_tree_demo () in
  Printf.printf "tree1 sum = %d, tree2 sum = %d\n" s1 s2;
  assert (s1 = 43);
  assert (s2 = 44);

  let (a, b) = make_shared_lists () in
  assert (a = [10; 3; 2; 1]);
  assert (b = [20; 3; 2; 1]);

  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_shared_tree_sums() {
        let (s1, s2, _) = shared_tree_demo();
        assert_eq!(s1, 43); // shared(42) + 1
        assert_eq!(s2, 44); // 2 + shared(42)
    }

    #[test]
    fn test_shared_tree_ref_count() {
        let (_, _, count) = shared_tree_demo();
        // `shared` + tree1's Rc::clone + tree2's Rc::clone = 3
        assert_eq!(count, 3);
    }

    #[test]
    fn test_shared_list_contents() {
        let (a, b, _) = shared_list_demo();
        assert_eq!(a, vec![10, 3, 2, 1]);
        assert_eq!(b, vec![20, 3, 2, 1]);
    }

    #[test]
    fn test_shared_list_ref_count() {
        let (_, _, count) = shared_list_demo();
        // tail itself + list_a holds a clone + list_b holds a clone = 3
        assert_eq!(count, 3);
    }

    #[test]
    fn test_rc_drop_semantics() {
        let (before, after) = rc_drop_demo();
        assert_eq!(before, 2);
        assert_eq!(after, 1);
    }

    #[test]
    fn test_tree_leaf_sum_is_zero() {
        assert_eq!(tree_sum(&Tree::Leaf), 0);
    }

    #[test]
    fn test_single_node_tree() {
        let t = Tree::Node(Rc::new(Tree::Leaf), 7, Rc::new(Tree::Leaf));
        assert_eq!(tree_sum(&t), 7);
    }

    #[test]
    fn test_list_nil_is_empty() {
        let nil: Rc<List<i32>> = List::nil();
        assert_eq!(List::to_vec(&nil), Vec::<i32>::new());
    }
}

Deep Comparison

OCaml vs Rust: Rc\<T\> — Shared Ownership

Side-by-Side Code

OCaml

(* Sharing is implicit — no annotation needed *)
type tree = Leaf | Node of tree * int * tree

let shared = Node (Leaf, 42, Leaf)
let tree1  = Node (shared, 1, Leaf)   (* GC keeps shared alive *)
let tree2  = Node (Leaf, 2, shared)   (* GC keeps shared alive *)

(* Shared-tail list — tail is never copied *)
let tail   = [3; 2; 1]
let list_a = 10 :: tail
let list_b = 20 :: tail

Rust (idiomatic — Rc for shared ownership)

use std::rc::Rc;

let shared = Rc::new(Tree::Node(Rc::new(Tree::Leaf), 42, Rc::new(Tree::Leaf)));
// Rc::clone bumps the reference count — O(1), no heap allocation
let tree1 = Tree::Node(Rc::clone(&shared), 1, Rc::new(Tree::Leaf));
let tree2 = Tree::Node(Rc::new(Tree::Leaf), 2, Rc::clone(&shared));
// shared strong_count == 3 here; freed when all three drop

Rust (functional — shared-tail cons list)

let tail   = List::cons(3, List::cons(2, List::cons(1, List::nil())));
let list_a = List::cons(10, Rc::clone(&tail));  // shares tail
let list_b = List::cons(20, Rc::clone(&tail));  // shares tail
// tail strong_count == 3; inner nodes never copied

Type Signatures

Concept	OCaml	Rust
Shared pointer	`'a` (implicit GC)	`Rc<T>`
Clone a handle	`let b = a` (implicit)	`Rc::clone(&a)`
Reference count	hidden	`Rc::strong_count(&a) : usize`
Drop	GC-determined	deterministic on last drop
Thread safety	GC-managed	`Rc` is `!Send`; use `Arc` for threads

Key Insights

Opt-in sharing: Rust's Rc<T> makes shared ownership visible in the type. Every Rc::clone call is a deliberate decision — no hidden aliases.

Zero-cost clone: Rc::clone only increments an integer counter; the data on the heap is not copied. This matches OCaml's pointer-copy semantics.

Deterministic drop: Unlike OCaml's GC, Rc frees memory the moment the last handle is dropped — useful for resources like file handles or locks inside an Rc.

No cycles: Rc cannot break reference cycles on its own; use Weak<T> for back-pointers to avoid leaking memory — a trade-off OCaml's GC avoids.

Single-threaded only: Rc<T> is not Send; the compiler prevents accidental sharing across threads. Arc<T> uses atomic operations for the same pattern in multi-threaded code.

When to Use Each Style

**Use Rc<T> when:** you genuinely need multiple owners in single-threaded code — shared tree nodes, immutable cons lists, reference-counted caches, or parent/child GUI widgets.

**Use plain references (&T) when:** you only need temporary access and the lifetime is clear — prefer borrows over Rc for zero-overhead sharing.

Exercises

Build a simple directed graph using Rc<RefCell<Node>> where each node holds a label and a list of neighbor references, then implement a DFS traversal.

Implement a basic observer pattern using Rc<dyn Fn(Event)> callbacks: register multiple observers on an event source and fire them all when an event occurs.

Demonstrate the Rc cycle problem by creating two nodes that reference each other, confirm the memory leak using a Drop impl, then fix it using Weak<T>.

Open Source Repos

functional-rust

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

Rust