A classic problem in Rust is data structures with backlinks. A tree where nodes have backlinks to their owner is tough. Rc/Weak works, but means extra run-time work and the possibility of a runtime panic. Ownership via "handles" which are keys to a HashMap or indices into a vector are really manual pointer manipulation. That's where we are now.
What's often wanted is single ownership with safe backlinks checked at compile time. Is that even possible? I think it is for the immutable case, but I'm not sure it could work for mutable.
So, a proposal for discussion:
A tree, where each struct has a Vec of child objects, is standard Rust. That works fine. Now, suppose we had language support for backlinks, like this:
#[derive(Owner)] // new feature
/// Node of a tree
struct Node {
name: String,
children: Vec<Node>
}
impl Node {
/// Print the ownership chain back to the root
pub fn print_ownership_chain(&self) {
println!("Node name: {}", self.name);
// get_owner is generated by the derive above.
while let Some(parent) = self.get_owner() {
parent.print_ownership_chain();
}
}
}
So, the idea is that #[derive(Owner)] does this:
The structure gets a hidden field which contains
Option<BackReference<Node>>
and the contents of that field are automatically maintained to point back at the owner, if it's another Node, or None, otherwise. When ownership transfers, that field must change. The compiler knows when an object is changing ownership. So that's an implementation problem, but it's not inherently unsafe.
Then there's get_owner(), generated by the derive. Signature:
fn get_owner(&Self) -> Option<&Self>
Deciding, at compile time, when it's allowed to call get_owner is the hard part. It's safe when no one has mutable access to the parent node. Can that be determined at compile time? Is that within the capabilities of the borrow checker model?
This is doing at compile time what people do at run time with Rc and Weak and .upgrade(). So it ought to be possible within the ownership model.
Is this theoretically possible? (And could it be extended to get_owner_mut(), returning a mutable reference?)