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:

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?

This is an exact duplicate because both issues have to do with the fact that unwrap consumes the Option. — Shepmaster
@Shepmaster I tried doing that, but then I get an error telling me I cannot assign to self.parent because it was already borrowed. And using as_mut() on the second error makes it so that I am returning a mutable reference to a mutable reference to the struct which didn't seem to work either. Even trying to spread this function out to take each part in step didn't seem to fix it. — mcdonalda1993
You may also be interested in Hand-over-hand locking with Rust where someone was also trying to implement union-find / disjoint-set. — Shepmaster

Shepmaster Shepmaster · Accepted Answer · 2015-01-28T14:50:00

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.

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

2 Answers