Borrow pointer errors recursively traversing tree [duplicate]

rust

To learn Rust, I am implementing an AVL tree/dictionary. To insert a new element, I descend into the tree until I find a node where it could be inserted. Unfortunately it complains about several issues with borrowing pointers, and I'm having trouble deciphering them.

I've highlighted where and which errors occur.

enum AVLTree<T, U> {
    Tree(T, U, Box<AVLTree<T, U>>, Box<AVLTree<T, U>>),
    Empty,
}

impl<T, U> AVLTree<T, U>
    where T: PartialOrd + PartialEq + Copy,
          U: Copy
{
    fn insert_element(&mut self, key: T, val: U) {
        let new_node = AVLTree::Tree(key, val, Box::new(AVLTree::Empty), Box::new(AVLTree::Empty));

        if let AVLTree::Empty = *self {
            *self = new_node;
            return;
        }

        let mut at = self;
        loop {
            match at {
                &mut AVLTree::Tree(key2, _, ref mut left, ref mut right) => {
                    //                      ^~~~~~~~~~~~
                    // error: cannot borrow `at.2` as mutable more than once at a time
                    //                                    ^~~~~~~~~~~~~
                    // error: cannot borrow `at.3` as mutable more than once at a time
                    if key < key2 {
                        if let AVLTree::Empty = **left {
                            *left = Box::new(new_node);
                            break;
                        }
                        at = &mut **left;
                        // error: cannot assign to `at` because it is borrowed
                    } else {
                        if let AVLTree::Empty = **right {
                            *right = Box::new(new_node);
                            break;
                        }
                        at = &mut **right;
                        // error: cannot assign to `at` because it is borrowed
                    }
                }
                &mut AVLTree::Empty => unreachable!(),
            }
        }
        // Do something
    }
}

Why is deconstructing at borrowing it? Why is the compiler complaining about multiple mutable borrows when this should never happen? How could this code be written instead to avoid such errors?

This seems to be a weakness of the borrow checker, and is perhaps a bug. The problem is that you are borrowing at in the match and then modifying it. Unfortunately, the compiler doesn't see that the at inside the loop and outside the loop are conceptually different. We can make them explicitly different, however:

enum AVLTree {
    Tree(Box<AVLTree>),
    Empty,
}

impl AVLTree {
    fn insert_element(&mut self) {
        let mut at = self;
        loop {
            let tmp_at = at; // Main change
            match tmp_at {
                &mut AVLTree::Tree(ref mut left) => {
                    at = &mut **left;
                }
                &mut AVLTree::Empty => unreachable!()
            }
        }
    }
}

fn main() {}

Here, we transfer the mutable borrow from at to tmp_at, then transfer it to left, then transfer it back to at.

A prettier option may be to use a new scope:

fn insert_element(&mut self) {
    let mut at = self;
    loop {
        match {at} { // Main change
            &mut AVLTree::Tree(ref mut left) => {
                at = &mut **left;
            }
            &mut AVLTree::Empty => unreachable!(),
        }
    }
}

Borrow pointer errors recursively traversing tree [duplicate]

Related

Recent Posts