Can I move from &mut self to &self within the same function?

user_2606953 0
Viewed 211

I'm trying to learn a bit of Rust through a toy application, which involves a tree data structure that is filled dynamically by querying an external source. In the beginning, only the root node is present. The tree structure provides a method get_children(id) that returns a [u32] of the IDs of all the node's children — either this data is already known, or the external source is queried and all the nodes are inserted into the tree.

I'm running into the following problem with the borrow checker that I can't seem to figure out:

struct Node {
    id: u32,
    value: u64, // in my use case, this type is much larger and should not be copied
    children: Option<Vec<u32>>,
}

struct Tree {
    nodes: std::collections::HashMap<u32, Node>,
}

impl Tree {
    fn get_children(&mut self, id: u32) -> Option<&[u32]> {
        // This will perform external queries and add new nodes to the tree
        None
    }

    fn first_even_child(&mut self, id: u32) -> Option<u32> {
        let children = self.get_children(id)?;
        let result = children.iter().find(|&id| self.nodes.get(id).unwrap().value % 2 == 0)?;
        Some(*result)
    }
}

Which results in:

error[E0502]: cannot borrow `self.nodes` as immutable because it is also borrowed as mutable
  --> src/lib.rs:19:43
   |
18 |         let children = self.get_children(id)?;
   |                        ---- mutable borrow occurs here
19 |         let result = children.iter().find(|&id| self.nodes.get(id).unwrap().value % 2 == 0)?;
   |                                      ---- ^^^^^ ---------- second borrow occurs due to use of `self.nodes` in closure
   |                                      |    |
   |                                      |    immutable borrow occurs here
   |                                      mutable borrow later used by call

Since get_children might insert nodes into the tree, we need a &mut self reference. However, the way I see it, after the value of children is known, self no longer needs to be borrowed mutably. Why does this not work, and how would I fix it?

EDIT -- my workaround

After Chayim Friedman's answer, I decided against returning Self. I mostly ran into the above problem when first calling get_children to get a list of IDs and then using nodes.get() to obtain the corresponding Node. Instead, I refactored to provide the following functions:

impl Tree {
    fn load_children(&mut self, id: u32) {
        // If not present yet, perform queries to add children to the tree
    }

    fn iter_children(&self, id: u32) -> Option<IterChildren> {
        // Provides an iterator over the children of node `id`
    }
}
borrow-checker rust reference
1 Answers

Downgrading a mutable reference into a shared reference produces a reference that should be kept unique. This is necessary for e.g. Cell::from_mut(), which has the following signature:

pub fn from_mut(t: &mut T) -> &Cell<T>

This method relies on the uniqueness guarantee of &mut T to ensure no references to T are kept directly, only via Cell. If downgrading the reference would mean the unqiueness could have been violated, this method would be unsound, because the value inside the Cell could have been changed by another shared references (via interior mutability).

For more about this see Common Rust Lifetime Misconceptions: downgrading mut refs to shared refs is safe.

To solve this you need to get both shared references from the same shared reference that was created from the mutable reference. You can, for example, also return &Self from get_children():

fn get_children(&mut self, id: u32) -> Option<(&Self, &[u32])> {
    // This will perform external queries and add new nodes to the tree
    Some((self, &[]))
}

fn first_even_child(&mut self, id: u32) -> Option<u32> {
    let (this, children) = self.get_children(id)?;
    let result = children.iter().find(|&id| this.nodes.get(id).unwrap().value % 2 == 0)?;
    Some(*result)
}
user_78843050
Related