Untangling lifetimes

[jgarvin]

I ran into a lifetime issue i don't understand which I've reduced to this minimalish example:

#![allow(dead_code)]

struct ComplexOuterObject(i32);

impl ComplexOuterObject {
    fn complex_objects(&self) -> ComplexObjectIter {
        ComplexObjectIter {
            x: self,
            count: 0,
            obj: None,
        }
    }
}

struct ComplexInnerObject<'a>(i32, &'a ComplexOuterObject);

struct ComplexObjectIter<'a> {
    x: &'a ComplexOuterObject,
    count: i32,
    obj: Option<ComplexInnerObject<'a>>,
}

impl<'a> Iterator for ComplexObjectIter<'a> {
    type Item = &'a ComplexInnerObject<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        self.obj = Some(ComplexInnerObject(self.x.0 + self.count, self.x));
        self.count += 1;
        if self.count >= 3 {
            None
        } else {
            self.obj.as_ref()
        }
    }
}

fn main() {
    let v = vec![0, 1, 2];

    let outer = ComplexOuterObject(0);

    v.iter().zip(outer.complex_objects());
}

Error:

   Compiling playground v0.0.1 (/playground)
error: lifetime may not live long enough
  --> src/main.rs:32:13
   |
23 | impl<'a> Iterator for ComplexObjectIter<'a> {
   |      -- lifetime `'a` defined here
...
26 |     fn next(&mut self) -> Option<Self::Item> {
   |             - let's call the lifetime of this reference `'1`
...
32 |             self.obj.as_ref()
   |             ^^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

error: could not compile `playground` due to previous error

Playground link

rustc complains that the returned reference has the lifetime associated with &mut self, rather than &'a. However, both lifetimes are bound by the lifetime of ComplexOuterObject, references to which are what drive the need for having a lifetime annotation in the first place. AFAICT there is no safety issue?

[2e71828]

The fundamental problem here is that next() is modifying a single ComplexInnerObject and handing out references to it, but Iterator requires that all the items you yield be able to both coexist and outlive the iterator itself (i.e. .collect::<Vec<_>>() must be a valid operation).

In terms of lifetime annotations, 'a must outlive the iterator itself because it's a named parameter to ComplexObjectIter. But the iterator must outlive the anonymous lifetime of &mut self so that the reference doesn't dangle. self.obj.as_ref() returns a reference to the Option stored in the iterator, which can only be valid for the &mut lifetime, and not the longer 'a that you've declared in Item.

The simplest fix is to yield owned items instead of references (i.e., Item = ComplexInnerObject<'a>), but I don't know if that causes problems for your actual use case.

[jgarvin]

@2e71828

Iterator requires that all the items you yield be able to both coexist and outlive the iterator itself (i.e. .collect::<Vec<_>>() must be a valid operation).

Oops, I hadn't thought about outliving the Iterator. I see, if it didn't have to outlive the iterator the trait would be something like this right?:

trait Iterator {
    type Item<'a>;
    fn next(&'a mut self) -> Self::Item<'a>;
}

Which would then cause the borrow checker to enforce that you had dropped the returned item before the next next call.

[2e71828]

Right. That's generally known as a "lending iterator," and has only been made possible recently with the stabilization of generic associated types.

[H2CO3]

Right. You can see the independence of the item and the iterator by considering the desugaring of the trait definition with all lifetimes spelled out:

trait Iterator {
    type Item;

    fn next<'iter>(&'iter mut self) -> Option<Self::Item>;
}

As you can see, there is no relationship between the Item and the lifetime that annotates self.