Rustで構文木の実装を考える

はじめに

ここしばらくRustでパーサを書いていて、構文木の表現（つまりどのような型定義にするか）についていろいろと試行錯誤しました。この記事ではその時に試した構造をまとめておきます。

題材

簡単な数値型の構文木を例に説明します。数値は整数か浮動小数点数で、整数はオプションで基数（"0x"とか"0o"とか）を付けられるという、いつものやつです。
BNFっぽく書くと

Number ::= IntegralNumber | RealNumber
IntegralNumber ::= [Base] NumberString 
Base ::= "0x" | "0o" | "0b"

という感じですね。（浮動小数点側は省略します）

単一Node

まず考えられるのはこんな型です。

enum NodeKind {
  Number,
  IntegralNumber,
  RealNumber,
  Base,
  NumberString,
}

struct Node {
  kind: NodeKind,
  nodes: Vec<Node>,
}

これは構文木というか、単にツリーを表しているだけです。これはこれでシンプルでいいのですが、ちょっと表現できる範囲が広すぎて不正な構文まで表せてしまいます。折角強力な型システムがあるので、できれば構文的に正しい構文木だけが表現できるようにしたいところです。

enumとstruct

次に考えられるのはこんな感じです。

enum Number {
  IntegralNumber(IntegralNumber),
  RealNumber(ReamNumber),
}

struct IntegralNumber {
  base: Option<Base>,
  number: NumberString,
}

ノードの種類ごとに型を分けて、子ノードもきちんとフィールド名を付けて表します。また、あるノードが複数の型のいずれかである場合はenumを使います。
このようにすることで、型レベルで構文的な正しさが保証できるようになり、もし不正な構文の構文木を作ろうとするとコンパイルエラーとなります。
Rustの手続きマクロでよく使われる構文解析クレートsynはこのタイプです。

子ノードをtupleに

enum/structのバージョンはかなりいい感じでしたが、子ノードを統一的に得る方法がありません。つまり必ず型毎に適切なフィールド名でアクセスする必要があるということです。そこで子ノードのフィールド名をnodesに統一したものが以下です。

enum Number {
  IntegralNumber(IntegralNumber),
  RealNumber(ReamNumber),
}

struct IntegralNumber {
  nodes: (Option<Base>, NumberString),
}

子ノードのフィールド名がなくても型を見ればそのノードが何なのか分かるので、それほど問題はなさそうです。また「Rustで複雑な複合型をイテレートする」に書いた通りタプルはイテレートすることができるので、この構文木に対してイテレータを実装することができます。

Boxの利用

1つ前のバージョンで機能的には満足できるようになりました。しかし、このまま構文木を大きくしていくとサイズの問題が発生します。各ノードは子ノードの実体を所有しているので、構文木の浅いノードはそれ以下のノードをすべて持っており、非常に大きくなることがあります。
これを回避するには子ノードを実体ではなくポインタで持てばよいので、Boxにすればよいということになります。
実サイズに応じて細かく調整してもいいのですが、調整が面倒なのと、使い勝手的にもBoxになる部分は統一されている方が扱いやすいので、enumは全てBoxにするようにしました。
また、Boxにしておくことで再帰が発生するケースも問題なく扱うことができます。

enum Number {
  IntegralNumber(Box<IntegralNumber>),
  RealNumber(Box<ReamNumber>),
}

struct IntegralNumber {
  nodes: (Option<Base>, NumberString),
}

custom derive

ノードの種類ごとに型をつくっていくと型が多くなって、それに対するメソッド実装は非常に大変になります。
そこでcustom deriveを定義して、メソッドは全てderiveで導出するようにします。

#[derive(Node)]
enum Number {
  IntegralNumber(Box<IntegralNumber>),
  RealNumber(Box<ReamNumber>),
}

#[derive(Node)]
struct IntegralNumber {
  nodes: (Option<Base>, NumberString),
}

任意ノード型

ノード種類ごとに型を作りましたが、任意のノードを示す型もそれはそれで必要です。
例えば構文木にイテレータを実装することを考えると、そのイテレータが返す型は任意のノードを表せる必要があります。
そのために任意のノードを保持できるAnyNodeと任意のノードへの参照としてRefNodeを定義しました。

enum AnyNode {
  Number(Number),
  IntegralNumber(IntegralNumber),
  RealNumber(RealNumber),
  Base(Base),
  NumberString(NumberString),
}

enum RefNode<'a> {
  Number(&'a Number),
  IntegralNumber(&'a IntegralNumber),
  RealNumber(&'a RealNumber),
  Base(&'a Base),
  NumberString(&'a NumberString),
}

build.rsによるAnyNodeとRefNodeの生成

例によって型の量が多いとAnyNodeとRefNodeを手書きするのも大変です。そこでbuild.rsによる自動生成としました。
全てのノード型は#[derive(Node)]を持つことを利用して、src中でそのderiveを持つ型を正規表現で探してAnyNodeとRefNodeを生成します。
（厳密にはちゃんと構文解析した方がいいかもしれませんが、このライブラリをメンテする人が気を付ければいいだけなので割と適当にやっています）

まとめ

ここに書いたことを反映した実際の構文木は以下になります。

最終的に型の個数は1300以上になってしまい、custom deriveなどがなければとても実装できない規模でした。
ここまでやる必要のあるケースはあまりないと思いますが、部分的にでも参考になる箇所があれば幸いです。