Rust vs Borrow Checker中的树遍历 [英] Tree traversal in Rust vs Borrow Checker
问题描述
我正在尝试在Rust中实现树结构，对其进行遍历并对其进行修改，但是借阅检查器遇到了麻烦。我的设置大致如下：
I'm attempting to implement a tree structure in Rust, traverse it, and modify it, and I'm running into trouble with the borrow checker. My setup is more or less the following:
#![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 ，然后为路径的其余部分添加不匹配的节点
I have mutable references here because I want to be able to mutate the node returned by the method. For example, an add method would call traverse_path and then add nodes for the remainder of the path that did not have matching nodes.
这会产生以下错误：
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
我知道为什么借阅检查器不喜欢此代码，但我不知道
I understand why the borrow checker doesn't like this code, but I don't know how to make this work.
我还尝试了使用迭代器的替代实现，并使用如下代码：
I also attempted an alternate implementation using an iterator using code like the following:
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
}
}
错误最终与生命周期相关：
The errors here ended up being lifetime-related:
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 $ c>，这吓到我了。我的下一个希望是，迭代器实现（如果我可以使其工作）将自然地适合于这种事情。
Another thing I'm interested in is to collect the values of the decoration field for matching nodes and display these values if the path was fully exhausted. My very first thought was to have backlinks from the nodes to their parents, but the only example of this I found was Rawlink in DList, which scared me off. My next hope is that the iterator implementation (if I can get it to work) would lend itself naturally to something like that. Is that the right track to pursue?
推荐答案
这是您的第一种方法的变体，使用递归避免借入冲突。等效迭代程序无法编译，因为Rust在处理指向可变值的可变借用指针时过于严格。
Here's a variant of your first approach, using recursion to avoid borrowing conflicts. The iterative equivalent fails to compile because Rust is too strict when dealing with mutable borrowed pointers to mutable values.
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节点;您无需向用户透露您在实现中使用的是 Box 。另外，请参阅 Node :: traverse_path 如何首先使用 contains_key（） ，然后使用索引检索值。这意味着该值被查询了两次，但这是我发现无需使用不安全代码即可完成此工作的唯一方法。
Note that I've changed the return type from &mut Box<Node> to &mut Node; you don't need to reveal to your users that you're using a Box in your implementation. Also, see how Node::traverse_path first checks if there's a value in the map using contains_key(), then retrieving the value using indexing. This means that the value is looked up twice, but that's the only way I've found to make this work without requiring unsafe code.
PS：您可以更改< 树中的code> root 成为 Node 的节点，而不是 Box< Node> 。
P.S.: You can change the root in Tree to be a Node, rather than a Box<Node>.
这篇关于Rust vs Borrow Checker中的树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
