Reinventing From Scratch — Rc<T>

Chapter 10 — Tests, Miri, and Behavioral Contracts

10.1 Unit tests

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

#[test]
fn weak_upgrade_roundtrip() {
    let a = MyRc::new(String::from("hi"));
    let w = MyRc::downgrade(&a);
    let a2 = w.upgrade().unwrap();
    assert!(MyRc::ptr_eq(&a, &a2));
    drop(a2);
    assert!(w.upgrade().is_some());
    drop(a);
    assert!(w.upgrade().is_none());
}

#[test]
fn try_unwrap_unique() {
    let a = MyRc::new(99);
    assert_eq!(MyRc::try_unwrap(a).ok(), Some(99));
}

10.2 Miri for UB detection

Run under Miri to detect use-after-free and invalid drops:

cargo +nightly miri test

Miri won’t detect counter over/underflow logic errors; write explicit tests for edge transitions (1→0, 2→1, 0→?).

10.3 Property tests (optional)

Use proptest to generate clone/drop/upgrade/downgrade sequences and assert that:

The final deallocation occurs exactly once.
upgrade never yields Some after the last strong is dropped.
No panics in drop paths for well-behaved T: Drop.

10.4 Behavioral contracts

No aliasing of &mut T: get_mut returns Some only when unique.
No use-after-free: allocation survives until both counts zero.
No leaks (absent cycles): last strong + last weak frees memory.

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.

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.

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.

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.

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.

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.

Tests and Miri Validation

Reinventing From Scratch — Rc<T>

Chapter 10 — Tests, Miri, and Behavioral Contracts

10.1 Unit tests

10.2 Miri for UB detection

10.3 Property tests (optional)

10.4 Behavioral contracts

Notes & Asides

Notes & Asides

Notes & Asides

Notes & Asides

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