Borrow checker on parent-child relation

Question

I have the code below producing the error message marked in its comments. I think I understand the message: I want to borrow parent two times: once for finding its child, and once as an argument to the child (and the mutable/immutable words in the error are not relevant). I have to prove that Child doesn't disappear when it modifies Parent. But I don't know how to do this. I could Rc<Child> everything but that seams wasteful, so I hope adding some lifetimes would do the trick.

struct Parent {
    used: i32,
    child: Child,
}

struct Child {
    dummy: i32,
}

impl Child { 
    fn use_parent(&mut self, parent: &mut Parent) {
        // use both child and parent
        parent.used += self.dummy;
        self.dummy += 1;
    }
}
fn main() {
    let parent = Parent {
        used: 0,
        child: Child {
            dummy: 1
        }
    };
    //Error: cannot borrow immutable local variable `parent` as mutable
    parent.child.use_parent(&mut parent);
}

Answer 1

You are getting the error message for a different reason. You have a non-mutable variable parent and are trying to create a &mut to it. Fixing that you get

let mut parent = Parent {
    used: 0,
    child: Child {
        dummy: 1
    }
};
parent.child.use_parent(&mut parent);

and the corresponding error

<anon>:31:34: 31:40 error: cannot borrow `parent` as mutable more than once at a time
<anon>:31     parent.child.use_parent(&mut parent);
                                           ^~~~~~
<anon>:31:5: 31:17 note: previous borrow of `parent.child` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `parent.child` until the borrow ends
<anon>:31     parent.child.use_parent(&mut parent);
              ^~~~~~~~~~~~
<anon>:31:41: 31:41 note: previous borrow ends here
<anon>:31     parent.child.use_parent(&mut parent);
                                                 ^

---

You almost drew the right conclusion.

I have to prove that Child doesn't disappear when it modifies Parent

Not quite. You have to prove that you will never have two &mut or one &mut and a & to the child. If you had a &mut to the parent you could use it to get a &mut to the child. Therefor, if you had a &mut to the parent and a &mut to the child, you could get two &mut to the child.

---

The only solution I see is to move the use function to the Parent type and access the child through self.

impl Parent { 
    fn use_parent(&mut self) {
        // use both child and parent
        self.used += self.child.dummy;
        self.child.dummy += 1;
    }
}

---

Addressing your comment:

Unfortunately, the solution applies to this simplified problem, but not to my actual problem. Parent has a vector of children, which might have deeple nested grand children. I can't just say self.child

Since you shouldn't modify your vector (and can't, Rust protects you), because that would invalidate the reference to the child, you can pass those parts to the function that you need, but none of the parts that are direct parents of the child.

impl Child { 
    fn use_parent(&mut self, used: &mut i32) {
        // use both child and parent
        *used += self.dummy;
        self.dummy += 1;
    }
}

fn main() {
    let mut parent = Parent {
        used: 0,
        child: Child {
            dummy: 1
        }
    };
    // although both point to elements of the same structure
    // it is guaranteed at compile-time that they point to
    // non-overlapping parts
    let child = &mut parent.child;
    let used = &mut parent.used;
    child.use_parent(used);
}

unfortunatly i don't see a way to prove that use_parent's parameters point to parts of the same Parent object. Maybe that could be done with lifetimes, I'm not sure, but I would be immensly interested in that. Note: Rc has the same issue.

Answer 2

and the mutable/immutable words in the error are not relevant

I'm not sure why you think this. Mutability is very important in Rust! For example, while you are allowed multiple references to immutable data at the same time, you are only allowed to have a single reference to mutable data at a time.

First, you need to fix the mutability of parent:

let mut parent = // ...

Then, you will get an error from the line:

parent.child.use_parent(&mut parent);

When you run this line, you are implicitly mutably borrowing parent and child. This is done so that you can call use_parent, which requires a &mut self.

However, you are also trying to get a second mutable reference as the argument! This is a no-no, because if you were allowed to have multiple aliasing mutable references, the compiler wouldn't be able to track it and make sure that you don't break the memory-safety guarantees.

Suppose I remove the line self.dummy+=1; so there is only 1 mutable alias - can I get this to work?

Let's look at some variations of the function signature

fn use_parent(&self, parent: &mut Parent)
// cannot borrow `parent` as mutable because `parent.child` is also borrowed as immutable

fn use_parent(&mut self, parent: &Parent)
// cannot borrow `parent` as immutable because `parent.child` is also borrowed as mutable

fn use_parent(&self, parent: &Parent)
// OK

As I mentioned earlier, if you have a mutable reference to something, you aren't allowed to have any other references to that same thing (mutable or not).

Also, note that it doesn't matter what the body of the method is! Rust only checks the signature of a called function to verify if it's safe to borrow something.

So how do you try to solve your problem? Ultimately, you are trying to do something that is very difficult for the compiler to prove safe. You want a graph of mutable links. I'd highly suggest reading the module documentation for Rc which has an example of exactly this parent-child relationship.