8 ms·

Rust data structures with circular references

138 points by picture 5y ago

implfuture 5y ago
Nice post! Might be worth mentioning that some data structure implementations already exist in std or as a crate, i.e. std::collections::BTreeSet and petgraph. While it’s good to understand how Rc/Weak/raw pointers work, I always check if there is a battle-tested version of what I need before reaching for them.
conradludgate 5y ago
As a slight nit-pick. For the third option, instead of having raw pointers in the struct, I'd instead have `Option<NonNull<Node>>`. It compiles to the same thing thanks to niche optimisations but it has much better safety and semantics
phendrenad2 5y ago
Very interesting. Rust is certainly an interesting language and this angle made me understand more of it.
aldanor 5y ago
By the title of the post, I was expecting to see an example of where to use Pin<> and was surprised to not even see it mentioned...
pca006132 5y ago
What about using ghost cell? https://github.com/matthieu-m/ghost-cell https://github.com/matthieu-m/ghost-cell
- thurn 5y ago
  Has any ghost cell stuff gotten closer to production-ready in the last couple months? It seems like it's still pretty early on in its development lifecycle.
  - pca006132 5y ago
    I haven't heard of it getting closer to production-ready, but I hope articles can cover this so more people can look into it.
  - PoignardAzur 5y ago
    I remember seeing a mature-ish project that was architectured around them. I think it was JS-related.
- ModernMech 5y ago
  I hadn’t heard of this before. Is this a drop in replacement for RefCell that is compile time checked?
beltsazar 5y ago
Similar to the second approach, you can have better ergonomics and performance by using a memory arena library like slotmap. A doubly linked list implemented using slotmap: https://github.com/orlp/slotmap/blob/ce6e1e02bb2c2074d8d581e87ad9c2f72ce495c3/examples/doubly_linked_list.rs https://github.com/orlp/slotmap/blob/ce6e1e02bb2c2074d8d581e...
- orlp 5y ago
  Hi, author of slotmap here if anyone has any questions. Slotmap is essentially the Vec + indices solution, while allowing memory to be reused. It is still completely safe, as it automatically versions each slot, and checks the version contained in the key when indexing.
  - mattgreenrocks 5y ago
    If there’s a lot of churn on the tree, does fragmentation rear its head? Or does the version in the key come into play here?
    - nightcracker 5y ago
      There is no fragmentation whatsoever in the traditional sense (unusable gaps left due to size mismatches), because a slotmap only stores a single type of value. Thus every slot is interchangeable and memory can always be reused. For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.
      - mattgreenrocks 5y ago
        Yes, holes is a better term. Was wondering if double pointers (as they were) were used, looks like it was right. Thank you for the reply!
drran 5y ago
Tree and Node must own subnodes, but node need just to point to parent, it cannot own parent. #[derive(Debug)] struct Node { data: i32, left: Option<Box<Node>>, right: Option<Box<Node>>, parent: Option<*mut Node>, } impl Node { pub fn new_root(data: i32) -> Self { Node { data, left: None, right: None, parent: None, } } pub fn new_leaf(data: i32, parent: *mut Node) -> Self { Node { data, left: None, right: None, parent: Some(parent), } } } #[derive(Debug)] struct Tree { root: Option<Node>, } impl Tree { pub fn new() -> Self { Tree { root: None } } pub fn insert(&mut self, data: i32) -> bool { match self.root { Some(ref mut node) => Tree::insert_at(node, data), None => { self.root = Some(Node::new_root(data)); true } } } fn insert_at(current_node: &mut Node, data: i32) -> bool { match ( current_node.left.as_deref_mut(), current_node.right.as_deref_mut(), ) { _ if data == current_node.data => false, (Some(left_node), _) if data < current_node.data => Tree::insert_at(left_node, data), (None, _) if data < current_node.data => { let new_node = Node::new_leaf(data, current_node); current_node.left = Some(Box::new(new_node)); true } (_, Some(right_node)) => Tree::insert_at(right_node, data), (_, None) => { let new_node = Node::new_leaf(data, current_node); current_node.right = Some(Box::new(new_node)); true } } } } pub fn main() { let mut tree = Tree::new(); let data = [5, 3, 65, 123, 6, 11, 3, 1, 5, 42]; for i in data { tree.insert(i); } println!("{:?}", tree); }
- scotty79 5y ago
  Could you keep parent reference in Option<Rc<Node>> ?
  - eliben 5y ago
    `Rc` implies ownership, albeit shared one. So if a heap location is held by `Rc`, all reference to it should be either `Rc` or `Weak`. You can't have an `Rc` and a `Box` for the same data, IIUC. A `Box` is unaware of `Rc` and will drop its data when dropped itself.
Syzygies 5y ago
In Haskell and other purely functional programming languages, one encounters exactly the same challenge. These communities have worked out sophisticated, well-documented solutions. Facing any problem, one should always ask "Who else has already encountered this problem?" To ignore their work is to reinvent the wheel. As a Haskell programmer exploring Rust, I was thrilled to recognize this parallel. One gains persistent data structures. In many problems, "reuse" is far more efficient than carving out each new instance from scratch. I've never understood the evangelists that claim one can't learn functional programming after any exposure to conventional programming, but perhaps the prejudices run deeper than I've recognized. How does one characterize a rejection out-of-hand of persistent data structures? "One-use plastic bag syndrome"
- throwvirtever 5y ago
  Looking for precedents is always good advice, but the essential issue is that even if you don't re-invent the wheel, the "wheel" that works in functional programming territory, for certain tasks (e.g. the binary tree with parent pointers), is more complicated, more verbose, and comes with downsides. People ignore existing work (at least at first), and assume they can make it simpler themselves, because they're surprised it _needs_ to be sophisticated. EDIT: That said, the article does a great job of explaining the problems and the potential solutions.
- helen___keller 5y ago
  I come from a functional background (significant work in SML and Ocaml) and went into learning Rust excited to implement all my favorite persistent data structures, only to find myself foiled by borrow and lifetime madness similar to what’s described in the naive implementation in the OP. Where I could define a simple tree in one line of SML, I struggled to define one at all in Rust! (I think my problem actually just came down to the lifetime on the object holding the tree itself and the way I was instantiating nodes; but when those lifetime compiler warnings popped up my eyes would glaze over and I knew it was time to put rust down for the day) I imagine Haskell programmers have a step up because the Monad system is significantly less forgiving than SML’s look-the-other-way approach to side effects, and in this sense Haskell and Rust are more similar than many other functional languages.
Rusky 5y ago
Another interesting variant is a cross between 1 and 2- centralize ownership of the nodes, but continue to use references rather than handles. You can't do this with a Vec<Node> (unless you can create all the nodes up front before initializing them) because resizing the Vec would invalidate references into it. But if you use a different "allocator" that leaves its contents in-place, you can make all the links into references with a single lifetime. The remaining tricky part is, still, deallocation- you can't fully free a node in a structure like this because they all share a lifetime. But you can put it on a free list for future node allocations, with similar risks to the handle approach.
- loeg 5y ago
  > But if you use a different "allocator" that leaves its contents in-place, you can make all the links into references with a single lifetime. E.g., something like Bumpalo?
  - shepmaster 5y ago
    I lean towards an arena.
bilkow 5y ago
I think there is a slight mistake in the article: > So how can a reference in a child assume the same lifetime? It can't. Well actually, it can, because the owned Struct itself (Node) can outlive any borrow. You won't be able to mutate the parent though, as you can't mutate any value that has an active immutable borrow. That's the problem: you can't add the child node as adding it would mutate the parent and the there's an active immutable borrow (in the child node). This reddit comment[0] has one possible solution[1] to this problem: not saving all of those parent references in the node itself, only adding when you're retrieving it. It also seems a lot better since there's less data in-tree to change if the structure itself changes. [0] https://old.reddit.com/r/rust/comments/qstlto/rust_data_structures_with_circular_references/hkg1omp/ https://old.reddit.com/r/rust/comments/qstlto/rust_data_stru... [1] https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=731ab0fcad708964792f4b30e3aef2da https://play.rust-lang.org/?version=stable&mode=debug&editio...
- eliben 5y ago
  Thanks, you're making a good point. I like how you phrased the problem here, will ponder about updating the wording of the post slightly to reflect that.
natded 5y ago
Rust really doesn't like pointers; and as such modeling graph data structures besides something like a DAG is a huge pain in the ass: there barely is any idiomatic way to make a mutable self-referential, undirected graph in std-only.
- baq 5y ago
  yeah, that's by design. how do you check borrows in a mutable self-referential data structure? you don't by definition.
  - natded 5y ago
    I know. I've just been going through an algorithm book and trying to implement them and the graphs were easily hardest to implement in Rust despite the pseudocode being simple as peanuts (and trivial in a GC language).

138 points by picture 5y ago

Nice post! Might be worth mentioning that some data structure implementations already exist in std or as a crate, i.e. std::collections::BTreeSet and petgraph. While it’s good to understand how Rc/Weak/raw pointers work, I always check if there is a battle-tested version of what I need before reaching for them.

conradludgate 5y ago

As a slight nit-pick. For the third option, instead of having raw pointers in the struct, I'd instead have `Option<NonNull<Node>>`. It compiles to the same thing thanks to niche optimisations but it has much better safety and semantics

phendrenad2 5y ago

Very interesting. Rust is certainly an interesting language and this angle made me understand more of it.

aldanor 5y ago

By the title of the post, I was expecting to see an example of where to use Pin<> and was surprised to not even see it mentioned...

pca006132 5y ago

What about using ghost cell? https://github.com/matthieu-m/ghost-cell https://github.com/matthieu-m/ghost-cell

thurn 5y ago
Has any ghost cell stuff gotten closer to production-ready in the last couple months? It seems like it's still pretty early on in its development lifecycle.
- pca006132 5y ago
  I haven't heard of it getting closer to production-ready, but I hope articles can cover this so more people can look into it.
- PoignardAzur 5y ago
  I remember seeing a mature-ish project that was architectured around them. I think it was JS-related.
ModernMech 5y ago
I hadn’t heard of this before. Is this a drop in replacement for RefCell that is compile time checked?

beltsazar 5y ago

Similar to the second approach, you can have better ergonomics and performance by using a memory arena library like slotmap. A doubly linked list implemented using slotmap: https://github.com/orlp/slotmap/blob/ce6e1e02bb2c2074d8d581e87ad9c2f72ce495c3/examples/doubly_linked_list.rs https://github.com/orlp/slotmap/blob/ce6e1e02bb2c2074d8d581e...

orlp 5y ago
Hi, author of slotmap here if anyone has any questions. Slotmap is essentially the Vec + indices solution, while allowing memory to be reused. It is still completely safe, as it automatically versions each slot, and checks the version contained in the key when indexing.
- mattgreenrocks 5y ago
  If there’s a lot of churn on the tree, does fragmentation rear its head? Or does the version in the key come into play here?
  - nightcracker 5y ago
    There is no fragmentation whatsoever in the traditional sense (unusable gaps left due to size mismatches), because a slotmap only stores a single type of value. Thus every slot is interchangeable and memory can always be reused. For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.
    - mattgreenrocks 5y ago
      Yes, holes is a better term. Was wondering if double pointers (as they were) were used, looks like it was right. Thank you for the reply!

drran 5y ago

Tree and Node must own subnodes, but node need just to point to parent, it cannot own parent. #[derive(Debug)] struct Node { data: i32, left: Option<Box<Node>>, right: Option<Box<Node>>, parent: Option<*mut Node>, } impl Node { pub fn new_root(data: i32) -> Self { Node { data, left: None, right: None, parent: None, } } pub fn new_leaf(data: i32, parent: *mut Node) -> Self { Node { data, left: None, right: None, parent: Some(parent), } } } #[derive(Debug)] struct Tree { root: Option<Node>, } impl Tree { pub fn new() -> Self { Tree { root: None } } pub fn insert(&mut self, data: i32) -> bool { match self.root { Some(ref mut node) => Tree::insert_at(node, data), None => { self.root = Some(Node::new_root(data)); true } } } fn insert_at(current_node: &mut Node, data: i32) -> bool { match ( current_node.left.as_deref_mut(), current_node.right.as_deref_mut(), ) { _ if data == current_node.data => false, (Some(left_node), _) if data < current_node.data => Tree::insert_at(left_node, data), (None, _) if data < current_node.data => { let new_node = Node::new_leaf(data, current_node); current_node.left = Some(Box::new(new_node)); true } (_, Some(right_node)) => Tree::insert_at(right_node, data), (_, None) => { let new_node = Node::new_leaf(data, current_node); current_node.right = Some(Box::new(new_node)); true } } } } pub fn main() { let mut tree = Tree::new(); let data = [5, 3, 65, 123, 6, 11, 3, 1, 5, 42]; for i in data { tree.insert(i); } println!("{:?}", tree); }

scotty79 5y ago
Could you keep parent reference in Option<Rc<Node>> ?
- eliben 5y ago
  `Rc` implies ownership, albeit shared one. So if a heap location is held by `Rc`, all reference to it should be either `Rc` or `Weak`. You can't have an `Rc` and a `Box` for the same data, IIUC. A `Box` is unaware of `Rc` and will drop its data when dropped itself.

Syzygies 5y ago

In Haskell and other purely functional programming languages, one encounters exactly the same challenge. These communities have worked out sophisticated, well-documented solutions. Facing any problem, one should always ask "Who else has already encountered this problem?" To ignore their work is to reinvent the wheel. As a Haskell programmer exploring Rust, I was thrilled to recognize this parallel. One gains persistent data structures. In many problems, "reuse" is far more efficient than carving out each new instance from scratch. I've never understood the evangelists that claim one can't learn functional programming after any exposure to conventional programming, but perhaps the prejudices run deeper than I've recognized. How does one characterize a rejection out-of-hand of persistent data structures? "One-use plastic bag syndrome"

throwvirtever 5y ago
Looking for precedents is always good advice, but the essential issue is that even if you don't re-invent the wheel, the "wheel" that works in functional programming territory, for certain tasks (e.g. the binary tree with parent pointers), is more complicated, more verbose, and comes with downsides. People ignore existing work (at least at first), and assume they can make it simpler themselves, because they're surprised it _needs_ to be sophisticated. EDIT: That said, the article does a great job of explaining the problems and the potential solutions.
helen___keller 5y ago
I come from a functional background (significant work in SML and Ocaml) and went into learning Rust excited to implement all my favorite persistent data structures, only to find myself foiled by borrow and lifetime madness similar to what’s described in the naive implementation in the OP. Where I could define a simple tree in one line of SML, I struggled to define one at all in Rust! (I think my problem actually just came down to the lifetime on the object holding the tree itself and the way I was instantiating nodes; but when those lifetime compiler warnings popped up my eyes would glaze over and I knew it was time to put rust down for the day) I imagine Haskell programmers have a step up because the Monad system is significantly less forgiving than SML’s look-the-other-way approach to side effects, and in this sense Haskell and Rust are more similar than many other functional languages.

Rusky 5y ago

Another interesting variant is a cross between 1 and 2- centralize ownership of the nodes, but continue to use references rather than handles. You can't do this with a Vec<Node> (unless you can create all the nodes up front before initializing them) because resizing the Vec would invalidate references into it. But if you use a different "allocator" that leaves its contents in-place, you can make all the links into references with a single lifetime. The remaining tricky part is, still, deallocation- you can't fully free a node in a structure like this because they all share a lifetime. But you can put it on a free list for future node allocations, with similar risks to the handle approach.

loeg 5y ago
> But if you use a different "allocator" that leaves its contents in-place, you can make all the links into references with a single lifetime. E.g., something like Bumpalo?
- shepmaster 5y ago
  I lean towards an arena.

bilkow 5y ago

I think there is a slight mistake in the article: > So how can a reference in a child assume the same lifetime? It can't. Well actually, it can, because the owned Struct itself (Node) can outlive any borrow. You won't be able to mutate the parent though, as you can't mutate any value that has an active immutable borrow. That's the problem: you can't add the child node as adding it would mutate the parent and the there's an active immutable borrow (in the child node). This reddit comment[0] has one possible solution[1] to this problem: not saving all of those parent references in the node itself, only adding when you're retrieving it. It also seems a lot better since there's less data in-tree to change if the structure itself changes. [0] https://old.reddit.com/r/rust/comments/qstlto/rust_data_structures_with_circular_references/hkg1omp/ https://old.reddit.com/r/rust/comments/qstlto/rust_data_stru... [1] https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=731ab0fcad708964792f4b30e3aef2da https://play.rust-lang.org/?version=stable&mode=debug&editio...

eliben 5y ago
Thanks, you're making a good point. I like how you phrased the problem here, will ponder about updating the wording of the post slightly to reflect that.

natded 5y ago

Rust really doesn't like pointers; and as such modeling graph data structures besides something like a DAG is a huge pain in the ass: there barely is any idiomatic way to make a mutable self-referential, undirected graph in std-only.

baq 5y ago
yeah, that's by design. how do you check borrows in a mutable self-referential data structure? you don't by definition.
- natded 5y ago
  I know. I've just been going through an algorithm book and trying to implement them and the graphs were easily hardest to implement in Rust despite the pseudocode being simple as peanuts (and trivial in a GC language).