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字段的值，并在路径完全穷尽时显示这些值。我的第一个想法是从节点到其父节点建立反向链接，但我找到的唯一一个例子是 DList中的Rawlink，这让我有点害怕。我的下一个希望是迭代器实现（如果我能让它工作）会自然地借助这样的事情。这是要追求的正确轨迹吗？

- Ray

---

能否请您发布错误信息？这样可以更快地解决问题。 - Chris Morgan

啊，严格的词法作用域。在一些地方会引起许多烦人的问题，这种情况就是其中之一。 - Chris Morgan

这与https://dev59.com/uoXca4cB1Zd3GeqPIG1Y类似，但希望返回“node”，这意味着我无法说服编译器在没有“unsafe”的情况下接受它。 - huon

@ChrisMorgan，您能详细说明为什么最终只剩下对盒子的引用是不好的吗？这是风格问题还是存在更隐匿的危险？ - Ray

@dbaupp，涉及到不安全的解决方案是什么？ - Ray

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()检查映射中是否有值，然后使用索引检索该值。这意味着该值被查找了两次，但这是我找到的无需使用不安全代码就能使其工作的唯一方法。

另外，您可以将Tree中的root更改为Node，而不是Box<Node>。

- Francis Gagné

---

谢谢你的回答！也许有一种使用不安全代码实现迭代方法的方式吗？ - Ray