Repository: rust
Issue: compiler trait solver gets stuck (infinite loop or tail recursion?), related to GAT and associated type equality constraint
Labels: C-bug,I-hang,T-types,fixed-by-next-solver,A-GATs

I was playing with GAT and stomped upon this weird issue, and here's a reproducible example that I managed to reduced to:

```rust
trait Foo {
    type Gat<'a>;
}

trait Bar {
    type Ty: Foo
    where
        for<'a> <Self::Ty as Foo>::Gat<'a>: Assoc<Ty = ()>;
}

trait Assoc {
    type Ty;
}
```

some research and observations:

- it **WILL** affect the playground, tested both stable and nightly;
- after somel search of the issue tracker, I thought it might be dup of #132032, but I'm not sure;
- if move the `Ty :Foo` bound to `where` clause like the following, it will **NOT** hang:
  ```rust
  trait Bar {
      type Ty
      where
          Self::Ty: Foo,
          for<'a> <Self::Ty as Foo>::Gat<'a>: Assoc<Ty = ()>;
  }
  ```
- if the `Assoc` has not associated type constraint, it will **NOT** hang:
  ```rust
  trait Bar {
      type Ty: Foo
      where
          for<'a> <Self::Ty as Foo>::Gat<'a>: Assoc;
  }
  ```
- it does **NOT** matter what type I used for the associated type equality, as long I have something, it will hang. e.g. the following will **STILL** hang, **AFTER** output of `E0582`:
  ```rust
  trait Bar {
      type Ty: Foo
      where
          for<'a> <Self::Ty as Foo>::Gat<'a>: Assoc<Ty = &'a ()>;
  }
  ```
- this should not matter, but just to mention it, the `Assoc` trait in the reproducing example was `Iterator` in my original code where I encountered this problem

I expected to see this happen: the compiler either accept or reject the code;

Instead, this happened: the compiler never finish while using 100% of one of the CPU cores.

### Meta

`rustc --version --verbose`:
```
rustc 1.84.0-nightly (917a50a03 2024-11-15)
binary: rustc
commit-hash: 917a50a03931a9861c19a46f3e2a02a28f1da936
commit-date: 2024-11-15
host: x86_64-unknown-linux-gnu
release: 1.84.0-nightly
LLVM version: 19.1.3
```

--------

Backtrace:

the compiler didn't crash, no backtrace available

--------

<details><summary>RUSTC_LOG=debug</summary>

<p>

because the compilation never finish, the log is infinitely sized and repeating, and since the issue is reproducible, I'll only attach the lines where it starts to repeat:

```text
...
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=126, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=126, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !127_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=126)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=127, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=127, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !128_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=127)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !129_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=128)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !130_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=129)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), '^0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. })], def_id: DefId(0:10 ~ col[f450]::Assoc::Ty), .. }, Term::Ty(())), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !131_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=129)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), '^0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. })], def_id: DefId(0:10 ~ col[f450]::Assoc::Ty), .. }, Term::Ty(())), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !130_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=128)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !131_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=129)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), '^0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. })], def_id: DefId(0:10 ~ col[f450]::Assoc::Ty), .. }, Term::Ty(())), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !132_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=129)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=127, value=Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), '^0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. })], def_id: DefId(0:10 ~ col[f450]::Assoc::Ty), .. }, Term::Ty(())), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !129_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=127)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !130_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=128)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !131_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=129)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), '^0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. })], def_id: DefId(0:10 ~ col[f450]::Assoc::Ty), .. }, Term::Ty(())), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !132_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=129)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), '^0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. })], def_id: DefId(0:10 ~ col[f450]::Assoc::Ty), .. }, Term::Ty(())), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:7 ~ col[f450]::Bar::Ty), .. }), !131_0.Named(DefId(0:8 ~ col[f450]::Bar::Ty::'a), "'a")], def_id: DefId(0:4 ~ col[f450]::Foo::Gat), .. }, depth=128)
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=<<Self as Bar>::Ty as Foo>
rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=Binder { value: TraitPredicate(<<<Self as Bar>::Ty as Foo>::Gat<'a> as Assoc>, polarity:Positive), bound_vars: [Region(BrNamed(DefId(0:8 ~ col[f450]::Bar::Ty::'a), 'a))] }
...
```

</p>
</details>