go/types, types2: document predicates on generic types

[findleyr]

Right now, go/types has limited functionality for computing predicates "modulo type parameters": signatures are considered identical modulo renaming of type parameters in their type parameter list:

func F[A ~int](A) {}
func G[B ~int](B) {}
func H[C int](C) {}

type T[D ~int] func(D)

In this example, the types of F and G are considered identical, because they have pairwise identical type parameter constraints and their signatures are identical after substituting type parameters. However, the signature of F is NOT identical to the signature of H (constraints don't match), and NOT identical to the underlying type of T (the signature itself does not have a type parameter list -- it uses type parameters from the declaration for T).

CL 379540 was intended to clean up some logic that existed to work around an earlier limitation that we didn't have instantiated methods. However, it inadvertently removed a "feature" that APIs like AssignableTo would somewhat work with uninstantiated types:

We ran into this example in kythe:

type Interface[T any] interface {
        Accept(T)
}

type Container[T any] struct {
        Element T
}

func (c Container[T]) Accept(t T) { c.Element = t }

Previously, we would report that Container is assignable to Interface (AssignableTo(Container, Interface) == true), because they would unify. However, this could be wrong, as in the following example:

type InterfaceInt[T ~int] interface {
        Accept(T)
}

type ContainerString[T ~string] struct {
        Element T
}

func (c ContainerString[T]) Accept(t T) { c.Element = t }

We would also have AssignableTo(ContainerString, InterfaceInt) == true, even though there is no instantiation for which this holds.

Related:

• cmd/go: go vet reports error: impossible type assertion: no type can implement both... for generic interface #50658 (comment). We don't expose any API for unification, and it would useful in several places.
• go/types: method signatures not identical modulo receiver type parameter names #49912 -- an outstanding bug for comparing method signatures modulo type parameters. However, notably fixing this bug would not address the behavior with respect to the Interface type above: the methods on Interface are parameterized by the type declaration parameters, not receiver type parameters.

Alternatively, callers could "instantiate" the types with identical arguments, but then the burden is pushed onto the caller to find type arguments that satisfy both type parameter lists, which is arbitrarily complicated. (EDIT: this wouldn't even really work: type parameters could be in arbitrary order, and so for the caller to even know which type parameters should correspond, they'd have to do the unification themselves).

I don't believe this affects type-checking, but matters for the API and for tools. We need to reconsider what is most useful here.

My initial thoughts are as follows: rather than what we currently do for function signatures, generalize to a limited form of unification in Identical, where type parameters are joined and then substituted in constraints.

This runs into a problem of "free type parameters"

func _[A *C, B *C, C any]() {
  var X func(A)
  var Y func(B)
}

type I[P *Q, Q any] interface{
  m(P)
}

The type of X and Y should not be identical. What about the type of X and the signature of I.m? (EDIT: X and Y do NOT have identical types).

CC @griesemer @mdempsky

[mdempsky]

I don't believe this affects type-checking

Why do you say that? In my experience, it's always possible to write type-checker test cases that exercise identity rules. E.g., adding _ = &X == &Y to the function above will only type check if X and Y's types are identical. But maybe I misunderstand your point.

The type of X and Y should probably be identical.

I think func(A) and func(B) should only be considered identical if we also consider A and B identical. And then we should probably consider them also identical to *C.

It seems kind of a niche use case though. If a type parameter can only be instantiated by a single type, there's not much reason to have it be a parameter in the first place.

[findleyr]

I think func(A) and func(B) should only be considered identical if we also consider A and B identical.

Oops, that was a broken example, sorry (initially I was using local type declarations, and didn't fix the example properly). A and B are definitely not identical there. UPDATED: the example illustrates that the type of X and Y should not be identical, as you point out.

[findleyr]

CC @schroederc for awareness that beta2 will break kythe edges between generic types, and that we're aware of the problem.

[mdempsky]

I see. The question is about how to handle type identity for parameterized types that haven't yet been instantiated?

Is there a use case for defining identity on such types? If not, I'm inclined to say type identity is undefined on parameterized, non-instantiated types, and types.Identical should panic if it finds such a type.

[griesemer]

Since generic types/functions can only be used in instantiated form (at which point they are not generic anymore) I believe @findleyr is correct that this shouldn't affect type checking of source code.

With respect to the API behavior, we need to determine the behavior for types.Identical as other API functions depend on its behavior.

If we have bound type parameters only, i.e., type parameters declared with the generic function/type, I believe we are in agreement that generic functions/types are identical if they can be made identical by renaming type parameters.

With respect to "free" type parameters, it seems that there are two different kinds:

1. type parameters declared with a generic type and used by methods of that type, and
2. type parameters declared in an outer scope (which must be a generic function).
   And then there may be combined uses of 1) and 2).

For 1), given a generic type T, when we consider the type of a method m of T, we should be able to consider the type of the method expression T.m while ignoring the first parameter (the receiver that has become an ordinary parameter) for signature identity. That type is a function and type parameters of T are effectively "bound" with T.m. It seems that we should be able to handle this case like the bound type parameter case.

Using the example from above:

type Interface[T any] interface {
        Accept(T)
}

type Container[T any] struct {
        Element T
}

func (c Container[T]) Accept(t T) { c.Element = t }

The respective method expression types are (pseudo code):

func Interface.Accept[T any](Interface[T], T)
func Container.Accept[T any](Container[T], T)

Ignoring the first parameter for signature identity leads to two identical function signatures. Doing the same with the second (invalid) example from above will lead to two different function signatures because the constraints don't match.

Fo assignability, besides checking all methods, we also need to check assignment compatibility of the receiver type to the interface (because of type sets). Again, type parameters and constraints must be identical modulo renaming.

For case 2) I think we can only compare types/functions that are declared within the same environment, i.e., enclosed within the same generic function. There can be only one such generic function enclosing parameterized types/functions because we don't allow function-local method, or type-local type declarations. So for the purposes of comparing generic function-local types or functions, it seems that type parameters by the enclosing function simply have to match exactly. In other words, local types/functions are always different from any other type or function that is not defined in the same scope.

[findleyr]

@griesemer and I had a long brainstorming session about this today, and finally arrived at the conclusion that there is no obvious way to define most predicates for uninstantiated generic types that Do The Right Thing.

For one, the two ms here must be identical:

type T1 int
type T2[P any] int

func (T1) m() {}
func (T2[P]) m() {}

and above we discuss making these ms identical:

type T1[P any] int
type T2[P any] int

func (T1[P]) m(P) {}
func (T2[P]) m(P) {}

but we don't want these m's to be identical?

type T1[P any] int
type T2[P ~int] int

func (T1[P]) m(P) {}
func (T2[P]) m(P) {}

Why do we care about constraints in the last, but not the first? This is incoherent, and more generally we concluded that any decision about the meaning of predicates on generic types runs into inconsistent and/or confusing behavior.

The problem is that there is more than one way to extend predicates to generic types: do all instantiations satisfy the predicate? Do any? Do we ignore constraints? Each of these could be useful interpretations in different situations. It's also a problem that some predicates (such as types.Implements) do not have access to an explicit type parameter list, and it's not clear that we can work around this limitation: the interpretations above rely on access to type parameter lists.

In the future we will probably want to expose APIs for substitution and unification that can efficiently answer any such question, but in the meantime we realized that the correct instantiations can answer many of them now, without additional APIs.

For example https://go.dev/cl/383094 extends types.AssignableTo in a way that we think would be useful for tools like Kythe, reporting if every instantiation V[A_1, ..., A_N] of a generic type V is assignable to the corresponding instantiation T[A_1, ..., A_N] of a generic type T.

So the good news is that we don't think any significant changes or new APIs are necessary for 1.18*, and this exercise (as well as related discussions around method identity) have given us a lot of insight into the APIs we should be thinking about for 1.19.

*well actually, we will probably want to remove the special handling that was added to types.Identical for generic signatures, since the same behavior can be replicated with instantiations similarly to CL 383094.

[findleyr]

*well actually, we will probably want to remove the special handling that was added to types.Identical for generic signatures, since the same behavior can be replicated with instantiations similarly to CL 383094.

Actually, I think what we have now is correct. The original reason for this decision still holds: for the purposes of type identity, it is consistent to treat signature type parameters the same way we treat ordinary parameters, ignoring their names. It is also helpful: with the current behavior (ignoring names), if two generic signatures are identical they will behave the same during instantiation: func F[P ~int] (P) will behave identically in instantiation as func G[Q ~int] (Q), returning the same resulting signature identity and failing in the same cases.

If we just ignore type parameters entirely, we lose some of this useful behavior. The F and G above will be considered different, even though they behave the same, but func H[P any]() will be considered the same as func K[Q ~int](), even though they behave differently (one can be instantiated with string whereas the other can't).

Furthermore, I no longer think that it's logically inconsistent not to ignore receiver type parameter names in signatures. As we've seen, methods are not really "generic" at all: they are all methods on an instantiated type -- instantiated with their receiver type parameters. This last point is rather subtle, and warrants exposition.

[findleyr]

Per #50887 (comment), I don't think there's anything more to do here other than try to document everything we've learned.

To preserve history, I'll change the title of this issue to track updating our documentation. I'm also going to remove the release-blocker label.

[gopherbot]

Change https://go.dev/cl/390039 mentions this issue: go/types: document that predicates are undefined on generic types

[gopherbot]

Change https://go.dev/cl/390575 mentions this issue: [release-branch.go1.18] go/types: document that predicates are undefined on generic types