Rust與遍歷Checker的樹遍歷

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()檢查地圖中是否有值，然後使用索引檢索值。這意味着該值會被查找兩次，但這是我發現在不需要不安全代碼的情況下完成此項工作的唯一方法。

P.S .:您可以將Tree中的root更改爲Node，而不是Box<Node>。