"Borrowed value does not live long enough" 在 B-Tree 节点枚举上匹配以获取引用时

Question

我正在尝试在 Rust 中实现 B 树，我正在努力解决如何管理与 match 语句交互的生命周期。我是 Rust 的新手，虽然我认为我了解生命周期是什么以及它们是如何工作的，但我不知道如何让它们做我想做的事。

我的数据结构是这样的：

enum Node<T: Key> {
    Internal(InternalNode<T>),
    Leaf(LeafNode<T>),
}

enum NodeRef<'a, T: 'a + Key> {
    Internal(&'a InternalNode<T>),
    Leaf(&'a LeafNode<T>),
}

enum NodeRefMut<'a, T: 'a + Key> {
    Internal(&'a mut InternalNode<T>),
    Leaf(&'a mut LeafNode<T>),
}

struct InternalNode<T: Key> {
    keys: Vec<T>,
    children: Vec<Box<Node<T>>>,
    num_keys: usize,
}

struct LeafNode<T: Key> {
    keys: Vec<T>,
    num_keys: usize,
}

pub struct BTree<T: Key> {
    num_keys: usize,
    root: Node<T>
}

在B-tree插入中，你需要插入一个节点，然后保持对你插入的节点的引用，这样你就可以平衡和分裂。这不是关于算法的问题，但这是一个说明问题的代码片段：

pub fn insert(&mut self, key: T) -> bool {
    let (_inserted_at, success) = match self.root {
        Node::Internal(ref mut node) =>
            BTree::insert_at_internal_node(&mut node, key),

        Node::Leaf(ref mut node) =>
            BTree::insert_at_leaf_node(&mut node, key),
    };

    panic!() // snip
}

fn insert_at_leaf_node<'a>(leaf: &'a mut LeafNode<T>, key: T) -> (NodeRefMut<'a, T>, bool) {
    panic!() // snip
}

fn insert_at_internal_node<'a>(internal: &'a mut InternalNode<T>, key: T) -> (NodeRefMut<'a, T>, bool) {
    panic!() // snip
}

然后我们得到以下我不知道如何解决的相当明显的错误：

   error[E0597]: `node` does not live long enough
--> src/trees/mod.rs:102:53
    |
102 |                 BTree::insert_at_internal_node(&mut node, key),
    |                                                     ^^^^ borrowed value does not live long enough
...
106 |         };
    |         - `node` dropped here while still borrowed
...
109 |     }
    |     - borrowed value needs to live until here

error[E0597]: `node` does not live long enough
--> src/trees/mod.rs:105:49
    |
105 |                 BTree::insert_at_leaf_node(&mut node, key),
    |                                                 ^^^^ borrowed value does not live long enough
106 |         };
    |         - `node` dropped here while still borrowed
...
109 |     }
    |     - borrowed value needs to live until here

本质上，我们需要一个对我们插入的叶节点的可变引用，insert_at 方法可以轻松生成它。但是，当我执行 match 语句时，它会生成一个对节点的可变引用，该节点的生命周期与匹配语句一样长（因此生成的引用不能比匹配块长寿，从而违背了目的）。

目前我只想可变地借用所有东西（我有一个 &mut self 是有原因的）但我不知道该怎么做。

Answer 1

TL;DR — 从通话中删除 &mut：

let (_inserted_at, success) = match self.root {
    Node::Internal(ref mut node) => BTree::insert_at_internal_node(node, key),
    Node::Leaf(ref mut node) => BTree::insert_at_leaf_node(node, key),
};

你的问题可以简化为这个（并且可能更进一步，但这仍然具有原始的一般形状）：

enum Node {
    Internal(InternalNode),
}

enum NodeRefMut<'a> {
    Internal(&'a mut InternalNode),
}

struct InternalNode;

fn insert(mut root: Node) {
    let _inserted_at = match root {
        Node::Internal(ref mut node) => internal(&mut node),
    };
}

fn internal<'a>(_internal: &'a mut InternalNode) -> NodeRefMut<'a> {
    unimplemented!()
}

如果您 print out the type of node，您会发现通过在模式中使用 ref mut，您已经创建了一个 &mut Node :

Node::Internal(ref mut node) => {
    let _: () = node;
    internal(&mut node)
}

error[E0308]: mismatched types
  --> src/main.rs:14:21
   |
14 |         let _: () = node; 
   |                     ^^^^ expected (), found mutable reference
   |
   = note: expected type `()`
              found type `&mut InternalNode`

当您获取第二个可变引用时，您获取的是对仅在匹配臂范围内的变量的可变引用。该变量的生命周期正是错误消息所指出的：匹配臂本身。

有趣的是，此错误仅在您从 match 返回值时发生。如果你不这样做，你会得到一个不同的错误：

error[E0596]: cannot borrow immutable local variable `node` as mutable
  --> src/main.rs:17:27
   |
17 |             internal(&mut node)
   |                           ^^^^
   |                           |
   |                           cannot reborrow mutably
   |                           try removing `&mut` here

因为变量node确实本身是不可变的！

"Borrowed value does not live long enough" 在 B-Tree 节点枚举上匹配以获取引用时

"Borrowed value does not live long enough" when matching on a B-Tree node enum to get a reference

tree

lifetime

rust