🎬 Rust Ownership in 30 seconds Visual walkthrough of ownership, moves, and automatic memory management.

📝 Text version (for readers / accessibility)

• Each value in Rust has exactly one owner — when the owner goes out of scope, the value is dropped

• Assignment moves ownership by default; the original binding becomes invalid

• Borrowing (&T / &mut T) lets you reference data without taking ownership

• The compiler enforces: many shared references OR one mutable reference, never both

• No garbage collector needed — memory is freed deterministically at scope exit

551: Rc and Weak for Cycles

Difficulty: 4 Level: Advanced Break reference cycles with non-owning weak pointers.

The Problem This Solves

`Rc<T>` uses reference counting: when the count reaches zero, the value is dropped. This works perfectly for trees where ownership flows in one direction. But add a back-pointer — a child holding a reference to its parent — and you have a cycle. Both sides keep the other's count above zero. Neither ever drops. You have a memory leak. This problem appears in every bidirectional data structure: trees with parent pointers, doubly-linked lists, observer patterns where subjects know about their observers, and graph nodes that reference neighbors. In garbage-collected languages, the GC handles cycles. In Rust's ownership model, you need to break cycles explicitly. `Weak<T>` is a non-owning reference: it doesn't increment the strong count. You create one with `Rc::downgrade(&rc)`. When all strong `Rc<T>` references drop, the value is deallocated — even if `Weak<T>` references remain. Those weak refs become "dead": `weak.upgrade()` returns `None`. This makes the pattern explicit: the owner holds a strong `Rc`, the back-pointer holds a `Weak`.

The Intuition

Think of `Rc` as owning a house and `Weak` as having a key to it. Owning the house keeps it standing. Holding a key doesn't. Once all the owners sell and the house is demolished, your key opens nothing — `upgrade()` returns `None`. The key doesn't prevent demolition. In a tree: parent owns its children (`Rc`). Children have a key to their parent (`Weak`). The tree is alive as long as someone holds the root. Drop the root, everything falls.

How It Works in Rust

1. Downgrade to weak — `Rc::downgrade(&strong)` creates a `Weak<T>` without incrementing the strong count. 2. Upgrade to check liveness — `weak.upgrade()` returns `Option<Rc<T>>`: `Some` if the value is still alive, `None` if it was dropped. 3. Tree parent pattern — parent field is `Option<Weak<RefCell<Node>>>`: weak because children don't own their parent. 4. Reference count inspection — `Rc::strong_count(&rc)` and `Rc::weak_count(&rc)` let you observe the counts; useful for debugging cycles. 5. Cycle prevention check — wrap in a block: create `Rc`, downgrade to `Weak`, drop the `Rc`; `upgrade()` then returns `None`, confirming no cycle.

What This Unlocks

Build bidirectional tree and graph structures without memory leaks.
Implement observer/listener patterns where subjects don't own their observers.
Reason precisely about object lifetimes in data structures with back-references.

Key Differences

Concept	OCaml	Rust
Shared ownership	GC; no explicit reference counting	`Rc<T>`: single-threaded reference counting
Cycles	GC detects and collects cycles	`Rc` leaks cycles; must use `Weak` to break them
Non-owning reference	Mutable weak refs via `Weak` module or custom	`Weak<T>`: explicit non-owning handle; `upgrade()` → `Option`
Back-pointers in trees	Record field; GC handles liveness	`Option<Weak<RefCell<Node>>>`: explicit, non-owning

//! # 551. Rc and Weak for Cycles
//! Breaking reference cycles with weak references.

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

/// Tree node: parent owns children (Rc), children reference parent (Weak)
#[derive(Debug)]
struct TreeNode {
    value: i32,
    parent: Option<Weak<RefCell<TreeNode>>>,
    children: Vec<Rc<RefCell<TreeNode>>>,
}

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

    fn add_child(
        parent: &Rc<RefCell<TreeNode>>,
        child: Rc<RefCell<TreeNode>>,
    ) {
        // Child gets weak ref to parent (avoids cycle)
        child.borrow_mut().parent = Some(Rc::downgrade(parent));
        // Parent owns child (strong Rc)
        parent.borrow_mut().children.push(child);
    }

    fn parent_value(&self) -> Option<i32> {
        self.parent.as_ref()?.upgrade().map(|p| p.borrow().value)
    }
}

/// Doubly-linked list with Weak for back-links
struct ListNode<T> {
    value: T,
    next: Option<Rc<RefCell<ListNode<T>>>>,
    prev: Option<Weak<RefCell<ListNode<T>>>>, // weak to break cycle
}

impl<T: std::fmt::Display> ListNode<T> {
    fn new(value: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(ListNode { value, next: None, prev: None }))
    }
}

/// Show Rc/Weak reference counting
fn reference_counting_demo() {
    let a = Rc::new(5i32);
    println!("strong count after creating a: {}", Rc::strong_count(&a));

    let b = Rc::clone(&a);
    println!("strong count after cloning b: {}", Rc::strong_count(&a));

    let weak_a = Rc::downgrade(&a);
    println!("strong count after downgrade: {}", Rc::strong_count(&a));
    println!("weak count: {}", Rc::weak_count(&a));

    // Weak::upgrade returns Option — None after strong refs drop
    println!("upgrade: {:?}", weak_a.upgrade());
    drop(a);
    drop(b);
    println!("upgrade after drops: {:?}", weak_a.upgrade()); // None!
}

fn main() {
    println!("=== Tree with parent Weak refs ===");
    let root = TreeNode::new(1);
    let child1 = TreeNode::new(2);
    let child2 = TreeNode::new(3);
    let grandchild = TreeNode::new(4);

    TreeNode::add_child(&root, child1.clone());
    TreeNode::add_child(&root, child2.clone());
    TreeNode::add_child(&child1, grandchild.clone());

    println!("root children: {}", root.borrow().children.len());
    println!("child1 parent: {:?}", child1.borrow().parent_value());
    println!("grandchild parent: {:?}", grandchild.borrow().parent_value());

    // Drop root — children's Weak<parent> becomes invalid
    println!("strong count of root: {}", Rc::strong_count(&root));
    drop(root); // drops strong count — but child1 and child2 still hold it...
    // Actually: root strong_count = 1 (only root var), dropping it goes to 0

    println!("\n=== Reference counting demo ===");
    reference_counting_demo();

    // Cycle prevention: demonstrate Weak becomes None
    let outer;
    {
        let inner = Rc::new(42i32);
        outer = Rc::downgrade(&inner);
        println!("upgrade inside: {:?}", outer.upgrade());
    } // inner dropped here
    println!("upgrade after inner dropped: {:?}", outer.upgrade()); // None
}

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

    #[test]
    fn test_rc_strong_count() {
        let a = Rc::new(1i32);
        let b = a.clone();
        assert_eq!(Rc::strong_count(&a), 2);
        drop(b);
        assert_eq!(Rc::strong_count(&a), 1);
    }

    #[test]
    fn test_weak_upgrades_to_none_after_drop() {
        let weak;
        {
            let strong = Rc::new(42i32);
            weak = Rc::downgrade(&strong);
            assert!(weak.upgrade().is_some());
        }
        assert!(weak.upgrade().is_none());
    }

    #[test]
    fn test_tree_parent_ref() {
        let root = TreeNode::new(10);
        let child = TreeNode::new(20);
        TreeNode::add_child(&root, child.clone());
        assert_eq!(child.borrow().parent_value(), Some(10));
    }
}

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