How do I return a reversed iterator?

Question

I was writing some code where I want to use an iterator, or its reversed version depending on a flag, but the straightforward code gives an error

pub fn eggs<I,T>(iter:I)->Box<dyn Iterator<Item=T>>
where I:Iterator<Item=T>+DoubleEndedIterator
{
    Box::new(iter.rev())
}

pub fn bacon<I,T>(iter:I, reverse:bool) -> Box<dyn Iterator<Item=T>>
    where I:Iterator<Item=T>+DoubleEndedIterator
{
    if reverse {
        Box::new(iter.rev())
    } else {
        Box::new(iter)
    }

}

fn main()
{
    let pants:String = "pants".into();
    eggs(pants.chars());
}

fails to compile:

error[E0310]: the parameter type `I` may not live long enough
 --> src/main.rs:5:5
  |
2 | pub fn eggs<I,T>(iter:I)->Box<dyn Iterator<Item=T>>
  |             - help: consider adding an explicit lifetime bound...: `I: 'static`
...
5 |     Box::new(iter.rev())
  |     ^^^^^^^^^^^^^^^^^^^^ ...so that the type `Rev<I>` will meet its required lifetime bounds

With my limited understanding of Rust, I'm not sure where those lifetime bounds are coming from. There aren't any on the Iterator trait, or the Rev struct, and the parameter is being moved.

What is the proper way to declare these sorts of functions given that 'static isn't really an option.

rust playground

Answer 1

This doesn't have to do with .rev() at all, but with returning Box<dyn Iterator>:

// error[E0310]: the parameter type `I` may not live long enough
fn boxed_iter<I, T>(iter: I) -> Box<dyn Iterator<Item = T>>
//            - help: consider adding an explicit lifetime bound...: `I: 'static`
where
    I: Iterator<Item = T>,
{
    Box::new(iter)
//  ^^^^^^^^^^^^^^ ...so that the type `I` will meet its required lifetime bounds
}

The reason for this is that trait objects like Box<dyn Trait> have an implicit 'static lifetime if not specified. So when the compiler tries to cast Box<I> to Box<dyn Iterator>, it fails if I is does not also have a 'static lifetime. (There are some more specific rules if the trait contains lifetimes itself; you can read about those in more detail here.)

If you instead want a shorter lifetime, you need to specify it explicitly as Box<dyn 'a + Trait>. So for example:

fn boxed_iter<'a, I, T>(iter: I) -> Box<dyn 'a + Iterator<Item = T>>
where
    I: 'a + Iterator<Item = T>,
{
    Box::new(iter)
}

Answer 2

Frxstrem's answer is excellent. I just want to add that, if you know that the return value of your function has a specific concrete type, you can use the special impl trait syntax.

In the case of your eggs function, the return type is probably something like Rev<I>. That type, on its own, isn't very illuminating, but we know that such a type exists and the only thing we care about is that it's an iterator, so we can write

pub fn eggs<I,T>(iter:I) -> impl Iterator<Item=T> + DoubleEndedIterator
where I: Iterator<Item=T> + DoubleEndedIterator {
  iter.rev()
}

Now the compiler still understands that there is a single concrete type and will act accordingly (no need to box the value or have dynamic dispatch), but we as the programmers still only have to care about the Iterator and DoubleEndedIterator aspects of it. Zero-cost abstraction at its finest.

Your bacon function can't benefit from this, as it could return either an I or a Rev<I> depending on input, so the dynamic dispatch is actually necessary. In that case, you'll need to follow Frxstrem's answer to correctly box your iterator.