Iterator returning items by reference, lifetime issue

I have a lifetime issue, I'm trying to implement an iterator returning its items by reference, here is the code:

struct Foo {
   d: [u8; 42],
   pos: usize
}

impl<'a> Iterator<&'a u8> for Foo {
   fn next<'a>(&'a mut self) -> Option<&'a u8> {
      let r = self.d.get(self.pos);
      if r.is_some() {
         self.pos += 1;
      }
      r
   }
}

fn main() {
   let mut x = Foo {
      d: [1; 42],
      pos: 0
   };

   for i in x {
      println!("{}", i);
   }
}

However this code doesn't compile properly, I get an issue related to the lifetime of parameters, here is the corresponding error:

$ rustc test.rs
test.rs:8:5: 14:6 error: method `next` has an incompatible type for trait: expected concrete lifetime, but found bound lifetime parameter
test.rs:8     fn next<'a>(&'a mut self) -> Option<&'a u8> {
test.rs:9         let r = self.d.get(self.pos);
test.rs:10         if r.is_some() {
test.rs:11             self.pos += 1;
test.rs:12         }
test.rs:13         r
           ...
test.rs:8:49: 14:6 note: expected concrete lifetime is the lifetime 'a as defined on the block at 8:48
test.rs:8     fn next<'a>(&'a mut self) -> Option<&'a u8> {
test.rs:9         let r = self.d.get(self.pos);
test.rs:10         if r.is_some() {
test.rs:11             self.pos += 1;
test.rs:12         }
test.rs:13         r
           ...
error: aborting due to previous error

Does somebody has an idea how to fix this issue and still returning items by reference?

At least what does this message means: expected concrete lifetime, but found bound lifetime parameter ?

Solution 1:

Note on the version of Rust used: at the time this question and answer were written, the Iterator trait used generics; it has changed to use associated types and is now defined thus:

pub trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
    …
}

And so the incorrect implementation shown here would be like this:

impl<'a> Iterator for Foo {
    type Item = &'a u8;

    fn next<'a>(&'a mut self) -> Option<&'a u8>;
}

In practical terms this affects nothing; it is merely that A becomes Self::Item.

The definition of the Iterator trait is thus:

pub trait Iterator<A> {
    fn next(&mut self) -> Option<A>;
    …
}

Note carefully: fn next(&mut self) -> Option<A>.

Here is what you have:

impl<'a> Iterator<&'a u8> for Foo {
    fn next<'a>(&'a mut self) -> Option<&'a u8>;
}

Note carefully: fn next<'a>(&'a mut self) -> Option<&'a u8>.

There are several problems here:

1. You have introduced a new generic parameter <'a> which should not be there. For convenience’s sake and to emphasise what has happened here, I shall dub the 'a defined on the impl block ρ₀ and the 'a defined on the method ρ₁. They are not the same.

2. The lifetime of &mut self is different from that of the trait.

3. The lifetime of the return type is different to the trait: where A is &'ρ₀ u8, the return type uses in the place of A &'ρ₁ u8. It expected the concrete lifetime ρ₀ but found instead the lifetime ρ₁. (I’m not certain precisely what the “bound” bit means, so I’ll keep quiet on it lest I be wrong.)

Here’s what this amounts to: you cannot connect the lifetime of the object you are iterating over to &mut self. Instead, it must be bound to something in the type you are implementing the trait for. To take an example, iterating over items in a slice is done by creating a new iterator object connected to the base slice, impl<'a, T> Iterator<&'a T> for Items<'a, T>. Expressed in another way, the way the iteration traits are designed is not, if you are producing references, for you to return something inside self, but rather to return something inside another object that you have a reference to.

For your specific, presumably simple example, you should either stop yielding references, or alter it so that your iterator object does not contain the data that you are iterating over—let it merely contain a reference to it, e.g. &'a [T] or even something like Items<'a, T>.