具有可变引用的递归结构中的生存期 [英] Lifetime in recursive struct with mutable reference
问题描述
我正在尝试定义类似于树遍历的链表的递归结构.节点具有一些数据并可以访问其父节点.子节点应可变地借用其父节点以确保独占访问，并在删除后释放它.我可以使用不可变的引用定义此结构，但是当我使父引用可变时则不能.当使父引用可变时，我会因编译器错误而困惑，无法理解.
如何使用可变的父引用定义这种递归结构的生存期?
这是一个最小的示例.可以编译，但使用只读引用:
struct Node<'a>{//父级参考.`None` 表示根节点.//我希望这是一个可变的引用.pub parent:选项<&'a Node<'a>> ;，//此字段仅表示附加到此节点的一些数据.pub值:u32，}//创建一个根节点//我使用静态生命周期，因为根没有父级，所以那里没有约束fn root_node(值:u32)->节点<'static>{节点{父母:没有，价值，}}//创建一个子节点//生命周期表示父母必须比孩子长寿fn child_node<'inner，'outer:'inner>(父级:&'inner mut Node<'outer> ;，值:u32，)->节点<'inner>{节点{父母:一些(父母)，价值，}}//使用struct的示例函数fn main(){让mut root = root_node(0);让mut c1 = child_node(& mut root，1);let mut c2 = child_node(& mut c1，2);{let mut c3 = child_node(& mut c2，3);令c4 = child_node(& mut c3，4);let mut cur = Some(&c4);而让Some(n)= cur {println！("{}"，n.value);cur = n.parent；}}{令c5 = child_node(& mut c2，5);let mut cur = Some(&c5);而让Some(n)= cur {println!("{}", n.value);cur = n.parent；}}println！("{}"，c2.value);} 我想要一个可变引用，所以我尝试替换 Node 结构以使用可变引用:
struct Node<'a>{//父级参考.无"表示根节点.//我希望这是一个可变的引用.pub parent:Option< a mut Node< a> ;，//此字段仅表示附加到此节点的一些数据.pub值:u32，} 但是随后出现以下错误:
错误[E0623]:生命周期不匹配->src/main.rs:25:22|21 |父级:&'inner mut Node<'outer> ;，|------------------------|||这两种类型声明了不同的生存期......25 |父母:一些(父母)，|^^^^^^ ...但是来自"parent"的数据在这里流入"parent" 我不了解可变性和流入字段的数据之间的关系.在不变的情况下，我已经要求函数传递可变/专有引用.我一直在尝试生命周期的各种组合(使用单个生命周期，逆转它们之间的关系等)，但是没有成功.
由于差异，无法使用可变引用实现这种递归结构.
Rustonomicon中有一个关于方差的部分，其中包含以下内容表:
||'a |T || ----------- | ----------- || ----------- ||& a T |协变协变|& a mut T |协变不变的 尤其是，&'a mut T 对于 T 是不变的.
这里的核心问题是，节点仅知道其父节点的生存期，而不知道其所有祖先的生存期.即使就我而言，我只想更改祖先的 value 字段，& mut Node 也可以修改 parent >我们无法获得精确生命周期的任何祖先领域.
这是一个示例，其中我的结构可能会导致可变的父级引用不正确.如果 T 在 &'a mut T 中是协变的，则以下代码将被接受:
fn main(){let mut root:节点<'static> ;；= root_node(0);//其中'a对应于`root`let mut c1:节点"a".= child_node(& mut root，1);{let mut evil_root:Node<'static>= root_node(666);{//其中'b对应于`c1`let mut c2:节点"b".= child_node(& mut c1，2);//其中 'c 对应于 `c2`let mut c3:节点"c".= child_node(& mut c2，3);//这是问题所在:`c3`知道其祖先的寿命至少与//作为`c2`.但是它不知道确切要多久.//由于存在协方差，因此evil_root的生存期是兼容的，因为//它比`c2`寿命更长.并且因为`& mut T`可以改变任何字段//我们可以执行以下操作:让c2_ref:& mut Node<'c>= c3.parent.unwrap();让c1_ref:& mut Node<'c>= c2_ref.parent.unwrap();* c1_ref.parent = Some(&mut; mut evil_root);}}//现在尝试访问`c1`的父级会导致读取后释放println！("{}"，c1.parent.unwrap().value);} 不变性规则可确保上面的代码被编译器拒绝，并且不会造成不健全的情况.
因为& mut 允许修改任何字段，包括带有引用的字段，并且由于这种递归不能跟踪所有父项的生命周期，因此这是不合理的.为了安全地实现这种递归结构，Rust需要一个允许变异 value 的引用(因为它具有静态生存期，在那里没有问题)，但没有 parent .在我上面发布的最小示例中，可以使用对父代的不可变引用并将节点数据放在 Cell 或 RefCell 之后.另一个可能的解决方案(但我对此没有做过多研究)是将可变的父引用放置在 Pin 后面，但取消引用将是 unsafe :手动确保我永远不会更改 parent 引用.
我的实际用例稍微复杂一点，因此我将尝试通过将数据存储在由 Vec 支持的堆栈中来重新构造它，以消除对递归结构的需要./p>
I am trying to define a recursive struct similar to a linked list for a tree traversal. A node has some data and access to its parent. The child node should borrow its parent mutably to ensure exclusive access, and release it once it's dropped. I can define this struct using immutable references, but not when I make the parent reference mutable. When making the parent reference mutable, I am confused by the compiler error and do not understand it.
How can I define the lifetimes for such a recursive structure with a mutable parent reference?
Here is a minimal example. This compiles but uses a readonly reference:
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: immutable reference
I want a mutable reference, so I tried to replace the Node struct to use a mutable reference:
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,
}
But then I get the following error:
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: mutable reference
I do not understand the relationship between mutability and data flowing into a field. In the immutable case, I was already requiring the functions to pass mutable/exclusive references. I've been trying various combinations of lifetimes (using a single lifetime, reversing their relationship, etc.) but was unsuccessful.
It is not possible to implement this kind of recursive structure with mutable references due to variance.
The Rustonomicon has a section on variance, with the following table:
| | 'a | T |
|-----------|-----------|-----------|
| &'a T | covariant | covariant |
| &'a mut T | covariant | invariant |
In particular, &'a mut T is invariant with regard to T.
The core issue here is that a Node only knows the lifetimes of its parent, not the lifetime of all its ancestors. Even if in my case I'm just interested in mutating the value field of the ancestor, &mut Node also gives access to modify the parent field of any ancestor up the chain where we don't have access to the precise lifetime.
Here is an example where my struct may causes unsoundness with a mutable parent reference.
The following code would be accepted if T was covariant in &'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);
}
The invariance rule ensures that the code above is rejected by the compiler and there is no unsoundness.
Because &mut allows to modify any field, including ones with references, and because this kind of recursion does not keep track of all the parent lifetimes, it would be unsound.
To safely implement such a recursive struct Rust would need a reference allowing to mutate value (since it has a static lifetime, no issue there) but not parent.
In the minimal example I posted above it could be achieved using immutable references for the parents and placing the node data behind a Cell or RefCell. Another possible solution (but I haven't looked much into it) would be to place the mutable parent references behind a Pin but dereferencing it would be unsafe: I'd have to manually ensure that I am never changing the parent reference.
My actual use case is a bit more complex, so I'll try to instead restructure it to remove the need for the recursive struct by storing my data in a stack backed by a Vec.
这篇关于具有可变引用的递归结构中的生存期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
