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.

Answer 1

'_ 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
}