Skip to content
New issue

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

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

Already on GitHub? Sign in to your account

Wrong (?) [E0631] signature mismatch for function with Fn trait arguments with GAT arguments #88382

Open
tim3z opened this issue Aug 27, 2021 · 8 comments
Labels
A-GATs Area: Generic associated types (GATs) GATs-triaged Issues using the `generic_associated_types` feature that have been triaged S-bug-has-test Status: This bug is tracked inside the repo by a `known-bug` test.

Comments

@tim3z
Copy link

tim3z commented Aug 27, 2021

Compiling this code

#![feature(generic_associated_types)]

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

struct SomeImplementation();

impl Iterable for SomeImplementation {
    type Iterator<'a> = std::iter::Empty<usize>;
    fn iter(&self) -> Self::Iterator<'_> {
        std::iter::empty()
    }
}

fn do_something<I: Iterable>(i: I, mut f: impl for<'a> Fn(&mut I::Iterator<'a>)) {
    f(&mut i.iter());
}

fn main() {
    do_something(SomeImplementation(), |_| ());
    do_something(SomeImplementation(), test);
}

fn test<'a, I: Iterable>(_: &mut I::Iterator<'a>) {}

with the current nightly (rustc 1.56.0-nightly (0afc20860 2021-08-25)) yields an E0631 argument mismatch for both calls to do_something.

error[E0631]: type mismatch in closure arguments
  --> src/main.rs:22:5
   |
22 |     do_something(SomeImplementation(), |_| ());
   |     ^^^^^^^^^^^^                       ------ found signature of `for<'r> fn(&'r mut std::iter::Empty<usize>) -> _`
   |     |
   |     expected signature of `for<'r, 'a> fn(&'r mut <SomeImplementation as Iterable>::Iterator<'a>) -> _`
   |
note: required by a bound in `do_something`
  --> src/main.rs:17:48
   |
17 | fn do_something<I: Iterable>(i: I, mut f: impl for<'a> Fn(&mut I::Iterator<'a>)) {
   |                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `do_something`

error[E0631]: type mismatch in function arguments
  --> src/main.rs:23:40
   |
23 |     do_something(SomeImplementation(), test);
   |                                        ^^^^ expected signature of `for<'a> fn(&mut <SomeImplementation as Iterable>::Iterator<'a>) -> _`
...
26 | fn test<'a, I: Iterable>(_: &mut I::Iterator<'a>) {}
   | ------------------------------------------------- found signature of `for<'r> fn(&'r mut std::iter::Empty<usize>) -> _`
   |
note: required by a bound in `do_something`
  --> src/main.rs:17:56
   |
17 | fn do_something<I: Iterable>(i: I, mut f: impl for<'a> Fn(&mut I::Iterator<'a>)) {
   |                                                        ^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `do_something`

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

I expected both calls to compile and from looking at the errors I also see no reasons why the signatures should be incompatible. In the case that my expectation is wrong I would expect the compiler to give me some hint, why this is not possible.

Sorry for the double post, I accidentally used the wrong template in #88355

@skyzh
Copy link
Contributor

skyzh commented Sep 22, 2021

I have a similar case in our project, and we could workaround this by construct the struct directly instead of using a new function.

#![feature(generic_associated_types)]
use std::marker::PhantomData;

trait ScalarRef<'a> {}
trait Scalar {
    type Ref<'a>: ScalarRef<'a>;
}

struct Func<I1: Scalar, I2: Scalar, O: Scalar, F: Fn(I1::Ref<'_>, I2::Ref<'_>) -> O> {
    func: F,
    _phantom: PhantomData<(I1, I2, O)>,
}

impl<I1: Scalar, I2: Scalar, O: Scalar, F: Fn(I1::Ref<'_>, I2::Ref<'_>) -> O> Func<I1, I2, O, F> {
    fn new(func: F) -> Self {
        Self {
            func,
            _phantom: PhantomData,
        }
    }
}

impl ScalarRef<'_> for &i32 {}
impl Scalar for i32 {
    type Ref<'a> = &'a i32;
}

fn add(x: &i32, y: &i32) -> i32 {
    *x + *y
}

fn main() {
    let expr1 = Func::<i32, i32, i32, _> {
        func: add,
        _phantom: PhantomData,
    }; // works

    let expr2 = Func::<i32, i32, i32, _>::new(add); // compile error
}

... where the error is

error[E0631]: type mismatch in function arguments
  --> src/main.rs:38:47
   |
28 | fn add(x: &i32, y: &i32) -> i32 {
   | ------------------------------- found signature of `for<'r, 's> fn(&'r i32, &'s i32) -> _`
...
38 |     let expr2 = Func::<i32, i32, i32, _>::new(add);
   |                 ----------------------------- ^^^ expected signature of `for<'r, 's> fn(<i32 as Scalar>::Ref<'r>, <i32 as Scalar>::Ref<'s>) -> _`
   |                 |
   |                 required by a bound introduced by this call
   |

In rustc 1.57.0-nightly (ac2d9fc 2021-09-21)

@skyzh
Copy link
Contributor

skyzh commented Sep 22, 2021

@tim3z and I've made a workaround for your code, hope this helps!

#![feature(generic_associated_types)]

use std::marker::PhantomData;

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

struct SomeImplementation();

impl Iterable for SomeImplementation {
    type Iterator<'a> = std::iter::Empty<usize>;
    fn iter(&self) -> Self::Iterator<'_> {
        std::iter::empty()
    }
}

struct DoSomething<I: Iterable, F: Fn(&mut I::Iterator<'_>)> {
    f: F,
    _phantom: PhantomData<I>,
}

impl<I: Iterable, F: Fn(&mut I::Iterator<'_>)> DoSomething<I, F> {
    fn really_do_something(&self, i: I) {
        (self.f)(&mut i.iter());
    }
}

fn main() {
    let do_something = DoSomething::<SomeImplementation, _> {
        f: |_| (),
        _phantom: PhantomData,
    };
    do_something.really_do_something(SomeImplementation());
}

fn test<'a, I: Iterable>(_: &mut I::Iterator<'a>) {}

@tim3z
Copy link
Author

tim3z commented Sep 22, 2021

Thank you very much, I'll try to work that into my code.

@tim3z
Copy link
Author

tim3z commented Sep 22, 2021

So, that definitely helps as long as its possible to define all the necessary functionality as methods on the struct.
Once you try to pass that struct to a function you're back to the original error, i.e.:

#![feature(generic_associated_types)]

use std::marker::PhantomData;

pub trait Iterable {
    type Iterator<'a>;
    fn iter(&self) -> Self::Iterator<'_>;
}

pub struct SomeImplementation();

impl Iterable for SomeImplementation {
    type Iterator<'a> = std::iter::Empty<usize>;
    fn iter(&self) -> Self::Iterator<'_> {
        std::iter::empty()
    }
}

pub struct DoSomething<I: Iterable, F: Fn(&mut I::Iterator<'_>)> {
    pub f: F,
    pub _phantom: PhantomData<I>,
}

impl<I: Iterable, F: Fn(&mut I::Iterator<'_>)> DoSomething<I, F> {
    pub fn really_do_something(&self, i: &mut I) {
        (self.f)(&mut i.iter());
    }
}

fn main() {
    let foo = 42;
    let do_something = DoSomething::<SomeImplementation, _> {
        f: |i| {
            i.next();
        },
        _phantom: PhantomData,
    };
    do_something.really_do_something(&mut SomeImplementation());
    do_some_more(SomeImplementation(), do_something);
}

fn do_some_more<I: Iterable, F: Fn(&mut I::Iterator<'_>)>(
    iterable: I,
    callback: DoSomething<I, F>,
) {
    callback.really_do_something(&mut iterable);
}

yields

error[E0631]: type mismatch in closure arguments
  --> src/main.rs:39:40
   |
33 |         f: |i| {
   |            --- found signature of `for<'r> fn(&'r mut std::iter::Empty<usize>) -> _`
...
39 |     do_some_more(SomeImplementation(), do_something);
   |     ------------                       ^^^^^^^^^^^^ expected signature of `for<'r, 's> fn(&'r mut <SomeImplementation as Iterable>::Iterator<'s>) -> _`
   |     |
   |     required by a bound introduced by this call
   |
note: required by a bound in `do_some_more`
  --> src/main.rs:42:33
   |
42 | fn do_some_more<I: Iterable, F: Fn(&mut I::Iterator<'_>)>(
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `do_some_more`

For more information about this error, try `rustc --explain E0631`.

@tim3z
Copy link
Author

tim3z commented Sep 23, 2021

So, while trying to integrate the workaround into my code, i ran into a compiler crash. I'll try to make a minimal example which reproduces the crash but for the moment, I pushed the exact code state which reproduces the crash into a branch: https://github.com/kit-algo/rust_road_router/tree/gat_closure_bug (even without the crash, the code in that state does not compile, but this is expected. I just captured the crashing state without any edits to fix things.)

error: internal compiler error: compiler/rustc_borrowck/src/universal_regions.rs:782:36: cannot convert `RePlaceholder(Placeholder { universe: U2, name: BrAnon(1) })` to a region vid

thread 'rustc' panicked at 'Box<dyn Any>', compiler/rustc_errors/src/lib.rs:1146:9
stack backtrace:
   0: std::panicking::begin_panic
   1: std::panic::panic_any
   2: rustc_errors::HandlerInner::bug
   3: rustc_errors::Handler::bug
   4: rustc_middle::ty::context::tls::with_opt
   5: rustc_middle::util::bug::opt_span_bug_fmt
   6: rustc_middle::util::bug::bug_fmt
   7: rustc_borrowck::type_check::free_region_relations::UniversalRegionRelationsBuilder::add_implied_bounds
   8: core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once
   9: <core::iter::adapters::flatten::FlatMap<I,U,F> as core::iter::traits::iterator::Iterator>::next
  10: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  11: rustc_borrowck::type_check::free_region_relations::create
  12: rustc_borrowck::type_check::type_check
  13: rustc_borrowck::nll::compute_regions
  14: rustc_borrowck::do_mir_borrowck
  15: rustc_infer::infer::InferCtxtBuilder::enter
  16: rustc_borrowck::mir_borrowck
  17: core::ops::function::FnOnce::call_once
  18: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  19: rustc_data_structures::stack::ensure_sufficient_stack
  20: rustc_query_system::query::plumbing::try_execute_query
  21: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::mir_borrowck
  22: rustc_middle::ty::<impl rustc_middle::ty::context::TyCtxt>::par_body_owners
  23: rustc_interface::passes::analysis
  24: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  25: rustc_data_structures::stack::ensure_sufficient_stack
  26: rustc_query_system::query::plumbing::try_execute_query
  27: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::analysis
  28: rustc_interface::passes::QueryContext::enter
  29: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
  30: rustc_span::with_source_map
  31: scoped_tls::ScopedKey<T>::set
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.57.0-nightly (308dffd25 2021-09-22) running on x86_64-unknown-linux-gnu

note: compiler flags: -C opt-level=3 -C embed-bitcode=no -C debuginfo=2 -C debug-assertions=on -C incremental --crate-type bin

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
#0 [mir_borrowck] borrow-checking `main::{closure#2}`
#1 [analysis] running analysis passes on this crate
end of query stack

And with RUST_BACKTRACE=full

error: internal compiler error: compiler/rustc_borrowck/src/universal_regions.rs:782:36: cannot convert `RePlaceholder(Placeholder { universe: U2, name: BrAnon(1) })` to a region vid

thread 'rustc' panicked at 'Box<dyn Any>', compiler/rustc_errors/src/lib.rs:1146:9
stack backtrace:
   0:     0x7ff6c79af4dc - std::backtrace_rs::backtrace::libunwind::trace::h2ab374bc2a3b7023
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/../../backtrace/src/backtrace/libunwind.rs:90:5
   1:     0x7ff6c79af4dc - std::backtrace_rs::backtrace::trace_unsynchronized::h128cb5178b04dc46
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7ff6c79af4dc - std::sys_common::backtrace::_print_fmt::h5344f9eefca2041f
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/sys_common/backtrace.rs:67:5
   3:     0x7ff6c79af4dc - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h213003bc5c7acf04
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/sys_common/backtrace.rs:46:22
   4:     0x7ff6c7a0d75c - core::fmt::write::h78bf85fc3e93663f
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/core/src/fmt/mod.rs:1126:17
   5:     0x7ff6c79a03d5 - std::io::Write::write_fmt::he619515c888f21a5
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/io/mod.rs:1667:15
   6:     0x7ff6c79b2a40 - std::sys_common::backtrace::_print::hf706674f77848203
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/sys_common/backtrace.rs:49:5
   7:     0x7ff6c79b2a40 - std::sys_common::backtrace::print::hf0b6c7a88804ec56
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/sys_common/backtrace.rs:36:9
   8:     0x7ff6c79b2a40 - std::panicking::default_hook::{{closure}}::h2dde766cd83a333a
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/panicking.rs:210:50
   9:     0x7ff6c79b25f7 - std::panicking::default_hook::h501e3b2e134eb149
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/panicking.rs:227:9
  10:     0x7ff6c8195241 - rustc_driver::DEFAULT_HOOK::{{closure}}::{{closure}}::h8ff5de92123cb8fd
  11:     0x7ff6c79b3259 - std::panicking::rust_panic_with_hook::hc09e869c4cf00885
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/panicking.rs:628:17
  12:     0x7ff6c922228b - std::panicking::begin_panic::{{closure}}::h5c7a29a9f3c50d8d
  13:     0x7ff6c92221c6 - std::sys_common::backtrace::__rust_end_short_backtrace::h11b7892876009c1e
  14:     0x7ff6c922225f - std::panicking::begin_panic::hd63e7fe0ba9182da
  15:     0x7ff6c92321dd - std::panic::panic_any::h3c06e175d31a9167
  16:     0x7ff6c9234740 - rustc_errors::HandlerInner::bug::he6d06053695a98ed
  17:     0x7ff6c9233f60 - rustc_errors::Handler::bug::h61abf9991ffffcbc
  18:     0x7ff6c90b0fde - rustc_middle::ty::context::tls::with_opt::hd0b25ef1fa372784
  19:     0x7ff6c90b14b0 - rustc_middle::util::bug::opt_span_bug_fmt::he982db01d383152c
  20:     0x7ff6c90b1426 - rustc_middle::util::bug::bug_fmt::h3252ae0338f3fde6
  21:     0x7ff6c9777ab7 - rustc_borrowck::type_check::free_region_relations::UniversalRegionRelationsBuilder::add_implied_bounds::h6fc51cad360e4c45
  22:     0x7ff6c9774d2d - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once::he159d5dccad8f6c8
  23:     0x7ff6c9800e5e - <core::iter::adapters::flatten::FlatMap<I,U,F> as core::iter::traits::iterator::Iterator>::next::h58a65807831cb8e5
  24:     0x7ff6c980ddbf - <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter::h278c3d2eb57eb6fe
  25:     0x7ff6c9776e76 - rustc_borrowck::type_check::free_region_relations::create::h1e099acafe4805c1
  26:     0x7ff6c97e0b3c - rustc_borrowck::type_check::type_check::h3c4dfe3f7cb7800b
  27:     0x7ff6c97ac5dc - rustc_borrowck::nll::compute_regions::haa6cecc831d0b29a
  28:     0x7ff6c97bb62c - rustc_borrowck::do_mir_borrowck::h700e8947cfdadc30
  29:     0x7ff6c9793083 - rustc_infer::infer::InferCtxtBuilder::enter::h9b172b82676b5208
  30:     0x7ff6c97baa44 - rustc_borrowck::mir_borrowck::h43f04ab543d2f43f
  31:     0x7ff6c97b5d91 - core::ops::function::FnOnce::call_once::h8103cea540657a78
  32:     0x7ff6ca351731 - rustc_query_system::dep_graph::graph::DepGraph<K>::with_task::h289a71605f390793
  33:     0x7ff6ca2f9423 - rustc_data_structures::stack::ensure_sufficient_stack::h4b6e02134b2da06d
  34:     0x7ff6c98b2cbd - rustc_query_system::query::plumbing::try_execute_query::hb362ed745d75a2d5
  35:     0x7ff6c991c269 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::mir_borrowck::hf27d489416d05e03
  36:     0x7ff6c934f1d8 - rustc_middle::ty::<impl rustc_middle::ty::context::TyCtxt>::par_body_owners::h227c8cd8436c8ccc
  37:     0x7ff6c9d4ecaa - rustc_interface::passes::analysis::hb918b02982537851
  38:     0x7ff6ca355b7f - rustc_query_system::dep_graph::graph::DepGraph<K>::with_task::h347feb22cb0d1ecf
  39:     0x7ff6ca2f9559 - rustc_data_structures::stack::ensure_sufficient_stack::h4b6ffa4a2dfebaef
  40:     0x7ff6ca23d49b - rustc_query_system::query::plumbing::try_execute_query::h784269645558384c
  41:     0x7ff6ca3139f2 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::analysis::ha8ab0b7748e9a5d1
  42:     0x7ff6c9d45b19 - rustc_interface::passes::QueryContext::enter::h805836b6c10e023c
  43:     0x7ff6c9d2caf4 - rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter::hded9061889acb733
  44:     0x7ff6c9d19e15 - rustc_span::with_source_map::hce3a664e96079636
  45:     0x7ff6c9d2c41c - scoped_tls::ScopedKey<T>::set::h033dd5b45ac9d9cd
  46:     0x7ff6c9d1ae4d - std::sys_common::backtrace::__rust_begin_short_backtrace::hc72d766e7b5b424b
  47:     0x7ff6c9d186b5 - core::ops::function::FnOnce::call_once{{vtable.shim}}::hdbb85447b47f9f9d
  48:     0x7ff6c79bfdf3 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h59eef3b9c8a82350
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/alloc/src/boxed.rs:1638:9
  49:     0x7ff6c79bfdf3 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hb5bbe017c347469c
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/alloc/src/boxed.rs:1638:9
  50:     0x7ff6c79bfdf3 - std::sys::unix::thread::Thread::new::thread_start::h62931528f61e35f5
                               at /rustc/308dffd25cb55bbb4a1fbee9822cf82c6a5d012d/library/std/src/sys/unix/thread.rs:106:17
  51:     0x7ff6c78d5259 - start_thread
  52:     0x7ff6c77ea5e3 - __GI___clone
  53:                0x0 - <unknown>

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.57.0-nightly (308dffd25 2021-09-22) running on x86_64-unknown-linux-gnu

note: compiler flags: -C opt-level=3 -C embed-bitcode=no -C debuginfo=2 -C debug-assertions=on -C incremental --crate-type bin

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
#0 [mir_borrowck] borrow-checking `main::{closure#2}`
#1 [analysis] running analysis passes on this crate
end of query stack

@tim3z
Copy link
Author

tim3z commented Sep 23, 2021

Small example for the crash

#![feature(generic_associated_types)]

use std::marker::PhantomData;

trait Iterable {
    type Iterator<'a>
    where
        Self: 'a;
    fn iter(&self) -> Self::Iterator<'_>;
}

struct SomeImplementation<'a> {
    data: &'a [usize],
}

impl<'a> SomeImplementation<'a> {
    fn new(data: &'a [usize]) -> Self {
        SomeImplementation { data }
    }
}

impl<'d> Iterable for SomeImplementation<'d> {
    type Iterator<'a>
    where
        Self: 'a,
    = std::slice::Iter<'a, usize>;
    fn iter(&self) -> Self::Iterator<'_> {
        self.data.iter()
    }
}

struct DoSomething<I: Iterable, F: Fn(&mut I::Iterator<'_>)> {
    f: F,
    _phantom: PhantomData<I>,
}

impl<I: Iterable, F: Fn(&mut I::Iterator<'_>)> DoSomething<I, F> {
    fn really_do_something(&self, i: I) {
        (self.f)(&mut i.iter());
    }
}

fn main() {
    let data = Vec::<usize>::new();
    DoSomething {
        f: |_| (),
        _phantom: PhantomData,
    }
    .really_do_something(SomeImplementation::new(&data));
}

@jackh726
Copy link
Member

Haven't read through all the new comments, but figured I'd jot down what I've learned when trying to fix this.

This is effectively a more difficult variant of #88459. #88441 fixes that issue, but isn't quite enough to fix this one (though it does allow us to make more progress)

@jackh726
Copy link
Member

GATs issue triage: not blocking. This isn't really a GAT issue, though it does pop up a little bit more often with GATs. I've done some work elsewhere that has and will continue to improve the story here, but for now, there's nothing specific to GATs to do here.

@jackh726 jackh726 added the GATs-triaged Issues using the `generic_associated_types` feature that have been triaged label Oct 20, 2021
@jackh726 jackh726 added the S-bug-has-test Status: This bug is tracked inside the repo by a `known-bug` test. label Mar 12, 2022
bors added a commit to rust-lang-ci/rust that referenced this issue Sep 13, 2022
…er-errors

Stabilize generic associated types

Closes rust-lang#44265

r? `@nikomatsakis`

# ⚡ Status of the discussion ⚡

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

# Stabilization proposal

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

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

## Motivation

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

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

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

## What is stabilized

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

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

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

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

```rust
struct X;
struct Y;

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

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

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

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

To take a relatively simple example:

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

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

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

## What isn't stabilized/implemented

### Universal type/const quantification

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

Here is an example where this is needed:

```rust
trait Foo {}

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

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

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

### Object-safe GATs

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

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

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

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

### Higher-kinded types

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

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

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

## Tests

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

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

## Remaining bugs and open issues

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

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

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

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

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

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

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

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

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

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

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

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

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

## Potential Future work

### Universal type/const quantification

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

###  Object-safe GATs

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

### GATified std lib types

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

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

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

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

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

### Better implied bounds on higher-ranked things

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

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

## Alternatives

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

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

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

### Stabilize lifetime GATs first

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

## History

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

Stabilize generic associated types

Closes rust-lang#44265

r? `@nikomatsakis`

# ⚡ Status of the discussion ⚡

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

# Stabilization proposal

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

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

## Motivation

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

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

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

## What is stabilized

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

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

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

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

```rust
struct X;
struct Y;

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

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

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

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

To take a relatively simple example:

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

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

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

## What isn't stabilized/implemented

### Universal type/const quantification

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

Here is an example where this is needed:

```rust
trait Foo {}

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

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

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

### Object-safe GATs

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

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

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

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

### Higher-kinded types

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

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

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

## Tests

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

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

## Remaining bugs and open issues

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

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

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

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

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

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

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

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

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

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

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

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

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

## Potential Future work

### Universal type/const quantification

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

###  Object-safe GATs

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

### GATified std lib types

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

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

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

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

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

### Better implied bounds on higher-ranked things

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

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

## Alternatives

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

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

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

### Stabilize lifetime GATs first

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

## History

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

No branches or pull requests

4 participants