 # Puzzle when playing with lifetime

Days ago, I came across some codes on this forum(original post gets forgotten by me, but no need to read or review it)

say we have a Rust tree with a `find_leafs` method here on playground:

``````use std::vec;

#[derive(Debug)]
pub struct Tree<T> {
root: Option<TreeNode<T>>,
}

#[derive(Debug)]
pub struct TreeNode<T> {
val: T,
children: Vec<TreeNode<T>>,
}

impl<T> TreeNode<T> {
pub fn new(val: T) -> Self {
Self {
val,
children: vec![],
}
}
pub fn find_leafs(&self) -> Vec<&TreeNode<T>> {
let mut leafs: Vec<&TreeNode<T>> = vec![];
self.find_leafs_r(&mut leafs);
leafs
}
fn find_leafs_r<'a, 'b>(&'a self, lfs: &'b mut Vec<&'a TreeNode<T>>) {
if self.children.len() > 0 {
self.children.iter().for_each(|c| c.find_leafs_r(lfs))
} else {
lfs.push(&self)
}
}
}

impl<T> Tree<T> {
pub fn new() -> Self {
Self { root: None }
}
pub fn find_leafs(&self) -> Vec<&TreeNode<T>> {
if self.root.is_none() {
return vec![];
}

let l = self.root.as_ref().unwrap().find_leafs();
return l;
}
}
``````

This is FINE now

After changing

``````    fn find_leafs_r<'a, 'b>(&'a self, lfs: &'b mut Vec<&'a TreeNode<T>>) {
// ...
}
``````

to

``````    fn find_leafs_r<'a, 'b: 'a>(&'a self, lfs: &'b mut Vec<&'a TreeNode<T>>) {
// ...
}
``````

it doesn't compile

why is this WRONG?

Based on my understanding, we use lifetime to refer to lifetime of pointee(the one gets pointed) of a borrow
so adding this constraint seems natural:

we need to make sure when we're able to access `lfs` (that `Vec`), all its contents' pointee (those `TreeNode`) don't get erased,
which indicates `'b: 'a` imo

BTW, I've tried to read error of `rustc`, but it seems pretty hard to understand

`'b: 'a` means "`'b` is longer then `'a`". On the other hand, existence of `&'b mut T<'a>` requires `'a` to be longer then `'b`. Combined, these two options mean that `'a` and `'b` must be identical, and thus the call to `find_leafs_r` locks the `lfs` vector behind the exclusive reference forever.

1 Like

As an illustration, consider the following code:

``````fn check<'a, 'b: 'a>(_: &'a mut &'b mut i32) {}

fn get_num() -> i32 { 42 }

fn main() {
let mut num = get_num();
let mut num_ref = &mut num;
check(&mut num_ref);
*num_ref = 42;
}
``````

Playground
This code compiles and runs fine, because lifetime annotations on `check` are aligned with the real usage (in fact, that's what would be elided if we remove the lifetime parameters entirely). But once you replace `&'a mut &'b mut` with `&'b mut &'a mut`, compiler immediately throws an error:

``````error[E0506]: cannot assign to `*num_ref` because it is borrowed
--> src/main.rs:9:5
|
8 |     check(&mut num_ref);
|           ------------ borrow of `*num_ref` occurs here
9 |     *num_ref = 42;
|     ^^^^^^^^^^^^^
|     |
|     assignment to borrowed `*num_ref` occurs here
|     borrow later used here
``````

This essentially means "`num_ref` is required to be alive here, since it's used; but `check` requires `&mut num_ref` which is alive as long as `num_ref` itself; so we can't assign to `*num_ref` - it is still exclusively borrowed by `check`".

I recently made the same mistake in another context.

we need to make sure when we're able to access `lfs` (that `Vec` ), all its contents' pointee (those `TreeNode` ) don't get erased,
which indicates `'b: 'a` imo
But I just mistakenly code the opposite ... 