cmd/compile: seemingly valid generic interface rejected

[griesemer]

I don't see a good reason why the following interface should be invalid:

type Element[E Element[E]] interface {
	Less(E) bool
}

Yet the compiler reports an invalid recursive type.
See example application here.

[gabyhelp]

Similar Issues

• go/types: accepts invalid `type T = interface{ f(T) }` #23139
• cmd/compile: "F is not a generic type" when F is a recursive generic interface #47836
• spec: disallow recursive embedded interfaces #1814

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

[magical]

Your playground example asserts that it is not possible to factor

type SortedList[E interface{ Less(E) bool }] []E

into

type SortedList[E Element[E]] []E
type Element[E] ...something...

But this definition seems to fit the bill:

type Element[E any] interface {
	Less(E) bool
}

https://go.dev/play/p/nqgWVreqDoW?v=gotip

Maybe i'm missing something but i'm not sure why Element's type argument would need to itself be constrained by Element. That does seem troublesomely recursive.

[magical]

If Go had a Self type, you could write something like this and avoid needing to pass E to Element as an argument, but of course it doesn't.

type SortedList[E Element] []E

type Element interface {
    Less(Self) bool
}

[timothy-king]

I think the most relevant comparison is with something that does work already, which is not naming the constraint:

type I[E interface{ Less(E) bool }] interface {
	Less(E) bool
}

[zephyrtronium]

I believe this is a duplicate of #63149.

[ruyi789]

Firstly, you can't create yourself, and secondly, you don't exist yet.

[arvidfm]

This kind of recursive constraint is needed to be able to express interfaces that reference types that in turn have type parameters with the same constraint. For instance:

type ElementList[E Element[E]] []E

func (el ElementList[_]) IsSorted() bool {
    for i := 0; i < len(el) - 1; i++ {
        // E must be Element to be able to call Less()
        if !el[i].Less(el[i+1]) {
            return false
        }
    }
    return true
}

type Element[E Element[E]] interface {
    Less(E) bool
    Children() ElementList[E] // E must be Element
}

The limitation discussed in this issue currently makes it impossible to define an interface like this.

I've run into this limitation multiple times, in particular in the context of self-descriptive types, i.e. types that model themselves - for example, a type that holds data from a database and also has methods that describe what fields correspond to what database columns, how the type relates to other types, etc. That often leads to this kind of recursive constraint and has resulted in a lot of refactoring to work around, generally having to make tradeoffs in regards to how ergonomic the API is, requiring more boilerplate or auxiliary types for the API user.

[griesemer]

@magical Thanks for pointing this out. I missed that while hastily writing this up so as not to forget about it before leaving for home. That said, there may still be situations where the circularity might be needed (see @arvidfm's example); and more generally there's a question as to whether there's a more principal reason why such declarations should or should not be valid.

@zephyrtronium Thanks for finding the duplicate #63149. Leaving both open for now to capture both discussions.

@arvidfm Just to be clear, the only thing that doesn't work in your example is the Children definition. The rest of the code will work with Element[E any] instead of Element[E Element[E]] (playground).

[magical]

@griesemer Indeed. Thank you @arvidfm for the example. I can see how mutually-recursive types would cause more difficulties. The self-recursive case seems much less compelling on its own since it seems easy to eliminate the recursion by hand.

[gopherbot]

Change https://go.dev/cl/605755 mentions this issue: go/types, types2: permit type cycles through type parameter lists