rust-lang / rust-lang/rust

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

Open
#134,370 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-GATs C-bug fixed-by-next-solver I-hang T-types
Dominant language
Rust
Stars
119k
Forks
16.1k
PR metrics pending

Description

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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by compiling the reduced GAT example with the reported nightly toolchain and confirm the non-terminating behavior. Trace the repeated rustc_trait_selection::traits::normalize::normalize_with_depth_to and project::project entries in the debug log, then compare the variants that do not hang; done means rustc terminates with an appropriate acceptance or diagnostic result.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.