The problem is simple:
If we change Iterator's associated type to be GAT what would we have here is:
impl Iterator for Range<i32> {
type Item<?>; // prior to GATification, we had no generic parameter here at all
...
}
So, we want:
to keep existing code compiling and not change it's semantics
and to allow the Item be generic where necessary
One way to solve both points is to have a default lifetime to go there. But what it would be?
'static is not the case, because it breaks code that return foreign references, like impl Iterator for &[T]
???
The core insight here is that lifetime of the Item itself may not always be tied to the lifetime of Self. However we lack of a way to express this.
I want to propose one: the empty lifetime '! - analogous to the empty type.
How it solves the problem?
We immediately use it as default for lifetime in, for example, GATified iterator:
trait Iterator {
type Item<'i = '!>;
...
}
Important examples with it:
Yielding foreign data
impl<'a,T> Iterator for &'a [T] {
// Really, a `type Item<'_ ='!> = ...`
type Item = &'a T;
...
}
Lending is simple: empty lifetime doesn't figure there.
Yielding a static data
impl Iterator for MyStruct {
type Item<'_ = '!> = [f32;5]; //for example; `<'!>` could have been ommited
}
From here we see the core semantic point: '! lifetime cannot influence any other lifetime.
Breakdown:
the default lifetime parameter in example 1 doesn't influence the associated lifetime of Item type (for references this lifetime is written explicitly);
in trait, this is still a default generic value - it can be overridden in impls, so all the possibilities of lending iterators are unaffected;
in case of an actual type being free of lifetimes (owned) this default also helps - it surpasses the implict Type<'a>: 'a bound.
The “ordinary iterator” special gace of a GATified iterator would simply be to add a lifetime parameter to Item but never use it in the implementation. E.g.
trait Iterator {
type Item<'b> where Self: 'b;
... // fn next(&mut self) -> Self::Item<'_>
}
impl<'a,T> Iterator for &'a [T] {
type Item<'b> = &'a T where Self: 'b; // `&'a T` doesn’t use `'b`
// ^^^ current rustc is pedantic and wants the `where Self: 'b` clause
// here, too, for whatever reason, even though IMO a more general
// (less restrained) implementation should be okay
... // fn next(&mut self) -> &'a T
}
But they still will have to do it. Doesn't it defeat stability? If so, we would phase GATification through edition. In case of an additional trait we inevitably get migration concerns.
For a backwards-compatible upgrade to the Iterator trait, you also have to consider trait bounds. Currently T: Iterator means that the Item must not depend on the &mut self’s lifetime. There isn’t really any option other than introducing a second trait. Called LendingIterator, say. However, for backwards compatibility in using existing iterators with that new, generalized, trait, all you’d need is to make sure that Iterator implementations are also creating LendingIterator implementations.
Well, except for when you don’t want that, e.g. for combinators. A Map<I, F> should be Iterator ifI: Iterator and it should be LendingIterator if I: LendingIterator.
This problem is comparable to (and hence probably solvable with the same kind of features I imagined for) a problem I wrote something about here in the context of a trait for non-cancellation-safe futures, and I do intend to eventually try and make the relevant feature(s) an RFC perhaps. Edit: I suppose Iterators could make a good motivating use-case.
This kind of hierarchy should work (compiles on nightly)
// Legacy `T: Iterator<Item = …>` bounds use this trait.
// Also a useful “trait alias” for the simple case of a non-generic item type.
trait Iterator: for<'s> GIterator<GItem<'s> = Self::Item> {
type Item;
}
// (lifetime-) “_g_eneric” iterator
trait GIterator {
type GItem<'s>; // missing `where Self: 's` bound
// but with the bound, the `for<'s> GIterator<GItem<'s> = …>` constraints break
}
impl<T: ?Sized, Item> Iterator for T
where
T: for<'s> GIterator<GItem<'s> = Item>,
{
type Item = Item;
}
// Legacy `impl Iterator for …` impls will use this template instead.
trait IteratorTemplate {
type Item;
}
impl<T: ?Sized> GIterator for T
where
T: IteratorTemplate,
{
type GItem<'s> = <Self as IteratorTemplate>::Item;
}
impl<'a, T> IteratorTemplate for std::slice::Iter<'a, T> {
type Item = &'a T;
}
fn expect_iterator<T: Iterator>() {}
fn test<'a, 'b: 'a>() {
expect_iterator::<std::slice::Iter<'a, &'b ()>>()
}
and with some additional features to make sure that Iterator in exiting code refers either to Iterator above or to IteratorTemplate depending on if it’s used in a trait bound or to write an impl … for Iterator, the change could become backwards compatible.
That’s already where we run into annoying limitations of GATs, many of which aren’t present in the stable workarounds. Adding the where Self: 's bound causes problems. Here’s the equivalent hierarchy with the stable GAT-free “emulation” of (lifetime-based) GATs instead, where (effectively) adding that bound and adding a next methods works without much problem:
trait HasGItem<'s, _Outlives = &'s Self> {
type GItem;
}
type GItem<'s, _Self> = <_Self as HasGItem<'s>>::GItem;
trait GIterator: for<'s> HasGItem<'s> {
fn next(&mut self) -> Option<GItem<'_, Self>>;
}
trait Iterator: GIterator + for<'s> HasGItem<'s, GItem = Self::Item> {
type Item;
fn next(_self: &mut Self) -> Option<Self::Item>;
}
trait IteratorTemplate {
type Item;
fn next(_self: &mut Self) -> Option<Self::Item>;
}
impl<T: ?Sized, Item> Iterator for T
where
T: GIterator + for<'s> HasGItem<'s, GItem = Item>,
{
type Item = Item;
fn next(_self: &mut Self) -> Option<Self::Item> {
_self.next()
}
}
impl<'s, T: ?Sized> HasGItem<'s> for T
where
T: IteratorTemplate,
{
type GItem = T::Item;
}
impl<T: ?Sized> GIterator for T
where
T: IteratorTemplate,
{
fn next(&mut self) -> Option<GItem<'_, Self>> {
IteratorTemplate::next(self)
}
}
impl<'a, T> IteratorTemplate for std::slice::Iter<'a, T> {
type Item = &'a T;
fn next(_self: &mut Self) -> Option<Self::Item> {
std::iter::Iterator::next(_self)
}
}
fn expect_iterator<T: Iterator>() {}
fn test<'a, 'b: 'a>() {
expect_iterator::<std::slice::Iter<'a, &'b ()>>()
}
struct RepeatMut<'a, T>(&'a mut T);
impl<'s, T> HasGItem<'s> for RepeatMut<'_, T> {
type GItem = &'s mut T;
}
impl<T> GIterator for RepeatMut<'_, T> {
fn next(&mut self) -> Option<GItem<'_, Self>> {
Some(self.0)
}
}
struct RepeatMutOwned<T>(T);
impl<'s, T> HasGItem<'s> for RepeatMutOwned<T> {
type GItem = &'s mut T;
}
impl<T> GIterator for RepeatMutOwned<T> {
fn next(&mut self) -> Option<GItem<'_, Self>> {
Some(&mut self.0)
}
}
struct Take<I> {
iter: I,
len: usize,
}
impl<'s, I: GIterator> HasGItem<'s> for Take<I> {
type GItem = GItem<'s, I>;
}
impl<I: GIterator> GIterator for Take<I> {
fn next(&mut self) -> Option<GItem<'_, Self>> {
if self.len > 0 {
self.len -= 1;
self.iter.next()
} else {
None
}
}
}
// Take is still an ordinary Iterator if T is one
fn test2<T: Iterator>(i: T) {
fn expect_iter<T: Iterator>(_: T) {}
expect_iter(Take{ iter: i, len: 42});
}
Actually, as seen in the Take example above, you don’t even have to implement Iterator directly anymore; this kind of caveat was more relevant in the original context with cancel safety, because in that case the compiler could not automatically implement Future in terms of Async, whereas in the code example above, implementing Iterator generically in terms of GIteratordoes work out fine.
Regarding the case of Map, I didn’t get any achieve any proper support for those; any tricks with helper traits would probably kill good type inference, and directly writing something like F: for<'s> FnMut(SomeGAT<'s>) -> SomeOtherGAT<'t> is apparently not supported in a trait bound for some (strange?) reason.
And with described default, they are not affected.
Impls for these types would be changed to use Items lifetime parameters.
The signature of Iterator::next will also change.
Fully patched trait:
trait Iterator {
type Item<'i = '!> where Self: 'i; // If the default is not overidden the semantics doesn't differ from current one
fn next<'i = '!>(&mut self) -> Option<Self::Item<'i>>; //can impls not specify the generic lifetime parameter if it has a default? (1)
}
&mut self lifetime is unconstrained here, because for the default of the empty lifetime it's senseless.
The answer should be true. (if it's not, then existing implementations, that haven't migrated or don't want will stop to compile)
An example of impl supporting GATs:
pub struct Map<I, F> {
pub(crate) iter: I,
f: F,
}
impl<I, F> Map<I, F> {
pub(in crate::iter) fn new(iter: I, f: F) -> Map<I, F> {
Map { iter, f }
}
}
impl<B, I: Iterator, F> Iterator for Map<I, F>
where
F: for<'i> FnMut(I::Item<'i>) -> B, //we want the closure to operate on all lifetimes
{
type Item<'i> = B where B: 'i; //we want the closure output's lifetime to be derived from generic one.
#[inline]
fn next<'i>(&mut self) -> Option<B<'i>> { //and finally, we thread lifetimes through the method
self.iter.next().map(&mut self.f)
}
}
An example of impl for [T]s iter that don't:
pub struct Iter<'a, T: 'a> {
ptr: NonNull<T>,
end: *const T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that
// ptr == end is a quick test for the Iterator being empty, that works
// for both ZST and non-ZST.
_marker: PhantomData<&'a T>,
}
...
impl<'a,T: 'a> Iterator for Iter<'a,T> {
type Item = &'a T;
fn next(&mut self) -> &'a T {
if self.ptr == self.end {
None
} else {
Some(self.ptr.inc()) //or what was that method
}
}
}
It hasn't changed at all!
And from here it's clear that &! T === ! for all T + all the consequences.
The purpose of '! is to express the lack of lifetime which is not exactly life forever as with 'static:
If T: Iterator bounds are unaffected, how would you write a bound that doesn't imply that the item type must not actually use its lifetime parameter? In my code examples, there is a significant difference between T: Iterator and T: GIterator, the former being more restrictive (i. e. fulfilled by fewer types).
I don't understand this, isn't the whole point of making Item a GAT, so that the next method can relate the &mut self's lifetime to the Item's lifetime parameter? Like, a generalization that combines both the current Iterators as well as StreamingIterator...
If not, what actually is the point? What kind of new iterators (not iterator adaptors) are possible?
If we really view empty lifetime as an opposite of static than the signature above is pointless as 's would be essentially forced to also be '! with clear consequences.
What would help here is making '! lifetime to satisfy all possible lifetime bounds, but be unobtainable itself (and really, what on earth can construct a valid reference of an empty lifetime?) => the only possible use switching requested above.
For example, I: Iterator<Item<'_> >, but this may be too confusing, + it clashes with possible shorthand for HRTBs.