递归结构体中带有可变引用的生命周期问题

Question

我正在尝试定义一个递归结构，类似于用于树遍历的链表。节点包含一些数据和对其父节点的访问权限。子节点应该通过可变引用借用其父节点以确保独占访问，并在其被删除时释放它。我可以使用不可变引用来定义这个结构，但是当我使父引用可变时，我被编译器错误所困扰，无法理解它。

如何为具有可变父引用的这种递归结构定义生命周期？

以下是一个最简示例。这个示例编译成功，但使用了只读引用：

struct Node<'a> {
    // Parent reference. `None` indicates a root node.
    // I want this to be a mutable reference.
    pub parent: Option<&'a Node<'a>>,
    // This field just represents some data attached to this node.
    pub value: u32,
}

// Creates a root node
// I use a static lifetime since there's no parent for the root so there are no constraints there
fn root_node(value: u32) -> Node<'static> {
    Node {
        parent: None,
        value,
    }
}

// Creates a child node
// The lifetimes indicates that the parent must outlive its child
fn child_node<'inner, 'outer: 'inner>(
    parent: &'inner mut Node<'outer>,
    value: u32,
) -> Node<'inner> {
    Node {
        parent: Some(parent),
        value,
    }
}

// An example function using the struct
fn main() {
    let mut root = root_node(0);
    let mut c1 = child_node(&mut root, 1);
    let mut c2 = child_node(&mut c1, 2);
    {
        let mut c3 = child_node(&mut c2, 3);
        let c4 = child_node(&mut c3, 4);
        let mut cur = Some(&c4);
        while let Some(n) = cur {
            println!("{}", n.value);
            cur = n.parent;
        }
    }
    {
        let c5 = child_node(&mut c2, 5);
        let mut cur = Some(&c5);
        while let Some(n) = cur {
            println!("{}", n.value);
            cur = n.parent;
        }
    }
    println!("{}", c2.value);
}

Rust playground: 不可变引用

我想要一个可变引用，所以我尝试将 Node 结构体替换为使用可变引用：

struct Node<'a> {
    // Parent reference. `None` indicates a root node.
    // I want this to be a mutable reference.
    pub parent: Option<&'a mut Node<'a>>,
    // This field just represents some data attached to this node.
    pub value: u32,
}

但是我遇到了以下错误：

error[E0623]: lifetime mismatch
  --> src/main.rs:25:22
   |
21 |     parent: &'inner mut Node<'outer>,
   |             ------------------------
   |             |
   |             these two types are declared with different lifetimes...
...
25 |         parent: Some(parent),
   |                      ^^^^^^ ...but data from `parent` flows into `parent` here

Rust playground: 可变引用

我不理解可变性和数据流入字段之间的关系。在不可变情况下，我已经要求函数传递可变/独占引用。我一直在尝试各种生命周期的组合（使用单个生命周期，反转它们的关系等），但都没有成功。

- Demurgos

---

我相当确定你的整个概念是错误的。这种结构会允许可变别名(head.next.next和(head.next).next)。 - Shepmaster

@Shepmaster 我的目标是只有最低（活动）节点可以操作链中的数据。我不太理解您对可变别名的符号表示法。在我的示例中，一旦创建了 c3，它就借用了 c2（以及其中的 c1 和 root），因此在 c2 被丢弃之前，您无法访问它们，因此不应该能够为它们创建别名（至少这是目标）。 - Demurgos

这让我强烈想起了《如何使用特质对象链实现责任链模式？》（https://dev59.com/vqXja4cB1Zd3GeqPY_Ou），但我不确定它是否足够接近以标记为重复。那个问题的答案（我的和Lukas的）是否对你的问题有所启示？ - trent

@trentcl 谢谢，我会研究一下。为了更好地理解，我想使用这种结构来在递归函数调用之间传递数据。每个节点代表一个函数调用级别。这确保父节点首先被创建，然后将其作为可变引用传递给下一个调用，它使用这个父节点创建一个具有独占访问权限的子节点，当内部调用结束时，将删除子节点并重新获得对父节点的访问权限。 - Demurgos

@trentcl 你发的问题确实很相似。实际上，这是一个更通用的问题，使用了特质，并且下一个节点是在方法中设置的而不是在构造函数中。你对这个问题的回复实际上对应了我的不可变案例。问题在于我需要可变性。尽管如此，我仍然认为它帮助我解决了问题。我感觉这与生命周期方差有关。我记得结构体中的不可变引用是协变的，但可变引用是不变的，但我不确定这是否意味着我的问题可以解决。 - Demurgos

Answer 1

无法使用可变引用实现这种递归结构，因为存在"variance"(协变性)问题。 Rustonomicon有一个关于协变性的章节，其中包含以下表格：

|           | 'a        | T         |
|-----------|-----------|-----------|
| &'a T     | covariant | covariant |
| &'a mut T | covariant | invariant |

特别地，&'a mut T 在 T 方面是不变的。

这里的核心问题是，一个节点只知道其父节点的生命周期，而不知道其所有祖先节点的生命周期。即使在我的情况下，我只对祖先节点的 value 字段感兴趣，&mut Node 也提供了访问修改任何祖先节点的 parent 字段的权限，其中我们无法访问精确的生命周期。

以下是一个示例，其中我的结构可能导致可变父引用的不安全性。 如果 T 在 &'a mut T 方面是协变的，则将接受以下代码：

fn main() {
    let mut root: Node<'static> = root_node(0);

    // where 'a corresponds to `root`
    let mut c1: Node<'a> = child_node(&mut root, 1);
    {
        let mut evil_root: Node<'static> = root_node(666);
        {
            // where 'b corresponds to `c1`
            let mut c2: Node<'b>  = child_node(&mut c1, 2);
            // where 'c corresponds to `c2`
            let mut c3: Node<'c>  = child_node(&mut c2, 3);

            // Here is the issue: `c3` knows that its ancestors live at least as long
            // as `c2`. But it does not know how long exactly.
            // With covariance, the lifetime of `evil_root` would be compatible since
            // it outlives `c2`. And because `&mut T` enables to mutate any field
            // we could do the following:
            let c2_ref: &mut Node<'c> = c3.parent.unwrap();
            let c1_ref: &mut Node<'c> = c2_ref.parent.unwrap();
            *c1_ref.parent = Some(&mut evil_root);
        }
    }
    // Trying to access the parent of `c1` now causes a read-after-free
    println!("{}", c1.parent.unwrap().value);
}

不变性规则确保编译器拒绝上述代码并且不存在不安全性。

因为 &mut 允许修改任何字段，包括带有引用的字段，并且这种递归不跟踪所有父生命周期，所以这将是不安全的。 要安全地实现这样一个递归结构，Rust 需要一个允许修改 value（因为它具有静态生命周期，所以没有问题）但不允许修改 parent 的引用。 在我上面发布的最小示例中，可以使用父级的不可变引用来实现，并将节点数据放在 Cell 或 RefCell 后面。另一个可能的解决方案（但我没有深入研究）是将可变父引用放在 Pin 后面，但对其进行解引用会是 unsafe：我必须手动确保我从未更改过 parent 引用。 我的实际用例有点更复杂，因此我将尝试重新结构化它，通过存储由 Vec 支持的堆栈中的数据来消除对递归结构的需要。

- Demurgos