4 ms·

The difficulty in Rust is reflecting how there's not much difference between a correct doubly-linked list and an incorrect one: it's not too hard to end up with

by dbaupp 9y ago

The difficulty in Rust is reflecting how there's not much difference between a correct doubly-linked list and an incorrect one: it's not too hard to end up with dangling pointers due to bad destruction. It's (very) hard for a compiler to tell that a back-pointer won't be held around after the thing to which it points is destroyed, or even the pointer to a node after something else deallocates it, e.g. in pseudo-code: def remove_from_list(node: pointer ListNode): node.prev.next = node.next node.next.prev = node.prev Unfortunately, this would be a use-after-free, if one were to translate that code into C++, using modern features that are always touted as part of "modern C++ is safe enough", with the obvious definition: class ListNode { std::unique_ptr<ListNode> next; ListNode *prev; // some data or whatever }; One could even switch to 'std::optional<std::reference_wrapper<ListNode>> prev' (i.e. trying to avoid C legacy that people sometimes suggest is the unsafety in C++), and... it doesn't change anything. Each node is owned by its previous one, meaning 'node.prev.next = node.next' overwrites the owner of 'node', and so the next line is accessing freed memory. Of course, it's not very hard to fix (or find, in the first place) this particular example, e.g. just swapping the lines, or a completely different ownership scheme ala what you say about std::list. But, the above code looks very reasonable, is a problem even using good modern idioms in C++, and is also only a minor change from correct code (and, C and C++ do not offer much assistance to find or fix these sort of problems).

mehrdadn 9y ago
Fun fact: The `unique_ptr` approach you mention is also broken (and I would go so far as to say it's wrong entirely). The destructors will blow the stack. I really do think std::list's approach is the only correct solution for a generic linked list.
- dbaupp 9y ago
  Using the default destructor is broken, yes, but the approach isn't: one can avoid it in the list's destructor using a loop that walks over the list to not let nodes be destroyed recursively (i.e. clearing the next pointers). node = head while node: next = transferOwnershipAndClear(node.next) node = next Where the third line would be 'std::unique_ptr<...> next(std::move(node.next)); ' in C++ that uses unique_ptr<...>, or 'let next = node.next.take()' in Rust that uses Option<Box<...>>. Of course, you could definitely argue that there's little point using unique_ptr if you're still having to write a destructor for the list itself.
  - deleted 9y ago
    [deleted]
  - mehrdadn 9y ago
    You can keep putting bandages over it, but the approach itself is fundamentally broken. It fundamentally intertwines the memory management with the data structure management when the two really are pretty orthogonal to each other. For example, if you ever want to use a different allocation function, you'll run into trouble. How do you get the right function to deallocate each node, and at what penalty? Does every node keep a pointer to a common allocator now? Or, for example, if you have a move constructor/assignment like that, now you're declaring that it makes sense to "move" one node onto another, even if they use different allocators. But does it really? Their ownership simply doesn't have anything to do with their sibling relationship, and you're forcing them to be tied together. Like, yeah, you can keep putting bandages on top of this, rub some alcohol on it, and giving it crutches to make it work, and I'm sure you'll eventually make it work, but the right thing to do is to just step back and realize the flaw is in the approach itself: some concerns are global across the nodes (like memory management), and some are local (data structure management), and hence it doesn't make sense to mix the two. (Oh, and did I point out that all of this means you'll have to find a different solution when the data structure is no longer linear to allow a destructor hack like that? The fact that the scope of the approach is limited by a property that really isn't all that relevant to the actual problem is another sign that it isn't the gift one.)
    - dbaupp 9y ago
      I am not advocating for it being a great way to implement a linked list, just using it as an example that can be easily understood in a throwaway comment. As an alternative: # Delete all the elements from node 'from' to (but not including) node 'to' erase(list, from, to): from.prev.next = to to.prev = from.prev while from and from != to: from = from.next list.allocator.free(from) # update 'tail' if necessary destroy(list): node = list.head while node: next = node.next list.allocator.free(node) node = next This code is also wrong. Calling erase(list, list.tail, list.head) or similar will create a loop, and then destroy will loop forever/read dangling pointers. This is also very close to correct (I believe 'destroy' looking for node == tail instead of node being null would avoid the loop), but isn't. Yes, it's easy to write a linked list, but it's also easy to screw up in subtle ways, and that line is thin. The safe subset of Rust restricts what is legal to be able to get some sort of control/understanding on pointer-soups, so that it can verify and validate that problems like the above don't turn into really bad problems. (The equivalent thing couldn't happen with vector-and-indices or arena-allocated nodes, and would result in the less dangerous[1] problem of an infinite loop/memory leak with Rc/Weak or garbage collection.) [1]: A denial of service is better than remote code execution (proof: the latter can be turned into the former).
pjmlp 9y ago
I think the C++ example is safer modeled like this class ListNode { std::unique_ptr<ListNode> next; std::weak_ptr<ListNode> prev; // some data or whatever };
- dbaupp 9y ago
  That doesn't work. std::weak_ptr is a reference counted pointer matched to std::shared_ptr; there's no concept of weak pointers (i.e. non-owning with dynamic checks) for std::unique_ptr, which corresponds almost exactly to Rust's Box.

by dbaupp 9y ago

mehrdadn 9y ago

Fun fact: The `unique_ptr` approach you mention is also broken (and I would go so far as to say it's wrong entirely). The destructors will blow the stack. I really do think std::list's approach is the only correct solution for a generic linked list.

dbaupp 9y ago
Using the default destructor is broken, yes, but the approach isn't: one can avoid it in the list's destructor using a loop that walks over the list to not let nodes be destroyed recursively (i.e. clearing the next pointers). node = head while node: next = transferOwnershipAndClear(node.next) node = next Where the third line would be 'std::unique_ptr<...> next(std::move(node.next)); ' in C++ that uses unique_ptr<...>, or 'let next = node.next.take()' in Rust that uses Option<Box<...>>. Of course, you could definitely argue that there's little point using unique_ptr if you're still having to write a destructor for the list itself.
- deleted 9y ago
  [deleted]
- mehrdadn 9y ago
  You can keep putting bandages over it, but the approach itself is fundamentally broken. It fundamentally intertwines the memory management with the data structure management when the two really are pretty orthogonal to each other. For example, if you ever want to use a different allocation function, you'll run into trouble. How do you get the right function to deallocate each node, and at what penalty? Does every node keep a pointer to a common allocator now? Or, for example, if you have a move constructor/assignment like that, now you're declaring that it makes sense to "move" one node onto another, even if they use different allocators. But does it really? Their ownership simply doesn't have anything to do with their sibling relationship, and you're forcing them to be tied together. Like, yeah, you can keep putting bandages on top of this, rub some alcohol on it, and giving it crutches to make it work, and I'm sure you'll eventually make it work, but the right thing to do is to just step back and realize the flaw is in the approach itself: some concerns are global across the nodes (like memory management), and some are local (data structure management), and hence it doesn't make sense to mix the two. (Oh, and did I point out that all of this means you'll have to find a different solution when the data structure is no longer linear to allow a destructor hack like that? The fact that the scope of the approach is limited by a property that really isn't all that relevant to the actual problem is another sign that it isn't the gift one.)
  - dbaupp 9y ago
    I am not advocating for it being a great way to implement a linked list, just using it as an example that can be easily understood in a throwaway comment. As an alternative: # Delete all the elements from node 'from' to (but not including) node 'to' erase(list, from, to): from.prev.next = to to.prev = from.prev while from and from != to: from = from.next list.allocator.free(from) # update 'tail' if necessary destroy(list): node = list.head while node: next = node.next list.allocator.free(node) node = next This code is also wrong. Calling erase(list, list.tail, list.head) or similar will create a loop, and then destroy will loop forever/read dangling pointers. This is also very close to correct (I believe 'destroy' looking for node == tail instead of node being null would avoid the loop), but isn't. Yes, it's easy to write a linked list, but it's also easy to screw up in subtle ways, and that line is thin. The safe subset of Rust restricts what is legal to be able to get some sort of control/understanding on pointer-soups, so that it can verify and validate that problems like the above don't turn into really bad problems. (The equivalent thing couldn't happen with vector-and-indices or arena-allocated nodes, and would result in the less dangerous[1] problem of an infinite loop/memory leak with Rc/Weak or garbage collection.) [1]: A denial of service is better than remote code execution (proof: the latter can be turned into the former).

pjmlp 9y ago

I think the C++ example is safer modeled like this class ListNode { std::unique_ptr<ListNode> next; std::weak_ptr<ListNode> prev; // some data or whatever };

dbaupp 9y ago
That doesn't work. std::weak_ptr is a reference counted pointer matched to std::shared_ptr; there's no concept of weak pointers (i.e. non-owning with dynamic checks) for std::unique_ptr, which corresponds almost exactly to Rust's Box.