How can I return an impl Iterator that has multiple lifetimes?

Question

I'm having trouble with lifetimes on an impl trait. I'm trying to get the following code to work:

struct Foo<'op, Input> {
    op: Box<dyn Fn(Input) -> i32 + 'op>,
}

impl<'op, Input> Foo<'op, Input> {
    fn new<Op>(op: Op) -> Foo<'op, Input>
    where
        Op: Fn(Input) -> i32 + 'op,
    {
        Foo { op: Box::new(op) }
    }

    fn apply<'input_iter, InputIter>(
        self,
        input_iter: InputIter,
    ) -> impl Iterator<Item = i32> + 'op + 'input_iter
    where
        InputIter: IntoIterator<Item = Input> + 'input_iter,
    {
        input_iter.into_iter().map(move |input| (self.op)(input))
    }
}

(Playground)

This is giving me the following error:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src/lib.rs:20:36
   |
20 |         input_iter.into_iter().map(move |input| (self.op)(input))
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime 'op as defined on the impl at 5:6...
  --> src/lib.rs:5:6
   |
5  | impl<'op, Input> Foo<'op, Input> {
   |      ^^^
   = note: ...so that the types are compatible:
           expected Foo<'_, _>
              found Foo<'op, _>
note: but, the lifetime must be valid for the lifetime 'input_iter as defined on the method body at 13:14...
  --> src/lib.rs:13:14
   |
13 |     fn apply<'input_iter, InputIter>(
   |              ^^^^^^^^^^^
note: ...so that return value is valid for the call
  --> src/lib.rs:16:10
   |
16 |     ) -> impl Iterator<Item = i32> + 'op + 'input_iter
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Here's my understanding of the lifetimes involved. Foo owns an op, which is a closure that may have a reference in it somewhere, so it may have a bound lifetime. This is denoted by 'op, and Foo is constrained such that it can't outlive it. So far, so good.

In apply(), the idea is that we want to consume an input_iter and self and return an iterator of each element in input_iter mapped using self.op. input_iterator may also contain references, so it may have its own lifetime bounds, denoted by 'input_iter.

What I want is to return an iterator that takes ownership of both self and input_iter. In doing so, it would have to take on both of their lifetime parameters to ensure that it didn't outlast either the input_iter references or the op references. I thought impl Iterator<Item = i32> + 'op + 'input_iter would accomplish this, but I seem to have taken a wrong turn somewhere.

It's also weird that it's complaining about the closure. I understand that the closure can't outlive 'op, because it takes ownership of the operator and its references. That makes perfect sense. What I don't understand is why it needs to live as long as 'input_iter. The closure and the input iterator shouldn't care about each other at all; the only thing connecting them is that they both have the same owner (the output iterator).

What am I missing here?

Francis Gagné Francis Gagné · Accepted Answer · 2019-10-20T02:43:27

Lifetime parameters don't always represent the exact lifetime of an object (or of a borrow). Let's consider this example:

fn main() {
    let a = 3;
    let b = 5;
    let c = min(&a, &b);
    println!("{:?}", c);
}

fn min<'a>(a: &'a i32, b: &'a i32) -> &'a i32 {
    if a < b {
        a
    } else {
        b
    }
}

Here, min takes two reference arguments with the same lifetime. However, we call it with borrows of different variables, which have different lifetimes. So why does this code compile?

The answer is subtyping and variance. Larger lifetimes are subtypes of shorter lifetimes; conversely, shorter lifetimes are supertypes of larger lifetimes. In the example above, the compiler has to find one lifetime that is compatible with both input lifetimes. The compiler does this by finding the common supertype of both lifetimes (i.e. the shortest lifetime that contains both). This is called unification.

Back to your problem. It seems like the compiler doesn't handle multiple lifetime bounds on impl Trait too well at the moment. However, there's no real need to have two lifetime bounds: one is enough. The compiler will shorten this single lifetime if necessary to satisfy the requirements of both self and input_iter.

struct Foo<'op, Input> {
    op: Box<dyn Fn(Input) -> i32 + 'op>,
}

impl<'op, Input> Foo<'op, Input> {
    fn new<Op>(op: Op) -> Foo<'op, Input>
    where
        Op: Fn(Input) -> i32 + 'op,
    {
        Foo { op: Box::new(op) }
    }

    fn apply<InputIter>(
        self,
        input_iter: InputIter,
    ) -> impl Iterator<Item = i32> + 'op
    where
        Input: 'op,
        InputIter: IntoIterator<Item = Input> + 'op,
    {
        input_iter.into_iter().map(move |input| (self.op)(input))
    }
}

fn main() {
    let y = 1;
    let foo = Foo::new(|x| x as i32 + y);

    let s = "abc".to_string();
    let sr: &str = &*s;
    let bar = sr.chars();

    let baz: Vec<_> = foo.apply(bar).collect();
    println!("{:?}", baz);
}

Try moving the lines in main around to convince yourself that the lifetimes are indeed unified.

At this point, calling the lifetime 'op is somewhat misleading; it might as well be called 'a.

How can I return an impl Iterator that has multiple lifetimes?

1 Answers