Lifetimes using recursive tree structure

I'm trying to understand how lifetimes work within a recursive structure.

Below is a sample program that implements a simple family tree. I designed it as a simple example in order to capture lifetime questions I'm having using a far more complex recursive tree structure, but the problems are well captured here.

It compiles and runs, and produces the output shown below. The family tree is modeled using the recursive Person structure storing a name, age and children vector of Person structures intended to hold the children (modeled of course by other Person structures). Inside main(), the code creates and populates 3 generations of a family tree starting with person1 as single root Person local variable.

Here's the output:

Ruth, 120 yrs old
    Pat, 91 yrs old
        Jim, 65 yrs old
        Chuck, 65 yrs old
    John, 89 yrs old
        Stan, 57 yrs old
        Anne, 55 yrs old
            Helena, 21 yrs old
            Peter, 19 yrs old

It shows my late Grandmother Ruth, and two of her children, Pat (my mom), John (my uncle), along with two of John's children (Ruth's grand children), Helena and Peter. (My first cousins once removed.)

The output is generated by a call to the method Person::show_family_tree(), which sets up the recursion that takes place in the Person::show_r() method.

The show_r() method first prints the person's name and age, and then iterates through and
calls itself using an indendation of 4 for each recursion level.

My goal for understanding lifetimes starts with simply trying to turn the Person::name field from a String to a &str. This should be posslbe since the lifetimes for all the strings are within the lifetime of the main() block.

When I try to do this, I start getting the usual complaints that I've come to undersant that require adding a generic lifetime to the Person struture that defines the lifetime of the &str field.

However, once I do that I start to get into a series of more complex complaints that seem intractable to me.

First I'll show the working program using String fields:

struct Person {
    name: String,
    age: i32,
    children: Vec<Person>,
}
impl Person {
    fn new(name: &str, age: i32) -> Person {
        Person {
            name: name.to_string(),
            age,
            children: Vec::new(),
        }
    }
    fn add<'a>(&mut self, name: &str, age: i32) -> &mut Person {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show_r(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
}

fn main() {
    let mut person1 = Person::new("Ruth", 120);
    person1
        .add("Pat", 91)
        .add("John", 89);
        
    person1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);

    person1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);

    person1.show_family_tree();
}

The first thing I do is to modify the Person::name field from a String to a &str, adding the lifetime as suggested by the compiler. I also add the suggested anonymous lifetime to the impl Person clause as well as remove the -- to_string() method invocation in the Person::new() method that is no longer required.

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}

impl Person<'_> {
    fn new(name: &str, age: i32) -> Person {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
....  rest of program remains untouched.

This generates the following stream errors, that suggest I've run into some kind of recursive lifetime referencing problem. My basic question is can this be easily solved or do I need to result to unsafe raw ptr managment tactics?

16 |             Self::new(name, age)
   |             ^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 14:33...
  --> src/main.rs:14:33
   |
14 |     fn add<'a>(&mut self, name: &str, age: i32) -> &mut Person {
   |                                 ^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:16:23
   |
16 |             Self::new(name, age)
   |                       ^^^^
note: but, the lifetime must be valid for the lifetime `'_` as defined on the impl at 6:13...
  --> src/main.rs:6:13
   |
6  | impl Person<'_> {
   |             ^^
note: ...so that the expression is assignable
  --> src/main.rs:16:13
   |
16 |             Self::new(name, age)
   |             ^^^^^^^^^^^^^^^^^^^^
   = note: expected `Person<'_>`
              found `Person<'_>`

error[E0308]: mismatched types
  --> src/main.rs:18:9
   |
18 |         self
   |         ^^^^ lifetime mismatch
   |
   = note: expected mutable reference `&mut Person<'_>`
              found mutable reference `&mut Person<'_>`
note: the anonymous lifetime defined on the method body at 14:16...
  --> src/main.rs:14:16
   |
14 |     fn add<'a>(&mut self, name: &str, age: i32) -> &mut Person {
   |                ^^^^^^^^^
note: ...does not necessarily outlive the lifetime `'_` as defined on the impl at 6:13
  --> src/main.rs:6:13
   |
6  | impl Person<'_> {
   |             ^^
1 Like

You’ve got to make sure that the &str and the Person<'_>’s lifetimes match up as promised in the struct definition. So you need impl<'a> Person<'a> and &'a str.

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}

impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show_r(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
}

fn main() {
    let mut person1 = Person::new("Ruth", 120);
    person1
        .add("Pat", 91)
        .add("John", 89);
        
    person1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);

    person1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);

    person1.show_family_tree();
}

For completeness. What you had

impl Person<'_> {
    fn new(name: &str, age: i32) -> Person {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add<'a>(&mut self, name: &str, age: i32) -> &mut Person {
        self.children.push(
            Self::new(name, age)
        );
        self
    }

is equivalent (under lifetime elision rules) to

impl<'b> Person<'b> {
    fn new<'e>(name: &'e str, age: i32) -> Person<'e> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add<'a, 'c, 'd>(self: &'c mut Person<'b>, name: &'d str, age: i32) -> &'c mut Person<'c> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }

You can try to figure out yourself where exactly the lifetimes don’t add up.

Also, the error messages become a lot better like this (no more “anonymous lifetime”s):

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter 'e in function call due to conflicting requirements
  --> src/main.rs:17:13
   |
17 |             Self::new(name, age)
   |             ^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'d` as defined on the method body at 15:20...
  --> src/main.rs:15:20
   |
15 |     fn add<'a, 'c, 'd>(self: &'c mut Person<'b>, name: &'d str, age: i32) -> &'c mut Person<'c> {
   |                    ^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:17:23
   |
17 |             Self::new(name, age)
   |                       ^^^^
note: but, the lifetime must be valid for the lifetime `'b` as defined on the impl at 7:6...
  --> src/main.rs:7:6
   |
7  | impl<'b> Person<'b> {
   |      ^^
note: ...so that the expression is assignable
  --> src/main.rs:17:13
   |
17 |             Self::new(name, age)
   |             ^^^^^^^^^^^^^^^^^^^^
   = note: expected `Person<'b>`
              found `Person<'_>`

error[E0308]: mismatched types
  --> src/main.rs:19:9
   |
19 |         self
   |         ^^^^ lifetime mismatch
   |
   = note: expected mutable reference `&'c mut Person<'c>`
              found mutable reference `&'c mut Person<'b>`
note: the lifetime `'c` as defined on the method body at 15:16...
  --> src/main.rs:15:16
   |
15 |     fn add<'a, 'c, 'd>(self: &'c mut Person<'b>, name: &'d str, age: i32) -> &'c mut Person<'c> {
   |                ^^
note: ...does not necessarily outlive the lifetime `'b` as defined on the impl at 7:6
  --> src/main.rs:7:6
   |
7  | impl<'b> Person<'b> {
   |      ^^

Some errors have detailed explanations: E0308, E0495.
2 Likes

Thank you for the tip. I've never liked adding anonymous lifetimes and your description of what actually is happening when I do that is helpful. I'll give that a try and see if the problem becomes more tractable.

error[E0496]: lifetime name `'a` shadows a lifetime name that is already in scope
  --> src/main.rs:14:12
   |
6  | impl<'a> Person<'a> {
   |      -- first declared here
...
14 |     fn add<'a>(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
   |            ^^ lifetime `'a` already in scope

For more information about this error, try `rustc --explain E0496`.
error: could not compile `playground` due to previous error

Here is my code, in case I missed somethig. I'm still fiddling around with various combinations of lifetimes to see if it will compile. I am wondering if I need to employ unsafe blocks and use raw pointers, but I'm hoping to avoid that until I know it's needed.

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}
impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add<'a>(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show_r(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
}

fn main() {
    let mut person1 = Person::new("Ruth", 120);
    person1
        .add("Pat", 91)
        .add("John", 89);
        
    person1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);
        
    person1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);
        
    person1.children[1].children[1]
        .add("Helena", 21)
        .add("Peter", 19);

    person1.show_family_tree();
}

My bad. I copied your change incorrectly!

I had an <'a'> on my fn add() function.

Once I removed that it worked!

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.