Rustの構造体定義におけるエラー「recursive type has infinite size」の修正方法

TL;DR: クイックフィックス

recursive type has infinite size エラーを解消するには、再帰的なフィールドを Box<T> でラップします。これによりデータがヒープに移動します。無限に大きな構造体の代わりに、Rustはスタック上に固定サイズのポインタのみを保存すれば済むようになります。

修正前のコード:

struct Node {
    value: i32,
    next: Option<Node>, // エラー E0072: Node が Node を含んでいる
}

修正後のコード:

struct Node {
    value: i32,
    next: Option<Box<Node>>, // 修正済み: Box が間接参照を提供
}

なぜこのエラーが発生するのか

Rustはコンパイル時にすべての型の正確なバイト数を知る必要があります。これにより、コンパイラは変数に対して適切な量のスタックメモリを割り当てることができます。再帰的な型はこのロジックを破綻させます。

次のように定義された List 構造体を想像してみてください。

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

コンパイラはサイズを計算しようとします。i32（4バイト）に加えて、別の List のサイズを確認します。そのサイズを知るために再び内部を見に行くと、さらに4バイトと別の List が見つかります。これが無限ループを引き起こします。理論上、この構造体は表現不可能な無限のメモリを必要とすることになります。

コンパイラは、再帰を指摘する特定のメッセージを出力します。

error[E0072]: recursive type `Node` has infinite size
  |
1 | struct Node {
  | ^^^^^^^^^^^ 再帰的な型が無限のサイズを持っています
2 |     value: i32,
3 |     next: Option<Node>,
  |                  ---- 間接参照のない再帰
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
（ヘルプ: サイクルを断ち切るために間接参照（Box、Rc、& など）を挿入してください）

エラーの修正方法

**間接参照（indirection）**を使用することで、このループを断ち切ることができます。型を直接ネストするのではなく、その型へのポインタを保存します。64ビットシステムでは、ポインタのサイズは指し示す内容に関わらず常に正確に8バイトです。これにより、コンパイラは具体的な数値を扱うことができるようになります。

1. Box を使用する（標準的なアプローチ）

Box<T> は、データをヒープに配置するスマートポインタです。連結リストやツリー構造を構築する際によく使われるツールです。Box を使用することで、構造体のサイズが予測可能になります。

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

これで、BinaryTree は安定したサイズを持つようになります。整数用の4バイトに加えて、パディングと子ノードへの8バイトのポインタです。ノードの実際のコンテンツはメモリの別の場所に存在します。

2. 参照（&T）を使用する

参照も8バイトの固定サイズを提供します。ただし、ライフタイムの管理が必要になり、コードが冗長になる可能性があります。通常、構造体が指し示すデータを所有する必要がない場合に使用されます。

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

ほとんどの開発者は、ライフタイムの煩わしさなしにメモリ所有権を自動的に処理してくれる Box を好みます。

3. 再帰的な列挙型（Enum）の修正

列挙型も、特に抽象構文木（AST）を構築する際に同様の問題が発生します。あるバリアントがその列挙型自体を含んでいる場合、コンパイラは行き詰まってしまいます。

// 'Add' が無限のスペースを必要とするため失敗する
enum Expression {
    Number(i32),
    Add(Expression, Expression),
}

// 成功: 各 'Add' は2つの8バイトポインタを保持する
enum Expression {
    Number(i32),
    Add(Box<Expression>, Box<Expression>),
}

動作確認

修正を適用したら、次の2つのステップで確認してください。

- `cargo check` を実行します。E0072エラーがすぐに消えるはずです。
- 構造体をインスタンス化してみます。`Box` を使用した場合は、`Box::new()` を使うことを忘れないでください。

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

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

    println!("ルートの値: {}", root.value);
}

適切なポインタの選択

- **Box<T>**: 単一の所有権に最適です。デフォルトではこれを使用してください。
- **Rc<T>**: アプリケーションの複数の部分で同じノードを共有する必要がある場合に使用します。
- **&T**: 一時的な、所有権を持たないリンクに最適です。

ルールはシンプルです。型が自分自身を参照する場合は、ポインタの背後に隠します。これにより、Rustがメモリを安全に管理するために必要な固定サイズが確保されます。