[dev.typeparams] cmd/compile/internal/types2: replace Sum type with Union type

- We still mostly ignore the tilde information.

- More consistent naming: A Union term is the pair (type, tilde).
  Rename Union.terms to Union.types; the Union.types and Union.tilde
  slices make up the Union terms.

- Replace Sum.is with Union.underIs: underIs iterates through all
  union terms and calls its argument function with the underlying
  type of the term (and thus can ignore the tilde information).
  This also eliminates the need to call under in the argument
  function.

- Added Union.is for situations where we need to consider the tilde
  information for each Union term.

Change-Id: I70fcf1813e072651dc0f61d52d5555642ee762fd
Reviewed-on: https://go-review.googlesource.com/c/go/+/323274
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>

1 files changed, 97 insertions, 14 deletions

diff --git a/src/cmd/compile/internal/types2/union.go b/src/cmd/compile/internal/types2/union.go
index 70dc3bc360..a5ef721ee6 100644
--- a/src/cmd/compile/internal/types2/union.go
+++ b/src/cmd/compile/internal/types2/union.go
@@ -10,16 +10,16 @@ import "cmd/compile/internal/syntax"
 // API
 
 // A Union represents a union of terms.
-// A term is a type, possibly with a ~ (tilde) indication.
+// A term is a type with a ~ (tilde) flag.
 type Union struct {
-	terms []Type // terms are unique
+	types []Type // types are unique
 	tilde []bool // if tilde[i] is set, terms[i] is of the form ~T
 }
 
-func NewUnion(terms []Type, tilde []bool) Type { return newUnion(terms, tilde) }
+func NewUnion(types []Type, tilde []bool) Type { return newUnion(types, tilde) }
 
-func (u *Union) NumTerms() int           { return len(u.terms) }
-func (u *Union) Term(i int) (Type, bool) { return u.terms[i], u.tilde[i] }
+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) Underlying() Type { return u }
 func (u *Union) String() string   { return TypeString(u, nil) }
@@ -27,26 +27,52 @@ func (u *Union) String() string   { return TypeString(u, nil) }
 // ----------------------------------------------------------------------------
 // Implementation
 
-func newUnion(terms []Type, tilde []bool) Type {
-	assert(len(terms) == len(tilde))
-	if terms == nil {
+func newUnion(types []Type, tilde []bool) Type {
+	assert(len(types) == len(tilde))
+	if types == nil {
 		return nil
 	}
 	t := new(Union)
-	t.terms = terms
+	t.types = types
 	t.tilde = tilde
 	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 {
+	if u == nil {
+		return false
+	}
+	for i, t := range u.types {
+		if !f(t, u.tilde[i]) {
+			return false
+		}
+	}
+	return true
+}
+
+// is reports whether f returned true for the underlying types of all terms of u.
+func (u *Union) underIs(f func(Type) bool) bool {
+	if u == nil {
+		return false
+	}
+	for _, t := range u.types {
+		if !f(under(t)) {
+			return false
+		}
+	}
+	return true
+}
+
 func parseUnion(check *Checker, tlist []syntax.Expr) Type {
-	var terms []Type
+	var types []Type
 	var tilde []bool
 	for _, x := range tlist {
 		t, d := parseTilde(check, x)
 		if len(tlist) == 1 && !d {
 			return t // single type
 		}
-		terms = append(terms, t)
+		types = append(types, t)
 		tilde = append(tilde, d)
 	}
 
@@ -55,7 +81,7 @@ func parseUnion(check *Checker, tlist []syntax.Expr) Type {
 	// for correctness of the code.
 	// Note: This is a quadratic algorithm, but unions tend to be short.
 	check.later(func() {
-		for i, t := range terms {
+		for i, t := range types {
 			t := expand(t)
 			if t == Typ[Invalid] {
 				continue
@@ -85,14 +111,14 @@ func parseUnion(check *Checker, tlist []syntax.Expr) Type {
 			}
 
 			// Complain about duplicate entries a|a, but also a|~a, and ~a|~a.
-			if includes(terms[:i], t) {
+			if includes(types[:i], t) {
 				// TODO(gri) this currently doesn't print the ~ if present
 				check.softErrorf(pos, "duplicate term %s in union element", t)
 			}
 		}
 	})
 
-	return newUnion(terms, tilde)
+	return newUnion(types, tilde)
 }
 
 func parseTilde(check *Checker, x syntax.Expr) (Type, bool) {
@@ -103,3 +129,60 @@ func parseTilde(check *Checker, x syntax.Expr) (Type, bool) {
 	}
 	return check.anyType(x), tilde
 }
+
+// intersect computes the intersection of the types x and y.
+// Note: An incomming nil type stands for the top type. A top
+// type result is returned as nil.
+func intersect(x, y Type) (r Type) {
+	defer func() {
+		if r == theTop {
+			r = nil
+		}
+	}()
+
+	switch {
+	case x == theBottom || y == theBottom:
+		return theBottom
+	case x == nil || x == theTop:
+		return y
+	case y == nil || x == theTop:
+		return x
+	}
+
+	// Compute the terms which are in both x and y.
+	xu, _ := x.(*Union)
+	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 _, y := range yu.types {
+			if includes(xu.types, y) {
+				types = append(types, y)
+				tilde = append(tilde, true) // TODO(gri) fix this
+			}
+		}
+		if types != nil {
+			return newUnion(types, tilde)
+		}
+
+	case xu != nil:
+		if includes(xu.types, y) {
+			return y
+		}
+
+	case yu != nil:
+		if includes(yu.types, x) {
+			return x
+		}
+
+	default: // xu == nil && yu == nil
+		if Identical(x, y) {
+			return x
+		}
+	}
+
+	return theBottom
+}