Lifetime in recursive struct with mutable reference

Question

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.

Answer 1

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.