Ottenere un riferimento mutevole iterando una struttura ricorsiva

Question

sto cercando di navigare una struttura dati ricorsiva iterativamente per inserire elementi in una certa posizione. La mia comprensione limitata, ciò significa assumere un riferimento mutevole alla radice della struttura e successivamente sostituzione con un riferimento alla sua follower:

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)

Tuttavia, questo fallisce:

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 

Questo ha senso in quanto sia anchor che node si riferiscono alla stessa struttura, ma in realtà non mi interessa più di anchor dopo averlo distrutto.

Come potrebbe back() essere implementato correttamente utilizzando Rust sicuro?

Answer 1

E 'possibile ... ma vorrei avere una soluzione più elegante.

Il trucco è di non prendere in prestito da anchor, e quindi destreggiarsi tra due accumulatori:

• uno tiene il riferimento al nodo corrente
• l'altro è assegnato il riferimento al nodo successivo

Questo mi porta a:

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

Non esattamente bella, ma questo qualcosa il correttore prestito può ottenere dietro in modo ¯ \ _ (ツ) _/¯.

@ker ha migliorato su questo creando un temporaneo anonimo:

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

Il trucco è che l'utilizzo {anchor}muove il contenuto di anchor in un temporaneo anonimo sul quale partita esegue. Pertanto, nel blocco match non stiamo prendendo in prestito da anchor ma dalla temporanea, lasciandoci liberi di modificare anchor. Vedere il relativo post sul blog Stuff the Identity Function Does (in Rust).

Answer 2

È possibile utilizzare la ricorsione per soddisfare il correttore prestito. Questo ha lo svantaggio di creare una cornice di stack per ogni elemento della tua lista. Se la tua lista è lunga, questo sicuramente finirà in uno stack overflow. LLVM ottimizzerà il metodo Node::back in un ciclo (vedere la LLVM IR generata sulla 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

Funziona:

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