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

cmd/compile: cyclic constraints are not detected #69589

Closed
mneverov opened this issue Sep 23, 2024 · 8 comments
Closed

cmd/compile: cyclic constraints are not detected #69589

mneverov opened this issue Sep 23, 2024 · 8 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@mneverov
Copy link
Contributor

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.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Sep 23, 2024
@mneverov
Copy link
Contributor Author

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

atdiar commented Sep 23, 2024

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

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

@ianlancetaylor
Copy link
Member

CC @griesemer

@zigo101
Copy link

zigo101 commented Sep 23, 2024

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

zigo101 commented Sep 23, 2024

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.

@dr2chase dr2chase added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 24, 2024
@mknyszek mknyszek added this to the Go1.24 milestone Sep 25, 2024
@griesemer
Copy link
Contributor

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
Development

No branches or pull requests

9 participants