Rust: 🔬 Tracking issue for generic associated types (GAT)

[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. :smile: (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? :smiley:

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

https://github.com/rust-lang/rust/blob/a35a3abcda67a729edbb7d649dbc663c6feabd4c/src/librustc_resolve/lib.rs#L1890-L1892

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

https://github.com/rust-lang/rust/blob/a35a3abcda67a729edbb7d649dbc663c6feabd4c/src/librustc_resolve/lib.rs#L1897-L1901

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.

[nikomatsakis]

Next step. Lifetime resolution.

For better or worse, this is currently done in an entirely separate bit of code from other name resolution. This is because it takes place after the HIR is constructed. Almost certainly this will change but it hasn't changed yet.

The basic ideas are the same as in normal name resolution, though, except we don't call things "ribs" but rather "scopes". =)

There are some mild complications because of this concept of "late-bound" lifetimes. It's not really relevant here though -- all the lifetimes for a generic associated type will be "early-bound", which is kind of the simple case. A "late bound" lifetime is a lifetime declared on a method or function whose value is not supplied until the method is invoked. I won't go into the details here because it's not that relevant -- the main thing is that we don't want to follow precisely the same model for methods as we do for other sorts of generic items, unlike in the other name resolution cases.

Here is an example bit of code. This is the code that visits an impl, struct or other non-function item. In these cases, as in GATs, we basically want to bring all the lifetime parameters from a Generics into scope and map them to "early-bound" lifetimes:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L370-L388

You can see that it first creates a vector of lifetimes, invoking Region::early for each one:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L376-L378

Next it creates a Scope. The next_early_index variable is just counting how many early-bound lifetimes are in scope. Since this code is specific to items, that will always be the number of early-bound lifetimes declared on this current item. (Later we'll look at a case where we are bringing additional lifetimes into scope, which is more what we want for GATs.)

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L379-L384

Finally, we invoke with(). This method will bring the scope into scope and invoke a closure. Any lifetimes that we visit inside this closure will see those names that we just defined as being in scope:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L385-L388

OK, now let's look at one more example. This case covers "impl traits". The details of what it's doing aren't that important (that is, you don't have to under the impl Trait desugaring per se). It suffices to say that it is bringing some new early-bound lifetimes into scope -- that is precisely what we are going to want to do for GATs.

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L482-L501

Let me highlight a few things. First off, the method next_early_index returns the next unassigned early-bound index:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L488

That provides a starting point. Next, we use Region::early again to create new early-bound lifetime definitions that will be resolved against:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L490-L492

Finally, we bring those into scope by calling with again:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L494-L501

OK, those are two examples. We're going to want to do something much like the second one. We'll want to modify the definitions of these two methods:

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L509

https://github.com/rust-lang/rust/blob/ddaebe938b8eb1f5e17570ae8091743972e02bdd/src/librustc/middle/resolve_lifetime.rs#L520

Both of which will need to, for associated types, process the associated generics. (They should prbably assert, in the other cases, that the generics are empty.)

[brandonson]

So I jumped in on this earlier today. I'd like to make sure I'm on the right track:

• All that needed to be done was introduce the lifetimes to the map and then walk the trait/impl item? Checking seems to be working, though it's hard to tell (see later)... may only be working in the simple (unbounded) case.
• I dropped type parameter prohibitions for qpath_to_ty and associated_path_def_to_ty in librustc_typeck/astconv.rs to fix the type parameters are not allowed on this type errors. I think that needs replacing with some checks. Also...
• I'm getting crashes from typeck now. (writeback, specifically)

typeck failures are triggered src/test/compile-fail/struct-path-associated-type.rs because it provides generics to values that don't have an associated type.

If I'm reading things right, I need to at least add a check that the associated generic counts match up (trying to figure out where to do that...), and also possibly do other checks to add types for nodes etc.

Going to work on that, but pointers on whether I'm even going in the right direction are appreciated.

[nikomatsakis]

Hi @brandonson! I'm loathe to discourage anyone from hacking on the Rust compiler, but I think that @sunjay was already actively hacking on the same stuff and has been kind of pursuing this change since the start, so it probably makes sense for them to finish up this change as well (I think they've already started). I'm not sure if there's an obvious way to parallelize this effort (certainly it's possible, but we'd have to game out the steps a bit before hand).

However, if you are interested in finding something to tackle, may I recommend tackling some of the bugs on this milestone? https://github.com/rust-lang/rust/issues/46472 doesn't seem to be spoken for, I can try to leave some comments there soon.

[brandonson]

Certainly I don't mean to step on anyone's toes, but I didn't see anything indicating further progress was actually occurring (though admittedly the comment regarding next steps is rather recent). Really, I started trying to solve this because I wanted GATs several times in the last couple of days, so while I wouldn't necessarily mind working through some NLL stuff in the future, this is way higher up in my list of things to resolve at the moment.

@sunjay, if you are still actively working/planning to work on this, please do let me know - no point in having me duplicating your work on this.

[sunjay]

Hi @brandonson, thank you for your eagerness and willingness to help out. :) I am indeed actively working on this. I've been going through each part of the implementation step by step while working closely with Niko to get it right.

I'll do everything I can to get this out as soon as possible. I really want this feature too!

[Centril]

How's the progress going ? =) Can't wait to experiment with this in nightly <3

I wonder how the cross section of GAT and const generics will work and if it was part of the proposals when put together?

An example of what I mean:

trait Foo {
    type Bar<const N>;
}

[rusterize]

Hi @sunjay I think this is quite an important feature, it was heavily mentioned in the 2018 Roadmap comments. How is it progressing? Thanks for your work!

[natepisarski]

This is my most desired feature at the moment. I hope this becomes a priority and finds its way into nightly soon!

[nikomatsakis]

So recently I met up with @sunjay, who is busy right now with school and other things, to try and lay out the next steps here. They and I had met up at some point and discussed the overall implementation strategy, culminating in a commit on their repo where we left a bunch of inline comments.

I think the strategy that makes the most sense going forward is two-fold:

• First, we need to write-up some more tests.
• There are some known shortcomings in our parser and some other "front-end" bits of the system, we need to enumerate and fix those. We'll probably find more in tests.
• At that point, we're ready to start hacking up the trait system proper:
  
  
  
  • some of the foundation has already been laid, so this is hopefully largely a "refactoring" task
  
  
  • but I need to write up in detail, there is no written description of the plan that I know and I don't have time for it this minute.
  
  

I'll start by trying to write up some instructions re: tests, since those are more immediately actionable, and schedule some time later this week to write up how the rest of the design will work and how to get the code from where it is now to where it needs to be.

[bugQ]

that's wonderful !! best of luck to @sunjay in this and all other endeavors.

[nikomatsakis]

First step will be ensuring that we have a full suite of tests. Existing tests can be found in:

src/test/ui/rfc1598-generic-associated-types

Just looking at those, we can already see some of the work to be done:

• [ ] construct_with_other_type.rs -- gives unexpected E0110 error
• [x] empty_generics -- checks that type Bar<,> gives an error, seems ok
• [x] generic-associated-types-where.rs -- checks that we can parse where clauses in the right places, seems ok
• [ ] generic_associated_type_undeclared_lifetimes.rs -- gives unexpected E0110 error
• [ ] iterable.rs -- gives unexpected E0110 error
• [ ] pointer_family.rs -- gives unexpected E0109 error
• [ ] streaming_iterator.rs -- gives unexpected E0110 error

Places that lack coverage

• [ ] we don't currently have much "expected usage" tests -- i.e., things that should succeed
  
  
  
  • pointer_family appears to be in that direction
  
  
  • I would expect some kind of trait Iterable { type Item; type Iter<'a>: Iterator<Item = &'a Self::Item>; } test
  
  
• [ ] lifetime shadowing tests -- we generally prohibit lifetime shadowing, so these ought to be illegal:
  
  
  
  • trait Foo<'a> { type Item<'a>; }
  
  
  • impl<'a> Foo<'a> for &'a u32 { type Item<'a> = i32; }
  
  
• [ ] "fully qualified" syntax doesn't appear to be tested
  
  
  
  • e.g., the pointer_family test has Self::Pointer<T>, but not <Self as PointerFamily>::Pointer<T>
  
  
• [ ] Wrong number of arguments to a GAT. e.g., given the Iterable definition above:
  
  
  
  • <T as Iterable>::Item -- no parameters at all? Bad.
  
  
  • Note that we might accept this in some contexts, since in some comparable contexts we permit eliding lifetimes.
    
    I could go either way here; I'd prefer for people to be writing an explicit '_ in cases like this.
  
  
  • <T as Iterable>::Item<'_> -- Correct!
  
  
  • <T as Iterable>::Item<T> -- Too many types!
  
  
  • etc, it'd be good to have tests that take both types and lifetimes of course
  
  
• [ ] Defaults on associated types? trait Foo { type Bar<T, U = T> where T: PartialEq<U>; }
  
  
  
  • in that case, SomeType::Bar<u32> would be shor for SomeType::Bar<u32,u32>, which we ought to check.
  
  

Fixing unexpected E0110 errors

Error E0110 is reported by prohibit_type_params:

https://github.com/rust-lang/rust/blob/e65547d4fad0425d1db4f33a4d8134bf2cad939e/src/librustc_typeck/astconv.rs#L912

The first step is to figure out where that is invoked from. My preferred way to do that is to get a local build and use -Ztreat-err-as-bug combined with RUST_BACKTRACE=1. But I can't show you those results because rustc is still building. :P So instead I did a quick rg prohibit_type_params, let me quickly go point out one suspicious case that I see.

One invocation is from associated_path_def_to_ty:

https://github.com/rust-lang/rust/blob/e65547d4fad0425d1db4f33a4d8134bf2cad939e/src/librustc_typeck/astconv.rs#L791-L803

As the comment indicates, this is invoked to resolve the Pointer<T> component in a path like Self::Pointer<T> (note that type parameters are considered part of a path segment, along with the name to which they are attached). Until GATs, type parameters were not legal there (e.g., T::Item), so we just have a blanket restriction:

https://github.com/rust-lang/rust/blob/e65547d4fad0425d1db4f33a4d8134bf2cad939e/src/librustc_typeck/astconv.rs#L810

Clearly this will not do. We should remove that line and replace it with some kind of check that, if parameters are provided, they match the expected number. To do this, we presumably want some error-checking code similar to what is found in create_substs_for_ast_path. We probably want to create some shared code here, particularly for accounting with defaults -- maybe we can actually re-use that function?

[0b01]

Is anyone still working on this? It seems to me that this has a long way to go. GAT is my most desired RFC. If not, I'd love to contribute some tests...

[nikomatsakis]

@rickyhan so @Centril and @gavento were talking on the WG-traits gitter about divvying up the test work, but I don't know if any progress has been made. Maybe they can chime in. I think a PR would be welcome. =)

[quadrupleslap]

Sorry if I'm being stupid, but is this kind of thing going to be legal with GATs?

trait Sequencer {
    type Wrap<A>;
    fn chain<A, B, F>(Self::Wrap<A>, F) -> Self::Wrap<B>
        where F: FnOnce(A) -> Self::Wrap<B>;
    fn wrap<A>(A) -> Self::Wrap<A>;
}

[mark-i-m]

What's the status of this? I know that chalk recently gained gat support. Is that intended to land in rust soon?

[baloo]

@mark-i-m I gave it a shot last week. From my understanding, the syntax parser is there (although missing tests). But the "implementation" is not written yet. (see https://github.com/rust-lang/rust/issues/44265#issuecomment-330915766 for more details)

[Boscop]

@quadrupleslap AIUI, that will be possible later, but at first, GATs will only support lifetime parameters..

[Centril]

@Boscop the RFC specifies that type parameters will also be supported.

[scalexm]

Does someone know the exact status of the implementation of the syntax in rustc? It seems mostly there, but higher ranked bounds generate ICEs:
http://play.rust-lang.org/?gist=a48959858ed5dd432c2396feae5c3cc1&version=nightly&mode=debug

I’d at least need the whole syntax to be implemented in order to advance on the chalkification work. If anybody is still working on the syntax, please let me know, or else I might go and fix it myself :)

[LukasKalbertodt]

To me it looks like communication is the major problem slowing down the implementation of GATs. There seem to be at least a few people interested in working on this, but no one really knows the exact implementation status and who is working on this already. What do you think about an Discord (or IRC?) channel just to talk about implementing GATs? I think that would certainly help.

Also, I could certainly contribute a few work days in the following weeks to work on this (but I don't really know anything about this part of the compiler yet).

[LukasKalbertodt]

So I asked for a dedicated channel on Discord. But instead of getting a channel, I learned a few things. I also searched for everything related to GATs. So I'll try to summarize all information regarding this feature; maybe it's useful to some people. But I don't know anything, so take this with a grain of salt! Also: please tell me if some information is incorrect so that I can fix it.

Summary of implementation efforts regarding GATs

• @sunjay landed two awesome PRs:

  • Generic Associated Types Parsing & Name Resolution (merged 2017-12-02)
  • Lifetime Resolution for Generic Associated Types (merged 2017-12-15)

• Then, for some time, not a lot happened. Niko then summarized what still needs to happen in this comment (2018-03-12). Basically (a) write tests, (b) fix bugs in/improve parser/front-end and (c) the implementation in the trait system. Point (a) was further explained in this comment (2018-03-13).

• @gavento landed Extend tests for RFC1598 (GAT) (merged 2018-05-11)

  • I'm not sure if Niko's comment about the tests already reflects changes made in this PR. The latest edit is from 2018-03-27, the same day @gavento opened their PR. (@gavento can you tell us about the status?)

Since then there weren't any UI tests added. And I can't find any other PRs directly related to GATs.

However, the point (c) from above (the trait system) is being worked on "in secret". As far as I understand it, the plan is to migrate to the new chalk-based trait solver soon and not make GATs work on the old system. Integration of the new trait solver is tracking by the "Chalkification" tracking issue. There have been quite a few PRs related to chalk and chalkification. Notably, there is a chalk PR called "Finish implementing GATs" (merged 2018-05-24). So it seems like the core system for GATs is already in place.

That said, the "GATs" in chalk are a prototype implementation and using it in rustc is not just a use chalk;. As @scalexm told me: "There seems to be quite a lot [to do]".

---

For more information and to help out, it's probably useful to take a look into the #wg-traits Discord channel and the traits WG tracking issue.

[LukasKalbertodt]

So @nikomatsakis just created the #wg-traits-gat channel on the rust-lang discord server (join here). It would be great if we could get everyone who wants to help in there. Plus a few people who know about the status of this feature (in particular, what still needs to be done and where we could help). That should make communication easier and faster, especially for people like me who are not yet deeply involved/part of the traits WG :)

[alexreg]

Is there any update on this recently? Are we waiting for Chalk integration into the compiler? (Perhaps there's a separate issue for that.)

[shepmaster]

Perhaps there's a separate issue for that.

48049

[wdanilo]

Just as a note (possibly known), this code panics the compiler:

use typenum::{U1,U2,U3,Unsigned};

trait Array {
    type Of<Elem> ;
}

impl Array for U1 { type Of<T> = [T;1]; }
impl Array for U2 { type Of<T> = [T;2]; }
impl Array for U3 { type Of<T> = [T;3]; }

[varkor]

@wdanilo: I believe this is https://github.com/rust-lang/rust/issues/64755.

[wdanilo]

@varkor awesome, thanks!

Yet another note (again, possibly known). Having GATs in place, we would be able to nicely abstract over & and &mut types, so we could stop constantly copy-pasting code between functions my_func and my_func_mut :) Here is a possible implementation of such abstraction (aka pseudo HKT):

#![feature(arbitrary_self_types)]
#![feature(generic_associated_types)]

use std::marker::PhantomData;

struct Pure <'t> (PhantomData<&'t()>);
struct Mut  <'t> (PhantomData<&'t()>);

type Ref<M, T> = <M as Acc>::Pat<T>;

trait Acc { type Pat<T: ?Sized>; }
impl<'t> Acc for Pure <'t> { type Pat<T> = PureRef <'t, T>; }
impl<'t> Acc for Mut  <'t> { type Pat<T> = MutRef  <'t, T>; }

struct PureRef <'t, T: ?Sized> (&'t     T);
struct MutRef  <'t, T: ?Sized> (&'t mut T);


/// USAGE ///

struct Buf<T> {
    data: Vec<T>
}

impl<T> Buf<T> {
    fn as_mut<M: Acc>(s: Ref<M, Self>) -> Ref<M, [f32]>
    {
        unimplemented!()
    }
}

It almost compiles. We can also implement it without GATs but types explode:

#![feature(arbitrary_self_types)]

use std::marker::PhantomData;
use std::ops::Deref;

struct Pure <'t> (PhantomData<&'t()>);
struct Mut  <'t> (PhantomData<&'t()>);

type Ref<M, T> = <M as Acc<T>>::Pat;

trait Acc<T: ?Sized> { type Pat; }
impl<'t, T: 't + ?Sized> Acc<T> for Pure <'t> { type Pat = PureRef <'t, T>; }
impl<'t, T: 't + ?Sized> Acc<T> for Mut  <'t> { type Pat = MutRef  <'t, T>; }

struct PureRef <'t, T: ?Sized> (&'t     T);
struct MutRef  <'t, T: ?Sized> (&'t mut T);


/// USAGE ///

struct Buf<T> {
    data: Vec<T>
}

impl<T> Buf<T> {
    fn as_mut<M>(self: Ref<M, Self>) -> Ref<M, [f32]>
    where M: Acc<Self> + Acc<[f32]>,
          Ref<M, Self>: Deref<Target = Self>
    {
        unimplemented!()
    }
}

(this actualy compiles)

[clintonmead]

Perhaps this is more of a support question but I think it might be useful to those coming to this page to understand this proposal because it wasn't entirely clear to me from the RFC or the comments here:

With the 1.41 nightly, I tried the following:

pub trait MyTrait {
    type MyType<U>;

    fn f<U>(self, x : <Self as MyTrait>::MyType<U>);
}

And this fails to compile, the error being "type argument not allowed" MyType.

I then removed the <U>, which looked suspicious but I thought I'd give it a go:

pub trait MyTrait {
    type MyType<U>;

    fn f<U>(self, x : <Self as MyTrait>::MyType);
}

Which surprisingly did compile. But then when I wrote an impl:

impl MyTrait for u64 {
    type MyType<U> = U;

    fn f<U>(self, x : <Self as MyTrait>::MyType) -> <Self as MyTrait>::MyType {
        x;
    }
}

This panicked the compiler.

My questions are:

1. Is this sort of scheme possible now but I'm just doing it wrong?
2. If it's not possible now, will it ever be possible under this proposal?
3. If so, is there any idea of the sort of timeline that I'd be able to do this in nightly?

Thanks in advance for your time in answering this.

[Manishearth]

@clintonmead I believe that should eventually be possible, but the feature implementation is not yet finished (indeed, the compiler warns you that it may crash when you try to use it!). I don't know what the timeline is.

[alexreg]

Maybe worth checking with the Chalk guys to see if integration is sufficiently advanced for work on this feature to resume?

[matthewjasper]

This is now blocked on

• #30472
• #67509
• #67510
• #67512
• #67513

[khionu]

Can we get the Issue Description updated with the current blockers?

[matthewjasper]

Added more blocking issues raised by @DutchGhost

[jendrikw]

This would be a major step in emulation of higher-kinded types.

I'm imagining something like this:

// the plug/unplug idea is from https://gist.github.com/edmundsmith/855fcf0cb35dd467c29a9350481f0ecf

trait Monad /* : Applicative (for pure/return, doesn't matter for this example) */ {
    // Self is like the "f a" in haskell

    /// extract the "a" from "f a"
    type Unplug;

    /// exchange the "a" in "f a" in the type of Self with B
    type Plug<B>: Monad;

    fn bind<B, F>(this: Self, f: F) -> Self::Plug<B>
    where
        F: Fn(Self::Unplug) -> Self::Plug<B>;
}

impl<A> Monad for Option<A> {
    type Unplug = A;
    type Plug<B> = Option<B>;
    fn bind<B, F>(this: Self, f: F) -> Option<B>
    where
        F: Fn(A) -> Option<B> {
        this.and_then(f)
    }
}

[travis-leith]

Question on the proposed implementation:

I have a trait that looks like this

trait TradeableResource{
}

and an implementer that looks like this

struct Food(f64);
impl TradeableResource for Food{}

I'd like to be able to limit all implementers of my trait to be a "newtype" (single element tuple struct wrapping an f64).

Would that be possible with the proposed implementation being considered here?

The following looks a bit weird admittedly but hopefully demonstrates what I want to be able to do.

trait TradeableResource{
    type Wrapper<T>:T(f64)
}

[42triangles]

@ChechyLevas as far as I'm aware this is not within the scope of GADTs.

But what you want to do doesn't need GADTs to begin with, from what I can gather, if you're willing to give up on the guarantee that it's a newtype and instead have to functions which wrap and retrieve the inner value, respectively. It's not as convenient, but should probably work well enough.

So you could do the following:

trait Traceable resource: From<f64> + Into<f64> { }

(this would require you to also implement From in both directions, which I'd do via a macro)

[Blub]

I'd like to get a bit of a feeling for the current state of this. I've been playing with async traits and lifetimes a bit.
One thing I wanted to do was to create a trait ReadAt<'r> with an associated ReadAt: Future type. Which works for a lot of cases, except when I want to use trait objects.

Mostly because doing the following would force me to attach a not-generic-enough lifetime to R:

impl<'a, 'r, R> ReadAt<'r> for &'a dyn for<'z> ReadAt<'z, ReadAt = R> + 'a {
    type ReadAt = R; // cannot have an `impl<R<'lifetime>>`
    ...
}

So I thought, maybe this could be solved with GATs, but I ran into similar issues where I'd need some syntax magic again, because trait objects require associated types to be written out:

Like:

trait ReadAt {
    type ReadAt<'r>: Future<Output = io::Result<usize>>;

    fn read_at<'a>(&'a self, buf: &'a mut [u8], at: u64) -> Self::ReadAt<'a>;
}

impl<'d> ReadAt for &'d (dyn ReadAt<HERE> + 'd) {
}

I'd need a way to include the lifetime in HERE. This, for instance, is accepted, but IMO would not be enough, as R is too concrete:

impl<'d, R> ReadAt for &'d (dyn ReadAt<ReadAt = R> + 'd) {
    type ReadAt<'r> = R;

    fn read_at<'a>(&'a self, buf: &'a mut [u8], at: u64) -> Self::ReadAt<'a> {
        (**self).read_at(buf, at)
    }
}

But I can't really test if that would work anyway, since I'm not sure how to turn this into a trait object, as I don't know how I'd get the lifetimes into the following snippet:

struct Test<T: ReadAt>(T);

impl<T: ReadAt> Test<T> {
    fn into_trait_object<'a>(&'a self) -> Test<&'a dyn ReadAt<ReadAt = T::ReadAt>> {
        todo!();
    }
}

Since T::ReadAt takes a lifetime which I can't provide, so this would miss a syntax extension for dyn ReadAt<ReadAt<'r> = T::ReadAt<'r>>. (Or for matching lifetime parameters IMO the above snippet could just work ;-) )

Since I'm only using lifetime parameters, not type parameters, I think this should technically be possible, unless lifetime parameters can affect vtables and type sizes somehow?

[madushan1000]

@jendrikw your code compiles and runs with the latest nightly(1.46). I did some tests with custom types etc.. but I lack the fp knowledge to check more.

[zserik]

Today, I tried using GATs for something where I thought that maybe a lifetime wouldn't be generic enough (working code follows; complete code file):

/// Helper trait for "stripping indention" from an object reference
pub trait AsUnindented<'ast> {
    type Output;

    /// Returns a reference to the unindented part of `Self`
    fn as_unindented(&'ast self) -> Self::Output;
}

impl<'ast, T: 'ast> AsUnindented<'ast> for Indented<T> {
    type Output = &'ast T;

    #[inline]
    fn as_unindented(&'ast self) -> &'ast T {
        &self.data
    }
}

impl<'ast, T: 'ast> AsUnindented<'ast> for crate::Block<T>
where
    T: AsUnindented<'ast> + 'ast,
{
    type Output = crate::View<'ast, T, fn(&'ast T) -> T::Output>;

    #[inline]
    fn as_unindented(&'ast self) -> Self::Output {
        crate::View::new(self, T::as_unindented)
    }
}

Then, I tried using GATs in the following code:

pub trait AsUnindented {
    type Output<'ast>;

    /// Returns a reference to the unindented part of `Self`
    fn as_unindented<'ast>(&'ast self) -> Self::Output<'ast>;
}

impl<T> AsUnindented for Indented<T> {
    type Output<'ast> = &'ast T;

    #[inline]
    fn as_unindented<'ast>(&'ast self) -> &'ast T {
        &self.data
    }
}

impl<T> AsUnindented for crate::Block<T>
where
    T: AsUnindented,
{
    type Output<'ast> = crate::View<'ast, T, fn(&'ast T) -> T::Output<'ast>>;

    #[inline]
    fn as_unindented<'ast>(&'ast self) -> Self::Output<'ast> {
        crate::View::new(self, T::as_unindented)
    }
}

That doesn't work. It fails with E0309 (the parameter type 'T' may not live long enough) for both trait implementations. I'm unsure how to fix this or if I have some misconception. The compiler wants that I attach a bound on T at impl level, but at that level, there is no lifetime 'ast, and I don't want to constrain T: 'static (and something like for<'ast> T: 'ast doesn't work).

edit: I tried applying GATs to another part of my code base, it throws only one error (for now), but that one can't be simply fixed as it depends on a fix for my forementioned problem.

[matthewjasper]

The outlives bound can be added to the associated type (using Self: 'ast on the trait's version). This test shows what this should look like:
https://github.com/rust-lang/rust/blob/db4826dd6ca48663a0b4c5ab0681258999017c7d/src/test/ui/generic-associated-types/iterable.rs#L6-L21

[zserik]

well, that does only work partially...

error messages

error[E0309]: the parameter type `T` may not live long enough
  --> src/indention.rs:33:5
   |
33 |     type Output<'ast> where T: 'ast = &'ast T;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `T: 'ast`...
   = note: ...so that the type `T` will meet its required lifetime bounds

error[E0309]: the parameter type `T` may not live long enough
  --> src/indention.rs:45:5
   |
45 |     type Output<'ast> where T: 'ast = crate::View<'ast, T, fn(&'ast T) -> T::Output<'ast>>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `T: 'ast`...
   = note: ...so that the type `T` will meet its required lifetime bounds

error[E0309]: the parameter type `T` may not live long enough
  --> src/indention.rs:59:5
   |
59 | /     type Output<'ast2>
60 | |         where
61 | |             T: 'ast2,
62 | |             O: 'ast2
63 | |         = crate::View<'ast2, T, crate::view::MapViewFn<F, fn(F::Output<'ast2>) -> O::Output<'ast2>>>;
   | |_____________________________________________________________________________________________________^
   |
   = help: consider adding an explicit lifetime bound `T: 'ast2`...
   = note: ...so that the type `T` will meet its required lifetime bounds

error[E0309]: the parameter type `O` may not live long enough
  --> src/indention.rs:59:5
   |
59 | /     type Output<'ast2>
60 | |         where
61 | |             T: 'ast2,
62 | |             O: 'ast2
63 | |         = crate::View<'ast2, T, crate::view::MapViewFn<F, fn(F::Output<'ast2>) -> O::Output<'ast2>>>;
   | |_____________________________________________________________________________________________________^
   |
   = help: consider adding an explicit lifetime bound `O: 'ast2`...
   = note: ...so that the type `O` will meet its required lifetime bounds

It seems as the code passes one stage (previously, it errored with similiar errors, but between them, another category of error appeared which consisted only of E0107s) hm.

edit: I missed the first statement (where Self: 'ast). That part is fixed now. I try to continue.

[zserik]

additional context

ok, the following snippet:

impl<'ast, T, F, O> AsUnindented for crate::View<'ast, T, F>
where
    Self: Clone,
    F: crate::view::ViewFn<T, Output = &'ast O>,
    O: AsUnindented + 'ast,
{
    type Output<'ast2>
        where
            T: 'ast2,
        = crate::View<'ast, T, crate::view::MapViewFn<F, fn(&'ast O) -> O::Output<'ast>>>;

    #[inline]
    fn as_unindented<'ast2>(&'ast2 self) -> Self::Output<'ast2> {
        self.clone().map::<for<'x> fn(&'x O) -> O::Output<'x>, _>(O::as_unindented)
    }
}

errors with:

error[E0631]: type mismatch in function arguments
  --> src/indention.rs:66:67
   |
66 |         self.clone().map::<for<'x> fn(&'x O) -> O::Output<'x>, _>(O::as_unindented)
   |                                                                   ^^^^^^^^^^^^^^^^
   |                                                                   |
   |                                                                   expected signature of `for<'x> fn(<F as view::ViewFn<T>>::Output<'x>) -> _`
   |                                                                   found signature of `for<'x> fn(&'x O) -> _`

and I know that <F as view::ViewFn<T>>::Output<'x> ==> &'ast O and &'x O aren't equal, but I don't know how to fix it (the compiler doesn't accept the bound F: for<'x> crate::view::ViewFn<T, Output = &'x O>).
The other try errors with:

error[E0582]: binding for associated type `Output` references lifetime `'x`, which does not appear in the trait input types
  --> src/indention.rs:56:39
   |
56 |     F: for<'x> crate::view::ViewFn<T, Output = &'x O>,
   |                                       ^^^^^^^^^^^^^^

I don't know how to express a forall<'x> bound in an trait output type assignment, e.g.

where
    F: crate::view::ViewFn<T, for<'x> Output<'x> = &'x O>,

doesn't even parse ("expected one of +, ,, ::, or >, found =").

[matthewjasper]

67510 tracks being able to write that bound. That example may also need lazy normalization (#60471).

[sighoya]

Is the trait output type of self.clone().map really the type of O::as_unindented, i.e the argument type of map
Don't know what crate::View is, but the map function may expect a different argument, therefore the type mismatch.

[zserik]

@sighoya I've linked the repository in previous posts, here's a direct link to the impl of crate::view::ViewFn::map

[sighoya]

What does the compiler said about this?:

where
    for<'x> F: crate::view::ViewFn<T, Output<'x> = &'x O>,

[matthewjasper]

It doesn't parse (yet).

[sighoya]

@matthewjasper,

From Rust Nomicon, the following parses:

where for<'a> F: Fn(&'a (u8, u16)) -> &'a u8,

Is it because of the use of Output<'x> = &'x 0> that it doesn't parse?

[matthewjasper]

Yes, Output<'x>=... doesn't parse in that position.

[timothee-haudebourg]

I have a create, grdf that does not compile anymore with rustc 1.46.0-nightly. Has anything changed around GAT recently?

My case is a bit weird since I had to use a trick to make it work in the first place. I essential have a Graph trait with associated iterator types. To make it work, I've placed all the iterators in another trait, Iter:

pub trait Iter<'a, T: 'a> {
    type Triples: Iterator<Item = Triple<&'a T>>;
    type Subjects: Iterator<Item = (&'a T, Self::Predicates)>;
    type Predicates: Iterator<Item = (&'a T, Self::Objects)>;
    type Objects: Iterator<Item = &'a T>;
}

pub trait Graph<T = crate::Term> {
    /// Iterators.
    type Iter<'a>: Iter<'a, T>;

    ...
}

I have one implementation of Graph that worked just fine until now:

impl<'a, T: 'a + Hash + Eq> crate::Iter<'a, T> for Iterators {
    type Objects = Objects<'a, T>;
    type Predicates = Predicates<'a, T>;
    type Subjects = Subjects<'a, T>;
    type Triples = Iter<'a, T>;
}

impl<T: Hash + Eq> crate::Graph<T> for HashGraph<T> {
    type Iter<'a> = Iterators;

    ...
}

Now that i've updated rustc it fails with the following:

error[E0309]: the parameter type `T` may not live long enough
  --> src/hash_dataset.rs:50:2
   |
50 |     type Iter<'a> = Iterators;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `T: 'a`...
   = note: ...so that the type `T` will meet its required lifetime bounds

This doesn't make much sense to me since T is already bound by 'a in Iter...

[timothee-haudebourg]

Okey I made it work again by adding some where bounds.
In the trait:

type Iter<'a>: Iter<'a, T> where T: 'a;

and in the implementation:

type Iter<'a> where T: 'a = Iterators;

But I'm not sure to understand the exact semantics of the where bounds, particularly in the implementation (first time I've seen that). And also why did it previously work.

EDIT: I've even been able to remove my nasty hack and put the associated iterators in the trait itself.

[DutchGhost]

Added more blocking issues raised by @DutchGhost

You can add https://github.com/rust-lang/rust/issues/74684 as well :)

[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]

https://github.com/rust-lang/rust/issues/44265#issuecomment-568247656 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.