最近Rustの勉強を始めました。手始めに以前Javaで作った簡易プログラミング言語samplanでも実装してみようかと思ったのですが、コンパイラを作るとなれば解析木が作れなければ話にならず、では木を作ろうとするとRustといえば所有権だのなんだのと参照(ポインタ)の扱いが大変なのが知られているわけで、ひとまず小さなサンプルプログラムで木構造を作ってみました。Boxを使って、こんな感じの木構造を作ります。
// 木構造のノードを表す構造体。 // 複数の子を指す参照をVecで保持している。 struct Node { value: i32, children: Vec<Box<Node>> } impl Node { fn new(value: i32) -> Node { Node { value: value, children: Vec::new() } } } fn main() { let mut root = Node::new(0); let mut node1 = Node::new(1); let node2 = Node::new(2); node1.children.push(Box::new(node2)); let node3 = Node::new(3); node1.children.push(Box::new(node3)); root.children.push(Box::new(node1)); let mut node4 = Node::new(4); let node5 = Node::new(5); node4.children.push(Box::new(node5)); root.children.push(Box::new(node4)); dump(root); } // 木構造を行きがけ順(先行順)でダンプする fn dump(node: Node) { println!("node({})", node.value); for child in node.children { dump(*child); } }
まあ、簡単です。ヒープに領域を確保するにはBoxを使う、というのはRust独特ですが、それを除けばCやJavaに慣れた人なら読めるコードだと思います。所有権云々で気を付けなければいけないのは、main()の中で木構造を作っているところで、たとえばこんなふうに、「Nodeを作ったらとりあえず親に登録しておこう」という方針で書くと、変数が所有権を失って以後使えなくなるので、順番に気を付ける必要がある、ということぐらいです。
fn main() { let mut root = Node::new(0); let mut node1 = Node::new(1); root.children.push(Box::new(node1)); // node1をrootの子として登録した時点で、変数node1は所有権を失う let node2 = Node::new(2); let node3 = Node::new(3); node1.children.push(Box::new(node2)); // だから、ここでnode1は使えない node1.children.push(Box::new(node3)); let mut node4 = Node::new(4); root.children.push(Box::new(node4)); let node5 = Node::new(5); node4.children.push(Box::new(node5)); dump(root); }
上記のソースだと、こんなエラーが出ます(抜粋)。
error[E0382]: borrow of moved value: `node1` --> src\main.rs:23:5 | 19 | let mut node1 = Node::new(1); | --------- move occurs because `node1` has type `Node`, which does not implement the `Copy` trait 20 | root.children.push(Box::new(node1)); | ----- value moved here ... 23 | node1.children.push(Box::new(node2)); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ value borrowed here after move
……まあ、その程度のことで、ここまでは簡単なんです。
しかし、プログラミング言語の解析木だと、こんな単純な木構造では済まず、「子から親への参照」が必要になる部分もあります。samplanのような言語(CやJavaも同じですが)では、波括弧で囲まれたブロックがスコープを示し、各ブロックの中では、その外側のブロックで宣言された変数とかが参照できます。そうなると、子のブロックから親のブロックへの参照が保持できないと嬉しくありません。
それをやってみたらえらく大変だったのですが、その話はまた次回に。乞うご期待!
