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

TL;DR: Cách khắc phục nhanh

Để khắc phục lỗi recursive type has infinite size, hãy bọc trường đệ quy trong một Box<T>. Điều này sẽ chuyển dữ liệu sang vùng nhớ heap. Thay vì một struct có kích thước vô hạn, Rust giờ đây chỉ cần lưu trữ một con trỏ có kích thước cố định trên stack.

Mã lỗi:

struct Node {
    value: i32,
    next: Option<Node>, // Lỗi E0072: Node chứa Node
}

Mã đã sửa:

struct Node {
    value: i32,
    next: Option<Box<Node>>, // Đã sửa: Box cung cấp indirection
}

Tại sao lỗi này xảy ra

Rust phải biết chính xác số lượng byte của mọi kiểu dữ liệu tại thời điểm biên dịch. Điều này cho phép trình biên dịch cấp phát đúng lượng bộ nhớ stack cho các biến của bạn. Các kiểu dữ liệu đệ quy (recursive types) làm phá vỡ logic này.

Hãy tưởng tượng một struct List được định nghĩa như thế này:

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

Trình biên dịch cố gắng tính toán kích thước. Nó thấy một i32 (4 byte) cộng với kích thước của một List khác. Để tìm kích thước đó, nó lại nhìn vào bên trong, tìm thấy 4 byte khác cộng với một List khác nữa. Điều này tạo ra một vòng lặp vô hạn. Về mặt lý thuyết, struct này sẽ yêu cầu bộ nhớ vô hạn, điều không thể biểu diễn được.

Trình biên dịch sẽ xuất ra một thông báo lỗi cụ thể chỉ vào sự đệ quy:

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: chèn thêm một số indirection (ví dụ: `Box`, `Rc`, hoặc `&`) để phá vỡ vòng lặp

Cách khắc phục lỗi

Bạn có thể phá vỡ vòng lặp bằng cách sử dụng indirection (sự gián tiếp). Thay vì lồng trực tiếp kiểu dữ liệu, bạn lưu trữ một con trỏ tới nó. Trên hệ thống 64-bit, một con trỏ luôn có kích thước chính xác là 8 byte, bất kể nó trỏ tới cái gì. Điều này cung cấp cho trình biên dịch một con số cụ thể để làm việc.

1. Sử dụng Box (Cách tiếp cận tiêu chuẩn)

Một Box<T> là một con trỏ thông minh (smart pointer) đưa dữ liệu vào heap. Đây là công cụ phổ biến nhất để xây dựng danh sách liên kết hoặc cấu trúc cây. Bằng cách sử dụng Box, kích thước của struct trở nên có thể dự đoán được.

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

Giờ đây, BinaryTree có kích thước ổn định: 4 byte cho số nguyên, cộng với phần đệm (padding) và các con trỏ 8 byte cho các nút con. Nội dung thực tế của các nút đó nằm ở nơi khác trong bộ nhớ.

2. Sử dụng tham chiếu (&T)

Các tham chiếu cũng cung cấp kích thước cố định là 8 byte. Tuy nhiên, chúng yêu cầu bạn phải quản lý lifetime (vòng đời), điều này có thể làm cho mã của bạn trở nên rườm rà hơn. Bạn thường sử dụng cách này khi struct không cần sở hữu dữ liệu mà nó trỏ tới.

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

Hầu hết các lập trình viên thích Box hơn vì nó tự động xử lý quyền sở hữu bộ nhớ mà không gặp khó khăn về lifetime.

3. Sửa lỗi Recursive Enums

Enums cũng gặp vấn đề tương tự, đặc biệt là khi xây dựng Cây cú pháp trừu tượng (AST). Nếu một biến thể (variant) chứa chính enum đó, trình biên dịch sẽ bị kẹt.

// Lỗi vì 'Add' cần không gian vô hạn
enum Expression {
    Number(i32),
    Add(Expression, Expression),
}

// Hoạt động: mỗi 'Add' giữ hai con trỏ 8-byte
enum Expression {
    Number(i32),
    Add(Box<Expression>, Box<Expression>),
}

Kiểm tra

Sau khi áp dụng bản sửa lỗi, hãy kiểm tra lại bằng hai bước nhanh sau:

- Chạy `cargo check`. Lỗi E0072 sẽ biến mất ngay lập tức.
- Thử khởi tạo struct của bạn. Nếu bạn đã sử dụng `Box`, hãy nhớ sử dụng `Box::new()`:

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

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

    println!("Giá trị Root: {}", root.value);
}

Chọn con trỏ phù hợp

- **Box<T>**: Tốt nhất cho quyền sở hữu đơn lẻ. Hãy sử dụng mặc định.
- **Rc<T>**: Sử dụng nếu nhiều phần trong ứng dụng của bạn cần chia sẻ cùng một nút.
- **&T**: Tốt nhất cho các liên kết tạm thời, không có quyền sở hữu.

Quy tắc rất đơn giản: nếu một kiểu dữ liệu tham chiếu đến chính nó, hãy ẩn nó sau một con trỏ. Điều này giúp Rust có được kích thước cố định cần thiết để quản lý bộ nhớ của bạn một cách an toàn.