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

My question is about lifetime constraint:

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.

Thansk for reply!

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

seems my understanding is correct!

But I just mistakenly code the opposite ...:sob: