How can I make a structure with internal reference

Question

I'm trying to make a graph with adjacency lists, but I can't figure out how to specify an appropriate lifetime for the references in the adjacency list.

What I'm trying to get at is the following:

struct Graph<T> {
    nodes : Vec<T>,
    adjacencies : Vec<Vec<&T>>
}

This won't work because there is a lifetime specifier missing for the reference type. I suppose I could use indices for the adjacencies, but I'm actually interested in the internal reference problem, and this is just a vehicle to express that problem.

The way I see it, this should be possible to do safely, since the nodes are owned by the object. It should be allowed to keep references to those nodes around.

Am I right? How can this be done in Rust? Or, if I'm wrong, what did I miss?

Answer 1

It is not possible to represent this concept in Rust with just references due to Rust’s memory safety—such an object could not be constructed without already existing. As long as nodes and adjacencies are stored separately, it’s OK, but as soon as you try to join them inside the same structure, it can’t be made to work thus.

The alternatives are using reference counting (Rc<T> if immutable is OK or Rc<RefCell<T>> with inner mutability) or using unsafe pointers (*const T or *mut T).

Answer 2

I think there is an issue here. If we transpose this to C++:

template <typename T>
struct Graph {
    std::vector<T> nodes;
    std::vector<std::vector<T*>> adjacencies;
};

where adjacencies points into nodes, then one realizes that there is an issue: an operation on nodes that invalidates references (such as reallocation) will leave dangling pointers into adjacencies.

I see at least two ways to fix this:

• Use indexes in adjacencies, as those are stable
• Use a level of indirection in nodes, so that the memory is pinned

In Rust, this gives:

struct Graph<T> {
    nodes: Vec<T>,
    adjacencies: Vec<Vec<uint>>,
};

struct Graph<T> {
    nodes: Vec<Rc<RefCell<T>>>,
    adjacencies: Vec<Vec<Rc<RefCell<T>>>>,
};

Note: the RefCell is to allow mutating T despite it being aliased, by introducing a runtime check.