go: go/types, types2: inconsistent behavior with recursive generic types that produces deadlock, invalid recursive, unknown field error

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

$ go version
go version go1.20.5 darwin/arm64

Does this issue reproduce with the latest release?

Yes, since go1.18 had introduced generics.

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

go env Output

$ go env
GO111MODULE="on"
GOARCH="arm64"
GOBIN=""
GOCACHE="/Users/neko/Library/Caches/go-build"
GOENV="/Users/neko/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/neko/golang/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/neko/golang"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/opt/homebrew/Cellar/go/1.20.5/libexec"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/opt/homebrew/Cellar/go/1.20.5/libexec/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="go1.20.5"
GCCGO="gccgo"
AR="ar"
CC="cc"
CXX="c++"
CGO_ENABLED="1"
GOMOD="/Users/neko/Playground/go/recursive_generic_type/go.mod"
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="/opt/homebrew/bin/pkg-config"
GOGCCFLAGS="-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/m0/k_38ftb53yg0mqbcrrjypr3m0000gn/T/go-build4074324993=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

I defined a recursive generic type like this:

type CommonOption[T any, C TypeA[T] | TypeB[T]] struct {
	value     T
	container *C
}

func (o *CommonOption[T, C]) WithValue(v T) *C {
	o.value = v

	return o.container
}

type TypeA[T any] struct {
	*CommonOption[T, TypeA[T]]

	subFieldA string
}

type TypeB[T any] struct {
	*CommonOption[T, TypeB[T]]
}

And trying to discover the possibility of using generics to make the common options assignment easier and more readable by using chained calls pattern.

What did you expect to see?

Either the compiler or the documentations of generics of Golang addresses the restricted usage of recursive generic types or the compiler behaves consistently. The inconsistent behavior may be vary based on whether it’s with in tests or just build, whether it’s a single source file or multiple source files, whether it’s wrapped with a pointer over pointer or not, whether it’s imported the outside package or not.

What did you see instead?

Issue 1: `fatal error: all goroutines are asleep - deadlock!`

Panic stack

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [sync.Mutex.Lock]:
sync.runtime_SemacquireMutex(0x0?, 0x0?, 0x0?)
	/usr/local/go/src/runtime/sema.go:77 +0x26
sync.(*Mutex).lockSlow(0xc0003b1218)
	/usr/local/go/src/sync/mutex.go:171 +0x165
sync.(*Mutex).Lock(...)
	/usr/local/go/src/sync/mutex.go:90
cmd/compile/internal/types2.(*Named).resolve(0xc0003b11f0)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:164 +0x7b
cmd/compile/internal/types2.(*Named).TypeParams(0x0?)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:310 +0x19
cmd/compile/internal/types2.(*subster).typ(0xc0000c4e18, {0xf26150?, 0xc0003b12d0?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:223 +0xd95
cmd/compile/internal/types2.(*subster).typ(0x3?, {0xf26178?, 0xc00008d050?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:118 +0x3ae
cmd/compile/internal/types2.(*subster).var_(0xc0000c4bc0?, 0xc0003b1340)
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:285 +0x32
cmd/compile/internal/types2.(*subster).varList(0xc33e51?, {0xc00009c530, 0x1, 0x415ed0?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:311 +0x90
cmd/compile/internal/types2.(*subster).typ(0x0?, {0xf261f0?, 0xc000347e30?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:111 +0x25c
cmd/compile/internal/types2.(*Checker).subst(0x0, {0x0?, 0x3b2300?, 0xc0?}, {0xf261f0?, 0xc000347e30}, 0xc0003dc270, 0xc0003b1420, 0x0)
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:78 +0x1c5
cmd/compile/internal/types2.(*Named).expandUnderlying(0xc0003b1420)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:623 +0x505
cmd/compile/internal/types2.(*Named).resolve(0xc0003b1420)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:177 +0x185
cmd/compile/internal/types2.(*Named).Underlying(0x1?)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:456 +0x19
cmd/compile/internal/types2.(*Named).under(0xc0003b1420)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:484 +0x36
cmd/compile/internal/types2.under({0xf26150?, 0xc0003b1420?})
	/usr/local/go/src/cmd/compile/internal/types2/type.go:19 +0x45
cmd/compile/internal/types2.computeInterfaceTypeSet(0x0, {0xc000347c80?, 0x7e8c72af?, 0x7cc7?}, 0xc0003adbd0)
	/usr/local/go/src/cmd/compile/internal/types2/typeset.go:275 +0x567
cmd/compile/internal/types2.(*TypeParam).iface(0xc0003dc090)
	/usr/local/go/src/cmd/compile/internal/types2/typeparam.go:138 +0x1b2
cmd/compile/internal/types2.(*TypeParam).SetConstraint(...)
	/usr/local/go/src/cmd/compile/internal/types2/typeparam.go:86
cmd/compile/internal/importer.(*reader).typeParamNames(0xc00009ff80)
	/usr/local/go/src/cmd/compile/internal/importer/ureader.go:510 +0x213
cmd/compile/internal/importer.(*pkgReader).objIdx.func1.1(0xc000347b90?)
	/usr/local/go/src/cmd/compile/internal/importer/ureader.go:430 +0x26
cmd/compile/internal/types2.(*Named).resolve(0xc0003b11f0)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:203 +0x122
cmd/compile/internal/types2.(*Named).TypeParams(0xc0003d80e0?)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:310 +0x19
cmd/compile/internal/types2.(*subster).typ(0xc0000c5e48, {0xf26150?, 0xc0003b12d0?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:223 +0xd95
cmd/compile/internal/types2.(*subster).typ(0xc0000c5bb8?, {0xf26178?, 0xc00008d050?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:118 +0x3ae
cmd/compile/internal/types2.(*subster).var_(0xc0000c5bf0?, 0xc0003b1340)
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:285 +0x32
cmd/compile/internal/types2.(*subster).varList(0xc33e51?, {0xc00009c530, 0x1, 0x415ed0?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:311 +0x90
cmd/compile/internal/types2.(*subster).typ(0x0?, {0xf261f0?, 0xc000347e30?})
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:111 +0x25c
cmd/compile/internal/types2.(*Checker).subst(0xc0000e23c0, {0xc000347860?, 0x3b22c0?, 0xc0?}, {0xf261f0?, 0xc000347e30}, 0xc0003dc030, 0xc0003b13b0, 0xc0003b21c0)
	/usr/local/go/src/cmd/compile/internal/types2/subst.go:78 +0x1c5
cmd/compile/internal/types2.(*Named).expandUnderlying(0xc0003b13b0)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:623 +0x505
cmd/compile/internal/types2.(*Named).resolve(0xc0003b13b0)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:177 +0x185
cmd/compile/internal/types2.(*Named).Underlying(0xc0003b13b0?)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:456 +0x19
cmd/compile/internal/types2.(*Named).under(0xc0003b13b0)
	/usr/local/go/src/cmd/compile/internal/types2/named.go:484 +0x36
cmd/compile/internal/types2.under({0xf26150?, 0xc0003b13b0?})
	/usr/local/go/src/cmd/compile/internal/types2/type.go:19 +0x45
cmd/compile/internal/types2.coreType({0xf26150?, 0xc0003b13b0?})
	/usr/local/go/src/cmd/compile/internal/types2/type.go:33 +0x9a
cmd/compile/internal/types2.(*Checker).exprInternal(0xc0000e23c0, 0xc0003d02c0, {0xf28200?, 0xc0000b3300}, {0x0?, 0x0?})
	/usr/local/go/src/cmd/compile/internal/types2/expr.go:1403 +0x82f
cmd/compile/internal/types2.(*Checker).rawExpr(0xc0000e23c0, 0xc0003d02c0, {0xf28200?, 0xc0000b3300?}, {0x0?, 0x0?}, 0x0)
	/usr/local/go/src/cmd/compile/internal/types2/expr.go:1252 +0x1a5
cmd/compile/internal/types2.(*Checker).multiExpr(0x503b01512f1d42fc?, 0xc0000c6948?, {0xf28200?, 0xc0000b3300?})
	/usr/local/go/src/cmd/compile/internal/types2/expr.go:1817 +0x35
cmd/compile/internal/types2.(*Checker).exprList(0xd4c?, {0xc0000c6be0?, 0xc0003adb30?, 0xc0003adae0?}, 0x0)
	/usr/local/go/src/cmd/compile/internal/types2/call.go:273 +0x97
cmd/compile/internal/types2.(*Checker).assignVars(0xc0000e23c0, {0xc0000c6bf0?, 0x1, 0x1}, {0xc0000c6be0?, 0x1, 0x1})
	/usr/local/go/src/cmd/compile/internal/types2/assignments.go:384 +0x7f
cmd/compile/internal/types2.(*Checker).stmt(0xc0000e23c0, 0x0, {0xf27078?, 0xc0003d0100?})
	/usr/local/go/src/cmd/compile/internal/types2/stmt.go:472 +0x7c5
cmd/compile/internal/types2.(*Checker).stmtList(0xf259d0?, 0x0, {0xc00008ceb0?, 0xbecba0?, 0xc0000e23c0?})
	/usr/local/go/src/cmd/compile/internal/types2/stmt.go:123 +0x78
cmd/compile/internal/types2.(*Checker).funcBody(0xc0000e23c0, 0xc00009fce0, {0xc0000ab738?, 0x1?}, 0xc0003d0280, 0xc0003d00c0, {0x0, 0x0})
	/usr/local/go/src/cmd/compile/internal/types2/stmt.go:43 +0x396
cmd/compile/internal/types2.(*Checker).funcDecl.func1()
	/usr/local/go/src/cmd/compile/internal/types2/decl.go:760 +0x45
cmd/compile/internal/types2.(*Checker).processDelayed(0xc0000e23c0, 0x0)
	/usr/local/go/src/cmd/compile/internal/types2/check.go:383 +0x1af
cmd/compile/internal/types2.(*Checker).checkFiles(0xc0000e23c0, {0xc00009c4c8, 0x1, 0x1})
	/usr/local/go/src/cmd/compile/internal/types2/check.go:328 +0x172
cmd/compile/internal/types2.(*Checker).Files(...)
	/usr/local/go/src/cmd/compile/internal/types2/check.go:300
cmd/compile/internal/types2.(*Config).Check(0xc000099998?, {0x7fff23c24cc8?, 0x7?}, {0xc00009c4c8, 0x1, 0x1}, 0xdc612a?)
	/usr/local/go/src/cmd/compile/internal/types2/api.go:434 +0x70
cmd/compile/internal/noder.checkFiles({0xc00009c4b0, 0x1, 0xdcb342?})
	/usr/local/go/src/cmd/compile/internal/noder/irgen.go:73 +0x465
cmd/compile/internal/noder.writePkgStub({0xc00009c4b0, 0x1, 0x1})
	/usr/local/go/src/cmd/compile/internal/noder/unified.go:210 +0x46
cmd/compile/internal/noder.unified({0xc00009c4b0?, 0xc000347890?, 0x2?})
	/usr/local/go/src/cmd/compile/internal/noder/unified.go:75 +0x85
cmd/compile/internal/noder.LoadPackage({0xc0000a4120, 0x1, 0x2})
	/usr/local/go/src/cmd/compile/internal/noder/noder.go:77 +0x465
cmd/compile/internal/gc.Main(0xdfc760)
	/usr/local/go/src/cmd/compile/internal/gc/main.go:196 +0xc53
main.main()
	/usr/local/go/src/cmd/compile/main.go:57 +0xdd

Errored:
- when met the following criteria [playground]:
  1. takes place on go build or go test,
  2. the target code imports a package containing recursive generics type definition.
Error disappeared:
- when met the following criteria [playground]:
  1. the target code imports a package containing recursive generics type definition,
  2. recursive generics type has pointer reference for both field and type parameter.
  - which results in:
    1. fmt.Printf("%T") still works as expected,
    2. the recursive type definition might be optimized by compiler with abnormal assembly code when inspect the assembly by using go build -gcflags=-S.
- when met the following criteria [playground]:
  1. the package has the target code lives in contains the recursive generics type defined
  - which results in:
    1. fmt.Printf("%T") still works as expected,
    2. the recursive type definition might be optimized by compiler with abnormal assembly code when inspect the assembly by using go build -gcflags=-S.

Issue 2: `invalid recursive type x`

Output

./file_2.go:3:6: invalid recursive type T2
	./file_2.go:3:6: T2 refers to
	./main.go:8:6: innerT refers to
	./file_2.go:3:6: T2

errored:
- when met the following criteria [playground]:
  1. takes place on go build or go test,
  2. define one of the type parameter of type innerT as union type recursively,
  3. definitions live in two separated files.
error disappeared
- when met the following criteria [playground]:
  1. define one of the type parameter of type innerT as union type recursively.
  2. definitions live in one single file.
  - which results in:
    1. fmt.Printf("%T") still works as expected,
    2. the recursive type definition might be optimized by compiler with abnormal assembly code when inspect the assembly by using go build -gcflags=-S.

Issue 3: `unknown field x in struct literal of type y`

errored:
- when met the following criteria [playground]:
  1. this case is not playground reproducible due to it only take place when editing in Visual Studio Code with a hovering popup,
  2. try to access or set the field within the parent of the recursive generics type.
  - which results in:
    1. if try to execute go build or go test the compiler will complain fatal error: all goroutines are asleep - deadlock! error
error disappeared:
- when met the following criteria [playground]:
  1. try to access or set the field within the parent of the recursive generics type.
  2. recursive generics type has pointer reference for both field and type parameter.
  - which results in:
    1. fmt.Printf("%T") still works as expected,
    2. the recursive type definition might be optimized by compiler with abnormal assembly code when inspect the assembly by using go build -gcflags=-S.
- when met the following criteria:
  1. the package has the target code lives in contains the recursive generics type defined.
  - which results in:
    1. fmt.Printf("%T") still works as expected,
    2. the recursive type definition might be optimized by compiler with abnormal assembly code when inspect the assembly by using go build -gcflags=-S.

Issue 4: `x` redeclared in this block

It errored with a single valid file_1.go, and the package channelx only containing the SubContainer, ContainerA, ContainerB types.

This is the most hard to reproduced one by comparing to the other issues I have faced. I only encountered once when debugging the invalid recursive type error.

Further more

I have found a issue that containing the same error message just like me in #49439. However, this doesn’t explain why it compiles successfully and run expected when the type definitions and the functions that referenced the type are in a same package.

Later I found #51244 with a ongoing fix at CL 386718 that pending on merge (maybe merge before next cycle of Golang release?). However, just like the same issue, this doesn’t explain why it compiles successfully and run expected in some cases while the compiler and static analysis behaves inconsistently.

So, is this such inconsistent behavior a already known issue? At least it jammed me for a while to find out what I have done wrong.

Especially the compiler would optimized the recursive type definition and generate a unexpected assembly code:

$ go build -gcflags=-S ./minimum_repro/deadlock_issue/with_generics                     
# github.com/nekomeowww/recursive_generic_type_issue_reproduction/minimum_repro/deadlock_issue/with_generics
go:cuinfo.producer.github.com/nekomeowww/recursive_generic_type_issue_reproduction/minimum_repro/deadlock_issue/with_generics SDWARFCUINFO dupok size=0
        0x0000 2d 73 68 61 72 65 64 20 72 65 67 61 62 69        -shared regabi
go:cuinfo.packagename.github.com/nekomeowww/recursive_generic_type_issue_reproduction/minimum_repro/deadlock_issue/with_generics SDWARFCUINFO dupok size=0
        0x0000 77 69 74 68 5f 67 65 6e 65 72 69 63 73           with_generics

Is this abnormal? The normal assembly output doesn’t look like this.

Imagine a developer is maintaining a package that is widely used by other users, and the developer never test the code with a test package suffixed with _test, and developer initially would have no ideas to understand how and why the compiler may complain and throw a panic with fatal error: all goroutines are asleep - deadlock! message when users imported the package with the version contained some type definitions the same as the reproduction codes in playground bellow.

By the way, run go build and go test with GOEXPERIMENT=nounified env flag fixed the following errors I encountered bellow (suggested in #54535).

About this issue

Original URL
State: open
Created a year ago
Reactions: 1
Comments: 30 (17 by maintainers)

Commits related to this issue

go/types: add test cases for generic constraints, types and functions Dups: #60856 For #60817 Change-Id: Ic0710758e170d6ceed66649fec08ef8054be4d6b GitHub-Last-Rev: 8bbc76aaa704f102f9eabdfead45da452e... — committed to golang/go by Nasfame a year ago

Most upvoted comments

Thanks for finding this issue. I’ll look into that reproducer when I work on this (which I still plan for 1.22).

findleyr on Sep 20, 2023

@mdempsky thanks. I’m not sure if it’s possible to do this properly with the current APIs, since SetConstraint is called from reader.typeParamNames, which in turn is called from the load func passed to NewTypeNameLazy. I don’t know how this sequence of API calls can be avoided from the load func, with the current semantics. But perhaps I’m missing something.

Discussed with @griesemer, and we think we should take the more principled approach (option 1 above) to fix the SetConstraint API, for go1.22.

As suggested by @griesemer, perhaps we should avoid the sync.Once and use an explicit Complete method, as is done for interfaces. (we should holistically evaluate the current type construction APIs).

findleyr on Jun 26, 2023

CC @griesemer

Thanks for the report. Independent of what the correct behavior is here, we should never deadlock, even in invalid code.

findleyr on Jun 21, 2023

@jub0bs I think your issue may be only indirectly related, as I can only reproduce it using import/export, not with pure type checking from source (see the above CL for a reproducing test).

findleyr on Sep 28, 2023

@Nasfame thanks for that CL, and for your investigation. I am not convinced that CL fixes the problem, because I don’t think the tests are actually using the unified export data reader.

@mdempsky @griesemer: the problem here is that the unified type loader calls SetConstraint, which is documented to “only be valid after the bound’s underlying is fully defined”. But in this case, due to the recursive definition, SetConstraint is being called while the underlying is being resolved. This isn’t a problem with the old importer because all calls to SetConstraint were deferred: https://cs.opensource.google/go/go/+/master:src/go/internal/gcimporter/iimport.go;l=195;drc=1c05968c9a5d6432fc6f30196528f8f37287dd3d

Of course, this is a very tricky API to use correctly. I’m not sure how to proceed.

Option 1: make the call to TypeParam.iface lazy. One may argue that just moves the footgun down one level: each time we move the reentrant API, we make it less likely to hit this type of recursion, but also make it that much more confusing when we do.

I think we may be able to make this easier to understand by segregating the type API into method that are valid “constructors”, and other non-constructors. Constructors can be called in any order, but you must not call any constructors after a non-constructor has been used. That’s effectively what we have now, but we have no formality to the schema.

Then we would make SetConstraint conform to the rules for constructors by internally deferring its call to iface, via sync.Once.

Not pretty, but arguably better than what we have now, which is an API that is almost impossible to use outside of the carefully crafted import logic.

Option 2: let the lazy type loading logic assume single-threadedness. Since this API is only used by the compiler, and I believe is only used in a single-threaded context, perhaps we can avoid the deadlock by unlocking after nilling out the loader here: https://cs.opensource.google/go/go/+/master:src/cmd/compile/internal/types2/named.go;l=199;drc=5724daa6825db0a9097254060633439e6538d845

That would probably work, but is not obviously correct.

findleyr on Jun 26, 2023

My fixes for minimum_repro- https://github.com/golangFame/recursive_generic_type_issue_reproduction

@nekomeowww

Thanks, and sorry that I forgot to update the reproduction issue to include the reproduction for issue 3 unknown field.

nekomeowww on Jun 17, 2023