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.

Pretty sure that your entire concept is flawed. This structure would allow mutable aliasing (head.next.next and (head.next).next). — Shepmaster
– Shepmaster, Commented Feb 11, 2020 at 21:53
@Shepmaster My goal is that only the lowest (active) node can manipulate the data in the chain. I do not quite understand your notation for mutable aliasing. In my example, once c3 is created it borrows c2 (and with it c1 and root) so you can't access those until c2 is dropped and so you shouldn't be able to alias them (at least it's the goal). — Demurgos
– Demurgos, Commented Feb 11, 2020 at 22:02
This strongly reminds me of How do I implement the Chain of Responsibility pattern using a chain of trait objects?, but I'm not sure it is close enough to mark a duplicate. Do the answers to that question (both mine and Lukas's) shed any light on your problem? — trent
– trent, Commented Feb 11, 2020 at 22:20
@trentcl Thanks, I'll look into it. To give more context, I want to use this structure to pass data between recursive function calls. Each node represents a function call level. This ensures that the parent is created first, I pass it as a mutable reference to the next call, it creates a child node with exclusive access to this parent, and when the inner call ends the child is dropped and I get back access to the parent node. — Demurgos
– Demurgos, Commented Feb 11, 2020 at 22:26
@trentcl The question you posted is indeed similar. It's actually a more general question using traits and where the next node is set with a method and not at construction. Your reply to this question actually corresponds to my immutable case. The issue is that I need mutability. Still, I believe that it helped me advance on the problem. I feel like this is related to lifetime variance. I think that I remember that immutable references in structs are covariant but mutable ones are invariant, but I am not sure if it means my question is solvable or not. — Demurgos
– Demurgos, Commented Feb 11, 2020 at 22:45

Demurgos · Accepted Answer · 2020-02-12 00:39:45Z

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.

Collectives™ on Stack Overflow

Lifetime in recursive struct with mutable reference

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related