Reinventing From Scratch — Rc<T>

Chapter 0 — Preface: Why Rebuild `Rc<T>`?

Shared ownership looks polite on the surface; under the hood it’s a negotiation of lifetimes, counts, and carefully staged destruction.

This book-length chapter set is a ground-up reconstruction of Rust’s single-threaded reference-counted pointer: Rc<T>. The goal is not to replace the standard library but to internalize the invariants that make Rc<T> sound. By building our own miniature Rc, you’ll see the engineering tradeoffs behind:

The distinction between strong and weak references.
Why Rc<T> is deliberately !Send and !Sync (non-thread-safe).
How implicit weak ownership ties the allocation’s lifetime to the strong regime.
Why cycles leak and how Weak<T> is the standard escape hatch.
Where tail allocation and header+value layouts yield cache-friendly designs.

How to read this series

Each chapter mixes narrative, diagrams, code, and proof sketches that state what the unsafe blocks rely on. We keep invariants front-and-center and introduce interior mutability via Cell<usize> for counts. You’ll also get:

Progressive implementations (MyRc<T>, MyWeak<T>).
Deallocation paths that separate value drop from block free.
Testing guidance with Miri (to catch UB) and checklists you can keep next to your editor.

Why care if `Rc<T>` already exists?

Because containers and smart pointers are patterns, and you will one day invent one. Understanding Rc empowers you to design safe intrusive lists, arenas, interning tables, and cache layers. You’ll know when to use Rc, when to pick Arc, and when to build bespoke ownership forms.

What we won’t cover

Multi-threaded atomics (Arc<T>). Our focus is single-threaded Cell-based counts.
Garbage collection and tracing. RC is a deterministic, local heuristic—GC is global.
Cycle collectors. We’ll show leak-avoidance patterns using Weak, not full collectors.

A running mental model

Rc<T> (strong)           Weak<T> (weak)
   │                         │
   └──► [header: strong, weak | value: T]
                     ▲  ▲
    value kept alive │  └─ allocation kept alive (implicit weak)
``

When **strong > 0**, `T` is alive. When **strong == 0**, `T` is dropped, but the allocation remains as long as **weak > 0** (so `Weak` can still upgrade and fail gracefully). Finally, when **strong == 0 && weak == 0**, the allocation is deallocated.

### Safety mindset

- The counts live in a **header** (`RcBox<T>`) preceding `T`. We mutate them via `Cell<usize>`.
- `Clone` increments **strong**; `Drop` decrements **strong** and maybe destroys `T`.
- `Weak::upgrade` observes **strong** and, if nonzero, increments it and returns a new strong handle.
- `Weak::drop` decrements **weak** and perhaps frees the allocation once both counts are zero.

> ⚠️ We never touch atomics here. That is the single-threaded contract that keeps `Rc` fast but confined.

### Who is this for?

Systems programmers, Rust learners who want to go beyond “just use it,” and anyone designing data structures that need explicit, deterministic memory management under the borrow checker.



---

## 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 `Rc`s 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

```rust
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.

Preface: Why Rebuild Rc<T>?

Reinventing From Scratch — Rc<T>

Chapter 0 — Preface: Why Rebuild `Rc<T>`?

How to read this series

Why care if `Rc<T>` already exists?

What we won’t cover

A running mental model

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