Requirement machine internal error on simple recursive same-type requirement

[AnthonyLatsis]

Description

No response

Reproduction

struct S<X, Y> {
  func foo() where (X, Y) == X {}
}

error: cannot build rewrite system for generic signature; concrete nesting limit exceeded [requirement_machine_completion_failed]
  func foo() where (X, Y) == X {}
             ^
note: failed rewrite rule is τ_0_0.[concrete: ((((((((((((((((((((((((((((((τ_0_0, τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1), τ_0_1)] => τ_0_0 [requirement_machine_completion_rule]
  func foo() where (X, Y) == X {}

Expected behavior

A regular error about the requirement being recursive and unsatisfiable.

Environment

Swift version 5.11-dev (LLVM 13124099c3f0229, Swift 6d66211)
Target: x86_64-apple-darwin23.0.0

Additional information

No response

[Rajveer100]

@AnthonyLatsis
Could you provide some insight on this?

[AnthonyLatsis]

Another example:

struct S<T> {}
func foo<U>(_: U) where U == S<U> {}

[AnthonyLatsis]

@Rajveer100 I have not looked into this. If you are willing to give it a crack and are more or less familiar with how generics are modeled in the AST, I think a good starting point would be to (1) find the place where recursive_same_type_constraint is emitted, (2) come up with a similar example that—unlike the one above—triggers the emission, and (3) start a comparative analysis of the logic and code paths that both examples hit.

[Rajveer100]

I believe we just need a better diagnostic and omit printing the two errors that show up currently (probably limit it to debug print).

Regarding detecting the issue itself, do we need an alternative logic to detect such nesting by specifying certain conditions, or can we just consider the recursion limit and add the new error diagnostic which is already being done internally?

File: lib/AST/RequirementMachine/Diagnostics.cpp

assert(requirement.getKind() == RequirementKind::SameType ||
             requirement.getKind() == RequirementKind::Superclass);
// ...

[Rajveer100]

Currently the trigger point for this error is under InferredGenericSignatureRequest::evaluate where requirement_machine_completion_failed is called.

// Diagnose redundant requirements and conflicting requirements.
    if (attempt == 0) {
      machine->computeRequirementDiagnostics(errors, inverses, loc);
      diagnoseRequirementErrors(...)
// ...

Also, under diagnoseRequirementErrors, the recursive_same_type_constraint diagnosis isn't called at the moment.

From what I understand, right before the diagnosis is performed, internally an error is already handled, i.e, requirement_machine_completion_failed, hence we don't see the user friendly recursive call diagnostic.