Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

GATs: Decide whether to have defaults for where Self: 'a #87479

Open
nikomatsakis opened this issue Jul 26, 2021 · 51 comments · Fixed by #89970
Open

GATs: Decide whether to have defaults for where Self: 'a #87479

nikomatsakis opened this issue Jul 26, 2021 · 51 comments · Fixed by #89970
Labels
A-GATs Area: Generic associated types (GATs) disposition-merge This issue / PR is in PFCP or FCP with a disposition to merge it. finished-final-comment-period The final comment period is finished for this PR / Issue. GATs-triaged Issues using the `generic_associated_types` feature that have been triaged T-lang Relevant to the language team, which will review and decide on the PR/issue. T-types Relevant to the types team, which will review and decide on the PR/issue.

Comments

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Jul 26, 2021

Coming from the "missing required bounds" error?

The "missing required bounds" error that was emitted is intended to ensure that current code is forwards-compatible with potential future changes. We'll provide a brief summary of the why the bounds are required, the potential future changes, and a workaround if the required bounds are too restrictive. We would appreciate any feedback for this issue.

Why are these bounds required

Let's start by imagining a trait:

trait Iterable {
    type Item<'x>;
    fn iter<'a>(&'a self) -> Self::Item<'a>;
}

As-is, nothing looks wrong about this; without the "missing required bounds" error, this would compile. However, let's try to add an impl:

impl<T> Iterable for T {
    type Item<'a> = &'a T;
    fn iter<'a>(&'a self) -> Self::Item<'a> { self }
}

This definition of Item<'a> = &'a T is invalid, since we don't know that T outlives 'a. So, our first thought might be to modify the definition to add a where Self: 'a clause. This is what we want. However, impls are not allowed to have more where clauses than the trait.

Luckily, we can detect in a trait when this type of problem might occur. To do this, we look at the trait methods that construct the GAT. There, we find the bounds that we know and require that those bounds be written on the GAT itself.

Here, on the Iterable trait, we construct the GAT Self::Item<'a> in the iter method. There, we have an argument &'a self, which allows us to know Self: 'a. Therefore, we require the where Self: 'a bound on the GAT.

Potential future changes

Following the above logic, if we know all the required bounds when the trait is written, why require them at all? In fact, allowed these bounds to be implied is a potential future change. However, to make this change in a backwards-compatible manner, we must require the bounds now that we want to eventually imply. At that time, the written bounds will be redundant and can be removed.

This breaks my code. Workaround?

First, if any code breaks from adding the required bounds, we really want feedback. Second, the workaround is to move the GAT into a super trait. Using the example above, our new code would look like:

trait IterableSuper {
    type Item<'x>;
}
trait Iterable: IterableSuper {
    fn iter<'a>(&'a self) -> Self::Item<'a>;
}

Previous discussion

What is this bug?

We are moving towards stabilizing GATs (tracking issue: #44265) but there is one major ergonomic hurdle that we should decide how to manage before we go forward. In particular, a great many GAT use cases require a surprising where clause to be well-typed; this typically has the form where Self: 'a. It might be useful if we were to create some rules to add this rule by default. Once we stabilize, changing defaults will be more difficult, and could require an edition, therefore it's better to evaluate the rules now.

I have an opinion! What should I do?

To make this decision in an informed way, what we need most are real-world examples and experience reports. If you are experimenting with GATs, for example, how often do you use where Self: 'a and how did you find out that it is necessary? Would the default proposals described below work for you? If not, can you describe the trait so we can understand why they would not work?

Of great use would be example usages that do NOT require where Self: 'a. It'd be good to be able to evaluate the various defaulting schemes and see whether they would interfere with the trait. Knowing the trait and a rough sketch of the impls would be helpful.

Background: what where clause now?

Consider the typical "lending iterator" example. The idea here is to have an iterator that produces values that may have references into the iterator itself (as opposed to references into the collection being iterated over). In other words, given a next method like fn next<'a>(&'a mut self), the returned items have to be able to reference 'a. The typical Iterator trait cannot express that, but GATs can:

trait LendingIterator {
    type Item<'a>;

    fn next<'b>(&'b mut self) -> Self::Item<'b>;
}

Unfortunately, this trait definition turns out to be not quite right in practice. Consider an example like this, an iterator that yields a reference to the same item over and over again (note that it owns the item it is referencing):

struct RefOnce<T> {
    my_data: T    
}

impl<T> LendingIterator for RefOnce<T> {
    type Item<'a> where Self: 'a = &'a T;

    fn next<'b>(&'b mut self) -> Self::Item<'b> {
        &self.my_data
    }
}

Here, the type type Item<'a> = &'a T declaration is actually illegal. Why is that? The assumption when authoring the trait was that 'a would always be the lifetime of the self reference in the next function, of course, but that is not in fact required. People can reference Item with any lifetime they want. For example, what if somebody wrote the type <SomeType<T> as LendingIterator>::Item<'static>? In this case, T: 'static would have to be true, but T may in fact contain borrowed references. This is why the compiler gives you a "T may not outlive 'a" error (playground).

We can encode the constraint that "'a is meant to be the lifetime of the self reference" by adding a where Self: 'a clause to the type Item declaration. This is saying "you can only use a 'a that could be a reference to Self". If you make this change, you'll find that the code compiles (playground):

trait LendingIterator {
    type Item<'a> where Self: 'a;

    fn next<'b>(&'b mut self) -> Self::Item<'b>;
}

When would you NOT want the where clause Self: 'a?

If the associated type cannot refer to data that comes from the Self type, then the where Self: 'a is unnecessary, and is in fact somewhat constraining. As an example, consider:

XXX finish this

What could we do about it?

There are a few options. Here is the list of ideas we've had so far.

  1. Status quo: require that people add the where Self: 'a bounds, and try to do better with diagnostics.
  2. Simple, limited default: If a GAT has exactly one lifetime parameter 'a, add where Self: 'a to both traits and impls. Need some way to opt out.
  3. More extensive defaults: e.g., for every lifetime parameter 'a to a GAT, add where Self: 'a, and maybe where T: 'a for type parameters too. Need some way to opt out.
  4. Add a syntactic sugar for this common case, e.g. type Foo<'self>. This could be added later.
  5. self-oriented defaults: Given some GAT Foo<'a>, if each use Self::Foo<'b> within the trait methods references a 'b that is the lifetime parameter for self, then add where Self: 'b. While kind of complex to explain, this captures the intuition that 'a is meant to be the "lifetime of the self reference" in practice. We probably still want a way to opt out (though maybe not; maybe that way is "don't use &'a self notation").
  6. Even smarter defaults A: Look at the method signatures in the trait. If we find that each use of Self::Item<'b> is associated with a lifetime 'b where Self: 'b is implied by the method arguments, then infer that where Self: 'b. This is a more extensive, general version of self-oriented defaults. We probably still want a way to opt out (though maybe not).

In general, once we stabilize GATs, we likely cannot add defaults, except via an edition -- although we may be able to get away with it in this instance if the defaults are smart enough.

@jonas-schievink jonas-schievink added F-generic_associated_types `#![feature(generic_associated_types)]` a.k.a. GATs T-lang Relevant to the language team, which will review and decide on the PR/issue. labels Jul 26, 2021
@nikomatsakis
Copy link
Contributor Author

cc @rust-lang/lang

@cramertj
Copy link
Member

cramertj commented Jul 26, 2021

Of great use would be example usages that do NOT require where Self: 'a. It'd be good to be able to evaluate the various defaulting schemes and see whether they would interfere with the trait. Knowing the trait and a rough sketch of the impls would be helpful.

One of the ones that seems most obvious to me is when the output borrows not from self, but from a parameter to the method, such as in the case of a parser:

trait Parser {
    type Output<'a>;
    fn parse<'a>(&mut self, data: &'a [u8]) -> Self::Output<'a>;
}

Parser output wouldn't usually reference state internal to the parser, but it very well may reference the input data. In practice, you can express this instead with for<'a> Parser<'a>, but it's often the case that lifetime-only GATs can be replaced with HRTB-based solutions. I think it might be a goal of ours to allow people to avoid HRTBs for these types of things-- if it is, then this use-case is worth considering.

@jplatte
Copy link
Contributor

jplatte commented Jul 27, 2021

For another example where Self: 'a would be wrong, in Ruma we have a trait IncomingRequest that I've long wanted to use GATs for, which would be another example of this. Simplified:

// Every endpoint in the Matrix REST API has two request and response types in Ruma, one Incoming
// (used for deserialization) and out Outgoing (used for serialization). To avoid annoying clones when
// sending a request, most non-copy fields in the outgoing structs are references.
//
// The request traits have an associated type for the corresponding response type so things can be
// matched up properly.
pub trait IncomingRequest: Sized {
    // This is the current definition of the associated type I'd like to make generic.
    type OutgoingResponse: OutgoingResponse;
    // AFAICT adding a lifetime parameter is all I need.
    type OutgoingResponse<'a>: OutgoingResponse;

    // Other trait members... (not using Self::OutgoingResponse)
}

(full definition here if sbd. is curious)

My 2c regardingthe potential solutions: type Foo<'self> looks really nice.

@ShadowJonathan
Copy link

ShadowJonathan commented Jul 30, 2021

I'm also in favour of keeping status quo and adding the implicit 'self lifetime, it balances the need for being explicit with DRY, is easy to hint at by the compiler (for one scenario or another), and easy to reference by the book & other resources.

In general I think the compiler shouldn't try to be "smart" about this, I'm still a learning rustacean, but having the compiler try to infer multiple lifetimes by default, and implicitly, seems confusing and footgun-y to me.

@ammkrn
Copy link

ammkrn commented Aug 2, 2021

I have a use case of the kind @cramertj referenced that I ended up working around with macros, but I would like to try and remove them when GATs are available. Also for cramertj, I couldn't figure out how to implement your example with HRTBs, so if you can actually do that I'd be interested to learn how it's done.

My specific use case is a little more complex, but I think the idea is relevant to many applications of indirect data structures. I have tree structures that are managed with type/memory safe integer pointers:

struct Ptr<'a, A> {
  id: usize,
  marker: PhantomData<&'a A>

The backing storage struct looks like:

struct Store<'a> {
  a_set: IndexSet<ThingA<'a>>,
  b_set: IndexSet<ThingB<'a>>,
  ..
  n_set: IndexSet<ThingN<'a>>,
}

The program is a type checker, so there may be multiple stores alive with lifetimes 'a > 'b > .. 'n, but they nest, so we're always dealing with the "outermost" one (with the shortest lifetime). The guarantees I'm currently able to enforce within Rust's type system are that a Ptr<'a, A> can't outlive its backing Store<'a>, and that you can only create a Ptr<'a, A> if you actually have a Store<A>. The macro-based solution runs really well, but GATs would be much more satisfying. The GAT solution I originally wanted was to have a trait for the stored types so that the output's lifetime was dependent on the lifetime of the backing store that was passed as an argument. As long as the underlying data is alive at least as long as the backing store I've been passed, I can both read a Ptr<'a, A> -> A and allocate an A -> Ptr<'a, A>.

trait IsStored<'x>: Sized {
    type Carrier<'a>;
    fn read<'a, S: Store<'a>>(self, storage: &mut S) -> Self::Carrier<'a>
    where 'x: 'a ;
    fn alloc<'a, S: Store<'a>>(self, storage: &mut S) -> Ptr<'a, Self::Carrier<'a>>
    where 'x: 'a;
}

In this case, it seems like type Carrier<'a> where Self: 'a would be incorrect, but I wrote up a basic implementation of it with the syntax proposed here and it seems to compile on nightly, I guess because the actual self lifetime is longer than the 'a bound, though I'm sure there are programs that would benefit from similar indirect structures in which that wouldn't always be the case.

Also I have no idea if this is possible, but in playing around with this feature with the thought of making stuff generic over lifetimes, it would be cool if there was a way to add sugar or something to enable this:

trait Thing {
    fn f<'a>(self, ctx: &'a Ctx) -> Self<'a>;
}

// Desugars to something like:
impl<'x> Thing for A<'x> {
  type Assoc<'a> = A<'a>;
  fn f<'a>(self, ctx: &'a Ctx) -> Self::Assoc<'a> { .. }
}

@P-E-Meunier
Copy link

GATs are probably the only feature I've been missing in Rust since 1.0, I'm delighted to see progress on that.

@nikomatsakis, I do have an example where Self: 'a isn't always the case: in Sanakirja, an on-disk key-value store I wrote, memory management is a bit messy. I'd also like to extend it by implementing other transactional datastructures in the future.

Since I don't know the kind of details yous need, here is a quick summary of how Sanakirja works:

  • There is a number of memory-mapped files, of exponentially-increasing size (db0 is of some size given by the user, then when we run out of space in the middle of a transaction we start db(n+1), which is twice the size of db(n)). This trick allows us to never unmap the file in the middle of a transaction. Some of the pointers (explained below) may still be valid after an increase.
  • A fixed-size cyclic array of memory pages at the beginning of db0 (of a size set when creating the database) is dedicated to independent versions of the database, and only the latest version is writable, and writable by a single (mutable) transaction. The only concurrency control is a simple read-write lock on each of these memory pages.
  • Pages are allocated and freed by maintaining two distinct extra B trees: one for free pages (edits in that tree are done by allocating new pages at the end of the file), and another one to store reference counts of pages referenced at least twice. The pointer to the root of these trees is stored in the transactions' pages in the initial cyclic array.
  • Another thing stored in the cyclic array is a number of "roots", which are pointers to some pages in the file. I do abuse these pages sometimes as well to write other things, even though that is probably fairly unsafe if you don't know how things work.

Now, there's a choice about the lifetime of values retrieved from the database: we may choose to have them borrow the transactions, or to have them borrow individual tables. In the former case, a GAT may look like:

trait TableIterator {
  type Iter<'txn, K, V>: Iterator<(&'txn K, &'txn V)>;
  fn iter(&'txn self, db: &'txn Db<K, V>) -> Self::Iter<'txn, K, V>;
}

In the latter case, we'll have the following instead:

trait TableIterator {
  type Iter<'db, K, V>: Iterator<(&'db K, &'db V)>;
  fn iter(&'txn self, db: &'db Db<K, V>) -> Self::Iter<'db, K, V>;
}

This could work with an extra mechanism to make sure Db isn't alive after the end of a transaction, for example.

As a conclusion, I don't have a strong opinion about what the default should be, since I understand this is a rather niche use case. I haven't actually tried to implement these using nightly + GAT, but I could try if yous need more feedback.

@eira-fransham
Copy link

eira-fransham commented Aug 10, 2021

I feel like you're always going to want to allow where Self: 'a even if you don't always require it, so why not stabilise it with the requirement that you must always annotate and add elision later as a separate RFC? That's what we did for lifetime elision in impl specs (e.g. impl Trait for &'_ Foo). This is now, as far as I know, the only remaining blocker for GATs being stabilised so it seems silly to hold that up while we bikeshed this considering that there exists a MVP solution that would be trivial to improve on later in a backwards-compatible way.

@nikomatsakis
Copy link
Contributor Author

Hi all! I'm reading these responses and trying to summarize.

@P-E-Meunier what would be useful is to see not only the trait definition, but prospective impl definitions

@ammkrn the same! What does an impl for the trait IsStored look like? You mentioned that you prototyped your setup on nightly, can you link to that on the Rust playground perhaps?

@ammkrn
Copy link

ammkrn commented Aug 25, 2021

@nikomatsakis

I put it in a gat_nightly branch, here are the impls for one base type and its pointer.
https://github.com/ammkrn/nanoda_lib/blob/4c46ec08cb80e12de1cf5a312f17c3fd67feb228/src/utils.rs#L370
https://github.com/ammkrn/nanoda_lib/blob/4c46ec08cb80e12de1cf5a312f17c3fd67feb228/src/utils.rs#L409

This application's state management is somewhat involved for performance reasons, but I think this issue boils down to what I believe is a GAT use case that's been discussed quite a bit, which is generalizing over the lifetime of a container.

ctx is the telescope of stores,'a is the lifetime of the outermost/shortest-lived backing store, and the one we have mutable access to. 'x is any lifetime equal to or longer than 'a. The two ideas are: "given a pointer to an object known to live at least as long as the shortest-lived store, I can return the pointed-to data, though I can only guarantee it lives as long as the shortest-lived store", and "given some data, I can allocate it and return a pointer, but I can only promise the pointer is good for the lifetime of the shortest-lived store".

or:
read: ∀ 'x >= 'a, (Ptr<'x>, Store<'a>) -> Data<'a>
alloc: ∀ 'x >= 'a, (Data<'x>, Store<'a>) -> Ptr<'a>

@jgarvin
Copy link

jgarvin commented Aug 29, 2021

I ran into a simple case using GATs where I didn't need the clause. I have a trait representing mutable pointers so that I can write generic functions that work both with regular pointers and compressed pointers. Since it's for pointers, there are no lifetimes.

pub trait MutPointer<T>:
{
    type Cast<U>: MutPointer<U>;

    fn cast<U>(self) -> Self::Cast<U>;

    // ... other less relevant methods
}

This is analogous in C++ to std::static_pointer_cast and related functions which work both on regular pointers and smart pointers like shared_ptr and unique_ptr. One problem that still exists with this is that MutPointer<U> could still be some other smart pointer type when it should really be the same generic with a different type plugged in (in other words you shouldn't be able to implement the trait such that shared_ptr<T> is castable to unique_ptr<U>, only shared_ptr<U>). I think doing it right might require HKTs. Something like:

pub trait MutPointer<P<T>>:
{
    fn cast<U>(self) -> P<U>;
}

@dbdeviant
Copy link

I recently came across a scenario where I didn't need the clause. The library performs async serialization for any given user provided format (basically async serde). In my case, only the serializer trait needed the Self lifetime annotation, as the returned future from the method holds on to a reference to the data until complete. The deserializer owns its own internal buffers, and as such just defines an associated function for which no Self reference is needed.

In this case, it would seem that option 6 would be necessary to properly infer the type. (Full disclosure: new rustacean here, so there might be a better way to do this.)

My type definitions:

/// Serialize a data structure asynchronously.
pub trait AsyncSerialize: Encodable
{
    /// The concrete [future](Future) returned by the `serialize` method.
    type Future<'w, F, W>: Future<Output=Result<(), F::Error>> + Unpin
    where
        Self: 'w,
        F: 'w + FormatSerialize,
        W: 'w + AsyncWrite + Unpin,
    ;

    /// Attempt to serialize the type asynchronously for the indicated [format](Format)
    /// via the provided [asynchronous writer](AsyncWrite).
    fn serialize<'w, F, W>(&'w self, format: &'w F, writer: &'w mut W) -> Self::Future<'w, F, W>
    where
        F: FormatSerialize,
        W: AsyncWrite + Unpin,
    ;
}

/// Deserialize a data structure asynchronously.
pub trait AsyncDeserialize: Decodable
{
    /// The concrete [future](Future) returned by the `deserialize` method.
    type Future<'r, F, R>: Future<Output=Result<Self, F::Error>> + Unpin
    where
        F: 'r + FormatDeserialize,
        R: 'r + AsyncRead + AsyncBufRead + Unpin,
    ;

    /// Attempt to deserialize the type asynchronously for the indicated [format](Format)
    /// via the provided [asynchronous reader](AsyncRead).
    fn deserialize<'r, F, R>(format: &'r F, reader: &'r mut R) -> Self::Future<'r, F, R>
    where
        F: FormatDeserialize,
        R: AsyncRead + AsyncBufRead + Unpin,
    ;
}

@madsmtm
Copy link
Contributor

madsmtm commented Oct 8, 2021

I have a use case (that may be similar to the others people have noted, if so, apologies).

A sealed marker trait Ownership with two implementors Owned and Shared is used in objc_id inside a reference-counted type Id<T, O: Ownership>, to specify whether you have mutable or immutable access to the data.

In some cases I would like to consume the Id and return the appropriate reference (bound to some other type, in this case AutoreleasePool); either an &mut T for Owned data or &T for Shared data.

This doesn't require Self: 'a.

trait Ownership {
    type Reference<'a, T: 'a>;

    unsafe fn as_ref_pool<'p, T: 'p>(
        pool: &'p AutoreleasePool,
        ptr: *mut T,
    ) -> Self::Reference<'p, T>;
}

enum Owned {}

impl Ownership for Owned {
    type Reference<'a, T: 'a> = &'a mut T;

    unsafe fn as_ref_pool<'p, T: 'p>(
        pool: &'p AutoreleasePool,
        ptr: *mut T,
    ) -> Self::Reference<'p, T> {
        // SAFETY: Bound by function signature (bound to pool)
        // Pointer validity is up to caller
        &mut *ptr
    }
}

enum Shared {}

impl Ownership for Shared {
    type Reference<'a, T: 'a> = &'a T;

    unsafe fn as_ref_pool<'p, T: 'p>(
        pool: &'p AutoreleasePool,
        ptr: *mut T,
    ) -> Self::Reference<'p, T> {
        // SAFETY: Bound by function signature (bound to pool)
        // Pointer validity is up to caller
        &*ptr
    }
}

@nikomatsakis
Copy link
Contributor Author

Thanks @madsmtm! I believe your use case will work fine with the current plan.

@nikomatsakis
Copy link
Contributor Author

Brief update:

The current plan is to adopt a conservative stance. We'll apply an analyses to determine when we believe that a default ought to be applied. If we find that a default would be appropriate, we will check if that where clause is written explicitly. If not, we will error.

In other words, we are not doing defaults, but we are forcing users to write the where clauses that we would have done by default.

At the same time, we'll include an informational note asking people to give feedback on whether these where clauses caused them problems in an issue. We'll also explain the workarounds to disable the default if it is a problem (so folks are not blocked in the interim).

After some time, we can opt to either make the defaults truly defaulted or take some other action.

My expectation is that there will be no problems with the defaults: they are quite narrowly targeted and the chance of false positive seems to me to be remote. But better safe than sorry!

@cuviper
Copy link
Member

cuviper commented Oct 8, 2021

I was just experimenting with GAT for rayon's with_producer, but it needs an HRTB callback, and I can't see how to constrain that. Here's an artificial self-contained example: playground

#![feature(generic_associated_types)]

use std::iter::Map;
use std::slice::Iter;

pub trait WithStrings {
    type Strings<'a>: Iterator<Item = String>
    where
        Self: 'a;

    fn with_strings<R>(self, f: impl FnOnce(Self::Strings<'_>) -> R) -> R;
}

impl<T: ToString, const N: usize> WithStrings for [T; N] {
    type Strings<'a>
    where
        Self: 'a,
    = Map<Iter<'a, T>, fn(&T) -> String>;

    fn with_strings<R>(self, f: impl FnOnce(Self::Strings<'_>) -> R) -> R {
        f(self.iter().map(T::to_string))
    }
}

(I'm aware this could use array into_iter(), but that's not the point.)

error[E0311]: the parameter type `T` may not live long enough
  --> src/lib.rs:20:8
   |
14 | impl<T: ToString, const N: usize> WithStrings for [T; N] {
   |      -- help: consider adding an explicit lifetime bound...: `T: 'a +`
...
20 |     fn with_strings<R>(self, f: impl FnOnce(Self::Strings<'_>) -> R) -> R {
   |        ^^^^^^^^^^^^ ...so that the type `[T; N]` will meet its required lifetime bounds

I can't put Self: 'a or T: 'a on that AFAIK, or is there a way with explicit for<'a>?

But I kind of imagine a "default" Self: 'a could insert itself in that implicit HRTB somehow.

@eira-fransham
Copy link

eira-fransham commented Oct 10, 2021

@cuviper I believe that T: 'static is the only correct bound, since the function is for<'a> and so it’s only valid if &'a T is valid for any 'a, including 'static. You could add explicit lifetime bounds on the method in the trait definition to relax that bound though.

@cuviper
Copy link
Member

cuviper commented Oct 12, 2021

@Vurich I'm not sure about GATs, but I don't think that's true of for<'a> in general. Iterator::filter has a similar case with its P: FnMut(&Self::Item) -> bool, and this does not require Self::Item: 'static.

I can't use a lifetime parameter on the method though, because it needs a local borrow -- like the self.iter() in my example.

@jackh726
Copy link
Member

GATs issue triage: blocking. I'm currently working on the lint. At minimum, we want to land it before stabilization. But we should consider if we want to do a crater run (not sure how helpful it will be), we should double check against the examples posted here, and we should consider how long we feel like we have to let it sit before stabilizing GATs. But otherwise, hopefully lint will be ready soonish™.

@jackh726 jackh726 added GATs-blocking Issues using the `generic_associated_types` feature that block stabilization GATs-triaged Issues using the `generic_associated_types` feature that have been triaged labels Oct 16, 2021
@nikomatsakis
Copy link
Contributor Author

@rfcbot fcp merge

The currently plan (implemented in #89970, modulo some ongoing discussion):

  • We are going to apply the "defaulting algorithm" described here, but instead of adding the where clauses by default, we will error if the where clauses are not written explicitly.
  • This ensures that we have the freedom to add defaults in the future, and also ensures that people will notice if those defaults are causing them problems.
  • The error message will reflect that request.

I'm therefore moving to FCP that decision for the lang team.

@rfcbot
Copy link

rfcbot commented Oct 25, 2021

Team member @nikomatsakis has proposed to merge this. The next step is review by the rest of the tagged team members:

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

@rfcbot rfcbot added proposed-final-comment-period Proposed to merge/close by relevant subteam, see T-<team> label. Will enter FCP once signed off. disposition-merge This issue / PR is in PFCP or FCP with a disposition to merge it. labels Oct 25, 2021
@nikomatsakis nikomatsakis reopened this Dec 29, 2022
@nikomatsakis
Copy link
Contributor Author

Agreed! We are still soliciting data.

calebcartwright pushed a commit to calebcartwright/rustfmt that referenced this issue Jan 24, 2023
Stabilize generic associated types

Closes #44265

r? `@nikomatsakis`

# ⚡ Status of the discussion ⚡

* [x] There have been several serious concerns raised, [summarized here](rust-lang/rust#96709 (comment)).
* [x] There has also been a [deep-dive comment](rust-lang/rust#96709 (comment)) explaining some of the "patterns of code" that are enabled by GATs, based on use-cases posted to this thread or on the tracking issue.
* [x] We have modeled some aspects of GATs in [a-mir-formality](https://github.com/nikomatsakis/a-mir-formality) to give better confidence in how they will be resolved in the future. [You can read a write-up here](https://github.com/rust-lang/types-team/blob/master/minutes/2022-07-08-implied-bounds-and-wf-checking.md).
* [x] The major points of the discussion have been [summarized on the GAT initiative repository](https://rust-lang.github.io/generic-associated-types-initiative/mvp.html).
* [x] [FCP has been proposed](rust-lang/rust#96709 (comment)) and we are awaiting final decisions and discussion amidst the relevant team members.

# Stabilization proposal

This PR proposes the stabilization of `#![feature(generic_associated_types)]`. While there a number of future additions to be made and bugs to be fixed (both discussed below), properly doing these will require significant language design and will ultimately likely be backwards-compatible. Given the overwhelming desire to have some form of generic associated types (GATs) available on stable and the stability of the "simple" uses, stabilizing the current subset of GAT features is almost certainly the correct next step.

Tracking issue: #44265
Initiative: https://rust-lang.github.io/generic-associated-types-initiative/
RFC: https://github.com/rust-lang/rfcs/blob/master/text/1598-generic_associated_types.md
Version: 1.65 (2022-08-22 => beta, 2022-11-03 => stable).

## Motivation

There are a myriad of potential use cases for GATs. Stabilization unblocks probable future language features (e.g. async functions in traits), potential future standard library features (e.g. a `LendingIterator` or some form of `Iterator` with a lifetime generic), and a plethora of user use cases (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it).

There are a myriad of potential use cases for GATs. First, there are many users that have chosen to not use GATs primarily because they are not stable (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it). Second, while language feature desugaring isn't *blocked* on stabilization, it gives more confidence on using the feature. Likewise, library features like `LendingIterator` are not necessarily blocked on stabilization to be implemented unstably; however few, if any, public-facing APIs actually use unstable features.

This feature has a long history of design, discussion, and developement - the RFC was first introduced roughly 6 years ago. While there are still a number of features left to implement and bugs left to fix, it's clear that it's unlikely those will have backwards-incompatibility concerns. Additionally, the bugs that do exist do not strongly impede the most-common use cases.

## What is stabilized

The primary language feature stabilized here is the ability to have generics on associated types, as so. Additionally, where clauses on associated types will now be accepted, regardless if the associated type is generic or not.

```rust
trait ATraitWithGATs {
    type Assoc<'a, T> where T: 'a;
}

trait ATraitWithoutGATs<'a, T> {
    type Assoc where T: 'a;
}
```

When adding an impl for a trait with generic associated types, the generics for the associated type are copied as well. Note that where clauses are allowed both after the specified type and before the equals sign; however, the latter is a warn-by-default deprecation.

```rust
struct X;
struct Y;

impl ATraitWithGATs for X {
    type Assoc<'a, T> = &'a T
      where T: 'a;
}
impl ATraitWithGATs for Y {
    type Assoc<'a, T>
      where T: 'a
    = &'a T;
}
```

To use a GAT in a function, generics are specified on the associated type, as if it was a struct or enum. GATs can also be specified in trait bounds:

```rust
fn accepts_gat<'a, T>(t: &'a T) -> T::Assoc<'a, T>
  where for<'x> T: ATraitWithGATs<Assoc<'a, T> = &'a T> {
    ...
}
```

GATs can also appear in trait methods. However, depending on how they are used, they may confer where clauses on the associated type definition. More information can be found [here](rust-lang/rust#87479). Briefly, where clauses are required when those bounds can be proven in the methods that *construct* the GAT or other associated types that use the GAT in the trait. This allows impls to have maximum flexibility in the types defined for the associated type.

To take a relatively simple example:

```rust
trait Iterable {
    type Item<'a>;
    type Iterator<'a>: Iterator<Item = Self::Item<'a>>;

    fn iter<'x>(&'x self) -> Self::Iterator<'x>;
    //^ We know that `Self: 'a` for `Iterator<'a>`, so we require that bound on `Iterator`
    //  `Iterator` uses `Self::Item`, so we also require a `Self: 'a` on `Item` too
}
```

A couple well-explained examples are available in a previous [blog post](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html).

## What isn't stabilized/implemented

### Universal type/const quantification

Currently, you can write a bound like `X: for<'a> Trait<Assoc<'a> = &'a ()>`. However, you cannot currently write `for<T> X: Trait<Assoc<T> = T>` or `for<const N> X: Trait<Assoc<N> = [usize; N]>`.

Here is an example where this is needed:

```rust
trait Foo {}

trait Trait {
    type Assoc<F: Foo>;
}

trait Trait2: Sized {
    fn foo<F: Foo, T: Trait<Assoc<F> = F>>(_t: T);
}
```

In the above example, the *caller* must specify `F`, which is likely not what is desired.

### Object-safe GATs

Unlike non-generic associated types, traits with GATs are not currently object-safe. In other words the following are not allowed:

```rust
trait Trait {
    type Assoc<'a>;
}

fn foo(t: &dyn for<'a> Trait<Assoc<'a> = &'a ()>) {}
         //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed

let ty: Box<dyn for<'a> Trait<Assoc<'a> = &'a ()>>;
          //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed
```

### Higher-kinded types

You cannot write currently (and there are no current plans to implement this):

```rust
struct Struct<'a> {}

fn foo(s: for<'a> Struct<'a>) {}
```

## Tests

There are many tests covering GATs that can be found in  `src/test/ui/generic-associated-types`. Here, I'll list (in alphanumeric order) tests highlight some important behavior or contain important patterns.

- `./parse/*`: Parsing of GATs in traits and impls, and the trait path with GATs
- `./collections-project-default.rs`: Interaction with associated type defaults
- `./collections.rs`: The `Collection` pattern
- `./const-generics-gat-in-trait-return-type-*.rs`: Const parameters
- `./constraint-assoc-type-suggestion.rs`: Emit correct syntax in suggestion
- `./cross-crate-bounds.rs`: Ensure we handles bounds across crates the same
- `./elided-in-expr-position.rs`: Disallow lifetime elision in return position
- `./gat-in-trait-path-undeclared-lifetime.rs`: Ensure we error on undeclared lifetime in trait path
- `./gat-in-trait-path.rs`: Base trait path case
- `./gat-trait-path-generic-type-arg.rs`: Don't allow shadowing of parameters
- `./gat-trait-path-parenthesised-args.rs`: Don't allow paranthesized args in trait path
- `./generic-associated-types-where.rs`: Ensure that we require where clauses from trait to be met on impl
- `./impl_bounds.rs`: Check that the bounds on GATs in an impl are checked
- `./issue-76826.rs`: `Windows` pattern
- `./issue-78113-lifetime-mismatch-dyn-trait-box.rs`: Implicit 'static diagnostics
- `./issue-84931.rs`: Ensure that we have a where clause on GAT to ensure trait parameter lives long enough
- `./issue-87258_a.rs`: Unconstrained opaque type with TAITs
- `./issue-87429-2.rs`: Ensure we can use bound vars in the bounds
- `./issue-87429-associated-type-default.rs`: Ensure bounds hold with associated type defaults, for both trait and impl
- `./issue-87429-specialization.rs`: Check that bounds hold under specialization
- `./issue-88595.rs`: Under the outlives lint, we require a bound for both trait and GAT lifetime when trait lifetime is used in function
- `./issue-90014.rs`: Lifetime bounds are checked with TAITs
- `./issue-91139.rs`: Under migrate mode, but not NLL, we don't capture implied bounds from HRTB lifetimes used in a function and GATs
- `./issue-91762.rs`: We used to too eagerly pick param env candidates when normalizing with GATs. We now require explicit parameters specified.
- `./issue-95305.rs`: Disallow lifetime elision in trait paths
- `./iterable.rs`: `Iterable` pattern
- `./method-unsatified-assoc-type-predicate.rs`: Print predicates with GATs correctly in method resolve error
- `./missing_lifetime_const.rs`: Ensure we must specify lifetime args (not elidable)
- `./missing-where-clause-on-trait.rs`: Ensure we don't allow stricter bounds on impl than trait
- `./parameter_number_and_kind_impl.rs`: Ensure paramters on GAT in impl match GAT in trait
- `./pointer_family.rs`: `PointerFamily` pattern
- `./projection-bound-cycle.rs`: Don't allow invalid cycles to prove bounds
- `./self-outlives-lint.rs`: Ensures that an e.g. `Self: 'a` is written on the traits GAT if that bound can be implied from the GAT usage in the trait
- `./shadowing.rs`: Don't allow lifetime shadowing in params
- `./streaming_iterator.rs`: `StreamingIterator`(`LendingIterator`) pattern
- `./trait-objects.rs`: Disallow trait objects for traits with GATs
- `./variance_constraints.rs`: Require that GAT substs be invariant

## Remaining bugs and open issues

A full list of remaining open issues can be found at: https://github.com/rust-lang/rust/labels/F-generic_associated_types

There are some `known-bug` tests in-tree at `src/test/ui/generic-associated-types/bugs`.

Here I'll categorize most of those that GAT bugs (or involve a pattern found more with GATs), but not those that include GATs but not a GAT issue in and of itself. (I also won't include issues directly for things listed elsewhere here.)

Using the concrete type of a GAT instead of the projection type can give errors, since lifetimes are chosen to be early-bound vs late-bound.
- #85533
- #87803

In certain cases, we can run into cycle or overflow errors. This is more generally a problem with associated types.
- #87755
- #87758

Bounds on an associatd type need to be proven by an impl, but where clauses need to be proven by the usage. This can lead to confusion when users write one when they mean the other.
- #87831
- #90573

We sometimes can't normalize closure signatures fully. Really an asociated types issue, but might happen a bit more frequently with GATs, since more obvious place for HRTB lifetimes.
- #88382

When calling a function, we assign types to parameters "too late", after we already try (and fail) to normalize projections. Another associated types issue that might pop up more with GATs.
- #88460
- #96230

We don't fully have implied bounds for lifetimes appearing in GAT trait paths, which can lead to unconstrained type errors.
- #88526

Suggestion for adding lifetime bounds can suggest unhelpful fixes (`T: 'a` instead of `Self: 'a`), but the next compiler error after making the suggested change is helpful.
- #90816
- #92096
- #95268

We can end up requiring that `for<'a> I: 'a` when we really want `for<'a where I: 'a> I: 'a`. This can leave unhelpful errors than effectively can't be satisfied unless `I: 'static`. Requires bigger changes and not only GATs.
- #91693

Unlike with non-generic associated types, we don't eagerly normalize with param env candidates. This is intended behavior (for now), to avoid accidentaly stabilizing picking arbitrary impls.
- #91762

Some Iterator adapter patterns (namely `filter`) require Polonius or unsafe to work.
- #92985

## Potential Future work

### Universal type/const quantification

No work has been done to implement this. There are also some questions around implied bounds.

###  Object-safe GATs

The intention is to make traits with GATs object-safe. There are some design work to be done around well-formedness rules and general implementation.

### GATified std lib types

It would be helpful to either introduce new std lib traits (like `LendingIterator`) or to modify existing ones (adding a `'a` generic to `Iterator::Item`). There also a number of other candidates, like `Index`/`IndexMut` and `Fn`/`FnMut`/`FnOnce`.

### Reduce the need for `for<'a>`

Seen [here](rust-lang/rfcs#1598 (comment)). One possible syntax:

```rust
trait Iterable {
    type Iter<'a>: Iterator<Item = Self::Item<'a>>;
}

fn foo<T>() where T: Iterable, T::Item<let 'a>: Display { } //note the `let`!
```

### Better implied bounds on higher-ranked things

Currently if we have a `type Item<'a> where self: 'a`, and a `for<'a> T: Iterator<Item<'a> = &'a ()`, this requires `for<'a> Self: 'a`. Really, we want `for<'a where T: 'a> ...`

There was some mentions of this all the back in the RFC thread [here](rust-lang/rfcs#1598 (comment)).

## Alternatives

### Make generics on associated type in bounds a binder

Imagine the bound `for<'a> T: Trait<Item<'a>= &'a ()>`. It might be that `for<'a>` is "too large" and it should instead be `T: Trait<for<'a> Item<'a>= &'a ()>`. Brought up in RFC thread [here](rust-lang/rfcs#1598 (comment)) and in a few places since.

Another related question: Is `for<'a>` the right syntax? Maybe `where<'a>`? Also originally found in RFC thread [here](rust-lang/rfcs#1598 (comment)).

### Stabilize lifetime GATs first

This has been brought up a few times. The idea is to only allow GATs with lifetime parameters to in initial stabilization. This was probably most useful prior to actual implementation. At this point, lifetimes, types, and consts are all implemented and work. It feels like an arbitrary split without strong reason.

## History

* On 2016-04-30, [RFC opened](rust-lang/rfcs#1598)
* On 2017-09-02, RFC merged and [tracking issue opened](rust-lang/rust#44265)
* On 2017-10-23, [Move Generics from MethodSig to TraitItem and ImplItem](rust-lang/rust#44766)
* On 2017-12-01, [Generic Associated Types Parsing & Name Resolution](rust-lang/rust#45904)
* On 2017-12-15, [https://github.com/rust-lang/rust/pull/46706](https://github.com/rust-lang/rust/pull/46706)
* On 2018-04-23, [Feature gate where clauses on associated types](rust-lang/rust#49368)
* On 2018-05-10, [Extend tests for RFC1598 (GAT)](rust-lang/rust#49423)
* On 2018-05-24, [Finish implementing GATs (Chalk)](rust-lang/chalk#134)
* On 2019-12-21, [Make GATs less ICE-prone](rust-lang/rust#67160)
* On 2020-02-13, [fix lifetime shadowing check in GATs](rust-lang/rust#68938)
* On 2020-06-20, [Projection bound validation](rust-lang/rust#72788)
* On 2020-10-06, [Separate projection bounds and predicates](rust-lang/rust#73905)
* On 2021-02-05, [Generic associated types in trait paths](rust-lang/rust#79554)
* On 2021-02-06, [Trait objects do not work with generic associated types](rust-lang/rust#81823)
* On 2021-04-28, [Make traits with GATs not object safe](rust-lang/rust#84622)
* On 2021-05-11, [Improve diagnostics for GATs](rust-lang/rust#82272)
* On 2021-07-16, [Make GATs no longer an incomplete feature](rust-lang/rust#84623)
* On 2021-07-16, [Replace associated item bound vars with placeholders when projecting](rust-lang/rust#86993)
* On 2021-07-26, [GATs: Decide whether to have defaults for `where Self: 'a`](rust-lang/rust#87479)
* On 2021-08-25, [Normalize projections under binders](rust-lang/rust#85499)
* On 2021-08-03, [The push for GATs stabilization](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html)
* On 2021-08-12, [Detect stricter constraints on gats where clauses in impls vs trait](rust-lang/rust#88336)
* On 2021-09-20, [Proposal: Change syntax of where clauses on type aliases](rust-lang/rust#89122)
* On 2021-11-06, [Implementation of GATs outlives lint](rust-lang/rust#89970)
* On 2021-12-29. [Parse and suggest moving where clauses after equals for type aliases](rust-lang/rust#92118)
* On 2022-01-15, [Ignore static lifetimes for GATs outlives lint](rust-lang/rust#92865)
* On 2022-02-08, [Don't constrain projection predicates with inference vars in GAT substs](rust-lang/rust#92917)
* On 2022-02-15, [Rework GAT where clause check](rust-lang/rust#93820)
* On 2022-02-19, [Only mark projection as ambiguous if GAT substs are constrained](rust-lang/rust#93892)
* On 2022-03-03, [Support GATs in Rustdoc](rust-lang/rust#94009)
* On 2022-03-06, [Change location of where clause on GATs](rust-lang/rust#90076)
* On 2022-05-04, [A shiny future with GATs blog post](https://jackh726.github.io/rust/2022/05/04/a-shiny-future-with-gats.html)
* On 2022-05-04, [Stabilization PR](rust-lang/rust#96709)
@dhedey
Copy link

dhedey commented Jan 30, 2023

I've just been pointed to this issue, where the suggested where Self: 'a bound was incorrect - so I thought it worth noting it here as an additional example.

Roughly speaking, there was a template object, and there was a method to create an instance from the template and install a runtime reference into it.

Adding a bound that the Template outlives the Runtime was too restrictive and caused issues elsewhere.

pub trait Template {
    type Instance<'r>;

    fn create_with_runtime<'r>(
        &self,
        runtime: &'r Runtime
    ) -> Self::Instance<'r>;
}

Personally, I prefer explicit code, so I'd rather require a where Self: 'a bound is explicitly specified where necessary. I think the bound is rather natural to need to add, and the syntax is actually quite nice.

If the bound was added automatically, there wouldn't even be an obvious link to this issue with the workaround, in the case this bound were not required.

@yshui
Copy link
Contributor

yshui commented Feb 7, 2023

I have another case where this bound is undesirable. Although this might be somewhat similar to #87479 (comment)

Imagine we have an AsIterator trait for things whose references can be converted to an iterator:

pub trait AsIterator {
    type Item<'a> where Self: 'a;
    type Iter<'a>: Iterator<Item=Self::Item<'a>> where Self: 'a;
    fn as_iter(&self) -> Self::Iter<'_>;
}

In a function that uses this trait, we might want to be able to say something about the items returned:

fn bound<T>() where T: for<'a> AsIterator<Item<'a> = &'a u32> {
    
}

However, this essentially puts a T: 'static requirement because of this Self: 'a bound. This is also somewhat related to: https://sabrinajewson.org/blog/the-better-alternative-to-lifetime-gats

A workaround suggested in the article is:

pub trait IteratorItem<'a> {
	type Item;
}
pub trait AsIterator {
    type Item: ?Sized + for<'a> IteratorItem<'a>;
    type Iter<'a>: Iterator<Item=<Self::Item as IteratorItem<'a>>::Item> where Self: 'a;
    fn as_iter(&self) -> Self::Iter<'_>;
}

And use type Item = dyn for<'a> IteratorItem<'a, Item = &'a u32>; in impl, basically emulating lifetime GAT with HRTB trait objects, to workaround the required where Self: 'a bound.

@QuineDot
Copy link

Ran into this again today in the context of abstracting over owning or borrowing a known-'static type.

// Does not compile due to this lint
trait Get {
    type Ref<'a>;
    fn get(&self) -> Self::Ref<'_>;
}

impl Get for Owning {
    type Ref<'a> = Ret<'a>;
    fn get(&self) -> Self::Ref<'_> {
        Ret(&self.value)
    }
}

impl<'a> Get for Borrowing<'a> {
    type Ref<'any> = Ret<'a>;
    fn get(&self) -> Self::Ref<'a> {
        self.owned.get()
    }
}

And I would like to stress again that the workaround which maintains GAT ergonomics is unintuitive and pollutes the trait, and yet is still preferable to the "official" workaround of a lifetime carrying trait in my estimation.

 trait Get {
     type Ref<'a>;
     fn get(&self) -> Self::Ref<'_>;
+    fn _silence_incorrect_lint(_: &Self::Ref<'_>) {}
 }

Therefore, a better way to disable the lint / inference should be designed and implemented before the inference is finalized, assuming the inference isn't dropped.

@jackh726
Copy link
Member

@dhedey

Can you please post more information about the issues you ran into? A small snippet of code is not very helpful to understand the full problem.

@yshui

The problem you ran is because of a bug. Once fixed, the where Self: 'a bound should be fine.

@QuineDot

Having trouble figuring out the problem here. Yes, the lint fires and might seem at first glance wrong, but following the compiler's suggestions leads this code to compile fine. Is there a larger piece of code that demonstrates a problem?

@dhedey
Copy link

dhedey commented Mar 22, 2023

@jackh726 - Sure. I'll try to describe the setup, in case some additional context helps.

We're running single-threaded. We had a setup where we were creating WASM instances. Many of these instances were going to be the same code, but needed to be created with clean state. These instances were therefore created from a template. Upon instantiation, these templates captured a reference to a runtime, which they could then use for sys-calls. We were trialling a few different WASM runners, so were abstracting with traits over their common interfaces.

Each WASM instance we create starts off with some code, with the process being: take the WASM code, instrument it and prepare it to get a Template. Then, when you want to run an instance, you call a method on the template to instantiate the template, passing a reference to the runtime.

This returns an instance which captures the reference, and thus has a lifetime which is shorter than the runtime - and, importantly, independent of the Template. (The template's lifetime is irrelevant after each instantiation, although typically, is actually longer than the runtime, but could potentially be shorter).

We therefore produce this trait - and importantly, Instance<'r> should not have a where Self: 'r bound - because, as mentioned, the lifetime of the template is not related to the lifetime of the instance.

pub trait Template {
    type Instance<'r>: Instance;

    fn create_with_runtime<'r>(
        &self,
        runtime: &'r Runtime
    ) -> Self::Instance<'r>;
}

It could be that I'm misunderstanding some corner case, or using GATs wrong, if so, happy to be corrected - although I imagine other people may want to do something similar in future.

@nikomatsakis
Copy link
Contributor Author

@dhedey I made a standalone version of your code...

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c45d7fe1d38cf8b8c69bafeec266e7c9

...just to be clear, though, this pattern compiles today (and hence would not be affected by any default that matched the required bounds), right?

@jackh726
Copy link
Member

Right @dhedey, I think this is fine. The title of this issue is not 100% accurate, because it's exactly requiring where Self: 'a, but rather more "intuitively" requiring what can already be proven when using the GAT (and gets used in the GAT projection).

For your example, the anonymous lifetime in &self doesn't get passed to Self::Instance, so we don't require the Self: 'r bound to be written.

@dhedey
Copy link

dhedey commented Mar 22, 2023

@nikomatsakis , @jackh726 - ahh sorry, I didn't think to use the playground. I think in the interests of simple exposition I overly simplified the previous code - there was another lifetime on eg MyTemplate<'a> which tripped things up.

So I've taken your playground link and updated it to something which only compiles if where Self: 'r is not included: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=30ef9ff7bb5d02862fb7ccc488fcb7de

But - as you rightfully point out, it compiles fine without the where Self: 'r bound, and there doesn't appear to be a lint telling me to add it in the playground / on latest rust version, so it's working splendidly now.

At the time, I definitely somehow got a lint which told me I had to add where Self: 'r / directed me to this page - and I believe that adding this bound then broke my code - but it could be that (A) I'm mis-remembering something and my code did reference the lifetime of &self somehow in one iteration which led me here, and then I got confused by the initial comment in the PR, or (B) this behaviour has got more clever in more recent versions of rust.

Either way it's working splendidly now, so apologies for wasting anyones' time - and thanks for all the great work everyone's doing on Rust :)

@yshui
Copy link
Contributor

yshui commented Mar 30, 2023

@jackh726

The problem you ran is because of a bug. Once fixed, the where Self: 'a bound should be fine.

Is there a related issue for this, if this is a bug?

@QuineDot
Copy link

QuineDot commented Jun 9, 2023

#90696 and #111852 have programs where eliding the Self: 'a GAT bound works around some bugs.

@yshui these may be the related issue(s) you asked about?

@spikespaz
Copy link

I have a problem when I want to use a type with a trait using where Self: 'a in a loop, borrowing mutably.

I have defined the trait as follows:

pub trait Buffered
where
    Self: Iterator,
{
    type ItemSlice<'a>
    where
        Self: 'a;

    /// Consume up to `count` items from the internal iterator, moving them into
    /// the buffer. Return an optional reference to the buffer's items.
    ///
    /// If the iterator did not contain enough items to satisfy `count`, `None`
    /// will be returned. In this case, the only way to get the remaining items
    /// out is by consuming the iterator normally.
    fn buffer(&mut self, count: usize) -> Option<Self::ItemSlice<'_>>;
}

Now I use it in two places:

impl<S> Buffered for SourceBytes<S>
where
    S: Iterator<Item = u8>,
{
    type ItemSlice<'a> = &'a [S::Item] where Self: 'a;

    fn buffer(&mut self, count: usize) -> Option<&[S::Item]> {
        if self.buffer.len() < count {
            self.buffer
                .extend(self.iter.by_ref().take(count - self.buffer.len()));
        }
        self.buffer.get(0..count)
    }
}

That one was easy. But now, if I want to have SourceChars (a wrapper on any Iterator<Item = u8> that iterates characters) , I can't use self.0.buffer in a loop because it has already been borrowed in a previous iteration of the loop.

impl<S> Buffered for SourceChars<S>
where
    for<'a> S: Iterator<Item = u8> + Buffered<ItemSlice<'a> = &'a [u8]> + 'a,
{
    type ItemSlice<'a> = &'a str where Self: 'a;

    fn buffer(&mut self, count: usize) -> Option<Self::ItemSlice<'_>> {
        for byte in 0.. {
            let buf = self.0.buffer(byte)?;
            if let Ok(slice) = std::str::from_utf8(&buf) {
                if slice.chars().count() >= count {
                    return Some(slice);
                }
            }
        }
        None
    }
}
error[E0499]: cannot borrow `self.0` as mutable more than once at a time
   --> src/parser/iter.rs:111:23
    |
109 |     fn buffer(&mut self, count: usize) -> Option<Self::ItemSlice<'_>> {
    |               - let's call the lifetime of this reference `'1`
110 |         for byte in 0.. {
111 |             let buf = self.0.buffer(byte)?;
    |                       ^^^^^^ `self.0` was mutably borrowed here in the previous iteration of the loop
...
114 |                     return Some(slice);
    |                            ----------- returning this value requires that `self.0` is borrowed for `'1`

I'm being told that the real representation I want is impossible with the current syntax for GATs.

@Kixunil
Copy link
Contributor

Kixunil commented Jan 20, 2024

I struggle to understand why not having the where bound is an issue with GAT but not with this trick I use to simulate GAT in older MSRVs:

trait EncodeTc<'a> {
    type Encoder: Encoder;
}

trait Encode: for<'a> Self: EncodeTc<'a> {
    fn encoder(&self) -> <Self as EncodeTc<'_>>::Encoder;
}

I don't see anything telling the compiler that Self: 'a yet AFAICT this works perfectly fine. I've even implemented a macro that can use GAT syntax to impl the trait (so that once MSRV bumps it'll be a simple change). Is there a problem lurking there that I will hit eventually? Also why did the GAT work take so much time if it looks like it could be just a syntax sugar for what I wrote? I must be missing something.

@QuineDot
Copy link

@Kixunil There are situations where your pattern fails because the implementation of EncodeTc<'a> requires Self: 'a.

For example:

impl Encoder for &&str {}
impl<'a, 'b> EncodeTc<'a> for &'b str {
    type Encoder = &'a &'b str;
}

Can't work without the bound:

error[E0491]: in type `&'a &'b str`, reference has a longer lifetime than the data it references
  --> src/lib.rs:13:20
   |
13 |     type Encoder = &'a &'b str;
   |                    ^^^^^^^^^^^

So you add the bound...

// This part now compiles due to `'b: 'a`
impl<'a, 'b: 'a> EncodeTc<'a> for &'b str {
    type Encoder = &'a &'b str;
}

...but now the HRTB can't hold due to the extra constraint (which is not present in the HRTB).

impl<'b> Encode for &'b str {
    fn encoder(&self) -> <Self as EncodeTc<'_>>::Encoder {
        self
    }
}

(intermediate playground)

error: implementation of `EncodeTc` is not general enough
  --> src/lib.rs:16:21
   |
16 | impl<'b> Encode for &'b str {
   |                     ^^^^^^^ implementation of `EncodeTc` is not general enough
   |
   = note: `EncodeTc<'0>` would have to be implemented for the type `&'b str`, for any lifetime `'0`...
   = note: ...but `EncodeTc<'_>` is actually implemented for the type `&'1 str`, for some specific lifetime `'1`

You can work around this like so:

// Default type parameter with an implied `Self: 'a` bound
//               vvvvvvvvvvvvvvvvvvvvvvvvvvv
trait EncodeTc<'a, _LifetimeBound = &'a Self> {
    type Encoder: Encoder;
}

//   vvvvvv  Explicit `'b: 'a` bound no longer required
impl<'a, 'b> EncodeTc<'a> for &'b str {
    type Encoder = &'a &'b str;
}

And now the HRTB can be met, as the HRTB honors the implied bound.


The implied bound in the default type parameter is telling the compiler that Self: 'a. With GATs, you use a where clause on the GAT instead.

RalfJung pushed a commit to RalfJung/rust-analyzer that referenced this issue Apr 20, 2024
Stabilize generic associated types

Closes #44265

r? `@nikomatsakis`

# ⚡ Status of the discussion ⚡

* [x] There have been several serious concerns raised, [summarized here](rust-lang/rust#96709 (comment)).
* [x] There has also been a [deep-dive comment](rust-lang/rust#96709 (comment)) explaining some of the "patterns of code" that are enabled by GATs, based on use-cases posted to this thread or on the tracking issue.
* [x] We have modeled some aspects of GATs in [a-mir-formality](https://github.com/nikomatsakis/a-mir-formality) to give better confidence in how they will be resolved in the future. [You can read a write-up here](https://github.com/rust-lang/types-team/blob/master/minutes/2022-07-08-implied-bounds-and-wf-checking.md).
* [x] The major points of the discussion have been [summarized on the GAT initiative repository](https://rust-lang.github.io/generic-associated-types-initiative/mvp.html).
* [x] [FCP has been proposed](rust-lang/rust#96709 (comment)) and we are awaiting final decisions and discussion amidst the relevant team members.

# Stabilization proposal

This PR proposes the stabilization of `#![feature(generic_associated_types)]`. While there a number of future additions to be made and bugs to be fixed (both discussed below), properly doing these will require significant language design and will ultimately likely be backwards-compatible. Given the overwhelming desire to have some form of generic associated types (GATs) available on stable and the stability of the "simple" uses, stabilizing the current subset of GAT features is almost certainly the correct next step.

Tracking issue: #44265
Initiative: https://rust-lang.github.io/generic-associated-types-initiative/
RFC: https://github.com/rust-lang/rfcs/blob/master/text/1598-generic_associated_types.md
Version: 1.65 (2022-08-22 => beta, 2022-11-03 => stable).

## Motivation

There are a myriad of potential use cases for GATs. Stabilization unblocks probable future language features (e.g. async functions in traits), potential future standard library features (e.g. a `LendingIterator` or some form of `Iterator` with a lifetime generic), and a plethora of user use cases (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it).

There are a myriad of potential use cases for GATs. First, there are many users that have chosen to not use GATs primarily because they are not stable (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it). Second, while language feature desugaring isn't *blocked* on stabilization, it gives more confidence on using the feature. Likewise, library features like `LendingIterator` are not necessarily blocked on stabilization to be implemented unstably; however few, if any, public-facing APIs actually use unstable features.

This feature has a long history of design, discussion, and developement - the RFC was first introduced roughly 6 years ago. While there are still a number of features left to implement and bugs left to fix, it's clear that it's unlikely those will have backwards-incompatibility concerns. Additionally, the bugs that do exist do not strongly impede the most-common use cases.

## What is stabilized

The primary language feature stabilized here is the ability to have generics on associated types, as so. Additionally, where clauses on associated types will now be accepted, regardless if the associated type is generic or not.

```rust
trait ATraitWithGATs {
    type Assoc<'a, T> where T: 'a;
}

trait ATraitWithoutGATs<'a, T> {
    type Assoc where T: 'a;
}
```

When adding an impl for a trait with generic associated types, the generics for the associated type are copied as well. Note that where clauses are allowed both after the specified type and before the equals sign; however, the latter is a warn-by-default deprecation.

```rust
struct X;
struct Y;

impl ATraitWithGATs for X {
    type Assoc<'a, T> = &'a T
      where T: 'a;
}
impl ATraitWithGATs for Y {
    type Assoc<'a, T>
      where T: 'a
    = &'a T;
}
```

To use a GAT in a function, generics are specified on the associated type, as if it was a struct or enum. GATs can also be specified in trait bounds:

```rust
fn accepts_gat<'a, T>(t: &'a T) -> T::Assoc<'a, T>
  where for<'x> T: ATraitWithGATs<Assoc<'a, T> = &'a T> {
    ...
}
```

GATs can also appear in trait methods. However, depending on how they are used, they may confer where clauses on the associated type definition. More information can be found [here](rust-lang/rust#87479). Briefly, where clauses are required when those bounds can be proven in the methods that *construct* the GAT or other associated types that use the GAT in the trait. This allows impls to have maximum flexibility in the types defined for the associated type.

To take a relatively simple example:

```rust
trait Iterable {
    type Item<'a>;
    type Iterator<'a>: Iterator<Item = Self::Item<'a>>;

    fn iter<'x>(&'x self) -> Self::Iterator<'x>;
    //^ We know that `Self: 'a` for `Iterator<'a>`, so we require that bound on `Iterator`
    //  `Iterator` uses `Self::Item`, so we also require a `Self: 'a` on `Item` too
}
```

A couple well-explained examples are available in a previous [blog post](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html).

## What isn't stabilized/implemented

### Universal type/const quantification

Currently, you can write a bound like `X: for<'a> Trait<Assoc<'a> = &'a ()>`. However, you cannot currently write `for<T> X: Trait<Assoc<T> = T>` or `for<const N> X: Trait<Assoc<N> = [usize; N]>`.

Here is an example where this is needed:

```rust
trait Foo {}

trait Trait {
    type Assoc<F: Foo>;
}

trait Trait2: Sized {
    fn foo<F: Foo, T: Trait<Assoc<F> = F>>(_t: T);
}
```

In the above example, the *caller* must specify `F`, which is likely not what is desired.

### Object-safe GATs

Unlike non-generic associated types, traits with GATs are not currently object-safe. In other words the following are not allowed:

```rust
trait Trait {
    type Assoc<'a>;
}

fn foo(t: &dyn for<'a> Trait<Assoc<'a> = &'a ()>) {}
         //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed

let ty: Box<dyn for<'a> Trait<Assoc<'a> = &'a ()>>;
          //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed
```

### Higher-kinded types

You cannot write currently (and there are no current plans to implement this):

```rust
struct Struct<'a> {}

fn foo(s: for<'a> Struct<'a>) {}
```

## Tests

There are many tests covering GATs that can be found in  `src/test/ui/generic-associated-types`. Here, I'll list (in alphanumeric order) tests highlight some important behavior or contain important patterns.

- `./parse/*`: Parsing of GATs in traits and impls, and the trait path with GATs
- `./collections-project-default.rs`: Interaction with associated type defaults
- `./collections.rs`: The `Collection` pattern
- `./const-generics-gat-in-trait-return-type-*.rs`: Const parameters
- `./constraint-assoc-type-suggestion.rs`: Emit correct syntax in suggestion
- `./cross-crate-bounds.rs`: Ensure we handles bounds across crates the same
- `./elided-in-expr-position.rs`: Disallow lifetime elision in return position
- `./gat-in-trait-path-undeclared-lifetime.rs`: Ensure we error on undeclared lifetime in trait path
- `./gat-in-trait-path.rs`: Base trait path case
- `./gat-trait-path-generic-type-arg.rs`: Don't allow shadowing of parameters
- `./gat-trait-path-parenthesised-args.rs`: Don't allow paranthesized args in trait path
- `./generic-associated-types-where.rs`: Ensure that we require where clauses from trait to be met on impl
- `./impl_bounds.rs`: Check that the bounds on GATs in an impl are checked
- `./issue-76826.rs`: `Windows` pattern
- `./issue-78113-lifetime-mismatch-dyn-trait-box.rs`: Implicit 'static diagnostics
- `./issue-84931.rs`: Ensure that we have a where clause on GAT to ensure trait parameter lives long enough
- `./issue-87258_a.rs`: Unconstrained opaque type with TAITs
- `./issue-87429-2.rs`: Ensure we can use bound vars in the bounds
- `./issue-87429-associated-type-default.rs`: Ensure bounds hold with associated type defaults, for both trait and impl
- `./issue-87429-specialization.rs`: Check that bounds hold under specialization
- `./issue-88595.rs`: Under the outlives lint, we require a bound for both trait and GAT lifetime when trait lifetime is used in function
- `./issue-90014.rs`: Lifetime bounds are checked with TAITs
- `./issue-91139.rs`: Under migrate mode, but not NLL, we don't capture implied bounds from HRTB lifetimes used in a function and GATs
- `./issue-91762.rs`: We used to too eagerly pick param env candidates when normalizing with GATs. We now require explicit parameters specified.
- `./issue-95305.rs`: Disallow lifetime elision in trait paths
- `./iterable.rs`: `Iterable` pattern
- `./method-unsatified-assoc-type-predicate.rs`: Print predicates with GATs correctly in method resolve error
- `./missing_lifetime_const.rs`: Ensure we must specify lifetime args (not elidable)
- `./missing-where-clause-on-trait.rs`: Ensure we don't allow stricter bounds on impl than trait
- `./parameter_number_and_kind_impl.rs`: Ensure paramters on GAT in impl match GAT in trait
- `./pointer_family.rs`: `PointerFamily` pattern
- `./projection-bound-cycle.rs`: Don't allow invalid cycles to prove bounds
- `./self-outlives-lint.rs`: Ensures that an e.g. `Self: 'a` is written on the traits GAT if that bound can be implied from the GAT usage in the trait
- `./shadowing.rs`: Don't allow lifetime shadowing in params
- `./streaming_iterator.rs`: `StreamingIterator`(`LendingIterator`) pattern
- `./trait-objects.rs`: Disallow trait objects for traits with GATs
- `./variance_constraints.rs`: Require that GAT substs be invariant

## Remaining bugs and open issues

A full list of remaining open issues can be found at: https://github.com/rust-lang/rust/labels/F-generic_associated_types

There are some `known-bug` tests in-tree at `src/test/ui/generic-associated-types/bugs`.

Here I'll categorize most of those that GAT bugs (or involve a pattern found more with GATs), but not those that include GATs but not a GAT issue in and of itself. (I also won't include issues directly for things listed elsewhere here.)

Using the concrete type of a GAT instead of the projection type can give errors, since lifetimes are chosen to be early-bound vs late-bound.
- #85533
- #87803

In certain cases, we can run into cycle or overflow errors. This is more generally a problem with associated types.
- #87755
- #87758

Bounds on an associatd type need to be proven by an impl, but where clauses need to be proven by the usage. This can lead to confusion when users write one when they mean the other.
- #87831
- #90573

We sometimes can't normalize closure signatures fully. Really an asociated types issue, but might happen a bit more frequently with GATs, since more obvious place for HRTB lifetimes.
- #88382

When calling a function, we assign types to parameters "too late", after we already try (and fail) to normalize projections. Another associated types issue that might pop up more with GATs.
- #88460
- #96230

We don't fully have implied bounds for lifetimes appearing in GAT trait paths, which can lead to unconstrained type errors.
- #88526

Suggestion for adding lifetime bounds can suggest unhelpful fixes (`T: 'a` instead of `Self: 'a`), but the next compiler error after making the suggested change is helpful.
- #90816
- #92096
- #95268

We can end up requiring that `for<'a> I: 'a` when we really want `for<'a where I: 'a> I: 'a`. This can leave unhelpful errors than effectively can't be satisfied unless `I: 'static`. Requires bigger changes and not only GATs.
- #91693

Unlike with non-generic associated types, we don't eagerly normalize with param env candidates. This is intended behavior (for now), to avoid accidentaly stabilizing picking arbitrary impls.
- #91762

Some Iterator adapter patterns (namely `filter`) require Polonius or unsafe to work.
- #92985

## Potential Future work

### Universal type/const quantification

No work has been done to implement this. There are also some questions around implied bounds.

###  Object-safe GATs

The intention is to make traits with GATs object-safe. There are some design work to be done around well-formedness rules and general implementation.

### GATified std lib types

It would be helpful to either introduce new std lib traits (like `LendingIterator`) or to modify existing ones (adding a `'a` generic to `Iterator::Item`). There also a number of other candidates, like `Index`/`IndexMut` and `Fn`/`FnMut`/`FnOnce`.

### Reduce the need for `for<'a>`

Seen [here](rust-lang/rfcs#1598 (comment)). One possible syntax:

```rust
trait Iterable {
    type Iter<'a>: Iterator<Item = Self::Item<'a>>;
}

fn foo<T>() where T: Iterable, T::Item<let 'a>: Display { } //note the `let`!
```

### Better implied bounds on higher-ranked things

Currently if we have a `type Item<'a> where self: 'a`, and a `for<'a> T: Iterator<Item<'a> = &'a ()`, this requires `for<'a> Self: 'a`. Really, we want `for<'a where T: 'a> ...`

There was some mentions of this all the back in the RFC thread [here](rust-lang/rfcs#1598 (comment)).

## Alternatives

### Make generics on associated type in bounds a binder

Imagine the bound `for<'a> T: Trait<Item<'a>= &'a ()>`. It might be that `for<'a>` is "too large" and it should instead be `T: Trait<for<'a> Item<'a>= &'a ()>`. Brought up in RFC thread [here](rust-lang/rfcs#1598 (comment)) and in a few places since.

Another related question: Is `for<'a>` the right syntax? Maybe `where<'a>`? Also originally found in RFC thread [here](rust-lang/rfcs#1598 (comment)).

### Stabilize lifetime GATs first

This has been brought up a few times. The idea is to only allow GATs with lifetime parameters to in initial stabilization. This was probably most useful prior to actual implementation. At this point, lifetimes, types, and consts are all implemented and work. It feels like an arbitrary split without strong reason.

## History

* On 2016-04-30, [RFC opened](rust-lang/rfcs#1598)
* On 2017-09-02, RFC merged and [tracking issue opened](rust-lang/rust#44265)
* On 2017-10-23, [Move Generics from MethodSig to TraitItem and ImplItem](rust-lang/rust#44766)
* On 2017-12-01, [Generic Associated Types Parsing & Name Resolution](rust-lang/rust#45904)
* On 2017-12-15, [https://github.com/rust-lang/rust/pull/46706](https://github.com/rust-lang/rust/pull/46706)
* On 2018-04-23, [Feature gate where clauses on associated types](rust-lang/rust#49368)
* On 2018-05-10, [Extend tests for RFC1598 (GAT)](rust-lang/rust#49423)
* On 2018-05-24, [Finish implementing GATs (Chalk)](rust-lang/chalk#134)
* On 2019-12-21, [Make GATs less ICE-prone](rust-lang/rust#67160)
* On 2020-02-13, [fix lifetime shadowing check in GATs](rust-lang/rust#68938)
* On 2020-06-20, [Projection bound validation](rust-lang/rust#72788)
* On 2020-10-06, [Separate projection bounds and predicates](rust-lang/rust#73905)
* On 2021-02-05, [Generic associated types in trait paths](rust-lang/rust#79554)
* On 2021-02-06, [Trait objects do not work with generic associated types](rust-lang/rust#81823)
* On 2021-04-28, [Make traits with GATs not object safe](rust-lang/rust#84622)
* On 2021-05-11, [Improve diagnostics for GATs](rust-lang/rust#82272)
* On 2021-07-16, [Make GATs no longer an incomplete feature](rust-lang/rust#84623)
* On 2021-07-16, [Replace associated item bound vars with placeholders when projecting](rust-lang/rust#86993)
* On 2021-07-26, [GATs: Decide whether to have defaults for `where Self: 'a`](rust-lang/rust#87479)
* On 2021-08-25, [Normalize projections under binders](rust-lang/rust#85499)
* On 2021-08-03, [The push for GATs stabilization](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html)
* On 2021-08-12, [Detect stricter constraints on gats where clauses in impls vs trait](rust-lang/rust#88336)
* On 2021-09-20, [Proposal: Change syntax of where clauses on type aliases](rust-lang/rust#89122)
* On 2021-11-06, [Implementation of GATs outlives lint](rust-lang/rust#89970)
* On 2021-12-29. [Parse and suggest moving where clauses after equals for type aliases](rust-lang/rust#92118)
* On 2022-01-15, [Ignore static lifetimes for GATs outlives lint](rust-lang/rust#92865)
* On 2022-02-08, [Don't constrain projection predicates with inference vars in GAT substs](rust-lang/rust#92917)
* On 2022-02-15, [Rework GAT where clause check](rust-lang/rust#93820)
* On 2022-02-19, [Only mark projection as ambiguous if GAT substs are constrained](rust-lang/rust#93892)
* On 2022-03-03, [Support GATs in Rustdoc](rust-lang/rust#94009)
* On 2022-03-06, [Change location of where clause on GATs](rust-lang/rust#90076)
* On 2022-05-04, [A shiny future with GATs blog post](https://jackh726.github.io/rust/2022/05/04/a-shiny-future-with-gats.html)
* On 2022-05-04, [Stabilization PR](rust-lang/rust#96709)
RalfJung pushed a commit to RalfJung/rust-analyzer that referenced this issue Apr 27, 2024
Stabilize generic associated types

Closes #44265

r? `@nikomatsakis`

# ⚡ Status of the discussion ⚡

* [x] There have been several serious concerns raised, [summarized here](rust-lang/rust#96709 (comment)).
* [x] There has also been a [deep-dive comment](rust-lang/rust#96709 (comment)) explaining some of the "patterns of code" that are enabled by GATs, based on use-cases posted to this thread or on the tracking issue.
* [x] We have modeled some aspects of GATs in [a-mir-formality](https://github.com/nikomatsakis/a-mir-formality) to give better confidence in how they will be resolved in the future. [You can read a write-up here](https://github.com/rust-lang/types-team/blob/master/minutes/2022-07-08-implied-bounds-and-wf-checking.md).
* [x] The major points of the discussion have been [summarized on the GAT initiative repository](https://rust-lang.github.io/generic-associated-types-initiative/mvp.html).
* [x] [FCP has been proposed](rust-lang/rust#96709 (comment)) and we are awaiting final decisions and discussion amidst the relevant team members.

# Stabilization proposal

This PR proposes the stabilization of `#![feature(generic_associated_types)]`. While there a number of future additions to be made and bugs to be fixed (both discussed below), properly doing these will require significant language design and will ultimately likely be backwards-compatible. Given the overwhelming desire to have some form of generic associated types (GATs) available on stable and the stability of the "simple" uses, stabilizing the current subset of GAT features is almost certainly the correct next step.

Tracking issue: #44265
Initiative: https://rust-lang.github.io/generic-associated-types-initiative/
RFC: https://github.com/rust-lang/rfcs/blob/master/text/1598-generic_associated_types.md
Version: 1.65 (2022-08-22 => beta, 2022-11-03 => stable).

## Motivation

There are a myriad of potential use cases for GATs. Stabilization unblocks probable future language features (e.g. async functions in traits), potential future standard library features (e.g. a `LendingIterator` or some form of `Iterator` with a lifetime generic), and a plethora of user use cases (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it).

There are a myriad of potential use cases for GATs. First, there are many users that have chosen to not use GATs primarily because they are not stable (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it). Second, while language feature desugaring isn't *blocked* on stabilization, it gives more confidence on using the feature. Likewise, library features like `LendingIterator` are not necessarily blocked on stabilization to be implemented unstably; however few, if any, public-facing APIs actually use unstable features.

This feature has a long history of design, discussion, and developement - the RFC was first introduced roughly 6 years ago. While there are still a number of features left to implement and bugs left to fix, it's clear that it's unlikely those will have backwards-incompatibility concerns. Additionally, the bugs that do exist do not strongly impede the most-common use cases.

## What is stabilized

The primary language feature stabilized here is the ability to have generics on associated types, as so. Additionally, where clauses on associated types will now be accepted, regardless if the associated type is generic or not.

```rust
trait ATraitWithGATs {
    type Assoc<'a, T> where T: 'a;
}

trait ATraitWithoutGATs<'a, T> {
    type Assoc where T: 'a;
}
```

When adding an impl for a trait with generic associated types, the generics for the associated type are copied as well. Note that where clauses are allowed both after the specified type and before the equals sign; however, the latter is a warn-by-default deprecation.

```rust
struct X;
struct Y;

impl ATraitWithGATs for X {
    type Assoc<'a, T> = &'a T
      where T: 'a;
}
impl ATraitWithGATs for Y {
    type Assoc<'a, T>
      where T: 'a
    = &'a T;
}
```

To use a GAT in a function, generics are specified on the associated type, as if it was a struct or enum. GATs can also be specified in trait bounds:

```rust
fn accepts_gat<'a, T>(t: &'a T) -> T::Assoc<'a, T>
  where for<'x> T: ATraitWithGATs<Assoc<'a, T> = &'a T> {
    ...
}
```

GATs can also appear in trait methods. However, depending on how they are used, they may confer where clauses on the associated type definition. More information can be found [here](rust-lang/rust#87479). Briefly, where clauses are required when those bounds can be proven in the methods that *construct* the GAT or other associated types that use the GAT in the trait. This allows impls to have maximum flexibility in the types defined for the associated type.

To take a relatively simple example:

```rust
trait Iterable {
    type Item<'a>;
    type Iterator<'a>: Iterator<Item = Self::Item<'a>>;

    fn iter<'x>(&'x self) -> Self::Iterator<'x>;
    //^ We know that `Self: 'a` for `Iterator<'a>`, so we require that bound on `Iterator`
    //  `Iterator` uses `Self::Item`, so we also require a `Self: 'a` on `Item` too
}
```

A couple well-explained examples are available in a previous [blog post](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html).

## What isn't stabilized/implemented

### Universal type/const quantification

Currently, you can write a bound like `X: for<'a> Trait<Assoc<'a> = &'a ()>`. However, you cannot currently write `for<T> X: Trait<Assoc<T> = T>` or `for<const N> X: Trait<Assoc<N> = [usize; N]>`.

Here is an example where this is needed:

```rust
trait Foo {}

trait Trait {
    type Assoc<F: Foo>;
}

trait Trait2: Sized {
    fn foo<F: Foo, T: Trait<Assoc<F> = F>>(_t: T);
}
```

In the above example, the *caller* must specify `F`, which is likely not what is desired.

### Object-safe GATs

Unlike non-generic associated types, traits with GATs are not currently object-safe. In other words the following are not allowed:

```rust
trait Trait {
    type Assoc<'a>;
}

fn foo(t: &dyn for<'a> Trait<Assoc<'a> = &'a ()>) {}
         //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed

let ty: Box<dyn for<'a> Trait<Assoc<'a> = &'a ()>>;
          //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed
```

### Higher-kinded types

You cannot write currently (and there are no current plans to implement this):

```rust
struct Struct<'a> {}

fn foo(s: for<'a> Struct<'a>) {}
```

## Tests

There are many tests covering GATs that can be found in  `src/test/ui/generic-associated-types`. Here, I'll list (in alphanumeric order) tests highlight some important behavior or contain important patterns.

- `./parse/*`: Parsing of GATs in traits and impls, and the trait path with GATs
- `./collections-project-default.rs`: Interaction with associated type defaults
- `./collections.rs`: The `Collection` pattern
- `./const-generics-gat-in-trait-return-type-*.rs`: Const parameters
- `./constraint-assoc-type-suggestion.rs`: Emit correct syntax in suggestion
- `./cross-crate-bounds.rs`: Ensure we handles bounds across crates the same
- `./elided-in-expr-position.rs`: Disallow lifetime elision in return position
- `./gat-in-trait-path-undeclared-lifetime.rs`: Ensure we error on undeclared lifetime in trait path
- `./gat-in-trait-path.rs`: Base trait path case
- `./gat-trait-path-generic-type-arg.rs`: Don't allow shadowing of parameters
- `./gat-trait-path-parenthesised-args.rs`: Don't allow paranthesized args in trait path
- `./generic-associated-types-where.rs`: Ensure that we require where clauses from trait to be met on impl
- `./impl_bounds.rs`: Check that the bounds on GATs in an impl are checked
- `./issue-76826.rs`: `Windows` pattern
- `./issue-78113-lifetime-mismatch-dyn-trait-box.rs`: Implicit 'static diagnostics
- `./issue-84931.rs`: Ensure that we have a where clause on GAT to ensure trait parameter lives long enough
- `./issue-87258_a.rs`: Unconstrained opaque type with TAITs
- `./issue-87429-2.rs`: Ensure we can use bound vars in the bounds
- `./issue-87429-associated-type-default.rs`: Ensure bounds hold with associated type defaults, for both trait and impl
- `./issue-87429-specialization.rs`: Check that bounds hold under specialization
- `./issue-88595.rs`: Under the outlives lint, we require a bound for both trait and GAT lifetime when trait lifetime is used in function
- `./issue-90014.rs`: Lifetime bounds are checked with TAITs
- `./issue-91139.rs`: Under migrate mode, but not NLL, we don't capture implied bounds from HRTB lifetimes used in a function and GATs
- `./issue-91762.rs`: We used to too eagerly pick param env candidates when normalizing with GATs. We now require explicit parameters specified.
- `./issue-95305.rs`: Disallow lifetime elision in trait paths
- `./iterable.rs`: `Iterable` pattern
- `./method-unsatified-assoc-type-predicate.rs`: Print predicates with GATs correctly in method resolve error
- `./missing_lifetime_const.rs`: Ensure we must specify lifetime args (not elidable)
- `./missing-where-clause-on-trait.rs`: Ensure we don't allow stricter bounds on impl than trait
- `./parameter_number_and_kind_impl.rs`: Ensure paramters on GAT in impl match GAT in trait
- `./pointer_family.rs`: `PointerFamily` pattern
- `./projection-bound-cycle.rs`: Don't allow invalid cycles to prove bounds
- `./self-outlives-lint.rs`: Ensures that an e.g. `Self: 'a` is written on the traits GAT if that bound can be implied from the GAT usage in the trait
- `./shadowing.rs`: Don't allow lifetime shadowing in params
- `./streaming_iterator.rs`: `StreamingIterator`(`LendingIterator`) pattern
- `./trait-objects.rs`: Disallow trait objects for traits with GATs
- `./variance_constraints.rs`: Require that GAT substs be invariant

## Remaining bugs and open issues

A full list of remaining open issues can be found at: https://github.com/rust-lang/rust/labels/F-generic_associated_types

There are some `known-bug` tests in-tree at `src/test/ui/generic-associated-types/bugs`.

Here I'll categorize most of those that GAT bugs (or involve a pattern found more with GATs), but not those that include GATs but not a GAT issue in and of itself. (I also won't include issues directly for things listed elsewhere here.)

Using the concrete type of a GAT instead of the projection type can give errors, since lifetimes are chosen to be early-bound vs late-bound.
- #85533
- #87803

In certain cases, we can run into cycle or overflow errors. This is more generally a problem with associated types.
- #87755
- #87758

Bounds on an associatd type need to be proven by an impl, but where clauses need to be proven by the usage. This can lead to confusion when users write one when they mean the other.
- #87831
- #90573

We sometimes can't normalize closure signatures fully. Really an asociated types issue, but might happen a bit more frequently with GATs, since more obvious place for HRTB lifetimes.
- #88382

When calling a function, we assign types to parameters "too late", after we already try (and fail) to normalize projections. Another associated types issue that might pop up more with GATs.
- #88460
- #96230

We don't fully have implied bounds for lifetimes appearing in GAT trait paths, which can lead to unconstrained type errors.
- #88526

Suggestion for adding lifetime bounds can suggest unhelpful fixes (`T: 'a` instead of `Self: 'a`), but the next compiler error after making the suggested change is helpful.
- #90816
- #92096
- #95268

We can end up requiring that `for<'a> I: 'a` when we really want `for<'a where I: 'a> I: 'a`. This can leave unhelpful errors than effectively can't be satisfied unless `I: 'static`. Requires bigger changes and not only GATs.
- #91693

Unlike with non-generic associated types, we don't eagerly normalize with param env candidates. This is intended behavior (for now), to avoid accidentaly stabilizing picking arbitrary impls.
- #91762

Some Iterator adapter patterns (namely `filter`) require Polonius or unsafe to work.
- #92985

## Potential Future work

### Universal type/const quantification

No work has been done to implement this. There are also some questions around implied bounds.

###  Object-safe GATs

The intention is to make traits with GATs object-safe. There are some design work to be done around well-formedness rules and general implementation.

### GATified std lib types

It would be helpful to either introduce new std lib traits (like `LendingIterator`) or to modify existing ones (adding a `'a` generic to `Iterator::Item`). There also a number of other candidates, like `Index`/`IndexMut` and `Fn`/`FnMut`/`FnOnce`.

### Reduce the need for `for<'a>`

Seen [here](rust-lang/rfcs#1598 (comment)). One possible syntax:

```rust
trait Iterable {
    type Iter<'a>: Iterator<Item = Self::Item<'a>>;
}

fn foo<T>() where T: Iterable, T::Item<let 'a>: Display { } //note the `let`!
```

### Better implied bounds on higher-ranked things

Currently if we have a `type Item<'a> where self: 'a`, and a `for<'a> T: Iterator<Item<'a> = &'a ()`, this requires `for<'a> Self: 'a`. Really, we want `for<'a where T: 'a> ...`

There was some mentions of this all the back in the RFC thread [here](rust-lang/rfcs#1598 (comment)).

## Alternatives

### Make generics on associated type in bounds a binder

Imagine the bound `for<'a> T: Trait<Item<'a>= &'a ()>`. It might be that `for<'a>` is "too large" and it should instead be `T: Trait<for<'a> Item<'a>= &'a ()>`. Brought up in RFC thread [here](rust-lang/rfcs#1598 (comment)) and in a few places since.

Another related question: Is `for<'a>` the right syntax? Maybe `where<'a>`? Also originally found in RFC thread [here](rust-lang/rfcs#1598 (comment)).

### Stabilize lifetime GATs first

This has been brought up a few times. The idea is to only allow GATs with lifetime parameters to in initial stabilization. This was probably most useful prior to actual implementation. At this point, lifetimes, types, and consts are all implemented and work. It feels like an arbitrary split without strong reason.

## History

* On 2016-04-30, [RFC opened](rust-lang/rfcs#1598)
* On 2017-09-02, RFC merged and [tracking issue opened](rust-lang/rust#44265)
* On 2017-10-23, [Move Generics from MethodSig to TraitItem and ImplItem](rust-lang/rust#44766)
* On 2017-12-01, [Generic Associated Types Parsing & Name Resolution](rust-lang/rust#45904)
* On 2017-12-15, [https://github.com/rust-lang/rust/pull/46706](https://github.com/rust-lang/rust/pull/46706)
* On 2018-04-23, [Feature gate where clauses on associated types](rust-lang/rust#49368)
* On 2018-05-10, [Extend tests for RFC1598 (GAT)](rust-lang/rust#49423)
* On 2018-05-24, [Finish implementing GATs (Chalk)](rust-lang/chalk#134)
* On 2019-12-21, [Make GATs less ICE-prone](rust-lang/rust#67160)
* On 2020-02-13, [fix lifetime shadowing check in GATs](rust-lang/rust#68938)
* On 2020-06-20, [Projection bound validation](rust-lang/rust#72788)
* On 2020-10-06, [Separate projection bounds and predicates](rust-lang/rust#73905)
* On 2021-02-05, [Generic associated types in trait paths](rust-lang/rust#79554)
* On 2021-02-06, [Trait objects do not work with generic associated types](rust-lang/rust#81823)
* On 2021-04-28, [Make traits with GATs not object safe](rust-lang/rust#84622)
* On 2021-05-11, [Improve diagnostics for GATs](rust-lang/rust#82272)
* On 2021-07-16, [Make GATs no longer an incomplete feature](rust-lang/rust#84623)
* On 2021-07-16, [Replace associated item bound vars with placeholders when projecting](rust-lang/rust#86993)
* On 2021-07-26, [GATs: Decide whether to have defaults for `where Self: 'a`](rust-lang/rust#87479)
* On 2021-08-25, [Normalize projections under binders](rust-lang/rust#85499)
* On 2021-08-03, [The push for GATs stabilization](https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html)
* On 2021-08-12, [Detect stricter constraints on gats where clauses in impls vs trait](rust-lang/rust#88336)
* On 2021-09-20, [Proposal: Change syntax of where clauses on type aliases](rust-lang/rust#89122)
* On 2021-11-06, [Implementation of GATs outlives lint](rust-lang/rust#89970)
* On 2021-12-29. [Parse and suggest moving where clauses after equals for type aliases](rust-lang/rust#92118)
* On 2022-01-15, [Ignore static lifetimes for GATs outlives lint](rust-lang/rust#92865)
* On 2022-02-08, [Don't constrain projection predicates with inference vars in GAT substs](rust-lang/rust#92917)
* On 2022-02-15, [Rework GAT where clause check](rust-lang/rust#93820)
* On 2022-02-19, [Only mark projection as ambiguous if GAT substs are constrained](rust-lang/rust#93892)
* On 2022-03-03, [Support GATs in Rustdoc](rust-lang/rust#94009)
* On 2022-03-06, [Change location of where clause on GATs](rust-lang/rust#90076)
* On 2022-05-04, [A shiny future with GATs blog post](https://jackh726.github.io/rust/2022/05/04/a-shiny-future-with-gats.html)
* On 2022-05-04, [Stabilization PR](rust-lang/rust#96709)
@fmease fmease added A-GATs Area: Generic associated types (GATs) T-types Relevant to the types team, which will review and decide on the PR/issue. and removed F-generic_associated_types `#![feature(generic_associated_types)]` a.k.a. GATs GATs-blocking Issues using the `generic_associated_types` feature that block stabilization labels Sep 24, 2024
@arvidfm
Copy link

arvidfm commented Nov 17, 2024

I've also run into a case where this bound being required is causing issues. It's similar to the HRTB issues above, but in my case it's causing the code to fail to build outright, with no easy solution that I can see beyond the mentioned workaround (splitting the trait into two) or giving up on GATs altogether (moving the lifetime to a trait parameter).


Minimised example (playground):

trait MakeNode {
    type Node<'a> where Self: 'a;
    fn make_node(&self) -> Self::Node<'_>;
}
trait MakeExprNode: for<'b> MakeNode<Node<'b> = &'b i32> {}

Background motivation (playground):

I have some AST nodes used for code generation. There are two levels of the AST, the low-level AST that handles the code generation itself; below simplified:

enum ExprNode<'a> {
    Value(&'a dyn Display),
    Add(Box<ExprNode<'a>>, Box<ExprNode<'a>>),
}

impl Display for ExprNode<'_> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Value(v) => v.fmt(f),
            Self::Add(a, b) => write!(f, "{a} + {b}"),
        }
    }
}

and then a more strongly-typed higher-level AST which can be transformed into the lower-level AST; simplified:

trait MakeNode {
    type Node<'a>: Display where Self: 'a;
    fn make_node(&self) -> Self::Node<'_>;
}

struct Add<T, U>(T, U);

impl<T, U> MakeNode for Add<T, U> {
    type Node<'a> = ExprNode<'a> where Self: 'a;
    fn make_node(&self) -> Self::Node<'_> {
        todo!()
    }
}

(The purpose is to let the higher-level AST ignore certain syntactic details, and to allow multiple low-level backends for the same high-level AST.)

In order to be able to implement this Add::make_node method, we need to ensure that T and U generate expression nodes, so to simplify matters my idea was to create a subtrait which is automatically implemented for all implementors of MakeNode where the node type is an ExprNode:

trait MakeExprNode: for<'b> MakeNode<Node<'b> = ExprNode<'b>> {}
impl<T> MakeExprNode for T where T: for<'b> MakeNode<Node<'b> = ExprNode<'b>> {}

However, the presence of the HRTB in the supertrait bound for MakeExprNode results in this less-than-helpful error:

error[E0311]: the parameter type `Self` may not live long enough
    |
note: ...that is required by this bound
   --> src/lib.rs:127:19
    |
127 |             Self: 'a;
    |                   ^^
    = help: consider adding an explicit lifetime bound `Self: 'b`...

I think this is a limitation of HRTBs applied to bounded GATs, where the upper bound of the HRTB doesn't take the Self: 'b constraint into account. But this issue is exacerbated by the compiler's insistence on the presence of the bound.

If I use the suggested workaround and split the MakeNode trait in two and remove the Self: 'a bound, the definition of MakeExprNode works as-is, and I can implement the MakeNode trait for Add without issue:

trait MakeNodeType {
    type Node<'a>: Display;
}
trait MakeNode: MakeNodeType {
    fn make_node(&self) -> Self::Node<'_>;
}

trait MakeExprNode: for<'b> MakeNode<Node<'b> = ExprNode<'b>> {}
impl<T> MakeExprNode for T where T: for<'b> MakeNode<Node<'b> = ExprNode<'b>> {}

impl<T, U> MakeNodeType for Add<T, U> {
    type Node<'a> = ExprNode<'a>;
}
impl<T, U> MakeNode for Add<T, U>
where
    T: MakeExprNode,
    U: MakeExprNode,
{
    fn make_node(&self) -> Self::Node<'_> {
        ExprNode::Add(self.0.make_node().into(), self.1.make_node().into())
    }
}

But it's very cumbersome to have to implement two traits for every node. And in my case all my GATs are concrete types known to live for 'a, meaning I have no need for the Self: 'a bound to begin with, so it would be nice if there was a less verbose way of opting out of the requirement.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-GATs Area: Generic associated types (GATs) disposition-merge This issue / PR is in PFCP or FCP with a disposition to merge it. finished-final-comment-period The final comment period is finished for this PR / Issue. GATs-triaged Issues using the `generic_associated_types` feature that have been triaged T-lang Relevant to the language team, which will review and decide on the PR/issue. T-types Relevant to the types team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.