Iterator returning a reference to itself

Question

I'm aware of Lifetime in Iterator impl, but I'd like some more detail to help me properly understand.

I want to write an infinite Iterator that returns &[0], &[0, 1], &[0, 1, 2], etc... . I'd like to write this:

struct Countings(Vec<usize>);

impl Countings {
    fn new() -> Countings { Countings(vec![]) }
}

impl Iterator for Countings {
    type Item = &[usize];

    fn next(&mut self) -> Option<Self::Item> {
        self.0.push(self.0.len());
        Some(self.0.as_slice())
    }
}

I can't because the type Countings::Item does not have a lifetime.

error[E0106]: missing lifetime specifier
 --> src/lib.rs:8:17
  |
8 |     type Item = &[usize];
  |                 ^ expected lifetime parameter

So I add one. It has to be bound by the impl Iterator. That, in turn, requires a lifetime parameter on struct Countings. So far, I'm here:

struct Countings<'a>(Vec<usize>);

impl<'a> Countings<'a> {
    fn new() -> Countings<'a> { Countings(vec![]) }
}

impl<'a> Iterator for Countings<'a> {
    type Item = &'a [usize];

    fn next(&mut self) -> Option<Self::Item> {
        self.0.push(self.0.len());
        Some(self.0.as_slice())
    }
}

Now I have a different error:

error[E0392]: parameter `'a` is never used
 --> src/lib.rs:1:18
  |
1 | struct Countings<'a>(Vec<usize>);
  |                  ^^
  |
  = help: consider removing `'a` or using a marker such as `std::marker::PhantomData`

I seriously consider it:

use std::marker::PhantomData;

struct Countings<'a>(Vec<usize>, PhantomData<&'a [usize]>);

impl<'a> Countings<'a> {
    fn new() -> Countings<'a> { Countings(vec![], PhantomData) }
}

impl<'a> Iterator for Countings<'a> {
    type Item = &'a [usize];

    fn next(&mut self) -> Option<Self::Item> {
        self.0.push(self.0.len());
        Some(self.0.as_slice())
    }
}

but to no avail:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:14:25
   |
14 |             Some(self.0.as_slice())
   |                         ^^^^^^^^

Question 1: What are the "conflicting requirements"?

Question 2: The answer cited above says that Item must borrow from something that the Iterator wraps. I have read the source for std::slice::Windows which is a good example. However, in my case I want to mutate the Vec each time next() is called. Is that possible?

score 2 · Accepted Answer · edited May 23 '17 at 10:32

Question 1: What are the "conflicting requirements"?

The borrow you try to return does not have lifetime 'a, as promised. Rather, it has the same lifetime as self. If the signature for next was written in full, it would be:

fn next<'b>(&'b mut self) -> Option<&'a [usize]>

Returning an Option<&'b [usize]> (with lifetime 'b instead of 'a) would be valid if it weren't for the fact that it violates the contract for the Iterator trait. However, it would freeze self until the result is dropped; i.e. you could not call next twice and use the result of both calls together. That's because each call to next can potentially invalidate the previously returned slices; pushing to a Vec can relocate the storage in memory to make room for additional elements, so the pointers in the slices would no longer be valid.

Question 2: The answer cited above says that Item must borrow from something that the Iterator wraps. I have read the source for std::slice::Windows which is a good example. However, in my case I want to mutate the Vec each time next() is called. Is that possible?

It's not possible to do this with the Iterator trait, so you won't be able to use a for loop on your struct. However, you can do it (with the caveat mentioned above) with an ordinary method.

struct Countings(Vec<usize>);

impl Countings {
    fn new() -> Countings { Countings(vec![]) }

    fn next<'a>(&'a mut self) -> &'a [usize] {
        let item = self.0.len();
        self.0.push(item);
        self.0.as_slice()
    }
}

score 2 · Answer 2 · answered Nov 07 '16 at 10:52

As Francis mentioned, it is not possible to modify the underlying vector during iteration. However, if you were to somehow have the possibility to specify the iteration bound, then things would be much easier:

You would create the vector [0, 1, 2, ...]
And then create an iterator that returns an ever-growing slice, up to the length of the vector

Just the iterator:

struct EverGrowingIterator<'a, T: 'a> {
    slice: &'a [T],
    current: usize,
}

impl<'a, T> Iterator for EverGrowingIterator<'a, T> {
    type Item = &'a [T];

    fn next(&mut self) -> Option<&'a [T]> {
        if self.current >= self.slice.len() {
            None
        } else {
            self.current += 1;
            Some(&self.slice[0..self.current])
        }
    }
}

And then:

fn ever_growing<'a, T>(slice: &'a [T]) -> EverGrowingIterator<'a, T> {
    EverGrowingIterator { slice: slice, current: 0 }
}

fn main() {
    let v = vec![0, 1, 2];
    for s in ever_growing(&v) {
        println!("{:?}", s);
    }
}

Will print:

[0]
[0, 1]
[0, 1, 2]

If you need to adapt this for infinite growth, you need to look into creating a custom container (not a Vec) that will grow while preserving references to previous slices. Something like a RefCell<Vec<Box<[T]>>> could be used.

Thanks. Your answer has some useful stuff. If I could accept both answers I would, but I think Francis's answer is better focused on my two questions. — apt1002, Nov 07 '16 at 19:48

Iterator returning a reference to itself

2 Answers2