Circular data structures in rust

help
1

I'm trying to create a lexical analyzer in rust, and I'm having trouble figuring out how to create the data structure I need in a way that passes the borrow checker. In short, I need a data structure that has similar functionality to this struct:

struct Node {
    transitions: Vec<Node>
}

These transitions are used to form a directed graph, so the same node could be referenced by several other nodes, which means my snippet above won't work because each node can only be owned in one place. It's also possible that a node might be in its own list, which I'm pretty sure rules out the possibility of making it a vector of immutable borrows. I've just started working with rust, so that's all I've really been able to come up with. Any ideas for what I could try?

2

I think you should use Rc and its downgrade function (aka Weak type) for this.

Somebody owns the node (they have the Rc), and everybody else gets a weak reference.

1 Like
3

Reference counting can be thought of as a very simple GC. For many workloads, it has significantly less throughput than a tracing collector, and it completely falls over if you manage to build cycles.

It looks like this guy is saying that reference counting will only work if there are no cycles, which means it won't work in my case. I tried it anyways, but I couldn't get it to work. Maybe unsafe pointers are the way to go?

4

The Weak type doesn't count wrt. cycles, so if you follow the advice above of only having an Rc once and using Weak everywhere else, it should work correctly. What was your issue when using rcs? I would definitely not recommend raw pointers, because that would mean you have to worry about all sorts of madness including reallocations of the vector when pushing more nodes to it.

1 Like
5 
use std::rc::{Rc, Weak};

struct Node {
    edges: Vec<Weak<Node>>
}

fn main() {
    let node = Rc::new(Node {edges: vec![]});
    node.edges.push(Rc::downgrade(&node));
}

@alice I was trying things in the rust playground for quite a while, and I'm pretty sure this is the closest I got to making something work. I was trying to create a cycle where a node has a reference to itself, but it doesn't compile because the contents of an Rc can't be borrowed as mutable. (node.edges is where the mutable borrow is needed)

6

You can add a RefCell inside the Rc to mutate the contents.

2 Likes
7

Or, as the usual advice goes, you can just use one single Vec<Node> and refer to nodes by their indices. Perhaps wrap the index as a newtype, something like NodeRef(usize), for more semantics.

2 Likes
8

I've heard this be referred to as an arena. For example here: Idiomatic tree and graph like structures in Rust – Rust Leipzig

2 Likes
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.