With &mut self, why can't this method move and replace a field's value?

I'm trying to implement a binary search tree. The parent struct, BinSearchTree, has a pointer to a root node:

pub struct BinSearchTree {
    root: Option<Box<Node>>,
    size: u32,
}

Each node holds a value (currently u32 are supported; I'll make it generic later) and two pointers to its branches:

struct Node {
    value: u32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

Because dropping a value can cause the tree to change, my drop_value method, called on a Node, takes the Node as a moved value and returns a new Box pointing to itself, or to one of its children, which the parent Node uses to replace the moved value. Within Node, the method has this signature and it works:

pub fn drop_value(mut self, value: u32) -> (Result<(),TreeError>, Option<Box<Node>>) {

Note that it consumes itself (mut self).

My problem is at the root struct. BinSearchTree::drop_value isn't supposed to return a new BinSearchTree, just replace the field root. So the signature uses &mut self:

pub fn drop_value(&mut self, value: u32) -> Result<(),TreeError> {
    match self.root {
        None => {
            self.root = None; // not my real code
            return Err(TreeError::ValueNotFound);
        },
        Some(child) => {
            self.root = Some(child); // not my real code
            return Ok(());
        },
    }
}

Here's what I don't understand: I get an error on the line match self.root { that says "cannot move out of self.root as enum variant Some which is behind a mutable reference". For some reason, in the Some branch of the match, I can't replace the root with a new value. (Note that I've shortened the code; in the real program I call drop_value on the child and use the result. Nevertheless I get the same compile error with this shortened version.) It works if I change the signature to use mut self but I don't want to do that. Why can't I replace the root?

Why can't I replace the root?

The way to think about the problem here is: what would happen if your program performed

match self.root {
    Some(child) => { 
        ...

and then did not assign a new value to self.root? In that case, since the Some value with its Box<Node> has been moved out, the place pointed to by the mutable reference self will be in the de-initialized state, or moved-out-of. It must not be read. But, code that runs after drop_value() returns (or panics) is in fact free to read the place. This would lead to undefined behavior (e.g. double free of the Box), so it is not allowed.

In your case, you do assign a new value to self.root immediately, but the analysis the compiler performs does not care about that (and in many cases other than this one, you have the problem that code between the move out and the assignment could panic).

The solution to this problem is to leave a placeholder value in place of the value you moved out. For Options, this is most readily done by using Option::take(), which will leave None in place:

match self.root.take() {

For types other than Option, you can use std::mem::take() or std::mem::replace().