借用指针错误递归遍历树

Question

为了学习Rust,我正在实现一个AVL树/字典.为了插入一个新元素,我下到树中,直到找到一个可以插入它的节点.不幸的是,它抱怨了借用指针的几个问题,而且我在解密它们时遇到了麻烦.

我已经突出显示了哪里出现错误.

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
    }
}

为什么解构at借钱呢？为什么编译器会抱怨多次可变借用,这种情况永远不会发生？如何编写此代码以避免此类错误？

Answer 1

这似乎是借用检查器的弱点,也许是一个错误.问题是你at在比赛中借用然后修改它.不幸的是,编译器没有看到at循环内部和循环外部在概念上是不同的.但是,我们可以使它们明显不同:

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() {}

在这里,我们从转移可变借at到tmp_at,然后传输到left,然后将其传送回at.

更漂亮的选择可能是使用新范围:

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!(),
        }
    }
}