compiler trait solver gets stuck (infinite loop or tail recursion?), related to GAT and associated type equality constraint

[nerditation]

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

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 rustc doesn't finish stuck at rustc_trait_selection::traits::normalize::normalize_with_depth_to #132032, but I'm not sure;
• if move the Ty :Foo bound to where clause like the following, it will NOT hang:

  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:

  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:

  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

---

RUSTC_LOG=debug

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:

...
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))] }
...

[lqd]

This should be fixed by the new solver

[nerditation]

This should be fixed by the new solver

indeed, I can confirm the compiler will not hang with -Znext-solver.

so, what should I do with this issue? I'm new here, should I close it, or should I leave it as is and the bot will take care of it?

[lqd]

We likely can leave it as is imho

[findepi]

This might be the same bug, but a different repro. Maybe useful as a test case?

trait Invocable {
    type Arg<'a>;
}

struct Holder<I>(I);
impl<I> Invocable for Holder<I>
where
    I: Fn(Self::Arg<'_>),
{
    type Arg<'a> = i32;
}

I checked that nightly with -Znext-solver bails out with "overflow evaluating the requirement" on this, instead of running endlessly.