Why `Vec`'s `.iter()` iterator can outlive the lifetime of the reference use to construct it?

help
1

I tried to design a trait that can be implemented for any tree so that I can adapt it to any tree from other crates to perform traversal operations on it. I have come up with something like this

// I could make this dyn compatible later
pub trait NodeView: Sized {
    // Some tree may error like fs::read_dir()
    type Err;
    type ChildIter<'c>: Iterator<Item = Result<Self, Self::Err>> + 'c
    where
        Self: 'c;
    fn children<'c>(&'c self) -> Result<Self::ChildIter<'c>, Self::Err>;
    fn parent(&self) -> Result<Option<Self>, Self::Err>;
}

But I encountered lifetime error:

fn dfs_api_test<T: NodeView>(a: T)
where
    T::Err: Debug,
    T: Debug,
{
    let c = a.children().unwrap();
    let mut stack = vec![];
    stack.push(c);
    while let Some(cur) = stack.pop() {
        for item in cur {
            let node = item.unwrap();
            // Do something with node...
            println!("We visited a node: {node:?}");
            let c = node.children().unwrap();
            stack.push(c);
        }
    }
}

error[E0597]: `node` does not live long enough
  --> tree_ast\src\lib.rs:80:21
   |
75 |     while let Some(cur) = stack.pop() {
   |                           ----- borrow later used here
76 |         for item in cur {
77 |             let node = item.unwrap();
   |                 ---- binding `node` declared here
...
80 |             let c = node.children().unwrap();
   |                     ^^^^ borrowed value does not live long enough
81 |             stack.push(c);
82 |         }
   |         - `node` dropped here while still borrowed

From my understanding, basically it is required that node have to be alive as long as c.
I tried to do something similar with a concrete type:

struct Node {
    value: String,
    children: Vec<Node>,
}

struct Descendants<'a> {
    stack: Vec<std::slice::Iter<'a, Node>>,
}

impl<'a> Iterator for Descendants<'a> {
    type Item = &'a Node;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(top_iter) = self.stack.last_mut() {
            if let Some(node) = top_iter.next() {
                if !node.children.is_empty() {
                    let c = &node.children; // Important part here
                    let iter = c.iter();
                    self.stack.push(iter);
                }
                return Some(node);
            } else {
                self.stack.pop();
            }
        }
        None
    }
}

In this snippet iter when expressed using opaque type, it should be impl Iterator + 'a

// Code from std
pub fn iter(&self) -> Iter<'_, T> {
    Iter::new(self)
}

However, self.stack.push(iter); complies without error. How is it allowed?
And in general, what is a good trait definition to generalize any tree-like data structure to traverse them?

2

Why Vec’s .iter() iterator can outlive the lifetime of the reference use to construct it?

It can’t. But it can live as long as the lifetime from the reference used to construct it. In particular, in your “concrete type” version, when you have a &'a Node and call node.children.iter(), that gets you an Iter<'a, Node> — the lifetime is equal.

On the other hand, your NodeView trait forces you to borrow the view again:

    fn children<'c>(&'c self) -> Result<Self::ChildIter<'c>, Self::Err>;

This means you have to supply it a &'c &'a Node and the child iter only lives for 'c, which lifetime is only valid as long as the &'a Node — not the Node — you borrowed continues to exist. That lifetime shortening is why your code doesn’t compile — your trait has given dfs_api_test an obligation to keep node alive, but you haven’t done that (and can’t do that in a non-recursive implementation).

A trait definition without this problem might be:

pub trait NodeView: Sized {
    type Err;
    type ChildIter: Iterator<Item = Result<Self, Self::Err>>;
    fn children(self) -> Result<Self::ChildIter, Self::Err>;
    fn parent(self) -> Result<Option<Self>, Self::Err>;
}

Note that self is taken by value, and no lifetimes appear because the lifetimes are all in the implementation, not the trait.

4 Likes
3

Thank you for the insight. Let the method take self solve the dfs_api_test obligation to keep node alive. However I still couldn't understand when I have a &'a Node and calling node.children.iter() will return Iter<'a, T> instead of Iter<'b, T> where 'b is a anonymous lifetime introduced by reborrowing node.children and 'b should end after the if block

4

Sorry, I can’t follow that sentence enough to tell exactly what you want me to explain. Does this help?

In the code that does not compile, dfs_api_test is trying to store T::ChildIter<'c>s in the stack. But 'c in that type is a lifetime of the borrow created by the node.children() method call, which cannot outlive the variable node, so it cannot be stored in stack which is outside the loop.

The part which actually creates the problem is that you linked the two lifetimes in fn children. It might be that the code will compile if you simply unlink them, allowing them to vary independently:

fn children<'c1, 'c2>(&'c1 self) -> Result<Self::ChildIter<'c2>, Self::Err>;

But if you do that, the lifetime on the ChildIter type has no actual purpose, so it should be removed. The change from &self to self isn't actually necessary, just tidy.

Or so I think. I haven't actually tested this, because you did not provide code for an impl of the NodeView trait.

5

Sorry if the question is unclear, the change you proposed to the trait works perfectly and dfs_api_test complies after the changes. The question refers to the concrete type example where node.children.iter() could be stored in the stack. But I think I get it now after looking at the signature of Iter<'a, T> again:

core::slice::iter::Iter
impl<'a, T> Iterator for Iter<'a, T>
fn next(&mut self) -> Option<&'a T>

Turns out that it returns the original lifetime instead of the self lifetime. I assume it would be something like this

fn next<'this>(&'this mut self) -> Option<&'this T>