Trouble understanding dereferencing after option destructuring

help
1

I am trying to implement a binary tree which, after reading other posts, seems to be a great way to test yourself against the borrow checker. The below code is reproduced here.

struct Node<T: Eq + PartialEq + Ord + PartialOrd> {
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
    value: T
}

impl<T> Node<T>
where
    T: Eq + PartialEq + Ord + PartialOrd,
{
    fn new(value: T) -> Self {
        Self {
            left: None,
            right: None,
            value,
        }
    }


    fn insert(&mut self, value: T) {
        if value == self.value {
            return;
        }

        let mut target = if value > self.value {
            self.right
        } else {
            self.left
        };

        match target {
            Some(ref mut t) => {
                t.insert(value);
            }
            None => {
                let new_node = Node::new(value);
                *target = Some(Box::new(new_node));
            }
        }
    }
}

And the error:

   Compiling playground v0.0.1 (/playground)
error[E0614]: type `Option<Box<Node<T>>>` cannot be dereferenced
  --> src/lib.rs:37:17
   |
37 |                 *target = Some(Box::new(new_node));
   |                 ^^^^^^^

For more information about this error, try `rustc --explain E0614`.
error: could not compile `playground` (lib) due to previous error

The error of course makes sense. I am trying to set something of type Option to something else via dereferencing which isn't possible. What is confusing to me is how to handle this case. In the Some case it seems obvious that I need to destructure the option with ref mut to get the inner box of a node and then call insert on it. However, in the None case there is nothing to destructure to and I need to set the target itself. If I remove the dereference it will not set the pointed-to value itself.

I am not sure how to reorganize this code so that dereferencing will be allowed. I would appreciate any help!

1 Like
2

The main problem is earlier in the code… unfortunately hidden by the error about dereferencing triggering earlier in compilation

fn insert(&mut self, value: T) {
    if value == self.value {
        return;
    }

    let mut target = if value > self.value {
        self.right
    } else {
        self.left
    };

    // match target {
    //     Some(ref mut t) => {
    //         t.insert(value);
    //     }
    //     None => {
    //         let new_node = Node::new(value);
    //         *target = Some(Box::new(new_node));
    //     }
    // }
}

error[E0507]: cannot move out of `self.right` which is behind a mutable reference
  --> src/lib.rs:26:9
   |
26 |         self.right
   |         ^^^^^^^^^^ move occurs because `self.right` has type `Option<Box<Node<T>>>`, which does not implement the `Copy` trait
   |
help: consider borrowing here
   |
26 |         &self.right
   |         +

error[E0507]: cannot move out of `self.left` which is behind a mutable reference
  --> src/lib.rs:28:9
   |
28 |         self.left
   |         ^^^^^^^^^ move occurs because `self.left` has type `Option<Box<Node<T>>>`, which does not implement the `Copy` trait
   |
help: consider borrowing here
   |
28 |         &self.left
   |         +
1 Like
3

Indeed the following code does work:

    fn insert(&mut self, value: T) {
        if value == self.value {
            return;
        }

        let target = if value > self.value {
            &mut self.right
        } else {
            &mut self.left
        };

        match target {
            Some(ref mut t) => {
                t.insert(value);
            }
            None => {
                let new_node = Node::new(value);
                *target = Some(Box::new(new_node));
            }
        }
    }

This seems like it would've been impossible to simply guess at my experience level. Is there something that made you think that it would be a hidden compiler error? Or maybe better asked: is there a strategy for debugging these types of things you could share?

1 Like
4

Possibly… writing code line by line, and run the compiler as often as possible can help not missing anything, as you’ll have more than one error less often… (use todo!() at the end of functions with return values, until they’re finished).

And perhaps, with a little bit more experience, you’d question whether target is defined correctly if you notice that it’s an owned Option<Box<Node<T>>> instead of a reference type; which is information the compiler does give (though perhaps not clearly enough) in the message “type `Option<Box<Node<T>>>` cannot be dereferenced”, referring to dereferencing target with the dereferencing expression *target; thus claiming that target is of type Option<Box<Node<T>>> – and such type information is also something where tools like rust-analyzer can help ^^

1 Like
5

Excellent. I didn't even know todo!() existed. Thank you very much.

6

By the way, with the working code, it is an option not to write the ref mut in the ref mut t pattern explicitly, since the “match ergonomics” feature will take care of that.

match target {
    Some(t) => {
        t.insert(value);
    }
    None => {
        let new_node = Node::new(value);
        *target = Some(Box::new(new_node));
    }
}

Or if you want to have the type of the pattern correspond exactly to the actual type, you could also be more explicit if you wanted, via something like

match target {
    &mut Some(ref mut t) => {
        t.insert(value);
    }
    &mut None => {
        let new_node = Node::new(value);
        *target = Some(Box::new(new_node));
    }
}

or by dereferencing before the match

match *target {
    Some(ref mut t) => {
        t.insert(value);
    }
    None => {
        let new_node = Node::new(value);
        *target = Some(Box::new(new_node));
    }
}

(also, in that case #![warn(clippy::pattern_type_mismatch)] can point out the existence of “match ergonomics”)

To be clear, all these alternatives have the same behavior, and t will be a &mut Box<Node<T>>>

There are differing opinions on the topic. I personally like the feature and would rarely write an explicit “ref”/“ref mut” at all; for an owned target value, match &mut target { Some(t) => …, … } can make t a mutable reference, too.

Sometimes it’s also useful to know of the as_ref() and as_mut() methods of Option, especially in cases where you want to unwrap() it, but by-reference, not by-value; e.g. for a target: &mut Option<…>, you cannot do &mut target.unwrap() as that’d try to move the value – instead target.as_mut().unwrap() is the approach that works. (Feel free to look up the signatures of these methods in the docs.)

1 Like
7

Well, if you want to mutate something, you either have to own it or have a mutable reference to it. Owning it doesn't help in your case, because that would mean you are mutating a local, which doesn't affect anything behind the *self parameter. Hence, you must have a mutable reference to whatever you are trying to mutate.

Incidentally, this is not a "guess". This is the only reasonable/standard solution. (By "reasonable", I mean that – as always – it's probably possible to come up with convoluted ways that technically achieve the same result, e.g. multiple layers of references, interior mutability, unsafe, etc. But those are unnecessary.)

The fact that you are trying to move out from behind a reference, which is generally impossible (unless the types are Copy, which Box isn't).

1 Like
8

Another way to get to the other error message would've been to first rewrite *target = into target =.