Erhalten einer veränderbaren Referenz durch Iterieren einer rekursiven Struktur

Question

Ich versuche, eine rekursive Datenstruktur iterativ zu navigieren, um Elemente an einer bestimmten Position einzufügen. Um mein begrenztes Verständnis bedeutet dies eine veränderbare Bezugnahme auf die Wurzel der Struktur zu nehmen und sie nacheinander durch einen Verweis auf seine Folger ersetzt:

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)

jedoch dies nicht gelingt:

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 

Dies macht Sinn, da sich sowohl anchor als auch node auf die gleiche Struktur beziehen, aber nach der Destrukturierung kümmert es mich eigentlich nicht mehr um anchor. Wie kann back() mit Safe Rust korrekt implementiert werden?

Answer 1

Es ist möglich, ... aber ich wünschte, ich hätte eine elegantere Lösung.

Der Trick von anchor, zu borgen ist nicht und somit zwischen zwei Akkumulatoren einen Hut zu bringen:

• eine hält den Verweis auf den aktuellen Knoten
• den anderen zugeordnet ist, um den Verweis auf den nächsten Knoten

Dies führt mich zu:

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

Nicht gerade hübsch, aber dieses Etwas, das der Border Checker bekommen kann, ist also ¯ \ _ (ツ) _/¯.

@ker hat hierzu verbesserte sich um eine unbenannte temporäre Schaffung:

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

Der Trick besteht darin, dass unter Verwendung von {anchor}bewegt der Gehalt an anchor in eine unbenannte vorübergehende, auf dem das Spiel ausführt. Daher sind wir im match Block nicht von anchor, sondern vom temporären, was uns erlaubt, anchor zu modifizieren. Siehe den zugehörigen Blogpost Stuff the Identity Function Does (in Rust).

Answer 2

Sie können die Rekursion verwenden, um den Border Checker zu erfüllen. Dies hat den Nachteil, dass für jeden Eintrag in Ihrer Liste ein Stapelrahmen erstellt wird. Wenn Ihre Liste lang ist, wird dies definitiv zu einem Stapelüberlauf führen. LLVM wird die Node::back Verfahren in eine Schleife (siehe die LLVM IR auf der playground generiert) optimieren

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

Es funktioniert:

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