借用指针错误递归遍历树 [英] Borrow pointer errors recursively traversing tree

问题描述

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

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

为什么解构 at 借用它?为什么编译器会在不应该发生的情况下抱怨多个可变借用?如何编写此代码来避免此类错误?

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?

推荐答案

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

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

这里，我们将可变借用从at转移到tmp_at，然后转移到left，再转移回在.

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

这篇关于借用指针错误递归遍历树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！