The only Rust programs I've written are simple toys, and I don't know enough computer science to fully understand the problem space here. However, the first thing that comes to mind is, what if you just used unsafe for your doubly linked list?
I understand this defeats the point of using Rust. But if the argument is "I'm using C because I actually need doubly linked lists and Rust makes that hard/slow", well C is also unsafe, so using Rust with an unsafe block for your doubly linked list seems like an improvement.
I feel like at least part of the reason not to do this is "because the Rust community will yell at you." Well, maybe they shouldn't do that? If you were using C no one would care, so switching to unsafe Rust shouldn't imply the sky is falling.
Unsafe is quite plainly the right tool for the job. Yes, people can mess up unsafe code, but that really is just how things are (until we get magic formally verifying compilers?!). I appreciate your levelheaded take, rather than advocating for only C or exaggerated concern for safe Rust.
Why would the rust community “yell at you” for using unsafe somewhere where it’s clearly needed?
By the way, unsafe doesn’t defeat the purpose of rust. The entire point of rust is that it lets you build safe abstractions on top of unsafe code, not that it eliminates unsafe code entirely.
The answer to "why not use unsafe" is it's hard to do correctly. What you have to do is pretty well documented https://doc.rust-lang.org/nomicon/working-with-unsafe.html but it's fiddly, tedious, easy to get wrong (you have to understand what the compiler is doing internally), and there are no automated checks to verify you have got it right. A newbie has almost no hope of getting right in the first 5 tries (5 is entirely made up.)
But, Rust already provides a linked list in it's standard library: https://doc.rust-lang.org/std/collections/struct.LinkedList.... So a Rust programmer might say there is no need use unsafe if you want a linked list. There is a "source" link on that page, so it isn't hard to see how it's done. Yes, it does use "unsafe".
Where it gets a little complex is a C programmer will look at that implementation and scoff at the linked list the Rust standard library provides. Amazingly the C and Rust programmers agree that this implementation is mostly useless. We know that because the Rust documentation says: "NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache [than this Rust linked list]."
When a C programmer uses a linked list, he almost invariably uses what someone above termed above an "intrusive" implementation. An intrusive implementation is typically faster, more memory efficient, and makes just as good use of the CPU cache as the Rust Vec or VecDeque. An intrusive implementation reserves a bit of memory inside of the object you want to put in a linked list for the linked list code. That memory is typically "owned" by the linked list code, as in it manages it's lifetime, whereas the lifetime of the object the memory is in is managed by some other mechanism. For example, if you delete some unrelated item it list, it might have to reach in and modify the linked list pointer in this item. But Rust has a simple memory model: if you modify an object you have to prove you own it. The linked list code reaching into another object can not do that.
That's one example, but intrusive linked lists break Rust's ownership and borrowing rules in so many ways, they are like oil and water. As far as I can tell there is no way to provide an intrusive linked list library in Rust that is safe to use, which is to say all code that uses it would have to be flagged as unsafe too.
This probably raises as more questions that it answered, and you are probably wondering how could two implementations of the same thing (a linked list) be so different. I'm not going to go down that rabbit hole, other than to remark it's clear a lot of Rust programmers commenting here don't understand the flexibility the intrusive method gives you. But their instincts are right about one thing: they are dangerous. It's the sort of danger a C programmer is entirely comfortable with, but that same danger is what has lead to C programmers being responsible for a of CVE's. They are right about another thing too: if you put a bit of thought into it, you can usually come up with something that is for all practical purposes just as fast, and the Rust compiler can prove is safe. Sometimes though, "a bit of thought" is an understatement, and sometimes it feels like you are in a straight jacket.
The article code be read is someone straining against that straight jacket, doing a lot of thinking and coming up with what a C programmer would call a fairly ugly (and slower) solution. The old C programmer in me says that's a fair summary. But I also have to acknowledge it is a very safe solution.
> As far as I can tell there is no way to provide an intrusive linked list library in Rust that is safe to use, which is to say all code that uses it would have to be flagged as unsafe too.
But if you need a linked list, would that be so bad? Again, the alternative is C where literally the whole program is unsafe...
> But if you need a linked list, would that be so bad?
The answer from a Rust programmers perspective is: yes, it's bad.
Rust's secret sauce is if you don't use unsafe, you have a memory safe language. In fact it's better than that. Due to its strong type system "safe Rust" is safer than almost all languages, including Java and the popular interpreted languages like Python, the one notable exception being Ada spark.
The problem with this rosy picture is unsafe Rust. It's harder to get right than C (which 100% unsafe), and you can't write a non-trivial Rust program without at least calling unsafe code. That means there is a trade-off going on. If Rust can keep the amount of unsafe code small and bounded, it wins over 100% unsafe C. If it can't, well you may as well use C.
Today's Rust does manage to keep unsafe code bounded. Just about any program can be written using purely safe code by using Rusts standard library ("std"). Std itself does contain a high'ish percentage of unsafe code (about 20%), but crucially a programmer using std never needs to use unsafe if they are prepared to make the occasional speed tradeoff (as could have been done in the article). Thus Rust + std + the rule "no unsafe", makes for a perfectly memory safe programming environment.
Based on that, a pact has now arisen in the Rust community. You are allowed to write libraries like "std" that use unsafe, but normal usage of those libraries must never require the caller to use unsafe code. The pact ensures unsafe code doesn't spread like a virus, and so Rust will always maintain it's safety advantage over C for your average programmer.
But, it's not possible to write an intrusive implementation of a linked list that doesn't required the caller to use unsafe. Therefore, any such library would be ostracised by the Rust community.
Using one when you don't need to would be considered bad, but unsafe exists to be used when necessary. Nobody shuns unsafe code purely for it being unsafe code.
Ahh, I stand corrected. It is possible to implement an intrusive collection without making the caller use unsafe. For some uses.
For the others he's abstracted the unsafe calls to just cursor_from_ptr and cursor_mut_from_ptr. I suspect they would see heavy use, but he's reduced the safety guarantees you have to prove to the absolute minimum. Colour me impressed. I wish I had thought of that.
I might become the 5,243,766 + 1 user.
As for this:
> Using one when you don't need to would be considered bad, but unsafe exists to be used when necessary. Nobody shuns unsafe code purely for it being unsafe code.
Hmmm. You've just contradicted yourself. You've just said if you were given a safe and unsafe implementation of the same thing, you would shun the unsafe version. Than go on to say "Nobody shuns unsafe code purely for it being unsafe code".
No, I did not. It is true that nobody shuns unsafe code for simply being unsafe. Choosing a safe alternative over an unsafe one means that there is an alternative. Unsafe code to do the job that unsafe code is meant to do is totally fine. That’s the reason it exists!
I understand this defeats the point of using Rust. But if the argument is "I'm using C because I actually need doubly linked lists and Rust makes that hard/slow", well C is also unsafe, so using Rust with an unsafe block for your doubly linked list seems like an improvement.
I feel like at least part of the reason not to do this is "because the Rust community will yell at you." Well, maybe they shouldn't do that? If you were using C no one would care, so switching to unsafe Rust shouldn't imply the sky is falling.