3 ms·

Seriously, just use unsafe. “Welp, can’t write a doubly-linked list in safe Rust so I might as well use C” is throwing the baby, the bathtub, and the rest of t

Seriously, just use unsafe. “Welp, can’t write a doubly-linked list in safe Rust so I might as well use C” is throwing the baby, the bathtub, and the rest of the greater metro area out with the bathwater.

chongli 4y ago
Sorry to stretch the analogy beyond recognition but a lot of people who would prefer C over Rust want to build a bathtub for the baby without dragging the rest of the greater metro area into the picture.
- stouset 4y ago
  Yeah, and a ton of people still complain about having to put their seat belt on in the car too.
  - chongli 4y ago
    No, the point is that Rust does not replace C. At best, it’s “safe C++” (and even that’s debatable, given the cyclic references issue discussed here). But for the use cases where even C++ is too much, there is no replacement for C. Zig aspires to be that minimal language. It seems to have a lot of really good ideas. It’s too bad the compiler is so opinionated that a lot of developers will be alienated by it.
    - stouset 4y ago
      > No, the point is that Rust does not replace C. At best, it’s “safe C++”. This is a meaningless distinction. No language in the history of languages has ever strictly "replaced" another. Over time Rust will eat into the market share of every language to differing amounts. C and C++ top the list of languages that Rust will likely eat into the most, but of course they will still continue to exist and people will find reasons to continue using them. > But for the use cases where even C++ is too much, there is no replacement for C. Rust is a significantly less complicated language than C++. But what does this even mean, anyway? Whose use-case is "A systems programming language, but the spec can only be so many pages long?" > (and even that’s debatable, given the cyclic references issue discussed here) struct Node<T> { data: T, left: *mut Node<T>, right: *mut Node<T>, parent: *mut Node<T>, } Wow, so difficult! If the comparison is C, I don't even have to bother writing a safe abstraction around this.
archi42 4y ago
Not a rust dev, but shouldn't this be solvable using generics? At least I'm pretty sure I could construct a double linked list with a sane API using only references in C++ with templates. I would have used inheritance to create a "ListBaseType" with a "ListElementType" specialization (with all the data required to wrap some element) and an empty "ListNullType" to use as begin/end elements. A quick Google search results in a implementation using "None" instead: https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a82098ca https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a... (I don't vouch for it!) In the end the correctness boils down to correctly handling the beginning/end. It does matter little if that's a NULL, None, nullptr or ListNullType. The real difficulty would be adding thread safety with minimal performance loss.
- DougBTX 4y ago
  Not really. The fundamental issue is ownership, what is responsible for freeing resources when they are no-longer needed? In that example, owning references are used on the "next" pointers and weak references are used on the "previous" pointers. Then there are no ownership loops, and everything is fine. In a GC language, the runtime has ownership over memory allocations. The "owner" is actually outside the application code, so the application code can have as many reference loops as it likes, as none of them are owning references.
- scaredginger 4y ago
  Why would you design a list this way? So many things are wrong here; to name just a few: 1. Pointers work fine, you're not solving any problems here. 2. You can't rebind references in C++, so you wouldn't be able to delete nodes 3. Even with this insane approach, why would you use inheritance over a sum type? 4. Extra allocations or statics are needed to hold sentinels. As for why this wouldn't work in Rust, in addition to its many general problems, the fundamental issue is aliasing. Rust mandates that if a mutable reference to an object is alive, then nothing else references it. Thus, it would only work if your entire list was immutable; this may fit within your definition of a sane API, but it's not what most people would want if they were choosing to use Rust.
  - 4y ago
throwaway2037 4y ago
Yes, I felt the same when I read the grandparent post! I am not a Rust nut (nor expert!), but the improvements offered seem very impressive. After reading your post, I immediately went to Google this phrase: "doubly-linked list in safe Rust". Plenty of good and interesting results!
pizza234 4y ago
There are convenient libraries for working with such data structures. Unsafe should be relegated for highly specific us cases.

chongli 4y ago

Sorry to stretch the analogy beyond recognition but a lot of people who would prefer C over Rust want to build a bathtub for the baby without dragging the rest of the greater metro area into the picture.

stouset 4y ago
Yeah, and a ton of people still complain about having to put their seat belt on in the car too.
- chongli 4y ago
  No, the point is that Rust does not replace C. At best, it’s “safe C++” (and even that’s debatable, given the cyclic references issue discussed here). But for the use cases where even C++ is too much, there is no replacement for C. Zig aspires to be that minimal language. It seems to have a lot of really good ideas. It’s too bad the compiler is so opinionated that a lot of developers will be alienated by it.
  - stouset 4y ago
    > No, the point is that Rust does not replace C. At best, it’s “safe C++”. This is a meaningless distinction. No language in the history of languages has ever strictly "replaced" another. Over time Rust will eat into the market share of every language to differing amounts. C and C++ top the list of languages that Rust will likely eat into the most, but of course they will still continue to exist and people will find reasons to continue using them. > But for the use cases where even C++ is too much, there is no replacement for C. Rust is a significantly less complicated language than C++. But what does this even mean, anyway? Whose use-case is "A systems programming language, but the spec can only be so many pages long?" > (and even that’s debatable, given the cyclic references issue discussed here) struct Node<T> { data: T, left: *mut Node<T>, right: *mut Node<T>, parent: *mut Node<T>, } Wow, so difficult! If the comparison is C, I don't even have to bother writing a safe abstraction around this.

archi42 4y ago

Not a rust dev, but shouldn't this be solvable using generics? At least I'm pretty sure I could construct a double linked list with a sane API using only references in C++ with templates. I would have used inheritance to create a "ListBaseType" with a "ListElementType" specialization (with all the data required to wrap some element) and an empty "ListNullType" to use as begin/end elements. A quick Google search results in a implementation using "None" instead: https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a82098ca https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a... (I don't vouch for it!) In the end the correctness boils down to correctly handling the beginning/end. It does matter little if that's a NULL, None, nullptr or ListNullType. The real difficulty would be adding thread safety with minimal performance loss.

DougBTX 4y ago
Not really. The fundamental issue is ownership, what is responsible for freeing resources when they are no-longer needed? In that example, owning references are used on the "next" pointers and weak references are used on the "previous" pointers. Then there are no ownership loops, and everything is fine. In a GC language, the runtime has ownership over memory allocations. The "owner" is actually outside the application code, so the application code can have as many reference loops as it likes, as none of them are owning references.
scaredginger 4y ago
Why would you design a list this way? So many things are wrong here; to name just a few: 1. Pointers work fine, you're not solving any problems here. 2. You can't rebind references in C++, so you wouldn't be able to delete nodes 3. Even with this insane approach, why would you use inheritance over a sum type? 4. Extra allocations or statics are needed to hold sentinels. As for why this wouldn't work in Rust, in addition to its many general problems, the fundamental issue is aliasing. Rust mandates that if a mutable reference to an object is alive, then nothing else references it. Thus, it would only work if your entire list was immutable; this may fit within your definition of a sane API, but it's not what most people would want if they were choosing to use Rust.
- 4y ago

throwaway2037 4y ago

Yes, I felt the same when I read the grandparent post! I am not a Rust nut (nor expert!), but the improvements offered seem very impressive. After reading your post, I immediately went to Google this phrase: "doubly-linked list in safe Rust". Plenty of good and interesting results!

pizza234 4y ago

There are convenient libraries for working with such data structures. Unsafe should be relegated for highly specific us cases.