녹이에서 트리 탐색과 빌려 오기 검사기

Question

녹 구조에서 트리 구조를 구현하고 트래버스하고 수정하며 차용 검사 기능에 문제가 있습니다. 제 설정은 다소 차이가 있습니다 :

#![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이었습니다. 그게 제가 겁 먹었습니다. 내 다음 희망은 iterator 구현 (만약 내가 그것을 얻을 수있다) 자연스럽게 뭔가 빌려줄 것입니다. 그게 옳은 길인가?

Answer 1

차용 충돌을 피하기 위해 재귀를 사용하는 첫 번째 방법의 변형입니다. 변경 가능한 값에 대한 변경 가능한 빌린 포인터를 처리 할 때 Rust가 너무 엄격하기 때문에 반복적으로 동일한 컴파일을 컴파일 할 수 없습니다. 내가 &mut Box<Node>&mut Node까지 반환 형식을 변경 한

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) 
    } 
} 

참고; 구현시 Box을 사용하고 있음을 사용자에게 알릴 필요는 없습니다. 또한 Node::traverse_path이 contains_key()을 사용하여지도에 값이 있는지 먼저 확인한 다음 색인을 사용하여 값을 검색하는 방법을 확인하십시오. 이것은 값이 두 번 조회된다는 것을 의미하지만 안전하지 않은 코드를 요구하지 않고이 작업을 수행하는 유일한 방법입니다.

추신 : 이 아닌 Tree의 root을 Node으로 변경할 수 있습니다.