go/types, types2: type inference should report a better error message #48619

eliben · 2021-09-24T22:31:06Z

What version of Go are you using (`go version`)?

$  gotip version
go version devel go1.18-fe8347b Fri Sep 24 10:51:48 2021 +0000 linux/amd64

What did you do?

Trying to compile this sample: https://go2goplay.golang.org/p/MAplKhfhuKs

What did you expect to see?

The sample is incomplete (I tried to minimize it), so I don't expect it to compile. At the very least, there are calls to functions that don't exist.

The code is also incorrect. In the signature of quickSort_gen_func, a, b should be int, not Elem. Fixing this, the compiler produces an expected error message instead of going into infinite recursion.

What did you see instead?

runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc0205e0318 stack=[0xc0205e0000, 0xc0405e0000]
fatal error: stack overflow

runtime stack:
runtime.throw(0x6aa2fc, 0xe)
	/usr/local/go-faketime/src/runtime/panic.go:1126 +0x74
runtime.newstack()
	/usr/local/go-faketime/src/runtime/stack.go:1069 +0x7de
runtime.morestack()
	/usr/local/go-faketime/src/runtime/asm_amd64.s:436 +0x8b

goroutine 1 [running]:
go/types.(*unifier).nifyEq(0xc00058a140, 0x6f32a0, 0xc0000105a0, 0x6f30e8, 0x817000, 0x0, 0x0)
	/usr/local/go-faketime/src/go/types/unify.go:197 +0xb8 fp=0xc0205e0328 sp=0xc0205e0320 pc=0x5a6c18
go/types.(*unifier).nify(0xc00058a140, 0x6f32a0, 0xc0000105a0, 0x6f30e8, 0x817000, 0x0, 0x0)
	/usr/local/go-faketime/src/go/types/unify.go:238 +0x10f6 fp=0xc0205e0488 sp=0xc0205e0328 pc=0x5a7d16
go/types.(*unifier).nifyEq(0xc00058a140, 0x6f32a0, 0xc0000105a0, 0x6f30e8, 0x817000, 0x0, 0x0)
	/usr/local/go-faketime/src/go/types/unify.go:198 +0x70 fp=0xc0205e04d0 sp=0xc0205e0488 pc=0x5a6bd0
go/types.(*unifier).nify(0xc00058a140, 0x6f32a0, 0xc0000105a0, 0x6f30e8, 0x817000, 0x0, 0x0)
	/usr/local/go-faketime/src/go/types/unify.go:238 +0x10f6 fp=0xc0205e0630 sp=0xc0205e04d0 pc=0x5a7d16
...
<SNIP>

The text was updated successfully, but these errors were encountered:

griesemer · 2021-09-25T00:04:00Z

Smaller reproducer:

package p

func f[P any](a, _ P) {
	f(a, int(0))
}

Compiling leads to an infinite recursion in type inference.

gopherbot · 2021-09-28T21:36:16Z

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

gopherbot · 2021-09-29T03:47:06Z

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

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 · 2021-10-07T23:50:29Z

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

griesemer · 2021-10-08T00:07:50Z

The previous fix attempt was incorrect. Re-opening.

…"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>

cherrymui · 2021-12-15T19:01:55Z

Any update on this? Thanks.
(checking in as this is a release blocker.)

findleyr · 2021-12-20T14:10:31Z

I de-duped #50273 to this issue. Once this is fixed we should confirm that it also resolves the repro there.

gopherbot · 2022-01-12T05:08:52Z

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

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 · 2022-01-12T19:05:32Z

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

Due to golang/go#48619, constraints of quickSortOrdered and its related functions are not changed. So cast S to []E for now.

Like what we done in exp/maps, exp/slices would be better to accept a type whose underlying type is slice. Due to golang/go#48619, constraints of quickSortOrdered and its related functions are not changed. So cast S to []E for now.

gopherbot · 2022-01-27T09:31:09Z

Change https://golang.org/cl/381274 mentions this issue: slices: relax the constraints to type whose underlying type is slice

griesemer · 2022-02-01T17:50:07Z

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

gopherbot · 2022-02-13T21:45:20Z

Change https://go.dev/cl/385494 mentions this issue: go/types, types2: avoid infinitely recursive instantiation

Type inference uses type parameter pointer identity to keep track of the correspondence between type parameters and type arguments. However, this technique can misidentify type parameters that are used in explicit type arguments or function arguments, as in the recursive instantiation below: func f[P *Q, Q any](p P, q Q) { f[P] } In this example, the fact that the P used in the instantation f[P] has the same pointer identity as the P we are trying to solve for via unification is coincidental: there is nothing special about recursive calls that should cause them to conflate the identity of type arguments with type parameters. To put it another way: any such self-recursive call is equivalent to a mutually recursive call, which does not run into any problems of type parameter identity. For example, the following code is equivalent to the code above. func f[P interface{*Q}, Q any](p P, q Q) { f2[P] } func f2[P interface{*Q}, Q any](p P, q Q) { f[P] } We can turn the first example into the second example by renaming type parameters in the original signature to give them a new identity. This CL does this for self-recursive instantiations. Fixes #51158 Fixes #48656 Updates #48619 Change-Id: I54fe37f2a79c9d98950cf6a3602335db2896dc24 Reviewed-on: https://go-review.googlesource.com/c/go/+/385494 Trust: Robert Findley <rfindley@google.com> Run-TryBot: Robert Findley <rfindley@google.com> Reviewed-by: Robert Griesemer <gri@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org>

griesemer · 2022-03-30T21:27:10Z

The type inference algorithm doesn't run into endless recursions anymore since 1.18, and for 1.19 we have disabled the catch-all in case of an infinite recursion and haven't seen any problems so far.

For the simple reproducer

package p

func f[P any](a, _ P) {
	f(a, int(0))
}

the error message is:

testdata/manual.go:4:7: type int of int(0) does not match inferred type P for P

which is exactly right (barring more information, the 2nd argument's type must be P) , and at the correct location.

There's nothing else to do here for now. Closing.

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>

eliben assigned griesemer Sep 24, 2021

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 25, 2021

griesemer added this to the Go1.18 milestone Sep 25, 2021

gopherbot removed the NeedsFix The path to resolution is known, but the work has not been done. label Sep 25, 2021

griesemer added NeedsFix The path to resolution is known, but the work has not been done. release-blocker labels Sep 25, 2021

gopherbot removed the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 25, 2021

findleyr mentioned this issue Sep 27, 2021

go/types, types2: correctly handle some recursive constraint type inference cases - don't bail out #48656

Closed

gopherbot closed this as completed in 435718e Sep 28, 2021

griesemer mentioned this issue Oct 7, 2021

cmd/compile, go/types: recursive type matching regression #48695

Closed

griesemer reopened this Oct 8, 2021

findleyr mentioned this issue Oct 21, 2021

cmd/compile: fuzzing triggers various crashes or internal compiler errors on tip #49019

Open

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

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

findleyr mentioned this issue Dec 20, 2021

go1.18b1: stack overflow #50273

Closed

seankhliao mentioned this issue Dec 20, 2021

Go1.18: runtime: goroutine stack exceeds 1000000000-byte limit with generic function #50275

Closed

bmizerany mentioned this issue Jan 9, 2022

go/types, types2: stack overflow results after naming type parameter after interface name. #50517

Closed

griesemer removed the release-blocker label Jan 12, 2022

griesemer changed the title ~~go/types, types2: stack overflow while type-checking generic code~~ go/types, types2: type inference should report a better error message Jan 12, 2022

thanm mentioned this issue Jan 25, 2022

Go compiler and runtime meeting notes #43930

Open

SilverRainZ added a commit to SilverRainZ/exp that referenced this issue Jan 27, 2022

slices: relax the constraints to type whose underlying type is slice

abb5c4f

Due to golang/go#48619, constraints of quickSortOrdered and its related functions are not changed. So cast S to []E for now.

SilverRainZ mentioned this issue Jan 27, 2022

slices: relax the constraints to type whose underlying type is slice golang/exp#27

Closed

griesemer modified the milestones: Go1.18, Go1.19 Feb 1, 2022

griesemer closed this as completed Mar 30, 2022

rsc unassigned griesemer Jun 23, 2022

golang locked and limited conversation to collaborators Jun 23, 2023

gopherbot added the FrozenDueToAge label Jun 23, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

go/types, types2: type inference should report a better error message #48619

go/types, types2: type inference should report a better error message #48619

eliben commented Sep 24, 2021 •

edited

griesemer commented Sep 25, 2021 •

edited

gopherbot commented Sep 28, 2021

gopherbot commented Sep 29, 2021

gopherbot commented Oct 7, 2021

griesemer commented Oct 8, 2021

cherrymui commented Dec 15, 2021

findleyr commented Dec 20, 2021

gopherbot commented Jan 12, 2022

griesemer commented Jan 12, 2022

gopherbot commented Jan 27, 2022

griesemer commented Feb 1, 2022

gopherbot commented Feb 13, 2022

griesemer commented Mar 30, 2022

go/types, types2: type inference should report a better error message #48619

go/types, types2: type inference should report a better error message #48619

Comments

eliben commented Sep 24, 2021 • edited

What version of Go are you using (go version)?

What did you do?

What did you expect to see?

What did you see instead?

griesemer commented Sep 25, 2021 • edited

gopherbot commented Sep 28, 2021

gopherbot commented Sep 29, 2021

gopherbot commented Oct 7, 2021

griesemer commented Oct 8, 2021

cherrymui commented Dec 15, 2021

findleyr commented Dec 20, 2021

gopherbot commented Jan 12, 2022

griesemer commented Jan 12, 2022

gopherbot commented Jan 27, 2022

griesemer commented Feb 1, 2022

gopherbot commented Feb 13, 2022

griesemer commented Mar 30, 2022

eliben commented Sep 24, 2021 •

edited

What version of Go are you using (`go version`)?

griesemer commented Sep 25, 2021 •

edited