[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>

16 files changed, 187 insertions, 190 deletions

diff --git a/src/cmd/compile/internal/types2/builtins.go b/src/cmd/compile/internal/types2/builtins.go
index 94fb506d80..1779e32c5c 100644
--- a/src/cmd/compile/internal/types2/builtins.go
+++ b/src/cmd/compile/internal/types2/builtins.go
@@ -178,9 +178,9 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 				mode = value
 			}
 
-		case *Sum:
-			if t.is(func(t Type) bool {
-				switch t := under(t).(type) {
+		case *Union:
+			if t.underIs(func(t Type) bool {
+				switch t := t.(type) {
 				case *Basic:
 					if isString(t) && id == _Len {
 						return true
@@ -460,8 +460,8 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 				m = 2
 			case *Map, *Chan:
 				m = 1
-			case *Sum:
-				return t.is(valid)
+			case *Union:
+				return t.underIs(valid)
 			default:
 				return false
 			}
@@ -749,10 +749,14 @@ func (check *Checker) applyTypeFunc(f func(Type) Type, x Type) Type {
 	if tp := asTypeParam(x); tp != nil {
 		// Test if t satisfies the requirements for the argument
 		// type and collect possible result types at the same time.
+		// TODO(gri) This needs to consider the ~ information if we
+		//           have a union type.
 		var rtypes []Type
+		var tilde []bool
 		if !tp.Bound().is(func(x Type) bool {
 			if r := f(x); r != nil {
 				rtypes = append(rtypes, r)
+				tilde = append(tilde, true) // for now - see TODO above
 				return true
 			}
 			return false
@@ -768,7 +772,7 @@ func (check *Checker) applyTypeFunc(f func(Type) Type, x Type) Type {
 		// construct a suitable new type parameter
 		tpar := NewTypeName(nopos, nil /* = Universe pkg */, "<type parameter>", nil)
 		ptyp := check.NewTypeParam(tpar, 0, &emptyInterface) // assigns type to tpar as a side-effect
-		tsum := NewSum(rtypes)
+		tsum := newUnion(rtypes, tilde)
 		ptyp.bound = &Interface{allMethods: markComplete, allTypes: tsum}
 
 		return ptyp
diff --git a/src/cmd/compile/internal/types2/expr.go b/src/cmd/compile/internal/types2/expr.go
index 23b79656bb..b223387f18 100644
--- a/src/cmd/compile/internal/types2/expr.go
+++ b/src/cmd/compile/internal/types2/expr.go
@@ -723,8 +723,8 @@ func (check *Checker) implicitTypeAndValue(x *operand, target Type) (Type, const
 		default:
 			return nil, nil, _InvalidUntypedConversion
 		}
-	case *Sum:
-		ok := t.is(func(t Type) bool {
+	case *Union:
+		ok := t.underIs(func(t Type) bool {
 			target, _, _ := check.implicitTypeAndValue(x, t)
 			return target != nil
 		})
diff --git a/src/cmd/compile/internal/types2/index.go b/src/cmd/compile/internal/types2/index.go
index 33e79aac3e..47e0853a3b 100644
--- a/src/cmd/compile/internal/types2/index.go
+++ b/src/cmd/compile/internal/types2/index.go
@@ -91,15 +91,15 @@ func (check *Checker) indexExpr(x *operand, e *syntax.IndexExpr) (isFuncInst boo
 		x.expr = e
 		return
 
-	case *Sum:
-		// A sum type can be indexed if all of the sum's types
+	case *Union:
+		// A union type can be indexed if all of the union's terms
 		// support indexing and have the same index and element
-		// type. Special rules apply for maps in the sum type.
+		// type. Special rules apply for maps in the union type.
 		var tkey, telem Type // key is for map types only
-		nmaps := 0           // number of map types in sum type
-		if typ.is(func(t Type) bool {
+		nmaps := 0           // number of map types in union type
+		if typ.underIs(func(t Type) bool {
 			var e Type
-			switch t := under(t).(type) {
+			switch t := t.(type) {
 			case *Basic:
 				if isString(t) {
 					e = universeByte
@@ -113,7 +113,7 @@ func (check *Checker) indexExpr(x *operand, e *syntax.IndexExpr) (isFuncInst boo
 			case *Slice:
 				e = t.elem
 			case *Map:
-				// If there are multiple maps in the sum type,
+				// If there are multiple maps in the union type,
 				// they must have identical key types.
 				// TODO(gri) We may be able to relax this rule
 				// but it becomes complicated very quickly.
@@ -148,7 +148,7 @@ func (check *Checker) indexExpr(x *operand, e *syntax.IndexExpr) (isFuncInst boo
 				// ok to continue even if indexing failed - map element type is known
 
 				// If there are only maps, we are done.
-				if nmaps == len(typ.types) {
+				if nmaps == typ.NumTerms() {
 					x.mode = mapindex
 					x.typ = telem
 					x.expr = e
@@ -246,7 +246,7 @@ func (check *Checker) sliceExpr(x *operand, e *syntax.SliceExpr) {
 		valid = true
 		// x.typ doesn't change
 
-	case *Sum, *TypeParam:
+	case *Union, *TypeParam:
 		check.error(x, "generic slice expressions not yet implemented")
 		x.mode = invalid
 		return
diff --git a/src/cmd/compile/internal/types2/infer.go b/src/cmd/compile/internal/types2/infer.go
index d8865784a5..73ea8330d4 100644
--- a/src/cmd/compile/internal/types2/infer.go
+++ b/src/cmd/compile/internal/types2/infer.go
@@ -307,7 +307,7 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 			}
 		}
 
-	case *Sum:
+	case *Union:
 		return w.isParameterizedList(t.types)
 
 	case *Signature:
@@ -320,9 +320,6 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 		// Thus, we only need to look at the input and result parameters.
 		return w.isParameterized(t.params) || w.isParameterized(t.results)
 
-	case *Union:
-		unimplemented()
-
 	case *Interface:
 		if t.allMethods != nil {
 			// interface is complete - quick test
diff --git a/src/cmd/compile/internal/types2/interface.go b/src/cmd/compile/internal/types2/interface.go
index d590066ad6..db34d0705f 100644
--- a/src/cmd/compile/internal/types2/interface.go
+++ b/src/cmd/compile/internal/types2/interface.go
@@ -242,23 +242,26 @@ func completeInterface(check *Checker, pos syntax.Pos, ityp *Interface) {
 			}
 			types = t.allTypes
 		case *Union:
-			types = NewSum(t.terms)
-			// TODO(gri) don't ignore tilde information
+			// TODO(gri) combine with default case once we have
+			//           converted all tests to new notation and we
+			//           can report an error when we don't have an
+			//           interface before go1.18.
+			types = typ
 		case *TypeParam:
 			if check != nil && !check.allowVersion(check.pkg, 1, 18) {
 				check.errorf(pos, "%s is a type parameter, not an interface", typ)
 				continue
 			}
-			types = t
+			types = typ
 		default:
-			if t == Typ[Invalid] {
+			if typ == Typ[Invalid] {
 				continue
 			}
 			if check != nil && !check.allowVersion(check.pkg, 1, 18) {
 				check.errorf(pos, "%s is not an interface", typ)
 				continue
 			}
-			types = t
+			types = typ
 		}
 		allTypes = intersect(allTypes, types)
 	}
@@ -279,44 +282,6 @@ func completeInterface(check *Checker, pos syntax.Pos, ityp *Interface) {
 	ityp.allTypes = allTypes
 }
 
-// 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
-	}
-
-	xtypes := unpack(x)
-	ytypes := unpack(y)
-	// Compute the list rtypes which includes only
-	// types that are in both xtypes and ytypes.
-	// Quadratic algorithm, but good enough for now.
-	// TODO(gri) fix this
-	var rtypes []Type
-	for _, x := range xtypes {
-		if includes(ytypes, x) {
-			rtypes = append(rtypes, x)
-		}
-	}
-
-	if rtypes == nil {
-		return theBottom
-	}
-	return NewSum(rtypes)
-}
-
 func sortTypes(list []Type) {
 	sort.Stable(byUniqueTypeName(list))
 }
diff --git a/src/cmd/compile/internal/types2/operand.go b/src/cmd/compile/internal/types2/operand.go
index 455d8b5dd1..fdc6ec52aa 100644
--- a/src/cmd/compile/internal/types2/operand.go
+++ b/src/cmd/compile/internal/types2/operand.go
@@ -248,6 +248,12 @@ func (x *operand) assignableTo(check *Checker, T Type, reason *string) (bool, er
 
 	V := x.typ
 
+	const debugAssignableTo = false
+	if debugAssignableTo && check != nil {
+		check.dump("V = %s", V)
+		check.dump("T = %s", T)
+	}
+
 	// x's type is identical to T
 	if check.identical(V, T) {
 		return true, 0
@@ -256,11 +262,20 @@ func (x *operand) assignableTo(check *Checker, T Type, reason *string) (bool, er
 	Vu := optype(V)
 	Tu := optype(T)
 
+	if debugAssignableTo && check != nil {
+		check.dump("Vu = %s", Vu)
+		check.dump("Tu = %s", Tu)
+	}
+
 	// x is an untyped value representable by a value of type T.
 	if isUntyped(Vu) {
-		if t, ok := Tu.(*Sum); ok {
-			return t.is(func(t Type) bool {
+		if t, ok := Tu.(*Union); ok {
+			return t.is(func(t Type, tilde bool) bool {
 				// TODO(gri) this could probably be more efficient
+				if tilde {
+					// TODO(gri) We need to check assignability
+					//           for the underlying type of x.
+				}
 				ok, _ := x.assignableTo(check, t, reason)
 				return ok
 			}), _IncompatibleAssign
diff --git a/src/cmd/compile/internal/types2/predicates.go b/src/cmd/compile/internal/types2/predicates.go
index ab0a457276..bcb3e221d0 100644
--- a/src/cmd/compile/internal/types2/predicates.go
+++ b/src/cmd/compile/internal/types2/predicates.go
@@ -28,8 +28,8 @@ func is(typ Type, what BasicInfo) bool {
 	switch t := optype(typ).(type) {
 	case *Basic:
 		return t.info&what != 0
-	case *Sum:
-		return t.is(func(typ Type) bool { return is(typ, what) })
+	case *Union:
+		return t.underIs(func(t Type) bool { return is(t, what) })
 	}
 	return false
 }
@@ -124,11 +124,10 @@ func comparable(T Type, seen map[Type]bool) bool {
 		return true
 	case *Array:
 		return comparable(t.elem, seen)
-	case *Sum:
-		pred := func(t Type) bool {
+	case *Union:
+		return t.underIs(func(t Type) bool {
 			return comparable(t, seen)
-		}
-		return t.is(pred)
+		})
 	case *TypeParam:
 		return t.Bound().IsComparable()
 	}
@@ -142,8 +141,8 @@ func hasNil(typ Type) bool {
 		return t.kind == UnsafePointer
 	case *Slice, *Pointer, *Signature, *Interface, *Map, *Chan:
 		return true
-	case *Sum:
-		return t.is(hasNil)
+	case *Union:
+		return t.underIs(hasNil)
 	}
 	return false
 }
@@ -261,21 +260,20 @@ func (check *Checker) identical0(x, y Type, cmpTags bool, p *ifacePair) bool {
 				check.identical0(x.results, y.results, cmpTags, p)
 		}
 
-	case *Sum:
-		// Two sum types are identical if they contain the same types.
-		// (Sum types always consist of at least two types. Also, the
-		// the set (list) of types in a sum type consists of unique
-		// types - each type appears exactly once. Thus, two sum types
+	case *Union:
+		// Two union types are identical if they contain the same terms.
+		// The set (list) of types in a union type consists of unique
+		// 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.(*Sum); ok && len(x.types) == len(y.types) {
+		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 _, x := range x.types {
-				for _, y := range y.types {
-					if Identical(x, y) {
+			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
 					}
 				}
@@ -284,9 +282,6 @@ func (check *Checker) identical0(x, y Type, cmpTags bool, p *ifacePair) bool {
 			return true
 		}
 
-	case *Union:
-		unimplemented()
-
 	case *Interface:
 		// Two interface types are identical if they have the same set of methods with
 		// the same names and identical function types. Lower-case method names from
diff --git a/src/cmd/compile/internal/types2/sanitize.go b/src/cmd/compile/internal/types2/sanitize.go
index c30febfda8..ce26bab186 100644
--- a/src/cmd/compile/internal/types2/sanitize.go
+++ b/src/cmd/compile/internal/types2/sanitize.go
@@ -106,11 +106,8 @@ func (s sanitizer) typ(typ Type) Type {
 		s.tuple(t.params)
 		s.tuple(t.results)
 
-	case *Sum:
-		s.typeList(t.types)
-
 	case *Union:
-		s.typeList(t.terms)
+		s.typeList(t.types)
 
 	case *Interface:
 		s.funcList(t.methods)
diff --git a/src/cmd/compile/internal/types2/sizeof_test.go b/src/cmd/compile/internal/types2/sizeof_test.go
index 552f3488cd..d3c391161e 100644
--- a/src/cmd/compile/internal/types2/sizeof_test.go
+++ b/src/cmd/compile/internal/types2/sizeof_test.go
@@ -27,7 +27,6 @@ func TestSizeof(t *testing.T) {
 		{Pointer{}, 8, 16},
 		{Tuple{}, 12, 24},
 		{Signature{}, 44, 88},
-		{Sum{}, 12, 24},
 		{Union{}, 24, 48},
 		{Interface{}, 52, 104},
 		{Map{}, 16, 32},
diff --git a/src/cmd/compile/internal/types2/sizes.go b/src/cmd/compile/internal/types2/sizes.go
index c6b807cd06..cb789598e5 100644
--- a/src/cmd/compile/internal/types2/sizes.go
+++ b/src/cmd/compile/internal/types2/sizes.go
@@ -148,10 +148,8 @@ func (s *StdSizes) Sizeof(T Type) int64 {
 		}
 		offsets := s.Offsetsof(t.fields)
 		return offsets[n-1] + s.Sizeof(t.fields[n-1].typ)
-	case *Sum:
-		panic("Sizeof unimplemented for type sum")
 	case *Union:
-		unimplemented()
+		panic("Sizeof unimplemented for union")
 	case *Interface:
 		return s.WordSize * 2
 	}
diff --git a/src/cmd/compile/internal/types2/stmt.go b/src/cmd/compile/internal/types2/stmt.go
index c3e646c80c..e9ffd4f5ca 100644
--- a/src/cmd/compile/internal/types2/stmt.go
+++ b/src/cmd/compile/internal/types2/stmt.go
@@ -912,12 +912,12 @@ func rangeKeyVal(typ Type, wantKey, wantVal bool) (Type, Type, string) {
 			msg = "receive from send-only channel"
 		}
 		return typ.elem, Typ[Invalid], msg
-	case *Sum:
+	case *Union:
 		first := true
 		var key, val Type
 		var msg string
-		typ.is(func(t Type) bool {
-			k, v, m := rangeKeyVal(under(t), wantKey, wantVal)
+		typ.underIs(func(t Type) bool {
+			k, v, m := rangeKeyVal(t, wantKey, wantVal)
 			if k == nil || m != "" {
 				key, val, msg = k, v, m
 				return false
diff --git a/src/cmd/compile/internal/types2/subst.go b/src/cmd/compile/internal/types2/subst.go
index a2b81ba0cc..bfec61a065 100644
--- a/src/cmd/compile/internal/types2/subst.go
+++ b/src/cmd/compile/internal/types2/subst.go
@@ -298,21 +298,13 @@ func (subst *subster) typ(typ Type) Type {
 			}
 		}
 
-	case *Sum:
-		types, copied := subst.typeList(t.types)
-		if copied {
-			// Don't do it manually, with a Sum literal: the new
-			// types list may not be unique and NewSum may remove
-			// duplicates.
-			return NewSum(types)
-		}
-
 	case *Union:
-		terms, copied := subst.typeList(t.terms)
+		types, copied := subst.typeList(t.types)
 		if copied {
-			// TODO(gri) Do we need to remove duplicates that may have
-			//           crept in after substitution? It may not matter.
-			return newUnion(terms, t.tilde)
+			// 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)
 		}
 
 	case *Interface:
diff --git a/src/cmd/compile/internal/types2/type.go b/src/cmd/compile/internal/types2/type.go
index 3b2a5960e8..aab75811b8 100644
--- a/src/cmd/compile/internal/types2/type.go
+++ b/src/cmd/compile/internal/types2/type.go
@@ -261,53 +261,6 @@ func (s *Signature) Results() *Tuple { return s.results }
 // Variadic reports whether the signature s is variadic.
 func (s *Signature) Variadic() bool { return s.variadic }
 
-// A Sum represents a set of possible types.
-// Sums are currently used to represent type lists of interfaces
-// and thus the underlying types of type parameters; they are not
-// first class types of Go.
-type Sum struct {
-	types []Type // types are unique
-}
-
-// NewSum returns a new Sum type consisting of the provided
-// types if there are more than one. If there is exactly one
-// type, it returns that type. If the list of types is empty
-// the result is nil.
-func NewSum(types []Type) Type {
-	if len(types) == 0 {
-		return nil
-	}
-
-	// What should happen if types contains a sum type?
-	// Do we flatten the types list? For now we check
-	// and panic. This should not be possible for the
-	// current use case of type lists.
-	// TODO(gri) Come up with the rules for sum types.
-	for _, t := range types {
-		if _, ok := t.(*Sum); ok {
-			panic("sum type contains sum type - unimplemented")
-		}
-	}
-
-	if len(types) == 1 {
-		return types[0]
-	}
-	return &Sum{types: types}
-}
-
-// is reports whether all types in t satisfy pred.
-func (s *Sum) is(pred func(Type) bool) bool {
-	if s == nil {
-		return false
-	}
-	for _, t := range s.types {
-		if !pred(t) {
-			return false
-		}
-	}
-	return true
-}
-
 // An Interface represents an interface type.
 type Interface struct {
 	methods   []*Func // ordered list of explicitly declared methods
@@ -325,8 +278,8 @@ func unpack(typ Type) []Type {
 	if typ == nil {
 		return nil
 	}
-	if sum := asSum(typ); sum != nil {
-		return sum.types
+	if u := asUnion(typ); u != nil {
+		return u.types
 	}
 	return []Type{typ}
 }
@@ -716,9 +669,16 @@ func optype(typ Type) Type {
 		// for a type parameter list of the form:
 		// (type T interface { type T }).
 		// See also issue #39680.
-		if u := t.Bound().allTypes; u != nil && u != typ {
-			// u != typ and u is a type parameter => under(u) != typ, so this is ok
-			return under(u)
+		if a := t.Bound().allTypes; a != nil {
+			// 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]
+			}
+			if a != typ {
+				// a != typ and a is a type parameter => under(a) != typ, so this is ok
+				return under(a)
+			}
 		}
 		return theTop
 	}
@@ -800,7 +760,6 @@ func (t *Struct) Underlying() Type    { return t }
 func (t *Pointer) Underlying() Type   { return t }
 func (t *Tuple) Underlying() Type     { return t }
 func (t *Signature) Underlying() Type { return t }
-func (t *Sum) Underlying() Type       { return t }
 func (t *Interface) Underlying() Type { return t }
 func (t *Map) Underlying() Type       { return t }
 func (t *Chan) Underlying() Type      { return t }
@@ -818,7 +777,6 @@ func (t *Struct) String() string    { return TypeString(t, nil) }
 func (t *Pointer) String() string   { return TypeString(t, nil) }
 func (t *Tuple) String() string     { return TypeString(t, nil) }
 func (t *Signature) String() string { return TypeString(t, nil) }
-func (t *Sum) String() string       { return TypeString(t, nil) }
 func (t *Interface) String() string { return TypeString(t, nil) }
 func (t *Map) String() string       { return TypeString(t, nil) }
 func (t *Chan) String() string      { return TypeString(t, nil) }
@@ -833,7 +791,7 @@ func (t *top) String() string       { return TypeString(t, nil) }
 // under must only be called when a type is known
 // to be fully set up.
 func under(t Type) Type {
-	// TODO(gri) is this correct for *Sum?
+	// TODO(gri) is this correct for *Union?
 	if n := asNamed(t); n != nil {
 		return n.under()
 	}
@@ -880,8 +838,8 @@ func asSignature(t Type) *Signature {
 	return op
 }
 
-func asSum(t Type) *Sum {
-	op, _ := optype(t).(*Sum)
+func asUnion(t Type) *Union {
+	op, _ := optype(t).(*Union)
 	return op
 }
 
diff --git a/src/cmd/compile/internal/types2/typestring.go b/src/cmd/compile/internal/types2/typestring.go
index 55858b7b42..466beb2398 100644
--- a/src/cmd/compile/internal/types2/typestring.go
+++ b/src/cmd/compile/internal/types2/typestring.go
@@ -157,11 +157,8 @@ func writeType(buf *bytes.Buffer, typ Type, qf Qualifier, visited []Type) {
 		buf.WriteString("func")
 		writeSignature(buf, t, qf, visited)
 
-	case *Sum:
-		writeTypeList(buf, t.types, qf, visited)
-
 	case *Union:
-		for i, e := range t.terms {
+		for i, e := range t.types {
 			if i > 0 {
 				buf.WriteString("|")
 			}
diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index f1630b75d0..e5983dd40c 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -352,12 +352,9 @@ func (u *unifier) nify(x, y Type, p *ifacePair) bool {
 				u.nify(x.results, y.results, p)
 		}
 
-	case *Sum:
-		// This should not happen with the current internal use of sum types.
-		panic("type inference across sum types not implemented")
-
 	case *Union:
-		unimplemented()
+		// This should not happen with the current internal use of union types.
+		panic("type inference across union types not implemented")
 
 	case *Interface:
 		// Two interface types are identical if they have the same set of methods with
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
+}