6 ms·
> I find a bit of solace in the fact that implementing a data structure like this in a non-garbage collected language without Rust is also quite tricky What? N
by mehrdadn 9y ago
> I find a bit of solace in the fact that implementing a data structure like this in a non-garbage collected language without Rust is also quite tricky
What? No it isn't. The entire problem here is incorrectly assuming that "A owns B" implies "A has a pointer to B". I don't know if this is a Rust-imposed constraint, but it certainly isn't a logically necessary one. Just do what C++ (and C#, etc.) do: the data structure (std::list, etc.) owns all the nodes, and the nodes merely reference each other. The nodes don't own their siblings. It makes sense and it doesn't get tricky.
- vvanders 9y ago> The entire problem here is incorrectly assuming that "A owns B" implies "A has a pointer to B". I don't know if this is a Rust-imposed constraint in some fashion, but it certainly isn't a necessary one. Rust has support for weak references[1] to support this exact use case. For 90% of uses cases A owns B tends to produce much cleaner architecture. Having ambiguous ownership is just a recipe for resource leaks and non-deterministic behavior. [1] https://doc.rust-lang.org/std/rc/struct.Weak.html https://doc.rust-lang.org/std/rc/struct.Weak.html
- mehrdadn 9y agoHmm... that doesn't make sense. Weak references are for refcounted values. There does not need to be any refcounting involved here at all.
- vvanders 9y agoYes but single owner and refcount of 1 are semantically the same. If you want to be strict about this just keep the Rc private to the implementations and only hand out Weak<T>.
- mehrdadn 9y agoSo you're suggesting we add a refcount to every value because it can be made to be semantically the same as not having one?
- vvanders 9y agoIf you want to stay in safe Rust, sure. If that's too much overhead feel free to drop down to unsafe and do it just like in C/C++. FWIW Rc is pretty lightweight. Arc is the heavier(and threadsafe) variant.
- deleted 9y ago[deleted]
- Retra 9y agoThere's no safe, general way to do shared ownership without ref counting or garbage collection. You can't expect Rust to provide one; it already provides ref counting and raw pointers, which is as good as any other Non-GC language does.
- foota 9y agoI think you mean "The entire problem here is incorrectly assuming that "A has a pointer to B" implies "A owns B"." Although perhaps I'm wrong.
- bfrog 9y agoSemantically thats what the Rust std library linked list does as well https://doc.rust-lang.org/std/collections/struct.LinkedList.html https://doc.rust-lang.org/std/collections/struct.LinkedList.... However that LinkedList implementation requires unsafe{} to be implemented. All unsafe really means is that the compiler isn't going to hold your hand, the usual memory ownership footgun is available at your discretion. unsafe shouldn't be this mythical thing you don't touch like people seem to think it is. If you need to escape the compilers very helpful guidance you can and should, but test thoroughly!
- mehrdadn 9y agoGoing on a tangent, but I honestly think 'unsafe' might suffer from a naming issue. It should've been called 'unchecked' or 'unverifiable' or something that says the code is merely not verified to be safe, not that it is actually unsafe.
- j1f4 9y agoThe word that I have seen in similar contexts is 'trusted', which I like and would have preferred -- the block has extra privileges and isn't machine verified. Some people tend to give 'trusted' an opposite reading when they first come across it, though.
- mehrdadn 9y agoOh yeah, 'trusted' would definitely give the opposite of the intended meaning! I had to read your comment twice just to get why you were calling it that.
- lmkg 9y agoThe problem with that word is it doesn't say who is doing the trusting, which is the crucial point. In fact, "trusted" can be used to describe both safe code and unsafe code. In the safe code, the programmer is trusting the compiler. In unsafe code, the compiler is trusting the programmer. Both code environments are "trusted," but the trust is being given to different parties.
- dbaupp 9y agoThe 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 agoFun 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 agoUsing 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.
- stochastic_monk 9y agoI find that evangelical Rustaceans often speak ill of C++ without knowing how one would solve a problem in C++, especially C++11/14/17. I’ve been told that “it takes a decade to grow a good C++ developer”. I think that’s an overestimate, having only written it for a few years, but it does take a lot of skill to write good C++, while Rust’s borrow-checker enforces safe practices.