Pass vector of borrowed variables to new Struct

Question

In an effort to learn about structs, borrowing, and lifetimes, I am putting together a toy library that would handle nodes and edges for a graph. It's been instructive, but I'm stuck when finally instantiating a Graph instance with Nodes that have already been borrowed by multiple Edges.

The error I'm receiving:

error[E0505]: cannot move out of `n0` because it is borrowed
  --> src/lib.rs:94:18
   |
90 |         let e0 = Edge::new(&n0, &n1);
   |                            --- borrow of `n0` occurs here
...
94 |             vec![n0, n1, n2],
   |                  ^^ move out of `n0` occurs here
95 |             vec![e0, e1, e2],
   |                  -- borrow later used here

Code being used:

use std::fmt;
use uuid::Uuid;

#[derive(PartialEq)]
struct Node {
    id: Uuid,
    label: Option<String>,
}

impl fmt::Display for Node {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "<Node {}>", self.id)
    }
}

impl Node {
    fn new() -> Node {
        Node {
            id: Uuid::new_v4(),
            label: None,
        }
    }

    fn new_with_id(id: Uuid) -> Node {
        Node {
            id,
            label: None,
        }
    }
}

struct Edge<'a> {
    nodes: (&'a Node, &'a Node),
}

impl fmt::Display for Edge<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "<Edge ({}, {})>", self.nodes.0, self.nodes.1)
    }
}

impl Edge<'_> {
    fn new<'a>(n0: &'a Node, n1: &'a Node) -> Edge<'a> {
        Edge {
            nodes: (n0, n1)
        }
    }
}

struct Graph<'a> {
    nodes: Vec<Node>,
    edges: Vec<Edge<'a>>,
}

impl Graph<'_> {
    fn new<'a>(nodes: Vec<Node>, edges: Vec<Edge>) -> Graph {
        Graph {
            nodes,
            edges,
        }
    }
}

///////////////////////////////////////////////////////////////////////
// Tests
///////////////////////////////////////////////////////////////////////
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn create_edge() {
        let n0 = Node::new();
        let n1 = Node::new();
        let e0 = Edge::new(&n0, &n1);
        println!("Created node: {}", n0);
        println!("Created node: {}", n1);
        println!("Created edge: {}", e0);
        assert!(e0.nodes.0 == &n0 && e0.nodes.1 == &n1);
    }

    #[test]
    fn create_undirected_graph() {
        let n0 = Node::new();
        let n1 = Node::new();
        let n2 = Node::new();
        let e0 = Edge::new(&n0, &n1);
        let e1 = Edge::new(&n1, &n2);
        let e2 = Edge::new(&n2, &n0);
        let g0 = Graph::new(
            vec![n0, n1, n2],
            vec![e0, e1, e2],
        );
    }
}

It feels like I would want to modify the struct Graph definition to expect borrowed instances in the vectors, but running into a bunch of compiler errors as I go in that direction.

Any help or guidance would be much appreciated!

Answer 1

As soon as you borrow any data structure, you may not change it except through that very borrow. Now, your edges immutably borrow your nodes. Since your nodes are in a Vec, your edges also implicitly borrow the whole vector. (If they didn't, you could, say, resize the vector, which would change the position of your nodes.) This means that you are not allowed to change anything about your vector of nodes.

However, you are trying to move your vector of nodes into a new memory location inside your struct. Since Vec is not Copy, this invalidates your previous vector, which is clearly "changing" it.

There are a number of ways you can go to avoid this issue.

Borrow the vector of nodes

Rather than moving the nodes into the Graph, you could borrow them.

struct Graph<'a> {
    nodes: &'a Vec<Node>,
    edges: Vec<Edge<'a>>,
}

While this should resolve your current compilation error, the resulting structure wouldn't be very pleasant to handle, because it cannot exist on its own. It can only exist as long as the vector of nodes exist elsewhere.

Use reference-counting

If you want to avoid the reliance on an "outside borrow", you can fall back to good old reference counting. If you know C++, this is a similar concept as a shared pointer. It's available in the standard library as std::rc::Rc. It puts an object on the heap along with a counter how often it is referenced and makes sure that the memory is not freed as long as one reference exists. If you put your nodes behind such an abstraction, you don't need lifetimes anymore (since the required properties are ensured at runtime).

In this case you would also change your Edges slightly.

struct Edge {
    nodes: (Rc<Node>, Rc<Node>),
}

struct Graph {
    nodes: Vec<Rc<Node>>,
    edges: Vec<Edge>,
}

Reference nodes by their ID or index

While the previous approach works just fine, you often want to avoid additional heap allocations. One of the standard ways to deal with issues such as this one is not to store references to the nodes in your edges, but rather to store either their index (or in your case potentially their UUID).

Self-referential structs

The structure you were trying to create is self-referential. That means that your field edges wanted to reference data from another field in the same struct, namely nodes. While it isn't impossible to create such structures in Rust, getting it right is often not easy and rather error-prone. There are some libraries performing black magic to make this easier, such as ouroboros. However, I would try to avoid such incantations if possible.