rust - No se puede obtener una referencia mutable al iterar una estructura recursiva: no se puede tomar prestada como mutable más de una vez a la vez

borrowing

Question

Estoy tratando de navegar una estructura de datos recursiva iterativamente para insertar elementos en una determinada posición. A mi entender limitado, esto significa tomar una referencia mutable a la raíz de la estructura y reemplazarla sucesivamente por una referencia a su seguidor:

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

(Enlace de patio de óxido)

Sin embargo, esto falla:

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

Esto tiene sentido ya que tanto el anchor como el node refieren a la misma estructura, pero en realidad ya no me importa el anchor después de desestructurarla.

¿Cómo se podría implementar correctamente back() usando Safe Rust?

Answer 1

El código original funciona como está una vez que se habilitan las vidas no léxicas :

#![feature(nll)]

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(node) = anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

fn main() {}

Los tiempos de vida no léxicos aumentan la precisión del verificador de préstamos del compilador, lo que le permite ver que el préstamo mutable del anchor ya no se usa. También podemos simplificar las palabras clave en if let debe a cambios recientes en el idioma.

Answer 2

Es posible ... pero desearía tener una solución más elegante.

El truco NO es tomar prestado del anchor y, por lo tanto, hacer malabarismos entre dos acumuladores:

• uno con la referencia al nodo actual
• al otro se le asigna la referencia al siguiente nodo

Esto me lleva 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
    }
}

No es exactamente bonito, pero esto es algo que el corrector de préstamos puede retrasar, así que ¯ / _ (ツ) _ / ¯.

@ker ha mejorado esto creando un temporal sin nombre:

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

El truco aquí es que el uso de {anchor} mueve el contenido del anchor a un temporal sin nombre en el que se ejecuta la coincidencia. Por lo tanto, en el bloque de match no tomamos prestado del anchor sino del temporal, dejándonos libres para modificar el anchor . Vea la publicación de blog relacionada Cosas que hace la función de identidad (en Rust) .

Answer 3

Funciona:

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

Answer 4

Puede usar la recursividad para satisfacer al verificador de préstamos. Esto tiene la desventaja de crear un marco de pila para cada elemento de su lista. Si su lista es larga, esto definitivamente se encontrará con un desbordamiento de pila. LLVM optimizará el método Node::back en un bucle (vea el IR LLVM generado en el 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())
    }
}