Iterator lifetime issue when returning references to inner collection

Question

I have a struct that lazily load data into an inner vector (but for the example this is ommited). Then I am implementing IntoIterator and Iterator for the IntoIterator type:

struct EntryOwned(u32);
struct Entry<'a>(&'a u32);

impl<'a> EntryOwned {
    fn to_entry(&'a self) -> Entry<'a> {
        Entry(&self.0)
    }
}

struct LazyStruct {
    cache: Vec<EntryOwned>,
}

impl<'a> LazyStruct {
    fn new(data: Vec<EntryOwned>) -> LazyStruct {
        Self {
            cache: data,
        }
    }

    fn get_entry(&'a self, index: usize) -> Option<Entry<'a>> {
        match self.cache.get(index) {
            Some(entry_owned) => Some(entry_owned.to_entry()),
            None => None,
        }
    }
}

impl<'a> IntoIterator for &'a mut LazyStruct {
    type Item = Entry<'a>;
    type IntoIter = LazyStructIter<'a>;

    fn into_iter(self) -> Self::IntoIter {
        LazyStructIter {
            inner: self,
            current_index: 0,
        }
    }
}

struct LazyStructIter<'a> {
    inner: &'a mut LazyStruct,
    current_index: usize,
}

impl<'a> LazyStructIter<'a> {
    fn next_item(&'a mut self) -> Option<Entry<'a>> {
        if self.current_index > self.inner.cache.len() {
            return None;
        }
        let ret = self.inner.get_entry(self.current_index);
        self.current_index += 1;
        ret
    }
}

impl<'a> Iterator for LazyStructIter<'a> {
    type Item = Entry<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        self.next_item()
    }
}

Which yields me to a lifetime issue:

   Compiling playground v0.0.1 (/playground)
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/main.rs:64:14
   |
64 |         self.next_item()
   |              ^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 63:5...
  --> src/main.rs:63:5
   |
63 | /     fn next(&mut self) -> Option<Self::Item> {
64 | |         self.next_item()
65 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:64:9
   |
64 |         self.next_item()
   |         ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 60:6...
  --> src/main.rs:60:6
   |
60 | impl<'a> Iterator for LazyStructIter<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src/main.rs:64:14
   |
64 |         self.next_item()
   |              ^^^^^^^^^
   = note: expected  `&mut LazyStructIter<'_>`
              found  `&mut LazyStructIter<'a>`

The lifetime of the references should be bind to the LazyStruct, but I cannot change the Iter trait do not accept any lifetime specifier. I have already check some answers to similar issues: Iterator returning items by reference, lifetime issue How do I write an iterator that returns references to itself?

EDIT: The Entry is a more complex data structure and it is not possible to copy it. I have to bind it to a specific lifetime since it contains references to things.

One of them points that the iterator should hold a reference to the original collection instead of owning it since it is not allowed to return a reference with the self lifetime. But I could't make it work. So, how should I play the references here?

Here is the playground example

Any help is more than welcome, thank you all in advance!

What you're looking for is called a streaming iterator. docs.rs/streaming-iterator/0.1.5/streaming_iterator — Optimistic Peach
@OptimisticPeach, Thanks for the info. I do want exactly that. I already read about it before. The problem is that I am bound to implement Iterator. (This was just the example). — Netwave

attdona attdona · Accepted Answer · 2020-03-23T08:51:24

You can't.

You require that each item returned by next() has a reference with a lifetime tied to the existence of the LazyStructIter iterator.

This it is not possible with the Iterator interface:

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;

But it would be possible with a trait defined as:

trait FakeIterator<'a> {
    type Item;

    fn next(&'a mut self) -> std::option::Option<Self::Item>;
}

impl<'a> FakeIterator<'a> for LazyStructIter<'a> {
    type Item = Entry<'a>;

    fn next(&'a mut self) -> Option<Self::Item> {
        self.next_item()
    }
}

Tha capability to have a kind of iterator which returns items borrowing from self is the goal of RFC 1598 - GAT.

See also this article for a collection of workarounds about this topic.

Iterator lifetime issue when returning references to inner collection

2 Answers