Comment by delamon
2 months ago
Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compromise safety.
2 months ago
Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compromise safety.
Rust wants all memory to be modeled as an ownership tree: the same bit of memory can't be owned by more than one data structure. A doubly linked list breaks that requirement so it can't be modeled in safe Rust directly. The options are using unsafe, or using one of the pointer wrapper types that have runtime checks that ensure correct behavior and own the underlying memory as far Rust is concerned.
Right. So it is not that double-linked lists are inherently unsafe, it is (just) Rust ownership model cannot represent them (any other cyclic structures).
It's not that it cannot, it just doesn't want to :-) (but you're right). I guess that in this very case of DLL, it's a bit hard to swallow. To be honest, it's because the rest of rust really helps me in other areas of my projects that I have accepted that. Learning the ownership model of rust is really painful, it really forces you to code in its way and it was not pleasant to me.
2 replies →
You can do it by combining ghostcell/qcell along with some bespoke "static/compile-time reference counting" for the double links part. But ghostcell/qcell is quite difficult to use with Rust's current feature set (it has to use lifetime hacks to place a safe "brand" on type instantiations, a kind of quasi-capability construct), so it hasn't become a part of standard rust so far.