Rust cannot move out of dereference pointer

Question

I try to run this code:

impl FibHeap {
fn insert(&mut self, key: int) -> () {
    let new_node = Some(box create_node(key, None, None));

        match self.min{
            Some(ref mut t) => t.right = new_node,
            None => (),
        };
        println!("{}",get_right(self.min));
    }
}
fn get_right(e: Option<Box<Node>>) -> Option<Box<Node>> {
    match e {
        Some(t) => t.right,
        None => None,
    }
}

And get error

error: cannot move out of dereference of `&mut`-pointer
println!("{}",get_right(self.min));
              ^

I dont understand why I get this problem, and what I must use to avoid problem.

Answer 1

Your problem is that get_right() accepts Option<Box<Node>>, while it should really accept Option<&Node> and return Option<&Node> as well. The call site should be also changed appropriately.

Here is the explanation. Box<T> is a heap-allocated box. It obeys value semantics (that is, it behaves like plain T except that it has associated destructor so it is always moved, never copied). Hence passing just Box<T> into a function means giving up ownership of the value and moving it into the function. However, it is not what you really want and neither can do here. get_right() function only queries the existing structure, so it does not need ownership. And if ownership is not needed, then references are the answer. Moreover, it is just impossible to move the self.min into a function, because self.min is accessed through self, which is a borrowed pointer. However, you can't move out from a borrowed data, it is one of the basic safety guarantees provided by the compiler.

Change your get_right() definition to something like this:

fn get_right(e: Option<&Node>) -> Option<&Node> {
    e.and_then(|n| n.right.as_ref().map(|r| &**r))
}

Then println!() call should be changed to this:

println!("{}", get_right(self.min.map(|r| &**r))

Here is what happens here. In order to obtain Option<&Node> from Option<Box<Node>> you need to apply the "conversion" to insides of the original Option. There is a method exactly for that, called map(). However, map() takes its target by value, which would mean moving Box<Node> into the closure. However, we only want to borrow Node, so first we need to go from Option<Box<Node>> to Option<&Box<Node>> in order for map() to work.

Option<T> has a method, as_ref(), which takes its target by reference and returns Option<&T>, a possible reference to the internals of the option. In our case it would be Option<&Box<Node>>. Now this value can be safely map()ped over since it contains a reference and a reference can be freely moved without affecting the original value.

So, next, map(|r| &**r) is a conversion from Option<&Box<Node>> to Option<&Node>. The closure argument is applied to the internals of the option if they are present, otherwise None is just passed through. &**r should be read inside out: &(*(*r)), that is, first we dereference &Box<Node>, obtaining Box<Node>, then we dereference the latter, obtaining just Node, and then we take a reference to it, finally getting &Node. Because these reference/dereference operations are juxtaposed, there is no movement/copying involved. So, we got an optional reference to a Node, Option<&Node>.

You can see that similar thing happens in get_right() function. However, there is also a new method, and_then() is called. It is equivalent to what you have written in get_right() initially: if its target is None, it returns None, otherwise it returns the result of Option-returning closure passed as its argument:

fn and_then<U>(self, f: |T| -> Option<U>) -> Option<U> {
    match self {
        Some(e) => f(e),
        None => None
    }
}

I strongly suggest reading the official guide which explains what ownership and borrowing are and how to use them, because these are the very foundation of Rust language and it is very important to grasp them in order to be productive with Rust.