I've previously discussed on HN how Rust could support backpointers safely.[1] The idea is to have a "backpointer" attribute, with some additional checking. Backpointers are non-owning pointers locked in an invariant relationship with an owning pointer.
You need backpointers not only for doubly linked lists, but for some tree-type data structures. The backpointer invariant is easy to check at run-time, and it's often possible to eliminate that check at compile time. With this feature, few if any tree-type data structures need "unsafe". Tree update code is error-prone; you need all the help you can get there.
The other basic thing you can't express safely in Rust is a partially initialized array. If you had syntax for "This array is initialized up to element N", with suitable checking, "vec" could be written safely.
Rust is pretty close on this. Those are the two main gaps in the safety system. Calling external non-Rust code is a separate problem, one which hopefully will decline as more low-level libraries are rewritten in Rust.
I don’t think your solution works. It will make sure the pointer is never null (assuming these back pointers are !Sync) sure, but rust guarantees far more that that. Each ownership type (value, &, &mut) is a capability, it very important to rust guarantees that you can’t go up the chain. Each node have an owned pointer to the next means that it can mutate it at anytime, the back pointer would always alias the previous node meaning that it has to be a weakened “&” reference (allows aliasing, lifetime rules relaxed). Because all of the nodes are owned it’s possible to traverse the back pointer then move forward again and recover ownership or a &mut of the same node twice.
You can however allocate the nodes in an arena and store your forward and back pointers in Cells. You can’t move the arena, but you’ll get nice back pointers. You could also make the linked list be backed by a slab and store indexes instead of node pointers. Both of these solutions will likely be more cache and allocation efficient than a traditional link list which does allocation for every node.
Right, you can go backwards, but not with mutability. Weak refs have some of the same problems.[1] You don't get the ability to mutate doubly linked lists this way. Navigate trees, yes; mutate them from below, no.
Right, they are basically weak references, but more efficient ones. Weak references involve not just a counter, but something that gets deallocated when the counter goes to zero. That adds complexity to a trivial operation.
You need backpointers not only for doubly linked lists, but for some tree-type data structures. The backpointer invariant is easy to check at run-time, and it's often possible to eliminate that check at compile time. With this feature, few if any tree-type data structures need "unsafe". Tree update code is error-prone; you need all the help you can get there.
The other basic thing you can't express safely in Rust is a partially initialized array. If you had syntax for "This array is initialized up to element N", with suitable checking, "vec" could be written safely.
Rust is pretty close on this. Those are the two main gaps in the safety system. Calling external non-Rust code is a separate problem, one which hopefully will decline as more low-level libraries are rewritten in Rust.
[1] https://news.ycombinator.com/item?id=14303858