🔬 Tracking issue for generic associated types (GAT)

[withoutboats]

This is a tracking issue for generic associated types (rust-lang/rfcs#1598)

TODO:

• Implement (mentoring instructions here)
• Document
• Stabilize

Blocking bugs

• #62521
• #30472 No longer blocking
• #67509
• #67510
• #67512
• #67513
• #68641
• #68642
• #68643
• #68644
• #68645
• #68648
• #68649
• #68650
• #68652
• #68653
• #68656
• #74684

[nikomatsakis]

Here is a kind of implementation plan I will endeavor to keep updated.

• Step one: add support into the AST and pretty-printing
  • Probably the first step is to start parsing the new forms and to add support for them to the AST.
  • See this comment for more detailed thoughts here.
  • We should be able to write some parsing-only tests and also test the pretty-printer hir
  • When we get to HIR lowering, we can error out if any GAT are present
  • We can also do the feature gate then
• More to come

[nikomatsakis]

Let me start by writing about the AST in more detail. First let's discuss how it works today:

A type Foo: Bar [= Baz]; item in a trait definition is defined by this AST variant. That includes the bounds (Bar) and the (optional) default value Baz. The name is defined in the TraitItem struct.

A type Foo = Bar; item in a trait impl is defined by this AST variant -- that only includes the type Bar, because the Foo etc is defined in the ImplItem struct.

Methods are an interesting case because they can already be made generic. Those generic parameters are declared in the field Generics of the MethodSig structure. This is an instance of the Generics struct.

My take is that the best thing to do would be to "lift" Generics out from methods into the TraitItem (and ImplItem) so that it applies equally to all forms of trait and impl items. For now, we will not support generic constants, I guess, but honestly they probably just fall out from the work we are doing in any case, so they would be a small extension. I think the work will go better if we just plan for them now.

Perhaps a decent first PR would be to just do that change, keeping all other existing functionality the same. That is, we would more Generics into TraitItem (and ImplItem) and out of MethodSig. We would supply an empty Generics for non-methods. We would work through the existing code, plumbing the generics along as needed to make it work.

[sunjay]

@nikomatsakis Cool! Thank you so much! I started experimenting with this last night and I'm proud to say that I found the same places you pointed to in your comment about the AST. 😄 (Given that this was my first time in rustc, I count that as an accomplishment!)

I didn't think to lift generics into TraitItem. My approach was to put Generics into TraitItemKind::Type since that's where the type declaration is stored already. Your approach makes sense too so I'll work on implementing that. Since I am still completely new to this codebase, I'm interested to know what the pitfalls of my approach would be if it were used over the one you suggested. Could you give me some insight into your thought process? 😃

Here's the change I would have made:

pub enum TraitItemKind {
    // Generics aren't supported here yet
    Const(P<Ty>, Option<P<Expr>>),
    // `Generics` is already a field in `MethodSig`
    Method(MethodSig, Option<P<Block>>),
    // Added `Generics` here:
    Type(Generics, TyParamBounds, Option<P<Ty>>),
    Macro(Mac),
}

Edit: Answer by nikomatsakis on Gitter

regarding the pitfalls of putting them in type
I think that could work too
the reason that I was reluctant to do that
is that we really want to do the same things (in theory, at least) for methods and types
and -- as I said -- in principle I see no reason we couldn't do the same things for constants
I think if you just move the Generics to the type variant
that would probably work ok, but if you look about, right now we often have to do "one thing for types/consts, one thing for methods" precisely because they are different
so I suspect the code will just get more uniform
I'm not really sure how it will go to be honest =) -- it might be a pain
but a lot of times having things be more generic than they have to be isn't so bad, because you can insert span_bug! calls in the impossible cases for now (and later we come aoround and patch them up)

[nikomatsakis]

All right! Next step is to extend the parser. Here are a few tips. Let's start with trait items.

This routine parses trait items. We want to extend the case that handles associated types to also parse things like type Foo<....> = ...; (also maybe where-clauses). (The <...> is the "generics" that we just added to the AST.)

Currently it is using parse_ty_param, which basically parses something like T: Foo etc. We'll have to stop doing that, because the grammar for associated type declarations no longer matches that for type parameters. So we'll probably want to add something like parse_trait_item_assoc_ty. This can start as a kind of clone of parse_ty_param(), but then we'll want to modify it to invoke parse_generics() right about here. That routine will parse a generics declaration (<...>) if one is present, otherwise it just returns an empty generics. Then we want to add a call to parse where clauses right here -- you can model that on the call that occurs when parsing methods, note that the result is stored into the generics that we parsed earlier.

Once we've done that, we should be able to add some parsing tests. I would do that by making a directory like src/test/run-pass/rfc1598-generic-associated-types/ and adding files that you expect to successfully parse in there. Right now they won't work right, but that doesn't matter. Just add an empty main function. Then we can also add examples that should not parse into src/test/ui/rfc1598-generic-associated-types/ (see COMPILER_TESTS.md for directions on adding UI tests).

Something else -- we need to feature gate this work at this point, to avoid people using this stuff in stable builds. There are some instructions for adding a feature-gate here on forge (see the final section). We should add a visit_trait_item and visit_impl_item to the visitor in feature_gate.rs; if that item is not a method, but it has a non-empty generics, we can invoke gate_feature_post (example).

[nikomatsakis]

To setup name resolution, I think all we have to do is to get the proper "ribs" in place (the name resolution stuff organizes the sets of names that are in scope into ribs; each rib represents one binding level). e.g. for an impl:

impl<A,B> Foo<B> for Vec<A> {
   fn bar<T,U>(x: ...) { 
       for y in ... {
       }
   }
}

we would have the following ribs:

- <A,B> (from the impl)
   - <T,U> (from the `bar` method's generics)
      - `x` (from the parameter list)
          - `y` (from the let)

In general, modeling things on how methods work is not a bad idea. We might also do a bit of "future proofing" here, I suppose.

Here is the code that brings a method's type parameters into scope (this is for a method defined in a trait):

rust/src/librustc_resolve/lib.rs

Lines 1890 to 1892 in a35a3ab

	let type_parameters =
	HasTypeParameters(&trait_item.generics,
	MethodRibKind(!sig.decl.has_self()));

Whereas for a type defined in a trait, we are hardcoded to add an empty type parameter rib (NoTypeParameters):

rust/src/librustc_resolve/lib.rs

Lines 1897 to 1901 in a35a3ab

	TraitItemKind::Type(..) => {
	this.with_type_parameter_rib(NoTypeParameters, |this| {
	visit::walk_trait_item(this, trait_item)
	});
	}

Now that generics are in place on every trait/impl item, I think we probably want to remove the handling for type and extract the method handling so that it occurs at a higher level. For the items (e.g., const) where there are no generics, then the newly introduced rib ought to be empty and hence harmless (I hope).

Other points of interest:

• where impl item methods are setup
• where type in impls are setup

You get the idea.

@petrochenkov -- sound about right?

[petrochenkov]

@nikomatsakis

sound about right?

Everything looks correct.

[dhardy]

I don't like to write please hurry up already posts, but this feature has been stalled for nearly three years already, and I believe ranks as one of the most-desired new features.

Where are we with this? The most recent status summary here is by @LukasKalbertodt from June 2018. Is it waiting on "chalkification"?

Naive observation: nearly all of my desired uses for GATs require only one lifetime parameter. Would a cut-down lifetime-only version of GATs be simpler to deliver?

[matthewjasper]

#44265 (comment) is a (somewhat terse) update.
#67510 is the last major ICE/missing feature that needs implementing.

[ibraheemdev]

Would this RFC make Monad and Functor possible directly? Or is there more work that needs to be done on HKT's?

[memoryruins]

Would this RFC make Monad and Functor possible directly? Or is there more work that needs to be done on HKT's?

@ibraheemdev The RFC states

This does not add all of the features people want when they talk about higher- kinded types. For example, it does not enable traits like Monad. Some people may prefer to implement all of these features together at once. However, this feature is forward compatible with other kinds of higher-kinded polymorphism, and doesn't preclude implementing them in any way. In fact, it paves the way by solving some implementation details that will impact other kinds of higher- kindedness as well, such as partial application.

[varkor]

@ibraheemdev: my feeling is that the most idiomatic way to make monads and functors possible would be to introduce generic associated traits, but generic associated types is certainly a prerequisite.

[ibraheemdev]

Is there a path to Monad that does not require GAT's?

[rpjohnst]

@ibraheemdev Hypothetically yes, it would be possible to implement HKTs directly and then implement a Monad trait on top. However, there is no work happening in that direction, and probably never will be, because that approach doesn't really solve the problems Rust has: https://twitter.com/withoutboats/status/1027702531361857536

[MikailBag]

Maybe I'm wrong, but I think GAT allow something like

trait MonadFamily {
    type Monad<T>;
    fn pure<T>(inner: T) -> Self::Monad<T>;
    fn bind<T, U, F: FnOnce(T) -> U>(this: Self::Monad<T>, f: F) -> Self::Monad<U>;
}

[tyranron]

@ibraheemdev

Is there a path to Monad that does not require GAT's?

Yup, see Method for Emulating Higher-Kinded Types in Rust. It even works on stable now.

[cynecx]

I am really surprised because this compiles successfully on nightly (@jendrikw’s Monad example):

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=61caef82814783feadc33a3b865fe8b3

🧐 Did I miss something, or when did this get implemented?

EDIT: #72788 (That PR actually "implemented" working GATs)

[alercah]

Is there any route to updating the current Iterator definition to support streaming? Or is that not possible because of the requirement that the parameter get used, so you cannot use a type without a lifetime parameter in place of one that requires one?

[cynecx]

@alercah I don’t think that would be possible because introducing a lifetime arg for an associated type would be a breaking change.

[alercah]

Is it?

[lambda-fairy]

I assume you mean a design similar to the streaming-iterator crate?

With the current Iterator trait, you can hold two elements of the iterator at once:

let first = it.next();
let second = it.next();
println!("{:?} {:?}", first, second);

This isn't possible with a streaming iterator, because the memory used by the first element might be reused for the second. So I think it would be a breaking change.

[alercah]

Ah, right. Thanks.

[LukasKalbertodt]

@lambda-fairy I don't think that's necessarily a problem. If we were to change type Item to type Item<'a>, then impls not using that lifetime parameter (e.g. type Item<'a> = u64;) would still allow multiple items in scope at the same time. See this playground. It's only disallowed for impls which use the lifetime parameter of the GAT (e.g. type Item<'a> = &'a str;).

In order to change the current Iterator in a backwards-compatible fashion, existing impls need to continue to compile. This means that:

• Writing type Item = Foo; needs to be legal despite Item being defined with a lifetime parameter: type Item<'a>;. Currently this leads to "lifetime parameters or bounds on type Item do not match the trait declaration".
• Writing fn next(&mut self) -> Option<Self::Item> needs to be legal. Currently, Self::item<'_> is required. Omitting <'_> leads to "wrong number of lifetime arguments: expected 1, found 0".

With that, I guess it's rather unlikely the existing Iterator can be changed, unfortunately. I doubt we do want to allow both of these things in the language.

[bluss]

I don't think we can find a reasonable solution on the side that uses the trait. Currently, where I: Iterator implies that I has a collect method, and that you can call it, and this is not true for streaming iterators.

[SoniEx2]

We would suggest something along the lines of default lifetimes.

type Item<'a = 'static> and allow omission of default parameters. (std::ops::Add already does this for type parameters, for example. unsure if anything like it works for lifetime parameters.)

and then collect would require 'a: 'static. would something like this work?

[Kixunil]

If what @SoniEx2 suggested would work that'd be pretty cool. If not perhaps something like this could work:

pub trait StreamingIterator {
    type Item<'a>;
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

impl<T> StreamingIterator for T where T: Iterator {
    type Item<'a> = <T as Iterator>::Item;
    fn next(&mut self) -> Option<Self::Item<'_>> {
        Iterator::next(self)
    }

    // possibly move/copy the combinators here?
}

pub trait IntoStreamingIterator {
    type IntoStreamingIter: StreamingIterator;
    // type Item either can't be here or IDK how
    // not too important I think
    fn into_streaming_iter(self) -> Self::IntoStreamingIter;
}

impl<T> IntoStreamingIterator for T where T: IntoIterator {
    type IntoStreamingIter = <T as IntoIterator>::IntoIter;
    fn into_streaming_iter(self) -> Self::IntoStreamingIter;
}

Finally modify for to accept T: IntoStreamingIterator. This is backwards compatible because Iterator implies StreamingIterator. Then libraries that are able to accept StreamingIterator would need to change their bounds as well, but that is also backwards-compatible change.

[shepmaster]

I believe that StreamingIterator is

pub trait StreamingIterator {
    type Item<'a>;
    fn next(&'a mut self) -> Option<Self::Item<'a>>;
}

And thus different and incompatible.

However, this tracking issue isn’t the right place for this pontification. I suggest you move it to IRLO