Rustで再帰的データ構造を定義する

Rust勉強中。現状メインで使用している言語はC。
Rustの勉強と低レイヤの勉強をかねて、「低レイヤを知りたい人のためのCコンパイラ作成入門」をRustで実装しているが、Cの頭で書こうとしたらつまづいたのでメモ。

構造体を定義する

実装したいデータ構造はCだとこうなる。（詳細はリンク元を参照）
lhsとrhsは自身が属しているstruct Nodeのポインタになっており、再帰的なデータ構造になる。

typedef struct Node Node;
struct Node {
  NodeKind kind; // ノードの型
  Node *lhs;     // 左辺
  Node *rhs;     // 右辺
  int val;       // kindがND_NUMの場合のみ使う
};

これをRustで表現する。
一旦こんな感じで書いてみたが、

struct Node {
    kind: NodeKind,
    lhs: Node,
    rhs: Node,
    val: u32,
}

これは当然失敗する。

error[E0072]: recursive type `Node` has infinite size
 --> src/main.rs:6:1
  |
6 | struct Node {
  | ^^^^^^^^^^^ recursive type has infinite size
7 |     kind: NodeKind,
8 |     lhs: Node,
  |     --------- recursive without indirection
9 |     rhs: Node,
  |     --------- recursive without indirection

lhsとrhsが実態として定義されており、再帰的に繰り返された場合に構造体のデータサイズが無限に発散してしまうため、コンパイラがエラーにする。
ここをCでいうポインタとして定義したい訳だが、Rustではポインタの考え方というか、使い方がCとは大きく異なる。生ポインタというものもあるらしいが、ここで安易にunsafeな処理にもしたくない。少し調べたら、こういう場合はBoxを使えばいいらしいと分かった。

Boxを使って書き変えてみる。

struct Node {
    kind: NodeKind,
    lhs: Box<Node>,
    rhs: Box<Node>,
    val: u32,
}

これでcargo checkするとコンパイルは問題なく通る。
しかし、以下で説明するが、これは罠である。

構造体を使ってみる

まず、Cの世界でデータ構造を使用する関数を見てみる。

Node *new_node(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_node_num(int val) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = ND_NUM;
  node->val = val;
  return node;
}

これをRustで実装してみる。

fn new_node(kind: NodeKind, lhs: Box<Node>, rhs: Box<Node>) -> Box<Node> {
    let node = Node {
        kind: kind,
        lhs: lhs,
        rhs: rhs,
    };
    let node = Box::new(node);
    node
}

fn new_node_num(val: u32) -> Box<Node> {
    let node = Node {
        kind: NodeNum,
        val: val,
    };
    let node = Box::new(node);
    node
}

しかし、これをcargo checkするとエラーになる。

error[E0063]: missing field `val` in initializer of `Node`
  --> src/main.rs:17:16
   |
17 |     let node = Node {
   |                ^^^^ missing `val`

error[E0063]: missing fields `lhs`, `rhs` in initializer of `Node`
  --> src/main.rs:27:16
   |
27 |     let node = Node {
   |                ^^^^ missing `lhs`, `rhs`

Rustでは構造体を使うとき、全てのメンバを初期化しなくてはならない。

ん？Boxの初期値？
u32であるvalの初期値は、適当に0とかに設定できなくもないが、Boxの初期値が設定できない。ダミーのBoxを用意してその値を入れようとしても、そのダミーの中のBoxを定義するためにまた別のBoxが、というように再帰しているので詰んでしまう。

では、どうする？

ここで、今回のデータ構造を整理してみる。再帰的データ構造には2種類のデータが含まれている。

• 再帰するデータ（次につながるデータ）
• 終端するデータ（次がないデータ）

ここまでに書いた構造体では、この2種類のデータが1つの構造体に混在してしまっていることになる。
Cではこのような構造体を定義できるが、結果としてそれぞれのデータを表現する際に初期化されない（意味のある値が入らない）領域ができてしまう。これでは、意味のない値に不正にアクセスしてしまう危険が生じるところ、Rustではそのような危険性を排除できている、と言えるかもしれない。

では、どうするか？
Rustでは、こういうときにはenumを使うとうまく表現できる。RustのenumはCに比べて多様なデータ構造を表現できる。
ここでは、再帰するデータは2項演算子、終端するデータは数字となるため、それぞれのデータに必要な情報を考えenumを用いて定義する。

enum Node {
    Operator {
        kind: NodeKind,
        lhs: Box<Node>,
        rhs: Box<Node>,
    },  
    Number {
        val: u32,
    },  
}

操作関数も定義する。

fn new_node(kind: NodeKind, lhs: Box<Node>, rhs: Box<Node>) -> Box<Node> {
    let node = Node::Operator {
        kind: kind,
        lhs: lhs,
        rhs: rhs,
    };
    let node = Box::new(node);
    node
}

fn new_node_num(val: u32) -> Box<Node> {
    let node = Node::Number {
        val: val,
    };
    let node = Box::new(node);
    node
}

これでcargo checkも通り、再帰的データ構造に必要な2種類のデータも明確に分離させて定義できた。

まとめ

Rustで再帰的データ構造を定義するときはenumを使おう。