3 ms·

Doubly linked lists. Any cyclic data structure.

hackyhacky 1y ago
Both of those are a direct consequence of Rust's memory model, not a result of animus against C++.
JoshTriplett 1y ago
That's not at all a "we don't like C++" problem. That's "the chosen borrow-checking model makes cyclic structures hard, you have to do Rc/Arc and some manual management, or use unsafe and raw pointers". (Frankly, the latter is easier.)
- pizlonator 1y ago
  Ref counting doesn’t work for cyclic data structures
  - JoshTriplett 1y ago
    It doesn't fully handle the memory management, but it handles having shared references. You can use weak references or manually break the links when you want to free something. Or you can use unsafe raw pointers, which frankly seem simpler. Either way you're going to wrap it in a data structure that encapsulates all the details.
  - NobodyNada 1y ago
    Sure it does. Make the backreferences weak, or use a library that provides cycle detection (or even full-on tracing GC if you really want).
    - pizlonator 1y ago
      That changes the semantics. It won’t work for a graph for example.
      - NobodyNada 1y ago
        Right. The comment you replied to said "Rc/Arc and some manual management" -- "some manual management" implying that you need to account for the change to semantics in the manner appropriate for your application.
        JoshTriplett 1y ago
        (Note that I edited my comment for clarity since the original reply. My original comment just said "reference counting".)
        pizlonator 1y ago
        The key part I agree with most in your edited comment is that unsafe raw pointers are the easiest way to deal with cycles. I think this is key. RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. In RC, you’d have to walk the graph to break cycles. That’s a rather important difference from how you’d manage a cyclic data structure in C, C++, Java, C#, or any GC’d language. In C/C++, you’d delete what you know to be dead; in Java et al it would be enough to kill the references that point at the outer edges of the dead subgraph. But you wouldn’t have to walk the subgraph to detangle the cycle. I think it really is worse than that; ie as you say, folks will just do anything but RC in that case. In Rust the safe bet would be to just shove all the nodes into an array and use indices (yuck!!!). But likely a lot of code with use raw pointers instead (also yuck). The whole thing where you reference count cyclic data structures is just too painful for sensible people
        adastra22 1y ago
        > RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. That’s exactly what weak references do.
        JoshTriplett 1y ago
        For a graph, I agree. For a tree with parent pointers, I'd absolutely use Rc, with Weak for the parent pointers.
  - adastra22 1y ago
    Rc has downgrade and the Weak type explicitly for this purpose.
  - cyberax 1y ago
    It works well. One easy trick is to have one reference count for the whole graph.
jnwatson 1y ago
While I think this is Rust's biggest flaw, this doesn't stem from any particular hatred of C/C++. This is related to memory safety, as it is very difficult to reason about memory lifetimes of object graphs with cycles.
adastra22 1y ago
The easiest way to implement these is with Weak references in one of the directions. This requires some checking and/or locks, but the fact it is not trivial to do is kinda the point: the integrity of a cyclic data structure depends on managing multiple pointers in multiple structs simultaneously, and with that comes concurrency dragons.
treyd 1y ago
There are doubly-linked list libraries in Rust. They are safe and well-designed. It's rare for a project to actually need a doubly-linked list. When you need it, you should use those instead of reimplementing your own.

Both of those are a direct consequence of Rust's memory model, not a result of animus against C++.

That's not at all a "we don't like C++" problem. That's "the chosen borrow-checking model makes cyclic structures hard, you have to do Rc/Arc and some manual management, or use unsafe and raw pointers". (Frankly, the latter is easier.)

pizlonator 1y ago
Ref counting doesn’t work for cyclic data structures
- JoshTriplett 1y ago
  It doesn't fully handle the memory management, but it handles having shared references. You can use weak references or manually break the links when you want to free something. Or you can use unsafe raw pointers, which frankly seem simpler. Either way you're going to wrap it in a data structure that encapsulates all the details.
- NobodyNada 1y ago
  Sure it does. Make the backreferences weak, or use a library that provides cycle detection (or even full-on tracing GC if you really want).
  - pizlonator 1y ago
    That changes the semantics. It won’t work for a graph for example.
    - NobodyNada 1y ago
      Right. The comment you replied to said "Rc/Arc and some manual management" -- "some manual management" implying that you need to account for the change to semantics in the manner appropriate for your application.
      - JoshTriplett 1y ago
        (Note that I edited my comment for clarity since the original reply. My original comment just said "reference counting".)
        pizlonator 1y ago
        The key part I agree with most in your edited comment is that unsafe raw pointers are the easiest way to deal with cycles. I think this is key. RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. In RC, you’d have to walk the graph to break cycles. That’s a rather important difference from how you’d manage a cyclic data structure in C, C++, Java, C#, or any GC’d language. In C/C++, you’d delete what you know to be dead; in Java et al it would be enough to kill the references that point at the outer edges of the dead subgraph. But you wouldn’t have to walk the subgraph to detangle the cycle. I think it really is worse than that; ie as you say, folks will just do anything but RC in that case. In Rust the safe bet would be to just shove all the nodes into an array and use indices (yuck!!!). But likely a lot of code with use raw pointers instead (also yuck). The whole thing where you reference count cyclic data structures is just too painful for sensible people
        adastra22 1y ago
        > RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. That’s exactly what weak references do.
        JoshTriplett 1y ago
        For a graph, I agree. For a tree with parent pointers, I'd absolutely use Rc, with Weak for the parent pointers.
- adastra22 1y ago
  Rc has downgrade and the Weak type explicitly for this purpose.
- cyberax 1y ago
  It works well. One easy trick is to have one reference count for the whole graph.

jnwatson 1y ago

While I think this is Rust's biggest flaw, this doesn't stem from any particular hatred of C/C++. This is related to memory safety, as it is very difficult to reason about memory lifetimes of object graphs with cycles.

adastra22 1y ago

The easiest way to implement these is with Weak references in one of the directions. This requires some checking and/or locks, but the fact it is not trivial to do is kinda the point: the integrity of a cyclic data structure depends on managing multiple pointers in multiple structs simultaneously, and with that comes concurrency dragons.

treyd 1y ago

There are doubly-linked list libraries in Rust. They are safe and well-designed. It's rare for a project to actually need a doubly-linked list. When you need it, you should use those instead of reimplementing your own.