Issues referencing and mutating id_tree Rust

Question

I'm at an impasse while using the id_tree crate. I'm using an id_tree to model the relationship between entities in my application. When deleting/adding/moving an element I would like to look up its position in the tree, then update the tree accordingly. I.e deleting an element removes that element from the tree. So I've created struct MyApp which has field tree: Tree<i32>.

When editing elements in my application I need to use functions like ancestors_id(). This creates an immutable borrow of my_app.tree. Then I need to mutate my_app.tree with information from that borrow. I.e. I need to find something in the tree, then I need to edit the tree. Doing so with a function like move_node() requires a mutable borrow of my_app.tree, resulting in an error when I've already created a immutable borrow of my_app.tree using a lookup function like ancestors_id(). I've looked over this answer to such an issue, which recommends using std::rc::Rc to make a cloneable reference, but doing so moves my_app.tree, limiting my ability to edit it.

Using .clone() on a id_tree::Tree<T> generates a new tree with different NodeId values, so I couldn't use those cloned values to reference Nodes in my_app.tree. If there's no way for me to clone the tree, then how could I get around needing to use both an immutable borrow and a mutable borrow to my_app.tree?

id_tree = "1.7.0"

The ancestor_ids and move_node functions from the id_tree docs:

pub fn ancestor_ids(
    &self,
    node_id: &NodeId
) -> Result<AncestorIds<T>, NodeIdError>

pub fn move_node(
    &mut self,
    node_id: &NodeId,
    behavior: MoveBehavior
) -> Result<(), NodeIdError>

use id_tree::*;
use id_tree::InsertBehavior::*;
use id_tree::MoveBehavior::*;
struct MyApp{
    pub tree: Tree<i32>
}

fn main() {


    //      0
    //     / 
    //    1   2
    //   / 
    //  3   4

    let mut my_app = MyApp{
        tree: TreeBuilder::new().with_node_capacity(5).build()
    };
    let root_id: NodeId = my_app.tree.insert(Node::new(0), AsRoot).unwrap();
    let child_id: NodeId = my_app.tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
    let node_2_id: NodeId = my_app.tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
    let node_3_id: NodeId = my_app.tree.insert(Node::new(3), UnderNode(&child_id)).unwrap();
    let node_4_id: NodeId = my_app.tree.insert(Node::new(4), UnderNode(&child_id)).unwrap();

    // let the_rc = std::rc::Rc::new(my_app.tree); 
    // let mut ancestor_ids = the_rc.ancestor_ids(&node_4_id).unwrap();
    //Err: creating rc moves the value
 
    
    let mut ancestor_ids = my_app.tree.ancestor_ids(&node_4_id).unwrap();
    //Err: creates a immutable borrow, which causes an error because move_node creates a mutable borrow
    //let mut ancestor_ids = my_app.tree.clone().ancestor_ids(&node_4_id).unwrap(); 
    //Err: cannot clone my_app.tree becuase clone() generates a new tree with different NodeId Values, causing move_node to panic


    let tx = my_app.tree.move_node(
        &node_4_id,
        ToParent(ancestor_ids.next().unwrap())
    );
}

question from:https://stackoverflow.com/questions/65894574/issues-referencing-and-mutating-id-tree-rust

Answer 1

You're using Rc the wrong way: you should put it directly inside MyApp, then clone it when needed:

struct MyApp{
    pub tree: Rc<Tree<i32>>
}

However this won't solve your problem because Rc does not allow you to have a mutable reference to its contents if there is another live reference to it. Quoting from the Rc::get_mut docs (emphasis mine):

Returns a mutable reference into the given Rc, if there are no other Rc or Weak pointers to the same allocation.

Returns None otherwise, because it is not safe to mutate a shared value.

There is no way in Rust to have a mutable and immutable reference simultaneously for the same value.

Instead you should collect your ancestor ids to get rid of the immutable references:

let ancestor_ids: Vec::<NodeId> = my_app.tree
    .ancestor_ids(&node_4_id)
    .unwrap()
    .cloned()
    .collect();

The call to cloned is here to clone each NodeId individually. Without cloned we would get a Vec::<&NodeId> with references into the tree, which would still prevent us from mutating the tree.