Hang on overflowing evaluating the requirement with extra generic types

[sgdxbc]

First of all I would like to make apology ahead if this is a duplicated case. It's really hard to describe such abstract pattern and look for it from previous issues. At least it is reproducible on nightly.

I tried this code:

pub trait Helper<O> {
    type Type: InnerT;
}

pub struct InnerHelper;

impl<O: OuterT<A>, A> Helper<O> for InnerHelper {
    type Type = Inner;
}

pub struct Outer<U, H: Helper<Self>> {
    inner: H::Type,
}

pub struct Inner;

pub trait OuterT<A> {
    type Inner: InnerT;
}

pub trait InnerT {}

impl InnerT for Inner {}

impl<U, A, H: Helper<Self>> OuterT<A> for Outer<U, H> {
    type Inner = H::Type;
}

fn main() {
    let outer = Outer::<_, InnerHelper> { inner: Inner };
    fn foo(_: impl OuterT<()>) {}
    foo(outer)
}

I expected to see this happen: compile terminates.

Instead, this happened:

$ cargo +nightly check
    Checking neatworks v0.1.0 (/workspaces/neatworks.3)
error[E0207]: the type parameter `A` is not constrained by the impl trait, self type, or predicates
 --> src/main.rs:7:20
  |
7 | impl<O: OuterT<A>, A> Helper<O> for InnerHelper {
  |                    ^ unconstrained type parameter

    Building [                             ] 0/1: neatworks(bin) 

And it hangs here forever. The memory gradually goes high, not fast but eventually memory will be exhausted.

What's more worrying is that on stable channel, the rustc process is not exiting even after ctrl-c is pressed and the shell gets back to prompt (which makes it feels like exited). This is probably a general issue not relevant to this case.

Meta

rustc --version --verbose:

rustc 1.79.0 (129f3b996 2024-06-10)
binary: rustc
commit-hash: 129f3b9964af4d4a709d1383930ade12dfe7c081
commit-date: 2024-06-10
host: x86_64-unknown-linux-gnu
release: 1.79.0
LLVM version: 18.1.7

Also reproduced on nightly channel

rustc 1.81.0-nightly (aa1d4f682 2024-07-03)
binary: rustc
commit-hash: aa1d4f6826de006b02fed31a718ce4f674203721
commit-date: 2024-07-03
host: x86_64-unknown-linux-gnu
release: 1.81.0-nightly
LLVM version: 18.1.7

Backtrace

<backtrace>

Related minor issues.

Removing either A from trait OuterT<A> or U from Outer<U, _> makes the compilation terminates. If choose to remove A the compilation will fail with

error[E0275]: overflow evaluating the requirement `Outer<_, InnerHelper>: Sized`
  --> src/main.rs:30:17
   |
30 |     let outer = Outer::<_, InnerHelper> { inner: Inner };
   |                 ^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`neatworks`)

The help: line is not helpful here, as in this case the recursion is obviously infinite.

If further remove the O: OuterT bound on line 9 and fill the type placeholder on line 32 (e.g. Outer::<(), InnerHelper>, the code will compile, which is possibly unexpected since the Outer<U, _> struct still has an unused generic type U.

Notes. I have been playing with this seemingly weird Helper trait because in the original code Inner need to take Outer as an generic parameter, and Helper acts as a "type level function" to pass Self out of Outer. During case reduction the generic on Inner is reduced. Not sure whether the whole Helper can also be reduced away as well, a simple attempt did not succeed.

[theemathas]

Minimized:

pub trait Helper {
    type Type;
}

impl<O, U> Helper for O where Outer<U>: Helper {
    type Type = ();
}

pub struct Outer<U> {
    inner: <Self as Helper>::Type,
}

fn main() {
    let outer = Outer { inner: () };
}

[Noratrieb]

What's more worrying is that on stable channel, the rustc process is not exiting even after ctrl-c is pressed

i don't have a link but this was because rustc had a buggy ctrl c handle that only worked when CTFE was happening, which has been fixed since.

[veera-sivarajan]

Regression between rustc 1.77.0 and rustc 1.78.0.

@rustbot label -needs-triage +I-hang +T-compiler +A-traits +A-inference +regression-from-stable-to-stable

[GrigorenkoPV]

Fixed by next solver.

Regression in #121154 (cc @oli-obk)

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-medium