Cannot borrow as mutable, getting a mutable reference from a borrowed value

Question

I was following this other post: Understanding Rust `Rc<RefCell<_>>` where op tried implementing a tree with Box and was successful in doing it but then tried implementing it with Rc and RefCell and found issues. The accepted answer compiles but doesn't work because it doesn't add nodes to the root. I tried updating the accepted answer a bit to try and get it to work but wasn't able to. Basically I'm trying to get mutable references in the loop and I can't because I borroed an immutable reference. But then if a borrow_mut() I get that value is a private field, so I'm assuming I can't access any properties of the contained value if it is a mutable reference?

What should I do to get this code to work?

use std::borrow::BorrowMut;
use std::cell::RefCell;
use std::cmp::Ordering;
use std::rc::Rc;
use std::fmt;

#[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;
    }
}

#[derive(Debug, Clone)]
pub(crate) struct Tree<T> {
    root: Option<Rc<RefCell<Node<T>>>>,
}

#[derive(Debug, Clone, PartialEq)]
struct Node<T> {
    value: T,
    left: Option<Rc<RefCell<Node<T>>>>,
    right: Option<Rc<RefCell<Node<T>>>>,
}

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

    pub fn insert(&mut self, value: T) -> bool {
        let mut node = &mut self.root;

        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 => &mut current_node.left,
                Ordering::Equal => return false,
                Ordering::Greater => &mut current_node.right,
            };
            node = new_node;
        }

        // let mut node = &mut node;
        *node = Some(Rc::new(RefCell::new(Node {
            value,
            left: None,
            right: None,
        })));

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

}

fn main() {

    let mut tree_box = TreeBox::new();
    tree_box.insert(1);
    tree_box.insert(2);
    tree_box.insert(3);

    let mut tree = Tree::new();
    tree.insert(1);
    tree.insert(2);
    tree.insert(3);

    println!("TreeBox: {:?}", tree_box);
    println!("Tree: {:?}", tree);
}

Answer 1

The accepted answer compiles but doesn't work because it doesn't add nodes to the root.

You are right, and fixing the original solution, here a version that add the root node correctly:

    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;
            }
        }
    }

Basically I'm trying to get mutable references in the loop and I can't because I borroed an immutable reference.

The problem is slightly different. what happens is that you can't walk this Rc<RefCell> tree, at least not interactively like this, because the "borrow" of such structures need to be keep while you are working with it. And your implementation releases the "borrow" after each loop.

But then if a borrow_mut() I get that value is a private field, so I'm assuming I can't access any properties of the contained value if it is a mutable reference?

Not really, what is happening here is that you are not calling the function RefCell::borrow_mut that returns a RefMut<Node>, you are in fact calling <Rc as BorrowMut>::borrow_mut that returns &mut RefMut<...>. And by accessing the value you are trying the access the private field value from RefCell, not Node.

Notice that in my implementation I explicitly called RefCell::borrow_mut, that fixes this issue.