具有可变引用的递归结构的生命周期

我试图定义一个类似于树遍历的链表的递归结构。节点拥有一些数据并可以访问其父节点。子节点应该可变地借用其父节点以确保独占访问，并在其被删除后释放它。我可以使用不可变引用定义此结构，但当我使父引用可变时则不行。当使父引用可变时，我对编译器错误感到困惑并且不理解它。

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

这是一个最小的例子。这可以编译但使用只读引用：

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

我想要一个可变的引用，所以我尝试替换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

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

由于以下原因，不可能使用可变引用来实现这种递归结构variance.

Rustonomicon 有一个关于方差的部分 https://doc.rust-lang.org/nomicon/subtyping.html#variance，用下表：

|           | '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);
}

不变性规则确保上面的代码被编译器拒绝并且不存在不健全之处。

Because &mut允许修改任何字段，包括带有引用的字段，并且因为这种递归不跟踪所有父生命周期，这是不健全的。 为了安全地实现这样的递归结构 Rust 需要一个允许变异的引用value（因为它有静态生命周期，所以没有问题）但不是parent。 在我上面发布的最小示例中，可以使用父级的不可变引用并将节点数据放在Cell or RefCell。另一个可能的解决方案（但我没有深入研究）是将可变父引用放在Pin但取消引用它会是unsafe：我必须手动确保我永远不会更改parent参考。

我的实际用例有点复杂，所以我将尝试重新构造它，通过将数据存储在由 a 支持的堆栈中来消除对递归结构的需要。Vec.