cmd/compile: cyclic constraints are not detected

mneverov commented 1 month ago

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 commented 1 month ago

Related Issues and Documentation

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

mneverov commented 1 month ago

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 commented 1 month ago

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 commented 1 month ago

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

ianlancetaylor commented 1 month ago

CC @griesemer

zigo101 commented 1 month ago

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 commented 1 month ago

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 commented 1 month ago

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.

golang / go