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: cannot use tilde for struct type in type parameter #52295

Closed
changkun opened this issue Apr 12, 2022 · 9 comments
Closed

cmd/compile: cannot use tilde for struct type in type parameter #52295

changkun opened this issue Apr 12, 2022 · 9 comments
Labels
WaitingForInfo

Comments

@changkun
Copy link
Member

@changkun changkun commented Apr 12, 2022

What version of Go are you using (go version)?

$ go version
go1.18

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE="auto"
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/changkun/.cache/go-build"
GOENV="/home/changkun/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/changkun/go/pkg/mod"
GONOPROXY="poly.red/x"
GONOSUMDB="poly.red/x"
GOOS="linux"
GOPATH="/home/changkun/go"
GOPRIVATE="poly.red/x"
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/changkun/goes/go1.18"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/changkun/goes/go1.18/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.18"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/changkun/dev/poly.red/polyred/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build2419884666=/tmp/go-build -gno-record-gcc-switches"

What did you do?

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

package main

type Type struct{}

type MyType Type

func F[T ~Type](t T) {}

func main() {
	x := Type{}
	y := MyType{}
	F(x)
	F(y)
}

What did you expect to see?

Compile success

What did you see instead?

./prog.go:7:10: invalid use of ~ (underlying type of Type is struct{})
./prog.go:12:3: cannot implement ~Type (empty type set)
./prog.go:13:3: cannot implement ~Type (empty type set)

Go build failed.

I am not sure if this was discussed somewhere, but I could not quickly find a discussion about this. This is the closest: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#approximation-constraint-element that discusses the requirements for a constraint to be valid.

According to the spec:

UnderlyingType = "~" Type .

Type      = TypeName [ TypeArgs ] | TypeLit | "(" Type ")" .
TypeName  = identifier | QualifiedIdent .
TypeArgs  = "[" TypeList [ "," ] "]" .
TypeList  = Type { "," Type } .
TypeLit   = ArrayType | StructType | PointerType | FunctionType | InterfaceType |
	    SliceType | MapType | ChannelType .

Tilde "~" can be used to a StructType. The defined function func F[T ~Type](t T)
is essentially func F[T interface{~Type}](t T), and the type constraints interface{~Type} is valid because its core type is Type.

It is also confusing for this error message:

cannot implement ~Type (empty type set)

Not entirely clear to me: why Type does not implement ~Type? why is it an empty type set?

@cherrymui
Copy link
Member

@cherrymui cherrymui commented Apr 12, 2022

~Type means the type set where the underlying type is Type, not struct{}. Type's underlying type is struct{}, not Type, so it doesn't satisfy the interface. This is also true for non-struct type, e.g. https://go.dev/play/p/X6mE1QQGDlJ

@changkun
Copy link
Member Author

@changkun changkun commented Apr 12, 2022

~Type means the type set where the underlying type is Type, not struct{}. Type's underlying type is struct{}, not Type, so it doesn't satisfy the interface. This is also true for non-struct type, e.g. https://go.dev/play/p/X6mE1QQGDlJ

I don't know what is the correct understanding for this. Your example seems align with your provided interpretation. The following example is also confusing because it feels like it is impossible to limit the type parameters to a slice that its element's "underlying" type is Type:

package main

type Type struct{}

type MyType Type

func main() {
	x := []Type{}
	y := []MyType{}
	F1(x) // OK

	F1(y) // ERROR: MyType does not implement Type
	F2(y) // ERROR: cannot implement ~Type (empty type set)
	F3(y) // ERROR: MyType does not implement interface{struct{}} (possibly missing ~ for struct{} in constraint interface{struct{}})
}

func F1[S []Elem, Elem Type](t S) {}

func F2[S []Elem, Elem ~Type](t S) {} // ERROR: invalid use of ~ (underlying type of Type is struct{})

func F3[S []Elem, Elem interface{ struct{} }](t S) {}

@cherrymui
Copy link
Member

@cherrymui cherrymui commented Apr 12, 2022

it feels like it is impossible to limit the type parameters to a slice that its element's "underlying" type is Type

Yeah, same issue. It is impossible because there is no type whose underlying type is Type. The underlying type of both Type and MyType is struct{}.

F3 would work if you use ~struct{}.

@changkun
Copy link
Member Author

@changkun changkun commented Apr 12, 2022

OK the trick is to use ~ in struct{}:

func F4[S []Elem, Elem interface{ ~struct{} }](t S) {}

F4(y) // OK

But what if it is a struct that we can't easily write? Does that mean we must provide and declare the nested struct in the type parameter? What if it is a circular struct?

func F5[S []Elem, Elem ~struct { /* Next *CircularType??? */ ](t S) {}

type CircularType struct {
	Next *CircularType
}

F5([]CircularType{})

Edit: What if there is a field typed in an unexported type?

@cherrymui
Copy link
Member

@cherrymui cherrymui commented Apr 12, 2022

I think ~struct { Next *CircularType } actually works. https://go.dev/play/p/Bw3Y4Pya_nX . I agree it is a bit awkward.

I don't know what to do with unexported fields.

Do you have a real use case that you need to define the element type with a different name? (i.e. use []MyType instead of just []Type ?)

@changkun
Copy link
Member Author

@changkun changkun commented Apr 12, 2022

Do you have a real use case that you need to define the element type with a different name? (i.e. use []MyType instead of just []Type ?)

I don't know how to answer what could be a real use case, but I am trying to write code like this:

A polygon mesh structure that consists of a slice of polygons:

type PolygonMesh struct { Faces []Polygon }

type Polygon struct {
    verts []Vertex
    ....
}

A specialized polygon, triangle, or quad has some sort of specialized implementation for polygons, such as computing normals, etc.

type Triangle Polygon

func (t Triangle) Normal() Vec3 { /* ... do stuff with vertices */ }

type Quad Polygon

... more specialized methods ...

There are also specialized polygon mesh structures:

type TriangleMesh struct { Faces []Triangles }
type QuadMesh struct     { Faces []Quad }

Now, I am expecting an iterator over all faces:

package mesh

func IterateFaces[F []Elem, Elem ~Polygon](faces F) { ... }

So that on the caller side:

mesh.IterateFaces(TriangleMesh{}.Faces)
mesh.IterateFaces(QuadMesh{}.Faces)
mesh.IterateFaces(PolygonMesh{}.Faces)

@cherrymui
Copy link
Member

@cherrymui cherrymui commented Apr 12, 2022

Thanks. Would it be possible to define Polygon an alias type, i.e. type Polygon = struct { verts []Vertex; ... }? Then I think ~Polygon would work. (But you cannot define methods on Polygon, then.)

If you believe there is a missing feature and it is useful to add the support, you are welcome to file a proposal (or modify this issue to a proposal) to change the language spec. (With the current spec, I think the compiler is correct.) Thanks.

@ianlancetaylor ianlancetaylor added the WaitingForInfo label Apr 12, 2022
@changkun
Copy link
Member Author

@changkun changkun commented Apr 12, 2022

Would it be possible to define Polygon an alias type, i.e. type Polygon = struct { verts []Vertex; ... }? Then I think ~Polygon would work. (But you cannot define methods on Polygon, then.)

I don't think it is possible to define as an alias because Polygon also its own specialized methods. Moreover, the Polygon struct itself will have circular fields pointing to another polygon, and so on. This is not a made up need but actually from research. I could also imagine in an abstract way that a similar need will happen as described on top of the issue. But I guess my provided case should be enough.

I don't have an idea about what a proposal could be. Sigh for this confusion.

@cherrymui
Copy link
Member

@cherrymui cherrymui commented Apr 12, 2022

Another possible workaround would be, instead of defining Triangle etc. as type Triangle Polygon, embed Polygon in them, i.e. type Triangle struct { Polygon }. Then you might be able to use ~struct { Polygon } as the constraint for generic functions? (I didn't try it myself.)

I guess one idea that you could potentially proposing is to change the type set ~T not to mean types whose underlying type is T, but types whose underlying type is the underlying type of T (or use a different notation than ~T for it), if you think that's helpful.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
WaitingForInfo
Projects
None yet
Development

No branches or pull requests

3 participants