go/types: self-reference within type parameter constraints

[mdempsky]

This test case sends go/types into an infinite recursion: https://go2goplay.golang.org/p/fpWup_pjUzi

type T[U interface{ M() T }] int

type X int
func (X) M() T[X] { return 0 }

Two questions:

1. Are recursive type parameters like this supposed to work? If so, this has implications on extending the go/types API and export data format to support type parameters (e.g., see also proposal: go/types: lazy resolution of imported objects #46449 (comment)).

2. Also if so, shouldn't interface{ M() T } actually be interface{ M() T[U] }? However, go/types explicitly rejects the latter.

/cc @griesemer @ianlancetaylor @findleyr @bcmills

[findleyr]

See also #45550, which is similar but manifests differently (stack overflow vs timeout).

My attempt to answer your questions:

1. I'm not sure, but recursive constraints are sufficiently mind-bending that perhaps they should be explicitly disallowed.
2. Yes, the use of the generic type T in a result parameter should be rejected. I suspect we never get to that point when type checking.

[ianlancetaylor]

Certainly type T[U interface{ M() T }] int is incorrect.

It seems to me that type T[U interface{ M() T[U] }] int should be accepted. A constraint should be able to refer to the type being defined at least in cases where a type can refer to itself. I also think it's OK if we give an error for this for now.

[griesemer]

types2 accepts

type T[U interface{ M() T[U] }] int

type X int
func (X) M() T[X] { return 0 }

which I believe is correct code and (eventually) should be accepted. Currently we have an endless recursion.

[griesemer]

@mdempsky Is there anything left to do here?

The compiler now accepts

package p

type T[U interface{ M() T[U] }] int

type X int
func (X) M() T[X] { return 0 }

[gopherbot]

Change https://golang.org/cl/348738 mentions this issue: test: add compiler regress tests for #46461

[mdempsky]

@mdempsky Is there anything left to do here?

CL 348738 adds a test. It looks like types2 and unified IR handle this correctly now, but iexport fails with:

/home/mdempsky/wd/go/test/typeparam/issue46461b.dir/b.go:7:8: could not import ./a (cannot import "a" (type parameter bound more than once), possibly version skew - reinstall package)

/cc @danscales

[mdempsky]

Relatedly, this package still crashes types2:

package p

type A[T interface{ A[T] }] interface{}

More complex example:

package p

type A[U interface{ A[U] }] interface{ M() A[U] }

type I interface{ A[I]; M() A[I] }

Caveat: I'm not certain whether these should be valid, but the type checker should at least gracefully report an error if not. (That said, I also know from experience how painful it is dealing with recursive and/or embedded interfaces.)

[griesemer]

I have a tentative fix for these, and they appear to be valid.

[cuonglm]

@mdempsky Is there anything left to do here?

CL 348738 adds a test. It looks like types2 and unified IR handle this correctly now, but iexport fails with:

/home/mdempsky/wd/go/test/typeparam/issue46461b.dir/b.go:7:8: could not import ./a (cannot import "a" (type parameter bound more than once), possibly version skew - reinstall package)

/cc @danscales

This seems issues #48280.

[mdempsky]

This seems issues #48280.

Yeah, that does look similar.

[danscales]

Do anyone know of a reasonable use case for a generic type that references itself in its own constraint?

If there is no obvious use case, I wonder if we should just disallow types that self-reference themselves in this way in Go 1.18, in order to cut down on complexity and the number of test cases. At the very least, seems like we should keep that as an option if the number of test cases multiplies.

cc @randall77

[gopherbot]

Change https://golang.org/cl/350330 mentions this issue: [dev.fuzz] all: merge master (b1bedc0) into dev.fuzz

[gopherbot]

Change https://golang.org/cl/350994 mentions this issue: [dev.fuzz] all: merge master (79159f2) into dev.fuzz

[gopherbot]

Change https://golang.org/cl/351969 mentions this issue: cmd/compile/internal/types2: delay union element checks

[gopherbot]

Change https://golang.org/cl/351971 mentions this issue: go/types: delay union element checks

[gopherbot]

Change https://golang.org/cl/361774 mentions this issue: [dev.boringcrypto] all: merge master (fa16efb) into dev.boringcrypto