Sửa lỗi Rust 'recursive type has infinite size' khi định nghĩa struct lồng nhau

TL;DR: The Quick Fix

To stop the recursive type has infinite size error, wrap the recursive field in a Box<T>. This moves the data to the heap. Instead of an infinitely large struct, Rust now only needs to store a fixed-size pointer on the stack.

Broken code:

struct Node {
    value: i32,
    next: Option<Node>, // Error E0072: Node contains Node
}

Fixed code:

struct Node {
    value: i32,
    next: Option<Box<Node>>, // Fixed: Box provides indirection
}

Why This Happens

Rust must know the exact byte count of every type at compile time. This allows the compiler to allocate the right amount of stack memory for your variables. Recursive types break this logic.

Imagine a List struct defined like this:

struct List {
    data: i32,
    child: List,
}

The compiler tries to calculate the size. It sees an i32 (4 bytes) plus the size of another List. To find that size, it looks inside again, finding another 4 bytes plus another List. This creates an infinite loop. Theoretically, this struct would require infinite memory, which is impossible to represent.

The compiler will output a specific error message pointing to the recursion:

error[E0072]: recursive type `Node` has infinite size
  |
1 | struct Node {
  | ^^^^^^^^^^^ recursive type has infinite size
2 |     value: i32,
3 |     next: Option<Node>,
  |                  ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle

How to Fix the Error

You can break the cycle using indirection. Rather than nesting the type directly, you store a pointer to it. On a 64-bit system, a pointer is always exactly 8 bytes, regardless of what it points to. This gives the compiler a concrete number to work with.

1. Using Box (The Standard Approach)

A Box<T> is a smart pointer that puts data on the heap. It is the most common tool for building linked lists or tree structures. By using Box, the size of your struct becomes predictable.

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

Now, BinaryTree has a stable size: 4 bytes for the integer, plus the padding and the 8-byte pointers for the child nodes. The actual content of those nodes lives elsewhere in memory.

2. Using References (&T)

References also provide a fixed size of 8 bytes. However, they require you to manage lifetimes, which can make your code more verbose. You typically use this when the struct doesn't need to own the data it points to.

struct Node<'a> {
    value: i32,
    next: Option<&'a Node<'a>>,
}

Most developers prefer Box because it handles memory ownership automatically without the lifetime headache.

3. Fixing Recursive Enums

Enums suffer from the same problem, particularly when building Abstract Syntax Trees (ASTs). If one variant contains the enum itself, the compiler gets stuck.

// This fails because 'Add' needs infinite space
enum Expression {
    Number(i32),
    Add(Expression, Expression),
}

// This works: each 'Add' holds two 8-byte pointers
enum Expression {
    Number(i32),
    Add(Box<Expression>, Box<Expression>),
}

Verification

Once you apply the fix, verify it with two quick steps:

- Run `cargo check`. The E0072 error should vanish immediately.
- Try instantiating your struct. If you used `Box`, remember to use `Box::new()`:

fn main() {
    let leaf = Node {
        value: 10,
        next: None,
    };

    let root = Node {
        value: 20,
        next: Some(Box::new(leaf)),
    };

    println!("Root value: {}", root.value);
}

Choosing the Right Pointer

- **Box<T>**: Best for single ownership. Use this by default.
- **Rc<T>**: Use this if multiple parts of your app need to share the same nodes.
- **&T**: Best for temporary, non-owned links.

The rule is simple: if a type refers to itself, hide it behind a pointer. This gives Rust the fixed size it needs to manage your memory safely.