Unconstrained Lifetime in Iterator Impl

[tomhamiltonlambda]

I'm trying to impl an iterator over a Grid structure. The iterator must outlive the grid, and I've implemented almost everything - the problem I've got is that the compiler is complaining about the lifetime in the line:

impl<'a, T: Clone + Eq + PartialEq + Default> IntoIterator for Grid<T>

which is the bottom impl. The error message is:

the lifetime parameter 'a is not constrained by the impl trait, self type, or predicates
unconstrained lifetime parameter

I don't understand a.) why it's showing up (I've included constraints in the methods within the impl block) or b.) how to fix. I thought I needed to include lifetimes because my iterator is non-owning - it's referencing back to the owned Vec - using its .iter() method. Is the fix to add a lifetime parameter to my Grid and then everything else that that references... (real pain)?

struct Grid<T> {
    values: Vec<T>,
    cols: usize
}

struct GridIterator<'a, T: Clone + Eq + PartialEq + Default> {
    cols: usize,
    index: usize,
    values: dyn Iterator<Item = &'a T>,
}

impl<'a, T: Clone + Eq + PartialEq + Default> Iterator for GridIterator<'a, T> {
    type Item = Cell<&'a T>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.values.next() {
            None => None,
            Some(value) => {
                let row = self.index / self.cols;
                let col = self.index % self.cols;
                self.index += 1;
                Some(Cell { row, col, value })
            }
        }
    }
}

impl<'a, T: Clone + Eq + PartialEq + Default> IntoIterator for Grid<T> {
    type Item = Cell<&'a T>;
    type IntoIter = GridIterator<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        GridIterator {
            cols: self.cols,
            index: 0,
            values: self.values.iter(),
        }
    }
}

[2e71828]

You probably want:

//                                                             vvv
impl<'a, T: Clone + Eq + PartialEq + Default> IntoIterator for &'a Grid<T> {

[kpreid]

@tomhamiltonlambda

The iterator must outlive the grid

Then the iterator must return owned values, T not &'a T. An Iterator cannot return borrows of its own data. The “unconstrained lifetime” is a symptom of this problem: the struct and impl Iterator are written so that 'a would be the lifetime of what it's borrowing, but the impl IntoIterator hasn't got anything specific to borrow to create the iterator.

    fn into_iter(self) -> Self::IntoIter {
        GridIterator {
            cols: self.cols,
            index: 0,
            values: self.values.iter(),
        }
    }

This code will not compile regardless of lifetime annotations, because self.values.iter() borrows self, but self is being dropped at the end of the function. You have to work with self.values.into_iter() instead, as long as you want the iterator to outlive the grid.

[tomhamiltonlambda]

Sorry I wrote the complete opposite of what I meant - the grid must outlive the iterator - I was just struggling to show that using lifetimes!

[kpreid]

OK, then @2e71828's suggestion is correct.

Here's a complete fixed version of your code. Note that I also replaced dyn Iterator — being a dynamically-sized type, it would have prevented actually constructing the struct unless you changed it to have a Box wrapper, and you don't really need dyn here.

struct Grid<T> {
    values: Vec<T>,
    cols: usize,
}

struct Cell<T> {
    row: usize,
    col: usize,
    value: T,
}

struct GridIterator<'a, T: 'a> {
    cols: usize,
    index: usize,
    values: std::slice::Iter<'a, T>,
}

impl<'a, T: 'a> Iterator for GridIterator<'a, T> {
    type Item = Cell<&'a T>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.values.next() {
            None => None,
            Some(value) => {
                let row = self.index / self.cols;
                let col = self.index % self.cols;
                self.index += 1;
                Some(Cell { row, col, value })
            }
        }
    }
}

impl<'a, T: 'a> IntoIterator for &'a Grid<T> {
    type Item = Cell<&'a T>;
    type IntoIter = GridIterator<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        GridIterator {
            cols: self.cols,
            index: 0,
            values: self.values.iter(),
        }
    }
}