Cannot implement IntoIterator for generic `enum`

Hey everyone, I'm seeing a rather strange lifetime error when trying to implement IntoIterator for a generic enum where all arms use a different container.

Here's a minimal reproduction recipe:

enum Enum<P> {
    Vec(Vec<P>),
    Queue(VecDeque<P>),
}

impl<P> IntoIterator for Enum<P> {
    type Item = P;
    type IntoIter = Box<dyn Iterator<Item = P>>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Self::Vec(v) => Box::new(v.into_iter()),
            Self::Queue(q) => Box::new(q.into_iter()),
        }
    }
}

The compiler complains about the lifetime of P, which is puzzling to me because P is always owned. Both Vec<P> and VecDeque<P> implement IntoIterator, and the return of those two implementations is always an Iterator<Item=P>, so I don't understand why it cannot be boxed and returned from the parent FromIterator.

error[E0310]: the parameter type `P` may not live long enough
--> src/test.rs:224:9
    |
219 |   impl<P> IntoIterator for Enum<P> {
    |        - help: consider adding an explicit lifetime bound...: `P: 'static`
...
224 | /         match self {
225 | |             Self::Vec(v) => Box::new(v.into_iter()),
226 | |             Self::Queue(q) => Box::new(q.into_iter()),
227 | |         }
    | |_________^ ...so that the type `std::collections::vec_deque::IntoIter<P>` will meet its required lifetime bounds

error[E0310]: the parameter type `P` may not live long enough
--> src/test.rs:225:29
    |
219 | impl<P> IntoIterator for Enum<P> {
    |      - help: consider adding an explicit lifetime bound...: `P: 'static`
...
225 |             Self::Vec(v) => Box::new(v.into_iter()),
    |                             ^^^^^^^^^^^^^^^^^^^^^^^ ...so that the type `std::vec::IntoIter<P>` will meet its required lifetime bounds

error: aborting due to 2 previous errors

I think the compiler's advice of adding a 'static lifetime is a red herring, but I don't know how to properly fix the issue. Any help is appreciated!

The root problem is that dyn Iterator has an implicit 'static lifetime. Normally, you'd fix it by specifying the lifetime explicitly, but I couldn't figure out how without getting another compile error. The closest I can get is:

impl<'a, P:'a> IntoIterator for Enum<P> {
    type Item = P;
    type IntoIter = Box<dyn Iterator<Item = P> + 'a>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Self::Vec(v) => Box::new(v.into_iter()),
            Self::Queue(q) => Box::new(q.into_iter()),
        }
    }
}

which produces this error:

error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
 --> src/lib.rs:8:6
  |
8 | impl<'a, P:'a> IntoIterator for Enum<P> {
  |      ^^ unconstrained lifetime parameter

(Playground)

What you really want to say is that 'a represents any lifetime for which P is valid, but I don't know how to express that in the type system. Unless I'm missing something, every named lifetime must come from:

  • 'static,
  • for<'a> ...,
  • a reference, or
  • an explicit type parameter

Looks like you'll need to do this using static dispatch (playground):

use std::collections::VecDeque;

enum Enum<P> {
    Vec(Vec<P>),
    Queue(VecDeque<P>),
}

enum IntoIter<P> {
    Vec(<Vec<P> as IntoIterator>::IntoIter),
    Queue(<VecDeque<P> as IntoIterator>::IntoIter),
}

impl<P> IntoIterator for Enum<P> {
    type Item = P;
    type IntoIter = IntoIter<P>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Self::Vec(v) => IntoIter::Vec(v.into_iter()),
            Self::Queue(q) => IntoIter::Queue(q.into_iter()),
        }
    }
}

impl<P> Iterator for IntoIter<P> {
    type Item = P;
    
    fn next(&mut self) -> Option<Self::Item> {
        match *self {
            IntoIter::Vec(ref mut it) => it.next(),
            IntoIter::Queue(ref mut it) => it.next(),
        }
    }
}

Oof, thanks for the answers folks. Static dispatch is something I considered, but it feels extremely inelegant to continuously match on every call to next() since the underlying iterator never changes.

It isn't "extremely inelegant", that's how enums are supposed to work. It might have a runtime cost, granted. Is it something that measurably matters in your use case? As long as it doesn't, you should probably just use static dispatch and an enum.

It looks like you can get it working with some sillyness,

In particular if you add the bounds on the enum,
and add a PhantomData for it (which could be in one of the existing variants, It just gets rid of a peculiar warning which says the lifetime is unused.

enum Never {}
enum Enum<'a, P: 'a>
{
    Vec(Vec<P>),
    Queue(VecDeque<P>),
    #[allow(unused)]
    Phantom(PhantomData<&'a Never>),
}

Then only some minor changes from your impl, adding the lifetime parameter to Enum<'a, P> and additional case...

impl<'a, P: 'a> IntoIterator for Enum<'a, P> {
    type Item = P;
    type IntoIter = Box<dyn Iterator<Item = P> + 'a>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Self::Vec(v) => Box::new(v.into_iter()),
            Self::Queue(q) => Box::new(q.into_iter()),
            Self::Phantom(_) => Box::new(std::iter::empty())
        }
    }
}

Kind of awkward, i'm uncertain why the run-around.

Edit: Should probably be an honest to goodness reference to never or Never<'a> or something, a Phantom IIRC allows you to actually construct one... since phantoms don't require evidence.

2 Likes

Very nice!