And the first feedback is why so many unsafe blocks? What is it Option<NonNull<Node<T>>> ? '_ ?
Another reason to share, if you can understand Linkedin List, you are free to code in Rust ;)
This LinkedList obsession is a bit bizarre to me, and tends to come from older programmers who come from a time when coding interviews involved writing linked lists and balancing b-trees. To me though it also represents the stubbornness of C programmers who refuse to consider things like growable vectors a solved problem. My reaction to the LinkedList coders is not "well Rust needs to maintain ownership", its why does your benchmark for how easy a language is involve how easy it is to fuck around with raw pointers?.
LinkedLists are a tool, but to C programmers that are an invaluable fundamental building block that shows up early in any C programmers education due to how simple they are to implement and the wide range of use cases they can be used for. But they are technically an unsafe data structure and if you willing to let some of that stubbornness go and finally accept some guard rails, you have to be able to see that a data structure like linkedlists will be harder to implement.
It has nothing to do with the language; implementing with LinkedLists with any sort of guardrails adds a ton of complexity, either up front (e.g. borrowchecker) or behind the scenes (e.g. a garbage collector). When you accept this fact, it becomes ludicrous to imply that a LinkedList implementation is a good benchmark for the ergonomics of a language like Rust.
You're acting like it's some epic burn on Rust that there's some ugly code in its stdlib. It's not. Stdlibs are like that. Furthermore, as others have pointed out, linked lists in particular are a pathological case for Rust, meaning you're pointing and snickering at a special case of a special case. Most people never have to write or look at that kind of code.
This isn't the best solution for all cases! Sometimes performance is more important than safety, and there are things you can't do as efficiently without mutable data. And sometimes (especially for systems that are reactive rather than transformational, in Harel and Pnueli's terms, or for libraries) a garbage collector is an unacceptable cost.
And Rust is actually reasonably good at singly-linked lists; it's just doubly-linked lists (which inherently feature mutation) that are troublesome. Singly-linked lists with sharing through Arc are a little more expensive in Rust than in something like GHC, Ikarus Scheme, or OCaml, but that's hardly a damning criticism of Rust.
But you seem to be claiming that linked lists are unsafe in any language, and to anyone familiar with functional programming, that claim is obvious nonsense. Did you intend it?
I would think that the implicit context for safety comparisons with Rust would be other languages designed with safety as a goal. Those languages are almost all GCed! ML, Haskell, Scheme, Oberon, Coq, Erlang — all GCed. That's because GC helps enormously with type- and memory-safety. In the example in question, it ensures that your doubly-linked list manipulation cannot cause undetected type errors, use-after-free errors, double-free errors, or memory leaks; this last guarantee goes beyond what Rust can offer in this case. In ML, Haskell, and Oberon, it even ensures that all type errors are detected at compile time instead of run time.
There are a few languages designed with safety as a goal that do not normally use GC: Pascal, Ada, COBOL, and MISRA C. But they suffer enormously in expressivity, are not pointer-heavy, and are generally only viable alternatives in restricted domains.
The usual pointer-heavy non-GC languages are C and C++, and these have no concern whatsoever for safety, so it seems like a weak-man argument to target linked-list manipulation in them as unsafe relative to Rust.
The correctness criteria for doubly-linked lists are indeed not within the capability of Rust's (or Haskell's, or ML's, or Oberon's) static checking. That doesn't imply that it's impossible to statically verify doubly-linked-list manipulation code, and in fact I think Ada SPARK is capable of doing it. Certainly it's within the scope of what you can prove with Coq or Isabelle/HOL.
We're deep into semantics territory with "what's the right context for comparing Rust", but I would strongly argue that yet another language safe via GC is not interesting for its safety. As you point out, it's been done a lot. Rust is interesting because it pushes safety into a new level of runtime performance and (to some extent) lower hardware abstraction. AIUI that's the motivation for Rust, where most of the marketing and enthusiasm is, etc. And if you don't need that speed/control, Rust isn't much of an improvement: just use a GC and have more fun (unless you just think Rust is neat, I guess, but whatever).
So it's the languages already in that "low level" domain (broadly defined) that are its real competition IMO, C/C++, upstarts like Zig/Nim/Crystal, etc, languages where linked lists are on the cards. Especially for the problems where safety has previously been seen as too costly in either runtime or development time (no one is coding to fast moving web standards in Ada/SPARK, methinks).
And I don't think I implied that those languages' list manipulation is less safe than Rust's, rather that Rust's isn't any worse, besides being uglier. I made almost the same point from the other direction in another sub-thread: there's no use denying that Rust code for DLL's is uglier for no safety benefit on that particular task.
As others have pointed out, the whole question of linked lists in Rust is a huge distraction from its actual benefits and weaknesses.
I think it's noteworthy that, not only in the doubly-linked-list case but even in cases that use Arc (which doesn't require `unsafe`), Rust is less safe than mainstream GCed languages like Java (and arguably Haskell and OCaml). Rust can leak memory; those other languages can't. Its safety guarantees in those cases are a proper subset of theirs.
Unless I'm misunderstanding the situation? I've only written very small amounts of Rust.
Re safety: Rust has, um, a very specific idea of what "safety" means. It's basically things that could cause RCE, or at least incorrect writes I guess. Memory leaks are specifically not considered "unsafe". :) And really, the worst you can do with a memory leak is DoS, until the target reboots. Handling mutable data across threads is included, though, which Java at least is somewhat famously not great at; it's really easy to write Baby's First Race Condition Demo in Java. So it feels really weird to say Rust's safety guarantees are a strict subset of Java's.
OTOH I agree it's hard to imagine Rust beating out Haskell for raw safety guarantees by any measure, and I have no idea for OCaml (despite having written a lot more Ocaml, heh).
There are reasonable arguments to be had about Rust. I wish people would do those instead of all the nonsense you usually see.
Rust is not perfect. I wont go into its faults, but you know what they are. I think overall, Rust is a great language, but you have to be realistic and understand that some stuff you ignore in favor of the holistic view, others might not be able to. So sometimes maybe just take the criticism and deal with it, or if you're in the position, do something to fix the problem.
> I wish people would do those instead of all the nonsense you usually see
you seem to want to place the blame squarely on the critics, when the reality is that many people in your position are seemingly intolerant of any criticism of "their thing", even constructive criticism.
As for the Option type, it is exactly what it says. It's an optional, non-nullable node generic over type T. I suppose generics, optionals and the idea of non-nullable types might be exotic at first, but this is not a problem with Rust as much as it's a problem with C not being able to express these concepts in the first place and instead expecting you to spray null checks all over the place!
Learn Rust with entirely too many linked lists (2019) - https://news.ycombinator.com/item?id=22390662 - https://rust-unofficial.github.io/too-many-lists/index.html
In this series I will teach you basic and advanced Rust programming entirely by having you implement 6 linked lists. In doing so, you should learn:
- The following pointer types: &, &mut, Box, Rc, Arc, const, mut, NonNull(?)
- Ownership, borrowing, inherited mutability, interior mutability, Copy
- All The Keywords: struct, enum, fn, pub, impl, use, ...
- Pattern matching, generics, destructors
- Testing, installing new toolchains, using miri
- Unsafe Rust: raw pointers, aliasing, stacked borrows, UnsafeCell, variance
And regardless, this book is teaching from the perspective of intentional super-hard-mode. Most Rust developers will never have to write that much unsafe code.
I guess there’s plenty of space in the world for PHP programmers and their predecessors, the VB programmers. So… congrats?
https://github.com/llvm-mirror/libcxx/blob/master/include/li...
And this is with several years cpp experience, and maybe a few months of Rust on and off.
Having said that - yes, it's not pretty. About the same length though.
https://github.com/rust-lang/rust/pull/103093/files#diff-8bd...
As for the unsafety, I would assume the authors of collections know what they are doing and do that for performance.
The latter is easier to type but worse in almost every way. Ergonomics should guide you to the former, not the latter.
> Rust guarantees to optimize the following types T such that Option<T> has the same size as T:
> - Box<U>
> - &U
> - &mut U
> - fn, extern "C" fn1
> - num::NonZero*
> - ptr::NonNull<U>
> - #[repr(transparent)] struct around one of the types in this list.
> This is called the “null pointer optimization” or NPO.
> It is further guaranteed that, for the cases above, one can mem::transmute from all valid values of T to Option<T> and from Some::<T>(_) to T (but transmuting None::<T> to T is undefined behaviour).
Although I'm not sure if the ABI is guaranteed to match (Which could differ even if the layout matches AFAIK). The ABI for Box is guaranteed to match since https://blog.rust-lang.org/2020/01/30/Rust-1.41.0.html , and I would imagine NonNull is the same. Maybe you could open an issue in the UCG asking if you're needing confirmation.
I suppose one problem with this approach for C FFI is that there's a lot of different values which could all be "null pointers". Converting them all for Option would be awkward and slow, and you wouldn't want to ever risk getting this stuff wrong.
But pointers are also useful even if you aren't doing FFI. Eg for implementing custom data structures. In that case, Option<NonNull<T>> (Or even NonNull<T>) is usually better than *mut T. But its harder to type, and it doesn't clearly tell you if the pointer should be *mut T or *const T. NonNull<T> should be preferred because security/safety is at stake for this sort of code.
is the "In" in "LinkedIn" deliberate here or just a typo that was made twice?
[1]: https://rust-unofficial.github.io/too-many-lists/sixth.html
This is a great resource that outlines several different strategies for implementing linked lists in Rust: https://rust-unofficial.github.io/too-many-lists/
Conceptually, the list as a vague concept owns all the nodes. The ownership just stops being expressible directly through references the way Rust wants it to be. But you don't have to re-invent hierarchical ownership to implement DLLs in other languages, because it's not really there in the problem. You just have to accept that they're always going to suck under Rust's ownership model.
What you do instead is use integers instead of pointers. The integers are indexes into a Vec of list nodes, owned by the linked list. Since the nodes are now owned only by the Vec, which is in turn owned only by the linked list, the borrow checker will not complain.
Some people object that this is cheating somehow, but what is memory but a giant untyped global vector, shared between all parts of your application? Pointers into that giant shared array are just indexes with extra risk, since you have to trust that they point to real nodes that have been initialized. Plus, you often see users of a linked list put the nodes into an arena allocator anyway, especially in the kernel. The Vec in your Rust implementation serves the same purpose as the arena allocator.
That's pretty important actually. I'd say it's a qualitative difference. :) But yeah, arenas are great.
The usual complaints are that "Safe Rust doesn't let you do this", when unsafe Rust is right there to let you operate on any soup of pointers datastructure that you'd want to implement.
> you don't really need either ref counting (again, pretty obviously, witness every real world implementation)
If you implement DDL in a memory managed language, you effectively have the same behavior as you would in Rust with Arc or Rc. The ownership of the nodes then belongs to the GC or the RC value. You don't have to think about it because you're abstracted from the lifetime of each node by the language and runtime.
> or hierarchical ownership outside Rust
The ownership/borrow checker requires hierarchical to operate, but it doesn't stop you from writing unsafe Rust.
> Conceptually, the list as a vague concept owns all the nodes. The ownership just stops being expressible directly through references the way Rust wants it to be. But you don't have to re-invent hierarchical ownership to implement DLLs in other languages, because it's not really there in the problem. You just have to accept that they're always going to suck under Rust's ownership model.
Yeah, and that's what unsafe is for. Most code doesn't need vague ownership, though. I'd go as far as saying that the nudge towards clear ownership helps both maintainability and performance.
My concern is with the prevalence of this idea that unsafe Rust is not "real Rust" or that the existence and use of unsafe Rust somehow precludes any benefits of Rust.