---
# System prepended metadata

title: GATs ahoy (1.0)

---

# GATs ahoy (1.0)

* [GATs Ahoy 2.0](https://hackmd.io/sxZENS1GTbil8qTTtgzQjQ)

## 2021-12-13

* What needs to happen
    * GAT triage
* Potential experiments
    * "what do people do when they're not instructed what to do"
    * "harm of getting it wrong is so low"
        * auto-fix will do it
* Stalled
    * Where clause syntax

### Jack's PR

* introduces a mode to AssocTypeNormalizer that falls back for inference variables

```rust
// Crate A
struct Set<K: Eq + Hash> { }

impl<K> Set<K> {
    fn insert(&mut self, value: K) {
        let hash = Hash::hash(&value);
        ...
    }
}

// Crate B


```

## 2021-11-29

### Niko's master plan

```rust
trait LendingIterable {
    final type Item<'me> = Self::iter<'me>::Item
    where
        Self: 'me;
    
    fn iter(&self) -> impl Iterator + '_;
}
```


```rust
trait LendingIterable {
    final type Item<'me> = Self::iter<'me>::Item
    /* implied: */
    where Self::iter<'me>::Item: OK;
    
    fn iter(&self) -> impl Iterator + '_;
}

type Item<Self, 'me> = Self::iter<'me>::Item
    /* implied: */
    where Self::iter<'me>::Item: OK;
```

* Current "default bounds requirement"
    * we check currently that the bounds are present
        * exactly in the form expected
    * but better would be to check that they can be proven
        * in the environment of the trait
* To do the above design, need to include:
    * implied bounds of `T: OK` include `WF(T)`
    * [playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=32bcd25cf9c0f2671233b6c58ff784d9) -- error: hack
    * [playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=d22f40fef3cb9f37ebbac07af585cb99) -- removed Eq bound, gets error
    * 

### "Jack's issue"

* #87748
* Jack's previous solution
    * treat unnormalized types in fn sig as "wf"
    * seemed ok but we missed something
    * implemented in PR #88312
* But #91068 filed 10 days ago
    * Related to https://github.com/rust-lang/rust/issues/25860
* Jack's expected solution
    * projection type is WF if all input types are
    * self type has to be WF
    * but it doesn't have to be *constructed*
* https://github.com/rust-lang/rust/blob/8b954910c59a7a362c60959e93110892b6e9a691/compiler/rustc_typeck/src/check/fn_ctxt/checks.rs#L39-L47
* https://github.com/rust-lang/rust/blob/8b954910c59a7a362c60959e93110892b6e9a691/compiler/rustc_typeck/src/check/fn_ctxt/checks.rs#L112-L116
* when you call a function f with arguments of type A0...An:
    * we check that the expected types of those arguments E0...En are WF
* Why is #25860 unsound?
    * `T1 <: T2` does not imply `WF(T1) <=> WF(T2)` (or maybe vice versa)
    * `Normalize(T) => U` does not imply `WF(T)` and `WF(U)` have entailment relationship
* 

## 2021-11-22

### Thoughts on associated types, implied bounds

```rust
trait Foo {
    type method<'me>: Trait;
    fn method(&'me self) -> Self::Trait<'me>;
}
```

Effect on inference?

* We only do the inference when the GAT is a return type
* Iterated inference

```rust
trait Foo {
    // what type do we introduce now?
    fn method(&self) -> (impl Debug, impl Debug);
}
```

```rust
trait LendingIterable {
    type Item<'me>;
    type Iter<'me>: Iterator<Item = Self::Item<'me>> + 'me;
    
    fn iter(&self) -> Self::Iter<'_>;
}

trait LendingIterable {
    type Item<'me>;
    fn iter(&self) -> impl Iterator<Item = Self::Item<'_>> + '_;
}

trait LendingIterable {
    final type Item<'me> = Self::iter<'me>::Item;
    fn iter(&self) -> impl Iterator + '_;
}
```

```rust
trait LendingIterable {
    final type Item<'me> = Self::iter<'me>::Item
    where
        Self: 'me;
    
    fn iter(&self) -> impl Iterator + '_;
}
```


```rust
type Item<Self, 'me> = impl Sized + 'me;
// use it in such a way that Self: 'me was required
// --> results in an error
```

```rust
trait WellFormed { }
impl<T: ?Sized> WellFormed for T { }


    final type Item<'me> = Self::iter<'me>::Item
    where
        Self::iter<'me>::Item: std::marker::WellFormed;

```


---


```rust
trait WellFormed { }
impl<T: ?Sized> WellFormed for T { }

// input from user:
trait LendingIterable {
    final type Item<'me> = Self::iter<'me>::Item;
    fn iter(&self) -> impl Iterator + '_;
}

// desugars to:
trait LendingIterable {
    final type Item<'me> = Self::iter<'me>::Item
    where
        Self: 'me; // <-- user will have to add this

    final type Item<'me>
    where
        Self: 'me // <-- user will have to add this
    = Self::iter<'me>::Item; 

    type iter<'me>: Iterator + '_
    where
        &'me Self: std::marker::WellFormed,
        A1: WellFormed,
        ...,  
        An: WellFormed;
    
    fn iter(&self, ...) -> impl Iterator + '_;
}
```

---

* introduce a type alias for the method's return type
    * xxx what about impl trait that is not at the root?
    * for that type alias, we add `where T: WellFormed`
* add a `std::marker::WellFormed` trait
* add `final` in traits
    * show how this will be useful for specialization
    * in an impl:
        * things are `final` by default
        * can be declared `default`
    * in a trait
        * things are `default` by default
        * can be declared `final`
* you will have to write `where Self: 'me` in the trait definition
* Unrelated, but:
    * Niko thinks we should support
        * `type Foo: Iterator` at the module level too :) 

### 

https://github.com/rust-lang/rust/issues/90573

### Jack's thing

- Try to normalize associated types before processing obligations
  - [#90887](https://github.com/rust-lang/rust/pull/90887)
- Two obligations O1 and O2 that feature a projection with an inference variable
    - In O2 we find a type for the inference variable
    - But when we go back to try and prove O1 we don't try to normalize again using the knowledge of the inference variable


## 2021-11-15

### Where the where

* jack: In a vacuum, changing the where clauses on GATs is the right decision
    * but for consts and functions...it feels more awkward
    * expressions can get long in consts
    * overall I feel on the fence
* maybe consult about how to drive this in a more data-oriented way
 
### Outlives lint

* no changes since last week
* Bug?: https://github.com/rust-lang/rust/issues/90808
```rust
#![feature(generic_associated_types)]

trait MyTrait {
    type AT<'a>;
}

struct Outer<'a, T>(&'a T);
impl<'a, T: MyTrait> MyTrait for Outer<'a, T> {
    type AT<'b> = T::AT<'b>; // Switching this to T::AT<'a> works
}

trait Ops<T> {
}

fn g<'this, O, T>(x: &'this O)
where
    O: MyTrait,
    T: Ops<O::AT<'this>>, // Commenting this line makes this compile
{}

fn f<'this, I, T>(x: &'this I)
where
    I: MyTrait,
    T: Ops<I::AT<'this>>
{
    let outer = Outer(x);
    g::<_, T>(&outer); // Should this be allowed?
}
```

https://github.com/vandenheuvel/relp/commit/aa471b3272cb53f8f497217585f89599cc9343c3

https://github.com/rust-lang/rust/issues/90713


https://github.com/rust-lang/rust/pull/90887

Niko's question:

* Where did this `F: 'static` come from ([code](https://github.com/vandenheuvel/relp/blob/aa471b3272cb53f8f497217585f89599cc9343c3/src/algorithm/two_phase/matrix_provider/matrix_data.rs#L281-L288))?
* Guess:
    * error from not being WF led to it being included

## 2021-11-08

* Planned
    * Where the where
        * FCP didn't get picked up
        * Centril's proposal to abbreviate `fn foo() { result }` to `fn foo() = result;`
        * Some [concerns](https://github.com/rust-lang/rust/issues/89122#issuecomment-962619847) about rustfmt
    * Outlives lint
        * What rule to apply when GAT appears in bounds of another GAT? See [test](https://github.com/rust-lang/rust/pull/89970/files#diff-75725c2c489f166d10b6f2d5d922249e1d3e5d318db9bcf6a89fee50616f4e4cR141)
        * What clause do we want when lifetime in trait? see [test](https://github.com/rust-lang/rust/pull/89970/files#diff-75725c2c489f166d10b6f2d5d922249e1d3e5d318db9bcf6a89fee50616f4e4cR113)

## what rule to apply...

* we definitely want this
* we wanted fixed point
* the algorithm is roughly like so
* For a trait T

```
required bounds is a set (TypeName<'a> where WC...)
required_bounds = {}
loop {
    required_bounds1 = infinity
    for each item in the trait
        required_bounds1 = required_bounds1 intersect required(required_bounds, item)
    if required_bounds != required_bounds1 {
        required_bounds = required_bounds1;
    } else {
        break;
    }
}

required(_, fn() -> T) =
    search return type T for appearances of GAT

required(b, type Foo<..>: Bounds) =
    * as today but where we search Bounds for appearances
    * include b in the environment
```

### question: why limit ourselves to return type?

can we come up with a realistic example?

```rust
trait Searchable {
    type Item<'a>;
    fn contains<'a>(&'a self, item: Self::Item<'a>);
}
```

## where the where examples

```rust
const Foo<T>: Type = value
where T: Bar;

const Foo<T>: Type = match {
    
} where T: Bar;

fn foo<T>() -> Type = value
where T: Bar;

fn foo<T>() -> Type
where T: Bar;


fn foo<T, U>() -> Type
where
    T: Bar,
    U: Baz,
{
    match {
        ...
    }
}

fn foo<T, U>() -> Type
where
    T: Bar,
    U: Baz,
= match {
    ...
}

fn foo<T: Bar, U: Baz>(
) -> Type = match {
    ...
}
```

## 2021-10-23

* Planned topics
    * Open PRs
        * [#89970](https://github.com/rust-lang/rust/pull/89970)
        * [#90017](https://github.com/rust-lang/rust/pull/90017)
        * [#90076](https://github.com/rust-lang/rust/pull/90076)
        * [#88441](https://github.com/rust-lang/rust/pull/88441)
    * Needs comment
        * [#87735]
    * 2 blocking issues for GATs (outlives & where)
        * [#89352](https://github.com/rust-lang/rust/issues/89352) "untriaged", but probably not blocking
    * [#90076]
        * Change to `Generics` + `usize`
    * [#89970]
        * Add a link in error message to initiative

### case niko is talking about

```
impl<A, B> Foo for A
whereu
}
```

## 2021-10-18

* PR: [#89970](https://github.com/rust-lang/rust/pull/89970)
    * Implemented using the lexical checker, but works
* Interaction of impl trait and GATs?
    * [play](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=9942a411c5d63023a7f0e7523bc86b81)
* Danger of this setup
    * If the compiler gets smarter, and is better able to prove outlives bounds, then it can be a breaking change
        * more things need to be declared
        * in the future, more defaults, which are *less* of a breaking change
    * Generally something we try to avoid
* Along those lines:
    * normalization
    * semi-cyclic reasoning
        * the where clauses we are inferring influence the "wf" condition
        * if we have implied bounds...
            * the implied bounds of the GAT might be its where clauses
            * and we are inferring those where clauses with implied bounds in scope
    * what this argues:
        * we can move forward but using an error is a good setup
        * more comfortable making this a default once we've moved to chalk
* Possibilities
    * Normalized type has *fewer* than the unnormalized type
        * `()`
    * Can it have *more*?
        * Argument: No
            * The WF requirements of the value of an associated type must be implied by the where clauses on the impl
            * So if we can successfully normalize, we must know those where clauses hold in some other way

```rust
trait Ref1<'a> {
    type T;
}

impl<'a, T> Ref1<'a> for T {
    type T = &'a T;
} 

trait Ref2 {
    type T<'a> /* where Self: 'a inferred, in principle */ ;
    
    fn blah(&self) -> Self::T<'_>;
}

impl<T> Ref2 for T {
    type T<'a> = &'a T;
} 
```

```rust
trait Foo {
    type Iter<'a>;
    
    fn foo(s: <Self as Ref2>::T<'a>) -> Self::Iter<'a>;
    // normalized: `s: &'a Self'
}

```

```rust
trait Foo {
    type Iter<'a>;
    
    fn foo(&self, x: ) -> Self::Iter<'a>;
}

trait Ref<'a, T>
where T: 'a
{
    type T = &'a u32;
} 
```


### Where the where clauses are

a la "Where the wild things are"

Not such a trivial change. When we are parsing (and lowering), we don't keep track of whether it's an associated type or a top-level type alias. Need to stay backwards compatibility.

Kind of annoying. Probably want to parse both and append them together in HIR lowering and then report errors in AST validation.

### Normalize closure

https://github.com/rust-lang/rust/pull/88441

in this logic:

https://github.com/rust-lang/rust/blob/5dab47dcd8267b8769421b46532414ec36d625e3/compiler/rustc_trait_selection/src/traits/project.rs#L476-L483

* if `normalized_ty` is an inference variable
* that was introduced by the projection code
* and will eventually be inferred to a placeholder `'a` representing one of the higher ranked regions in question
* *then* that placeholder will not be replaced

we thought that was not possible but we were wrong:

```rust
trait Foo {
    type Output;
}

trait Bar {
    type Output;
}

impl<A, B> Bar for A
where
    A: Foo<Output = B>,
{
    type Output = B;
}

impl<T> Foo for T {
    type Output = T;
}
```

Scenario:

* Normalizing `for<'a> <&'a u32 as Bar>::Output`
    * expected result: `for<'a> &'a u32`

what we wind up doing today:

* replace `B` with `?B` and generate a obligation
    * `A: Foo<Output = ?B>`
* result is `?B` with:
    * `&'!a u32: Foo<Output = ?B>`
* once we're done proving everything we have `?B = &'!a u32`

conclusion:

* orthogonal issue with various ways to fix
* investigate to see why NLL works but we can conceivably land and 
    * file a follow-up bug for this issue

## 2021-10-11

### Proposed defaulting algorithm

* Given a GAT `<P0 as Trait<P1..Pi>>::G<Pi...Pn>` declared as `trait T<A1..Ai> for A0 { type G<Ai...An>; }` used in return type of one associated function `F`
* Given env `E` (including implied bounds) for `F`
* For each lifetime parameter `'a` in `P0...Pn`:
    * For each other parameter `Pi != 'a` in `P0...Pn`:
        * If `E => (P: 'a)`:
            * Require where clause `Ai: 'a`

### Example A

```rust
trait Iterable {
    type Iter<'x>;
    
    fn iter<'me>(&'me self) -> Self::Iter<'me>;
    // Requires: Self: 'x
}
```

### Example B

```rust
trait Des3 {
    type Out<'x, D>;
    fn des<'z, T>(&self, data: &'z T) -> Self::Out<'z, T>;
    // Requires: D: 'x
}
```

### Example C

```rust
trait Des3 {
    type Out<'x, D>;
    fn des<'z, B: Deref<Target = A>, A>(&self, data: &'z B) -> Self::Out<'z, A>;
    // Requires: (nothing)
    //
    // but if we extend Deref with an "implied bound" of `for<'a> (Self: 'a => Self::Target: 'a)`
    // then it would require `D: 'x`
}
```

### Example D

```rust
trait Deserializer<T> {
    type Out<'x>;
    fn deserialize<'a>(&self, input: &'a T) -> Self::Out<'a>;
    
    // short for:
    fn deserialize<'a>(&self, input: &'a T) -> <Self as Deserializer<T>>::Out<'a>;
    // Requires `T: x`
}
impl<T> Deserializer<T> for () {
    type Out<'a> = &'a T;
    fn deserialize<'a>(&self, input: &'a T) -> Self::Out<'a> { input }
}
```

### Example E

```rust
trait Trait<T> {
    type Out<'a>;
    fn make<'a>(&self, input: &'a Vec<T>) -> Self::Out<'a>;
}
```

### Implementation strategy

* Add a new query that constructs the borrow check / type check data structures
    * gives them their implied bounds
    * tries to prove `Generic: 'a`
    * and reports back provable or not provable
    * https://github.com/rust-lang/rust/blob/86d6d2b7389fe1b339402c1798edae8b695fc9ef/compiler/rustc_borrowck/src/type_check/mod.rs#L126-L139
    * https://github.com/rust-lang/rust/blob/86d6d2b7389fe1b339402c1798edae8b695fc9ef/compiler/rustc_borrowck/src/type_check/mod.rs#L154-L164

## 2021-10-04

* This week:
    * Niko
        * Friday: outlives default inference
        * Dig further into #88441
    * Jack
* What blocks stabilization?
    * Default inference
    * Where clause syntax
        * Have to resolve questions about trait aliases
    * Explainer
    * Bugs and test case coverage
    * Triage and label
        * GATs-triaged
        * GATs-blocker-1
* What can we do to increase confidence?
    * Modeling specific use cases?
    * The graph iterator thing, port to use GATs
    * Async fns in traits
        * procedural macro that desugars
        * https://crates.io/crates/real-async-trait
* Notes
    * Nearly all bugs labeled GATs are "things we can't readily fix that arise more with GATs"
        * e.g. changes are early to late bound
        * something something overflow
        * 
* Pending issues
    * #89242
        * Where we start to have problems: https://github.com/rust-lang/rust/blob/a4797664ba9c7d71e586122853858eeb6c153bb9/compiler/rustc_typeck/src/check/callee.rs#L85
        * Confusing things
    * #89196
        * Not a regression
        * 

## 2021-09-20

* Niko this week:
    * Investigate #88441, why does this behave differently with NLL?
    * Open an issue about changing the syntax (which repo?)
* Digression about member constraints
    * Does falling back to static create a backwards incompatibility?
        * Niko's argument: no
            * The restriction comes late in type checking
            * Can influence borrow checking but
                * if the region comes from a borrow, that's an error either way
                * if the region comes from a reference, there is an upper bound (and hence PR doesn't apply)
                    * unless it comes from a static reference, in which case it's a fine choice
        * Crater run
* #88441
    * Did we always need a normalization here?
        * Jack thinks yes
    * Issue 62529-1 output changes
        * We are now able to infer a type successfully, no longer get a type mismatch
    * Issue 70120
        * Got an error before, but no longer do
    * Gets us closer to #88382
    * Branch: https://github.com/jackh726/rust/tree/issue-88459
        * Minimized issue: `src/test/ui/generic-associated-types/issue-88459-2.rs`
        * Log: https://gist.github.com/jackh726/a5e6c62dd1e76a28ab9491aa5d4e5079
        * [Debugging session](https://pernos.co/debug/aXf8Fomk39i3jbzQrsAsDQ/index.html#f{m[Xpo,AA_,t[AQ,FeUG_,f{e[Xpk,WA___/)

### Issue 88382

```rust
#![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>) {}
```


## 2021-09-13

* Normalize obligation for closure confirmation:
    * https://github.com/rust-lang/rust/pull/88441
* Recursive issue
    * https://github.com/rust-lang/rust/issues/87755
* This compiles
    * https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cd0d44d930eead0c705d6eeeafa22be7
    * not gat blocking
* Changes to default decision
    * move the ruled out options away
    * add example of `Iter<'static>`
    * add "opt-out" discussion, with `where` as the opt-out?
* Where clause syntax
    * Open an issue and start an FCP for T-lang to change the syntax
    * Type aliases -- keep it unstable until they have the desired semantics
* chalk-ty
    * problem is that we are no longer variant over the lifetime
    * but we have `'static` stuff that we try to use
* how to handle variance and subtyping?
    * can we do field-by-field comparisons?
    * two ways to fix
        * change how we handle variance, assoc types in some way
        * add a lifetime to the interner trait
* closure normalization issue
    * 

## 2021-08-30

* New PR [#88441]
* New bug related to #85499: [#88446]
* Starting looking at [#87755]
    * Don't know if there's anything to discuss; haven't actually done much


[#88441]: https://github.com/rust-lang/rust/pull/88441
[#88446]: https://github.com/rust-lang/rust/pull/88446
[#87755]: https://github.com/rust-lang/rust/pull/87755

## 2021-08-23

* Last week
    * PR [#87900]
        * Removed special case for adding the predicate into the environment
        * Works except for `default` and default associated types in traits

```rust
trait Family {
    type Member<C: Eq>;
}

impl Family for VecFamily {
    type Member<C: Eq> = i32;
}

// would generate a clause like

forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) } 

// which is wrong, we want

forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) :- Implemented(C: Eq) } 
```

Hypothesis:

Although the first clause can be used with types `C` that do not implement `Eq`, for it to cause some kind of problem, there would have to be a `VecFamily::Member<X>` for some type `X` where `!(X: Eq)`, that appears in the value of `type Member<C: Eq> = ...`. That type would fail a well-formedness check that we ought to be doing elsewhere, which would check that any `<T as Family>::Member<X>` meets the bounds declared in the trait (notably, that `X: Eq` and `T: Family`).



```rust
trait Family {
    type Member<C: Eq>: MyBound<C>;
}

trait MyBound<C> { }
impl<C: Eq> MyBound<C> for i32 { }

impl Family for VecFamily {
    type Member<C: Eq> = i32;
}


// would generate a clause like

forall<X> { Normalize(<VecFamily as Family>::Member<X> => i32) } 

// Environment like
// a. !C: Eq
// b. forall<X> { Normalize(<VecFamily as Family>::Member<X> => i32) }
// where !C = TyParam(C)

// Goal is to prove
//
// `i32: MyBound<!C>`
//
// will instantiate rule b with X = !C
```

### Categorizing our work

* https://rust-lang.github.io/wg-async-foundations/vision/roadmap/async_fn/async_fn_fundamentals.html
* This work needs to be retconn'd into an initiative
* Niko to setup a repo and so forth

### And now for something completely different

![gif](https://i.kym-cdn.com/photos/images/original/002/029/078/77f.gif)

https://github.com/rust-lang/rust/pull/88149#issuecomment-902268188

### #87735

https://github.com/rust-lang/rust/issues/87735

* https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=ca7c842d7fb8005e51d161f4553ccfae
* non-GATs: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=17d005614ab38b7b20280bbc6f8077b8

* conclusion:
    * orthogonal-ish, needs an extension for implied bounds or other improved reasoning, blocked on chalk progress
* two problems at play:
* what we would need to do for this to work:



### This week, goals

* Jack:
    * [x] Jack to add above as comment into #87900 with test
* Niko:
    * [x] Review https://github.com/rust-lang/rust/pull/85499
    * [x] Review #87900 once comment is added and r+
    * [x] Retconn GATs Ahoy into an initiative
    * [ ] Write a comment for #87735

[#87900]: https://github.com/rust-lang/rust/pull/87900
[#87735]: https://github.com/rust-lang/rust/issues/87735

## 2021-08-16

Updating Niko on recent events:

* Blog post went live (:tada:)
    * Folks were excited, as expected ([reddit thread](https://old.reddit.com/r/rust/comments/ox9re0/the_push_for_gats_stabilization/))
        * ["holy shit it's happening"](https://old.reddit.com/r/rust/comments/ox9re0/the_push_for_gats_stabilization/h7lb89i/)
* Some issues and PRs to discuss
    * 8 reported issues
        * some overflow issues
        * one that will get fixed with the "normalize under binders" PR
        * sized coinductiveness related issue
        * early vs late bound:
            * because the GAT is not normalized, you get early bound
        * some "actual" GAT issues
* Pending PRs
    * normalize under binders PRs
        * https://github.com/rust-lang/rust/pull/85499
    * Use bound vars for GAT params in param_env in check_type_bounds
        * https://github.com/rust-lang/rust/pull/87900
        * Currently, because of specialization, we are generating predicates like
            * `<P0 as Trait<P1..Pn>>::Foo --normalizes-to--> U` when we have `type Foo = U` in the impl (regardless of whether it is default or not)
                * it is needed when `default type Foo = U`
                * Niko's contention: it is not needed when not default, because the program clause from the impl applies
        * Problem occurs when extending to GATs
            * In the example from #87429
            * We currently generate (on master)
                * `<I32 as Family>::Member<'a> --> i32` where `'a` is the early-bound region (which will act as a placeholder when present in the param env)
            * Then we try to prove `<I32 as Family>::Member<'a>: for<'b> PartialEq<<I32 as Family>::Member<'b>>`
                * this obligation comes from the trait, which declares `type Member<'a>: for<'b> PartialEq<Self::Member<'b>>`
            * There are two normalizations required here:
                * `<I32 as Family>::Member<'a>` matches the inserted predicate exactly, so we get `i32` and everything is fine
                * create a placeholder `!b` and try to normalize `<I32 as Family>::Member<!b>`
                    * here we apply the `ParamEnv` rule ("because we are dumb")
                    * `!b = 'a` 
                    * and this is not possible, so we wind up with some sort of error somewhere along the line
            * If we did not add to the param env at all:
                * we would find the impl, replace all early-bound regions with fresh inference variables
                    * `<I32 as Family>::Member<?a> = i32`, we would unify this with `...` and get `!b = ?a`, which is fine
                    * normalize to `i32` (which doesn't reference `!b`)
                    * we have to prove `i32: PartialEq<i32>`, which is true
        * Niko's proposed fix
            * If there is no default, do not modify the environment
            * If there is a default, and a GAT, report an error
                * open a FIXME to resolve this in the "post chalk glorious future"
        * The example is below

```rust
trait Family {
    type Member<C: Eq>;
}

impl Family for VecFamily {
    type Member<C: Eq> = i32;
}

// would generate a clause like

forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) } 

// which is wrong, we want

forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) :- Implemented(C: Eq) } 
```

can we make a test case where it actually goes wrong? not obvious.

## 2021-07-19

Busy weekend!

### New PRs

- Pretty placeholders: https://github.com/rust-lang/rust/pull/87246
- Diagnostics for implicit static mismatch: https://github.com/rust-lang/rust/pull/87244

### Blog post

Blog post: https://hackmd.io/FuAvMj4ITLmqmfio47ZF3Q

### What comes next?

* Some time getting feedback and making sure that everything is stable
* Three known issues that are relevant
    * "When there's an implicit static, diagnostics are bad" -- easier to hit with GATs -- PR #87244
    * Cycle that we hit with Sized bounds -- not a GATs issue, but it may be easier to hit with GATs
        * Easiest solution: make Sized coinductive
            * Note that that the induction is actually meaningful here, since we don't want infinite size
        * Link to issue [#80626](https://github.com/rust-lang/rust/issues/80626)
    * Last issue is [#81487](https://github.com/rust-lang/rust/issues/81487), discussed below
        * feels like a GATs bug
        * somehow related to region inference
* Stabilization report
    * Derive tests and check that they are contained
    * Set of patterns and expected uses that we expect to work
        * Iterable `trait Iterable { type Item; type Iter<'i> where Self: i; fn iter(&self) -> Self::Iter<'i> }`
        * GATs with futures
        * Something with type parameters
        * Test with const maybe?
    * Port the rustc-data-structures traits?
        * https://doc.rust-lang.org/nightly/nightly-rustc/rustc_data_structures/graph/trait.GraphSuccessors.html
        * https://doc.rust-lang.org/nightly/nightly-rustc/rustc_data_structures/graph/trait.WithPredecessors.html
* Extend the "normalize under binders" to all projections?
    * Regression in diesel-doc-bench probably top blocker
    * Query normalize is still getting passed escaping bound vars
        * If you do this more generally, it crops up when building docs
    * Perhaps a better approach
        * Figure out how many universes we need and treat it "as if" we had passed through the binder
        * This is a reasonable hack, but still a hack
            * e.g. if we extend `forall` to carry where clauses, it wouldn't work
    * May cause a perf regression

### Issue 81487

```rust
#![feature(generic_associated_types)]

struct IntRef<'a>(&'a mut i32);

trait Trait {
    type Ref<'a>;
}

impl Trait for () {
    type Ref<'a> = IntRef<'a>;
}

struct RefWrapper<'a, T: Trait>(&'a mut <T as Trait>::Ref<'a>);

fn wrap<'a, T: Trait>(the_ref: &'a mut T::Ref<'a>) -> RefWrapper<'a, T> {
    RefWrapper(the_ref)
}

fn main() {
    let mut x = 3;
    let mut int_ref = IntRef(&mut x);
    let wrapper = wrap::<()>(&mut int_ref);
    *wrapper.0.0 = 2;
}
```

Error:

```rust
error[E0309]: the associated type `<T as Trait>::Ref<'_>` may not live long enough
  --> x.rs:16:5
   |
16 |     RefWrapper(the_ref)
   |     ^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `<T as Trait>::Ref<'_>: 'a`...
   = note: ...so that the type `<T as Trait>::Ref<'_>` will meet its required lifetime bounds
```
Ending up with these bounds (in lexical region resolve):
```
AnyBound([
    AnyBound([
        IfEq(
            <T as Trait>::Ref<'a>,
            OutlivedBy(ReFree(DefId(0:13 ~ issue_81487[fb0e]::wrap), BrNamed(DefId(0:14 ~ issue_81487[fb0e]::wrap::'a), 'a)))
        ),
        IfEq(
            <T as Trait>::Ref<'a>,
            OutlivedBy(ReFree(DefId(0:13 ~ issue_81487[fb0e]::wrap), BrNamed(DefId(0:14 ~ issue_81487[fb0e]::wrap::'a), 'a)))
        )
    ]),
    AllBounds([OutlivedBy('_#0r), AnyBound([OutlivedBy(ReEmpty(U0))])])
])
```
but our actual type
`<T as Trait>::Ref<?0>`

Member constraints:
```
DEBUG rustc_infer::infer::lexical_region_resolve Constraint 0 => VarSubVar('_#0r, '_#0r)
DEBUG rustc_infer::infer::lexical_region_resolve Constraint 1 => RegSubVar(ReFree(DefId(0:13 ~ issue_81487[fb0e]::wrap), BrNamed(DefId(0:14 ~ issue_81487[fb0e]::wrap::'a), 'a)), '_#0r)
DEBUG rustc_infer::infer::lexical_region_resolve Constraint 2 => VarSubReg('_#0r, ReFree(DefId(0:13 ~ issue_81487[fb0e]::wrap), BrNamed(DefId(0:14 ~ issue_81487[fb0e]::wrap::'a), 'a)))
```

Gist: https://gist.github.com/jackh726/92f92384bd5e878ca9741169779849fb

* Sounds like we're missing an implied bound
* Niko had a misconception
    * `&'a T::Foo` in the arguments
        * tells you that `T::Foo: 'a` can be implied
        * it does not tell yo that `T: 'a` is true
        * although, if you *did* know that `T: 'a` were true, then you would also know that `T::Foo: 'a`
    * given `T::Ref<'x>`...
        * if `'x == 'a` then `T::Ref<'x>: 'a` can be assumed
        * we are not inferring `'x` to `'a`
    * might be related to member constraints

### Branching out from GATs (uh-oh)

* lcnr had a different approach in #84944 that moves some of the "dedup" code to project
    * Revert save subobligations that had gone through crater
        * got closed, found regressions
    * changing where it got done
    * leads to a big perf improvement
    * interacts, maybe ask Aaron1011 to do a first review
* Charles Lew's PR on vtables #86461 needs review
    * niko should review, added test attribute which looks great
* ty-interner PR #86435 (LeSeulArtichaut)
    * kind of stuck in some lifetime errors, maybe the variance changed?
    * needs detailed examination

## 2021-07-12

### Discussing the PR to do normalization

https://github.com/rust-lang/rust/pull/86993

* Perf results are a bit of a mystery, but the result is common between this PR and the other one
* Separate out the changes to the WF


```
Normalize(<P0 as Foo>::Trait<P1..>) = ?T

for<'a> fn(<P0 as Foo>::Trait<'a>)
* if this is normalized to a variable, we are "screwed"
```

* when would we actually return an inference variable
    * *and in particular* a variable that does not appear in the input
* the PR uses `opt_normalize_projection_type`, not `normalize_projection_type`
    * looking at `project_type`
        * `impl<A> Foo for ... { type Assoc = A; }`
        * hopefully the builtin rules follow a similar logic
        * proof by contradiction: 
            * it would be unsound for associated type to have an unbound variable because the value of an associated type is supposed to be a pure function of its inputs
            * and other parts of the type system assume that to be true
    * this value gets returned to `AssocTypeNormalizer`
        * true by inductive hypothesis
    * in the case of *trait selection error*
        * we create a new variable and return it
* the PR 
* what we want to avoid:
    * that a late-bound variable appears in the output but is hidden under some inference variable whose value is not yet known
    * why?
        * `literate_late_bound_regions` currently just ignores inference variables, on the premise that they cannot name a late-bound region
* PR one:
    * well-formedness logic is in the wrong order
        * does this regress performance??
    * in the case of error, return the original type, not a fresh inference variable
        * do we really this? it's independent
        * [existing logic](https://github.com/rust-lang/rust/blob/c63f1fe92b99a9828e9f999355213b0b73175aa0/compiler/rustc_trait_selection/src/traits/project.rs#L969-L990) (return an unbound inference variable) is already unsound
* layout code and bound variables
    * `struct Foo { x: <fn(&u32) as Foo>::Bar }`

```rust=
impl Foo for fn(&u32) {
    type Bar = i32;
}

impl<'a> Foo for fn(&'a u32) {
    type Bar = u32;
}
```
