🔬 Tracking issue for generic associated types (GAT)
withoutboats opened this issue · 146 comments
This is a tracking issue for generic associated types (rust-lang/rfcs#1598)
Repository
- Detailed tracking information is available at the GAT initiative repository
Unresolved questions:
Blocking bugs
See also the GATs-blocking tag (the list below should be a superset of that, but its good to double-check).
- #62521
-
#30472No longer blocking - #67509
- #67510
- #67512
- #67513
- #68641
- #68642
- #68643
- #68644
- #68645
- #68648
- #68649
- #68650
- #68652
- #68653
- #68656
- #74684
- #75415
- #76826
- #79768
-
#80626Not GATs specific, not blocking - #81487
- #81801
- #99205
Postponed work
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
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.
@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)
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).
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
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
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:
You get the idea.
@petrochenkov -- sound about right?
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:
rust/src/librustc/middle/resolve_lifetime.rs
Lines 370 to 388 in ddaebe9
You can see that it first creates a vector of lifetimes, invoking Region::early for each one:
rust/src/librustc/middle/resolve_lifetime.rs
Lines 376 to 378 in ddaebe9
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.)
rust/src/librustc/middle/resolve_lifetime.rs
Lines 379 to 384 in ddaebe9
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:
rust/src/librustc/middle/resolve_lifetime.rs
Lines 385 to 388 in ddaebe9
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.
rust/src/librustc/middle/resolve_lifetime.rs
Lines 482 to 501 in ddaebe9
Let me highlight a few things. First off, the method next_early_index returns the next unassigned early-bound index:
rust/src/librustc/middle/resolve_lifetime.rs
Line 488 in ddaebe9
That provides a starting point. Next, we use Region::early again to create new early-bound lifetime definitions that will be resolved against:
rust/src/librustc/middle/resolve_lifetime.rs
Lines 490 to 492 in ddaebe9
Finally, we bring those into scope by calling with again:
rust/src/librustc/middle/resolve_lifetime.rs
Lines 494 to 501 in ddaebe9
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:
rust/src/librustc/middle/resolve_lifetime.rs
Line 509 in ddaebe9
rust/src/librustc/middle/resolve_lifetime.rs
Line 520 in ddaebe9
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.)
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_tyandassociated_path_def_to_tyinlibrustc_typeck/astconv.rsto fix thetype parameters are not allowed on this typeerrors. 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.
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? #46472 doesn't seem to be spoken for, I can try to leave some comments there soon.
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.
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!
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>;
}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!
This is my most desired feature at the moment. I hope this becomes a priority and finds its way into nightly soon!
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.
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 -
empty_generics-- checks thattype Bar<,>gives an error, seems ok -
generic-associated-types-where.rs-- checks that we can parsewhereclauses 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_familyappears 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_familytest hasSelf::Pointer<T>, but not<Self as PointerFamily>::Pointer<T>
- e.g., the
- Wrong number of arguments to a GAT. e.g., given the
Iterabledefinition 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.
- Note that we might accept this in some contexts, since in some comparable contexts we permit eliding lifetimes.
<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 forSomeType::Bar<u32,u32>, which we ought to check.
- in that case,
Fixing unexpected E0110 errors
Error E0110 is reported by prohibit_type_params:
rust/src/librustc_typeck/astconv.rs
Line 912 in e65547d
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:
rust/src/librustc_typeck/astconv.rs
Lines 791 to 803 in e65547d
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:
rust/src/librustc_typeck/astconv.rs
Line 810 in e65547d
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?
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...
@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. =)
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>;
}What's the status of this? I know that chalk recently gained gat support. Is that intended to land in rust soon?
@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 #44265 (comment) for more details)
@quadrupleslap AIUI, that will be possible later, but at first, GATs will only support lifetime parameters..
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 :)
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).
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.
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 :)
Is there any update on this recently? Are we waiting for Chalk integration into the compiler? (Perhaps there's a separate issue for that.)
Perhaps there's a separate issue for that.
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 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)
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:
- Is this sort of scheme possible now but I'm just doing it wrong?
- If it's not possible now, will it ever be possible under this proposal?
- 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.
@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.
Maybe worth checking with the Chalk guys to see if integration is sufficiently advanced for work on this feature to resume?
Can we get the Issue Description updated with the current blockers?
Added more blocking issues raised by @DutchGhost
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)
}
}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)
}@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)
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?
@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.
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.
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:
rust/src/test/ui/generic-associated-types/iterable.rs
Lines 6 to 21 in db4826d
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.
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 =").
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.
@sighoya I've linked the repository in previous posts, here's a direct link to the impl of crate::view::ViewFn::map
What does the compiler said about this?:
where
for<'x> F: crate::view::ViewFn<T, Output<'x> = &'x O>,It doesn't parse (yet).
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?
Yes, Output<'x>=... doesn't parse in that position.
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...
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.
Added more blocking issues raised by @DutchGhost
You can add #74684 as well :)
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?
#44265 (comment) is a (somewhat terse) update.
#67510 is the last major ICE/missing feature that needs implementing.
Would this RFC make Monad and Functor possible directly? Or is there more work that needs to be done on HKT's?
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.
@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.
Is there a path to Monad that does not require GAT's?
@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
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>;
}Is there a path to
Monadthat does not require GAT's?
Yup, see Method for Emulating Higher-Kinded Types in Rust. It even works on stable now.
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?
@alercah I don’t think that would be possible because introducing a lifetime arg for an associated type would be a breaking change.
Is it?
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.
Ah, right. Thanks.
@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 despiteItembeing defined with a lifetime parameter:type Item<'a>;. Currently this leads to "lifetime parameters or bounds on typeItemdo 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.
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.
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?
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.
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
Now that #79554 has been merged, all blocking bugs listed in the OP have been fixed.
Big thanks to everyone who have worked on this issue!
OP updated to reflect remaining blocking issues.
We would suggest something along the lines of default lifetimes.
type Item<'a = 'static>and allow omission of default parameters. (std::ops::Addalready 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?
This would probably work better/be more backwards-compatible by defining a lifetime on the whole trait, tbh:
trait<'a> Iterator where Self: 'a {
type Item<'b = 'a>;
fn collect(...) where Self::Item: 'a {...}
}(or something along these lines...)
Edit: Also, this would probably have to be done through some sort of "Iterators v2", separate from existing iterators. Said "Iterators v2" would ideally be automatically implemented for all existing iterators, and would replace existing iterators for the purposes of for loops. Then it's just a matter of making an edition import v2 instead of v1 by default. (stdlib would be forced to keep providing the existing v1 iterators tho. that would never change.)
With the big blockers removed, can this move away raising the incomplete_feature warning? Is there a possibility for easy parts of this (if there are any) to be stabilized in a first wave? (Having this at least for lifetimes would be really helpful.)
@chrysn wg-traits has just been talking about this. Stabilizing just lifetimes first is one likely option. See triage on zulip or just wg-traits zulip stream in general (latest meeting especially).
So, just wanted to summarize the current state here and the potential plans towards stabilization. This is mostly just a summary of the conversations we've had in wg-traits, with some of my own thoughts sprinkled in. Expect a "real" blog post at some point.
To begin, a lot of blocking issues related to specifying GATs in trait paths (e.g. for<'a> T: Foo<Y<'a> = u32>) have now been "resolved" with #79554. However, this isn't completely resolved, since we haven't completely decided whether you need that for<'a> or if you should be able to (or must) elide that. As long as we decide you don't have to omit it, allowing the elision in the future is probably a backwards-compatible change.
Next, we've somewhat discussed whether we want to work towards stabilizing a subset of GATs with only lifetimes or go all-in on full GATs. There's some rationale for both sides, but I won't go into that here. We (I) still need to go through and triage the non-lifetime GATs issues since #79554 was merged in order to get a better sense of current issues. There may also be some other restrictions that we might want in the "lifetimes-only" version, but nothing off the top of my mind.
As far as removing the incomplete_features warning: That's probably something we'll want to do soon, but there are things (e.g. #81823) that concern me about that. If we do decide to split this into lifetimes-only vs. all, then the lifetimes-only feature will probably remove that warning whereas the more general feature will keep it. But, again, not sure about that yet.
Finally, just a reminder to please try to keep discussion on library-focused features around GATs away from this tracking issue. Discussion here should be really only be on things related directly to the feature and its implementation (e.g. syntax, design decisions, implementation status). This will help us keep track of things that are relevant to what's blocking stabilization. Feel free to file separate issues for specific feature requests related to GATs though.
Does GAT moving closer to being stable mean that "chalkification" of rustc is already complete or that GAT do not actually require Chalk being the engine of trait-related matters?
Does GAT moving closer to being stable mean that "chalkification" of rustc is already complete or that GAT do not actually require Chalk being the engine of trait-related matters?
The latter. While I'm not completely sure of all the impl work here (@matthewjasper would have a better idea), it's my understanding that a few of Chalk's design principals have been ported to the rustc trait solver to enable things like GATs. But there's plenty that the final integration of Chalk can bring us. But in this case, we're pretty confident that we can stabilize GATs without Chalk integration.
I've come across an ICE when using GATs that requires only a generic lifetime and doesn't superficially appear to be the same as the two outstanding bugs already mentioned. Here's a minimal example that still exhibits the issue: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=9a7bd5fa389964b2cbe88d88440cba5e
It's hard for me to tell whether this is a known issue without knowing more about the compiler internals.
This is very similar to an ICE that I have on a much larger source code, but I wasn't able to pinpoint the problem and get a minimal example.
Please, feel free to open a dedicated ICE issue.
I've come across an ICE when using GATs that requires only a generic lifetime and doesn't superficially appear to be the same as the two outstanding bugs already mentioned. Here's a minimal example that still exhibits the issue: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=9a7bd5fa389964b2cbe88d88440cba5e
It's hard for me to tell whether this is a known issue without knowing more about the compiler internals.
This is similar to #76826, which falls under #62529. Fixed by #85499.
Now that we have minimal const generics in stable, are generic associated types with const generics a supported part of this feature? This code seems to compile and work on nightly, but I'm not sure if that's by accident or not: (Rust Playground)
#![feature(generic_associated_types)]
trait Foo {
type F<const X: usize>;
}
struct Q<const X: usize> {}
impl<const X: usize> Q<X> {
const Y: usize = X;
}
impl Foo for () {
type F<const X: usize> = Q<X>;
}
fn main() {
let q = <() as Foo>::F::<3>::Y;
println!("{}", q); // prints "3"
}Will GATs with const generics be stabilized separately from GATs with just regular types?
Off hand, I don't see any reason to distinguish GATs with const generics from other GATs.
After GAT being stabilized, can I expect the following codes compile in the future?
Closure that return reference to itself:
fn main() {
let mut buffer = vec![1, 2, 3];
let getter = move |i: usize| &mut buffer[i];
}fn main() {
let g = || {
let mut x = 1;
yield &mut x;
};
}@EFanZh at some point in the future perhaps, but not immediately. Those would require traits. Also, the terminology I prefer is "lending" -- a lending closure or lending generator (because it lends so its data to its caller, and because "stream" is quite overloaded).
Something I've not seen considered before: What about variance for GATs with lifetime parameters? A while ago I was experimenting with a GAT-based solution for self-referential structs similar to owning_ref, and apart from compiler bugs one thing that was causing issues was that I had no way to specify that a GAT has to be covariant (or invariant) over its lifetime parameter.
EDIT: Looks like I'm not the only one to have stumbled across this limitation, just found a thread about it on IRLO.
There is no plan to support variance annotations at present.
What does that mean for unsafe code though? Does it mean unsafe code can't assume anything about GAT lifetime parameters' variance, or is it valid to assume that GAT lifetime parameters are invariant until a variance annotations (once they exist) is added (which I'm assuming would be a breaking change)?
You could make the trait unsafe, I suppose, but yes in general unsafe code would have to assume users might put any kind of type in that position.