Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
mdempsky opened this issue Feb 17, 2022 · 15 comments
Open
Assignees
Labels
early-in-cycle A change that should be done early in the 3 month dev cycle. NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@mdempsky
Copy link
Member

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

@mdempsky mdempsky added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 17, 2022
@mdempsky mdempsky added this to the Go1.18 milestone Feb 17, 2022
@findleyr findleyr self-assigned this Feb 17, 2022
@findleyr
Copy link
Contributor

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

@findleyr
Copy link
Contributor

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
Copy link

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

@findleyr
Copy link
Contributor

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

@griesemer
Copy link
Contributor

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.

@griesemer griesemer modified the milestones: Go1.18, Go1.19 Feb 28, 2022
@griesemer griesemer added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Feb 28, 2022
@findleyr
Copy link
Contributor

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.

@findleyr findleyr modified the milestones: Go1.19, Go1.20 Jun 23, 2022
@findleyr findleyr added the early-in-cycle A change that should be done early in the 3 month dev cycle. label Jun 23, 2022
@gopherbot
Copy link

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
Copy link
Contributor

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

@griesemer
Copy link
Contributor

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

@findleyr
Copy link
Contributor

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

@findleyr findleyr modified the milestones: Go1.20, Go1.21 Nov 17, 2022
@gopherbot
Copy link

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
Copy link
Contributor

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
Copy link
Contributor

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

@gopherbot
Copy link

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.

@findleyr findleyr modified the milestones: Go1.22, Go1.23 Nov 7, 2023
@gopherbot
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
early-in-cycle A change that should be done early in the 3 month dev cycle. NeedsFix The path to resolution is known, but the work has not been done.
Projects
Status: No status
Development

No branches or pull requests

4 participants