7

Rust でツリー構造を実装し、トラバースし、変更しようとしていますが、借用チェッカーで問題が発生しています。私のセットアップは多かれ少なかれ次のとおりです。

#![feature(slicing_syntax)]

use std::collections::HashMap;

#[deriving(PartialEq, Eq, Hash)]
struct Id {
    id: int,  // let’s pretend it’s that
}

struct Node {
    children: HashMap<Id, Box<Node>>,
    decoration: String,
    // other fields
}

struct Tree {
   root: Box<Node>
}

impl Tree {
    /// Traverse the nodes along the specified path.
    /// Return the node at which traversal stops either because the path is exhausted
    /// or because there are no more nodes matching the path.
    /// Also return any remaining steps in the path that did not have matching nodes.
    fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Box<Node>, &'p [Id]) {
        let mut node = &mut self.root;
        loop {
            match node.children.get_mut(&path[0]) {
                Some(child_node) => {
                    path = path[1..];
                    node = child_node;
                },
                None => {
                    break;
                }
            }
        }
        (node, path)
    }
}

メソッドによって返されたノードを変更できるようにしたいので、ここに変更可能な参照があります。たとえば、addメソッドが呼び出しtraverse_pathて、一致するノードを持たないパスの残りのノードを追加します。

これにより、次のエラーが生成されます。

s.rs:28:19: 28:32 error: cannot borrow `node.children` as mutable more than once at a time
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:28:19: 28:32 note: previous borrow of `node.children` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.children` until the borrow ends
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:39:6: 39:6 note: previous borrow ends here
s.rs:25     fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Box<Node>, &'p [Id]) {
...
s.rs:39     }
            ^
s.rs:31:21: 31:38 error: cannot assign to `node` because it is borrowed
s.rs:31                     node = child_node;
                            ^~~~~~~~~~~~~~~~~
s.rs:28:19: 28:32 note: borrow of `node` occurs here
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:38:10: 38:14 error: cannot borrow `*node` as mutable more than once at a time
s.rs:38         (node, path)
                 ^~~~
s.rs:28:19: 28:32 note: previous borrow of `node.children` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.children` until the borrow ends
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:39:6: 39:6 note: previous borrow ends here
s.rs:25     fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Box<Node>, &'p [Id]) {
...
s.rs:39     }
            ^
error: aborting due to 3 previous errors

借用チェッカーがこのコードを好まない理由は理解できますが、これを機能させる方法がわかりません。

また、次のようなコードを使用して反復子を使用して別の実装を試みました。

struct PathIter<'a> {
    path: &'a [Id],
    node: &'a mut Box<Node>
}
impl<'a> Iterator<Box<Node>> for PathIter<'a> {
    fn next(&mut self) -> Option<Box<Node>> {
        let child = self.node.get_child(&self.path[0]);
        if child.is_some() {
            self.path = self.path[1..];
            self.node = child.unwrap();
        }
        child
    }
}

ここでのエラーは、生涯に関連するものになりました。

src/http_prefix_tree.rs:147:27: 147:53 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
src/http_prefix_tree.rs:147     let child = self.node.get_child(&self.path[0]);
                                                  ^~~~~~~~~~~~~~~~~~~~~~~~~~
src/http_prefix_tree.rs:146:3: 153:4 help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<Box<Node>>
src/http_prefix_tree.rs:146   fn next(&mut self) -> Option<Box<Node>> {
src/http_prefix_tree.rs:147     let child = self.node.get_child(&self.path[0]);
src/http_prefix_tree.rs:148     if child.is_some() {
src/http_prefix_tree.rs:149       self.path = self.path[1..];
src/http_prefix_tree.rs:150       self.node = child.unwrap();
src/http_prefix_tree.rs:151     }

私が興味を持っているもう 1 つのことは、decoration一致するノードのフィールドの値を収集し、パスが完全に使い果たされた場合にこれらの値を表示することです。私の最初の考えは、ノードからその親へのバックリンクを持つことでしたが、私が見つけた唯一の例RawlinkはDList. 私の次の希望は、反復子の実装 (機能させることができれば) が自然にそのようなものに役立つことです。それは追求する正しい道ですか？

4

1 に答える 1

5

これは、再帰を使用して借用の競合を回避する、最初のアプローチの変形です。変更可能な値への変更可能な借用ポインターを処理する場合、Rust は厳しすぎるため、反復的な等価物はコンパイルに失敗します。

impl Node {
    fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Node, &'p [Id]) { // '
        if self.children.contains_key(&path[0]) {
            self.children[path[0]].traverse_path(path[1..])
        } else {
            (self, path)
        }
    }
}

impl Tree {
    /// Traverse the nodes along the specified path.
    /// Return the node at which traversal stops either because the path is exhausted
    /// or because there are no more nodes matching the path.
    /// Also return any remaining steps in the path that did not have matching nodes.
    fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Node, &'p [Id]) { // '
        self.root.traverse_path(path)
    }
}

戻り値の型を から&mut Box<Node>に変更したことに注意してください&mut Node。Box実装でを使用していることをユーザーに明らかにする必要はありません。また、Node::traverse_path最初に を使用してマップに値があるかどうかを確認しcontains_key()、次にインデックスを使用して値を取得する方法も参照してください。これは、値が 2 回検索されることを意味しますが、安全でないコードを必要とせずにこれを機能させる唯一の方法です。

PS: をではなくrootに変更できます。TreeNodeBox<Node>

于 2014-12-31T10:34:00.547 に答える