[dev.typeparams] go/types: use comparable bit rather than ==() method

This is a port of CL 337354 to go/types, adjusted for the error
reporting API and to reposition a couple error messages in
issue47411.go2 (the go/types position is probably better).

A panic is also fixed in lookup.go when method lookup fails and static
== false. I'll send a fix for types2 in a separate CL.

For #47411

Change-Id: Icc48f03c3958695f581f10e8675c1f32434c424b
Reviewed-on: https://go-review.googlesource.com/c/go/+/339652
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

9 files changed, 71 insertions, 43 deletions

diff --git a/src/go/types/instantiate.go b/src/go/types/instantiate.go
index 28d68cad0e..2e6c20723b 100644
--- a/src/go/types/instantiate.go
+++ b/src/go/types/instantiate.go
@@ -173,6 +173,17 @@ func (check *Checker) satisfies(pos token.Pos, targ Type, tpar *TypeParam, smap
 	// the parameterized type.
 	iface = check.subst(pos, iface, smap).(*Interface)
 
+	// if iface is comparable, targ must be comparable
+	// TODO(gri) the error messages needs to be better, here
+	if iface.IsComparable() && !Comparable(targ) {
+		if tpar := asTypeParam(targ); tpar != nil && tpar.Bound().typeSet().IsTop() {
+			check.softErrorf(atPos(pos), _Todo, "%s has no constraints", targ)
+			return false
+		}
+		check.softErrorf(atPos(pos), _Todo, "%s does not satisfy comparable", targ)
+		return false
+	}
+
 	// targ must implement iface (methods)
 	// - check only if we have methods
 	if iface.NumMethods() > 0 {
@@ -188,10 +199,7 @@ func (check *Checker) satisfies(pos token.Pos, targ Type, tpar *TypeParam, smap
 			//           (print warning for now)
 			// Old warning:
 			// check.softErrorf(pos, "%s does not satisfy %s (warning: name not updated) = %s (missing method %s)", targ, tpar.bound, iface, m)
-			if m.name == "==" {
-				// We don't want to report "missing method ==".
-				check.softErrorf(atPos(pos), 0, "%s does not satisfy comparable", targ)
-			} else if wrong != nil {
+			if wrong != nil {
 				// TODO(gri) This can still report uninstantiated types which makes the error message
 				//           more difficult to read then necessary.
 				// TODO(rFindley) should this use parentheses rather than ':' for qualification?
diff --git a/src/go/types/interface.go b/src/go/types/interface.go
index 686dd7a786..51eff8fbdd 100644
--- a/src/go/types/interface.go
+++ b/src/go/types/interface.go
@@ -111,7 +111,7 @@ func (t *Interface) Method(i int) *Func { return t.typeSet().Method(i) }
 // Empty reports whether t is the empty interface.
 func (t *Interface) Empty() bool { return t.typeSet().IsTop() }
 
-// IsComparable reports whether interface t is or embeds the predeclared interface "comparable".
+// IsComparable reports whether each type in interface t's type set is comparable.
 func (t *Interface) IsComparable() bool { return t.typeSet().IsComparable() }
 
 // IsConstraint reports whether interface t is not just a method set.
diff --git a/src/go/types/lookup.go b/src/go/types/lookup.go
index 07baf2a48b..6d38db4523 100644
--- a/src/go/types/lookup.go
+++ b/src/go/types/lookup.go
@@ -307,8 +307,7 @@ func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method,
 			_, f := ityp.typeSet().LookupMethod(m.pkg, m.name)
 
 			if f == nil {
-				// if m is the magic method == we're ok (interfaces are comparable)
-				if m.name == "==" || !static {
+				if !static {
 					continue
 				}
 				return m, f
@@ -358,10 +357,6 @@ func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method,
 		// we must have a method (not a field of matching function type)
 		f, _ := obj.(*Func)
 		if f == nil {
-			// if m is the magic method == and V is comparable, we're ok
-			if m.name == "==" && Comparable(V) {
-				continue
-			}
 			return m, nil
 		}
 
diff --git a/src/go/types/predicates.go b/src/go/types/predicates.go
index 41e0c25d6b..caf72c2f2e 100644
--- a/src/go/types/predicates.go
+++ b/src/go/types/predicates.go
@@ -96,19 +96,6 @@ func comparable(T Type, seen map[Type]bool) bool {
 	}
 	seen[T] = true
 
-	// If T is a type parameter not constrained by any type
-	// (i.e., it's operational type is the top type),
-	// T is comparable if it has the == method. Otherwise,
-	// the operational type "wins". For instance
-	//
-	//     interface{ comparable; type []byte }
-	//
-	// is not comparable because []byte is not comparable.
-	// TODO(gri) this code is not 100% correct (see comment for TypeSet.IsComparable)
-	if t := asTypeParam(T); t != nil && optype(t) == theTop {
-		return t.Bound().IsComparable()
-	}
-
 	switch t := under(T).(type) {
 	case *Basic:
 		// assume invalid types to be comparable
@@ -126,9 +113,7 @@ func comparable(T Type, seen map[Type]bool) bool {
 	case *Array:
 		return comparable(t.elem, seen)
 	case *TypeParam:
-		return t.underIs(func(t Type) bool {
-			return comparable(t, seen)
-		})
+		return t.Bound().IsComparable()
 	}
 	return false
 }
diff --git a/src/go/types/sizeof_test.go b/src/go/types/sizeof_test.go
index c8758663ec..b892e7e521 100644
--- a/src/go/types/sizeof_test.go
+++ b/src/go/types/sizeof_test.go
@@ -47,7 +47,7 @@ func TestSizeof(t *testing.T) {
 		// Misc
 		{Scope{}, 44, 88},
 		{Package{}, 40, 80},
-		{TypeSet{}, 20, 40},
+		{TypeSet{}, 24, 48},
 	}
 	for _, test := range tests {
 		got := reflect.TypeOf(test.val).Size()
diff --git a/src/go/types/testdata/check/issues.go2 b/src/go/types/testdata/check/issues.go2
index c57f002303..6a1a10ad49 100644
--- a/src/go/types/testdata/check/issues.go2
+++ b/src/go/types/testdata/check/issues.go2
@@ -65,7 +65,7 @@ func _() {
 type T1[P interface{~uint}] struct{}
 
 func _[P any]() {
-    _ = T1[P /* ERROR P has no type constraints */ ]{}
+    _ = T1[P /* ERROR P has no constraints */ ]{}
 }
 
 // This is the original (simplified) program causing the same issue.
@@ -81,8 +81,8 @@ func (u T2[U]) Add1() U {
     return u.s + 1
 }
 
-func NewT2[U any]() T2[U /* ERROR U has no type constraints */ ] {
-    return T2[U /* ERROR U has no type constraints */ ]{}
+func NewT2[U any]() T2[U /* ERROR U has no constraints */ ] {
+    return T2[U /* ERROR U has no constraints */ ]{}
 }
 
 func _() {
diff --git a/src/go/types/testdata/fixedbugs/issue47411.go2 b/src/go/types/testdata/fixedbugs/issue47411.go2
new file mode 100644
index 0000000000..7326205863
--- /dev/null
+++ b/src/go/types/testdata/fixedbugs/issue47411.go2
@@ -0,0 +1,26 @@
+// Copyright 2021 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
+
+func f[_ comparable]()
+func g[_ interface{interface{comparable; ~int|~string}}]()
+
+func _[P comparable,
+        Q interface{ comparable; ~int|~string },
+        R any,                               // not comparable
+        S interface{ comparable; ~func() },  // not comparable
+]() {
+        _ = f[int]
+        _ = f[P]
+        _ = f[Q]
+        _ = f[func /* ERROR does not satisfy comparable */ ()]
+        _ = f[R /* ERROR R has no constraints */ ]
+
+        _ = g[int]
+        _ = g[P /* ERROR P has no type constraints */ ]
+        _ = g[Q]
+        _ = g[func /* ERROR does not satisfy comparable */()]
+        _ = g[R /* ERROR R has no constraints */ ]
+}
diff --git a/src/go/types/typeset.go b/src/go/types/typeset.go
index 3df2f1235f..226e438cc9 100644
--- a/src/go/types/typeset.go
+++ b/src/go/types/typeset.go
@@ -16,22 +16,31 @@ import (
 
 // A TypeSet represents the type set of an interface.
 type TypeSet struct {
+	comparable bool // if set, the interface is or embeds comparable
 	// TODO(gri) consider using a set for the methods for faster lookup
 	methods []*Func // all methods of the interface; sorted by unique ID
 	types   Type    // typically a *Union; nil means no type restrictions
 }
 
 // IsTop reports whether type set s is the top type set (corresponding to the empty interface).
-func (s *TypeSet) IsTop() bool { return len(s.methods) == 0 && s.types == nil }
+func (s *TypeSet) IsTop() bool { return !s.comparable && len(s.methods) == 0 && s.types == nil }
 
 // IsMethodSet reports whether the type set s is described by a single set of methods.
-func (s *TypeSet) IsMethodSet() bool { return s.types == nil && !s.IsComparable() }
+func (s *TypeSet) IsMethodSet() bool { return !s.comparable && s.types == nil }
 
 // IsComparable reports whether each type in the set is comparable.
 // TODO(gri) this is not correct - there may be s.types values containing non-comparable types
 func (s *TypeSet) IsComparable() bool {
-	_, m := s.LookupMethod(nil, "==")
-	return m != nil
+	if s.types == nil {
+		return s.comparable
+	}
+	tcomparable := s.underIs(func(u Type) bool {
+		return Comparable(u)
+	})
+	if !s.comparable {
+		return tcomparable
+	}
+	return s.comparable && tcomparable
 }
 
 // NumMethods returns the number of methods available.
@@ -54,6 +63,12 @@ func (s *TypeSet) String() string {
 
 	var buf bytes.Buffer
 	buf.WriteByte('{')
+	if s.comparable {
+		buf.WriteString(" comparable")
+		if len(s.methods) > 0 || s.types != nil {
+			buf.WriteByte(';')
+		}
+	}
 	for i, m := range s.methods {
 		if i > 0 {
 			buf.WriteByte(';')
@@ -205,6 +220,9 @@ func computeTypeSet(check *Checker, pos token.Pos, ityp *Interface) *TypeSet {
 		switch t := under(typ).(type) {
 		case *Interface:
 			tset := computeTypeSet(check, pos, t)
+			if tset.comparable {
+				ityp.tset.comparable = true
+			}
 			for _, m := range tset.methods {
 				addMethod(pos, m, false) // use embedding position pos rather than m.pos
 
diff --git a/src/go/types/universe.go b/src/go/types/universe.go
index 489587f393..e2b3bd7c18 100644
--- a/src/go/types/universe.go
+++ b/src/go/types/universe.go
@@ -89,23 +89,19 @@ func defPredeclaredTypes() {
 		res := NewVar(token.NoPos, nil, "", Typ[String])
 		sig := NewSignature(nil, nil, NewTuple(res), false)
 		err := NewFunc(token.NoPos, nil, "Error", sig)
-		ityp := NewInterfaceType([]*Func{err}, nil)
+		ityp := &Interface{obj, []*Func{err}, nil, nil, true, nil}
 		computeTypeSet(nil, token.NoPos, ityp) // prevent races due to lazy computation of tset
 		typ := NewNamed(obj, ityp, nil)
 		sig.recv = NewVar(token.NoPos, nil, "", typ)
 		def(obj)
 	}
 
-	// type comparable interface{ ==() }
+	// type comparable interface{ /* type set marked comparable */ }
 	{
 		obj := NewTypeName(token.NoPos, nil, "comparable", nil)
 		obj.setColor(black)
-		sig := NewSignature(nil, nil, nil, false)
-		eql := NewFunc(token.NoPos, nil, "==", sig)
-		ityp := NewInterfaceType([]*Func{eql}, nil)
-		computeTypeSet(nil, token.NoPos, ityp) // prevent races due to lazy computation of tset
-		typ := NewNamed(obj, ityp, nil)
-		sig.recv = NewVar(token.NoPos, nil, "", typ)
+		ityp := &Interface{obj, nil, nil, nil, true, &TypeSet{true, nil, nil}}
+		NewNamed(obj, ityp, nil)
 		def(obj)
 	}
 }