Reinventing From Scratch — Rc<T>

Chapter 1 — A Mental Model (Strong vs Weak)

Rc<T> is a shared ownership smart pointer designed for single-threaded code. Its strong references keep the value alive; its weak references keep the allocation alive so that upgrades can succeed or fail deterministically.

1.1 Two lifetimes, one block

Value lifetime: as long as strong > 0, the T in the block is alive and fully initialized.
Allocation lifetime: as long as strong + weak > 0, the memory block containing the header and T remains allocated.

      Rc<T> handles (N)              Weak<T> handles (M)
     ┌─────────┴─────────┐              ┌───────┴───────┐
     ▼                   ▼              ▼               ▼
  [ header: strong=N, weak=M+1 | value: T ]
                      ▲
               implicit weak (1)

The implicit weak is central: when the first Rc is created, weak starts at 1. This single “weak slot” is owned by the strong regime to represent that the allocation itself is still in use while strong references exist. When the last strong goes away, we drop T and consume that implicit weak (decrement weak); if that brings weak to zero, we deallocate the block right away.

1.2 Why not a single counter?

A single counter can’t represent “allocation without value.” We need Weak to outlive T so that upgrade() can fail gracefully (returning None instead of accessing freed memory). Thus, two counters:

strong: owns T
weak: owns the allocation post-T-drop (plus implicit weak while strongs exist)

1.3 Why is `Rc<T>` !Send and !Sync?

Because the counters are mutated with Cell<usize>, which is non-atomic and not thread-safe. This makes Rc fast (no atomics) but confined to a single thread. Multi-threaded shared ownership uses Arc<T> with atomics.

1.4 When to use `Rc<T>`

Trees/graphs in GUIs and game engines where nodes have multiple owners on one thread.
Caches and interning tables scoped to one event loop.
Sharing large constants across components on one thread.

1.5 When not to use

Cross-thread sharing (use Arc<T>).
Lifetimes that naturally fit the borrow checker (prefer &/&mut when possible).
Cyclic graphs without a break: use Weak for back-edges or strong cycles will leak.

1.6 A precise invariant sheet

While strong > 0: T is initialized and safe to reference.
When strong transitions to 0: drop T exactly once, decrement weak once (consuming the implicit weak).
After strong == 0: T is gone; header may remain until weak == 0.
Allocation is freed only when strong == 0 && weak == 0.

Understanding these rules is the key to implementing clone, drop, downgrade, and upgrade correctly without leaks or use-after-free.

Notes & Asides

Reference counting is deceptively simple: increments are easy; decrements must be exact.
Always document the invariants in prose before writing unsafe code.
Prefer small, focused unsafe blocks. Keep them near proofs.
Think in two layers: value lifetime (strong) vs allocation lifetime (weak).
Keep an eye on aliasing: shared references to interior-mutable fields are still mediated by Cell.

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

We maintain the following invariants for every allocation of RcBox<T>:

I1 (Header Validity): The fields strong and weak are valid usize counters that never underflow or overflow.
I2 (Value Liveness): value: T is initialized iff strong > 0. Equivalently, strong == 0 implies value has been dropped.
I3 (Allocation Liveness): The allocation is considered live iff strong + weak > 0.
I4 (Implicit Weak): While strong > 0, the weak counter includes an implicit unit that represents the allocation’s ownership by the strong regime. When strong becomes 0, we consume exactly one unit from weak.
I5 (Deallocation Condition): The allocation is deallocated iff strong == 0 && weak == 0.
I6 (Alias Soundness): get_mut only returns &mut T when strong == 1. No two &mut T aliases may exist simultaneously.
I7 (Upgrade Correctness): Weak::upgrade() returns Some iff it can soundly increment strong (i.e., strong > 0 at the time of the increment). Otherwise it returns None without touching memory after deallocation.

These invariants are checked conceptually at every mutating operation: clone, drop, downgrade, upgrade, get_mut, and try_unwrap.

B. Proof Sketches

B.1 Single Drop of value

Let S be the number of strong owners. Only when S transitions from 1 to 0 do we call drop_in_place(value).
After the transition, value is logically absent (I2). No future path calls drop_in_place(value) again because all other Drop paths observe S > 0 or S == 0 and skip value drop.
Therefore the destructor of T runs exactly once.

B.2 No Use-After-Free in upgrade

The allocation is freed only when S == 0 && W == 0 (I5).
upgrade first reads S. If S == 0, it returns None and does not dereference value nor mutate S.
If S > 0, it increments S before producing a MyRc<T>. Since writes to Cell are instantaneous w.r.t. this single-threaded model, either the increment happens first (then we are safe) or a concurrent decrement is impossible (no multi-threading). Hence no racing free occurs.

B.3 Safety of get_mut

get_mut requires unique strong ownership (S == 1) to produce &mut T. If a second Rc existed, S would be greater than 1 and the method would refuse, preserving aliasing guarantees (I6).

C. Panic Safety Considerations

Destructors should not panic. If they do, Rust aborts during unwinding-from-unwinding; our model does not attempt to recover from double-panics.
Construction is panic-safe because allocation and initialization happen in a single ptr::write of RcBox<T>; if panic occurs before storing, the program has not published the pointer.
Reduction operations (drop) use explicit branches and avoid underflow; we do not use saturating arithmetic to prevent masking logic errors.

D. Edge Cases

Degenerate types: For T = () or other ZSTs, headers still exist and counts still function; the value drop is a no-op, but the ordering invariants remain required.
Self-referential graphs: Rc<T> does not move T in memory; address stability is preserved, but cycles still leak. Use Weak for back-edges.
ptr_eq and multiple allocations: ptr_eq only answers whether two Rcs refer to the same allocation, not whether T values are equal by PartialEq.

E. Micro-bench Hints

Cloning is a single Cell increment; microbench with criterion across hot loops.
Avoid creating/dropping Weak in tight loops unless necessary; it touches weak each time.
Prefer get_mut or try_unwrap when ownership is unique; it skips reference-cell borrow machinery.

Worked Example: A Tiny Tree with Parent Weak Links

use std::cell::{RefCell};
#[derive(Debug)]
struct Node {
    name: String,
    parent: RefCell<MyWeak<Node>>,
    children: RefCell<Vec<MyRc<Node>>>,
}

fn make_node(name: &str) -> MyRc<Node> {
    MyRc::new(Node {
        name: name.into(),
        parent: RefCell::new(MyRc::downgrade(&MyRc::new(Node{name:String::new(), parent:RefCell::new(MyWeak{ptr: unsafe{std::mem::transmute(1usize)}, _marker: std::marker::PhantomData}}, children: RefCell::new(vec![])}))), // placeholder, replaced on adopt
        children: RefCell::new(vec![]),
    })
}

// Helper: adopt `child` into `parent` (strong), set child's parent (weak)
fn adopt(parent: &MyRc<Node>, child: &MyRc<Node>) {
    *child.parent.borrow_mut() = MyRc::downgrade(parent);
    parent.children.borrow_mut().push(child.clone());
}

The above uses a placeholder trick to satisfy the compiler in an example-only context; in production you would construct nodes in two phases or use Default and then set links.

Walkthrough

Create root, child1, child2 as MyRc<Node>.
Call adopt(&root, &child1) and adopt(&root, &child2).
Dropping root eventually drops both children once nothing else points at them strongly; their parent fields are Weak and do not retain the tree.

Debugging Playbook

Symptom: Allocation never freed.
Check: Did you forget to consume the implicit weak when last strong dropped? Are there outstanding Weak?
Symptom: Double free on last Weak.
Check: Did you decrement weak both on the last-strong path and again in Weak::drop without the implicit-weak protocol?
Symptom: Use-after-free in upgrade.
Check: Are you freeing the allocation while weak > 0? Did you deallocate before decrementing the very last weak?
Symptom: UB in get_mut.
Check: Ensure you only return &mut T when strong == 1 at the exact time of check. Avoid creating &mut across code that might clone another Rc.

FAQ (Extended)

Q: Why not store counts adjacent to each strong handle, like a decentralized RC?
A: It complicates synchronization even in single-threaded contexts and makes upgrade semantics unclear. Centralized counts in a header give one source of truth.

Q: Can I make Rc<T> Send if T: Send?
A: Not without atomics. The counters themselves would race; Arc<T> exists for this purpose.

Q: What about memory ordering on a single thread?
A: In single-threaded Rust, the memory model reduces to program order for Cell. We rely on the lack of concurrency, not on fences.

Q: Why does weak_count subtract 1 when strong > 0?
A: To hide the implicit weak from public observers and match std’s API expectations.

Q: Are overflow checks necessary?
A: Practically, you won’t reach usize::MAX strong references. We still use checked_add in educational code to make logic errors obvious.

Exercises (With Hints)

Design a make_cyclic_pair() that intentionally creates a leaking 2-node cycle.
Hint: Store strong references in each node’s next field; verify with drop logs that destructors never run.
Prove that try_unwrap is linear in the size of T.
Hint: It performs a single ptr::read of T and conditional deallocation; no per-field work beyond Drop of T is forced.
Implement Rc::make_mut that clones T on write if strong > 1.
Hint: This requires T: Clone and either temporary ownership or RefCell<T>.
Add debug assertions: ensure that on last-strong drop, strong == 1 and weak >= 1.
Hint: These can be debug_assert!s to avoid release-mode overhead.
Benchmark cloning vs upgrading using Criterion.
Hint: Hot loop with b.iter(|| { let _ = a.clone(); }) vs let _ = w.upgrade(); from a pre-made Weak.

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

We maintain the following invariants for every allocation of RcBox<T>:

I1 (Header Validity): The fields strong and weak are valid usize counters that never underflow or overflow.
I2 (Value Liveness): value: T is initialized iff strong > 0. Equivalently, strong == 0 implies value has been dropped.
I3 (Allocation Liveness): The allocation is considered live iff strong + weak > 0.
I4 (Implicit Weak): While strong > 0, the weak counter includes an implicit unit that represents the allocation’s ownership by the strong regime. When strong becomes 0, we consume exactly one unit from weak.
I5 (Deallocation Condition): The allocation is deallocated iff strong == 0 && weak == 0.
I6 (Alias Soundness): get_mut only returns &mut T when strong == 1. No two &mut T aliases may exist simultaneously.
I7 (Upgrade Correctness): Weak::upgrade() returns Some iff it can soundly increment strong (i.e., strong > 0 at the time of the increment). Otherwise it returns None without touching memory after deallocation.

These invariants are checked conceptually at every mutating operation: clone, drop, downgrade, upgrade, get_mut, and try_unwrap.

B. Proof Sketches

B.1 Single Drop of value

Let S be the number of strong owners. Only when S transitions from 1 to 0 do we call drop_in_place(value).
After the transition, value is logically absent (I2). No future path calls drop_in_place(value) again because all other Drop paths observe S > 0 or S == 0 and skip value drop.
Therefore the destructor of T runs exactly once.

B.2 No Use-After-Free in upgrade

The allocation is freed only when S == 0 && W == 0 (I5).
upgrade first reads S. If S == 0, it returns None and does not dereference value nor mutate S.
If S > 0, it increments S before producing a MyRc<T>. Since writes to Cell are instantaneous w.r.t. this single-threaded model, either the increment happens first (then we are safe) or a concurrent decrement is impossible (no multi-threading). Hence no racing free occurs.

B.3 Safety of get_mut

get_mut requires unique strong ownership (S == 1) to produce &mut T. If a second Rc existed, S would be greater than 1 and the method would refuse, preserving aliasing guarantees (I6).

C. Panic Safety Considerations

Destructors should not panic. If they do, Rust aborts during unwinding-from-unwinding; our model does not attempt to recover from double-panics.
Construction is panic-safe because allocation and initialization happen in a single ptr::write of RcBox<T>; if panic occurs before storing, the program has not published the pointer.
Reduction operations (drop) use explicit branches and avoid underflow; we do not use saturating arithmetic to prevent masking logic errors.

D. Edge Cases

Degenerate types: For T = () or other ZSTs, headers still exist and counts still function; the value drop is a no-op, but the ordering invariants remain required.
Self-referential graphs: Rc<T> does not move T in memory; address stability is preserved, but cycles still leak. Use Weak for back-edges.
ptr_eq and multiple allocations: ptr_eq only answers whether two Rcs refer to the same allocation, not whether T values are equal by PartialEq.

E. Micro-bench Hints

Cloning is a single Cell increment; microbench with criterion across hot loops.
Avoid creating/dropping Weak in tight loops unless necessary; it touches weak each time.
Prefer get_mut or try_unwrap when ownership is unique; it skips reference-cell borrow machinery.

Worked Example: A Tiny Tree with Parent Weak Links

use std::cell::{RefCell};
#[derive(Debug)]
struct Node {
    name: String,
    parent: RefCell<MyWeak<Node>>,
    children: RefCell<Vec<MyRc<Node>>>,
}

fn make_node(name: &str) -> MyRc<Node> {
    MyRc::new(Node {
        name: name.into(),
        parent: RefCell::new(MyRc::downgrade(&MyRc::new(Node{name:String::new(), parent:RefCell::new(MyWeak{ptr: unsafe{std::mem::transmute(1usize)}, _marker: std::marker::PhantomData}}, children: RefCell::new(vec![])}))), // placeholder, replaced on adopt
        children: RefCell::new(vec![]),
    })
}

// Helper: adopt `child` into `parent` (strong), set child's parent (weak)
fn adopt(parent: &MyRc<Node>, child: &MyRc<Node>) {
    *child.parent.borrow_mut() = MyRc::downgrade(parent);
    parent.children.borrow_mut().push(child.clone());
}

The above uses a placeholder trick to satisfy the compiler in an example-only context; in production you would construct nodes in two phases or use Default and then set links.

Walkthrough

Create root, child1, child2 as MyRc<Node>.
Call adopt(&root, &child1) and adopt(&root, &child2).
Dropping root eventually drops both children once nothing else points at them strongly; their parent fields are Weak and do not retain the tree.

Debugging Playbook

Symptom: Allocation never freed.
Check: Did you forget to consume the implicit weak when last strong dropped? Are there outstanding Weak?
Symptom: Double free on last Weak.
Check: Did you decrement weak both on the last-strong path and again in Weak::drop without the implicit-weak protocol?
Symptom: Use-after-free in upgrade.
Check: Are you freeing the allocation while weak > 0? Did you deallocate before decrementing the very last weak?
Symptom: UB in get_mut.
Check: Ensure you only return &mut T when strong == 1 at the exact time of check. Avoid creating &mut across code that might clone another Rc.

FAQ (Extended)

Q: Can I make Rc<T> Send if T: Send?
A: Not without atomics. The counters themselves would race; Arc<T> exists for this purpose.

Q: What about memory ordering on a single thread?
A: In single-threaded Rust, the memory model reduces to program order for Cell. We rely on the lack of concurrency, not on fences.

Q: Why does weak_count subtract 1 when strong > 0?
A: To hide the implicit weak from public observers and match std’s API expectations.

Q: Are overflow checks necessary?
A: Practically, you won’t reach usize::MAX strong references. We still use checked_add in educational code to make logic errors obvious.

Exercises (With Hints)

Design a make_cyclic_pair() that intentionally creates a leaking 2-node cycle.
Hint: Store strong references in each node’s next field; verify with drop logs that destructors never run.
Prove that try_unwrap is linear in the size of T.
Hint: It performs a single ptr::read of T and conditional deallocation; no per-field work beyond Drop of T is forced.
Implement Rc::make_mut that clones T on write if strong > 1.
Hint: This requires T: Clone and either temporary ownership or RefCell<T>.
Add debug assertions: ensure that on last-strong drop, strong == 1 and weak >= 1.
Hint: These can be debug_assert!s to avoid release-mode overhead.
Benchmark cloning vs upgrading using Criterion.
Hint: Hot loop with b.iter(|| { let _ = a.clone(); }) vs let _ = w.upgrade(); from a pre-made Weak.

Mental Model: Strong and Weak References

Reinventing From Scratch — Rc<T>

Chapter 1 — A Mental Model (Strong vs Weak)

1.1 Two lifetimes, one block

1.2 Why not a single counter?

1.3 Why is `Rc<T>` !Send and !Sync?

1.4 When to use `Rc<T>`

1.5 When not to use

1.6 A precise invariant sheet

Notes & Asides

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

B. Proof Sketches

C. Panic Safety Considerations

D. Edge Cases

E. Micro-bench Hints

Worked Example: A Tiny Tree with Parent Weak Links

Debugging Playbook

FAQ (Extended)

Exercises (With Hints)

Suggested Further Reading

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

B. Proof Sketches

C. Panic Safety Considerations

D. Edge Cases

E. Micro-bench Hints

Worked Example: A Tiny Tree with Parent Weak Links

Debugging Playbook

FAQ (Extended)

Exercises (With Hints)

Suggested Further Reading