go/types, types2: fix interface unification

When unification of two types succeeds and at least one of them
is an interface, we must be more cautious about when to accept
the unification, to avoid order dependencies and unexpected
inference results.

The changes are localized and only affect matching against
interfaces; they further restrict what are valid unifications
(rather than allowing more code to pass). We may be able to
remove some of the restriotions in a future release.

See comments in code for a detailed description of the changes.

Also, factored out "asInterface" functionality into a function
to avoid needless repetition in the code.

Fixes #60933.
Fixes #60946.

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

4 files changed, 203 insertions, 22 deletions

diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index 3e2b299e49..0f1423ff98 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -270,6 +270,15 @@ func (u *unifier) inferred(tparams []*TypeParam) []Type {
 	return list
 }
 
+// asInterface returns the underlying type of x as an interface if
+// it is a non-type parameter interface. Otherwise it returns nil.
+func asInterface(x Type) (i *Interface) {
+	if _, ok := x.(*TypeParam); !ok {
+		i, _ = under(x).(*Interface)
+	}
+	return i
+}
+
 // nify implements the core unification algorithm which is an
 // adapted version of Checker.identical. For changes to that
 // code the corresponding changes should be made here.
@@ -364,11 +373,46 @@ func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
 		if x := u.at(px); x != nil {
 			// x has an inferred type which must match y
 			if u.nify(x, y, mode, p) {
-				// If we have a match, possibly through underlying types,
-				// and y is a defined type, make sure we record that type
+				// We have a match, possibly through underlying types.
+				xi := asInterface(x)
+				yi := asInterface(y)
+				_, xn := x.(*Named)
+				_, yn := y.(*Named)
+				// If we have two interfaces, what to do depends on
+				// whether they are named and their method sets.
+				if xi != nil && yi != nil {
+					// Both types are interfaces.
+					// If both types are defined types, they must be identical
+					// because unification doesn't know which type has the "right" name.
+					if xn && yn {
+						return Identical(x, y)
+					}
+					// In all other cases, the method sets must match.
+					// The types unified so we know that corresponding methods
+					// match and we can simply compare the number of methods.
+					// TODO(gri) We may be able to relax this rule and select
+					// the more general interface. But if one of them is a defined
+					// type, it's not clear how to choose and whether we introduce
+					// an order dependency or not. Requiring the same method set
+					// is conservative.
+					if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
+						return false
+					}
+				} else if xi != nil || yi != nil {
+					// One but not both of them are interfaces.
+					// In this case, either x or y could be viable matches for the corresponding
+					// type parameter, which means choosing either introduces an order dependence.
+					// Therefore, we must fail unification (go.dev/issue/60933).
+					return false
+				}
+				// If y is a defined type, make sure we record that type
 				// for type parameter x, which may have until now only
 				// recorded an underlying type (go.dev/issue/43056).
-				if _, ok := y.(*Named); ok {
+				// Either both types are interfaces, or neither type is.
+				// If both are interfaces, they have the same methods.
+				// TODO(gri) We probably can do this only for inexact
+				//           unification. Need to find a failure case.
+				if yn {
 					u.set(px, y)
 				}
 				return true
@@ -398,14 +442,8 @@ func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
 	if enableInterfaceInference && mode&exact == 0 {
 		// One or both interfaces may be defined types.
 		// Look under the name, but not under type parameters (go.dev/issue/60564).
-		var xi *Interface
-		if _, ok := x.(*TypeParam); !ok {
-			xi, _ = under(x).(*Interface)
-		}
-		var yi *Interface
-		if _, ok := y.(*TypeParam); !ok {
-			yi, _ = under(y).(*Interface)
-		}
+		xi := asInterface(x)
+		yi := asInterface(y)
 		// If we have two interfaces, check the type terms for equivalence,
 		// and unify common methods if possible.
 		if xi != nil && yi != nil {
diff --git a/src/go/types/unify.go b/src/go/types/unify.go
index 9c40394c59..1b1d875dad 100644
--- a/src/go/types/unify.go
+++ b/src/go/types/unify.go
@@ -272,6 +272,15 @@ func (u *unifier) inferred(tparams []*TypeParam) []Type {
 	return list
 }
 
+// asInterface returns the underlying type of x as an interface if
+// it is a non-type parameter interface. Otherwise it returns nil.
+func asInterface(x Type) (i *Interface) {
+	if _, ok := x.(*TypeParam); !ok {
+		i, _ = under(x).(*Interface)
+	}
+	return i
+}
+
 // nify implements the core unification algorithm which is an
 // adapted version of Checker.identical. For changes to that
 // code the corresponding changes should be made here.
@@ -366,11 +375,46 @@ func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
 		if x := u.at(px); x != nil {
 			// x has an inferred type which must match y
 			if u.nify(x, y, mode, p) {
-				// If we have a match, possibly through underlying types,
-				// and y is a defined type, make sure we record that type
+				// We have a match, possibly through underlying types.
+				xi := asInterface(x)
+				yi := asInterface(y)
+				_, xn := x.(*Named)
+				_, yn := y.(*Named)
+				// If we have two interfaces, what to do depends on
+				// whether they are named and their method sets.
+				if xi != nil && yi != nil {
+					// Both types are interfaces.
+					// If both types are defined types, they must be identical
+					// because unification doesn't know which type has the "right" name.
+					if xn && yn {
+						return Identical(x, y)
+					}
+					// In all other cases, the method sets must match.
+					// The types unified so we know that corresponding methods
+					// match and we can simply compare the number of methods.
+					// TODO(gri) We may be able to relax this rule and select
+					// the more general interface. But if one of them is a defined
+					// type, it's not clear how to choose and whether we introduce
+					// an order dependency or not. Requiring the same method set
+					// is conservative.
+					if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
+						return false
+					}
+				} else if xi != nil || yi != nil {
+					// One but not both of them are interfaces.
+					// In this case, either x or y could be viable matches for the corresponding
+					// type parameter, which means choosing either introduces an order dependence.
+					// Therefore, we must fail unification (go.dev/issue/60933).
+					return false
+				}
+				// If y is a defined type, make sure we record that type
 				// for type parameter x, which may have until now only
 				// recorded an underlying type (go.dev/issue/43056).
-				if _, ok := y.(*Named); ok {
+				// Either both types are interfaces, or neither type is.
+				// If both are interfaces, they have the same methods.
+				// TODO(gri) We probably can do this only for inexact
+				//           unification. Need to find a failure case.
+				if yn {
 					u.set(px, y)
 				}
 				return true
@@ -400,14 +444,8 @@ func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
 	if enableInterfaceInference && mode&exact == 0 {
 		// One or both interfaces may be defined types.
 		// Look under the name, but not under type parameters (go.dev/issue/60564).
-		var xi *Interface
-		if _, ok := x.(*TypeParam); !ok {
-			xi, _ = under(x).(*Interface)
-		}
-		var yi *Interface
-		if _, ok := y.(*TypeParam); !ok {
-			yi, _ = under(y).(*Interface)
-		}
+		xi := asInterface(x)
+		yi := asInterface(y)
 		// If we have two interfaces, check the type terms for equivalence,
 		// and unify common methods if possible.
 		if xi != nil && yi != nil {
diff --git a/src/internal/types/testdata/fixedbugs/issue60933.go b/src/internal/types/testdata/fixedbugs/issue60933.go
new file mode 100644
index 0000000000..9b10237e5d
--- /dev/null
+++ b/src/internal/types/testdata/fixedbugs/issue60933.go
@@ -0,0 +1,67 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package p
+
+import (
+	"io"
+	"os"
+)
+
+func g[T any](...T) {}
+
+// Interface and non-interface types do not match.
+func _() {
+	var file *os.File
+	g(file, io /* ERROR "type io.Writer of io.Discard does not match inferred type *os.File for T" */ .Discard)
+	g(file, os.Stdout)
+}
+
+func _() {
+	var a *os.File
+	var b any
+	g(a, a)
+	g(a, b /* ERROR "type any of b does not match inferred type *os.File for T" */)
+}
+
+var writer interface {
+	Write(p []byte) (n int, err error)
+}
+
+func _() {
+	var file *os.File
+	g(file, writer /* ERROR "type interface{Write(p []byte) (n int, err error)} of writer does not match inferred type *os.File for T" */)
+	g(writer, file /* ERROR "type *os.File of file does not match inferred type interface{Write(p []byte) (n int, err error)} for T" */)
+}
+
+// Different named interface types do not match.
+func _() {
+	g(io.ReadWriter(nil), io.ReadWriter(nil))
+	g(io.ReadWriter(nil), io /* ERROR "does not match" */ .Writer(nil))
+	g(io.Writer(nil), io /* ERROR "does not match" */ .ReadWriter(nil))
+}
+
+// Named and unnamed interface types match if they have the same methods.
+func _() {
+	g(io.Writer(nil), writer)
+	g(io.ReadWriter(nil), writer /* ERROR "does not match" */ )
+}
+
+// There must be no order dependency for named and unnamed interfaces.
+func f[T interface{ m(T) }](a, b T) {}
+
+type F interface {
+	m(F)
+}
+
+func _() {
+	var i F
+	var j interface {
+		m(F)
+	}
+
+	// order doesn't matter
+	f(i, j)
+	f(j, i)
+}
\ No newline at end of file
diff --git a/src/internal/types/testdata/fixedbugs/issue60946.go b/src/internal/types/testdata/fixedbugs/issue60946.go
new file mode 100644
index 0000000000..a66254b6d0
--- /dev/null
+++ b/src/internal/types/testdata/fixedbugs/issue60946.go
@@ -0,0 +1,38 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package p
+
+type Tn interface{ m() }
+type T1 struct{}
+type T2 struct{}
+
+func (*T1) m() {}
+func (*T2) m() {}
+
+func g[P any](...P) {}
+
+func _() {
+	var t interface{ m() }
+	var tn Tn
+	var t1 *T1
+	var t2 *T2
+
+	// these are ok (interface types only)
+	g(t, t)
+	g(t, tn)
+	g(tn, t)
+	g(tn, tn)
+
+	// these are not ok (interface and non-interface types)
+	g(t, t1 /* ERROR "does not match" */)
+	g(t1, t /* ERROR "does not match" */)
+	g(tn, t1 /* ERROR "does not match" */)
+	g(t1, tn /* ERROR "does not match" */)
+
+	g(t, t1 /* ERROR "does not match" */, t2)
+	g(t1, t2 /* ERROR "does not match" */, t)
+	g(tn, t1 /* ERROR "does not match" */, t2)
+	g(t1, t2 /* ERROR "does not match" */, tn)
+}