Reorganize boxed elements inside struct

Question

I'm trying to implement the rotation code for a balanced (AVL) version of a binary search tree in Rust, but I'm having trouble claiming ownership of the nodes to be reorganized.

My structure:

struct Tree<T> {
    root: Box<TreeNode<T>>,
    depth: usize,
}

enum TreeNode<T> {
    Empty,
    Node {
        val: T,
        left: Tree<T>,
        right: Tree<T>,
    },
}

I know I could use only one type, or Options. This seemed a little nicer.

When I want to implement the rotation:

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

I cannot find a way to reassign the nodes. I have a rotate(&mut self, ...) method that I call on z node (the Tree<T> node), but I need to use a match *self.root {} to cast the root TreeNode to its Node version to get the components. That works, but I cannot use those extracted values to create a new node.

If I try this:

fn insert(&mut self, ...) {
   ...
   // need to rotate
   rotate(self, ...);
}

fn rotate(&mut ztree, ...) {
    ztree.root = match *ztree.root {
        // just re assign same tree to test...
        TreeNode::Node {val, left, right} =>
                Box::new(TreeNode::Node {val: val, left: left, right: right}),
        _ => panic!("meh"),
    } ...

I get this error.

    |
171 |             ztree.root = match *ztree.root {
    |                                 ^^^^^ cannot move out of borrowed content
172 |                 TreeNode::Node {val, left, right} =>
    |                                 ---  ----  ----- ...and here (use `ref right` or `ref mut right`)
    |                                 |    |
    |                                 |    ...and here (use `ref left` or `ref mut left`)
    |                                 hint: to prevent move, use `ref val` or `ref mut val`

I understand that it doesn't like me to get ownership on the boxed TreeNode, but I don't know how to tell Rust that I'm going to assign a new boxed TreeNode and the old TreeNode could be claimed locally.

If I try self.root = Box::new(TreeNode::Empty) that works just fine, because it knows that I'm reassigning self.root to a new box, and previous box and referenced heap struct should be deallocated.

Answer 1

Suppose that Rust did trust you to replace the value of ztree.root. Then you could write

fn rotate(&mut ztree, ...) {
    let locally_owned = ztree.root (and I promise to give it back);
    // Now, ztree.root is in some undefined state. 
    // Thats OK though, because I promise to fix it before anyone looks!

    let local_new_value = match locally_owned {
        // just re assign same tree to test...
        TreeNode::Node {val, left, right} =>
                Box::new(TreeNode::Node {val: val, left: left, right: right}),
        // Looks safe-ish, because the whole program will crash, 
        // so the programmer might expect that no one
        // will see the undefined value of ztree.root
        // (in fact, there would be problems when the destructor
        //  of ztree.root is called in the panic)
        _ => panic!("meh"), 
    }
    // FIXED IT! Put a value back into ztree.root
    ztree.root = local_new_value;
}

which looks kind of OK. However, imagine if you replaced the panic("meh") with some return statement. Then you could have code like this:

ztree.root = Box::new(TreeNode::Empty);
// Returns without replacing the value of ztree.root
// because ztree.root is Empty 
rotate(&mut ztree); 
// Now ztree.root is in a undefined state
rotate(&mut ztree); // So something bad happens here

Basically, the compiler would have to convince itself that, not only do you intend to replace the value of ztree.root, but that there is no code path that would result in the value not being replaced. This is way to complicated, and for this reason, there isn't a way to tell the compiler to let you do what you are trying to do.

Instead, you can solve your problem by restating it. Instead of trying to calculate a new value to replace the old value, you really just need to change the current value, without replacing it. One way to do this is by using std::mem::swap like so (Playground):

fn rotate<T>(ztree: &mut Tree<T>) {
    let ref mut root : TreeNode<T> = *ztree.root;

    match root {
        &mut TreeNode::Node {ref mut left, ref mut right, ..} => {
            std::mem::swap(left, right);
        },
        _ => unimplemented!(),
    }
}

If you're wondering why let ref mut root: TreeNode<T> = *ztree.root; works but match *ztree.root {...} doesn't, I am not really sure, but it probably has to do with this issue.