Storing an iterator over borrowed refs inside a Struct

Question

I'm new to Rust and like many finding lifetimes quite hard to get the hang of. I get the basics, but I can't quite fathom how to make this work.

I'm trying to implement an abstract data structure that holds a collection of records. One requirement is that the collection of records referenced by the data structure is represented as an Iterator, because at times the records will be read from disk, at other times they'll come from memory, and at other times somewhere like a cache. The data structure itself doesn't care how the records are returned. It simply needs to be able to iterate over them and filter/map them etc.

My actual code is more involved than this, but I've distilled this down as much as possible to illustrate the issue I'm hitting.

Let's say I have a type Record. It is not important what that is. If I have a Vec<Record> called records, then I can get an iterator over &Record instances, using records.iter() right? That's exactly what I need to store in a struct field, except that it needs to be abstract and not tied specifically to the implementation of Vec<T>.

I have tried to define a trait as such:

trait RecordIterator: Iterator<Item = &Record> {}

And the struct that holds trait objects of this type:

struct RecordSet {
    records_iter: Box<dyn RecordIterator>,
}

Of course this doesn't compile because I need to specify the lifetimes. The compiler suggests using higher rank lifetimes, so:

trait RecordIterator: for<'a> Iterator<Item = &'a Record> {}

impl<T> RecordIterator for T where T: for<'a> Iterator<Item = &'a Record> {}

But this gives me an error:

   Compiling playground v0.0.1 (/playground)
error[E0582]: binding for associated type `Item` references lifetime `'a`, which does not appear in the trait input types
 --> src/main.rs:3:40
  |
3 | trait RecordIterator: for<'a> Iterator<Item = &'a Record> {}
  |                                        ^^^^^^^^^^^^^^^^^

error[E0582]: binding for associated type `Item` references lifetime `'a`, which does not appear in the trait input types
 --> src/main.rs:5:56
  |
5 | impl<T> RecordIterator for T where T: for<'a> Iterator<Item = &'a Record> {}
  |                                                        ^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0582`.
error: could not compile `playground` due to 2 previous errors

Here is a link to the playground containing this code.

What do I need to do to store this kind of Iterator in the struct (as long as it is valid)? I'm also happy to avoid using Vec<T>::iter() entirely and construct a new Iterator that basically does the same thing but meets the compiler's expectations if that is necessary.

Does this answer your question? [How do I write an iterator that returns references to itself?](https://stackoverflow.com/questions/30422177/how-do-i-write-an-iterator-that-returns-references-to-itself) — drewtato, May 02 '23 at 05:05
TLDR is you can't make an iterator that gives out references to itself, so instead you implement `IntoIterator` and make another struct that will implement `Iterator`. — drewtato, May 02 '23 at 05:07
Side note, a type alias would probably better express your intentions than a trait: `type RecordIterator<'a> = dyn Iterator;`. Won't solve your issue though: if your iterator returns references, then _someone_ has to own the values. Question is: who does? — Jmb, May 02 '23 at 06:52
@drewtato I think that other question is not the same issue, but likely I'm not fully understanding the problem. The iterator doesn't return references to itself. It returns references to records, which can come from any kind of provider that is able to construct such records. — d11wtq, May 02 '23 at 07:24
@Jmb much nicer with the type alias, thank you. "if your iterator returns references, then someone has to own the values" — is this not what higher rank trait lifetime bounds are designed to solve? For example, if the iterator holds a `Vec`, then the refs `&T` that it yields have the same lifetime as the `Vec`. — d11wtq, May 02 '23 at 07:26
It is possible I don't actually need `&Record` and an owned `Record` will work just as well. One thing I wanted to be able to do was e.g. create new `RecordSet` instances based on some `map` or `filter` of another `RecordSet`, like: `RecordSet{records_iter: Box::new(some_other_record_set.records_iter.map( .... ))}`. If avoiding refs doesn't pose any complications for that kind of thing that's totally fine. I _should_ only need to iterate once. — d11wtq, May 02 '23 at 07:37
When you call `iterator.next()` and get a `&Record`, the compiler has to be able to track how long that `&Record` lives, and so needs to link its lifetime to that of the owner. This means having a specific lifetime that represents that link. — Jmb, May 02 '23 at 07:38
BTW, your playground example can be made to compile like [this](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3ebfa3eb99abe25dcc1d50e62eb19a2c). Not sure if that's useful for your actual use case, or if it only works in this simplified example. — Jmb, May 02 '23 at 07:40
As mentioned by @Jmb, you're trying to define a trait that depends on a lifetime that is not part of the trait input types. It is illegal in Rust. — Jishan Shaikh, May 02 '23 at 07:55
Is there maybe a more Rust-like way to model this? The core of the problem is that I want to be able to have a RecordSet for which Records can come from a range of backend sources, can be lazily transformed into other RecordSets using e.g. map/filter. Using `Iterator` felt like the natural choice, but seems like I'm swimming upstream before I even get moving. — d11wtq, May 03 '23 at 00:25

score 1 · Accepted Answer · answered May 02 '23 at 15:56

A higher-ranked lifetime cannot appear only in associated types without appearing in generics too. I don't think this is impossible to implement, as far as I understand it was allowed once but was implemented incorrectly, causing unsoundness because the trait solver was sometimes choosing different lifetimes for the same instance. So it was just forbidden. I don't know if it's even hard to implement, or just nobody bothered.

But this doesn't matter because your definition is incorrect anyway. Take for example std::slice::Iter<'a, Record>, created if you do vec.iter(). This struct does not implement Iterator<Item = &'b Record> for any lifetime 'b, only for the lifetime 'a - the lifetime of the vector. So what you need is a generic parameter, and not a higher-ranked trait bound:

pub trait RecordIterator<'a>: Iterator<Item = &'a Record> {}

impl<'a, T> RecordIterator<'a> for T where T: Iterator<Item = &'a Record> {}

pub struct RecordSet<'a> {
    records_iter: Box<dyn RecordIterator<'a> + 'a>,
}

Thank you. Something "clicked" here. I was close to giving up. — d11wtq, May 03 '23 at 01:29

Storing an iterator over borrowed refs inside a Struct

1 Answers1