Lifetime and associated types

Question

I have this enum:

enum Node<T> {
    Leaf(T),
    Children(Vec<Node<T>>),
}

And want to implement the Iterator trait for Node. I created this struct and tried to implement the IntoIterator trait:

struct NodeIter<'a, T>{
    children: &'a [Node<T>],
    parent: Option<&'a Node<T>>,
}

impl<'a, T> IntoIterator for Node<T> {
    type Item = T;
    type IntoIter = NodeIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        todo!()
    }
}

I can not figure out the correct lifetime specifiers, I end up getting this error:

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

I am new to Rust and I am not sure if I am doing it wrong or if it is not possible. Because I have read about similar problems. The problem seems to have something to do with traits (IntoIterator in my case) and associated types. I also read something about GAT.

Maybe someone could explains this problem and how one would solve it.

Rust Playground

Answer 1

IntoIterator::into_iter consumes its argument. This means that once you've called node.into_iter() the node no longer exists, but it looks like you want your NodeIter to keep references to node which is impossible since it's no longer around.

You will need to either change NodeIter to take ownership of the original Node so that NodeIter can keep the Node alive for as long as it needs it, or implement IntoIter for references to Node (which will consume the reference, but keep the original Node intact):

enum Node<T> {
    Leaf(T),
    Children(Vec<Node<T>>),
}

struct NodeIter<'a, T>{
    children: &'a [Node<T>],
    parent: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for NodeIter<'a, T> {
    type Item = T;
    fn next (&mut self) -> Option<Self::Item> {
        todo!();
    }
}

impl<'a, T> IntoIterator for &'a Node<T> {
    type Item = T;
    type IntoIter = NodeIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        todo!()
    }
}

Playground