Uzyskiwanie zmiennego odwołania przez iterowanie struktury rekurencyjnej

Question

Próbuję iteracyjnie nawigować w rekurencyjnej strukturze danych, aby wstawić elementy w określonej pozycji. Do mojego ograniczonego rozumienia, oznacza to, biorąc zmienny odniesienie do korzenia struktury i sukcesywnie zastępując je przez odniesienie do jego naśladowcy:

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)

Jednak ta kończy się niepowodzeniem:

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 

Ma to sens, ponieważ zarówno anchor, jak i odnoszą się do tej samej struktury, ale ja właściwie nie interesuje mnie już anchor po destrukcji.

Jak można prawidłowo zaimplementować back() przy użyciu bezpiecznej rdzy?

Answer 1

Jest to możliwe ... ale chciałbym mieć bardziej eleganckie rozwiązanie.

Sztuką jest, aby nie pożyczać od anchor, a zatem żonglować między dwoma akumulatorami:

• jednego gospodarstwa odniesienie do bieżącego węzła
• druga jest przypisany odniesienie do następnego węzła

To prowadzi mnie do:

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

Niezupełnie ładne, ale to coś, co może sprawdzić pożyczający, więc ¯ \ _ (ツ) _/¯.

@ker poprawiła się na to poprzez stworzenie nienazwany tymczasowa:

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

Sztuką jest to, że za pomocą {anchor}ruchy Zawartość anchor w nienazwany tymczasowa, na której wykonuje mecz. Dlatego w bloku match nie pożyczamy od anchor, ale z tymczasowego, pozostawiając nam swobodę modyfikacji anchor. Zobacz powiązany wpis na blogu: Stuff the Identity Function Does (in Rust).

Answer 2

Możesz użyć rekursji, aby spełnić warunki sprawdzania zdolności kredytowej. Ma to tę wadę, że tworzy ramkę stosu dla każdego elementu na liście. Jeśli twoja lista jest długa, z pewnością wystąpi przepełnienie stosu. LLVM zoptymalizuje metodę Node::back w pętlę (patrz LLVM IR generowane na 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

Działa:

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