Cannot implement IntoIterator for generic `enum`

[vmg]

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!

[2e71828]

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

[H2CO3]

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(),
        }
    }
}

[vmg]

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.

[H2CO3]

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.

[ratmice]

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.

[H2CO3]

Very nice!