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, types2: correctly handle some recursive constraint type inference cases - don't bail out #48656

Closed
findleyr opened this issue Sep 27, 2021 · 9 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@findleyr
Copy link
Contributor

Reminder issue: when type checking recursive function instances that use constraint type inference, we need to either succeed or produce a useful message. For example:

package p

func f[P interface{*Q}, Q any](p P, q Q) {
	_ = f[P]  // case 1
        _ = f[*P]  // case 2
}

Case 1 currently fails with stack overflow (see also #48619), and case 2 fails with a not-very-useful error message ("cannot infer P ([ ])").

CC @griesemer

@findleyr findleyr added this to the Go1.18 milestone Sep 27, 2021
@griesemer griesemer added NeedsFix The path to resolution is known, but the work has not been done. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Sep 27, 2021
@gopherbot gopherbot removed the NeedsFix The path to resolution is known, but the work has not been done. label Sep 27, 2021
@griesemer
Copy link
Contributor

Related: Sometimes we get fairly different error messages for different orders of parameters and arguments - i.e., the error depends on which type is inferred first. It would be good to be independent of that order.

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/352832 mentions this issue: cmd/compile/internal/types2: avoid infinite recursion in unification

gopherbot pushed a commit that referenced this issue Sep 28, 2021
If the type T inferred for a type parameter P is P itself (or a derived
type containing P), a subsequent unification step leads to infinite
recursion: at each encounter of P with the already inferred type T
(which is or contains P), P stands for that T and the recursive matching
process continues with T, which inevitably contains P again and recursion
never terminates.

This CL introduces a set of masks, one for each type parameter.
When a type parameter is encountered for which a type has already
been inferred, the type parameter is "masked" for the recursive
matching of the inferred type. Masking makes the type parameter
"invisible" such that it will be handled like any other type and
not unpacked further.

Fixes #48619.
For #48656.

Change-Id: Ic1d938322be51fd44323ea14f925303f58b27c97
Reviewed-on: https://go-review.googlesource.com/c/go/+/352832
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@gopherbot
Copy link
Contributor

Change https://golang.org/cl/353029 mentions this issue: go/types: avoid infinite recursion in unification

gopherbot pushed a commit that referenced this issue Sep 29, 2021
This is an almost clean port of CL 352832 from types2 to go/types:
The nest files and unify.go where copied verbatim; unify.go was
adjusted with correct package name, a slightly different comment
was restored to what it was. The test files got adjustments for
error position. infer.go got a missing _Todo error code.

For #48619.
For #48656.

Change-Id: Ia1a2d09e8bb37a85032b4b7e7c7a0b08e8c793a5
Reviewed-on: https://go-review.googlesource.com/c/go/+/353029
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@gopherbot
Copy link
Contributor

Change https://golang.org/cl/354690 mentions this issue: cmd/compile/internal/types2: fix unification (again)

gopherbot pushed a commit that referenced this issue Oct 8, 2021
…"fix"

The "fix" (CL 352832) for #48619 was incorrect and broke
the unification algorithm in some cases (e.g., #48695).

This CL reverts the changes made by CL 352832 to unify.go,
and comments out code in corresponding tests.

As a result, #48695 will be fixed, and we will re-open #48619.

Fixes #48695.
For #48619.
For #48656.

Change-Id: I91bc492062dbcc8dae7626f6b33f6dfabf48bcb8
Reviewed-on: https://go-review.googlesource.com/c/go/+/354690
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@griesemer griesemer added the okay-after-beta1 Used by release team to mark a release-blocker issue as okay to resolve either before or after beta1 label Nov 10, 2021
@findleyr findleyr removed their assignment Nov 18, 2021
@cherrymui cherrymui removed the okay-after-beta1 Used by release team to mark a release-blocker issue as okay to resolve either before or after beta1 label Dec 14, 2021
@cherrymui
Copy link
Member

Any update on this? Is there anything still need to be done after the CLs above? (The original example still falls into infinite recursion.) Thanks.
(checking in as this is a release blocker.)

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/377954 mentions this issue: go/types, types2: prevent unification from recursing endlessly

gopherbot pushed a commit that referenced this issue Jan 12, 2022
This is a stop gap solution to avoid panics due to stack overflow
during type unification. While this doesn't address the underlying
issues (for which we are still investigating the correct approach),
it prevents a panic during compilation and reports a (possibly not
quite correct) error message.

If the programs are correct in the first place, manually providing
the desired type arguments is a viable work-around, resulting in
code that will continue to work even when the issues here are fixed
satisfactorily.

For #48619.
For #48656.

Change-Id: I13bb14552b38b4170b5a1b820e3172d88ff656ec
Reviewed-on: https://go-review.googlesource.com/c/go/+/377954
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@griesemer
Copy link
Contributor

With the above CL this doesn't crash anymore. Still needs a proper fix but not a release blocker anymore.

@griesemer griesemer changed the title go/types, types2: handle recursive constraint type inference go/types, types2: correctly handle some recursive constraint type inference cases - don't bail out Feb 1, 2022
@griesemer
Copy link
Contributor

This reports an ok error message and doesn't crash anymore. Leaving for 1.19.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/385494 mentions this issue: go/types: prototype for eliminating recursive type parameters in

@dmitshur dmitshur 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 14, 2022
@dmitshur dmitshur modified the milestones: Go1.19, Go1.18 Feb 14, 2022
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
This is a stop gap solution to avoid panics due to stack overflow
during type unification. While this doesn't address the underlying
issues (for which we are still investigating the correct approach),
it prevents a panic during compilation and reports a (possibly not
quite correct) error message.

If the programs are correct in the first place, manually providing
the desired type arguments is a viable work-around, resulting in
code that will continue to work even when the issues here are fixed
satisfactorily.

For golang#48619.
For golang#48656.

Change-Id: I13bb14552b38b4170b5a1b820e3172d88ff656ec
Reviewed-on: https://go-review.googlesource.com/c/go/+/377954
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
@golang golang locked and limited conversation to collaborators Jun 23, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

5 participants