I've created a tree with a type definition similar to:
#[derive(Debug, Clone)]
pub(crate) struct TreeBox<T> {
root: Option<Box<NodeBox<T>>>,
}
#[derive(Debug, Clone)]
struct NodeBox<T> {
value: T,
left: Option<Box<NodeBox<T>>>,
right: Option<Box<NodeBox<T>>>,
}
impl<T: Ord> TreeBox<T> {
fn new() -> Self {
Self { root: None }
}
pub fn insert(&mut self, value: T) -> bool {
let mut node = &mut self.root;
while let Option::Some(current_node) = node {
match current_node.value.cmp(&value) {
Ordering::Less => node = &mut current_node.right,
Ordering::Equal => return false,
Ordering::Greater => node = &mut current_node.left,
}
}
*node = Option::Some(Box::new(NodeBox {
value,
left: Option::None,
right: Option::None,
}));
return true;
}
}
This works perfectly and I'm very happy with the implementation. However I want to store a reference from each node to it's parent. After some research I found a section in the Rust Book describing an implementation using RefCell
and Weak
structs.
With this knowledge my plan was to update the example from above. My idea was that I could just substitute Box<...>
with Rc<RefCell<..>>
. My thinking was that these types are very similar in that they both store a reference to some data structure, only difference is that there can be multiple Rc<RefCell<..>>
's pointing to that data structure. I changed my implementation to:
#[derive(Debug, Clone)]
pub(crate) struct Tree<T> {
root: Option<Rc<RefCell<Node<T>>>>,
}
#[derive(Debug, Clone)]
struct Node<T> {
value: T,
left: Option<Rc<RefCell<Node<T>>>>,
right: Option<Rc<RefCell<Node<T>>>>,
}
impl<T: Ord> Tree<T> {
fn new() -> Self {
Self { root: None }
}
pub fn insert(&mut self, value: T) -> bool {
let mut node = &mut self.root;
while let Option::Some(current_node) = node {
let cmp = current_node.borrow().value.cmp(&value);
match cmp {
Ordering::Less => node = &mut current_node.borrow_mut().right,
Ordering::Equal => return false,
Ordering::Greater => node = &mut current_node.borrow_mut().left,
};
}
*node = Option::Some(Rc::new(RefCell::new(Node {
value,
left: Option::None,
right: Option::None,
})));
return true;
}
}
However this updated example doesn't compile:
error[E0716]: temporary value dropped while borrowed
--> src/lib.rs:28:47
|
28 | Ordering::Less => node = &mut current_node.borrow_mut().right,
| ^^^^^^^^^^^^^^^^^^^^^^^^^ -
| | |
| | temporary value is freed at the end of this statement
| | ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `RefMut<'_, Node<T>>`
| creates a temporary which is freed while still in use
| a temporary with access to the borrow is created here ...
|
= note: consider using a `let` binding to create a longer lived value
Both examples are available on the playground.
Is my example wrong, or is there something I still don't quite understand about Rc<RefCell<_>>
?
So, you have a few problems. The primary one is that you're trying to take references to an Option
that contains a value whose lifetime is short because it's tied to the borrow()
on RefCell
. (You're also trying to borrow_mut
while a borrow
is in place, which will panic.) Thankfully, Rc
makes it cheap and easy to take ownership of references to Rc
(that's the whole point), so this problem can be solved by storing Option
, not &Option
, and liberally cloning the contained Rc
. We use Option::as_ref
to convert an &Option<Rc<_>>
into an Option<&Rc<_>>
, which then gets turned into a Option<Rc<_>>
by mapping Rc::clone
over it.
pub fn insert(&mut self, value: T) -> bool {
let mut node = self.root.as_ref().map(Rc::clone);
while let Some(current_node) = node {
let current_node = current_node.borrow();
let cmp = current_node.value.cmp(&value);
let new_node = match cmp {
Ordering::Less => ¤t_node.left,
Ordering::Equal => return false,
Ordering::Greater => ¤t_node.right,
};
node = new_node.as_ref().map(Rc::clone);
}
let node = &mut node;
*node = Some(Rc::new(RefCell::new(Node {
value,
left: None,
right: None,
})));
true
}