cmd/compile: infinite loop with recursive generic types

[Merovius]

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

$ go version
go version devel go1.20-3a41094107 Wed Nov 9 06:30:59 2022 +0000 linux/amd64

Does this issue reproduce with the latest release?

Yes. And on tip.

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/mero/.cache/go-build"
GOENV="/home/mero/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/mero/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/mero"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/mero/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/mero/go/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="devel go1.20-3a41094107 Wed Nov 9 06:30:59 2022 +0000"
GCCGO="/usr/bin/gccgo"
GOAMD64="v1"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/mero/tmp/x/go.mod"
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build1760935320=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Try to compile this program:

package main

type A[T any] interface {
	*T
}

type B[T any] interface {
	B[*T]
}

type C[T any, U B[U]] interface {
	*T
}

func main() {
}

What did you expect to see?

Something. Probably an error message, I assume this is somehow violating the rules against embedding type parameters or something.

What did you see instead?

The compiler hangs, eating CPU (one core and a bit), obviously in an endless loop of some kind.

[mknyszek]

CC @golang/compiler

[mknyszek]

Is this new in Go 1.20?

[mdempsky]

I think this is a go/types issue. /cc @griesemer @findleyr

Is this new in Go 1.20?

No, it repros on the playground in 1.18 and 1.19 too.

[findleyr]

The infinite recursion appears to be here:

go/types.(*typeWriter).typ(0xc0034ca770, {0x74b6a0, 0xc0003c16e0})
        /home/rfindley/src/go/src/go/types/typestring.go:172 +0x32b fp=0xc0032465d8 sp=0xc0032463f8 pc=0x5c6e2b

[findleyr]

More details: B is identified as invalid, but its underlying must not be marked as Typ[Invalid], allowing the type-checker to recurse while type-hashing.

--- FAIL: TestManual (0.00s)
    check_test.go:250: testdata/manual.go:17:2: invalid recursive type: B refers to itself
panic: here [recovered]
        panic: here [recovered]
        panic: here

goroutine 6 [running]:
testing.tRunner.func1.2({0x68ecc0, 0x74b7d8})
        /home/rfindley/src/go/src/testing/testing.go:1519 +0x24e
testing.tRunner.func1()
        /home/rfindley/src/go/src/testing/testing.go:1522 +0x39f
panic({0x68ecc0, 0x74b7d8})
        /home/rfindley/src/go/src/runtime/panic.go:884 +0x213
go/types.(*Checker).handleBailout(0xc00012c1e0, 0xc000167b60)
        /home/rfindley/src/go/src/go/types/check.go:299 +0x8b
panic({0x68ecc0, 0x74b7d8})
        /home/rfindley/src/go/src/runtime/panic.go:884 +0x213
go/types.(*typeWriter).typ(0xc000166910, {0x74de00, 0xc000063160})
        /home/rfindley/src/go/src/go/types/typestring.go:177 +0xe9b
go/types.(*typeWriter).typeList(0xc000166910?, {0xc000063170, 0x1, 0x1?})
        /home/rfindley/src/go/src/go/types/typestring.go:363 +0x47
go/types.(*Context).instanceHash(0xc00006c600, {0x74ddd8, 0xc00014abd0}, {0xc000063170, 0x1, 0x1})
        /home/rfindley/src/go/src/go/types/context.go:79 +0x134
go/types.(*Checker).instance(0x7f5674d6e108?, 0xc000063170?, {0x74ddd8?, 0xc00014abd0?}, {0xc000063170, 0x1, 0x1}, 0xc00014ae70, 0xc00006c600)
        /home/rfindley/src/go/src/go/types/instantiate.go:97 +0x269
go/types.(*subster).typ(0xc000166e98, {0x74ddd8?, 0xc00014ac40?})
        /home/rfindley/src/go/src/go/types/subst.go:261 +0x13aa
go/types.(*subster).typeList(0xc000063120?, {0xc000062f40?, 0x1, 0xc000166e90?})
        /home/rfindley/src/go/src/go/types/subst.go:363 +0xa5
go/types.(*subster).typ(0xc000166e98, {0x74dd88?, 0xc000079d60?})
        /home/rfindley/src/go/src/go/types/subst.go:168 +0x766
go/types.(*Checker).subst(0xc00012c1e0, 0x182, {0x74dd88?, 0xc000079d60}, 0xc00007bce0, 0xc00014ae70, 0xc00006c600)
        /home/rfindley/src/go/src/go/types/subst.go:78 +0x185
go/types.(*Named).expandUnderlying(0xc00014ae70)
        /home/rfindley/src/go/src/go/types/named.go:623 +0x41b
go/types.(*Named).resolve(0xc00014ae70)
        /home/rfindley/src/go/src/go/types/named.go:177 +0x185
go/types.(*Named).Underlying(0xd0?)
        /home/rfindley/src/go/src/go/types/named.go:456 +0x19
go/types.(*Named).under(0xc00014ae70)
        /home/rfindley/src/go/src/go/types/named.go:484 +0x36
go/types.under({0x74ddd8?, 0xc00014ae70?})
        /home/rfindley/src/go/src/go/types/type.go:23 +0x45
go/types.computeInterfaceTypeSet(0xc00012c1e0, 0xc00014ae00?, 0xc00016a0f0)
        /home/rfindley/src/go/src/go/types/typeset.go:273 +0x3f0
go/types.computeInterfaceTypeSet(0xc00012c1e0, 0xc00014ad20?, 0xc00016a050)
        /home/rfindley/src/go/src/go/types/typeset.go:277 +0x445
go/types.(*TypeParam).iface(0xc00007b4a0)
        /home/rfindley/src/go/src/go/types/typeparam.go:140 +0x1b2
go/types.(*TypeParam).Underlying(0x0?)
        /home/rfindley/src/go/src/go/types/typeparam.go:92 +0x19
go/types.under({0x74dec8?, 0xc00007b4a0?})
        /home/rfindley/src/go/src/go/types/type.go:25 +0x58
go/types.(*Checker).implements(0xc00012c1e0, {0x74dec8?, 0xc00007b4a0}, {0x74dd88?, 0xc000078a50}, 0x1, 0xc0001679e8)
        /home/rfindley/src/go/src/go/types/instantiate.go:193 +0x76
go/types.(*Checker).verify(0xc00014ad20?, 0x74e748?, {0xc000012130?, 0x1, 0x1?}, {0xc000062f80?, 0x1, 0xc00014ad20?}, 0xc00014acb0?)
        /home/rfindley/src/go/src/go/types/instantiate.go:179 +0x146
go/types.(*Checker).instantiatedType.func2()
        /home/rfindley/src/go/src/go/types/typexpr.go:441 +0x2da
go/types.(*Checker).processDelayed(0xc00012c1e0, 0x0)
        /home/rfindley/src/go/src/go/types/check.go:387 +0x39
go/types.(*Checker).checkFiles(0xc00012c1e0, {0xc000012100?, 0xc000079ae0?, 0x0?})
        /home/rfindley/src/go/src/go/types/check.go:332 +0xcb
go/types.(*Checker).Files(...)

[findleyr]

Ok, this is ringing bells.

When validating type B[T any] interface { B[*T] }, we mark B[*T] as invalid, but not B. I thought we had already fixed this, but was wrong.

Simpler reproducer:

type B[T any] interface {
	B[*T]
}

var _ B[int]

We can fix this by also marking the origin type B as invalid, though I need to verify that there are no side-effects of doing so (all tests pass, but this area is historically tricky).

[gopherbot]

Change https://go.dev/cl/449275 mentions this issue: go/types, types2: ensure invalid generic types are marked as invalid