在Rust与借阅检查器中的树遍历

Question

我正在尝试在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     }

我感兴趣的另一件事是收集decoration匹配节点的字段值,如果路径完全耗尽则显示这些值.我非常的第一个想法是有从节点反向链接到他们的父母,但我发现这是唯一的例子是Rawlink在DList,这吓死我了.我的下一个希望是迭代器实现(如果我可以让它工作)将自然适用于类似的东西.这是追求的正确轨道吗？

Answer 1

这是您的第一种方法的变体,使用递归来避免借用冲突.迭代等价物无法编译,因为在处理可变值的可变借用指针时,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(),然后使用索引检索值.这意味着该值被查找两次,但这是我发现使这项工作不需要不安全代码的唯一方法.

PS:您可以将rootin 更改Tree为a Node,而不是a Box<Node>.