How to handle "temporary value dropped" error when adapting Box-based tree structure to Rc+RefCell?

Question

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<_>>?

score 0 · Accepted Answer · answered Feb 02 '22 at 15:00

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 => &current_node.left,
            Ordering::Equal => return false,
            Ordering::Greater => &current_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
}

How is this the accepted answer if the code doesn't actually work? — Danilo Souza Morães, Dec 27 '22 at 18:17

score 0 · Answer 2 · answered Dec 28 '22 at 16:42

Although the original answer is correct, the code in the example don't work because it forgets to add the root node.

Those are two alternatives that solves this problem:

    pub fn insert(&mut self, value: T) -> bool {
        //if no root, just create one
        let mut node = if let Some(root) = &self.root {
            Rc::clone(root)
        } else {
            self.root = Some(Rc::new(RefCell::new(Node {
                value,
                left: None,
                right: None,
            })));
            return true;
        };

        loop {
            let current_node = Rc::clone(&node);
            let mut current_node = RefCell::borrow_mut(&current_node);
            let cmp = current_node.value.cmp(&value);
            let next_node = match cmp {
                Ordering::Less => &mut current_node.left,
                Ordering::Equal => return false,
                Ordering::Greater => &mut current_node.right,
            };
            if let Some(next_node) = next_node {
                node = Rc::clone(next_node);
            } else {
                *next_node = Some(Rc::new(RefCell::new(Node {
                    value,
                    left: None,
                    right: None,
                })));

                println!("node: {:?}", node);
                return true;
            }
        }
    }

Recursive solution:

impl<T: Ord + fmt::Debug> Tree<T> {
    fn new() -> Self {
        Self { root: None }
    }

    pub fn insert(&mut self, value: T) -> bool {
        //if no root, just create one
        if let Some(root) = &self.root {
            let mut root = RefCell::borrow_mut(&root);
            root.insert(value)
        } else {
            self.root = Some(Rc::new(RefCell::new(Node {
                value,
                left: None,
                right: None,
            })));
            true
        }
    }
}

impl<T: Ord + fmt::Debug> Node<T> {
    fn insert(&mut self, value: T) -> bool {
        let node = match self.value.cmp(&value) {
            Ordering::Less => &mut self.left,
            Ordering::Equal => return false,
            Ordering::Greater => &mut self.right,
        };
        //if the node is empty, add to it, otherwise check deeper
        if let Some(node) = node {
            let mut node = RefCell::borrow_mut(node);
            node.insert(value)
        } else {
            *node = Some(Rc::new(RefCell::new(Node {
                value,
                left: None,
                right: None,
            })));
            println!("node: {:?}", node);
            true
        }
    }
}

How to handle "temporary value dropped" error when adapting Box-based tree structure to Rc+RefCell?

2 Answers2

Linked

Related