Smart Pointers · about 45 min

Box, Deref and Drop: Owning Data on the Heap

Why this matters

Most heap allocation in Rust happens inside types like String and Vec. Sometimes you need to put a single value on the heap yourself: for a type that contains itself (lists, trees, expression syntax trees), for a large value you want to move around cheaply, or for a trait object whose concrete type is decided at run time. Box<T> is the simplest smart pointer: a pointer that owns what it points to and frees it when dropped. It is also the clearest example of the two traits that make a pointer "smart", Deref and Drop.

Box basics

fn main() {
    let b = Box::new(41);
    let n = *b + 1;
    println!("b = {b}, n = {n}");
    println!("Box<i32> is {} bytes; the i32 lives on the heap", std::mem::size_of::<Box<i32>>());

    let big = Box::new([0u8; 1_000_000]);
    let moved = big;
    println!("moved a {}-byte array by copying an {}-byte pointer", moved.len(), std::mem::size_of_val(&moved));
}

b = 41, n = 42
Box<i32> is 8 bytes; the i32 lives on the heap
moved a 1000000-byte array by copying an 8-byte pointer

Box::new(value) allocates heap memory, moves value into it, and returns the box, which is one pointer on the stack.
*b dereferences, just like a reference; printing and method calls auto-dereference.
The box owns its contents: moving the box moves ownership (only the pointer is copied), and when the box is dropped, the heap value is dropped and the memory freed. Ownership rules apply exactly as for any other value.

 stack             heap
 +---------+      +-------+
 | b: ptr -------> |  41   |
 +---------+      +-------+

Recursive types need indirection

A type that contains itself directly would be infinitely large:

enum List {
    Cons(i32, List),
    Nil,
}

fn main() {}

error[E0072]: recursive type `List` has infinite size
 --> main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^
2 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

E0072 explains the problem and the fix. With a Box, each Cons holds a pointer to the next node on the heap:

#[derive(Debug)]
enum List {
    Cons(i32, Box<List>),
    Nil,
}

use List::{Cons, Nil};

fn len(list: &List) -> usize {
    match list {
        Cons(_, rest) => 1 + len(rest),
        Nil => 0,
    }
}

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
    println!("{:?}", list);
    println!("length {}", len(&list));
    println!("size of List: {} bytes", std::mem::size_of::<List>());
}

Cons(1, Cons(2, Cons(3, Nil)))
length 3
size of List: 16 bytes

 stack                heap                      heap                      heap
 +-------------+     +--------------+          +--------------+          +-----+
 | Cons(1, ptr)---->  | Cons(2, ptr) ---------> | Cons(3, ptr) ---------> | Nil |
 +-------------+     +--------------+          +--------------+          +-----+

Trees work the same way, usually with Option<Box<Node>> for "child or no child" (the exercise builds one). Expression trees for interpreters, which you will build in module 16, are enums with Boxed sub-expressions.

Box<dyn Trait>

You met this in module 10: a Box<dyn Trait> owns a value of some type implementing the trait, chosen at run time. The box is a fat pointer (data plus vtable). It is the standard way to store different types in one collection or to return one of several types from a function.

Deref: behaving like a reference

What makes *b work on a Box? The Deref trait:

trait Deref {
    type Target;
    fn deref(&self) -> &Self::Target;
}

*b on a type implementing Deref becomes *(b.deref()). Implementing it for your own wrapper shows the mechanism:

use std::ops::Deref;

struct Wrapper {
    inner: String,
    reads: std::cell::Cell<u32>,
}

impl Deref for Wrapper {
    type Target = String;
    fn deref(&self) -> &String {
        self.reads.set(self.reads.get() + 1);
        &self.inner
    }
}

fn shout(s: &str) -> String {
    s.to_uppercase()
}

fn main() {
    let w = Wrapper { inner: String::from("hello"), reads: std::cell::Cell::new(0) };
    println!("{}", w.len());
    println!("{}", shout(&w));
    println!("{}", *w == "hello");
    println!("deref was called {} times", w.reads.get());
}

5
HELLO
true
deref was called 3 times

(Cell lets the counter change behind &self; it is the subject of lesson 3.) Two things happened:

w.len(): method calls auto-deref. Wrapper has no len, so Rust tries String::len through deref.
shout(&w): deref coercion. A &Wrapper was needed as &str; Rust applied deref (to &String) and then String's own Deref<Target = str> (to &str). This is the same mechanism that turns &String into &str and &Box<List> into &List everywhere, all at compile time and free.

Drop: cleaning up

The other half of a smart pointer is Drop, which you met in module 4. Box's drop frees the heap memory after dropping the contents. Dropping a long chain of boxes drops each node in turn:

struct Node {
    name: &'static str,
    next: Option<Box<Node>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("dropping {}", self.name);
    }
}

fn main() {
    let list = Node {
        name: "a",
        next: Some(Box::new(Node { name: "b", next: Some(Box::new(Node { name: "c", next: None })) })),
    };
    println!("list built, head is {}", list.name);
}

list built, head is a
dropping a
dropping b
dropping c

The head is dropped first (its drop runs), then its fields, including the box holding b, and so on down the chain. (For very long lists, this recursive drop can overflow the stack; production linked lists implement Drop with a loop.)

When to use Box

Recursive data structures: lists, trees, syntax trees.
Trait objects: Box<dyn Trait> for mixed types or run-time choice.
Moving a large value cheaply, or keeping a big value off the stack.

When none of these apply, plain values or a Vec are simpler. Box has single ownership; for shared ownership you need Rc (next lesson).

Common mistakes

E0072 recursive type has infinite size: wrap the recursive field in Box (or Option<Box<...>>).
Moving out of a borrowed box: match &list { Cons(v, rest) => ... } gives references; to take a node apart, match on the owned value or use *boxed on an owned box.
Over-boxing: Box<i32> or Box<Vec<T>> for no reason adds an allocation and a pointer hop.

Recap

Box<T> puts a value on the heap and owns it; it is one pointer in size; dropping it frees the value.
Recursive types need indirection: Box<List>, Option<Box<Node>>.
Box<dyn Trait> owns a trait object.
Deref makes * and method calls work through the pointer, and enables deref coercion (&Box<T> to &T, &String to &str).
Drop runs cleanup when the owner goes out of scope; for a box, the contents are dropped and the memory freed.

Going further: read the Rust Book chapter 15.1 to 15.3. Then add a fn push_front(self, v: i32) -> List method to the List enum and implement Display to print it as 1 -> 2 -> 3 -> nil.

Exercises

Exercise 1 · write code

A recursive list

Define

enum List {
    Cons(i64, Box<List>),
    Nil,
}

and two recursive functions, fn sum(list: &List) -> i64 and fn to_vec(list: &List) -> Vec<i64>. The given main builds a list from the numbers on stdin (one per line, preserving order) and prints:

[3, 1, 4]
sum 8

File: main.rs

Starting point

use std::io;

fn main() {
    let nums: Vec<i64> = io::stdin().lines().map(|l| l.unwrap().trim().parse().unwrap()).collect();
    let mut list = List::Nil;
    for &n in nums.iter().rev() {
        list = List::Cons(n, Box::new(list));
    }
    println!("{:?}", to_vec(&list));
    println!("sum {}", sum(&list));
}

Example

input

3
1
4

expected output

[3, 1, 4]
sum 8

Example

expected output

[]
sum 0

Hint 1

match list { List::Cons(v, rest) => v + sum(rest), List::Nil => 0 }: rest is a &Box<List>, which derefs to &List automatically.

Hint 2

For to_vec, walk with let mut cur = list; while let List::Cons(v, rest) = cur { out.push(*v); cur = rest; }.

Reference solution

use std::io;

enum List {
    Cons(i64, Box<List>),
    Nil,
}

fn sum(list: &List) -> i64 {
    match list {
        List::Cons(v, rest) => v + sum(rest),
        List::Nil => 0,
    }
}

fn to_vec(list: &List) -> Vec<i64> {
    let mut out = Vec::new();
    let mut cur = list;
    while let List::Cons(v, rest) = cur {
        out.push(*v);
        cur = rest;
    }
    out
}

fn main() {
    let nums: Vec<i64> = io::stdin().lines().map(|l| l.unwrap().trim().parse().unwrap()).collect();
    let mut list = List::Nil;
    for &n in nums.iter().rev() {
        list = List::Cons(n, Box::new(list));
    }
    println!("{:?}", to_vec(&list));
    println!("sum {}", sum(&list));
}

Exercise 2 · write code

A binary search tree

Implement a binary search tree of i32:

#[derive(Default)]
struct Tree {
    root: Option<Box<Node>>,
}

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

with fn insert(&mut self, v: i32) (ignore duplicates), fn contains(&self, v: i32) -> bool and fn in_order(&self) -> Vec<i32> (sorted). The given main inserts the numbers from the first stdin line and checks the numbers on the second:

sorted: [1, 3, 4, 5, 9]
4: yes
7: no

for 5 3 9 1 4 3 and 4 7.

File: main.rs

Starting point

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut lines = input.lines();
    let mut t = Tree::default();
    for w in lines.next().unwrap().split_whitespace() {
        t.insert(w.parse().unwrap());
    }
    println!("sorted: {:?}", t.in_order());
    for w in lines.next().unwrap_or("").split_whitespace() {
        let v: i32 = w.parse().unwrap();
        println!("{v}: {}", if t.contains(v) { "yes" } else { "no" });
    }
}

Example

input

5 3 9 1 4 3
4 7

expected output

sorted: [1, 3, 4, 5, 9]
4: yes
7: no

Hint 1

For insert, walk a mutable reference to the current slot: let mut slot = &mut self.root; while let Some(node) = slot { ... slot = &mut node.left; } then *slot = Some(Box::new(...)).

Hint 2

in_order is easiest with a recursive helper fn walk(n: &Option<Box<Node>>, out: &mut Vec<i32>): left, value, right.

Hint 3

A recursive insert on Node (match &mut self.left { Some(n) => n.insert(v), None => self.left = Some(Box::new(...)) }) also works.

Reference solution

use std::io::{self, Read};

#[derive(Default)]
struct Tree {
    root: Option<Box<Node>>,
}

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Tree {
    fn insert(&mut self, v: i32) {
        let mut slot = &mut self.root;
        while let Some(node) = slot {
            if v == node.value {
                return;
            }
            slot = if v < node.value { &mut node.left } else { &mut node.right };
        }
        *slot = Some(Box::new(Node { value: v, left: None, right: None }));
    }

    fn contains(&self, v: i32) -> bool {
        let mut cur = &self.root;
        while let Some(node) = cur {
            if v == node.value {
                return true;
            }
            cur = if v < node.value { &node.left } else { &node.right };
        }
        false
    }

    fn in_order(&self) -> Vec<i32> {
        fn walk(n: &Option<Box<Node>>, out: &mut Vec<i32>) {
            if let Some(node) = n {
                walk(&node.left, out);
                out.push(node.value);
                walk(&node.right, out);
            }
        }
        let mut out = Vec::new();
        walk(&self.root, &mut out);
        out
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut lines = input.lines();
    let mut t = Tree::default();
    for w in lines.next().unwrap().split_whitespace() {
        t.insert(w.parse().unwrap());
    }
    println!("sorted: {:?}", t.in_order());
    for w in lines.next().unwrap_or("").split_whitespace() {
        let v: i32 = w.parse().unwrap();
        println!("{v}: {}", if t.contains(v) { "yes" } else { "no" });
    }
}

Exercise 3 · quiz

Why does the recursive type need Box?

Why does enum List { Cons(i64, List), Nil } fail to compile (E0072), while Cons(i64, Box<List>) works?

Enums cannot contain themselves for safety reasons, and Box disables the check
The size of List would be infinite: a List contains a List which contains a List...; a Box is a fixed-size pointer, so List gets a finite size
Box makes the list immutable, which recursion requires
Without Box the list would live on the stack, and recursion is not allowed on the stack

Answer

The size of List would be infinite: a List contains a List which contains a List...; a Box is a fixed-size pointer, so List gets a finite size

Every type needs a size known at compile time. Inline, Cons would contain an i64 plus a whole List, which contains another List, and so on without end. A Box<List> is one pointer (8 bytes) to a List stored on the heap, so List is the size of a tag plus an i64 plus a pointer, and the recursion happens through heap allocations at run time instead of in the type's layout.