How do I access T in an Option<T> without causing a move?

Question

I'm working on an insert function in a binary search tree implementation. Here's my code:

pub struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>
}

fn insert_at_root(mut root_node: Node, new_node: Node) -> Node { //not reference because root_node will be mutated
    if root_node.data > new_node.data { // value less than root
        if let Some(left) = root_node.left {
            insert_node(*left, new_node); // *left is a way to downcast box, i.e. *left = T from Box<T>
        }
        else {
            root_node.set_left(Some(Box::new(new_node)));
        }
    }
    else if root_node.data < new_node.data {
        if let Some(right) = root_node.right {
            insert_node(*right, new_node);
        }
        else {
            root_node.set_right(Some(Box::new(new_node)));
        }
    }
    root_node
}

fn insert_node(mut exist_node: Node, new_node: Node) -> () {
    if exist_node.data > new_node.data {
        if let Some(left) = exist_node.left {
            insert_node(*left, new_node);
        }
        else {
            exist_node.set_left(Some(Box::new(new_node)));
        }
    }
    else if exist_node.data < new_node.data {
        if let Some(right) = exist_node.right {
            insert_node(*right, new_node);
        }
        else {
            exist_node.set_right(Some(Box::new(new_node)));
        }
    }
}

I have two insert functions so I can preserve the variable with the root node when I call insert_at_node.

My current problem is the line if let Some(left) = root_node.left { (and the line if let Some(right) = root_node.right {) in the insert_at_root function which apparently causes a move. As a result, I can't return root_node at the end of insert_at_node:

error[E0382]: use of moved value: `root_node`
  --> src/lib.rs:34:5
   |
19 |         if let Some(left) = root_node.left {
   |                     ---- value moved here
...
34 |     root_node
   |     ^^^^^^^^^ value used here after partial move
   |
   = note: move occurs because value has type `std::boxed::Box<Node>`, which does not implement the `Copy` trait

error: aborting due to previous error

The purpose of those lines is to check if the left (or right) child node is not None, basically root_node.left != None. Is there any way to achieve this without causing a move? Maybe something with an != or == sign.

Answer 1

You're problem is not that you test whether left/right is Some or None. BTW that could be done with the tests .is_some() and .is_none().

The problem you have is that you bind the variable left to the Node that is in the Option. By that you move the ownership of the content of the Option to the left variable.

In general if you don't want to move the ownership, you have to work with references. When ever the variable is inside an Option and you need to look inside it as a reference, you have to convert the type of it from Option<T> to Option<&T>. By than when you look inside the option, it's just a reference, and therefor doesn't move the ownership.

There are two functions available on Option that do this conversion: .as_ref() to convert to an immutable reference, and .as_mut() that converts to a mutable reference. Because you want to modify the content of left you need a mutable reference, so .as_mut() as what you want.

By using .as_mut() the left you get is a reference instead of the variable itself, so no ownership was transferred.

The next problem you get is that you cannot pass a reference into insert_node because the type signature of this function requires to get the variable instead of a reference. By that it would required that you pass the ownership inside this helper function, so it also wouldn't work. So we convert the signature of insert_node to take &mut Box<Node> instead of Node. So again we only take a reference and not the ownership.

pub fn insert_at_root(mut root_node: Node, new_node: Node) -> Node {
    //not reference because root_node will be mutated
    if root_node.data > new_node.data {
        // value less than root
        if let Some(left) = root_node.left.as_mut() {
            insert_node(&mut *left, new_node);
        } else {
            root_node.set_left(Some(Box::new(new_node)));
        }
    } else if root_node.data < new_node.data {
        if let Some(right) = root_node.right.as_mut() {
            insert_node(&mut *right, new_node);
        } else {
            root_node.set_right(Some(Box::new(new_node)));
        }
    }
    root_node
}

pub fn insert_node(exist_node: &mut Box<Node>, new_node: Node) -> () {
    if exist_node.data > new_node.data {
        if let Some(left) = exist_node.left.as_mut() {
            insert_node(&mut *left, new_node);
        } else {
            exist_node.set_left(Some(Box::new(new_node)));
        }
    } else if exist_node.data < new_node.data {
        if let Some(right) = exist_node.right.as_mut() {
            insert_node(&mut *right, new_node);
        } else {
            exist_node.set_right(Some(Box::new(new_node)));
        }
    }
}