Lifetime mismatch with self referencing structs in a `Vec`

user_736070 0
Viewed 118

I have the following code which you can also see in the playground:

struct Node<'a> {
    parent: Option<&'a Node<'a>>,
    name: &'a str,
}

fn looper(nodes: &mut Vec<Node>) {
    for i in 0..nodes.len() {
        let n = &nodes[i];
        let next_node = Node {
            parent: Some(n),
            name: "please compile",
        };
        nodes.push(next_node);
    }
}

It's supposed to take a Vec of Nodes and append Nodes to it that reference the Nodes already in the Vec. Unfortunately I get this error:

error[E0623]: lifetime mismatch
  --> src/main.rs:13:20
   |
6  | fn looper(nodes: &mut Vec<Node>) {
   |                  -------------- these two types are declared with different lifetimes...
...
13 |         nodes.push(next_node);
   |                    ^^^^^^^^^ ...but data from `nodes` flows into `nodes` here

How can I make this compile? An explanation of how to think about lifetimes in this context would be useful. I understand this may be an issue due to variance but am not sure how to rephrase my problem to give me the functionality I would like.

rust lifetime
1 Answers

A general rule: when some value's type, or trait it implements, has a lifetime parameter, that lifetime is always longer than the life of the value itself — the value has a guarantee that the references it contains won't go invalid before they are dropped.

In fact, in your example we can see that if this were not the case, the lifetime checking would be unsound; you're adding values to nodes, but nothing would prevent looper from instead removing values from nodes, which would then invalidate any parent references that referred to those values.

The only practical way to build a tree or linked list of references (without special-purpose unsafe code that has a particular plan to keep things sound) is to write a recursive function; each function call frame may refer to nodes constructed by its caller (and its caller's caller and so on). This is accepted by the borrow checker because each frame has its own new, shorter lifetime for the references (a reference can always be taken as having a shorter lifetime than it started with).

user_996920
Related