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

Jump to bottom

cmd/compile: infinite loop with recursive generic types #56665

Closed
Merovius opened this issue Nov 9, 2022 · 8 comments
Closed

cmd/compile: infinite loop with recursive generic types #56665

Merovius opened this issue Nov 9, 2022 · 8 comments
Assignees
@findleyr
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Go1.20

Comments

@Merovius
Copy link
Contributor

Merovius commented Nov 9, 2022 •
edited

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.
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Nov 9, 2022
@mknyszek
Copy link
Contributor

mknyszek commented Nov 9, 2022

CC @golang/compiler

@mknyszek mknyszek added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 9, 2022
@mknyszek mknyszek added this to the Backlog milestone Nov 9, 2022
@mknyszek
Copy link
Contributor

mknyszek commented Nov 9, 2022

Is this new in Go 1.20?

@mdempsky
Copy link
Member

mdempsky commented Nov 9, 2022

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

findleyr commented Nov 9, 2022

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 findleyr self-assigned this Nov 9, 2022
@findleyr findleyr added the NeedsFix The path to resolution is known, but the work has not been done. label Nov 9, 2022
@gopherbot gopherbot removed the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 9, 2022
@findleyr
Copy link
Contributor

findleyr commented Nov 9, 2022 •
edited

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

findleyr commented Nov 9, 2022

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

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

@findleyr findleyr modified the milestones: Backlog, Go1.20 Nov 10, 2022
@gopherbot
Copy link

Change https://go.dev/cl/451015 mentions this issue: go/types, types2: limit nesting depth in typeWriter

@golang golang locked and limited conversation to collaborators Nov 16, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@findleyr findleyr

Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Go1.20
Development

No branches or pull requests
5 participants
@mdempsky @Merovius @mknyszek @gopherbot @findleyr