skip to content

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.