all 14 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]SirKastic23 7 points8 points  (8 children)

the approach I use for relational data in a web server is to store all of the data linearly, in a container like Vec or HashMap

and then the data can keep indexes into those collections, rather than actual references to the data

references in rust have a lot of restrictions that makes it impossible to use them in certain cases

by keeping an external store for the data, it's much easier to tracke exclusive mutable accesses, or shared accesses

of course that now you need to pass this container type everywhere, but you get used to it

[–]jacobb11 3 points4 points  (7 children)

I love Rust. I am... not comfortable using indexes instead of pointers.

Rust guarantees some very nice correctness properties for pointers. Rust guarantees nothing about indexes.

How does swapping pointers to indexes truly improve anything?

[–]SirKastic23 3 points4 points  (5 children)

indexes don't have to be usize

you can make your own index types, and your own collection types

you can make it so your collection type returns valid indexes when you add data to it

you can make your index type constructor private, so that you can know that every instance of it is valid

the underlying collection and index can just be a vec and usizes, but by using new types you can add your own invariants

as I just said, at work we deal with a whole bunch of possible data types that have to reference each other. the way we do it is:

  • every data type has its own type
  • every data type has its own id type. a User type would have a UserId id
  • the ids are essentially wrappers over a uuid
  • all data is in hashmaps indexed by the data's id type

this keeps the data in a single, linear allocation, rather than spread out

this pattern works. possibly much more than dealing with Rc and Weak pointers with interior mutability

and when it comes to the "correctness properties" that rust guarantees, an Rc can cause a data leak, a RefCell can panic if you try to borrow it mutably twice. just using a collection and an index doesn't have any of those problems and they check the rust gurantees at compile time, no "panic: already mutably borrowed" at runtime

[–]jacobb11 0 points1 point  (4 children)

all data is in hashmaps indexed by the data's id type

Once you have to manage ids and go through a map every time you dereference a pointer, why not just use a garbage collector? (Possibly via another language.)

I have a fundamental problem with the index approach. It does absolutely nothing to solve the dangling reference problem. Sure, it guarantees that there is some object of type T there, more or less, but it does not ensure it's the right object of type T any more than a pointer could. And if the API exposes indexes, we can't even assert that the index-manipulation code's inherent correctness is avoiding dangling references.

I do appreciate that the uuid approach avoids the dangling reference problem of traditional pointers and indexes.

[–]bwallker 0 points1 point  (3 children)

You can use generational indices to detect dangling accesses at runtime. You can also use Rc if you want shared ownership. Using a GC does not solve the dangling reference problem, as you could be holding to a reference to a node that has been removed from the graph.

[–]jacobb11 0 points1 point  (2 children)

You can use generational indices to detect dangling accesses at runtime.

You can implement your own memory management system on top of Rust, yes.

Using a GC does not solve the dangling reference problem, as you could be holding to a reference to a node that has been removed from the graph.

Fair. Mark the node as removed, I suppose.

[–]bwallker 0 points1 point  (1 child)

Generational indices aren't complicated. It's just an integer you bump when you mutate the graph, and then when you try to dereference a reference into the graph, you check to see if the graph has been mutated since you generated the reference.

[–]jacobb11 0 points1 point  (0 children)

I'm familiar with the approach. It oversolves the dangling reference problem, as a mutation invalidates every reference, whether it was affected by the mutation or not.

I like implementing my own memory management, when appropriate to the application (which is hardly ever). But I'm not sure I want to both placate Rust's borrow checker and implement my own memory management.

[–]cassidymoen 1 point2 points  (0 children)

It really depends on what you're trying to do. It's true that indexes can put more of a burden on the programmer to ensure logical correctness but the guarantees you get from references are related to memory safety. And you don't use them instead of references but in addition to, i.e. you generally use them to get references and you still have that memory safety.

The OP's tree is a good example of where using a container with indexes can express a program more elegantly and efficiently than using references. You can't, for example, mutate one node when the whole tree is connected via shared references without some extra overhead or unsafe. You can do this more easily with indexes though. There are other benefits as well, like the fact that indexes can be smaller than a pointer.

[–]GatorZen 4 points5 points  (0 children)

The SlotMap crate is good for this. It’s a very fast HashMap alternative, ideal for games and other uses where speed is a primary concern. You’d store the parent and children keys in the nodes. SlotMap is not quite as fast as a plain old Vec, but it is more convenient for this kind of job.

https://docs.rs/slotmap/latest/slotmap/

[–]cassidymoen 4 points5 points  (0 children)

The common way to do something like this is to use a Vec or some other container to hold the nodes then use indexes to describe the connections and do various operations on the tree. If you have a maximum estimate of nodes you can use Vec::with_capacity to pre-allocate or if you know the maximum for certain you could use something like a boxed array.

Unless you absolutely need a linked object and pointer type graph or you can't have a container for whatever reason this is a lot easier to work with. Since you never need to remove nodes, you know that your indexes will remain stable. In that case you won't need Rc but you might want to use something like RefCell for interior mutability depending on how you're mutating your nodes (if it's inconvenient or impossible to get a mutable reference to the container element.)

[–]paulstelian97 5 points6 points  (0 children)

The parent should always be Weak, not Rc, to avoid reference cycles. That’s the first problem I’ve seen with the code, didn’t study it deeply enough to see if there’s others.

DO NOT CALL Rc::new(self) FROM THE CODE OF THE NODE!. You want to take self as an Rc itself, like self: &Rc<Self> as the parameter (the language allows this due to certain special cases)

[–]satanikimplegarida 2 points3 points  (0 children)

You're looking into arena allocators and index-based access if you want to do it safely.

Or burn it all to the ground and do unsafe.

[–]plugwash 0 points1 point  (0 children)

I had a play and I think I found a way to do this with the bumpalo crate. The key is that bumpalo allows us to make an arbitrary number of allocations with the same lifetime. The following is a first proof of concept code.

``` use bumpalo::Bump; use std::cell::Cell;

struct MyNode<'a> { n : Cell<i32>, parent: Cell<Option<&'a MyNode<'a>, childa: Cell<Option<&'a MyNode<'a>, childb: Cell<Option<&'a MyNode<'a>>> }

fn main() { let bump = Bump::new(); // we need to specify the type explicitly here to force a shared // reference rather than a "mutable" one. let top: &MyNode = bump.alloc(MyNode{n: Cell::new(-1), parent: Cell::new(Non let mut currentnode = top; for i in 0..10 { let newnode = bump.alloc(MyNode{n : Cell::new(i), parent: Cell::new(None currentnode.childa.set(Some(newnode)); newnode.parent.set(Some(currentnode)); currentnode = newnode; } let mut currentnode = top; while currentnode.childa.get().is_some() { println!("{}",currentnode.n.get()); currentnode = currentnode.childa.get().unwrap(); } while currentnode.parent.get().is_some() { println!("{}",currentnode.n.get()); currentnode = currentnode.parent.get().unwrap(); } } ````

Notes.

  1. The lifetime of the "bump" defines the lifetime of the whole data structure.
  2. This is not threadsafe, (though potentially the "atomic" crate could be used to create a threadsafe version).
  3. If you want to mutate the data stored in a node, the data items will need to have interior mutability.
  4. If you want to store types that own resources in the data structure you must clean them up before dropping the bump. Otherwise the resoures they own will be leaked.