[Starlevel001]

Rust is a clever language, which wrecks havoc on people's programming ego by making them very inclined to try and write clever code.

But if you avoid trying to be really annoying with the type system like the majority of the ecosystem is, and slap Arc/RefCell/heap allocations everywhere, the language turns back into a high-level language again.

Unfortunately, stepping outside the realm of ``core`` and ``alloc`` and ``std`` means having to repeatedly step on overly clever landmines everywhere you go.

[melony]

The problem is that you can't even build data structures from introductory algos in Rust without pulling your hair out. No linked lists, no graphs.

[msbarnett]

That’s really only a problem if you spend a significant amount of time trying to “build data structures from introductory algos” without reaching for unsafe, though.

If you find it easy to build a linked list or graph in C, you can do it just as easily in Rust — use unsafe, and you have your easy linked list, with exactly as much safety as it had in C. Sure, it’s more challenging to build a fully memory and thread safe linked list or graph, but it’s actually hard as hell to do that in C too. Other languages make it easy to build one with these guarantees only by requiring significant runtime support, which is out of scope for Rust.

In the end, it’s pretty unrealistic to expect that any language would allow you to write a guaranteed memory and threadsafe graph structure with zero runtime overhead, without a lot of knowledge, time, and attention on your part — there are no silver bullets.

And if you’re using Rust for anything real you’re generally not doing sophomore computer science homework like this anyway.

[nyanpasu64]

The problem is that unsafe data structures are often less safe (harder to avoid UB) than in C, because in the presence of pointer aliasing and cycles (found in unsafe data structures including BTreeMap's node.rs https://doc.rust-lang.org/src/alloc/collections/btree/node.r...), Stacked Borrows places strict conditions on constructing &mut T (they invalidate some but not all aliasing *const T). And the user of an owning or intrusive linked list generally expects to receive &mut T, which is not always safe to construct because of Stacked Borrows. In fact, Gankra, a major contributor to unsafe Rust libraries, standards, and documentation, doesn't solve this problem through axiomatic reasoning, but instead an "oversimplified" "heuristic" (IMO hopes and prayers): https://rust-unofficial.github.io/too-many-lists/fifth-stack... (written 2022-01).

In practice, I find that unsound libraries frequently get written and used unknowingly in the wild. I've commented on this earlier at https://news.ycombinator.com/item?id=31897503.

In short, I believe that Stacked Borrows places unreasonable and unattainable requirements on authors of unsafe structures and algorithms, which serve as the foundation for practically all safe code (outside of the vanishingly rare case of code operating on tree-shaped fixed-size variables allocated solely on the stack, and never creating aliased mutable pointers).

[msbarnett]

And The “easy” C sophomore computing science graph is inevitably chock full of Undefined Behavior too, the implementers just never noticed or gave a shit because they cobbled something together that looked superficially correct, the compiler didn’t complain, so they decided they were all good. Sophomores, as it turns out, are hardly world-beating experts in C standard esoterica.

The rest of what your wrote is completely irrelevant to the original point: this seems hard in safe Rust only because you’re comparing it to doing something totally different and simpler in C.

Grind your axe about stacked borrows elsewhere.

[nyanpasu64]

I agree that sophomores are better off sticking with safe Rust than writing linked lists, but they'll be using libraries written in unsafe Rust, and a "safe" Rust program built on unsound foundations is undefined behavior anyway (through no fault of your own).

You said Rust linked lists have "exactly as much safety as it had in C". Are you seriously arguing that C linked lists are just as wrong as Rust ones, by saying a CS student is as likely to write an incorrect C linked list as a hardened professional is to write an incorrect Rust linked list (eg. Tokio and https://gist.github.com/Darksonn/1567538f56af1a8038ecc3c664a...)? Stacked Borrows ensures that translating sound C code into idiomatic Rust APIs produces needlessly unsound Rust code, and the Rust language (or a specification if it existed) means C translated directly into raw-pointer Rust is unidiomatic and you're fighting the language every step of the way (no autoderef, no -> operator). At this point, an experienced programmer is more likely to write and use a correct C linked list than write and use a Rust one.

[msbarnett]

> Are you seriously arguing that C linked lists are just as wrong as Rust ones, by saying a CS student is as likely to write an incorrect C linked list as a hardened professional is to write an incorrect Rust linked list

What?

No, I’m saying that writing a linked list in C is “easy” if and only if your implementation doesn’t even bother to try to cope with the 9000 foot guns C offers you — that your easy C graph data structure is basically always a disaster of Undefined Behavior and thread unsafety, because if you try to make it otherwise, it will cease being at all easy. It will become in fact really fucking hard

So when I say “you can have your easy C-style linked list in Rust, just use unsafe”, I agree entirely: the Rust implementation will also likely be a gigantic clusterfuck of Undefined Behavior. That’s the entire point: it’s only ever easy in either language if you’re willing to blow both of your feet and you dick clean off. It’s easy only if you’re so inexperienced and naive that you don’t even perceive the dangers of the highly efficient dick-and-leg removal device you’ve built in C, and whine on forums about how mean-old-Rust is hard in comparison because it keeps refusing to compile your dick_exterminator.rs file.

That’s the Apples to Apples comparison. Which unsafe thing is harder to get right, I don’t honestly give a flying fuck about. Now, it’s highly de-fucking-batable that it’s easier for “an expert C programmer” to avoid undefined behavior entirely in an arbitrary mutable graph implementation in the presence of multithreading unless we’re talking about an entirely mythical level of expert here, but that’s utterly offtopic to the discussion at hand. You were just looking to grind a fucking axe about Stacked Borrows and decided to rant at me about it, but it really has fuck all to do with anything I was saying, man.

You can have an easy graph structure in Rust in the only way you can easily have one in C: by not giving a single shit about correctness.