I 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.