Rust 可变引用在某些情况下有效但在其他情况下无效

Question

我遇到了一个我无法理解的问题，涉及可变引用和借用检查器。我正在使用 safe rust 编写一个朴素的二叉搜索树。完整代码可以在这里看到：https://github.com/adensur/rust_learning/blob/master/bst/src/lib.rs
这是节点和树本身：

struct Node {
 key: i64,
 left_ptr: Option<Box<Node>>,
 right_ptr: Option<Box<Node>>,
}

#[derive(Default)]
pub struct BstSet {
 root: Option<Box<Node>>,
 len: usize,
}

这里是插入函数（类似于HashSet::insert()），并且有效：

pub fn insert(&mut self, key: i64) -> bool {
        let mut node_ptr = &mut self.root;
        while let Some(node) = node_ptr {
            match node.key.cmp(&key) {
                Ordering::Equal => return false,
                Ordering::Less => {
                    node_ptr = &mut node.right_ptr;
                }
                Ordering::Greater => {
                    node_ptr = &mut node.left_ptr;
                }
            }
        }
        *node_ptr = Some(Box::new(Node {
            key,
            left_ptr: None,
            right_ptr: None,
        }));
        self.len += 1;
        true
    }

我尝试将这段代码移动到一个函数中以供某些代码重用，但它没有编译：

fn find_node_mut(&mut self, key: i64) -> &mut Option<Box<Node>> {
        let mut node_ptr = &mut self.root;
        while let Some(node) = node_ptr {
            match node.key.cmp(&key) {
                Ordering::Equal => break,
                Ordering::Less => {
                    //node_ptr = &mut node_ptr.as_mut().unwrap().right_ptr;
                    node_ptr = &mut node.right_ptr;
                }
                Ordering::Greater => {
                    // node_ptr = &mut node_ptr.as_mut().unwrap().left_ptr;
                    node_ptr = &mut node.left_ptr;
                }
            }
        }
        node_ptr
    }

给我这个错误：

error[E0499]: cannot borrow `*node_ptr` as mutable more than once at a time
  --> src/lib.rs:61:9
   |
46 |     fn find_node_mut(&mut self, key: i64) -> &mut Option<Box<Node>> {
   |                      - let's call the lifetime of this reference `'1`
47 |         let mut node_ptr = &mut self.root;
48 |         while let Some(node) = node_ptr {
   |                        ---- first mutable borrow occurs here
...
61 |         node_ptr
   |         ^^^^^^^^
   |         |
   |         second mutable borrow occurs here
   |         returning this value requires that `node_ptr.0` is borrowed for `'1`

For more information about this error, try `rustc --explain E0499`.

为什么它在一种情况下有效而在另一种情况下无效？对此进行推理以预测编译器会说什么的正确方法是什么？

在摆弄代码之后，我找到了一种（有点乱）编写它的方式，以便它可以工作（代码中的注释行），但事实上我不明白为什么会这样发生的事情困扰着我。

Answer 1

这里的主要错误是你有一个 &mut Option<Box<Node>>，但这没有多大意义，你可能想要一个 Option<&mut Box<Node>>。无论是否找到某物，Option 都不需要是引用的可变对象。有了它，您可以利用 as_mut 和 and_then 来启动您的代码，然后对循环内部的检查进行一些修改：

impl BstSet {
    fn find_node_mut(&mut self, key: i64) -> Option<&mut Box<Node>> {
        self.root.as_mut().and_then(|mut node_ptr| loop {
            match node_ptr.key.cmp(&key) {
                Ordering::Equal => return Some(node_ptr),
                Ordering::Less => {
                    if let Some(right) = node_ptr.right_ptr.as_mut() {
                        node_ptr = right;
                    } else {
                        return None
                    }
                }
                Ordering::Greater => {
                    if let Some(left) = node_ptr.left_ptr.as_mut() {
                        node_ptr = left;
                    } else {
                        return None
                    }                
                }
            }
        })
    }
}

Playground

Answer 2

似乎这个帖子 that refers to a known issue https://github.com/rust-lang/rust/issues/21906#issuecomment-73296543 回答了我的问题。运行我的 Polonius 借用检查器程序似乎也可以工作：

RUSTFLAGS="-Z polonius" cargo +nightly test

这是解释事情的完美视频：https://www.youtube.com/watch?v=_agDeiWek8w
如何正确推理这个以确定为什么 insert 函数编译，而 find_node_mut 不编译：
在这两个函数中，node 和 node_ptr 可以互换使用，因此它们的范围有点“重叠”。在 insert 函数中，编译器能够正确判断贷款的“活跃度”：如果变量即将被写入（当前值不能在未来被引用），则该变量是“死的”。这样，即使两个可变引用具有重叠范围，它们的 'lifetimes'（由一组线表示）也不会重叠。
在 find_node_mut 中，引用是从函数返回的，将引用的生命周期从一小部分行扩大到某个“未知”生命周期 'a，至少覆盖了整个函数体。

Rust 可变引用在某些情况下有效但在其他情况下无效

Rust mutable references working in some cases but not in other cases

rust

borrow-checker