skip to content

Box and Heap Allocation

Box<T> owns one heap value, which recursive types and trait objects need. Interviewers ask when boxing is required and what Box::leak and into_raw are for.

on this pageshow

questions

4

In Rust, why does `enum Expr { Num(i64), Add(Expr, Expr) }` fail with E0072, and how does `Box` fix it?

level: juniorimportance: must knowfreq 75%

answer

  1. size known at compile time
  2. a variant contains itself
  3. indirection breaks the cycle
  4. a pointer has a fixed size

basics

~20 s

rustc needs every type's size at compile time, and an Expr holding two Exprs inline would be infinitely large. Boxing each child puts it on the heap behind a fixed-size pointer, so Expr gets a finite size.

solid answer

~40 s

An enum must hold its largest variant inline, so `Add(Expr, Expr)` would have to contain two whole `Expr` values, each containing two more, with no finite size. rustc rejects it with E0072, "recursive type `Expr` has infinite size". A `Box<Expr>` is a single pointer to a heap allocation, so `Add(Box<Expr>, Box<Expr>)` has a fixed size (24 bytes on a 64-bit target) however deep the tree grows. Every recursive field needs its own indirection: rustc's help boxes only the first field, and fixing that alone surfaces E0072 on the second. `Vec<Expr>`, `Rc<Expr>` or `&'a Expr` also break the cycle; `Option<Expr>` does not, because `Option` stores its payload inline.

code

rust · 29 lines
rust
use std::mem::size_of;

enum Expr {
    Num(i64),
    Neg(Box<Expr>),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

fn eval(e: &Expr) -> i64 {
    match e {
        Expr::Num(n) => *n,
        Expr::Neg(inner) => -eval(inner),
        Expr::Add(a, b) => eval(a) + eval(b),
        Expr::Mul(a, b) => eval(a) * eval(b),
    }
}

fn main() {
    // (2 + 3) * -4
    let e = Expr::Mul(
        Box::new(Expr::Add(Box::new(Expr::Num(2)), Box::new(Expr::Num(3)))),
        Box::new(Expr::Neg(Box::new(Expr::Num(4)))),
    );
    println!("value = {}", eval(&e));
    println!("size_of::<Expr>() = {}", size_of::<Expr>());
    println!("size_of::<Box<Expr>>() = {}", size_of::<Box<Expr>>());
    println!("size_of::<Option<Box<Expr>>>() = {}", size_of::<Option<Box<Expr>>>());
}

go deeper

for a junior

Recall the rule: every type needs a size known at compile time, and a type that contains itself inline has none. Box the recursive field and name E0072.

for a middle

Explain the layout: an enum holds its largest variant inline, a Box is one pointer, and every recursive field needs its own indirection, which is why Vec or Rc also work and Option alone does not.

for a senior

Show you know the costs: one allocation per node, recursive drop that can overflow the stack on very deep chains, and when Vec children or an arena of indices beat a Box per node.

for a principal

Weigh a Box-per-node tree against an arena with integer indices for a large AST: allocation count, cache locality and how lifetimes or indices change every pass that walks the tree.

## Why rustc needs a size for every type In Rust, every type that lives directly in a variable, a struct field or an enum variant must have a **size known at compile time** (the `Sized` property). rustc uses that size to lay out stack frames, to compute field offsets and to decide how many bytes a move copies. An enum is laid out as roughly **its largest variant plus a tag** (the discriminant) that records which variant is active. Now take an expression-tree interpreter: ```rust enum Expr { Num(i64), Add(Expr, Expr), } ``` To size `Expr`, rustc must size `Add`, which contains two whole `Expr` values stored inline, each of which may be an `Add` containing two more, and so on. The equation `size(Expr) = tag + 2 * size(Expr)` has no finite solution, so the compiler refuses the definition. ## What E0072 says rustc 1.99 reports it like this: ```plaintext error[E0072]: recursive type `Expr` has infinite size --> a1.rs:1:1 | 1 | enum Expr { | ^^^^^^^^^ 2 | Num(i64), 3 | Add(Expr, Expr), | ---- recursive without indirection | help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle ``` The error-code index puts it plainly: any use of the type being defined from inside its own definition must occur **behind a pointer**, because structs and enums need a well-defined size. ## How `Box` fixes it `Box<T>` is an owning pointer to one value of `T` on the heap. For a sized `T`, std guarantees a `Box<T>` is represented as **a single pointer**, so its size does not depend on what it points to. ```rust enum Expr { Num(i64), Neg(Box<Expr>), Add(Box<Expr>, Box<Expr>), Mul(Box<Expr>, Box<Expr>), } ``` On a 64-bit target this `Expr` is 24 bytes: two 8-byte pointers for the widest variant plus the tag, rounded to alignment. Each child lives in its own heap allocation, and the tree's depth no longer affects `size_of::<Expr>()`. | Field type for a child | Stored | Compiles? | |---|---|---| | `Expr` | inline | no, E0072 | | `Option<Expr>` | inline | no, E0072 | | `[Expr; 1]` | inline | no, E0072 | | `Box<Expr>` | heap, one pointer | yes | | `Vec<Expr>` | heap buffer, 3-word handle | yes | | `Rc<Expr>` | shared heap value, one pointer | yes | | `&'a Expr` | borrowed, one pointer | yes | ## Every recursive occurrence needs indirection A common slip is boxing only one field. rustc's help for `Add(Expr, Expr)` suggests `Add(Box<Expr>, Expr)`, and applying only that produces E0072 again, now pointing at the second field. Every path from `Expr` back to `Expr` must pass through a pointer: - **each field** of each variant that holds an `Expr` needs its own indirection; - **nested wrappers** count only if one of them is a pointer: `Option<Box<Expr>>` works, `Box<Option<Expr>>` also works, `Option<Expr>` does not; - **mutual recursion** (a `Stmt` holding an `Expr` that holds a `Stmt`) needs a pointer somewhere on the cycle, not necessarily in both types. ## Choosing the indirection `Box` is the default because it keeps **single ownership**: dropping the root drops the whole tree, with no counts and no lifetimes. The alternatives each solve a different problem: 1. `Vec<Expr>` when a node has a variable number of children, such as a function call's arguments; the vector is already a heap handle, so boxing its elements only adds allocations. 2. `Rc<Expr>` when subtrees are shared between several parents. 3. `&'a Expr` when the nodes live in an arena or a parsed buffer that outlives the tree. ## Working with a boxed tree Code that walks the tree barely notices the boxes: `match` on `&Expr`, and deref coercion lets `eval(inner)` accept a `&Box<Expr>` where `&Expr` is expected. When you consume a tree, `*boxed` moves the value out of its box, which `Box` alone among std's smart pointers allows. Two costs remain: one allocation per node, and **recursive drop**. Dropping a very deep chain, such as a million nested `Neg` nodes, recurses once per level and can overflow the stack, so very deep lists and trees often get a hand-written iterative `Drop`.

  • Why does `Sum(Vec<Expr>)` compile without any `Box`?
    A `Vec<Expr>` is itself a fixed-size handle (pointer, capacity and length, 24 bytes on a 64-bit target) to a heap buffer, so it already supplies the indirection. Writing `Vec<Box<Expr>>` instead adds one more allocation per child and gains nothing for the layout.
  • How large is `Option<Box<Expr>>`, and why?
    The same as `Box<Expr>`: 8 bytes on a 64-bit target. A `Box` is never null, and std guarantees that `Option<Box<U>>` for a sized `U` has the same size as the box, with `None` using the null value. A linked list's `Option<Box<Node>>` tail therefore costs no extra tag.
  • When you consume a tree, how do you get the child out of `Neg(Box<Expr>)` by value?
    Match the node by value and dereference the box: `Expr::Neg(inner) => *inner` moves the `Expr` out and frees the box's allocation. `Box` is the only std smart pointer that allows moving out through `*`; the same move out of an `Rc` fails with E0507.

A form that must include a complete copy of itself can never be printed; a form that writes a filing number pointing to another form fits on one page however long the chain of forms gets.

  • Recursive types need Box because the heap has more room than the stack.
  • One Box anywhere in a variant is enough to break the recursion.
  • Option<Expr> works because None carries no data.
  • E0072 is a borrow-checker error about a value owning itself.
  • Only Box can break the cycle; Vec or a reference never can.
open as a page

In Rust, when would you store a `Box<[T]>` or `Box<str>` instead of a `Vec<T>` or `String`, and what do you give up?

level: middleimportance: should knowfreq 30%

basics

~20 s

Use Box<[T]> or Box<str> for data that is finished and will never grow: the handle is two words instead of three and into_boxed_slice trims spare capacity. You lose push, insert and every other length-changing method.

open as a page

A Rust debug build aborts with a stack overflow at `Box::new([0u8; 16 * 1024 * 1024])`; why, and how do you heap-allocate that buffer safely?

level: seniorimportance: should knowfreq 35%

basics

~20 s

Box::new takes its argument by value, so the 16 MiB array is built on the stack and then copied to the heap, and an unoptimised build overflows the stack. Allocate on the heap directly with vec![0u8; N].try_into() or Box::new_zeroed().

open as a page

In Rust, when do you use `Box::leak` rather than `Box::into_raw`, and what must eventually happen to the pointer `into_raw` returns?

level: seniorimportance: should knowfreq 30%

basics

~20 s

Box::leak gives up the allocation for good and returns a &'a mut T, often 'static, for data that lives until exit. Box::into_raw returns a *mut T, and its owner must later pass it to Box::from_raw exactly once to drop and free it.

open as a page