Question is how to do these in Rust. An example might be a browser DOM: each node has a parent pointer, a list of child pointers, left and right sibling pointers, maybe a CSS node pointer, etc. Inserting or deleting nodes has to repair the pointers to and from the neighboring nodes as needed.
I know this is doable since obviously Servo (Rust’s initial driving application) has to do it. I hope the answer doesn’t involve the word “unsafe”. But I am quite unclear about how to create such a structure under Rust’s rules of pointer ownership, and also how to reliably reclaim storage when nodes and trees/subtrees are deleted. Plus there will be thread safety rules that should be statically enforced if possible.
I’ve heard that doubly linked lists in Rust are handled by an unsafe library, yet this seems even worse. Thanks.
Thanks, this sounds like a pretty serious abstraction inversion, exposes you to various kinds of bugs such as memory leaks, and gives a performance hit from all the hashing compared with using machine pointers, but I guess it does get rid of the circular references. Is it really the idiomatic answer? I’m ok if it is, but it’s not what I’d have expected from a low level language designed to replace C.
There are a few different ways to solve this problem without using unsafe and I’m not sure what would be considered idiomatic. Another option is to ultimately encapsulate all of the nodes in a reference-counted box like Rc or Arc and specify the type of your parent/child/sibling references to the same reference-counted box type. With that, you just share cloned instances around as needed.
The primary drawback here is that for mutable access you end up having to perform a lock every time on an underlying Mutex (or something similar). You also no longer have direct access to the singular instance of the node.
There are pros and cons to every approach.