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

spec: when unifying against interface types, consider common methods #60353

Closed
griesemer opened this issue May 23, 2023 · 10 comments
Closed

spec: when unifying against interface types, consider common methods #60353

griesemer opened this issue May 23, 2023 · 10 comments
Assignees
Labels
Proposal Proposal-Accepted TypeInference Issue is related to generic type inference
Milestone

Comments

@griesemer
Copy link
Contributor

griesemer commented May 23, 2023

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

@griesemer griesemer added Proposal TypeInference Issue is related to generic type inference labels May 23, 2023
@griesemer griesemer added this to the Go1.21 milestone May 23, 2023
@griesemer griesemer self-assigned this May 23, 2023
@gopherbot
Copy link

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

@gopherbot
Copy link

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

@ianlancetaylor
Copy link
Contributor

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
Copy link
Contributor Author

griesemer commented May 23, 2023

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 pushed a commit that referenced this issue May 23, 2023
…faces

When unifying two types A and B where one or both of them are
interfaces, consider the shared method signatures in unification.

1) If a defined interface (an interface with a type name) is unified
   with another (defined) interface, currently they must originate
   in the same type declaration (same origin) for unification to
   succeed. This is more restrictive than necessary for assignments:
   when interfaces are assigned to each other, corresponding methods
   must match, but the interfaces don't have to be identical.
   In unification, we don't know which direction the assignment is
   happening (or if we have an assignment in the first place), but
   in any case one interface must implement the other. Thus, we
   check that one interface has a subset of the methods of the other
   and that corresponding method signatures unify.
   The assignment or instantiation may still not be possible but that
   will be checked when instantiation and parameter passing is checked.
   If two interfaces are compared as part of another type during
   unification, the types must be equal. If they are not, unifying
   a method subset may still succeed (and possibly produce more type
   arguments), but that is ok: again, subsequent instantiation and
   assignment will fail if the types are indeed not identical.

2) In a non-interface type is unified with an interface, currently
   unification fails. If this unification is a consequence of an
   assignment (parameter passing), this is again too restrictive:
   the non-interface type must only implement the interface (possibly
   among other type set requirements). In any case, all methods of the
   interface type must be present in the non-interface type and unify
   with the corresponding interface methods. If they don't, unification
   will fail either way. If they do, we may infer additional type
   arguments. Again, the resulting types may still not be correct but
   that will be determined by the instantiation and parameter passing
   or assignment checks. If the non-interface type and the interface
   type appear as component of another type, unification may now
   produce additional type arguments. But that is again ok because the
   respective types won't pass instantiation or assignment checks since
   they are different types.

This CL introduces a new Config flag, EnableInterfaceInference, to
enable this new behavior. If not set, unification remains unchanged.
To be able to test the flag durign unification, a *Checker is passed
and stored with the unifier.

For #60353.
Fixes #41176.
Fixes #57192.

Change-Id: I6b167a9afa378d0682e9b101d9d86f5777308af7
Reviewed-on: https://go-review.googlesource.com/c/go/+/497015
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue May 23, 2023
…faces

When unifying two types A and B where one or both of them are
interfaces, consider the shared method signatures in unification.

1) If a defined interface (an interface with a type name) is unified
   with another (defined) interface, currently they must originate
   in the same type declaration (same origin) for unification to
   succeed. This is more restrictive than necessary for assignments:
   when interfaces are assigned to each other, corresponding methods
   must match, but the interfaces don't have to be identical.
   In unification, we don't know which direction the assignment is
   happening (or if we have an assignment in the first place), but
   in any case one interface must implement the other. Thus, we
   check that one interface has a subset of the methods of the other
   and that corresponding method signatures unify.
   The assignment or instantiation may still not be possible but that
   will be checked when instantiation and parameter passing is checked.
   If two interfaces are compared as part of another type during
   unification, the types must be equal. If they are not, unifying
   a method subset may still succeed (and possibly produce more type
   arguments), but that is ok: again, subsequent instantiation and
   assignment will fail if the types are indeed not identical.

2) In a non-interface type is unified with an interface, currently
   unification fails. If this unification is a consequence of an
   assignment (parameter passing), this is again too restrictive:
   the non-interface type must only implement the interface (possibly
   among other type set requirements). In any case, all methods of the
   interface type must be present in the non-interface type and unify
   with the corresponding interface methods. If they don't, unification
   will fail either way. If they do, we may infer additional type
   arguments. Again, the resulting types may still not be correct but
   that will be determined by the instantiation and parameter passing
   or assignment checks. If the non-interface type and the interface
   type appear as component of another type, unification may now
   produce additional type arguments. But that is again ok because the
   respective types won't pass instantiation or assignment checks since
   they are different types.

This CL introduces a new unifier flag, enableInterfaceInference, to
enable this new behavior. It is currently disabled.

For #60353.
For #41176.
For #57192.

Change-Id: I983d0ad5f043c7fe9d377dbb95f6b9342f36f45f
Reviewed-on: https://go-review.googlesource.com/c/go/+/497656
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
@rsc
Copy link
Contributor

rsc commented May 24, 2023

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
Copy link

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

@rsc
Copy link
Contributor

rsc commented May 31, 2023

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

gopherbot pushed a commit that referenced this issue May 31, 2023
For #39661.
For #41176.
For #51593.
For #52397.
For #57192.
For #58645.
For #58650.
For #58671.
For #59338.
For #59750.
For #60353.

Change-Id: Ib731c9f2879beb541f44cb10e40c36a8677d3ad4
Reviewed-on: https://go-review.googlesource.com/c/go/+/499282
TryBot-Bypass: Robert Griesemer <gri@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Nasfame pushed a commit to golangFame/go that referenced this issue Jun 4, 2023
For golang#39661.
For golang#41176.
For golang#51593.
For golang#52397.
For golang#57192.
For golang#58645.
For golang#58650.
For golang#58671.
For golang#59338.
For golang#59750.
For golang#60353.

Change-Id: Ib731c9f2879beb541f44cb10e40c36a8677d3ad4
Reviewed-on: https://go-review.googlesource.com/c/go/+/499282
TryBot-Bypass: Robert Griesemer <gri@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
@rsc
Copy link
Contributor

rsc commented Jun 7, 2023

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

@rsc rsc changed the title proposal: spec: when unifying against interface types, consider common methods spec: when unifying against interface types, consider common methods Jun 7, 2023
@griesemer
Copy link
Contributor Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Proposal Proposal-Accepted TypeInference Issue is related to generic type inference
Projects
Status: Accepted
Development

No branches or pull requests

4 participants