In the Rust book there is the following implementation of a tree Node:
struct Node {
value: RefCell<i32>,
parent: RefCell<Weak<Node>>,
children: RefCell<Vec<Rc<Node>>>,
}
(I changed i32
to RefCell<i32>
so I am able to mutate this as well).
One can then use a variable current_node: Weak<Node>
to move up and down the tree.
This works fine, but conceptually I don't understand why one should need to use Rc
. If I understand correctly, Rc
allows us to have data with multiple owners. In a tree, each node has exactly one owner, namely its parent node (or some variable we can name "root" in the case of the root node).
I tried to replace this with
struct Node<'a> {
value: RefCell<i32>,
parent: RefCell<Option<&'a Node<'a>>>,
children: RefCell<Vec<Box<Node<'a>>>>,
}
Then we would use current_node: &Node
.
Now this doesn't work, because it's not possible, e.g., to change current_node
from a node to one of its children.
Simplifying things, the problem comes down to the fact that
fn test<T>(v: &RefCell<Box<T>>) -> &T{
v.borrow().as_ref()
}
does not compile:
cannot return reference to temporary value; returns a reference to data owned by the current function.
The analogous
fn test2<T>(v: Weak<RefCell<Rc<T>>>) -> Weak<T> {
Rc::downgrade(&v.upgrade().unwrap().borrow())
}
does compile. So why can't I return &T
from &RefCell<Box<T>>
?
(I also tried using Ref<Node>
instead of &Node
as the type of current_node
, but then there are other issues).
Or more to the point, am I wrong in thinking that conceptually trees should not require multiple ownership?