Flattening Rust’s learning curve

> Treat the borrow checker as a co-author, not an adversary

Why would I pair-program with someone who doesn’t understand doubly-linked lists?

I'd rather pair program with someone wary of double-linked lists, but is really hot on understanding ownership than the other way around.

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.

https://rust-unofficial.github.io/too-many-lists/

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.

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.

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.

> Rust still needs a way out of that mess.

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%.

Because you care about productivity and safety more than l33t h4x0r hazing rituals?

I am working on a code base, that among its many glories and poo balls every list is a doubly linked list.

Stop!

If you are using a doubly linked list you (probably) do not have to, or want to.

There is almost no case where you need to traverse a list in both directions (do you want a tree?)

A doubly linked list wastes memory with the back links that you do not need.

A singly linked list is trivial to reason about: There is this node and the rest. A doubly linked list more than doubles that cognitive load.

Think! Spend time carefully reasoning about the data structures you are using. You will not need that complicated, wasteful, doubly linked list

> There is almost no case where you need to traverse a list in both directions

But you might need to remove a given element that you have a pointer to in O(1), which a singly linked list will not do

Because most of my code is not doubly-linked lists!

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.

Or whether an O(n) removal is acceptable.

Getting the pointer to that element means randomly hopping around the heap to traverse the list though.

Linked lists are perfect for inserting/deleting nodes, as long as you never need to traverse the list or access any specific node.

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).

Doubly linked lists are rare, but backlinks to the owner are often needed. It's the same problem, mostly.

> Rust still needs a way out of that mess.

It has one: use raw pointers and unsafe. People are way too afraid of unsafe, it's there specifically to be used when needed.

Note that some users of GC languages that support stack allocation, are used that it is a compiler error trying to have such a pointer/reference.

D example, https://godbolt.org/z/bbfbeb19a

> Error: returning `& my_value` escapes a reference to local variable `my_value`

C# example, https://godbolt.org/z/Y8MfYMMrT

> error CS8168: Cannot return local 'num' by reference because it is not a ref local

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.

Backlinks work fine with weak Arc references, don’t they?

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.

[1] https://arxiv.org/pdf/2401.01114

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.