前回の記事、Rustで木構造の続きです。
前回の木は、親が子への参照を持つ1方向の木でしたが、今回は、子が親への参照も持つようにします。親が子への参照を持つだけであれば、各ノードを指す参照は必ずひとつなのでBoxが使えましたが、子が親への参照も持つとなると各ノードが複数の箇所から参照されることになり、かつ、循環参照になります。こういう場合は、親から子への参照を参照カウンタ式のスマートポインタ型であるRc(reference countingの略)とし、子から親への参照を弱参照(weak reference)で保持します。
図にするとこんな感じ。
題材としては、「The Rust Programming Language」の以下のページでやっていることそのものです。
doc.rust-jp.rs
だったら丸写しするだけじゃん、と思われるでしょうが、まあ慣れない言語で自分で組んでみるとそんなことでもはまるものです。
上の図にある木構造を作って、それを行きがけ順で走査するプログラムが以下。
use std::rc::Weak; use std::rc::Rc; use std::cell::RefCell; struct Node { value: i32, children: RefCell<Vec<Rc<Node>>>, parent: RefCell<Weak<Node>> } impl Node { fn new(value: i32) -> Node { Node { value: value, children: RefCell::new(Vec::new()), parent: RefCell::new(Weak::new()) } } } fn main() { let root = Rc::new(Node::new(0)); let node1 = Rc::new(Node::new(1)); *node1.parent.borrow_mut() = Rc::downgrade(&root); let node2 = Rc::new(Node::new(2)); *node2.parent.borrow_mut() = Rc::downgrade(&node1); node1.children.borrow_mut().push(node2); let node3 = Rc::new(Node::new(3)); *node3.parent.borrow_mut() = Rc::downgrade(&node1); node1.children.borrow_mut().push(node3); root.children.borrow_mut().push(node1); let node4 = Rc::new(Node::new(4)); *node4.parent.borrow_mut() = Rc::downgrade(&root); let node5 = Rc::new(Node::new(5)); *node5.parent.borrow_mut() = Rc::downgrade(&node4); node4.children.borrow_mut().push(node5); root.children.borrow_mut().push(node4); dump(&root); } fn dump(node: &Rc<Node>) { print!("node({}) ", node.value); match node.parent.borrow().upgrade() { Some(parent) => { println!("parent..{}", parent.value); }, None => { println!("parent..None"); } } for child in &*node.children.borrow() { dump(child); } }
実行結果はこんな感じ。
node(0) parent..None node(1) parent..0 node(2) parent..1 node(3) parent..1 node(4) parent..0 node(5) parent..4
単にRcとWeakで木構造を作るだけなら、こう書けばよいのでは、と思うかもしれませんが、
use std::rc::Weak; use std::rc::Rc; struct Node { value: i32, children: Vec<Rc<Node>>, parent: Weak<Node> } impl Node { fn new(value: i32) -> Node { Node { value: value, children: Vec::new(), parent: Weak::new() } } } fn main() { let root = Rc::new(Node::new(0)); let node1 = Rc::new(Node::new(1)); node1.parent = Rc::downgrade(&root); root.children.push(node1); }
これだと、以下のエラーが出ます。Rustでは、「共有されているものには書き込めない」ので、Rcの指す先に書き込むことはできません。
error[E0594]: cannot assign to data in an `Rc` --> src\main.rs:24:5 | 24 | node1.parent = Rc::downgrade(&root); | ^^^^^^^^^^^^ cannot assign | = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Rc<Node>` error[E0596]: cannot borrow data in an `Rc` as mutable --> src\main.rs:25:5 | 25 | root.children.push(node1); | ^^^^^^^^^^^^^^^^^^^^^^^^^ cannot borrow as mutable | = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Rc<Node>`
Rcの指す先のものに書き込みたければ、最初に挙げたプログラムのように、RefCellで包む必要があります。
で、ここまでは、上で挙げた「The Rust Programming Language」に書いてあることそのものなんですが。
私がはまったのは、dump()関数の中の以下のループのところです。
for child in &*node.children.borrow() { dump(child); }
たとえば、main()の中で、rootの子としてnode1を足すところにはこう書いてあって、
root.children.borrow_mut().push(node1);
RefCellからborrow_mut()で書き換え可能な参照を借用し、それに対してpush()をいきなり呼んでいる、ということは、root.children.borrow_mut()はVecと同じように扱えるのだな、と思って、dump()関数を最初はこう書きました。
fn dump(node: Rc<Node>) { // 引数の型も違う。後述。 print!("node({}) ", node.value); match node.parent.borrow().upgrade() { Some(parent) => { println!("parent..{}", parent.value); }, None => { println!("parent..None"); } } for child in node.children.borrow() { // ←ここ dump(child); } }
しかしこれはコンパイルエラー。
error[E0277]: `Ref<'_, Vec<Rc<Node>>>` is not an iterator
--> src\main.rs:58:18
|
58 | for child in node.children.borrow() {
| ^^^^^^^^^^^^^^^^^^^^^^ `Ref<'_, Vec<Rc<Node>>>` is not an iterator
|
= help: the trait `Iterator` is not implemented for `Ref<'_, Vec<Rc<Node>>>`
= note: required because of the requirements on the impl of `IntoIterator` for `Ref<'_, Vec<Rc<Node>>>`
For more information about this error, try `rustc --explain E0277`.node.children.borrow()の型はVec
そこで、手動で参照を外すため*を付けたら、
for child in *node.children.borrow() { dump(child); }
これもコンパイルエラー。
error[E0507]: cannot move out of dereference of `Ref<'_, Vec<Rc<Node>>>`
--> src\main.rs:58:18
|
58 | for child in *node.children.borrow() {
| ^^^^^^^^^^^^^^^^^^^^^^^
| |
| value moved due to this implicit call to `.into_iter()`
| move occurs because value has type `Vec<Rc<Node>>`, which does not implement the `Copy` trait
|
note: this function takes ownership of the receiver `self`, which moves value
help: consider iterating over a slice of the `Vec<Rc<Node>>`'s content to avoid moving into the `for` loop
|
58 | for child in &*node.children.borrow() {
| +
For more information about this error, try `rustc --explain E0507`.まあこのエラーは見慣れてる。Vecはコピーできないから、こういう場合は&を付けて参照を見ればよいのだ。
fn dump(node: &Rc<Node>) { print!("node({}) ", node.value); match node.parent.borrow().upgrade() { Some(parent) => { println!("parent..{}", parent.value); }, None => { println!("parent..None"); } } for child in &*node.children.borrow() { dump(child); } }
というわけでこうなって、実際動いたわけですが、なんかこの「&*」のあたり、「これでいいの?」と思ってしまう。
ていうかRustの参照外し演算子の「*」ってなんで前置なの? もちろんCの*も前置ですが、これはCの作者Dennis Ritchieが、1981年に後置の方がよかったと指摘され、「but by then it was too late to change. 」(しかし、その時には、変更するにはもう遅すぎた」と言っているような仕様なのに。自動参照外しがあるからいいというものではなく、だいたい自動とか暗黙とかそういったものは混乱を招くものなのに。まさに今回私がはまったように。
なにかこう、Rust初心者の私の知らない理由があるんでしょうか。
