cmd/compile: cyclic constraints are not detected

[mneverov]

Go version

1.23.1

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/mneverov/.cache/go-build'
GOENV='/home/mneverov/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/mneverov/go/pkg/mod'
GONOPROXY='gitlab.in.strato.de,github.com/ionos-cloud'
GONOSUMDB='gitlab.in.strato.de,github.com/ionos-cloud'
GOOS='linux'
GOPATH='/home/mneverov/go'
GOPRIVATE='gitlab.in.strato.de,github.com/ionos-cloud'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/usr/local/go'
GOSUMDB='sum.golang.org'
GOTMPDIR='/home/mneverov/tmp'
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/local/go/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.23.1'
GODEBUG=''
GOTELEMETRY='on'
GOTELEMETRYDIR='/home/mneverov/.config/go/telemetry'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/home/mneverov/go/src/github.com/ionos-cloud/go-controller-test/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 -ffile-prefix-map=/home/mneverov/tmp/go-build2051668269=/tmp/go-build -gno-record-gcc-switches'

What did you do?

type T1[C1 any] struct{}
type T2[C2 T1[C2]] struct{}

What did you see happen?

Program compiles successfully.

What did you expect to see?

error invalid recursive type C2.

[gabyhelp]

Related Issues and Documentation

• cmd/compile/internal/types2: invalid recursive type not detected and panics #48096 (closed)
• cmd/compile: declaration order of types affects cycle detection #68025
• gccgo: internal compiler error with simple recursive type declaration #25320 (closed)
• cmd/go: compiler panic on recursive structures #45661 (closed)
• cmd/compile: constraints that are impossible to satisfy are not caught #67025 (closed)
• cmd/compile: infinite loop with recursive generic types #56665 (closed)
• cmd/compile: internal compiler error when processing invalid recursive type #49276 (closed)
• cmd/compile: Bad error message on missing type constraint #55961 (closed)
• cmd/compile: panic if recursive type with field of error type #47636 (closed)
• cmd/compile: infinite loop in -G=3 type instantiation #48030 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[mneverov]

Probably related #60817

I tried to understand how the type check happens and the constraint type passed to objDecl is colored black and the check is skipped. Also, type constraints are not named types and hence are not generic.

[atdiar]

I think that it's just that it is unsatisfiable but the compiler doesn't currently check for it (don't know whether it is necessary).

The compiler should error out as soon as someone tries to instantiate T2.

For instance this would work:

https://go.dev/play/p/mIrGf99BVK3

Meaning it depends on T1.

[ianlancetaylor]

I don't see any obvious reason that the code in the original post is invalid.

[ianlancetaylor]

CC @griesemer

[zigo101]

Finding 1: it will still compile even if T1 has a C1 field. This might because T1[C2] is an empty-type-set constraint.

type T1[C1 any] struct{
   x C1
}

type T2[C2 T1[C2]] struct{}

Finding 2: T2 can't be instantiated. The error message is not very clear.

type T1[C1 any] struct{}
type T2[C2 T1[C2]] struct{}
       
type T = T2[struct{}] // struct{} does not satisfy T1[struct{}] (struct{} missing in main.T1[struct{}])

[zigo101]

Rethink it for awhile. I think this is the same problem of empty-type-set constraints.
T1[C2] is a defined type, so it is effectively a empty-type-set constraint.
If T1 is an alias, then T2 can be instantiated (1,23 with GOEXPERIMENT=aliastypeparams):

type T1[C1 any] = struct{}
type T2[C2 T1[C2]] struct{}

type _ = T2[T1[int]] // okay
type _ = T2[struct{}] // okay

Please read the last section of https://go101.org/generics/777-operations-on-values-of-type-parameter-types.html for details.

[griesemer]

I don't believe this is related to #60817.

The compiler does currently report some cycles through type parameter lists, but I believe we're overly restrictive in those cases.

As @ianlancetaylor already said, I don't believe there should be an error in this specific case (type parameters renamed to simplify):

type T1[_ any] struct{}
type T2[P T1[P]] struct{}

T1 is a valid type for any instantiation because the constraint allows any type argument.

T2 can be instantiated with a type argument X that satisfies the constraint T1[X]. This means X must be in the type set containing just the type T1[X]; in other words, X must be T1[X] for this to be true. But T1[X] (for any X) is a named type (*), and named types are different from any other type. So for X to be the same as T1[X], X must be identical to T1[X]. In other words, X must be an alias for T1[X]. But Go does not allow such cyclic alias declarations (playground). Hence, no such type X exists and T2 cannot be instantiated.

All that said, as long as T2 is not instantiated, there's nothing wrong with this code.

One might argue that the compiler should report an error because effectively T2 can never be used. We don't do that because it is difficult (if not impossible) for the compiler to prove in general whether a generic type can be instantiated or not. On the other hand, given a concrete instantiation, it's straight-forward to check if the constraints are satisfied.

Closing this as working as intended.

PS: (*) If T1 were not a named type, it's possible to instantiate T2 as shown in this example.