Recursive type - lifetime issues

Question

I think I partially understand the lifetime concepts, but I have an issue in a recursive type definition:

struct Person<'a> {
    name: String,
    children: Vec<&'a mut Person<'a>>,
    birth: String,
    death: String,
    religion: String,
    genre: String,
}

impl Person<'_> {
    fn add_children(&'_ mut self, p: &'_ mut Person<'_>) {
        self.children.push(p);
    }
}

The compiler says:

error[E0312]: lifetime of reference outlives lifetime of borrowed content...
  --> src/lib.rs:12:28
   |
12 |         self.children.push(p);
   |                            ^
   |
note: ...the reference is valid for the lifetime `'_` as defined on the impl at 10:13...
  --> src/lib.rs:10:13
   |
10 | impl Person<'_> {
   |             ^^
note: ...but the borrowed content is only valid for the anonymous lifetime #2 defined on the method body at 11:5
  --> src/lib.rs:11:5
   |
11 |     fn add_children(&'_ mut self, p: &'_ mut Person<'_>) {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0308]: mismatched types
  --> src/lib.rs:12:28
   |
12 |         self.children.push(p);
   |                            ^ lifetime mismatch
   |
   = note: expected mutable reference `&mut Person<'_>`
              found mutable reference `&mut Person<'_>`
note: the anonymous lifetime #3 defined on the method body at 11:5...
  --> src/lib.rs:11:5
   |
11 |     fn add_children(&'_ mut self, p: &'_ mut Person<'_>) {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...does not necessarily outlive the lifetime `'_` as defined on the impl at 10:13
  --> src/lib.rs:10:13
   |
10 | impl Person<'_> {
   |             ^^

error[E0308]: mismatched types
  --> src/lib.rs:12:28
   |
12 |         self.children.push(p);
   |                            ^ lifetime mismatch
   |
   = note: expected mutable reference `&mut Person<'_>`
              found mutable reference `&mut Person<'_>`
note: the lifetime `'_` as defined on the impl at 10:13...
  --> src/lib.rs:10:13
   |
10 | impl Person<'_> {
   |             ^^
note: ...does not necessarily outlive the anonymous lifetime #3 defined on the method body at 11:5
  --> src/lib.rs:11:5
   |
11 |     fn add_children(&'_ mut self, p: &'_ mut Person<'_>) {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

How is that? In my understanding, self and p have the same lifetime.

I want it to be a Vec<&mut Person> because I have a HashMap<String, Person> with every person having its children initialized to Vec::new(). I want to pass references to the Vec so it does not copy the whole person's data when updating children.

You'll see that the answer now has a lot more useful context for your specific case, which is why we wanted to know why. What you wanted is _extremely_ limited and is covered by a lot of [Why can't I store a value and a reference to that value in the same struct?](https://stackoverflow.com/q/32300132/155423). — Shepmaster, Dec 08 '20 at 19:37

pretzelhammer · Accepted Answer · 2020-12-08T19:29:47.790

'_ tells the compiler to infer the lifetime for you but in this case it's inferring a bunch of different anonymous lifetimes. Since the lifetime of Person is directly dependent on the lifetimes of its children you should make that explicit in your implementation, and once you do it compiles:

struct Person<'a> {
    name: String,
    children: Vec<&'a mut Person<'a>>,
    birth: String,
    death: String,
    religion: String,
    genre: String,
}

impl<'a> Person<'a> {
    fn add_children(&mut self, p: &'a mut Person<'a>) {
        self.children.push(p);
    }
}

playground

While the above compiles you'll find in practice that it's incredibly restrictive and hard to work with, if it's okay to have clones of Persons you'll have a much easier time working with this struct instead:

struct Person {
    children: Vec<Person>,
    // other fields
}

If you need to share Persons between multiple children vectors while being able to mutate them you should go with:

struct Person {
    children: Vec<Rc<RefCell<Person>>>,
    // other fields
}

If you're storing all Persons in a HashMap<String, Person> where the keys are unique and immutable you could also maintain each children vector like so:

struct Person {
    children: Vec<String>, // keys for HashMap<String, Person>
    // other fields
}

I'd also add that one way to avoid ownership issues is to have a store that contains all references of a type and a struct containing structure with ids. This way you can structure your data by keeping identifiers in a recursive struct like Vec but be able to get e ref of those ids from the store whenever you need. — Loïc Faure-Lacroix, Dec 08 '20 at 20:51

Recursive type - lifetime issues

1 Answers1