Iterators v2

GATs are getting closer. We'd like to work an iterator design that is backwards-compatible with existing iterators. Here's our perceived requirements:

  1. They should be implementable for all existing Iterators.
  2. They should support streaming if desired.
  3. They should support collect if they're not streaming.

Here's our idea:

trait Iterator {
  type Item<'a = 'self>;
  fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
  fn collect<T>(...) -> T where Self::Item<'_>: 'self {...}
}

This would require an explicit use std::v2::Iterator; because unfortunately the way to request the collect method would be a breaking change. Other than that, changing existing types over to implement these Iterators v2 should just be a matter of importing Iterators v2 (this would require the crates to provide a semver bump however).

Additionally, for loops would have to use Iterators v2, and a blanket impl for existing Iterators should be provided. That's the easy part tho.

PS: 'self is meant as a shorthand for "the lifetime of the type". This could also be written as

trait<'b> Iterator where Self: 'b {
  type Item<'a = 'b>;
  fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
  fn collect<T>(...) -> T where Self::Item<'_>: 'b, T: ... {...}
}

The main benefit here is that the use of <'a = 'self> would allow one to omit the <> when implementing, if so desired. (as well as when matching?) As an example vec![1, 2, 3].into_iter() would have a type-lifetime of 'static, which would, effectively, degenerate this trait into the existing Iterator trait.

(Uh we're not entirely sure how lifetimes work also. Would something like this even work? Probably not? The lifetimes of next may need to be tweaked. >.<)

Neither GATs not lifetimes can have default values.

Well, this doesn't make them backwards-compatible.

Why would existing libraries need to implement this Iterator v2 if a blanklet impl will be provided? The current Iterator has more requirement for being implemented than your Iterator v2, so if a struct can already implement it what would it gain from switching to Iterator v2? I feel like this would be an useless breaking change.

You'll also need an IntoIterator v2 for that. Also, I'm not sure this is doable without a breaking change since this would potentially be more restricting for the user. It probably depends on when the borrow checking occurs and how smart it is.

Neither 'self nor trait<'b> ... are currently valid in Rust today.

What do you not like about the StreamingIterator that was proposed in the GATs RFC? It's simplier than yours, provides the same features and doesn try to create breaking changes in the ecosystem.

3 Likes
  1. GATs and lifetimes should be able to have default values. (especially 'static, but for GATs 'self would be nice too.)
  2. No, it is backwards-compatible. In that the new iterators can automatically use the old iterators' impls.
  3. The libraries should only implement this Iterator v2 if a streaming iterator is desired. Otherwise, they should implement the existing iterators, and automatically get support for collect and friends.
  4. Sure, a v2 IntoIterator sounds good.
  5. It would be nice if 'self and trait<'b> were a thing.
  6. The point of this is that for loops should only use a single Iterator trait instead of two. Turning existing Iterators into a simple library wart and adding a replacement lang item (Iterators v2) that can automatically pick up the existing Iterator impls through a blanket impl makes the language simpler, and you can always consume Iterators v2 if you wanna be more generic, while providing Iterators v1 for compatibility with old libraries. SteramingIterator should be a strict superset of Iterator, and Iterator should no longer be a lang item.

For GATs a default value would only work when you refer to it outside. What you probably want is being able to not write the generic type when implementing the GAT. For lifetimes, you can't have default lifetimes because omitting a lifetime already has a meaning.

Then backwards-compatible has different meaning for us. For me backward compatible means that you can swap it and everything else will keep working.

But if a normal Iterator is possible why would they want a streaming iterator?

'self would be nice, but it is probably reserved for self-referential structs, if we ever get them. trait<'b> is just weird. Anyway if your proposal needs them then this is probably not the right time to discuss it.

I don't think that there's any difference between StreamingIterator and Iterator v2 in this case.

You mean of Iterator v2? If that's the case I don't agree, StreamingIterator is exactly like Iterator v2, except that collect and friends are kept in the original Iterator trait, but that doesn't make it a superset.

StreamingIterator (aka what we call Iterators v2) should be a strict superset of Iterator (aka what we currently have).

This includes collect(), which should just be fn collect() where Self::Item: doesn't care about the lifetime (presumably where Self::Item<'_>: 'self). You should also be able to call cloned() or maybe owned() on such a StreamingIterator to get another StreamingIterator (but not an Iterator) where collect() is available.

Also: bonus points if you could do trait Iterator = IteratorV2 where Self::Item: 'self. :‌p (altho this is probably somewhat confusing...)

Also also: pretty sure changing the meaning of omitting a lifetime for types that explicitly opt-in to it isn't a breaking change.

Ok so we mean the same thing.

Maybe I get what you're trying to get. If for example you have a StreamingIterator with Item<'a> = &'a T and T: Clone + 'static then the clonable adapter would produce a StreamingIterator which is not an Iterator but that could still be collected. I agree this would be nice, but I don't see any way to do this right now.

Unfortunately you can't implement trait aliases, so this wouldn't solve the backwards-compatibility problem.

Not a breaking change, but surely pretty confusing.

ps: The name "Iterator v2" implies it would replace the Iterator trait, and IMO that makes it a bad name because we should focus on extending the Iterator trait with something that works with it rather than trying to replace it.

Not 'static because that's not required for existing collect. It'd have to be 'self. We really need 'self. (Perhaps 'self could even be used with Any while at it? but we digress.)

For now.

It should replace it as a lang item, tbh.

Personal pet peeve of mine, when the output type borrows from the generator then it should be called Cursor instead to differentiate it properly (i.e. clarify that the interface is quite a bit more restrictive for the caller than the iterator concept.) The naming is already somewhat established from databases—commonly they give access to rows of a query at a time but the memory used for this access is managed by the database and invalidated on itereration, so that for example a new row might evict the previous results from an internal cache.

Yes it would. On that topic, there are other uses for "lifetime of a type", thus more generic syntax would be preferred.

1 Like