Why does a function that accepts a Box complain of a value being moved when a function that accepts self works?

Question

I have the following code which compiles:

pub mod Btree {
    pub struct node {
        pub id: u32,
        pub red: bool,
        pub left: Option<Box<node>>,
        pub right: Option<Box<node>>,
    }

    impl<'a> node {
        pub fn insert(mut node_: Option<Box<node>>, id: u32) -> Option<Box<node>> {
            match node_ {
                None => Some(Box::new(node {
                    id: id,
                    red: true,
                    left: None,
                    right: None,
                })),
                Some(x) => x.insert_(id),
            }
        }

        pub fn insert_(mut self, id: u32) -> Option<Box<node>> {
            self.left = node::insert(self.left, id);
            Some(Box::new(self))
        }
    }
}

When I change insert_() to work with a Box<node> instead:

pub mod Btree {
    pub struct node {
        pub id: u32,
        pub red: bool,
        pub left: Option<Box<node>>,
        pub right: Option<Box<node>>,
    }

    impl<'a> node {
        pub fn insert(mut node_: Option<Box<node>>, id: u32) -> Option<Box<node>> {
            match node_ {
                None => Some(Box::new(node {
                    id: id,
                    red: true,
                    left: None,
                    right: None,
                })),
                Some(x) => node::insert_(x, id),
            }
        }

        pub fn insert_(mut node_: Box<node>, id: u32) -> Option<Box<node>> {
            node_.left = node::insert(node_.left, id);
            Some(node_)
        }
    }
}

I get:

error[E0382]: use of partially moved value: `node_`
  --> src/main.rs:23:13
   |
23 |             node_.left = node::insert(node_.left, id);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^----------^^^^^
   |             |                         |
   |             |                         value moved here
   |             value used here after move
   |
   = note: move occurs because `node_.left` has type `std::option::Option<std::boxed::Box<Btree::node>>`, which does not implement the `Copy` trait

I don't understand what that is. The code is very similar and in both cases there is a move.

Answer 1

You can only destructure a struct (move non-Copy elements out of it) if you have the struct itself in hand. Having a pointer to the struct on the heap is not sufficient, even if it's an owning pointer (e.g. Box). Shepmaster's answer describes in more detail why this is the case.

Fortunately, node.left is an Option<_>, so there is an easy fix for this: Option::take. .take() on an Option gives you the internal value (if there is one), but without consuming the Option, putting None in its place. So you can use .take() to swap None in temporarily while calling Node::insert, and then replace it with the return value.

pub mod btree {
    pub struct Node {
        pub id: u32,
        pub red: bool,
        pub left: Option<Box<Node>>,
        pub right: Option<Box<Node>>,
    }

    impl Node {
        pub fn insert(node: Option<Box<Node>>, id: u32) -> Option<Box<Node>> {
            match node {
                None => Some(Box::new(Node {
                    id: id,
                    red: true,
                    left: None,
                    right: None,
                })),
                Some(x) => Node::insert_(x, id),
            }
        }

        pub fn insert_(mut node: Box<Node>, id: u32) -> Option<Box<Node>> {
            node.left = Node::insert(node.left.take(), id);
            Some(node)
        }
    }
}

Playground.

(I have renamed Btree and Node to follow Rust naming conventions and removed the <'a> lifetime.)

Answer 2

Box is very special in Rust; it is well-known to the compiler and certain tricks happen. For example, you can move out of a box by dereferencing it. This is related to that.

When your function accepts self, it's equivalent to saying:

pub fn insert_(node: Node, id: u32) -> Option<Box<Node>>

Rust performs a number of dereference steps automatically, so your Box<Node> is dereferenced to just a Node, and then the function can be called. The expanded form of your original code is thus:

Some(x) => Node::insert_(*x, id),

pub fn insert_(mut self: Node, id: u32) -> Option<Box<Node>> { /* ... */ }

Because the entire struct has been transferred to the function, it is safe to tear it apart and have invalid struct members. When you do so, the compiler tracks which members are valid and which are not in order to properly call (or not call) their destructors.

---

In your second form, the entire Box<Node> is passed to the function. When you try to modify a member of the the struct, you are attempting to reach into it and remove ownership of a member. You aren't allowed to take ownership of something that you only have a reference to — there's no way to inform the true owner of the reference which pieces are valid and which are not.

In this case, Box isn't special enough for the compiler to deal with this.

You can replicate what the compiler does by explicitly moving out of the Box. You also have to create the new Box when you return it:

Some(x) => Node::insert_(x, id),

pub fn insert_(node: Box<Node>, id: u32) -> Option<Box<Node>> {
    let mut node = *node;
    node.left = Node::insert(node.left, id);
    Some(Box::new(node))
}

trentcl's answer solves the "maybe invalid maybe not" problem in a different way. Option::take replaces one valid value with another valid value. If the destructors need to be run for whatever reason, everything will still be safe and well-defined.

---

You can even use Box<...> as the self parameter type — Box is special!

Some(x) => x.insert_(id),

pub fn insert_(self: Box<Node>, id: u32) -> Option<Box<Node>> {
    let mut node = *self;
    node.left = Node::insert(node.left, id);
    Some(Box::new(node))
}