5 ms·
Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have
by Animats 7y ago
Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that.
If you have safe backpointers, most tree-type data structures with backpointers can be constructed. A nice feature to have.
- magicalhippo 7y agoAs a non-Ruster, any particular reason they didn't include this? A lot of the code I've done over the years involve graphs, which have a lot of circular pointer and/or backpointers. I find it kinda weird they'd make such a common thing a PITA in a new language.
- habitue 7y agoIt might actually be possible now with Pin. Could anyone actually knowledgeable about this comment?
- renox 7y agoI don't know much about Rust (and nearly nothing about Pin) but if this was true, don't you think someone would already have written a library providing doubly linked list without using unsafe?
- eximius 7y agoRust has a concept of ownership and borrowing. (I think) everything is fine when you just have immutable references everywhere. But as soon as you start taking mutable references (of which only one can exist at a time) or ownership (stronger than mutable references), then cycles break things. You can get around it with Interior Mutability, it's just slightly more verbose. Also, it isn't really that they made an easy thing hard. Properly maintaining the invariants with cyclical references is hard and unsafe. Rust exposes that difficulty in a very literal way
- wruza 7y agoComplete blind guess here, but maybe a safest language could “borrow” from accounting systems. Basic idea is that you don’t need to validate every step as long as the outcome of a specific set of operations is atomically valid. Some SQL have it, like checks on foreign keys and column check-exprs on commit, not on insert (that’s how you make back-refs by {insert; insert}, and not {insert; insert null; update}, which is similar to dl-lists and graph problem). Or you check that sums on both sides match, but not before “committing” ops into a book. Half of subj code uses sort of atomics (mem-replace), but they are too small to not leak complexity to “userland”. If they just replaced that with transaction { ...shuffle values... } and checked at “}”, it would be much easier to reason about when programming, instead of building microbridges everywhere. If code is not long and/or threaded, analyzer could calculate “balance” in a reasonable time just by looking at careless source code. >Properly maintaining the invariants with cyclical references is hard and unsafe. Rust exposes that difficulty in a very literal way But a solution to this problem is articulated easily: adjust corresponding nodes if this one goes away. It could help with that instead of just exposing, like tagging such types as heavily linked and demand/derive an [unoptimal] algorithm that would ensure correctness or define “corresponding” and “adjust” at least. ps. I’m not familiar with rust, nor with discussions on it, maybe that was already discussed and refused or proven unreasonable at early design stages.
- eximius 7y agoThat's kind of how unsafe rust works, except that the compiler doesn't check that you maintained the variants. Your unsafe code is expected to conform such that safe code interacting with it is safe. > But a solution to this problem is articulated easily: adjust corresponding nodes if this one goes away. It could help with that instead of just exposing, Articulating things easily doesn't mean they are easy. Now every value needs a backreference to every value that holds it and, during its destructor (which isn't guaranteed to run), it has to make those held references invalid? I know just enough to know how difficult the problem is, in the general case. The folks thinking about these problems for their day jobs have looked into a lot of simple solutions and they fall apart in cases that are too common or too valuable to no support.
- dodobirdlord 7y agoRust's ownership rules aren't for the purpose of making the user's life hard, they are the least restrictive system that could be devised that allow the compiler to uphold Rust's safety guarantees. It was not too long ago that it was common knowledge that a programming language either has a garbage collector or has manual memory management, or possible both. Safe Rust has neither, but not without the effect of making awkward certain kinds of programming that are fundamentally difficult to make safe. The Rust question to ask here is: Do you really need pointers, specifically? Or would some other reference mechanism work? You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a list of pointers. Or you could give all of your nodes unique keys and keep them in a table, and have them hold references to each other by key. The compiler will not try to prove the correctness of your graph algorithm, and in the event of programmer error that leads to dangling references your program will have to handle the scenario of following an index or a key and not finding a value, so bugs will not introduce memory unsafety. There's also ongoing work on memory arenas in the nightly compiler, and I believe some libraries. Putting a graph into an arena is a good way to appease the compiler, because the entire arena will be freed at the same time, ensuring that hanging pointers will never exist between graph nodes.
- dmitrygr 7y ago> You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a list of pointers Rust practitioners keep proposing this solution. It is like you have never heard of caches or do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics" This solution will be SIGNIFICANTLY slower on any modern CPU. By a wide margin! Since you'll keep having to wait for main memory as the cache prefetchers have no idea about this insane scheme and will not prefetch the data for you. They will for actual pointers.
- aw1621107 7y ago> It is like you have never heard of caches But isn’t that part of the point of putting nodes into an array? So the nodes are guaranteed to sit next to each other in memory, and so are quite likely to be in cache? > do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics" Doesn’t array indexing reduce down to pointer chasing anyways? Or are you saying that the prefetchers can’t see through “nested” array accesses (e.g. nodes[nodes[i].out[0]].data vs node.out[0].data)?
- lrem 7y agoIn your graph, the nodes are not owning each other, are they?
- magicalhippo 7y agoNo, but they do point to each other. For example, each node can have an array of all the edges, and each edge has two pointers to each node it connects. Via this you can walk around cycles for example. And typically these can change when nodes are inserted or removed.
- Animats 7y agoThis is an enforced invariant. This results in proposals that it should be done by adding a system for general invariants and design by contract features. Those are then rejected as too complicated and something for the far future. So, the usual answer is "use unsafe code." What could possibly go wrong?
- moth-fuzz 7y agoHistorically, the classic graph structures are adjacency lists and adjacency matrices. Those are quite easy to represent in Rust if you use indices instead of pointers. Node/Pointer type graph structures aren't particularly efficient anyway, even in C or C++.
- dpbriggs 7y agoYou can somewhat emulate this with Weak pointers: https://doc.rust-lang.org/std/rc/struct.Weak.html https://doc.rust-lang.org/std/rc/struct.Weak.html They don't count against ownership, but do bring some extra headaches of their own (referencing counting overhead, etc).
- dan-robertson 7y agoI would guess backpointers are tricky because they are types that need to care about the record field they are put inside in some other type. I would guess that it would be a lot of work to fit something like that into the language and make sure it’s correct. And it would surely become harder if backpointers were allowed between objects of different types. One way one can implement a circular doubly linked list is to confine all pointer manipulation to precisely two operations: 1. Creation of a node x such that x.next = x = x.prev 2. Given two double-links A <-> B (ie A.next = B, B.prev = A) and C <-> D, swizzle the pointers so A <-> D and C <-> B. Note that if the links are equal then the operation is trivial. Note also that these links must be in the direction of the circular list (ie if you have a circular list A<->B<->C, you can’t “reverse” the A<->B link to give this operation a B<->A link) One way to think of this is that every finite permutation (ie disjoint product of cycles ie set of disjoint circular linked lists, but also as permutations act on themselves as a way of rearranging the links to transform sets of disjoint doubly linked lists to other sets of doubly linked lists) is a product of transpositions (which correspond precisely to operation 2; and operation 1 corresponds to the identity element which may be thought of as a product of every cycle of size 1 rather than a product of 0 cycles). Suppose you construct the type of the “double pointer”. You use some magic or unsafe code to make sure that the creation operation follows these rules (I don’t really know any rust but I think this rule could be enforced with some careful helper functions and linear types. But rust doesn’t have linear types so maybe there isn’t a type system way to enforce that creation is done correctly or even that it is validated at runtime). But now what happens to the ownership with the magic swizzle operation? If the links are from different lists then it is splicing them together and the nodes should (I guess) now have the same owner/lifetime. If the links come from the same list then the operation splices them into two separate lists, so I guess the ownership should be split. The problem is that you don’t really have a way to do that because there isn’t really a way to know or specify at compile time whether two nodes are definitely in the same list or definitely not in the same list. (I guess you could enforce that every element has a pointer to some “owning object” for the list it’s in but now all your operations that were constant time are linear time). Adding or removing elements is a special case of these operations. It isn’t sufficient to always treat the result of the swizzle operation as if the lists have become the same list because if they have separated then you wouldn’t know to delete half of the list. Maybe the reply is just that somehow the typesystem should allow backpointers but somehow not this swizzling operation. But I don’t see how that helps with the ownership problems of doubly linked lists. Maybe the answer is that rust should get (or already has) some way to always know whether two things “definitely or definitely don’t alias when you include the transitive closure of all their pointers; but actually only some of their pointers,” but that sounds hard to define and even harder to have the type checker able to resolve.
- josteink 7y ago> I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Or you could simply give it a new type/semantic: owner. You could even use a familiar unix-shorthand for it: ~. Thus Node<T> will have a Parent: ~Node<T>, which you can pass by ~self. And graphs would suddenly be nice to work with. > Rust lacks that. I can’t be the only one who finds that ironic? And I say that as someone who likes rust.
- steveklabnik 7y agoIt is not particularly ironic; there's no actual design here. It's easy to say that a feature should exist (and your parent has said this, about this, repeatedly) but it's much harder to make sure that it's something that has the correct semantics (and your parent has never actually produced this, even though they've been asked, repeatedly.). (See the sibling comment by dan-robinson for just some of the issues here)
- josteink 7y agoThe absolute simplest semantic I can come up with here (too simple?) would be for a struct containing a non-null owner-pointer to be bound by its owner’s ownership/lifetime-scope. For most commonly used graph-types this should lead to pretty simple one-directional ownership chains which should be doable (although probably not trivial) for a compiler to enforce.