go/types, cmd/compile: "invalid type loop" depending on declaration order

[mdempsky]

types2 currently rejects the test case below with "invalid recursive type A". Swapping the order of declarations for A and B makes the error go away.

package p

type A interface{ M(B[T]) }
type B[_ A] struct{}

type T struct{}
func (T) M(B[T]) {}

/cc @findleyr @griesemer @ianlancetaylor

[findleyr]

Will investigate. I suspect that the fix in https://go.dev/cl/361922 may be incomplete.

[findleyr]

Ok, I looked into it and the fix from CL 361922 was indeed incomplete.

I have experimented with a couple solutions, and mailed one in https://go.dev/cl/386718. Reproducing the commit message here for discussion:

The check for invalid cycles through type parameter lists was too
coarse, resulting in inconsistent reporting of errors depending on
type-checking order.

Consider the following example:

  type A interface{ M(B[T]) }
  type B[_ A] struct{}

In this example, if we type-check A first, we will subsequently
type-check B, and encounter the cycle to A while inside the type
parameter list for B. However, if we type-check B first, we will
encounter the cycle to B while type checking the declaration of A (i.e.
not while inside a type parameter list). This means that our existing
heuristic for invalid cycles through type parameter lists depends on the
location of that type parameter list in the type-checking cycle.

As I understand it, we have two options to resolve this inconsistency:

1. Make the ambient type parameter list a global property of the
   type-checking pass, rather than scoped to the current object
   declaration (via types.environment). This would result in more
   invalid cycles.
2. Only raise an invalid cycle error if we are cycling back to the
   generic type that holds the current type parameter list. This would
   result in fewer invalid cycles, but still avoids the deadlock of
   [#49439](https://golang.org/issue/49439).

That CL implements option #2, which feels more correct but is also riskier. We should perhaps implement option #1 for 1.18 (if anything).

[gopherbot]

Change https://go.dev/cl/386718 mentions this issue: go/types: refine the check for invalid cycles through tparam lists

[findleyr]

@griesemer I think we decided not to fix this for 1.18, correct? Shall I move to the 1.19 milestone?

[griesemer]

Yes, I think pending CL may have subtle repercussions; any change in the cycle detection algorithm may have non-local effects. We decided to wait for 1.19 as this is not a release blocker.

Moving to 1.19.

[findleyr]

Just grooming issues, this may have fallen through the cracks.

@griesemer let's discuss whether to bump this to 1.20, or land a fix for 1.19.

[gopherbot]

This issue is currently labeled as early-in-cycle for Go 1.20. That time is now, so a friendly reminder to look at it again.

[findleyr]

@griesemer do we want to fix this for 1.20? I can revisit my CL.

[griesemer]

@findleyr We still have some time, so yes, let's see if we can address this.

[findleyr]

This was a complicated one, and we had higher priorities (even higher priority fixes to validType). I think we should aim for early-in-cycle 1.21 (but actually early, this time).

[gopherbot]

This issue is currently labeled as early-in-cycle for Go 1.21. That time is now, so a friendly reminder to look at it again.

[findleyr]

I thought about this more today, and while I think the fix in https://go.dev/cl/386718 is OK, I actually think we could go one step further: why can't we just allow cycles through constraints? If a cycle occurs through a constraint, that constraint is still well-defined, and we only need to verify instances that occur in the source, which is by definition a finite number of instances.

I think the guard was originally added to avoid infinite recursion, but we have since developed better mechanisms for this.

[findleyr]

Not happening for 1.21, but I think we know what to do. Should land this early in 1.22 cycle.

[gopherbot]

This issue is currently labeled as early-in-cycle for Go 1.22. That time is now, so a friendly reminder to look at it again.

[gopherbot]

This issue is currently labeled as early-in-cycle for Go 1.23. That time is now, so a friendly reminder to look at it again.

[gopherbot]

This issue is currently labeled as early-in-cycle for Go 1.24. That time is now, so a friendly reminder to look at it again.