@rust Blog post: Mutable object trees in Rust, using memory arenas
https://radiki.dev/posts/mutable-cursor-dags-in-arenas-rust/
@rust Blog post: Mutable object trees in Rust, using memory arenas
https://radiki.dev/posts/mutable-cursor-dags-in-arenas-rust/
I really don’t like the array approach. Indices into the array are effectively just references that are hidden from the compiler. They have all the same lifetime issues as real references, but the compiler can’t do anything to help you avoid them. Plus now you have the hassle of dealing with the array itself.
If you really want to opt out of the borrow checker, it’s better to use raw pointers and
unsafeblocks. That gets you out of managing the array, and it makes the fundamental unsafety of the solution much more obvious to other people reading the code.You can always use something like generational indices. They pop up a lot in ECS systems. A suitable container with an opaque index type prevents creation of invalid references, lets you check reference validity at runtime, and generational indices prevent reuse. The compiler can’t help with lifetime tracking, but that’s a problem with any shared reference type pointing to a resource with a lifetime that can only be known at runtime, eg. Arc.
As far as I understand that approach, it lets you detect dangling references but not prevent them, and it does nothing to detect when a node becomes unreachable. It also imposes a burden on the user to check every reference at runtime before it can be safely followed.
I think I’d much rather use
Rcwith strategic use of weak pointers to prevent cycles. That way at least some of your references can be trusted without verifying them on each use, and resources are freed when they become unreachable.If you need to represent a fully general graph structure, you’re pretty much obligated to implement some kind of garage collection on it, so any solution you come up with will be pretty hairy. Fortunately I’ve never once in my career needed a fully general graph. If you think you need one, it’s a good sign that you’re in the process of building an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. At that point you’re much better off embedding a real implementation of a garage collected language in your system.
I also feel I should point out that the need for the ugly wrapper enum in the article is a side-effect of using an array to store everything. If you use proper references or pointers, you can use
dynto automatically support every possible implementation of a trait, not just the ones listed in an enum. You might still want to use the array/enum approach for other reasons, like memory locality, butdynreferences provide a degree of freedom that can be very useful sometimes.If you don’t have a perf requirement like “all these things need to be in contiguous memory” then you probably don’t need a generational index anyway… it is effectively a weak reference, after all. ECS stores are optimised for repeatedly iterating over all the things, and games might have complex notions of “reachability”, but most things aren’t like that. There does seem to be a lot of “I don’t like using Rc RefCell” in object arena design that isn’t always justifiable, though nested generics don’t make for the most readable code in the world.
I think we’re more or less in agreement. I lean more towards leveraging language primitives when possible to get the most support from a compiler, but I’ll happily acknowledge that there are no one-size-fits-all designs.