[andrewflnr]

"Those solutions" start off being hierarchical ownership or reference counting, but turn into "pointers or reference counting". Requiring pointers is implicit to the definition of linked lists, and calling it out here is silly. And you don't really need either ref counting (again, pretty obviously, witness every real world implementation) or hierarchical ownership outside 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.

[db48x]

Technically the pointers don’t have to be actual pointers. And if they’re not actually pointers, then Rust’s ownership model and borrow checker will be perfectly content; they’ll barely trouble you at all. And you won’t even need any unsafe blocks.

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.

[andrewflnr]

> shared between all parts of your application... with extra risk

That's pretty important actually. I'd say it's a qualitative difference. :) But yeah, arenas are great.

[estebank]

> Requiring pointers is implicit to the definition of linked lists, and calling it out here is silly.

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.