Help us understand the problem. What is going on with this article?

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を使おう。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした