Come posso creare la mia struttura dati con un iteratore che restituisce riferimenti mutabili?

Question

Ho creato una struttura dati in Rust e voglio creare iteratori per questo. Gli iteratori immutabili sono abbastanza facili. Al momento ho questo, e funziona bene:

// This is a mock of the "real" EdgeIndexes class as 
// the one in my real program is somewhat complex, but 
// of identical type 

struct EdgeIndexes; 

impl Iterator for EdgeIndexes { 
    type Item = usize; 
    fn next(&mut self) -> Option<Self::Item> { 
     Some(0) 
    } 

    fn size_hint(&self) -> (usize, Option<usize>) { 
     (0, None) 
    } 
} 

pub struct CGraph<E> { 
    nodes: usize, 
    edges: Vec<E>, 
} 

pub struct Edges<'a, E: 'a> { 
    index: EdgeIndexes, 
    graph: &'a CGraph<E>, 
} 

impl<'a, E> Iterator for Edges<'a, E> { 
    type Item = &'a E; 

    fn next(&mut self) -> Option<Self::Item> { 
     match self.index.next() { 
      None => None, 
      Some(x) => Some(&self.graph.edges[x]), 
     } 
    } 

    fn size_hint(&self) -> (usize, Option<usize>) { 
     self.index.size_hint() 
    } 
} 

Voglio creare un iteratore che restituisce riferimenti mutabili pure. Ho provato a fare questo, ma non riesco a trovare un modo per farlo compilare:

pub struct MutEdges<'a, E: 'a> { 
    index: EdgeIndexes, 
    graph: &'a mut CGraph<E> 
} 

impl<'a, E> Iterator<&'a mut E> for MutEdges<'a, E> { 
    fn next(&mut self) -> Option<&'a mut E> { 
     match (self.index.next()) { 
      None => None, 
      Some(x) => Some(self.graph.edges.get_mut(x)) 
     } 
    } 

    fn size_hint(&self) -> (uint, Option<uint>) { 
     self.index.size_hint() 
    } 
} 

Compilazione questo si traduce nel seguente errore:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements 
    --> src/main.rs:53:24 
    | 
53 |    Some(x) => self.graph.edges.get_mut(x), 
    |      ^^^^^^^^^^^^^^^^ 
    | 
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the body at 50:45... 
    --> src/main.rs:50:46 
    | 
50 |  fn next(&mut self) -> Option<Self::Item> { 
    | ______________________________________________^ 
51 | |   match self.index.next() { 
52 | |    None => None, 
53 | |    Some(x) => self.graph.edges.get_mut(x), 
54 | |   } 
55 | |  } 
    | |_____^ 
note: ...so that reference does not outlive borrowed content 
    --> src/main.rs:53:24 
    | 
53 |    Some(x) => self.graph.edges.get_mut(x), 
    |      ^^^^^^^^^^^^^^^^ 
note: but, the lifetime must be valid for the lifetime 'a as defined on the body at 50:45... 
    --> src/main.rs:50:46 
    | 
50 |  fn next(&mut self) -> Option<Self::Item> { 
    | ______________________________________________^ 
51 | |   match self.index.next() { 
52 | |    None => None, 
53 | |    Some(x) => self.graph.edges.get_mut(x), 
54 | |   } 
55 | |  } 
    | |_____^ 
note: ...so that types are compatible (expected std::iter::Iterator, found std::iter::Iterator) 
    --> src/main.rs:50:46 
    | 
50 |  fn next(&mut self) -> Option<Self::Item> { 
    | ______________________________________________^ 
51 | |   match self.index.next() { 
52 | |    None => None, 
53 | |    Some(x) => self.graph.edges.get_mut(x), 
54 | |   } 
55 | |  } 
    | |_____^ 

io sono sicuro come interpretare questi errori e come cambiare il mio codice per consentire MutEdges di restituire riferimenti mutabili.

Collegamento a playground with code.

Answer 1

Non è possibile compilarlo perché i riferimenti mutabili sono più restrittivi dei riferimenti immutabili. Una versione ridotta che illustra il problema è questo:

struct MutIntRef<'a> { 
    r: &'a mut i32 
} 

impl<'a> MutIntRef<'a> { 
    fn mut_get(&mut self) -> &'a mut i32 { 
     &mut *self.r 
    } 
} 

fn main() { 
    let mut i = 42; 
    let mut mir = MutIntRef { r: &mut i }; 
    let p = mir.mut_get(); 
    let q = mir.mut_get(); 
} 

che produce lo stesso errore:

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements 
--> src/main.rs:7:9 
    | 
7 |   &mut *self.r 
    |   ^^^^^^^^^^^^ 
    | 
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the body at 6:41... 
--> src/main.rs:6:42 
    | 
6 |  fn mut_get(&mut self) -> &'a mut i32 { 
    | __________________________________________^ 
7 | |   &mut *self.r 
8 | |  } 
    | |_____^ 
note: ...so that reference does not outlive borrowed content 
--> src/main.rs:7:9 
    | 
7 |   &mut *self.r 
    |   ^^^^^^^^^^^^ 
note: but, the lifetime must be valid for the lifetime 'a as defined on the body at 6:41... 
--> src/main.rs:6:42 
    | 
6 |  fn mut_get(&mut self) -> &'a mut i32 { 
    | __________________________________________^ 
7 | |   &mut *self.r 
8 | |  } 
    | |_____^ 
note: ...so that reference does not outlive borrowed content 
--> src/main.rs:7:9 
    | 
7 |   &mut *self.r 
    |   ^^^^^^^^^^^^ 

Se diamo uno sguardo alla funzione principale, otteniamo due riferimenti mutevoli chiamati p e q che entrambi alias la posizione di memoria di i. Questo non è permesso. In Rust non possiamo avere due riferimenti mutabili che siano alias e siano entrambi utilizzabili. La motivazione per questa restrizione è l'osservazione che la mutazione e l'aliasing non giocano bene insieme rispetto alla sicurezza della memoria. Quindi, è positivo che il compilatore abbia rifiutato il codice. Se qualcosa di simile fosse compilato, sarebbe facile ottenere tutti i tipi di errori di corruzione della memoria.

Il modo in cui Rust evita questo tipo di pericolo è mantenere al massimo un riferimento mutabile utilizzabile. Quindi, se vuoi creare un riferimento mutabile a X sulla base di un riferimento mutabile a Y, dove X è di proprietà di Y, è meglio assicurarsi che finché esiste il riferimento a X, non possiamo più toccare l'altro riferimento a Y . In Rust questo è ottenuto attraverso vite e prestiti. Il compilatore considera il riferimento originale da prendere in prestito in questo caso e questo ha un effetto anche sul parametro lifetime del riferimento risultante. Se cambiamo

fn mut_get(&mut self) -> &'a mut i32 { 
    &mut *self.r 
} 

a

fn mut_get(&mut self) -> &mut i32 { // <-- no 'a anymore 
    &mut *self.r // Ok! 
} 

il compilatore ferma lamentarsi di questa funzione get_mut. Ora restituisce un riferimento con un parametro lifetime corrispondente a &self e non più a 'a. Questo rende mut_get una funzione con cui "prendi in prestito" self. Ed è per questo che il compilatore si lamenta una posizione diversa:

error[E0499]: cannot borrow `mir` as mutable more than once at a time 
    --> src/main.rs:15:17 
    | 
14 |   let p = mir.mut_get(); 
    |     --- first mutable borrow occurs here 
15 |   let q = mir.mut_get(); 
    |     ^^^ second mutable borrow occurs here 
16 |  } 
    |  - first borrow ends here 

A quanto pare, il compilatore davvero fatto considerare mir da prendere in prestito. Questo è buono. Ciò significa che ora c'è solo un modo per raggiungere la posizione di memoria di i: p.

Ora ci si potrebbe chiedere: come hanno fatto gli autori delle librerie standard a scrivere l'iteratore vettoriale mutabile? La risposta è semplice: hanno usato un codice non sicuro. Non c'è altro modo. Il compilatore Rust semplicemente non sa che ogni volta che chiedi a un iteratore vettoriale mutabile per l'elemento successivo, ottieni sempre un riferimento diverso e mai lo stesso riferimento due volte. Naturalmente, sappiamo che un tale iteratore non ti darà lo stesso riferimento due volte. E questo rende sicuro offrire questo tipo di interfaccia a cui sei abituato. Non è necessario "congelare" un tale iteratore. Se i riferimenti restituiti da un iteratore non si sovrappongono, è sicuro che non devono prendere in prestito l'iteratore per accedere a un elemento. Internamente, questo viene fatto usando un codice non sicuro (trasformando i puntatori grezzi in riferimenti).

La soluzione semplice per il tuo problema potrebbe essere fare affidamento su MutItems. Questo è già un iteratore mutabile fornito tramite libreria su un vettore. Quindi, potresti farla franca solo usando quella invece del tuo tipo personalizzato, oppure potresti avvolgerla all'interno del tuo tipo di iteratore personalizzato. Nel caso in cui non puoi farlo per qualche motivo, dovresti scrivere il tuo codice non sicuro. E se lo fai, assicurati che

• Non creare riferimenti mutabili multiplte che siano alias. Se lo facessi, ciò violerebbe le regole di Ruggine e invocherà un comportamento indefinito.
• Non dimenticare di utilizzare il tipo PhantomData per indicare al compilatore che il tuo iteratore è un tipo di riferimento in cui la sostituzione della durata con una più lunga non è consentita e potrebbe altrimenti creare un iteratore pendente.