Con el cambio de paradigma que supone la gestión de memoria de Rust, una de las cosas que pueden resultar más difíciles al principio es la definición de estructuras de datos "complejas", con el concepto de propiedad de memoria y referencias, definir cosas como una lista enlazada no es tan "sencillo" como en C.

Por supuesto esto no es sencillo porque definir este tipo de estructuras de forma segura es muy complejo, en C es muy fácil definir lo básico, con punteros, pero también es muy fácil que una lista enlazada apunte a un nodo eliminado, etc.

Voy a explicar diferentes aproximaciones para implementar una estructura cíclica en Rust, en este caso, vamos a definir un grafo.

He creado un repositorio en github con el código para que se pueda estudiar. En este artículo pondré partes del código para mostrar lo básico de la implementación, pero sobretodo me centraré en explicar la teoría detrás de cada solución.

Problema

Queremos implementar una estructura de datos sencilla para manejar grafos dirigidos.

Un grafo no es más que una lista de vértices conectados entre sí. Cada nodo tiene un valor, y una lista de nodos a los que apunta.

Podemos pensar en una primera implementación donde definamos cada nodo, con su valor y que tenga una lista de nodos hijos.

struct GraphNode<T> {
    value: T,
    childs: Vec<GraphNode<T>>,
}

Pero dada la gestión de memoria que se hace en Rust, esta estructura no nos valdría de mucho, ya que tendríamos que tener una copia diferente de un nodo para cada referencia, añadimos un nodo a otro, y luego intentamos usarlo, no podremos, porque será el nodo padre el que tenga la propiedad de sus hijos.

Con esta solución en realidad cada nodo es independiente, no se reutilizan, por lo que deja de ser útil para nuestro caso.

Lo primero que se nos ocurre para solucionar este problema es usar referencias:

struct GraphNode<T> {
    value: T,
    childs: Vec<&GraphNode<T>>,
}

Pero esto no compila, al usar referencias el compilador nos pide que definamos el lifetime de estas referencias, y al ser una estructura recursiva, se complica mucho el tema, los nodos se deben almacenar en alguna parte y ser referenciados entre sí, además, dado que en rust no es compatible tener referencias no mutables a la vez que una referencia mutable, no podríamos modificar estos nodos hijos por la referencia.

Usando punteros, unsafe

Una primera solución que se nos puede ocurrir es tirar directamente de punteros tipo C. Rust nos da la posibilidad de acceder a la memoria como en C, con punteros, de esta forma nos podemos saltar las limitaciones del compilador de Rust, pero esto implica que también perdemos la gestión de memoria, por lo que tendremos que controlar nosotros la memoria y perdemos la seguridad que nos proporciona el compilador.

El uso de punteros en Rust nos obliga a usar el calificador unsafe, para poder diferenciar de forma rápida el código seguro, donde la gestión de memoria se comprueba en tiempo de compilación, del código inseguro, que es código donde la memoria se gestiona de manera manual.

pub struct GraphNode<T> {
    pub value: T,
    pub childs: Vec<*mut GraphNode<T>>,
}

El tipo de dato Box nos permite convertir a puntero o desde puntero de forma sencilla con los métodos into_raw y from_raw.

pub fn add_child(&mut self, node: &mut GraphNode<T>, value: T) -> *mut GraphNode<T> {
    let n = Box::new(GraphNode::new(value));
    let pointer = Box::into_raw(n);
    node.childs.push(pointer);
    pointer
}

Y podemos acceder al valor de un puntero utilizando el operador * para deferenciar el puntero.

unsafe {
    (*node).value
}

Con into_raw Rust deja la gestión de la memoria en nuestras manos, por lo que para evitar memory leaks tenemos que destruir esa memoria en algún momento, y para ello podemos usar el from_raw que hace la operación inversa y devuelve a Rust la gestión de esa memoria.

Usando referencias, Rc<RefCell<Node>>, Arc<Mutex<Node>>

El uso de punteros es algo de lo que queremos huir cuando usamos Rust, ya que es código menos seguro. Por eso debemos dejar el uso de punteros sólo para momentos en los que necesitemos eficiencia a nivel de memoria o velocidad y sepamos exactamente lo que estamos haciendo.

En Rust hay una estructura que nos ofrece la posibilidad de implementar algo similar a los punteros, el contador de referencias. El patrón básico para permitir modificaciones de elementos interiores, es la composición Rc<RefCell<T>>.

use std::cell::RefCell;
use std::rc::Rc;

type GraphNodeRef<T> = Rc<RefCell<GraphNode<T>>>;

pub struct GraphNode<T> {
    pub value: T,
    pub childs: Vec<GraphNodeRef<T>>,
}

De esta forma podemos hacer un uso exactamente igual al de los punteros, pero con la seguridad de que no tendremos problemas de seguridad de memoria.

pub fn add_child(&mut self, node: GraphNodeRef<T>, value: T) -> GraphNodeRef<T> {
    let n = GraphNode::new(value);
    let rnode = Rc::new(RefCell::new(n));
    node.borrow_mut().childs.push(rnode.clone());
    rnode
}

En lugar de usar * para deferenciar los punteros, en este caso usamos borrow y borrow_mut para obetener una referencia. Con el método clone, el tipo Rc crea una referencia nueva, no duplica la información en sí, y cuando se queda sin referencias es cuando se elimina el contenido.

Esta solución nos permite hacer algo muy parecido a lo que hacemos con punteros, pero sin preocuparnos de tener que eliminar la memoria o de que hay overflow o lo que sea.

Sin embargo, esto no es la panacea, hay un problema si se generan ciclos, ya que las referencias cíclicas no se eliminarán nunca, no es algo muy grave, pero hay que tenerlo en cuenta, aunque ya hay alguien que ha implementado un recolector de basura para estos casos.

De forma similar, en caso de querer que sea thread safe, se puede usar Arc<Mutex<T>>.

Usando una estructura básica e identificadores de nodos, Vec, HashMap

Otra posible aproximación puede ser usar una estructura básica de Rust, como un Vec o un HashMap, para almacenar todos los elementos, y luego definir las referencias de los nodos usando índices a esta estructura.

Por ejemplo podríamos definir un vector con todos los nodos de nuestro grafo, y cada nodo define sus hijos como índices en ese vector, números enteros.

pub struct Graph<T> {
    pub nodes: Vec<GraphNode<T>>,
    pub idx: u32,
}

pub struct GraphNode<T> {
    pub value: T,
    pub childs: Vec<u32>,
}

En el código de ejemplo he usado HashMap en lugar de Vec, porque si por ejemplo queremos poder eliminar un nodo de forma fácil, en un Vec tendríamos que recorrer todo el vector y cambiar los indices de todos los nodos con cada cambio.

use std::collections::HashMap;

pub struct Graph<T> {
    pub nodes: HashMap<u32, GraphNode<T>>,
    pub idx: u32, // índice del siguiente nodo que se añada
}

pub struct GraphNode<T> {
    pub value: T,
    pub childs: Vec<u32>,
}

Con esta implementación, para nosotros los nodos serán enteros, y nos podemos definir los métodos que hagan uso de estos índices.

pub fn add_child(&mut self, node: u32, value: T) -> u32 {
    let n = GraphNode::new(value);
    let idx = self.idx;

    self.nodes.insert(idx, n);
    self.idx += 1;

    self.nodes.get_mut(&node).unwrap().childs.push(idx);
    idx
}

De esta forma, todo el código será seguro y además no utilizamos referencias, simplemente nos estamos implementando nuestros propios punteros. Aquí tenemos el compilador que comprueba la seguridad de la memoria, pero si no manejamos correctamente los índices enteros, podemos tener algún que otro panic, aunque siempre es mejor un panic que un segmentation fault, un painc es algo controlable y no da los mismos problemas que podría dar un overflow.

Conclusiones

Este ejemplo nos sirve para conocer diferentes formas de resolver un problema, con las herramientas que nos da Rust, pero también nos muestra que no sólo hay una solución correcta a un problema, se puede pensar de manera diferente e implementar.

Para mi, en principio la manera más natural es la de Rc<RefCell>>, viniendo de usar C y C++ y pensando en no usar punteros, pero después de investigar, veo que la opción de usar el HashMap no me parece ninguna locura, y se me ocurren otras formas de almacenar un grafo en memoria.

Por supuesto no soy un experto en este tipo de implementaciones y quizás esté haciendo alguna locura, si ese es el caso, no dudes en comentar y corregir cualquier gazapo.