[dev.typeparams] go/types: use type terms to represent unions

This is a straightforward port of CL 338092 to go/types.

Change-Id: I414ec0ad95648c201e85fd2b4f494b1206c658e7
Reviewed-on: https://go-review.googlesource.com/c/go/+/339674
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>

11 files changed, 130 insertions, 79 deletions

diff --git a/src/go/types/infer.go b/src/go/types/infer.go
index f3f69e01b6..6e70a103e7 100644
--- a/src/go/types/infer.go
+++ b/src/go/types/infer.go
@@ -303,7 +303,7 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 		}
 
 	case *Union:
-		return w.isParameterizedList(t.types)
+		return w.isParameterizedTermList(t.terms)
 
 	case *Signature:
 		// t.tparams may not be nil if we are looking at a signature
@@ -331,7 +331,7 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 		return w.isParameterized(t.elem)
 
 	case *Named:
-		return w.isParameterizedList(t.targs)
+		return w.isParameterizedTypeList(t.targs)
 
 	case *TypeParam:
 		// t must be one of w.tparams
@@ -344,7 +344,7 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 	return false
 }
 
-func (w *tpWalker) isParameterizedList(list []Type) bool {
+func (w *tpWalker) isParameterizedTypeList(list []Type) bool {
 	for _, t := range list {
 		if w.isParameterized(t) {
 			return true
@@ -353,6 +353,15 @@ func (w *tpWalker) isParameterizedList(list []Type) bool {
 	return false
 }
 
+func (w *tpWalker) isParameterizedTermList(list []*term) bool {
+	for _, t := range list {
+		if w.isParameterized(t.typ) {
+			return true
+		}
+	}
+	return false
+}
+
 // inferB returns the list of actual type arguments inferred from the type parameters'
 // bounds and an initial set of type arguments. If type inference is impossible because
 // unification fails, an error is reported if report is set to true, the resulting types
@@ -461,7 +470,8 @@ func (check *Checker) structuralType(constraint Type) Type {
 		if u, _ := types.(*Union); u != nil {
 			if u.NumTerms() == 1 {
 				// TODO(gri) do we need to respect tilde?
-				return u.types[0]
+				t, _ := u.Term(0)
+				return t
 			}
 			return nil
 		}
diff --git a/src/go/types/interface.go b/src/go/types/interface.go
index 51eff8fbdd..e98e40179c 100644
--- a/src/go/types/interface.go
+++ b/src/go/types/interface.go
@@ -34,7 +34,7 @@ func (t *Interface) is(f func(Type, bool) bool) bool {
 		// TODO(gri) should settle on top or nil to represent this case
 		return false // we must have at least one type! (was bug)
 	case *Union:
-		return t.is(func(typ Type, tilde bool) bool { return f(typ, tilde) })
+		return t.is(func(t *term) bool { return f(t.typ, t.tilde) })
 	default:
 		return f(t, false)
 	}
@@ -266,8 +266,8 @@ func (check *Checker) interfaceType(ityp *Interface, iface *ast.InterfaceType, d
 	// (don't sort embeddeds: they must correspond to *embedPos entries)
 
 	// Compute type set with a non-nil *Checker as soon as possible
-	// to report any errors. Subsequent uses of type sets should be
-	// using this computed type set and won't need to pass in a *Checker.
+	// to report any errors. Subsequent uses of type sets will use
+	// this computed type set and won't need to pass in a *Checker.
 	check.later(func() { computeTypeSet(check, iface.Pos(), ityp) })
 }
 
diff --git a/src/go/types/operand.go b/src/go/types/operand.go
index 1d0f5b80b6..c605cf781c 100644
--- a/src/go/types/operand.go
+++ b/src/go/types/operand.go
@@ -255,13 +255,13 @@ func (x *operand) assignableTo(check *Checker, T Type, reason *string) (bool, er
 	// x is an untyped value representable by a value of type T.
 	if isUntyped(Vu) {
 		if t, ok := Tu.(*Union); ok {
-			return t.is(func(t Type, tilde bool) bool {
+			return t.is(func(t *term) bool {
 				// TODO(gri) this could probably be more efficient
-				if tilde {
+				if t.tilde {
 					// TODO(gri) We need to check assignability
 					//           for the underlying type of x.
 				}
-				ok, _ := x.assignableTo(check, t, reason)
+				ok, _ := x.assignableTo(check, t.typ, reason)
 				return ok
 			}), _IncompatibleAssign
 		}
diff --git a/src/go/types/predicates.go b/src/go/types/predicates.go
index caf72c2f2e..579d35da42 100644
--- a/src/go/types/predicates.go
+++ b/src/go/types/predicates.go
@@ -238,20 +238,8 @@ func identical(x, y Type, cmpTags bool, p *ifacePair) bool {
 		// types - each type appears exactly once. Thus, two union types
 		// must contain the same number of types to have chance of
 		// being equal.
-		if y, ok := y.(*Union); ok && x.NumTerms() == y.NumTerms() {
-			// Every type in x.types must be in y.types.
-			// Quadratic algorithm, but probably good enough for now.
-			// TODO(gri) we need a fast quick type ID/hash for all types.
-		L:
-			for i, xt := range x.types {
-				for j, yt := range y.types {
-					if Identical(xt, yt) && x.tilde[i] == y.tilde[j] {
-						continue L // x is in y.types
-					}
-				}
-				return false // x is not in y.types
-			}
-			return true
+		if y, ok := y.(*Union); ok {
+			return identicalTerms(x.terms, y.terms)
 		}
 
 	case *Interface:
diff --git a/src/go/types/sizeof_test.go b/src/go/types/sizeof_test.go
index b892e7e521..75122b0273 100644
--- a/src/go/types/sizeof_test.go
+++ b/src/go/types/sizeof_test.go
@@ -26,12 +26,13 @@ func TestSizeof(t *testing.T) {
 		{Pointer{}, 8, 16},
 		{Tuple{}, 12, 24},
 		{Signature{}, 28, 56},
-		{Union{}, 24, 48},
+		{Union{}, 12, 24},
 		{Interface{}, 40, 80},
 		{Map{}, 16, 32},
 		{Chan{}, 12, 24},
 		{Named{}, 80, 152},
 		{TypeParam{}, 28, 48},
+		{term{}, 12, 24},
 		{top{}, 0, 0},
 
 		// Objects
diff --git a/src/go/types/subst.go b/src/go/types/subst.go
index c05e51d425..322e30d357 100644
--- a/src/go/types/subst.go
+++ b/src/go/types/subst.go
@@ -148,12 +148,12 @@ func (subst *subster) typ(typ Type) Type {
 		}
 
 	case *Union:
-		types, copied := subst.typeList(t.types)
+		terms, copied := subst.termList(t.terms)
 		if copied {
 			// TODO(gri) Remove duplicates that may have crept in after substitution
 			//           (unlikely but possible). This matters for the Identical
 			//           predicate on unions.
-			return newUnion(types, t.tilde)
+			return &Union{terms}
 		}
 
 	case *Interface:
@@ -393,3 +393,21 @@ func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
 	}
 	return
 }
+
+func (subst *subster) termList(in []*term) (out []*term, copied bool) {
+	out = in
+	for i, t := range in {
+		if u := subst.typ(t.typ); u != t.typ {
+			if !copied {
+				// first function that got substituted => allocate new out slice
+				// and copy all functions
+				new := make([]*term, len(in))
+				copy(new, out)
+				out = new
+				copied = true
+			}
+			out[i] = &term{t.tilde, u}
+		}
+	}
+	return
+}
diff --git a/src/go/types/testdata/examples/constraints.go2 b/src/go/types/testdata/examples/constraints.go2
index d9805fe694..28aa19bb12 100644
--- a/src/go/types/testdata/examples/constraints.go2
+++ b/src/go/types/testdata/examples/constraints.go2
@@ -31,9 +31,9 @@ type (
 	_ interface{int|~ /* ERROR duplicate term int */ int }
 	_ interface{~int|~ /* ERROR duplicate term int */ int }
 
-	// For now we do not permit interfaces with ~ or in unions.
-	_ interface{~ /* ERROR cannot use interface */ interface{}}
-	_ interface{int|interface /* ERROR cannot use interface */ {}}
+	// For now we do not permit interfaces with methods in unions.
+	_ interface{~ /* ERROR invalid use of ~ */ interface{}}
+	_ interface{int|interface /* ERROR cannot use .* in union */ { m() }}
 )
 
 type (
diff --git a/src/go/types/type.go b/src/go/types/type.go
index b575b11e4e..2ad89d9705 100644
--- a/src/go/types/type.go
+++ b/src/go/types/type.go
@@ -60,7 +60,7 @@ func optype(typ Type) Type {
 			// If we have a union with a single entry, ignore
 			// any tilde because under(~t) == under(t).
 			if u, _ := a.(*Union); u != nil && u.NumTerms() == 1 {
-				a = u.types[0]
+				a, _ = u.Term(0)
 			}
 			if a != typ {
 				// a != typ and a is a type parameter => under(a) != typ, so this is ok
diff --git a/src/go/types/typeset.go b/src/go/types/typeset.go
index 226e438cc9..cbd867dd95 100644
--- a/src/go/types/typeset.go
+++ b/src/go/types/typeset.go
@@ -43,6 +43,13 @@ func (s *TypeSet) IsComparable() bool {
 	return s.comparable && tcomparable
 }
 
+// TODO(gri) IsTypeSet is not a great name. Find a better one.
+
+// IsTypeSet reports whether the type set s is represented by a finite set of underlying types.
+func (s *TypeSet) IsTypeSet() bool {
+	return !s.comparable && len(s.methods) == 0
+}
+
 // NumMethods returns the number of methods available.
 func (s *TypeSet) NumMethods() int { return len(s.methods) }
 
diff --git a/src/go/types/typestring.go b/src/go/types/typestring.go
index 74b18a9ec8..c0c69624ec 100644
--- a/src/go/types/typestring.go
+++ b/src/go/types/typestring.go
@@ -163,14 +163,14 @@ func writeType(buf *bytes.Buffer, typ Type, qf Qualifier, visited []Type) {
 			buf.WriteString("⊥")
 			break
 		}
-		for i, e := range t.types {
+		for i, t := range t.terms {
 			if i > 0 {
 				buf.WriteByte('|')
 			}
-			if t.tilde[i] {
+			if t.tilde {
 				buf.WriteByte('~')
 			}
-			writeType(buf, e, qf, visited)
+			writeType(buf, t.typ, qf, visited)
 		}
 
 	case *Interface:
diff --git a/src/go/types/union.go b/src/go/types/union.go
index 556be46bf6..a56f9d29f3 100644
--- a/src/go/types/union.go
+++ b/src/go/types/union.go
@@ -13,10 +13,8 @@ import (
 // API
 
 // A Union represents a union of terms.
-// A term is a type with a ~ (tilde) flag.
 type Union struct {
-	types []Type // types are unique
-	tilde []bool // if tilde[i] is set, terms[i] is of the form ~T
+	terms []*term
 }
 
 // NewUnion returns a new Union type with the given terms (types[i], tilde[i]).
@@ -24,9 +22,9 @@ type Union struct {
 // of no types.
 func NewUnion(types []Type, tilde []bool) *Union { return newUnion(types, tilde) }
 
-func (u *Union) IsEmpty() bool           { return len(u.types) == 0 }
-func (u *Union) NumTerms() int           { return len(u.types) }
-func (u *Union) Term(i int) (Type, bool) { return u.types[i], u.tilde[i] }
+func (u *Union) IsEmpty() bool           { return len(u.terms) == 0 }
+func (u *Union) NumTerms() int           { return len(u.terms) }
+func (u *Union) Term(i int) (Type, bool) { t := u.terms[i]; return t.typ, t.tilde }
 
 func (u *Union) Underlying() Type { return u }
 func (u *Union) String() string   { return TypeString(u, nil) }
@@ -42,18 +40,20 @@ func newUnion(types []Type, tilde []bool) *Union {
 		return emptyUnion
 	}
 	t := new(Union)
-	t.types = types
-	t.tilde = tilde
+	t.terms = make([]*term, len(types))
+	for i, typ := range types {
+		t.terms[i] = &term{tilde[i], typ}
+	}
 	return t
 }
 
-// is reports whether f returned true for all terms (type, tilde) of u.
-func (u *Union) is(f func(Type, bool) bool) bool {
+// is reports whether f returns true for all terms of u.
+func (u *Union) is(f func(*term) bool) bool {
 	if u.IsEmpty() {
 		return false
 	}
-	for i, t := range u.types {
-		if !f(t, u.tilde[i]) {
+	for _, t := range u.terms {
+		if !f(t) {
 			return false
 		}
 	}
@@ -65,8 +65,8 @@ func (u *Union) underIs(f func(Type) bool) bool {
 	if u.IsEmpty() {
 		return false
 	}
-	for _, t := range u.types {
-		if !f(under(t)) {
+	for _, t := range u.terms {
+		if !f(under(t.typ)) {
 			return false
 		}
 	}
@@ -86,7 +86,7 @@ func parseUnion(check *Checker, tlist []ast.Expr) Type {
 	}
 
 	// Ensure that each type is only present once in the type list.
-	// It's ok to do this check at the end because it's not a requirement
+	// It's ok to do this check later because it's not a requirement
 	// for correctness of the code.
 	// Note: This is a quadratic algorithm, but unions tend to be short.
 	check.later(func() {
@@ -99,7 +99,7 @@ func parseUnion(check *Checker, tlist []ast.Expr) Type {
 			x := tlist[i]
 			pos := x.Pos()
 			// We may not know the position of x if it was a typechecker-
-			// introduced ~T type of a type list entry T. Use the position
+			// introduced ~T term for a type list entry T. Use the position
 			// of T instead.
 			// TODO(rfindley) remove this test once we don't support type lists anymore
 			if !pos.IsValid() {
@@ -109,13 +109,24 @@ func parseUnion(check *Checker, tlist []ast.Expr) Type {
 			}
 
 			u := under(t)
-			if tilde[i] && !Identical(u, t) {
-				check.errorf(x, _Todo, "invalid use of ~ (underlying type of %s is %s)", t, u)
-				continue // don't report another error for t
+			f, _ := u.(*Interface)
+			if tilde[i] {
+				if f != nil {
+					check.errorf(x, _Todo, "invalid use of ~ (%s is an interface)", t)
+					continue // don't report another error for t
+				}
+
+				if !Identical(u, t) {
+					check.errorf(x, _Todo, "invalid use of ~ (underlying type of %s is %s)", t, u)
+					continue // don't report another error for t
+				}
 			}
-			if _, ok := u.(*Interface); ok {
-				// A single type with a ~ is a single-term union.
-				check.errorf(atPos(pos), _Todo, "cannot use interface %s with ~ or inside a union (implementation restriction)", t)
+
+			// Stand-alone embedded interfaces are ok and are handled by the single-type case
+			// in the beginning. Embedded interfaces with tilde are excluded above. If we reach
+			// here, we must have at least two terms in the union.
+			if f != nil && !f.typeSet().IsTypeSet() {
+				check.errorf(atPos(pos), _Todo, "cannot use %s in union (interface contains methods)", t)
 				continue // don't report another error for t
 			}
 
@@ -167,25 +178,7 @@ func intersect(x, y Type) (r Type) {
 	yu, _ := y.(*Union)
 	switch {
 	case xu != nil && yu != nil:
-		// Quadratic algorithm, but good enough for now.
-		// TODO(gri) fix asymptotic performance
-		var types []Type
-		var tilde []bool
-		for j, y := range yu.types {
-			yt := yu.tilde[j]
-			if r, rt := xu.intersect(y, yt); r != nil {
-				// Terms x[i] and y[j] match: Select the one that
-				// is not a ~t because that is the intersection
-				// type. If both are ~t, they are identical:
-				//  T ∩  T =  T
-				//  T ∩ ~t =  T
-				// ~t ∩  T =  T
-				// ~t ∩ ~t = ~t
-				types = append(types, r)
-				tilde = append(tilde, rt)
-			}
-		}
-		return newUnion(types, tilde)
+		return &Union{intersectTerms(xu.terms, yu.terms)}
 
 	case xu != nil:
 		if r, _ := xu.intersect(y, false); r != nil {
@@ -219,14 +212,16 @@ func includes(list []Type, typ Type) bool {
 // intersect computes the intersection of the union u and term (y, yt)
 // and returns the intersection term, if any. Otherwise the result is
 // (nil, false).
+// TODO(gri) this needs to cleaned up/removed once we switch to lazy
+//           union type set computation.
 func (u *Union) intersect(y Type, yt bool) (Type, bool) {
 	under_y := under(y)
-	for i, x := range u.types {
-		xt := u.tilde[i]
+	for _, x := range u.terms {
+		xt := x.tilde
 		// determine which types xx, yy to compare
-		xx := x
+		xx := x.typ
 		if yt {
-			xx = under(x)
+			xx = under(xx)
 		}
 		yy := y
 		if xt {
@@ -242,3 +237,35 @@ func (u *Union) intersect(y Type, yt bool) (Type, bool) {
 	}
 	return nil, false
 }
+
+func identicalTerms(list1, list2 []*term) bool {
+	if len(list1) != len(list2) {
+		return false
+	}
+	// Every term in list1 must be in list2.
+	// Quadratic algorithm, but probably good enough for now.
+	// TODO(gri) we need a fast quick type ID/hash for all types.
+L:
+	for _, x := range list1 {
+		for _, y := range list2 {
+			if x.equal(y) {
+				continue L // x is in list2
+			}
+		}
+		return false
+	}
+	return true
+}
+
+func intersectTerms(list1, list2 []*term) (list []*term) {
+	// Quadratic algorithm, but good enough for now.
+	// TODO(gri) fix asymptotic performance
+	for _, x := range list1 {
+		for _, y := range list2 {
+			if r := x.intersect(y); r != nil {
+				list = append(list, r)
+			}
+		}
+	}
+	return
+}