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: inconsistent typechecking with self-referential type parameter constraints #65714

Open
dawidl022 opened this issue Feb 14, 2024 · 8 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. early-in-cycle A change that should be done early in the 3 month dev cycle. generics Issue is related to generics NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@dawidl022
Copy link

dawidl022 commented Feb 14, 2024

This issue is similar to #65711. However, the behaviour of the compiler is different, so I am opening a separate issue.

What did you do?

While working on formal methods (in the style of Featherweight Go) and a prototype type checker and interpreter for #65555, I came across a pattern of programs that either pass or fail type checking, depending on the order of the type declarations.

E.g. the following program passes the type checker (and the program successfully compiles), and it is possible to implement and use the Bar interface (Go playground):

package main

type Foo[T Bar] interface {
}

type Bar interface {
	foo() Foo[Bar]
}

func main() {
}

(note: this program looks silly because it is part of my interpreter's testing suite, explicitly meant to test various edge cases in the type checker)

However, if we swap the order of the type declaration, the compiler rejects the program (playground):

package main

type Bar interface {
	foo() Foo[Bar]
}

type Foo[T Bar] interface {
}

func main() {
}

Output of go build for the latter example:

./prog.go:3:6: invalid recursive type Bar
	./prog.go:3:6: Bar refers to
	./prog.go:7:6: Foo refers to
	./prog.go:3:6: Bar

As far as I'm aware, the order of type declarations should not matter in a Go program.

From the Go spec, it is not clear to me, which is the correct behaviour. The spec says:

Within a type parameter list of a generic type T, a type constraint may not (directly, or indirectly through the type parameter list of another generic type) refer to T.

and provides an example:

type T3[P interface{ m(T3[int])}] …   // illegal: T3 refers to itself

Foo neither refers to itself directly via its own type parameter list (i.e. the Bar interface is not inlined in the type parameter list), nor is it referred through "the type parameter list of another generic type" (Foo is the only generic type in the program).

The issue is not exclusive to interface type declarations. The same behaviour can be observed through pairs of program using struct and array types.

Struct example

Compiles (playground):

package main

type Foo[T Bar] interface {
}

type Bar struct {
	foo Foo[Bar]
}

func main() {
}

Does not compile (playground):

package main

type Bar struct {
	foo Foo[Bar]
}

type Foo[T Bar] interface {
}

func main() {
}

Related issues

#65711 is also affected by the ordering of the type declarations, which suggests that the two issues are related.

What did you see happen?

Type checker accepting or rejecting programs depending on the order of type declarations.

What did you expect to see?

Type checker consistently accepting or rejecting programs, regardless of the ordering of type declarations.

Go version

go version go1.22.0 darwin/arm64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/dawidl022/Library/Caches/go-build'
GOENV='/Users/dawidl022/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/dawidl022/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/dawidl022/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/usr/local/go'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/local/go/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.22.0'
GCCGO='gccgo'
AR='ar'
CC='clang'
CXX='clang++'
CGO_ENABLED='1'
GOMOD='/Users/dawidl022/Learning/Uni/ECS635U-project/work/projects/go-generic-array-sizes/interpreters/fgg/go.mod'
GOWORK='/Users/dawidl022/Learning/Uni/ECS635U-project/work/projects/go-generic-array-sizes/go.work'
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/70/xq_w4nkj0fg4n8g8sc4y3g080000gn/T/go-build2129288715=/tmp/go-build -gno-record-gcc-switches -fno-common'
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Feb 14, 2024
@thanm thanm added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 15, 2024
@thanm
Copy link
Contributor

thanm commented Feb 15, 2024

@golang/compiler

@mknyszek
Copy link
Contributor

mknyszek commented Mar 6, 2024

In triage, we're wondering if @griesemer or @mdempsky can take a look? Thanks.

@mknyszek mknyszek added this to the Backlog milestone Mar 6, 2024
@griesemer griesemer self-assigned this Mar 6, 2024
@griesemer
Copy link
Contributor

@mknyszek I will take this on.

@griesemer griesemer modified the milestones: Backlog, Go1.23 Mar 6, 2024
@griesemer
Copy link
Contributor

#65711 has been fixed and is unrelated to this issue.

@griesemer
Copy link
Contributor

griesemer commented May 17, 2024

This is clearly a bug in the implementation. Cycles are poorly defined in the spec.
Not sure we can fix this for 1.23, but probably not a release blocker because re-arranging things is possible, and this bug has been around (likely) since 1.18.

@griesemer griesemer added the generics Issue is related to generics label May 17, 2024
@griesemer
Copy link
Contributor

Too late for 1.23. Moving to 1.24.

@griesemer griesemer modified the milestones: Go1.23, Go1.24 May 29, 2024
@griesemer griesemer added the early-in-cycle A change that should be done early in the 3 month dev cycle. label May 29, 2024
@gopherbot
Copy link
Contributor

This issue is currently labeled as early-in-cycle for Go 1.24.
That time is now, so a friendly reminder to look at it again.

@griesemer
Copy link
Contributor

Too late for 1.24. Moving to 1.25.

@griesemer griesemer modified the milestones: Go1.24, Go1.25 Nov 11, 2024
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. early-in-cycle A change that should be done early in the 3 month dev cycle. generics Issue is related to generics 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

5 participants