cannot move out of borrowed content when unwrapping a member variable in a &mut self method

Question

I was trying to make a Disjoint-Set data structure in Rust. The relevant code is:

pub struct Set<'a, T: 'a> {
    rank: u32,
    value: T,
    parent: Option<&'a mut Set<'a, T>>,
}

impl<'a, T> Set<'a, T> {
    pub fn find(&'a mut self) -> &'a mut Set<'a, T> {
        match self.parent {
            None => self,
            Some(mut p) => {
                self.parent = Some(p.find());
                self.parent.unwrap()
            }
        }
    }
}

The errors I get are:

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:9:15
   |
9  |         match self.parent {
   |               ^^^^ cannot move out of borrowed content
10 |             None => self,
11 |             Some(mut p) => {
   |                  ----- hint: to prevent move, use `ref p` or `ref mut p`

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:13:17
   |
13 |                 self.parent.unwrap()
   |                 ^^^^ cannot move out of borrowed content

I'm not sure I understand the borrow checker fully, but I am using references to avoid taking ownership of structs themselves so that they can be pointed to and reassigned similar to how you would in other languages.

I can avoid these errors by removing the mut from the references in the struct, but then I cannot change the parent of each set because they are immutable.

I have read through similar questions such as:

• Rust: "cannot move out of `self` because it is borrowed" error
• Can't borrow File from &mut self (error msg: cannot move out of borrowed content)

These aren't helping me work out how to solve this issue. I have also tried restructuring the function find as well as the struct itself to use Rc<RefCell<Set>> and Box<Set> but I always end up at the same error.

What is this error and how do I fix it?

Answer 1

This match arm is going to take the enum variant components by value. Since your type isn't copyable, that would mean that the component would be moved out of the original place. This would make your original struct partially undefined - a big no-no in Rust.

To fix that, take a reference instead, as suggested by the compiler:

Some(ref mut p) =>

Next up, instead of storing the result in an Option and then immediately taking it back out, try to keep the reference in a variable, put it in the Option and return it:

let z = p.find();
self.parent = Some(z);
z

This leads to the core problem with the whole idea:

error[E0499]: cannot borrow `*z` as mutable more than once at a time
  --> src/main.rs:14:17
   |
13 |                 self.parent = Some(z);
   |                                    - first mutable borrow occurs here
14 |                 z
   |                 ^ second mutable borrow occurs here
15 |             }
   |             - first borrow ends here

You are trying to store a mutable reference and return it. This would mean that there would be multiple concurrent mutable references to the same item (also known as aliasing). Preventing this is another core tenet of Rust's safety systems, because then it's harder for the compiler to guarantee when and where things are being changed.

Check out this answer to see one way of working around that.

Answer 2

Use Option::take as match self.parent.take(), which is a basic idiom in such a context.

The self.parent.unwrap() expression will the cause an error as well; for that you need to work around the fact that unwrap consumes self; you use Option::as_mut to write self.parent.as_mut().unwrap() to have unwrap consume a reference instead.

The final code would be:

pub struct Set<'a, T: 'a> {
    rank: u32,
    value: T,
    parent: Option<&'a mut Set<'a, T>>,
}

impl<'a, T> Set<'a, T> {
    pub fn find(&'a mut self) -> &'a mut Set<'a, T> {
        match self.parent.take() {
            None => self,
            Some(p) => {
                self.parent = Some(p.find());
                self.parent.as_mut().unwrap()
            }
        }
    }
}