Hacker News Reader

Comment by cjg | Hacker News Reader

I feel confident that my Rust is strong enough that I can already write any structure that is expressible in another language.

It might be that I would have to add extra safety mechanisms - such as Arcs or Mutexes. But it's all possible.

Some Rust developers might see such code as less idiomatic and look for a different solution, but if a different solution doesn't exist, there's always the fallback.

Less experienced Rust developers, however, are more used to seeing only the easier patterns and may not appreciate how to achieve some of the more difficult ones.

It's not that these patterns are harder in Rust than another language, per se. But more typing is needed to convince the compiler that you have everything lined up. Other languages will just let you introduce data races / crashes.

View on HN

> I feel confident that my Rust is strong enough that I can already write any structure that is expressible in another language.

I think it still can't handle arbitrary reference graphs without a garbage collector. If I'm wrong, please correct me, and provide proof. I'm very interested in the problem of non-GC arbitrary reference graph cleanups.

On the other hand, one could ask the question of do we really need the arbitrary reference graphs? Or are they just a crutch that we use to make things easier for us? Perhaps every algorithm that requires a complex reference graph can be also expressed in Rust's safe mechanisms.

Note that I don't have any deep knowledge about Rust, only stuff that I've read on various blogs.

If you need a graph, the main approaches I see in Rust code are:

a) Good ol' `Arc<Mutex>`, messy and has overhead, but easy to slap in and recreate the Java sea of objects.

b) Arena allocators -- often if the graph is used for an uppercase Algorithm like spring layout or something, the graph has a singular lifetime, so not being able to individually free the nodes is fine. Then you just have `struct Node<'a> { others: Vec<&'a Node<'a>> }` and all is good, the nodes all have the same lifetime and the borrow checker doesn't care about the mutual reference recursion.

c) Generational indices into a `Vec`. This gets used a lot for ECS systems like in Bevy, but they're very neat -- you can reassign a spot by just bumping the generation, so you don't need to worry about leaving holes or use-after-free. If you squint at it, a generational index is basically a pointer with provenance.

Think vgel's answer to you was helpful.

There are other techniques too, such as https://docs.rs/crossbeam-epoch/latest/crossbeam_epoch/

You can also use Rc/RefCell rather than Arc/Mutex if you don't need a multi-thread capable structure. You can always wrap a Mutex round the tree as a whole instead.

Reply on news.ycombinator.com