Iterator returning items by reference, lifetime issue

Question

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 ?

Sanjak

Answer 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>.

Nieshanieto

Very helping answer. I must say 1- I'm struggling quite a lot to understand and correctly use lifetime/generic types/traits types specified in struct and traits and the ones used in methods, hence my bad use of 'a everywhere in this example. 2- I think I understand quite well your point, I tried to grep the Rust code and its libraries in order to find how a similar case was handled and what you said seems to correspond to several cases where a lifetime parameter is used in a struct with a referenced attribute like for instance the iterator for Splits in libcore/slice.rs. Thanks for your help – Sanjak

Sometimes you may find the examples in the standard library difficult to understand; for example, Items is actually something produced with a macro, so you need to understand the basics of Rust’s macros before you will be able to grok it! Be ready at all times to drop by irc://irc.mozilla.org/#rust, there are always people there to help. – Nieshanieto

I would note that there is an important reason for returning an item whose lifetime is not linked to the iterator: this allows implementing transformations in the iteration, which is something that is very hard to do in C++ for example. – Turning

This answer no longer works. Apparently RFC447 merged in 2015 broke it, I now get the error impl<'a> Iterator for Foo { // unconstrained lifetime parameter – Scorify

@JonasBerlin: this answer never contained functioning code, it just explained why what was being attempted wouldn’t work. – Nieshanieto