COMP 477

# Smart Pointers

## Scott Rixner and Alan Cox

---

<footer>COMP 477 Spring 2026 • Scott Rixner and Alan Cox</footer>

---

## Pointers

* You are already familiar with references (`&T` and `&mut T`).
    * They borrow data owned by someone else.
    * They have no runtime overhead (usually just a memory address).
    * They are checked at compile time for validity (lifetimes).
* Rust does not have (safe) raw pointers.
* Smart Pointers are data structures that act like pointers but have metadata and capabilities.
    * They usually **own** the data they point to.
    * Examples: `String`, `Vec<T>`, `Box<T>`, `Rc<T>`.

---

## `Box<T>`

```rust
fn main() {
    let b = Box::new(5); // 5 is allocated on the heap
    println!("b = {}", b);
} // b goes out of scope, heap memory is freed
```

The simplest smart pointer.

* Allocates data on the **heap**.
* The `Box` owns the data on the heap.
* When the `Box` goes out of scope, the heap memory is deallocated.

---

## Constructing a Cons List

```rust
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

fn main() {
    let list = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Cons(3, Box::new(List::Nil))))));
}
```

* Use a `Box` (pointer size is known/fixed).
* `Box` provides the indirection needed to break the infinite recursion cycle.

---

## Questions: Ownership

Who owns the list elements in the previous example?

When is the memory for the list and its constituent elements deallocated?

---

## Dereferencing `Box<T>`

```rust
fn greet(name: &str) {
    println!("Hello, {}!", name);
}

fn main() {
    // Explicit dereference
    let b = Box::new(5);
    assert_eq!(5, *b); // *Box<i32> → i32

// Implicit deref coercion when passing a Box<String> by reference
    let s = Box::new(String::from("Rice"));
    greet(&s); // &Box<String> → &String → &str
}
```

* `Box<T>` implements the `Deref` trait so you can treat `Box` like a reference.
* Rust will implicitly coerce references when needed.
    * E.g., `&Box<String>` -> `&String` -> `&str`.

---

## Shared Ownership

* Sometimes, a single piece of data needs multiple owners.
* Example: Graph nodes (multiple edges pointing to one node).
* Rust's ownership rules normally prevent this (one owner).

---

## Reference Counting: `Rc<T>`

```rust
use std::rc::Rc;

fn main() {
    let a = Rc::new(5);
    let b = Rc::clone(&a); // Increases ref count, doesn't deep copy
    let c = Rc::clone(&a);

println!("Count after creating c: {}", Rc::strong_count(&a));
    // Output: 3
} // c drops, b drops, a drops -> memory freed
```

* `Rc::new` allocates data on the heap, like `Box::new`.
* `Rc` enables shared ownership of data.
    * Immutable access only.
    * Keeps track of the number of references to a value.
    * Value is dropped only when the reference count reaches zero.
* `Rc::clone(&a)` just increments a reference counter.

---

## `Rc<T>` Example: Shared List

```rust
enum List<T> {
    Cons(T, Rc<List<T>>),
    Nil,
}

fn main() {
    let a = Rc::new(List::Cons(5, Rc::new(List::Cons(10, Rc::new(List::Nil)))));
    // b shares list a
    let b = List::Cons(3, Rc::clone(&a));
    // c also shares list a
    let c = List::Cons(4, Rc::clone(&a));
}
```

* Both `b` and `c` point to `a`.
* `a` won't be dropped until `a`, `b`, and `c` go out of scope.

---

## Question: Sharing

Is it a problem that the items of type `T` (in this case, the integers) are not wrapped in `Rc<T>`?  Why or why not?

---

## Limitations of `Rc<T>`

* `Rc<T>` gives you **immutable** access to the inner data.
* If `Rc<T>` allowed mutability, you could violate the borrowing rules with multiple mutable “borrows”.
* What if you need to mutate shared data?

---

## Interior Mutability

Allows you to mutate data via immutable references to that data.

* Borrowing rules are enforced at **runtime** instead of compile time.
* Uses `unsafe` code internally to bypass typical rules, but exposes a safe API.

---

## `RefCell<T>`

* Represents single ownership over the data it holds.
* Allows borrowing the data mutably (`&mut T`) even through an immutable reference (`&RefCell<T>`).
    * `.borrow()`: returns `Ref<T>` (acts like `&T`).
    * `.borrow_mut()`: returns `RefMut<T>` (acts like `&mut T`).
* Runtime borrow checking.
    * `RefCell` tracks active borrows dynamically.
    * If you violate the borrow rules (e.g., you have two live `RefMut<T>`), the program **panics** at runtime.

---

## Using `RefCell<T>`

```rust
use std::cell::RefCell;

fn main() {
    let x = RefCell::new(42);

let y = x.borrow(); // Immutable borrow
    println!("y: {}", *y); // y: 42
    // let mut z = x.borrow_mut(); // PANIC! Cannot borrow mutably while borrowed immutably
    drop(y); // Explicitly drop borrow

let mut z = x.borrow_mut(); // OK now
    *z += 1;
    println!("x: {:?}", x); // x: RefCell{value: <borrowed>}
}
```

---

## Combining `Rc` and `RefCell`

A common pattern for interior mutability: `Rc<RefCell<T>>`.

* `Rc` allows multiple owners.
* `RefCell` allows mutation.
* Multiple owners can mutate the shared data.
* Borrowing rules enforced at runtime.

---

## Example: N-ary Tree

```rust
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: i32,
    children: Vec<Rc<RefCell<Node>>>,
}

fn main() {
    let leaf = Rc::new(RefCell::new(Node { value: 3, children: vec![] }));
    let root = Rc::new(RefCell::new(Node { value: 5, children: vec![] }));

// Mutate root to add leaf as a child
    root.borrow_mut().children.push(Rc::clone(&leaf));
    
    // Mutate the leaf, which is shared with the root
    leaf.borrow_mut().value = 10;
    
    println!("root: {:?}", root);
    // root: RefCell{value: Node{value: 5, children: [RefCell{value: Node{value: 10, children: []}}]}}
}
```

---

## Question: Reference Counting and Interior Mutability

When should you use interior mutability in your designs?

What are the trade-offs of using `Rc<RefCell<T>>`?

---

## Memory Leaks: Reference Cycles

* `Rc` can create reference cycles.
* If `A` points to `B`, and `B` points to `A`, the reference count for both will never reach zero.
* Memory is never freed (memory leak).
* Leaks are memory-safe (no data races/segfaults), but undesirable.

---

## Cycle Example

```rust
struct Node<T> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>,
}

fn main() {
    let a = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let b = Rc::new(RefCell::new(Node { value: 2, next: Some(Rc::clone(&a)) }));

// Make it circular: a → b → a
    a.borrow_mut().next = Some(Rc::clone(&b));

// a and b will never be dropped! Reference count is 2 for both.
}
```

---

## Solving Cycles: `Weak<T>`

* `Weak<T>` is a **non-owning** reference to reference counted data.
* Does **not** increase the `strong_count` (ownership count).
* Increases `weak_count`.
* Data is dropped when `strong_count` reaches 0, even if `weak_count` > 0.
    * Destructor for `T` is run.
    * Memory is not deallocated until `weak_count` also goes to 0.

---

## Using `Weak<T>`

```rust
let strong = Rc::new(100);
let weak = Rc::downgrade(&strong); // Creates Weak<i32>

println!("Strong: {}, Weak: {}", Rc::strong_count(&strong), Rc::weak_count(&strong));
// Strong: 1, Weak: 1

// Upgrade to an Rc<T> (prints "Value is safe to use: 100").
match weak.upgrade() {
    Some(rc) => println!("Value is safe to use: {}", rc),
    None => println!("Value has been dropped!"),
} // Upgraded strong reference is dropped.

drop(strong); // The only remaining strong reference is dropped.

assert!(weak.upgrade().is_none()); // Cannot upgrade the weak reference anymore.
```

* `Weak<T>` is created from an `Rc<T>` using `Rc::downgrade`.
* To access the data, you must first **upgrade** a `Weak<T>` to an `Rc<T>`.
    * `Some(Rc<T>)` if at least one `Rc<T>` still refers to the data.
    * `None` if no remaining `Rc<T>` pointers refer to the data.

---

## Example: N-ary Tree with Parent Pointers

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

#[derive(Debug)]
struct Node {
    value: i32,
    parent: Weak<RefCell<Node>>,
    children: Vec<Rc<RefCell<Node>>>,
}

fn main() {
    let leaf = Rc::new(RefCell::new(Node { value: 3, parent: Weak::new(), children: vec![] }));
    let root = Rc::new(RefCell::new(Node { value: 5, parent: Weak::new(), children: vec![Rc::clone(&leaf)] }));

// Downgrade strong reference to root to create weak reference for leaf's parent
    leaf.borrow_mut().parent = Rc::downgrade(&root);

println!("Leaf parent: {:?}", leaf.borrow().parent.upgrade());
}
```

* `Weak` prevents reference cycles (memory leaks).
* `RefCell` allows interior mutability (modifying nodes).

---

## Question: Cycles and Weak Pointers

Does `Weak<T>` simplify the construction of data structures that contain cycles?

---

## Summary: Choosing a Pointer

---

## Performance Considerations

Use references (`&`) and `Box` whenever possible. Use `Rc` and `RefCell` only when ownership logic requires it.

* `Box` is fast (simple pointer).
* `Rc` has small overhead (increment/decrement counter).
* `RefCell` has overhead (checking borrow flags at runtime).

---

## Conclusion

Smart pointers enable complex data structures and patterns in Rust.

* **Box:** Heap allocation, unique ownership.
* **Rc:** Shared ownership, reference counting.
* **Weak:** Enables reference counted cycles, does not prevent destruction.
* **RefCell:** Interior mutability, runtime borrow checks.
    
Rust sometimes requires layers of smart pointers to make your
intent explicit, but avoid unecessary "pointer soup" like `Rc<RefCell<Box<Vec<T>>>>`.