spec: when unifying against interface types, consider common methods

[griesemer]

Background

Currently, type inference fails when trying to unify two interfaces of different type, or an interface and a non-interface type, even though the respective types may have the correct methods and type sets if they could be unified somehow.

Example 1 (see #57192)

type I1[T any] interface {
	m1(T)
}
type I2[T any] interface {
	I1[T]
	m2(T)
}

var V1 I1[int]
var V2 I2[int]

func g[T any](I1[T]) {}
func _() {
	g(V1)
	g(V2) // ERROR type I2[int] of V2 does not match I1[T] (cannot infer T)
}

In this case, I2 implements I1 if the type parameters T of I1 and I2 could be inferred to be int. Currently (Go 1.20) the compiler reports an error in this case.

Example 2 (see #41176):

type S struct{}

func (S) M() byte {
	return 0
}

type I[T any] interface {
	M() T
}

func f[T any](x I[T]) {}

func _() {
	f(S{}) // ERROR type S of S{} does not match I[T] (cannot infer T)
}

In this case, S implements I if the type parameter T of I could be inferred to be byte. Currently (Go 1.20) the compiler reports an error in this case.

The problem in the first case is that unification requires matching interfaces to be identical or from the same type declaration. The problem in the second case is that unification fails if the two types being compared (interface vs struct) are not of the same kind.

This does not accurately reflect Go's assignment rules for interfaces.

Proposal

We propose to change the type inference rules such that when interfaces are involved, type unification considers Go's assignment rules for interfaces. Specifically:

1. Two (unnamed) interfaces unify if they have identical type terms and if one of the interfaces has a subset of the methods of the other and the methods in this subset unify.
2. An interface I and a non-interface type T unify if all the methods of I exist in T and unify.
3. For two named (defined) types originating in different type declarations where one or both of the underlying types is an interface, use rule 1) or 2) respectively to unify the underlying types.

When unifying two defined types that are both interfaces originating in the same type declaration, use the current unification approach (type parameters must unify); i.e. there's no change in this case.

This is the entire proposal.

Discussion

The proposed changes are fully backward-compatible: the only case to consider is the unification of two interfaces (unifying an interface against a non-interface always failed in the past). In Go 1.20, two unnamed interfaces unify only if they have identical type terms, the same number of methods, and all methods unify. The proposed new rule will succeed in this case as well.

We don't change the existing behavior when unifying two defined types that are both interfaces originating in the same type declaration: first of all, the methods will unify if the type arguments unify (it's the same interface), but we also want to preserve existing behavior when type parameters are not used:

type T[_ any] any

func f[P any](T[P]) {}

func _() {
	var x T[string]
	f(x)
}

In this case we want to infer the type argument for P to be int string (as we do now). If we were only considering methods, this code would not work anymore. (That said, arguably this is a bug, see #60377: if we accept this as a bug then we don't need to separate between named/unnamed interface types for unification.)

Currently, if we try to unify two different interfaces, unification fails. The proposed new rule effectively means that one interface must implement the other. This may not be sufficient (e.g. if the interfaces are component types of other types) but if the two interfaces are compatible at all, it is a necessary condition.

Similarly, when unifying a non-interface type T with an interface I, at the very least T must implement all the methods of I; i.e. they must exist and they must unify. There are additional restrictions with respect to the type set but it's ok to ignore them for now (see next paragraph).

The proposed changes allow us to infer additional type arguments where unification (and thus type inference) currently fails immediately. It is still possible that the inferred type arguments lead to invalid instantiations and invalid parameter passing/assignments, in which case we will fail later.

Implementation

We have implemented this proposal (CL 497015) and enabled it through CL 497657.

Should this proposal not be accepted or should we run into problems during the freeze, the implementation can be safely disabled by issuing a revert of CL 497657.

cc: @ianlancetaylor @findleyr for visibility

[gopherbot]

Change https://go.dev/cl/497015 mentions this issue: go/types, types2: consider shared methods when unifying against interfaces

[gopherbot]

Change https://go.dev/cl/497119 mentions this issue: cmd/compile: enable inference across interface methods

[ianlancetaylor]

In this case we want to infer the type argument for P to be int

I think you mean string rather than int.

Two interfaces unify if they have identical type terms and methods common to (i.e., shared by) both interfaces unify.

This implies that two non-empty interfaces with no methods in common will unify. Is that useful? We won't be able to assign a value of one interface type to the other interface type. At least at the top level, this means that a function call can't work.

Should the rule instead be that one interface must have a subset of the methods of the other, and the common methods must unify? Or are there cases where requiring a subset will cause inference to fail unreasonably?

[griesemer]

Agreed that requiring a subset would be better. The proposed rule is simpler but may produce false positives (that then lead to an error later). The subset approach doesn't cause any problems with existing code and tests.

The proposal and implementation have been updated accordingly.

[gopherbot]

Change https://go.dev/cl/497656 mentions this issue: go/types, types2: consider shared methods when unifying against interfaces

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[gopherbot]

Change https://go.dev/cl/499282 mentions this issue: doc/go1.21: document type inference changes

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[griesemer]

This has been implemented and documented in the spec for Go 1.21.
Closing.