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

[nekomeowww]

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).

[nekomeowww]

Issue 1- Solution - https://go.dev/play/p/2XBjhY2XPmW

type H struct {

	h H

}//this is invalid

The same case extends to generic as well

First, thanks for workaround. I know it's invalid. I had a example in issue 1 at error disappeared at first branch which already uses pointer reference for both type parameter and field and the issue is resolved.

But the critical thing is:

1. it runs ok and smoothly if the functions and tests within the same package as the type definitions.
2. invalid recursive error may complain even when you used pointer reference.

[nekomeowww]

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]

Issue 1- Solution - https://go.dev/play/p/2XBjhY2XPmW Complete - https://go.dev/play/p/-Km9BInPB2r

type H struct {
	h H
}//this is invalid

The same case extends to generic as well

Hmm, I used the same method as you do in Complete as a workaround for issue 1.

However, since the non pointer reference for type param but within package scope case (or issue 1, error disappeared branch, when case 1) still runs and can be compiled, is this something that compiler behaves inconsistently? Both the three obvious issues would not occur when the type definitions and value references live in one package. How do you explain it?

[nekomeowww]

@nekomeowww u get the gist i guess - reproduce the issue by stripping off the generics.

| - needs some updating in gopls or a bug fix with respect to the scenario - type innerT[T any, R T1[T] | T2[T]]

Do I need to create a separate issue for gopls? Or I should wait for the investigation further on?

[nekomeowww]

still runs and can be compiled, is this something that compiler behaves inconsistently

No, i dont think so. Only time i felt it behaved differently was with | i.e for separated files scenario

So if am understand correctly, it is expected that the recursive generic type definition and logic can be run successfully within package scope instead of being addressed by compiler, and such behavior is different when used in outside of the package scope? This doesn't sound right to me.

IDIOM is that "non-pointer recursive types are not allowed" .

I know.
On the other hand, I think the compiler should prompt a trace error with invalid recursive type instead of panicking. Or Golang team think the fatal deadlock panics from the compiler is acceptable?

[gopherbot]

Change https://go.dev/cl/504195 mentions this issue: doc: | operator for constraints

[findleyr]

CC @griesemer

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

[findleyr]

I will fix the deadlock (I think it's my bug), but for 1.22, since presumably this has existed since 1.18.

[findleyr]

@Nasfame thanks, I will take a look.

[findleyr]

@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.

[mdempsky]

This isn't a problem with the old importer because all calls to SetConstraint were deferred

FWIW, gcimporter's unified reader still defers them too: https://cs.opensource.google/go/go/+/master:src/go/internal/gcimporter/ureader.go;l=618

If we need to defer the compiler's SetConstraint calls too, I think that's doable. Stylistically it's kinda gross, but pragmatically it seems fine to me.

The API for importers has always been a little awkward. I'd be surprised if there were any non-trivial implementations outside of std+x/tools.