# \[Pre-RFC\] Backward-compatible GATification

**URL:** <https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141>\
**Category:** language design\
**Created:** [August 5, 2021, 12:36am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141 "2021-08-05T00:36:36Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![voidc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/voidc/32/8162_2.png) [@voidc](https://internals.rust-lang.org/u/voidc)\
**Post date:** [August 5, 2021, 12:36am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/1 "2021-08-05T00:36:36Z")

</div>

## Summary

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

## Motivation

With generic associated types (GATs) on track for [stabilization](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html), I would like to open the discussion on how to leverage them in the standard library. In the [original RFC](https://rust-lang.github.io/rfcs/1598-generic_associated_types.html) 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:

```rust
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

```rust
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

```rust
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

```rust
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

```rust
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

```rust
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

- Discussion in issue [#44265](https://github.com/rust-lang/rust/issues/44265#issuecomment-737871294)

## Unresolved questions

### Which traits should be _GATified_?

How about, for example, _GATified_ closure traits:

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

```

(see also [this post](https://internals.rust-lang.org/t/closures-that-can-return-references-to-captured-variables/14756))

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [August 5, 2021, 3:55am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/2 "2021-08-05T03:55:06Z")

</div>

... 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

> [@voidc](#):
>
> Since non-lending iterators can be implemented in terms of the lending trait

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>`.

---

<div class="post-metadata">

**Author:** ![quinedot](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/quinedot/32/7294_2.png) [@quinedot](https://internals.rust-lang.org/u/quinedot)\
**Post date:** [August 5, 2021, 6:55am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/3 "2021-08-05T06:55:03Z")

</div>

> [@voidc](#):
>
> ```rust
> fn next(&'s mut self) -> Option<Self::Item<'s>>;
> 
> ```

I think you meant

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

```

> [@voidc](#):
>
> In the example above, `type Item = &'a T` would be equivalent to `type Item<'dummy> = &'a T` .

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

> [@voidc](#):
>
> In the example above, `Self::Item` would be equivalent to `Self::Item<'static>` .

You would need elision (`Item<'_>`, to be filled in by the lifetime on `&mut self`) and [not `'static`.](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=3d4652601b565a9665e8d8155c2ebc04)

> [@voidc](#):
>
> Thus, the bound `Iterator<Item = Self::Item>` in the example above would be equivalent to `Iterator<Item<'dummy> = Self::Item>`

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

---

<div class="post-metadata">

**Author:** ![voidc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/voidc/32/8162_2.png) [@voidc](https://internals.rust-lang.org/u/voidc)\
**Post date:** [August 5, 2021, 9:06am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/4 "2021-08-05T09:06:45Z")

</div>

> [@CAD97](#):
>
> You could provide `impl LendingIterator for <impl Iterator>` by just discarding the lifetime generic, but you can't `impl Iterator for <impl LendingIterator>` .

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)

> [@CAD97](#):
>
> I seem to recall arguing that this isn't possible

At least in [Closures that can return references to captured variables - #4 by CAD97](https://internals.rust-lang.org/t/closures-that-can-return-references-to-captured-variables/14756/4), you wrote:

> [@Closures that can return references to captured variables](https://internals.rust-lang.org/t/closures-that-can-return-references-to-captured-variables/14756/4):
>
> Underspecified, but I think possible, somewhat realistic given other lifetime inference rules, and potentially desirable if it allows us to reuse existing traits for the lending versions.

> [@quinedot](#):
>
> You would need elision ( `Item<'_>` , to be filled in by the lifetime on `&mut self` ) and [not `'static` .](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=3d4652601b565a9665e8d8155c2ebc04)

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?

---

<div class="post-metadata">

**Author:** ![mbartlett](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mbartlett/32/8691_2.png) [@mbartlett](https://internals.rust-lang.org/u/mbartlett)\
**Post date:** [August 5, 2021, 11:10am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/5 "2021-08-05T11:10:10Z")

</div>

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: 😔

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

```

---

<div class="post-metadata">

**Author:** ![voidc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/voidc/32/8162_2.png) [@voidc](https://internals.rust-lang.org/u/voidc)\
**Post date:** [August 5, 2021, 11:47am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/6 "2021-08-05T11:47:14Z")

</div>

> [@mbartlett](#):
>
> Your proposal will be backwards compatible for implementers but not users as far as I can see.

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

```rust
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](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=8bc66d42dcea35bd9b67685178d5f90a) 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?

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [August 5, 2021, 11:59am UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/7 "2021-08-05T11:59:36Z")

</div>

> [@voidc](#):
>
> According to the proposed rules, your example would be equivalent to the following code:

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`?

---

<div class="post-metadata">

**Author:** ![voidc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/voidc/32/8162_2.png) [@voidc](https://internals.rust-lang.org/u/voidc)\
**Post date:** [August 5, 2021, 12:05pm UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/8 "2021-08-05T12:05:18Z")

</div>

> [@SkiFire13](#):
>
> 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](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=5edcc536dd6485e17c7acc720228b08a).

---

<div class="post-metadata">

**Author:** ![elidupree](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/elidupree/32/4304_2.png) [@elidupree](https://internals.rust-lang.org/u/elidupree)\
**Post date:** [August 5, 2021, 12:48pm UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/9 "2021-08-05T12:48:42Z")

</div>

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 `Iterator`s (including lending iterators) - and I don't see a way to do that based on your current examples.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [August 5, 2021, 1:59pm UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/10 "2021-08-05T13:59:57Z")

</div>

> [@voidc](#):
>
> If you want to also accept lending iterators, the bound would have to look something like in `take_lending_iterator` [here](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=5edcc536dd6485e17c7acc720228b08a).

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.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [November 3, 2021, 2:00pm UTC](https://internals.rust-lang.org/t/pre-rfc-backward-compatible-gatification/15141/11 "2021-11-03T14:00:24Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.