"borrowed value does not live long enough" trie 插入错误

Question

我有一个简单的 trie 实现，其中 Edge 包含一个字符和对另一个 Node:

的引用

struct Edge<'a> {
    ch: char,
    to: &'a Node<'a>,
}

A Node 包含边向量：

pub struct Node<'a> {
    edges: Vec<Edge<'a>>,
}

我正在尝试实现将字符 insert/get 放入节点的方法。我认为return值应该是对Node的引用：如果字符已经在其中一条边上，那么我们直接return现有的Node；如果没有，我们 return 新创建的 Node。这就是我遇到麻烦的地方：

impl<'a> Node<'a> {
    fn get_or_create(&mut self, ch: char) -> &Node<'a> {
        match self.edges.binary_search_by(|e| e.ch.cmp(&ch)) {
            Ok(idx) => {
                return &self.edges.get(idx).unwrap().to;
            }
            Err(idx) => {
                let to = &Node { edges: Vec::new() };
                let e = Edge { ch: ch, to: to };
                self.edges.insert(idx, e);
                return to;
            }
        }
    }
}

据说to活不长

我很确定我写的远非惯用的 Rust。最初当我在 Edge 中包含对 Node 的引用时，我没有添加 lifetime 参数，并且被提示这样做，然后我不得不在所有地方添加它。然而，它看起来很奇怪。我想知道正确的方法是什么？

也许我真正应该使用的是 Edge 中的一些其他包装器类型抽象来引用堆分配的 Node，例如Box？我将仔细阅读 The Rust Programming Language 中有关此主题的部分。

Answer 1

此数据结构无法按设计工作。红旗就是下面这句话：

I think the return value should be a reference to a Node: if the character is already in one of the edges, then we directly return the existing Node; if not, we return the newly created Node.

代码没有return新创建的节点，它试图return一个引用到新创建的节点。返回对象的引用只有在对象存储在比引用更有效的地方时才是安全的。否则，引用最终会指向对象曾经驻留的堆栈位置，从而导致使用时崩溃。像这样的错误是 C 和 C++ 中常见的崩溃根源，而 Rust 的借用检查器正是为了防止这种错误而设计的。

Rust 使用函数和数据的生命周期参数来跟踪引用生命周期。为了证明引用不会比对象长寿，Rust 禁止引用的生命周期超过对象的生命周期。由于新节点在函数末尾被删除并且引用是从函数中 returned，对象的生命周期太短，代码被正确拒绝为无效。

有几种可能的修复方法：

将Node直接存入Edge。这是 shown to compile.
将 &Node 更改为 Rc<Node>。这允许多个边缘共享单个节点的所有权，并自动解除分配。

在这两种情况下，都不再需要明确的生命周期管理，所有权将 "just work"。如果您了解 C++11，Rc<> 大致等同于 std::shared_ptr.

"borrowed value does not live long enough" trie 插入错误

"borrowed value does not live long enough" error in trie insertion

lifetime

rust

borrow-checker