[dev.typeparams] cmd/compile/internal/types2: clean up type set/union intersection

- Eliminate the need for bottom type: This is now represented by
  an empty union (denoting the set of no types).

- Clean up type set intersection and incorporate tilde information
  in intersection operation and satisfaction tests.

- Minor cleanups along the way.

- Note: The intersection algorithm does not always compute the
        largest possible intersection. To be addressed in a follow-up CL.

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

1 files changed, 15 insertions, 25 deletions

diff --git a/src/cmd/compile/internal/types2/type.go b/src/cmd/compile/internal/types2/type.go
index aab75811b8..990b9d374c 100644
--- a/src/cmd/compile/internal/types2/type.go
+++ b/src/cmd/compile/internal/types2/type.go
@@ -376,7 +376,6 @@ func (t *Interface) Method(i int) *Func { t.Complete(); return t.allMethods[i] }
 // Empty reports whether t is the empty interface.
 func (t *Interface) Empty() bool {
 	t.Complete()
-	// A non-nil allTypes may still have length 0 but represents the bottom type.
 	return len(t.allMethods) == 0 && t.allTypes == nil
 }
 
@@ -431,11 +430,15 @@ func (t *Interface) iterate(f func(*Interface) bool, seen map[*Interface]bool) b
 //           "implements" predicate.
 func (t *Interface) isSatisfiedBy(typ Type) bool {
 	t.Complete()
-	if t.allTypes == nil {
-		return true
+	switch t := t.allTypes.(type) {
+	case nil:
+		return true // no type restrictions
+	case *Union:
+		r, _ := t.intersect(typ, false)
+		return r != nil
+	default:
+		return Identical(t, typ)
 	}
-	types := unpack(t.allTypes)
-	return includes(types, typ) || includes(types, under(typ))
 }
 
 // Complete computes the interface's method set. It must be called by users of
@@ -654,13 +657,11 @@ func (t *TypeParam) Bound() *Interface {
 	return iface
 }
 
-// optype returns a type's operational type. Except for
-// type parameters, the operational type is the same
-// as the underlying type (as returned by under). For
-// Type parameters, the operational type is determined
-// by the corresponding type bound's type list. The
-// result may be the bottom or top type, but it is never
-// the incoming type parameter.
+// optype returns a type's operational type. Except for type parameters,
+// the operational type is the same as the underlying type (as returned
+// by under). For Type parameters, the operational type is determined
+// by the corresponding type constraint. The result may be the top type,
+// but it is never the incoming type parameter.
 func optype(typ Type) Type {
 	if t := asTypeParam(typ); t != nil {
 		// If the optype is typ, return the top type as we have
@@ -733,20 +734,11 @@ var expandf func(Type) Type
 
 func init() { expandf = expand }
 
-// bottom represents the bottom of the type lattice.
-// It is the underlying type of a type parameter that
-// cannot be satisfied by any type, usually because
-// the intersection of type constraints left nothing).
-type bottom struct{}
-
-// theBottom is the singleton bottom type.
-var theBottom = &bottom{}
-
 // top represents the top of the type lattice.
 // It is the underlying type of a type parameter that
 // can be satisfied by any type (ignoring methods),
-// usually because the type constraint has no type
-// list.
+// because its type constraint contains no restrictions
+// besides methods.
 type top struct{}
 
 // theTop is the singleton top type.
@@ -766,7 +758,6 @@ func (t *Chan) Underlying() Type      { return t }
 func (t *Named) Underlying() Type     { return t.underlying }
 func (t *TypeParam) Underlying() Type { return t }
 func (t *instance) Underlying() Type  { return t }
-func (t *bottom) Underlying() Type    { return t }
 func (t *top) Underlying() Type       { return t }
 
 // Type-specific implementations of String.
@@ -783,7 +774,6 @@ func (t *Chan) String() string      { return TypeString(t, nil) }
 func (t *Named) String() string     { return TypeString(t, nil) }
 func (t *TypeParam) String() string { return TypeString(t, nil) }
 func (t *instance) String() string  { return TypeString(t, nil) }
-func (t *bottom) String() string    { return TypeString(t, nil) }
 func (t *top) String() string       { return TypeString(t, nil) }
 
 // under returns the true expanded underlying type.