4 ms·

> As for cyclic data structures, one would often like to have a primitive which encapsulates a forward owning pointer and a backpointer tied to it, with the bac

> As for cyclic data structures, one would often like to have a primitive which encapsulates a forward owning pointer and a backpointer tied to it, with the backpointer unable to outlive the forward pointer. One can already do this with `&T` (for the backpointer) and `Box<T>` or `&mut T` (for the forward pointer). The hard part is letting you safely mutate something once the back reference has been added, without any runtime checks and with arbitrary data in the pointer. I don't believe what you've described addresses that issue, but maybe I'm missing something.

Animats 12y ago
My point is that it's possible to extend the Rust model to check this at compile time. The borrow checker has to understand backpointers. The owned object cannot outlive the owner, so a simple backpointer is safe in that sense. But ownership can change, and when it does, the backpointer must also change. The Rust ownership model can almost do this now. A move-type assignment to the forward pointer which causes a change in ownership would have to do a mutable borrow on the backpointer to get exclusive use, then change the backpointer to the new owner. That prevents a change to the backpointer while it's being used for something. The borrow checker would have to understand that those two pointers are tied together by an invariant. There would need to be syntax for back references, understood by initialization as well as moves. It's such a common case that it's worth the special handling. It would let you do trees and doubly-linked lists without reference counts. The Rust ownership model is very powerful. I was fooling around with something like this a decade ago as an improvement to C++, but all I expected to get out of it was the elimination of reference count updates when you passed an object to a function without giving the function permission to delete or keep the object. Rust pushes that model much harder, and it works. It can be pushed even further to make more common use cases compile-time checkable. This would cover more common idioms from C++. Another possible extension is lifetimes on objects allocated with "new". If you need to add something to a tree, you want the new objects to have the same lifetime as the tree. If you could specify a lifetime in "new", resulting in an object being allocated in an outer scope, that would cover the idiom where you call some "add to data structure" function and it creates objects to be added to the data structure. Currently in Rust, you have to create new objects from within the scope that owns the data structure, then call some function to install them in the data structure. The idea of creating an object in an outer scope seems strange, but when you create a closure, you're doing just that.
tomjakubowski 12y ago
> One can already do this with `&T` (for the backpointer) and `Box<T>` or `&mut T` (for the forward pointer). The hard part is letting you safely mutate something once the back reference has been added, without any runtime checks and with arbitrary data in the pointer. Can one? A &mut T and &T both pointing to the same memory and existing at the same time causes undefined behavior, and such a pairing could only be constructed via a compiler bug or (wrong) unsafe code.

Animats 12y ago

My point is that it's possible to extend the Rust model to check this at compile time. The borrow checker has to understand backpointers. The owned object cannot outlive the owner, so a simple backpointer is safe in that sense. But ownership can change, and when it does, the backpointer must also change. The Rust ownership model can almost do this now. A move-type assignment to the forward pointer which causes a change in ownership would have to do a mutable borrow on the backpointer to get exclusive use, then change the backpointer to the new owner. That prevents a change to the backpointer while it's being used for something. The borrow checker would have to understand that those two pointers are tied together by an invariant. There would need to be syntax for back references, understood by initialization as well as moves. It's such a common case that it's worth the special handling. It would let you do trees and doubly-linked lists without reference counts. The Rust ownership model is very powerful. I was fooling around with something like this a decade ago as an improvement to C++, but all I expected to get out of it was the elimination of reference count updates when you passed an object to a function without giving the function permission to delete or keep the object. Rust pushes that model much harder, and it works. It can be pushed even further to make more common use cases compile-time checkable. This would cover more common idioms from C++. Another possible extension is lifetimes on objects allocated with "new". If you need to add something to a tree, you want the new objects to have the same lifetime as the tree. If you could specify a lifetime in "new", resulting in an object being allocated in an outer scope, that would cover the idiom where you call some "add to data structure" function and it creates objects to be added to the data structure. Currently in Rust, you have to create new objects from within the scope that owns the data structure, then call some function to install them in the data structure. The idea of creating an object in an outer scope seems strange, but when you create a closure, you're doing just that.

tomjakubowski 12y ago

> One can already do this with `&T` (for the backpointer) and `Box<T>` or `&mut T` (for the forward pointer). The hard part is letting you safely mutate something once the back reference has been added, without any runtime checks and with arbitrary data in the pointer. Can one? A &mut T and &T both pointing to the same memory and existing at the same time causes undefined behavior, and such a pairing could only be constructed via a compiler bug or (wrong) unsafe code.