For people who don't get the reference, this might be referring to the notoriously gnarly task of implementing a doubly-linked lists in Rust [1]
It is doable, just not as easy as in other languages because a production-grade linked-list is unsafe because Rust's ownership model fundamentally conflicts with the doubly-linked structure. Each node in a doubly-linked list needs to point to both its next and previous nodes, but Rust's ownership rules don't easily allow for multiple owners of the same data or circular references.
You can implement one in safe Rust using Rc<RefCell<Node>> (reference counting with interior mutability), but that adds runtime overhead and isn't as performant. Or you can use raw pointers with unsafe code, which is what most production implementations do, including the standard library's LinkedList.
Rust still needs a way out of that mess. It's conceptually possible to have compile time checking for this. Think of RefCell/Weak and .upgrade() and .borrow() being checked at compile time.
I've discussed this with some of the Rust devs. The trouble is traits. You'd need to know if a trait function could borrow one of its parameters, or something referenced by one of its parameters. This requires analysis that can't be done until after generics have been expanded. Or a lot more attributes on trait parameters. This is a lot of heavy machinery to solve a minor problem.
In practice, it really doesn't. The difficulty of implementing doubly linked lists has not stopped people from productively writing millions of lines of Rust in the real world. Most programmers spend less than 0.1% of their time reimplementing linked data structures; rust is pretty useful for the other 99.9%.
Yes. But the Arc has to wrap a Mutex, which means you have to lock to get access. It's a dual of the Rc/RefCell/borrow mechanism.
The trouble with calling .lock() is that there is a potential for deadlock. There are some people working on static analysis for deadlock prevention, which is a dual of the static analysis for double borrow protection problem. We're maybe a PhD thesis or two from a solution. Here's some current research, out of Shanghai.[1] Outlines the theory, but code does not yet seem to be available.
Apologies since I have not taken the time to learn rust yet, but I've written a lot of modern C++. Is the ownership model kind of like std::unique_ptr and std::move, and `Rc<RefCell<Node>>` the same idea as `std::shared_ptr`? But less idiomatic? Or do I have the wrong idea?
Not really, because Rust enforces a "many readers or one writer" invariant on everything that has no C++ equivalent. That invariant is precisely what makes the doubly-linked list case hard (because every interior node in the list would be readable from two places, which means it can never be written to).
If that's a specific use case you need to handle, it's O(1) again if you have a pointer to both the node to be removed and the previous node.
Whether it's more efficient to carry a second pointer around when manipulating the list, or store a second pointer in every list node (aka double linked list) is up to your problem space.
You’re assuming no other data structure points to the element. It may. Example: implement a cache.
Each element is: key, value, linked list node for hash table bucket, linked list node for LRU. Hash table to look up element. Element is both a member of hash table and of linked list. Linked list is used as LRU for feeling memory when needed.
LRU never traversed but often needs removal and reinsertion.
So that you learn that loaning is for giving temporary shared^exclusive access within a statically-known scope, and not for storing data.
Trying to construct permanent data structures using non-owning references is a very common novice mistake in Rust. It's similar to how users coming from GC languages may expect pointers to local variables to stay valid forever, even after leaving the scope/function.
Just like in C you need to know when malloc is necessary, in Rust you need to know when self-contained/owning types are necessary.
The biggest thing I’ve run into where I really want self-referential types is for work that I want to perform once and then cache, while still needing access to the original data.
An example: parsing a cookie header to get cookie names and values.
In that case, I settled on storing indexes indicating the ranges of each key and value instead of string slices, but it’s obviously a bit more error prone and hard to read. Benchmarking showed this to be almost twice as fast as cloning the values out into owned strings, so it was worth it, given it is in a hot path.
I do wish it were easier though. I know there are ways around this with Pin, but it’s very confusing IMO, and still you have to work with pointers rather than just having a &str.
It's not that it doesn't understand doubly linked list. It's just that you don't understand their consequences and have no objections against turning your program state briefly into inconsistent bullshit to facilitate them. The compiler minds. Unless you use Rc<>. That's what this language has for expressing inconsistency. Or unsafe {} if you are cocky. Borrows are not named pointers for a reason.
Why would I pair-program with someone who doesn’t understand doubly-linked lists?