Hacker News new | ask | show | jobs
by titzer 2528 days ago
You can't write a doubly-linked list without unsafe in Rust.
2 comments

Could not find any unsafe usage in Ian Jackson's, and it depends on no other crates.

https://lib.rs/crates/rc-dlist-deque

OK, perhaps we should say a doubly-linked list where each node contains the data and two pointers. While this is safe, it's also fairly inefficient, storing an extra counter with every node, which are dynamically updated, just to keep the borrow checker happy.
The word you're looking for is "intrusive".
Nope, intrusive is different. Because this is using an Rc (reference counted pointer) for the forward and backward pointers, these counters are both set to '2', as (almost) everything in a doubly-linked list has two things pointing to it, the thing after and the thing before.
I'm saying you're asking for intrusive ("each node contains the data and two pointers") whereas this list is not intrusive.
That's not true and a misunderstanding of what `unsafe` does. It has nothing to do with borrow checking (which is what trips people up when writing a double linked list). Unsafe is primarily used for FFI and lets you dereference raw pointers (among a few other related uses).
It is in general an escape hatch for being able to write code that isn't possible in safe Rust. Limitations of the borrow checker (e.g. for backpointers in circular data structures) definitely fall into that category. Even without FFI Rust would not be practical without unsafe.
You would use raw pointers instead of normal ones the type system (including borrow checker) cares more about, so ultimately yes it is about subverting the type system.