---
tags: traits, async, rustc
---

# RPITIT Ahoy (Return position impl trait in traits discussion)

## 2022-11-29

trait Foo {
    type Bar: Trait = impl Trait;
    fn foo() -> Self::Bar {
        
    }
}

## 2022-11-18

trait Foo {
    fn foo() -> impl Trait;
}
// desugars to
trait Foo {
    type Cake: Trait;
    fn foo() -> Self::Cake;
}

trait Foo {
    fn foo() -> impl Trait {}
}
// desugars to
trait Foo {
    type Cake: Trait    = impl Trait;
         ^^^^ same def_id ^^^^^^^^^^ as that
    fn foo() -> Self::Cake {}
}

## Older stuff

Example:

impl<'a> ... {
    fn bar<'b>(
        t: impl for<'c> SomeTrait<'c>
    ) -> impl Debug + for<'d> SomeTrait<'d> + 'b
    where
        ...
}

Version 1 (Niko's ideal):

* we have a visitor that extracts the "free" lifetimes from some piece of AST
* when applied to the bounds `Debug + for<'d> SomeTrait<'d> + 'b`, it would just yield `'b`
* when we are translating the bounds from AST into HIR
* Niko's ideal
* name resolution links from a reference to a lifetime like `'b` over to the definition (in the AST itself)
* when we "lower" binders
* e.g., we start lowering the `fn bar<'b>` method
* we would create the HIR definition
* and have a mapping like
* ast node -> hir definition
* so that we can translate the name resolution result into the HIR
* each time we "lower" a binder, we get a fresh HIR definition
* so in that case:
* when we lower `Debug + for<'d> SomeTrait<'d> + 'b`
* we encounter `for<'d> SomeTrait<'d>`, we create a `'d1` in the HIR and map `'d -> 'd1`.
* How it actually works today:
* we create most def-ids during name resolution
* so they have parents and things
* things are a bit more complex
* an alternative might be
* visitor that visits some ast A that returns a tuple of
* lifetimes that appear free
* lifetimes that are bound within A
* when applied to `Debug + for<'d> SomeTrait<'d> + 'b`, it would yield:
* free lifetimes: `'b`
* bound lifetimes: `'d`
* when we are lowering a RPIT (or RPITIT), we could create a remapping from
* 'b -> 'b1 (as today)
* 'd -> 'd1 (this is the new thing)
* these seem a bit different -- we haven't seen the binder for `'d` yet -- but that's... ok
* there is add'l info that we need to create the generics for the new opaque type
* we need to know which type parameters are in scope
* this includes any APIT parameters
* we need to know the where clauses that are in scope
* this includes the bounds on APIT parameters

to come back to our example...

impl<'a> ... {
    fn bar<'b>(
        t: impl for<'c> SomeTrait<'c>
    ) -> impl Debug + for<'d> SomeTrait<'d> + 'b
    where
        ...
}

...for the APIT `impl for<'c> SomeTrait<'c>`, which is roughly equivalent to this...

impl<'a> ... {
    fn bar<'b, T>(
        t: T
    ) -> impl Debug + for<'d> SomeTrait<'d> + 'b
    where
        T: for<'c> SomeTrait<'c>
}

* The "lifetime visitor", when applied to the RPIT bounds, has the following role today:
* it identifies the lifetimes which should be "captured" by the opaque type (i.e., added as parameters to the opaque type)
* If we extend it to return the `'d` lifetime:
* it has the added job of identifying lifetime parameters that will be remapped within the bounds

The APIT example is interesting because the bounds get lowered *twice*. For an RPIT, the bounds only get lowered once.

* The lifetime visitor could also be used for other things
* could apply to the APIT bounds to find out...
* which lifetimes (like `'c`) will need to be mapped to a fresh def-id the second time

fn filter_fold<T, Acc>(
    mut predicate: impl for<'c> FnMut(&'c T) -> bool,
    mut fold: impl FnMut(Acc, T) -> Acc,
) -> impl FnMut(Acc, T) -> Acc {
    move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
}

fn foo<T: for<'c> FnMut(&'c u32)>() -> impl Sized {}

//fn foo<T: for<'a> Fn(&'a u8)>() -> impl Sized

### niko's proposal

* when we lower a polytraitref
* check if we have remappings installed
* this is the sign that we are lowering the same AST twice
* in the future, this shouldn't be necessary, because we should ALWAYS be creating new def-ids
* if so, create new def-ids for each lifetime introduced by the binder
* these new def-ids will have a different parent than the original def-ids, we could even assert this if we wanted
* introduce a new remapping (layer) from the old def-ids to the new ones
* continue with lowering and it will "just work"

## 2022-06-28

Idea for this:

fn foo<'a, T>() -> impl Iterator<Item = T::Item>
where
    T: Foo<'a>
{}

without full existentials, what can we do?

type foo<T>: Iterator<Item = T::Item>
where
    T: Foo<'erased>; // <-- idea: use a special marker lifetime for "something existential", present in the HIR

fn foo<'a, T>() -> foo<T>
where
    T: Foo<'a>
{}

trait Foo<'a>: Bar { }
trait Bar { type Item; }

* There is currently a query that tries to resolve `T::Item`--
* it does a "special walk" through the predicates
* in this special query to resolve `T::Item`, we allow `'erased` to appear BUT
* if the final result is includes `'erased`, e.g., `<T as Foo<'erased>>::Item`, we issue an error
* if the final result might not include `'erased`, e.g., `<T as Bar>::Item`, that's ok
* We also need the hack that:
* when we ask for the predicates of `foo` (the TAIT), we either return an empty list or we ignore the `'erased` entries or something
* and then we don't try to prove that the final inferred value is well-formed given those where-clauses (because the list is incomplete)
* these parts are blocked on proper existentials

## 2022-06-27

fn foo<'a, 'b, 'c>() -> impl Sized + 'a + 'c
where
    'c: 'b,
    'b: 'a,
{}

// * we do not capture 'b
// * but if we ignore both where clauses, we lose the fact that 'c: 'a

trait Foo<'a>: Bar
trait Bar

fn foo<'a, T>() -> impl Sized 
where
    T: Foo<'a>
{}

// * we do not capture 'a
// * but if we ignore this where-clause, we lose track of the fact that `T: Bar`

solutions:

* elaborate the bounds first :-1:
* `where T: Foo<'a>`, elaboration would expand to `where T: Foo<'a>, T: Bar`
* if we filter after that, it works
* three problems:
* we don't elaborate transition lifetime relationships like the first example
* we elaborate after HIR is constructed (too late)
* I think there are more complex scenarios like `for<'a> ..` that would be harder to solve w/ elaboration
* alternative, that a-mir-formality would support :+1: but can't do it yet
* instead of removing `T: Foo<'a>` altogether
* replace with `where exists<'a> T: Foo<'a>`
* you could do the same with the first example
* two problems:
* rustc doesn't support this kind of thing
* and neither does a-mir-formality (yet)
* we do need this kind of support for other use cases
* ignore the bounds :scream:
* when we create this TAIT we flagit as "desugared from a impl Trait"
* and we ignore checking the bounds when we check if the inferred type is a good fit for the TAIT
* this is horrible, but it's actually what we do today, so no *more* horrible (pretty sure)

### connection to WF check

trait Foo<'a>: Bar
trait Bar

fn foo<'a, T>() -> impl Sized 
where
    T: Foo<'a>
{}

// becomes

type Foo<MY_T>: Sized
where
    MY_T: Foo<'static>;

fn foo<'a, T>() -> Foo<T>
where
    T: Foo<'a>
{
    None::<T> // returning an `Option<T>`
}

Two relevant checks:

* First, `fn foo<'a, T>() -> Foo<T>` has to show that
* `Foo<T>` is well-formed
* which implies `T: Foo<'static>` must hold (that's the where clause on `Foo`)
* which is not true
* Second, after we infer a hidden type `X`
* in this case, `X = Option<MY_T>`
* there is a check in the compiler that `Option<MY_T>: Sized`
* assuming that the where-clauses hold
* in this case, the where-clauses are `MY_T: Foo<'static>`
* these where clause are false, not great

### connection to WF check

trait Foo<'a> {
}
trait Bar {
    type Item;
}


fn foo<'a, T>() -> impl Iterator<Item = T::Item>
where
    T: Foo<'a>
{}

* How will we solve this problem with `T::Item` -- given that where-clauses have to come from the owner type?

### RPITIT current design

trait Foo {
    fn foo(&self) -> impl Debug;
    //               ~~~~~~~~~~ how do users name this type?
}

fn do_something<F: Foo>()
where
    /* F::foo() returns a Send type */
    F::foo(..): Send,
    F: Foo<foo(..): Send>, // shorthand

### async

async fn foo(x: &u32, b: &u64) {}

// desugars to

fn foo<'a, 'b>(x: &'a u32, b: &'b u64) -> impl Future<Output = ()> + 'a + 'b { async move { } }

## 2022-04-01

fn foo<T: Clone>(t: T) -> impl Clone {
    t
}

desugars to this in HIR:

fn foo<T: Clone>(t: T) -> Bar<T> {
    type Bar<U: Clone> = impl Clone;
    t
}

in the AST we have...

* [`ast::Fn`][](node_id=N0)
* Generics [`ast::Generics`][]
* [`ast::GenericParam`][](ident=T, node_id=N1)
* ReturnType [`ast::Ty`][](node_id=N2)
* [`TyKind::ImplTrait`][](node_id=N3)
* [`ast::GenericBounds`][]

in the name resolver we have created...

* a DefId D1 for the function
* a DefId D2 for T
* a DefId D3 for the Impl Trait

and we have a map `resolver.node_id_to_def_id` that contains *at least* the def-id for each *declaration*

* N0 -> D1
* N1 -> D2
* N3 -> D3 <-- Niko has mixed feelings about this

we want to generate...

* [`hir::ItemKind::Fn`][]: Item for the function
* this has DefId D1
* [`hir::Generics`][]
* [`hir::GenericParam`][](hir_id = H0, name = T)
* this has DefId D2
* [`hir::GenericBounds`][]
* ... `T: Clone` ... with hir_id H2
* return type is a `hir::Ty` with...
* [`hir::OpaqueDef`](D3, `[T]`)
* [`hir::ItemKind::OpaqueTy`][]
* this has DefId D3 *which is a child of D1*
* [`hir::Generics`][]
* [`hir::GenericParam`][](hir_id = H1, name = U)
* this has (fresh) DefId D4
* [`hir::GenericBounds`][]
* ... `U: Clone` ... with hir_id H3

implementation notes

* each def-id we synthesize during hir lowering has a DUMMY_NODE_ID
* because there is no node-id in the AST that maps to it
* we sometimes lower ast nodes *twice* in order to produce duplicates in the HIR
* but with different hir-id-owners, hence the mapping from node-id to hir-id is distinct and fresh hir-ids are assigned
* also we use the remapping to remap DefId D2 (`T`) to D4 (`U`)

also some kind of def-id maps

[`hir::GenericBounds`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/hir/type.GenericBounds.html
[`hir::ItemKind::OpaqueTy`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/hir/struct.OpaqueTy.html
[`hir::GenericParam`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/hir/struct.GenericParam.html
[`hir::Generics`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/hir/struct.Generics.html
[`hir::ItemKind::Fn`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/enum.ItemKind.html#variant.Fn
[`TyKind::ImplTrait`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/ast/enum.TyKind.html#variant.ImplTrait
[`ast::GenericBounds`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/ast/type.GenericBounds.html
[`ast::GenericParam`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/ast/struct.GenericParam.html
[`ast::Generics`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/ast/struct.Generics.html
[`ast::Fn`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/ast/struct.Fn.html
[`ast::Ty`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/ast/struct.Ty.html

## 2022-02-23

fn foo<'a, 'b, T>() -> impl Trait + 'b {
    ...
}

/// HIR representation

// old is really annoying

fn foo<'a, 'b, T>() -> Anon<'static, 'static, 'b, T> {
    #[magically_have_access_to_owner_generics]
    type Anon<'b> = impl Trait;
}

// new version


fn foo<'a, 'b, T>() -> Anon<'b, T> {
    type Anon<'b, T> = impl Trait;
}

/// Type system representation:

// function signature
fn foo<'a, 'b, T>() -> ty::Opaque(some_def_id, subst: ['static, 'static, 'b, T])

// new case:
fn foo<'a, 'b, T>() -> ty::Opaque(some_def_id, subst: ['b, T])

/// RPIT marker

is OpaqueTypeOrigin::FnReturn

## 2022-01-19

Problem:

There is a map in AST lowering

{AstNodeId -> HirId}

HirId = (OwnerDefId, RelativeHirId)

Idea #1:

{OwnerDefId -> {AstNodeId -> RelativeHirId}}

Idea #2:

* Conceptually a stack of `{AstNodeId -> RelativeHirId}` maps
* Push when you enter a new owner hir-id
* Pop when you exit
* [There is already a helper that swaps fields out when entering a new owner hir-id](https://github.com/rust-lang/rust/blob/2f004d2d401682e553af3984ebd9a3976885e752/compiler/rustc_ast_lowering/src/lib.rs#L443)

we have to validate that Idea #2 works, maybe there is some reason we keep the cached entries for older HIR nodes.

Step 1

* Add an assertion when looking into the map that the current owner def-id is equal to the owner def-id of the thing you find in the map
*

## 2021-12-21

// User writes this:
type Foo = (impl Trait, impl Trait);

// Internally, we have:
type Opaque1: Trait; // ItemKind::OpaqueTy
type Opaque2: Trait; // ItemKind::OpaqueTy
type Foo = (Opaque1, Opaque2); // ItemKind::TyAlias
    // Ty = TyKind::Tuple([
    //     TyKind::OpaqueDef(Opaque1), 
    //     TyKind::OpaqueDef(Opaque2)
    // ])

// User writes this:
type Foo = impl Trait;

// Internally, we have:
type Opaque1: Trait; // ItemKind::OpaqueTy
type Foo = Opaque1; // ItemKind::TyAlias(<Ty>, _)
    // Ty = TyKind::OpaqueDef(Opaque1)

`TyKind::OpaqueDef` is a specialized variant of `TyKind::Path` that refers to the (builtin, anonymous) opaque types.

// User writes this:
type Foo<'a, T> = (impl Trait, impl Trait);

// Internally, we have:
type Opaque1<'a, T>: Trait; // ItemKind::OpaqueTy
type Opaque2<'a, T>: Trait; // ItemKind::OpaqueTy
type Foo<'a, T> = (Opaque1<'a, T>, Opaque2<'a, T>); // ItemKind::TyAlias
    // Ty = TyKind::Tuple([
    //     TyKind::OpaqueDef(Opaque1, &['a, T]), 
    //     TyKind::OpaqueDef(Opaque2, &['a, T])
    // ])

## ---

fn foo<'a, 'b, T, U>(a: &'a i32, b: &'b i32) -> impl MyTrait<T> + 'a
where
    'a: 'b,
{
    a
}

OpaqueDef<'a, T, U>

## 2021-12-16

fn foo<'a, 'b, T, U>(a: &'a i32, b: &'b i32) -> impl MyTrait<T> + 'a
where
    'a: 'b,
{
    a
}

`OpaqueDef<T, U, 'a>`

// not real rust syntax but prob it should be:
type Foo<'a, T, U>: MyTrait<T> + 'a /* = hidden type */;
//       ^^^^^^^^ captures

fn foo<'a, 'b, T, U>(a: &'a i32, b: &'b i32) -> Foo<'a, T, U>
where
    'a: 'b,
{
    a
}

struct Hidden<T: Debug>(Option<T>);

// SUGARY
fn foo<'a, 'b, T, U>(a: &'a i32, b: &'b i32) -> impl MyTrait<T> + 'a
where
    T: Debug,
    U: Debug,
{
    Hidden(None::<(T, U)>)
    //Hidden Hidden<(T, U)>
}

// DESUGARED

// not real rust syntax but prob it should be:
type Foo<'a, T, U>: MyTrait<T> + 'a /* = Hidden<(T, U)> */
//       ^^^^^^^^ captures
where
    T: Debug,
    U: Debug;
//  ^^^^^^^^ bounds

fn foo<'a, 'b, T, U>(a: &'a i32, b: &'b i32) -> Foo<'a, T, U>
where
    'a: 'b,
    T: Debug,
{
    Hidden(None::<T>)
}

---

fn foo<'a, 'b>(a: &'a i32, b: &'b i32) -> impl Sized + 'a + 'b
where
    'a: 'b,
{
    a
}

fn bar<'c, 'd>(c: &'c i32, d: &'d i32) -> impl Sized + 'c + 'd
where
    'c: 'd,
{
    foo(c, d)
}

fn main() {}

---

// Hidden type: Option<T>, which references T
fn foo<T: Clone, U, 'a, 'b>(t: T) -> impl Clone + 'a + 'b
 where 'a: 'b { // OpaqueDef<T, U, 'a>
    Some(t) // Option<T>
}

## 2021-12-07

### Why is the rule that we capture only types and not lifetimes (unless explicitly in the bounds)

fn outer2(x: &Vec<u32>) -> impl Debug { x.iter().sum() }

fn main() {
    let mut something = vec![22, 44];
    let z = outer2(&something);
    something.push(66); // don't want an error here
    println!("{:?}", z);
}

tl;dr:

* We try to make "capturing" in the return type explicit
* It happens a lot that most of the input lifetimes are not being used

fn outer2<T>(x: T) -> impl Debug  {
    // note that T is not used here
    22
}

fn main() {
    let mut something = vec![22, 44];
    let z = outer2::<&Vec<u32>>(&something); // T = &Vec<u32>, T gets captured
    something.push(66); // ERROR
    println!("{:?}", z);
}

Try to capture the most common cases. This is the "explicit form" for when that doesn't work for you.

type Outer2 = impl Debug;
fn outer2<T>(x: T) -> Outer2 {
    // note that T is not used here
    22
}

fn main() {
    let mut something = vec![22, 44];
    let z = outer2::<&Vec<u32>>(&something); // T = &Vec<u32>, T not captured
    something.push(66); // no error
    println!("{:?}", z);
}

### Solution

[How to manage this](https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/rpit.20refactor)

1. Parsing into AST
2. Name resolution on the AST (produces some kind of map from AST paths to definitions)
3. AST lowering into HIR
4. reads the name resolution results and produces a `Res` in the HIR that maps to a `DefId`

fn foo<T>() -> impl Debug
where
    T: Ord
{ }

// want to produce

type Foo<T1> = impl Debug
where
    T1: Ord;

fn foo<T>() -> Foo<T>
where
    T: Ord
{ }

For example:

* There will be some AST nodes that represent `where T: Ord`
* the AST node for `T` will have a "name resolution result" that maps to `T` on `foo`
* Conceptually, you can model this as:
* `AstNameResolution: Map<AstNode, DefId>` 'more or less'

fn lower_ast_to_hir(&mut self, path: &ast::Path) -> hir::Path {
    let res = match self.ast_name_resolution[path.id] {
        SomeVariant(def_id) => Res::DefId(def_id),
        ...
    };
    
    hir::Path { res }
}

What we want to do, in terms of that example:

* Produce the same HIR we did before (`where T: Ord`) for use within `foo` function
* Produce the HIR for the `Foo` TAIT, which is *almost* the same but any reference to `T` now is mapped to `T1`
* `where T1: Ord`

#### Option 1.

Lower the AST twice, and have a mapping at that time.

let f = /* AST for some function that returns impl trait */;
let f_wc_hir = lower_ast_to_hir(f.where_clauses, |x| x); // <-- old code, nothing changed

let tait = /* new def id */;
let tait_generics = copy_of(f.generics);
let map = (f.generics -> tait.generics);
let tait_wc_hir = lower_ast_to_hir(f.where_clauses, |x| map[x]); // <-- old code, nothing changed

fn lower_ast_to_hir(&mut self, path: &ast::Path, map_fn: impl Fn(Res) -> Res) -> hir::Path {
    let res = match self.ast_name_resolution[path.id] {
        SomeVariant(def_id) => Res::DefId(def_id),
        ...
    };
    let res = map_fn(res);
    
    hir::Path { res }
}

#### Option 2.

Lower the AST to HIR, then clone the HIR and apply a mapping as we do so.

let f = /* AST for some function that returns impl trait */;
let f_wc_hir = lower_ast_to_hir(f.where_clauses); // <-- old code, nothing changed

let tait = /* new def id */;
let tait_generics = copy_of(f.generics);
let map = (f.generics -> tait.generics);
let tait_wc_hir = clone_hir(f_wc_hir, |x| map[x]);

## 2021-12-02

fn foo() -> impl Send + 'a {}

type Foo<'a> = impl Send;

fn foo() -> Foo<'a>;

fn foo() -> impl Send + 'a + 'b {}

type Foo<'a, 'b> = impl Send;

// fn foo() -> Foo<'a, 'b>;

If you are trying to show this...

Foo<P0...Pn>: 'x

where `Foo` is an opaque type and `P0...Pn` are its generic parameters. You can do that in two ways:

1. If the `bounds(Foo<P0...Pn>)` include some `'b` where `'b: 'a`
2. If `Pi: 'x` for all `i`

Applying to this specific example:

Foo<'a, 'b>: 'x

In both cases:

* If we know that `'a: 'x` and `'b: 'x` that's good enough

In the first case:

Bounds(Foo<'a, 'b>) = [Send, 'a, 'b]
* If 'a: 'x, that's good enough
* If 'b: 'x, that's good enough

### Case we will have to solve eventually

trait Foo<'a> {
    type Bar;
}

fn foo<'a, T> -> impl PartialEq<T::Bar>
where
    T: Foo<'a>

problem:

* User wrote `T::Bar` but that's "shorthand" for `<T as Foo<'a>>::Bar`
* so actually `'a` is used here
* we don't (currently, at least) discover this until after AST lowering is complete
* in typeck, specifically
* in the astconv/collect code
* oh wait we don't handle this today
* [playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=90252a49fb42d2005a75c7c1c68a04dc)
* well that's simpler:
* create a def-id for each parameter that is explicitly referenced (or just all of them, if that's easier)
* create the opaque type as a sibling with
* generics that are explicitly referenced
* where clauses that only contain names that were explicitly referenced
* "remapped" to the corresponding def-ids
* copy of bounds
* "remapped" to the corresponding def-ids

fn foo<T>() -> (impl Debug, impl Debug) { }
// both impl Debugs need a copy of the `T`

type Foo1<T>: Debug; // <-- "opaque type"
type Foo2<T>: Debug;

fn foo() -> impl Debug {
    ()    
}

fn is_send<T: Send>(t: T) {
    
}

fn bar() {
    // This SHOULD compile with `-> impl Debug` but should not
    // compile with `type Foo = impl Debug` and `-> Foo`
    let x = foo();
    is_send(x);
}

// should compile
 
mod m {
    pub type X = impl Debug;

    pub fn foo() -> X {
        ()    
    }

}

fn bar() {
    fn is_send<T: Send>(t: T) {

    }
    
    let x = m::foo();
    is_send(x);
}

// should not compile
//
// when you're inside the scope, you are supposed to either
//
// * rely only on the declared bounds (`Debug`)
//
// or
//
// * fully constrain the type for `X`
 
pub type X = impl Debug;

pub fn foo() -> X {
    ()    
}

// bar does not say what X should be,
// but it does require X to be Send,
// which is not declared
fn bar() {
    fn is_send<T: Send>(t: T) {

    }
    
    let x = m::foo();
    is_send(x);
}

interesting example with an opaque type explicitly inside a function:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=849ac936bdf979f0593f77561183127d

final notes

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=7d09605f8ab8b9e2a656a24f92093b74

## 2021-11-30

trait Foo {}

impl<'x> Foo for &'x mut i32 {}

trait Bar {
    fn bar<'a>(x: &'a mut i32) -> impl Foo;
    // desugars to
    
    type bar: Foo;
    fn bar<'a>(x: &'a mut i32) -> <Self as Bar>::bar;
}

fn muh<'b, T: Bar>(y: &'b mut i32) {
    let a = T::bar(y);
    let _b = T::bar(y); // ERROR
    let _c = a;
}

fn main() {}

trait Bar<'a> {
    fn bar<'b>(x: &'a mut i32) -> impl Foo;
    // desugars to
    
    type bar: Foo;
    fn bar<'b>(x: &'b mut i32) -> <Self as Bar<'a>>::bar;
    //                                        ^^^^
}

trait Bar<'a> {
    fn bar<'b>(x: &'a mut i32) -> impl Foo + 'b;
    // desugars to
    
    type bar<'b>: Foo + 'b;
    fn bar<'b>(x: &'b mut i32) -> <Self as Bar<'a>>::bar<'b>;
    //                                        ^^^^      ^^^^
}

impl Foo for Bar<'a> {
    type bar<'b> = impl Foo + 'b;
    
    fn bar<'b>(x: &'b mut i32) -> <Self as Bar<'a>>::bar<'b> {
        ...
    }
}

let x: <SomeType as Bar<'a>>::bar<'b> = ..;
let x: OpaqueTyp<'a, 'static, 'b> = ..;

## precisely how many lifetime arguments *do* we need for the GAT?

* oli: 4
* https://github.com/rust-lang/rust/issues/60670
* can we get away with less?

trait Foo {
    async fn do_the_thing(&self, data: &MyHashMap<&u32, &u64>);
    
    // Naive:
    type do_the_thing<'a, 'b, 'c, 'd>: Future<Output = ()>;
    fn do_the_thing<'a, 'b, 'c, 'd>(
        &'a self, 
        data: &'b MyHashMap<&'c u32, &'d u64>
    ) -> Self::do_the_thing<'a, 'b, 'c, 'd>;

    type do_the_thing<'e>: Future<Output = ()>;
    fn do_the_thing<'a, 'b, 'c, 'd, 'e>(
        &'a self, 
        data: &'b MyHashMap<&'c u32, &'d u64>
    ) -> Self::do_the_thing<'e>
    where
        ('a + 'b + 'c + 'd): 'e;
}

impl Foo for ... {
    fn do_the_thing<'a>(
        &'a self, 
        _data: &MyHashMap<&u32, &u64>
    ) -> impl Future<Output = ()> + 'a {
        async move { self.bar(); }
    }
    
    // desugar to
    type do_the_thing<'e>: Future<Output = ()>;
    fn do_the_thing<'a, 'e>(
        &'a self, 
        _data: &MyHashMap<&u32, &u64>
    ) -> Self::do_the_thing<'e>
    where 'a: 'e;
}

[This has been observed before](https://github.com/rust-lang/rust/issues/60670)...

## What Santiago did thus far

* Creating associated type as a sibling
* In the `generics_of` query...
* making the whole system believe that "this type which is a sibling" is actually a child
* so that you inherit the generics and friends
*

## What happens if we make it a sibling?

* Collect lifetimes, generic parameters, predicates
* also implied bounds
* Change the definition of "defining scope" (maybe)

## What Niko expected

trait Foo {
    fn bar<P0..Pn>(A0..An) -> impl SomeThing
    where WC...;
    // P0..Pn could be types or lifetimes (including all elided lifetimes)
}

// Step 0
//
// only works for cases with no generics
trait Foo {
    type bar: SomeThing
    where WC...;
    
    fn bar<P0..Pn>(A0..An) -> <Self as Foo>::bar<P0..Pn>
    where WC...;
    // P0..Pn could be types or lifetimes (including all elided lifetimes)
}

// Step 1
trait Foo {
    type bar<Q0..Qn>: SomeThing
    where [Q0...Qn / P0...Pn] WC...;
    
    fn bar<P0..Pn>(A0..An) -> <Self as Foo>::bar<P0..Pn>
    where WC...;
    // P0..Pn could be types or lifetimes (including all elided lifetimes)
}

fn bar<P0..Pn>(A0..An) -> impl Trait
where WC....
{
    
}

type __bar__<Q0..Qn> = impl SomeThing
where [Q0...Qn / P0...Pn] WC...;

fn bar<P0..Pn>(A0..An) -> __bar__<P0...Pn>
where WC....
{
    
}

* how to tell which generics "appear in" the bounds?
* same problem as we encounter for const generics!

## Older

trait Foo {
    fn foo<'a, T>() -> impl Send;
}

would lower into ...

trait Foo {
    type foo<...>: Send;

    fn foo<'a, T>() -> Self::foo<...>;
}

Should we make the associated type a sibling of the function or a child?.

trait Foo {
    type foo::rpit<'a> = impl Trait<'a, T>;

    fn foo<'a, T>() -> foo::rpit<'a>;
}

The following example using a generic param should work but unless we carry over `I` it ICEs.

// check-pass

trait Parser {
    type Input;
}

trait Parseable {
    fn parser<I>() -> impl Parser<Input = I>;
}

fn main() {}

[nix-shell:~/src/oss/rust2]$ RUST_BACKTRACE=1 ./build/x86_64-unknown-linux-gnu/stage1/bin/rustc --edition 2018 src/test/ui/impl-trait/rpitit/generic_bounds.rs
error: internal compiler error: compiler/rustc_middle/src/ty/subst.rs:534:17: type parameter `O/#2` (O/2) out of range when substituting, substs=[Self]

thread 'rustc' panicked at 'Box<dyn Any>', /home/spastorino/src/oss/rust2/compiler/rustc_errors/src/lib.rs:1115:9
stack backtrace:
   0: std::panicking::begin_panic::<rustc_errors::ExplicitBug>
             at ./library/std/src/panicking.rs:525:12
   1: std::panic::panic_any::<rustc_errors::ExplicitBug>
             at ./library/std/src/panic.rs:57:5
   2: <rustc_errors::HandlerInner>::span_bug::<rustc_span::span_encoding::Span>
             at ./compiler/rustc_errors/src/lib.rs:1115:9

The following example using a lifetime param should work but it fails ...

trait Parser {
    type Input;
}

trait Parseable {
    fn parser<'a>() -> impl Parser<Input = &'a str> + 'a;
}

fn main() {}

error[E0107]: missing generics for associated type `Parseable::{opaque#0}`
   |
note: associated type defined here, with 1 lifetime parameter: `'a`
help: add missing lifetime argument
   |
1  | <'a>// check-pass
   | ++++

error: aborting due to previous error

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

## How to implement incrementally

`compiler\rustc_typeck\src\collect.rs:1374`

fn generics_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::Generics {
    use rustc_hir::*;

    let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());

    let node = tcx.hir().get(hir_id);
    let parent_def_id = match node {
        Node::TraitItem(_) => {
            // Check for associate type from impl trait,
            // get appropriate associated function as the parent
        }
        // ...

Could probably store the DefId here to start with:

`compiler\rustc_hir\src\hir.rs:2016`

pub enum TraitItemKind<'hir> {
    // ...
    Type(GenericBounds<'hir>, Option<&'hir Ty<'hir>>, /* new */ Option<DefId>),

DefId should be handled in the same way as `fn_def_id` in `lower_opaque_impl_trait` in `compiler\rustc_ast_lowering\src\lib.rs`.
Specifically, add a new parameter to `lower_impl_trait_in_trait` that's passed to the `TraitItem`, the method `DefId` also needs adding to `ImplTraitContext::ReturnPositionInTrait`.

# Impls

trait Foo {}

impl<'x> Foo for &'x i32 {}

trait Bar {
    fn bar<'a>(x: &'a i32) -> impl Foo;
}

impl Bar for () {
    fn bar<'a>(x: &'a i32) -> impl Foo {
        x // should get rejected, no `'a` in the `impl Foo`
    }
}

trait Foo {}

impl<'x> Foo for &'x mut i32 {}

trait Bar {
    type ty#bar<'xx, 'yy>; // 'xx is always 'static, but there is no 'yy, because `impl Foo` has no lifetimes mentioned
    fn bar<'a>(x: &'a mut i32) -> impl Foo;
}

fn muh<'b, T: Bar>(y: &'b mut i32) {
    let a: T::ty#bar::<'b> = T::bar::<'b>(y);
    let b: T::ty#bar::<'b> = T::bar::<'b>(y); // ERROR
    let c = a;
}

regular impl trait:

fn bar<'a>(x: &'a mut i32) -> impl Foo {
    ()
}

// same, but with TAIT
type Bar<'a> = impl Foo;

fn bar2<'a>(x: &'a mut i32) -> Bar<'static> {
    ()
}


fn foo<'a>(x: &'a mut i32) -> impl Foo + 'a {
    x
}

// same, but with TAIT
type Bar2<'a, 'aa> = impl Foo + 'aa;

fn foo2<'a>(x: &'a mut i32) -> Bar2<'static, 'a> {
    x
}