“does not live long enough” error when iterating t

Question

I'm trying to create a linked list and an iterator to iterate through the list.

enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

struct ListIterator<'a, T:'a> {
    cur: &'a List<T>
}

impl<'a, T> Iterator<T> for ListIterator<'a, T> {
    fn next(&mut self) -> Option<T>{
        match self.cur {
            &Cons(val, next) => {self.cur = &*next; Some(val)},
            &Nil => None
        }
    }
}

But I get the following error:

error: `*next` does not live long enough

Answer 1

The error message points to a real issue, but there is actually another one that the compiler should report instead because it comes earlier. In your match arm

&Cons(val, next) => {self.cur = &*next; Some(val)},

you are trying to destructure a List object into &Cons(val,next) which is an attempt to move val and next out from behind a borrowed pointer. This is not allowed. But if it were, val and next would be local variables with a rather short lifetime. The error message you see is because of that: next would be a local box that is about to be dropped. Hence the type of &*next is a reference with a lifetime parameter referring to the lifetime of this local box. And that's too short to return it.

This calls for the use of ref and box patterns:

&Cons(ref val, box ref next) => { self.cur = next; Some(*val) },

Now, val is of type &T and next is of type &List where both are references into your list data structure and nothing is moved out. Note also, that Some(*val) requires T to be Copy:

impl<'a, T: Copy> Iterator<T> for ListIterator<'a, T> {
...

But Copy is quite a requirement. A more general way would be to use Clone like this:

impl<'a, T: Clone> Iterator<T> for ListIterator<'a, T> {
...
    &Cons(ref val, box ref next) => { self.cur = next; Some((*val).clone()) },

This works for more types. And if you don't want to clone the values, you could also make your iterator yield &T instead of T just like it's done with vectors and slices.