The safe, fast and easy way to do trees is by using Rc<RefCell<T>>. Rc/Arc allows data to be owned multiple times. You want this because this way a node can be referenced by its parent and its child at the same time. However, Rc makes the inner type inmutable. And you probably will want to mutate it in a tree, that’s what RefCell is for. With RefCell you do the borrow checking at run-time instead of at compile-time. This allows you to mutate T even though Rc only gives you an inmutable reference. This is called interior mutability.
RefCell doesn’t eliminate the borrow checker though, you must still follow its rules. If you try to get 2 mutable references to the inner type of RefCell, it will panic.
I know you don’t want to read unsafe, but you gotta hear about the alternative. Just use pointers. Pointers don’t have the borrow checker to restrict them. And self-referencing structures with interior mutability are not easy to borrow-check automatically. You can have the raw pointers as private fields of the struct so the code that is actually unsafe will be a few very small functions.
Here’s why the other options worse than pointers:
Rc<RefCell<T>> will clutter your code with boilerplate and it’s a pain to deal with. Pointers are not too ergonomic in rust (mainly because there is no -> operator), but they need way less boilerplate. Also, you already need to manually check the mutability rules, why not all the rules.
Another option that I’ve seen is “have a hashmap with all the nodes, and just store the id of the node instead of a reference”. This is the same as “have all the nodes on a Vector and store the index”. Think about this for a second. You have a pool of memory and a number that identifies what part of that pool is the memory you want. Seen it yet? That is exactly what a pointer is! If you do that, you’re just disabling the borrow-checker anyway. You just created your own memory allocator and will have to manage your memory manually, at that point just use pointers, it will be the same except with fewer boilerplate and indirection.
RefCell is neither mutable nor immutable. It’s a type like any other. What is special about RefCell is that it has a method like:
fn borrow_mut(&self) -> &mut T
Which means you can get a mutable reference to its contents by only having a normal reference to the RefCell.
By pointers I mean raw pointers. The pointers themselves are not unsafe. They are just normal pointers like you would have in C.
Rc can be used to generate weak refs. Which is what you want for your tree.
I don’t know about servo. So I can’t tell you much about it.
Don’t hope too much about the temporary unsafe thing. It’s not practical (maybe impossible) to make a safety checker that checks the entire program. The practical way is to make safe abstractions using unsafe code. For example rust itself is built upon plenty of unsafe code, however, it provides to you the appropriate abstractions so what you do is safe.
In this case. You can have a bit of unsafe code on your tree, so that the users of that tree have a safe API to do something that you needed unsafe code for.
For example one of the cases where you cannot automatically check the safety is in dereferencing a raw pointer returned by a FFI function call to a dynamic library. Your automatic safety checker would need to be able to read the library’s documentation. And at that point it’s not a real safety checker because the documentation may lie or have bugs.