How to model complex recursive data structures (graphs)?

Question

I am very interested in Rust and am now starting my first non-trivial project in the language. I am still having a bit of trouble fully understanding the concepts of borrowing and lifetime.

The application is a logic gate simulator in which components are defined recursively (in terms of other components and their interconnections).

My current plan is to implement this similarly as I would in C++ by having a Component structure owning a vector of Components (its sub-components) and a vector of Nets describing the inter-connections between those components:

pub struct Pin {
    name: String
}

pub struct Net<'a> {
    nodes: Vec<(&'a Component<'a>,&'a Pin)>
}

pub struct Component<'a> {
    sub_components: Vec<Box<Component<'a>>>,
    in_pins: Vec<Pin>,
    out_pins: Vec<Pin>,
    netlist: Vec<Net<'a>>
}

impl<'a> Component<'a> {
    pub fn new() -> Component<'a> {
        ...
    }

    pub fn add_subcomponent( & mut self, comp: Component<'a> ) {
        // -> &Box<Component<'a>> ??
        ....
    }
}

In C++, Net would be easy to implement as an array of pointers to Components but I am not sure of the best way to do this in Rust, I suppose I should use borrowed pointers? Or is there a better way?

Consider the following main:

fn main() {
    let sub1 = Component::new();
    let sub2 = Component::new();
    let circuit = Component::new();

    circuit.add_subcomponent( sub1 );
    circuit.add_subcomponent( sub2 );
    // sub1 and sub2 are now empty...
}

How can I configure circuit to create a net between sub1 and sub2? Shall I have add_subcomponent returns a borrowed pointer to the added Component? or the Box?

It would be great if someone could point me in the right direction.

Thanks a lot.

Answer 1

You can't represent an arbitrary graph structure in safe rust.

The best way to implement this pattern is to use unsafe code and raw pointers, or an existing abstraction that wraps this functionality in a safe api, for example http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

For example, the typical bi directional linked list would be:

struct Node {
  next: Option<Node>, // Each node 'owns' the next one
  prev: *mut Node     // Backrefs are unsafe
}

There have been a number of 'safe' implementations floating around, where you have something like:

struct Node {
    id: u32,
    next: u32,
    prev: u32
}
struct Nodes {
  all:Vec<Node>,
  root:Option<Node>
}

This is 'technically' safe, but it's a terrible pattern; it breaks all the safety rules by just manually implementing raw pointers. I strongly advise against it.

You could try using references, eg:

struct Container<'a> {
  edges:Vec<Edge<'a>>,
  pub root: Node
}

struct Node {
  children:Vec<Node>  
}

struct Edge<'a> {
  n1: &'a Node,
  n2: &'a Node
}

...but you'll stumble almost immediately into borrow checker hell. For example, when you remove a node, how does the borrow checker know that the associated links in 'edges' are no longer valid?

Although you might be able to define the structures, populating them will be extremely troublesome.

I know that's probably a quite unsatisfying answer; you may find it useful to search github for 'rust graph' and 'rust tree' and look at the implementations other people have done.

Typically they enforce single-ownership of a sub-tree to a parent object.