[Pre-RFC] Backward-compatible GATification

Summary

Allow adding generic parameters to associated types in a backward compatible fashion.

Motivation

With generic associated types (GATs) on track for stabilization, I would like to open the discussion on how to leverage them in the standard library. In the original RFC for GATs, lending iterators served as the main motivating example. Unlike the current Iterator trait, a LendingIterator may yield items whose lifetime is tied to the iterator itself. For the currently unstable Stream trait, a similar lending variant has been discussed.

The downside of adding a lending variant for each trait is increased duplication and complexity. Especially Rust new-comers may find it difficult to choose between the classic and lending variants. Since non-lending iterators can be implemented in terms of the lending trait, I propose to add a generic lifetime parameter to the associated type of the existing trait, instead of introducing new traits. This pre-RFC outlines how such a change could be possible while retaining backward compatibility with existing implementations.

Guide-level explanation

The existing Iterator trait (and potentially other traits) is modified to allow producing values that may have references into the iterator itself. This is possible by making the associated Item type generic over the lifetime of the iterator. To ensure backward compatibility, a default is specified for the generic parameter. A GATified version of the Iterator trait would then look as follows:

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

Implementations, trait bounds and traits with Iterator as a supertrait may omit the generic parameter when referring to the associated Item type.

Reference-level explanation

We consider how the GATified version of the Iterator trait from above would affect implementations, trait bounds and supertraits.

Trait Implementations

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        /* ... */
    }
}

In trait implementations, the generic parameters in the definition of an associated types can be omitted if they are not used. This is equivalent to explicit dummy parameters. In the example above, type Item = &'a T would be equivalent to

type Item<'dummy> where Self: 'dummy = &'a

When referring to an associated type, generic parameters can be omitted if a default is specified. Hence, Self::Item and <Foo as Iterator>::Item would be equivalent to Self::Item<'static> and <Foo as Iterator>::Item<'static>, respectively. In the example above, the substituted value is actually irrelevant, since it is not used in the definition of the associated type. However, the default value is important in the case of supertraits, as is explained next.

Supertraits

trait DoubleEndedIterator: Iterator {
    fn next_back(&mut self) -> Option<Self::Item>;
}

In case a GATified trait is a supertrait of an existing trait, the associated type may be referred to without generic parameters. In this case, the defaults defined in the supertrait will be used. In the example above, Self::Item would be equivalent to Self::Item<'static>.

Trait Bounds

trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
    fn into_iter(self) -> Self::IntoIter;
}

While the IntoIterator may also be a candiate for GATification, here we consider how a non-GATified version would interact with a GATified Iterator trait. In trait bounds, the generic parameters of an associated type may be omitted if unused. Thus, the bound Iterator<Item = Self::Item> in the example above would be equivalent to

for<'dummy> Iterator<Item<'dummy> = Self::Item>

Drawbacks

  • The Iterator trait becomes more complex

Rationale and alternatives

  • Add new GATified traits in addition to the existing ones
  • The default for generic lifetime parameters could always be 'static

Prior art

Unresolved questions

Which traits should be GATified?

How about, for example, GATified closure traits:

trait Fn<Args> {
    type Output<'s>;
    fn call(&self, arg: Args) -> Self::Output<'_>;
}

(see also this post)

11 Likes

... I seem to recall arguing that this isn't possible .... but maybe I'm confusing this with indexing proxies.

Assuming this is viable, I think it's definitely a good idea to provide LendingIterator in this fashion. (Nit: I'd use '_ instead of 'dummy.)

One thing I want to note is that

is backwards. You could provide impl LendingIterator for <impl Iterator> by just discarding the lifetime generic, but you can't impl Iterator for <impl LendingIterator>.

I think you meant

    fn next(&mut self) -> Option<Self::Item<'_>>;

It would need to be type Item<'dummy> where Self: 'dummy = &'a T.

You would need elision (Item<'_>, to be filled in by the lifetime on &mut self) and not 'static.

for<'dummy> Iterator<Item<'dummy> = Self::Item>.

This is exactly what I meant. Maybe my wording is imprecise. Given a non-lending T: Iterator a impl LendingIterator for T can be provided trivially. (i.e. non-lending iterators are a special case)

At least in Closures that can return references to captured variables - #4 by CAD97, you wrote:

Hmm, you are right. Maybe we only need "defaults" for type parameters and lifetimes are elided if not specified. Are there cases where elision would not work?

Your proposal will be backwards compatible for implementers but not users as far as I can see. The following code works currently but won't with your proposal: :pensive:

fn take_iterator<I: Iterator>(mut i: I) {
    let _a = i.next();
    let _b = i.next();
}

According to the proposed rules, your example would be equivalent to the following code:

fn take_iterator<T, I>(mut i: I)
where
    I: for<'s> Iterator<Item<'s> = T>,
{
    let _a = i.next();
    let _b = i.next();
    // use _a
}

My experiments here showed that supplying a type which uses the GAT parameter in its implementation is correctly rejected by the compiler. A type not using the GAT parameter is accepted. Thus, backwards compatibility should also be ensured for users. (The function continues to accept all types for I it previously accepted while extending support for lending iterators would require modification.)

In my experiment, the NonGatImpl required its argument to be a 'static reference, although I expected it to work with shorter lifetimes, too. Any insights?

Which is currently not the case, if you write I: Gaterator in your experiments the compiler rejects it. And if you change its meaning then how can you take a Gaterator where the item yielded borrows from self?

Yes, the meaning of just writing I: Iterator would change to only accept non-lending iterators. If you want to also accept lending iterators, the bound would have to look something like in take_lending_iterator here.

I'm generally in favor of the overall proposal, but it does seem like this is a significant hole in it. It sounds like you've made a good working approach for trait bounds that specify the associated type, which is going to be true most of the time for Iterator, but the issue is for trait bounds that do not specify the associated type. For a GAT, one would expect I: Iterator to allow lending iterators, so it is a troublesome (if perhaps acceptable) inconsistency that adding a default parameter to the GAT would change the semantics of the trait bound. But it would be a serious problem if there wasn't any way to write a trait bound that can accept any and all Iterators (including lending iterators) - and I don't see a way to do that based on your current examples.

2 Likes

That doesn't solve the issue, it only accepts lending iterators of some specific type you have to name. There's still no way to be completly generic over the type of the lending iterator.