再帰的構造を反復することによって可変参照を取得する

Question

私は、反復的なデータ構造を反復的に特定の位置に要素を挿入するためにナビゲートしようとしています。私の限られた理解に、これは構造のルートへの変更可能な参照を取り、連続的にそのフォロワーを参照することによって、それを置き換える意味：

type Link = Option<Box<Node>>; 

struct Node { 
    next: Link 
} 

struct Recursive { 
    root: Link 
} 

impl Recursive { 
    fn back(&mut self) -> &mut Link { 
     let mut anchor = &mut self.root; 
     while let Some(ref mut node) = *anchor { 
      anchor = &mut node.next; 
     } 
     anchor 
    } 
} 

(Rust playground link)

しかし、これは失敗します。

error[E0499]: cannot borrow `anchor.0` as mutable more than once at a time 
    --> src/main.rs:14:24 
    | 
14 |   while let Some(ref mut node) = *anchor { 
    |      ^^^^^^^^^^^^ 
    |      | 
    |      second mutable borrow occurs here 
    |      first mutable borrow occurs here 
... 
18 |  } 
    |  - first borrow ends here 

error[E0506]: cannot assign to `anchor` because it is borrowed 
    --> src/main.rs:15:13 
    | 
14 |   while let Some(ref mut node) = *anchor { 
    |      ------------ borrow of `anchor` occurs here 
15 |    anchor = &mut node.next; 
    |    ^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `anchor` occurs here 

error[E0499]: cannot borrow `*anchor` as mutable more than once at a time 
    --> src/main.rs:17:9 
    | 
14 |   while let Some(ref mut node) = *anchor { 
    |      ------------ first mutable borrow occurs here 
... 
17 |   anchor 
    |   ^^^^^^ second mutable borrow occurs here 
18 |  } 
    |  - first borrow ends here 

を

anchorとnodeの両方が同じ構造を指していますが、実際にはそれを分解した後にはもうanchorは気にしません。

back()は安全な錆を使用して正しく実装できますか？

Answer 1

をNode::back方法を最適化します...しかし、私はもっとエレガントな解決策があればいいのに。

トリックanchorから借りることではないので、2行のアキュムレータとの間に両立する：次のノードへの参照を割り当てられている現在のノード

他の参照を保持

これはに私をリード：

impl Recursive { 
    fn back(&mut self) -> &mut Link { 
     let mut anchor = &mut self.root; 

     loop { 
      let tmp = anchor; 
      if let Some(ref mut node) = *tmp { 
       anchor = &mut node.next; 
      } else { 
       anchor = tmp; 
       break; 
      } 
     } 

     anchor 
    } 
} 

あまりにもかわいいですが、この借りたチェッカーが\ \ _（ツ）_ /¯の後ろに来ることができる何か。

@ker無名一時的に作成することで、この上に改善されている：

impl Recursive { 
    fn back(&mut self) -> &mut Link { 
     let mut anchor = &mut self.root; 

     loop { 
      match {anchor} { 
       &mut Some(ref mut node) => anchor = &mut node.next, 
       other => return other, 
      } 
     } 
    } 
} 

ここでトリック{anchor}移動一致が実行される名前一時的にanchorのコンテンツを使用することです。したがって、matchブロックではanchorから借りていませんが、一時的にはanchorを変更する必要はありません。関連するブログ記事Stuff the Identity Function Does (in Rust)を参照してください。

Answer 2

再帰を使用して、貸借チェッカーを満たすことができます。これには、リスト内のすべての項目のスタックフレームを作成するという欠点があります。あなたのリストが長い場合、これは間違いなくスタックオーバーフローに繋がります。 LLVMは、それが可能である（LLVM IRはplayground上で生成参照）ループに

impl Node { 
    fn back(&mut self) -> &mut Link { 
     match self.next { 
      Some(ref mut node) => node.back(), 
      None => &mut self.next, 
     } 
    } 
} 

impl Recursive { 
    fn back(&mut self) -> Option<&mut Link> { 
     self.root.as_mut().map(|node| node.back()) 
    } 
} 

Answer 3

それは動作します：

fn back(&mut self) -> &mut Link { 
    let mut anchor = &mut self.root; 
    while anchor.is_some(){ 
     anchor = &mut {anchor}.as_mut().unwrap().next; 
    } 
    anchor 
}