Stuck on impl iterator and life times

I am confused about lifetimes and iterators.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=221a69fc535d38a58eeb013126a92f0a

I want to return an iterator from an inner vector for a struct. All works well when I return an option, using find, but the roughly equivalent code with filter fails.

I cannot see how one of these methods works but the other doesn't.

Here's the error for reference:

error[E0623]: lifetime mismatch
 --> src/lib.rs:8:42
  |
8 |     fn filter_s<'a>(&self, s:&String) -> impl Iterator<Item=& String>{
  |                              -------     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |                              |           |
  |                              |           ...but data from `s` is returned here
  |                              this parameter and the return type are declared with different lifetimes...

Here's why your second function is problematic. The signature of Iterator::filter looks like this:

pub fn filter<P>(self, predicate: P) -> Filter<Self, P> where
    P: FnMut(&Self::Item) -> bool, 

The return type is Filter<Self, P>. This is a type that holds your original iterator (self) in one field and the predicate/filtering function in another. Filter<Self, P> is a fully-fledged type: you could assign it to a variable, store it in a struct, etc.

Now, you're passing a closure |i| i == &s to the filter. A closure is not quite the same thing as a normal function (the thing you write with the fn keyword): it can capture local variables from the scope it's written in and carry that data around to use when you eventually call it (potentially more than once). Here, your closure captures the local variable s. A consequence of this is that the closure can only exist as long as the reference s: &String is valid.

To see how this causes a compiler error, look again at the type signature you wrote for filter_s:

fn filter_s<'a>(&self, s: &String) -> impl Iterator<Item = &String>

First of all, you never use the lifetime parameter 'a, so we can get rid of it.

fn filter_s(&self, s: &String) -> impl Iterator<Item = &String>

Now let's expand all the implicit lifetimes following the elision rules:

fn filter_s<'av, 's>(&'av self, s: &'s String) -> impl Iterator<Item = &'av String> + 'av

(I'm actually not 100% sure how lifetime elision works for impl Trait in return position; this is my guess based on the compiler's feedback.)

This signature is incompatible with the body you've written for filter_s, because the returned iterator (Filter<Self, P>) contains a closure that captures the reference s, so its lifetime is bounded by 's, not just by 'av. A type signature that's compatible with the body of the function is this:

fn filter_s<'b>(&'b self, s: &'b String) -> impl Iterator<Item = &'b String>

That tells the compiler that the same lifetime 'b governs the borrows self and s, so it can use 'b to bound the lifetime of the returned iterator. You will also need to add the move keyword in front of the closure so that it captures s by value instead of by reference.

Oh yes, of course. It's not the life time of the returned Strings that is being worried about, but the lifetime of the thing we are matching it to.

I think that this lifetime will work for my use-case, but even if it doesn't in my real code I am using an Rc value so I could always just clone s.

Thank you very much!

Applying the rules of lifetime elision to your filter function, we get:

fn filter_s<'a, 'b>(&'a self, s: &'b String) -> impl Iterator<Item= &'a String> {
    self.0.iter().filter(|i| i == &s)
}

You're returning an iterator over something in self, so the association of 'a with the output lifetime is correct. However, the iterator is also holding on to the s reference, so it must be limited by 'b as well. So, we can unify the lifetimes (the shorter of the two input lifetimes will result):

fn filter_s<'a>(&'a self, s: &'a String) -> impl Iterator<Item= &'a String> {
    self.0.iter().filter(|i| i == &s)
}

We still get an error, but it's a new error. s gets thrown out at the end of this function, but the iterator needs to hold on to it. We follow the error advice and make the filter closure a move closure:

fn filter_s<'a>(&'a self, s: &'a String) -> impl Iterator<Item= &'a String> {
    self.0.iter().filter(move |i| i == &s)
}

And now the borrow checker is satisfied.

Why does the other function work? Let's apply the rules of elision again:

fn find_s<'a, 'b>(&'a self, s: &'b String) -> Option<&'a String> {
    self.0.iter().find(|i| i == &s)
}

Here, the iterator runs to completion within the body of find_s and the output is returned. We're not returning the iterator, so we're not returning the closure. Once the function has finished, we don't need s any more. So we don't need to move it into the closure, and it doesn't limit any references in our return value either. Thus, the output need not be limited by 'b. So everything works fine.

1 Like

Note that while this may compile, it may be too restrictive depending on what you're trying to do. In particular the signature constrains the lifetime of the items yielded to the lifetime of s, even though that's not actually true.

For example this code could compile, but due to this additional restraint it doesnt:

fn foo(av: &Av) -> Vec<&String> {
    av.filter_s(&String::new()).collect()
}

However if you define filter_s like this, it will compile:

fn filter_s<'a: 'b, 'b>(&'a self, s: &'b String) -> impl Iterator<Item=&'a String> + 'b {
    self.0.iter().filter(move |i| i == &s)
}

This tell the compiler that the iterator is borrowing both self and s, but for the lifetime of s (so still allowing the borrow of self, and with that the lifetime of the returned references, to be longer than the one of s):

Another way would be to give each type a different lifetime and describe all the relations in the where clauses. It sometimes help me understand better what's going on:

fn filter_s<'a, 'b, 'c, 'd>(&'a self, s: &'b String) -> impl Iterator<Item=&'d String> + 'c
where
    'a: 'c, // Because the returned value borrows from `self`
    'b: 'c, // Because the returned value borrows from `s`
    'a: 'd, // Because the yielded items borrow from `self`
    'd: 'c, // I'm not quite sure about this one but I think it's because the return type must be well formed
{
    self.0.iter().filter(move |i| i == &s)
}
4 Likes

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.