From bb5608dd5d056519bd90666b815e0b2bf65e5ee8 Mon Sep 17 00:00:00 2001
From: Robert Griesemer <gri@golang.org>
Date: Thu, 29 Jul 2021 11:10:04 -0700
Subject: [dev.typeparams] cmd/compile/internal/types2: implement type sets
 with term lists

This CL resolves several known issues and TODOs.

- Represent type sets with term lists and using term list abstractions.

- Represent Unions internally as a list of (syntactical) terms.
  Use term operations to print terms and detect overlapping union
  entries.

- Compute type sets corresponding to unions lazily, on demand.

- Adjust code throughout.

- Adjusted error check in test/typeparam/mincheck.dir/main.go
  to make test pass.

Change-Id: Ib36fb7e1d343c2b6aec51d304f0f7d1ad415f999
Reviewed-on: https://go-review.googlesource.com/c/go/+/338310
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
---
 src/cmd/compile/internal/types2/builtins.go        |  16 +-
 src/cmd/compile/internal/types2/infer.go           |  37 +---
 src/cmd/compile/internal/types2/instantiate.go     |  24 ++-
 src/cmd/compile/internal/types2/interface.go       |  33 +---
 src/cmd/compile/internal/types2/operand.go         |   2 +-
 src/cmd/compile/internal/types2/predicates.go      |  12 +-
 src/cmd/compile/internal/types2/sizeof_test.go     |   4 +-
 src/cmd/compile/internal/types2/stmt.go            |   2 +-
 src/cmd/compile/internal/types2/subst.go           |  12 +-
 src/cmd/compile/internal/types2/termlist.go        |   2 +-
 .../internal/types2/testdata/check/typeinst2.go2   |   8 +-
 .../internal/types2/testdata/check/typeparams.go2  |  65 +++----
 .../types2/testdata/examples/constraints.go2       |  41 +++-
 .../types2/testdata/fixedbugs/issue41124.go2       |  10 +-
 src/cmd/compile/internal/types2/type.go            |  21 +--
 src/cmd/compile/internal/types2/typeparam.go       |  27 ++-
 src/cmd/compile/internal/types2/typeset.go         | 169 ++++++++++++-----
 src/cmd/compile/internal/types2/typestring.go      |  25 ++-
 src/cmd/compile/internal/types2/typexpr.go         |  16 +-
 src/cmd/compile/internal/types2/unify.go           |   5 +-
 src/cmd/compile/internal/types2/union.go           | 206 ++++-----------------
 src/cmd/compile/internal/types2/universe.go        |   4 +-
 test/typeparam/mincheck.dir/main.go                |   4 +-
 23 files changed, 331 insertions(+), 414 deletions(-)

diff --git a/src/cmd/compile/internal/types2/builtins.go b/src/cmd/compile/internal/types2/builtins.go
index 7b2c92bfa8..c022e79c97 100644
--- a/src/cmd/compile/internal/types2/builtins.go
+++ b/src/cmd/compile/internal/types2/builtins.go
@@ -144,7 +144,7 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 		mode := invalid
 		var typ Type
 		var val constant.Value
-		switch typ = implicitArrayDeref(optype(x.typ)); t := typ.(type) {
+		switch typ = implicitArrayDeref(under(x.typ)); t := typ.(type) {
 		case *Basic:
 			if isString(t) && id == _Len {
 				if x.mode == constant_ {
@@ -178,9 +178,9 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 				mode = value
 			}
 
-		case *Union:
+		case *TypeParam:
 			if t.underIs(func(t Type) bool {
-				switch t := t.(type) {
+				switch t := implicitArrayDeref(t).(type) {
 				case *Basic:
 					if isString(t) && id == _Len {
 						return true
@@ -817,10 +817,10 @@ func (check *Checker) applyTypeFunc(f func(Type) Type, x Type) Type {
 		// type and collect possible result types at the same time.
 		var rtypes []Type
 		var tildes []bool
-		if !tp.iface().is(func(typ Type, tilde bool) bool {
-			if r := f(typ); r != nil {
+		if !tp.iface().typeSet().is(func(t *term) bool {
+			if r := f(t.typ); r != nil {
 				rtypes = append(rtypes, r)
-				tildes = append(tildes, tilde)
+				tildes = append(tildes, t.tilde)
 				return true
 			}
 			return false
@@ -837,10 +837,8 @@ func (check *Checker) applyTypeFunc(f func(Type) Type, x Type) Type {
 		// type param is placed in the current package so export/import
 		// works as expected.
 		tpar := NewTypeName(nopos, check.pkg, "<type parameter>", nil)
-		ptyp := check.NewTypeParam(tpar, &emptyInterface) // assigns type to tpar as a side-effect
+		ptyp := check.NewTypeParam(tpar, NewInterfaceType(nil, []Type{newUnion(rtypes, tildes)})) // assigns type to tpar as a side-effect
 		ptyp.index = tp.index
-		tsum := newUnion(rtypes, tildes)
-		ptyp.bound = &Interface{complete: true, tset: &TypeSet{types: tsum}}
 
 		return ptyp
 	}
diff --git a/src/cmd/compile/internal/types2/infer.go b/src/cmd/compile/internal/types2/infer.go
index 00548b402e..a3772aa713 100644
--- a/src/cmd/compile/internal/types2/infer.go
+++ b/src/cmd/compile/internal/types2/infer.go
@@ -280,7 +280,7 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 	}()
 
 	switch t := typ.(type) {
-	case nil, *Basic: // TODO(gri) should nil be handled here?
+	case nil, *top, *Basic: // TODO(gri) should nil be handled here?
 		break
 
 	case *Array:
@@ -307,9 +307,6 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 			}
 		}
 
-	case *Union:
-		return w.isParameterizedTermList(t.terms)
-
 	case *Signature:
 		// t.tparams may not be nil if we are looking at a signature
 		// of a generic function type (or an interface method) that is
@@ -327,7 +324,9 @@ func (w *tpWalker) isParameterized(typ Type) (res bool) {
 				return true
 			}
 		}
-		return w.isParameterized(tset.types)
+		return tset.is(func(t *term) bool {
+			return w.isParameterized(t.typ)
+		})
 
 	case *Map:
 		return w.isParameterized(t.key) || w.isParameterized(t.elem)
@@ -358,15 +357,6 @@ func (w *tpWalker) isParameterizedTypeList(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
@@ -394,7 +384,7 @@ func (check *Checker) inferB(tparams []*TypeName, targs []Type, report bool) (ty
 	// Unify type parameters with their structural constraints, if any.
 	for _, tpar := range tparams {
 		typ := tpar.typ.(*TypeParam)
-		sbound := check.structuralType(typ.bound)
+		sbound := typ.structuralType()
 		if sbound != nil {
 			if !u.unify(typ, sbound) {
 				if report {
@@ -467,20 +457,3 @@ func (check *Checker) inferB(tparams []*TypeName, targs []Type, report bool) (ty
 
 	return
 }
-
-// structuralType returns the structural type of a constraint, if any.
-func (check *Checker) structuralType(constraint Type) Type {
-	if iface, _ := under(constraint).(*Interface); iface != nil {
-		types := iface.typeSet().types
-		if u, _ := types.(*Union); u != nil {
-			if u.NumTerms() == 1 {
-				// TODO(gri) do we need to respect tilde?
-				t, _ := u.Term(0)
-				return t
-			}
-			return nil
-		}
-		return types
-	}
-	return nil
-}
diff --git a/src/cmd/compile/internal/types2/instantiate.go b/src/cmd/compile/internal/types2/instantiate.go
index 357f041c46..b7ea193a06 100644
--- a/src/cmd/compile/internal/types2/instantiate.go
+++ b/src/cmd/compile/internal/types2/instantiate.go
@@ -212,7 +212,7 @@ func (check *Checker) satisfies(pos syntax.Pos, targ Type, tpar *TypeParam, smap
 	}
 
 	// targ's underlying type must also be one of the interface types listed, if any
-	if iface.typeSet().types == nil {
+	if !iface.typeSet().hasTerms() {
 		return true // nothing to do
 	}
 
@@ -220,24 +220,22 @@ func (check *Checker) satisfies(pos syntax.Pos, targ Type, tpar *TypeParam, smap
 	// list of iface types (i.e., the targ type list must be a non-empty subset of the iface types).
 	if targ := asTypeParam(targ); targ != nil {
 		targBound := targ.iface()
-		if targBound.typeSet().types == nil {
+		if !targBound.typeSet().hasTerms() {
 			check.softErrorf(pos, "%s does not satisfy %s (%s has no type constraints)", targ, tpar.bound, targ)
 			return false
 		}
-		return iface.is(func(typ Type, tilde bool) bool {
-			// TODO(gri) incorporate tilde information!
-			if !iface.isSatisfiedBy(typ) {
-				// TODO(gri) match this error message with the one below (or vice versa)
-				check.softErrorf(pos, "%s does not satisfy %s (%s type constraint %s not found in %s)", targ, tpar.bound, targ, typ, iface.typeSet().types)
-				return false
-			}
-			return true
-		})
+		if !targBound.typeSet().subsetOf(iface.typeSet()) {
+			// TODO(gri) need better error message
+			check.softErrorf(pos, "%s does not satisfy %s", targ, tpar.bound)
+			return false
+		}
+		return true
 	}
 
 	// Otherwise, targ's type or underlying type must also be one of the interface types listed, if any.
-	if !iface.isSatisfiedBy(targ) {
-		check.softErrorf(pos, "%s does not satisfy %s (%s not found in %s)", targ, tpar.bound, targ, iface.typeSet().types)
+	if !iface.typeSet().includes(targ) {
+		// TODO(gri) better error message
+		check.softErrorf(pos, "%s does not satisfy %s", targ, tpar.bound)
 		return false
 	}
 
diff --git a/src/cmd/compile/internal/types2/interface.go b/src/cmd/compile/internal/types2/interface.go
index fc1f5ffe00..aa7d0b05a0 100644
--- a/src/cmd/compile/internal/types2/interface.go
+++ b/src/cmd/compile/internal/types2/interface.go
@@ -21,20 +21,7 @@ type Interface struct {
 }
 
 // typeSet returns the type set for interface t.
-func (t *Interface) typeSet() *TypeSet { return computeTypeSet(nil, nopos, t) }
-
-// is reports whether interface t represents types that all satisfy f.
-func (t *Interface) is(f func(Type, bool) bool) bool {
-	switch t := t.typeSet().types.(type) {
-	case nil, *top:
-		// 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(t *term) bool { return f(t.typ, t.tilde) })
-	default:
-		return f(t, false)
-	}
-}
+func (t *Interface) typeSet() *TypeSet { return computeInterfaceTypeSet(nil, nopos, t) }
 
 // emptyInterface represents the empty interface
 var emptyInterface = Interface{complete: true, tset: &topTypeSet}
@@ -113,22 +100,6 @@ func (t *Interface) IsComparable() bool { return t.typeSet().IsComparable() }
 // IsConstraint reports whether interface t is not just a method set.
 func (t *Interface) IsConstraint() bool { return !t.typeSet().IsMethodSet() }
 
-// isSatisfiedBy reports whether interface t's type list is satisfied by the type typ.
-// If the type list is empty (absent), typ trivially satisfies the interface.
-// TODO(gri) This is not a great name. Eventually, we should have a more comprehensive
-//           "implements" predicate.
-func (t *Interface) isSatisfiedBy(typ Type) bool {
-	switch t := t.typeSet().types.(type) {
-	case nil:
-		return true // no type restrictions
-	case *Union:
-		r, _ := t.intersect(typ, false)
-		return r != nil
-	default:
-		return Identical(t, typ)
-	}
-}
-
 // Complete computes the interface's type set. It must be called by users of
 // NewInterfaceType and NewInterface after the interface's embedded types are
 // fully defined and before using the interface type in any way other than to
@@ -262,7 +233,7 @@ func (check *Checker) interfaceType(ityp *Interface, iface *syntax.InterfaceType
 	// Compute type set with a non-nil *Checker as soon as possible
 	// 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) })
+	check.later(func() { computeInterfaceTypeSet(check, iface.Pos(), ityp) })
 }
 
 func flattenUnion(list []syntax.Expr, x syntax.Expr) []syntax.Expr {
diff --git a/src/cmd/compile/internal/types2/operand.go b/src/cmd/compile/internal/types2/operand.go
index 34d35b2594..8336451e9c 100644
--- a/src/cmd/compile/internal/types2/operand.go
+++ b/src/cmd/compile/internal/types2/operand.go
@@ -273,7 +273,7 @@ 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 {
+		if t, ok := Tu.(*TypeParam); ok {
 			return t.is(func(t *term) bool {
 				// TODO(gri) this could probably be more efficient
 				if t.tilde {
diff --git a/src/cmd/compile/internal/types2/predicates.go b/src/cmd/compile/internal/types2/predicates.go
index bb7fedda3b..afef488b96 100644
--- a/src/cmd/compile/internal/types2/predicates.go
+++ b/src/cmd/compile/internal/types2/predicates.go
@@ -229,16 +229,6 @@ func identical(x, y Type, cmpTags bool, p *ifacePair) bool {
 				identical(x.results, y.results, cmpTags, p)
 		}
 
-	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.(*Union); ok {
-			return identicalTerms(x.terms, y.terms)
-		}
-
 	case *Interface:
 		// Two interface types are identical if they describe the same type sets.
 		// With the existing implementation restriction, this simplifies to:
@@ -250,7 +240,7 @@ func identical(x, y Type, cmpTags bool, p *ifacePair) bool {
 		if y, ok := y.(*Interface); ok {
 			xset := x.typeSet()
 			yset := y.typeSet()
-			if !Identical(xset.types, yset.types) {
+			if !xset.terms.equal(yset.terms) {
 				return false
 			}
 			a := xset.methods
diff --git a/src/cmd/compile/internal/types2/sizeof_test.go b/src/cmd/compile/internal/types2/sizeof_test.go
index 8255e6ded4..d2f53258f0 100644
--- a/src/cmd/compile/internal/types2/sizeof_test.go
+++ b/src/cmd/compile/internal/types2/sizeof_test.go
@@ -27,7 +27,7 @@ func TestSizeof(t *testing.T) {
 		{Pointer{}, 8, 16},
 		{Tuple{}, 12, 24},
 		{Signature{}, 28, 56},
-		{Union{}, 12, 24},
+		{Union{}, 16, 32},
 		{Interface{}, 40, 80},
 		{Map{}, 16, 32},
 		{Chan{}, 12, 24},
@@ -49,7 +49,7 @@ func TestSizeof(t *testing.T) {
 		// Misc
 		{Scope{}, 60, 104},
 		{Package{}, 40, 80},
-		{TypeSet{}, 24, 48},
+		{TypeSet{}, 28, 56},
 	}
 
 	for _, test := range tests {
diff --git a/src/cmd/compile/internal/types2/stmt.go b/src/cmd/compile/internal/types2/stmt.go
index 9b8295c4f4..1efce511f1 100644
--- a/src/cmd/compile/internal/types2/stmt.go
+++ b/src/cmd/compile/internal/types2/stmt.go
@@ -921,7 +921,7 @@ func rangeKeyVal(typ Type, wantKey, wantVal bool) (Type, Type, string) {
 			msg = "receive from send-only channel"
 		}
 		return typ.elem, Typ[Invalid], msg
-	case *Union:
+	case *TypeParam:
 		first := true
 		var key, val Type
 		var msg string
diff --git a/src/cmd/compile/internal/types2/subst.go b/src/cmd/compile/internal/types2/subst.go
index e497e17463..6c5f756491 100644
--- a/src/cmd/compile/internal/types2/subst.go
+++ b/src/cmd/compile/internal/types2/subst.go
@@ -145,12 +145,12 @@ func (subst *subster) typ(typ Type) Type {
 		}
 
 	case *Union:
-		terms, copied := subst.termList(t.terms)
+		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 &Union{terms}
+			// term list substitution may introduce duplicate terms (unlikely but possible).
+			// This is ok; lazy type set computation will determine the actual type set
+			// in normal form.
+			return &Union{terms, nil}
 		}
 
 	case *Interface:
@@ -387,7 +387,7 @@ func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
 	return
 }
 
-func (subst *subster) termList(in []*term) (out []*term, copied bool) {
+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 {
diff --git a/src/cmd/compile/internal/types2/termlist.go b/src/cmd/compile/internal/types2/termlist.go
index b2c26f41be..07056edd97 100644
--- a/src/cmd/compile/internal/types2/termlist.go
+++ b/src/cmd/compile/internal/types2/termlist.go
@@ -13,7 +13,7 @@ import "bytes"
 // normal form.
 type termlist []*term
 
-// topTermList represents the set of all types.
+// topTermlist represents the set of all types.
 // It is in normal form.
 var topTermlist = termlist{new(term)}
 
diff --git a/src/cmd/compile/internal/types2/testdata/check/typeinst2.go2 b/src/cmd/compile/internal/types2/testdata/check/typeinst2.go2
index 14d8f0ea8c..e90e4dde44 100644
--- a/src/cmd/compile/internal/types2/testdata/check/typeinst2.go2
+++ b/src/cmd/compile/internal/types2/testdata/check/typeinst2.go2
@@ -164,13 +164,13 @@ type _ interface {
 // for them to be all in a single list, and we report the error
 // as well.)
 type _ interface {
-	~int|~int /* ERROR duplicate term int */
-	~int|int /* ERROR duplicate term int */
-	int|int /* ERROR duplicate term int */
+	~int|~int /* ERROR overlapping terms ~int */
+	~int|int /* ERROR overlapping terms int */
+	int|int /* ERROR overlapping terms int */
 }
 
 type _ interface {
-	~struct{f int} | ~struct{g int} | ~struct /* ERROR duplicate term */ {f int}
+	~struct{f int} | ~struct{g int} | ~struct /* ERROR overlapping terms */ {f int}
 }
 
 // Interface type lists can contain any type, incl. *Named types.
diff --git a/src/cmd/compile/internal/types2/testdata/check/typeparams.go2 b/src/cmd/compile/internal/types2/testdata/check/typeparams.go2
index 54efd1485b..7392b88555 100644
--- a/src/cmd/compile/internal/types2/testdata/check/typeparams.go2
+++ b/src/cmd/compile/internal/types2/testdata/check/typeparams.go2
@@ -149,37 +149,40 @@ func _[T interface{}](x T) {
         for range x /* ERROR cannot range */ {}
 }
 
-func _[T interface{ ~string | ~[]string }](x T) {
-        for range x {}
-        for i := range x { _ = i }
-        for i, _ := range x { _ = i }
-        for i, e := range x /* ERROR must have the same element type */ { _ = i }
-        for _, e := range x /* ERROR must have the same element type */ {}
-        var e rune
-        _ = e
-        for _, (e) = range x /* ERROR must have the same element type */ {}
-}
-
-
-func _[T interface{ ~string | ~[]rune | ~map[int]rune }](x T) {
-        for _, e := range x { _ = e }
-        for i, e := range x { _ = i; _ = e }
-}
-
-func _[T interface{ ~string | ~[]rune | ~map[string]rune }](x T) {
-        for _, e := range x { _ = e }
-        for i, e := range x /* ERROR must have the same key type */ { _ = e }
-}
-
-func _[T interface{ ~string | ~chan int }](x T) {
-        for range x {}
-        for i := range x { _ = i }
-        for i, _ := range x { _ = i } // TODO(gri) should get an error here: channels only return one value
-}
-
-func _[T interface{ ~string | ~chan<-int }](x T) {
-        for i := range x /* ERROR send-only channel */ { _ = i }
-}
+// Disabled for now until we have clarified semantics of range.
+// TODO(gri) fix this
+//
+// func _[T interface{ ~string | ~[]string }](x T) {
+//         for range x {}
+//         for i := range x { _ = i }
+//         for i, _ := range x { _ = i }
+//         for i, e := range x /* ERROR must have the same element type */ { _ = i }
+//         for _, e := range x /* ERROR must have the same element type */ {}
+//         var e rune
+//         _ = e
+//         for _, (e) = range x /* ERROR must have the same element type */ {}
+// }
+// 
+// 
+// func _[T interface{ ~string | ~[]rune | ~map[int]rune }](x T) {
+//         for _, e := range x { _ = e }
+//         for i, e := range x { _ = i; _ = e }
+// }
+// 
+// func _[T interface{ ~string | ~[]rune | ~map[string]rune }](x T) {
+//         for _, e := range x { _ = e }
+//         for i, e := range x /* ERROR must have the same key type */ { _ = e }
+// }
+// 
+// func _[T interface{ ~string | ~chan int }](x T) {
+//         for range x {}
+//         for i := range x { _ = i }
+//         for i, _ := range x { _ = i } // TODO(gri) should get an error here: channels only return one value
+// }
+// 
+// func _[T interface{ ~string | ~chan<-int }](x T) {
+//         for i := range x /* ERROR send-only channel */ { _ = i }
+// }
 
 // type inference checks
 
diff --git a/src/cmd/compile/internal/types2/testdata/examples/constraints.go2 b/src/cmd/compile/internal/types2/testdata/examples/constraints.go2
index 28aa19bb12..f40d18c63e 100644
--- a/src/cmd/compile/internal/types2/testdata/examples/constraints.go2
+++ b/src/cmd/compile/internal/types2/testdata/examples/constraints.go2
@@ -18,18 +18,25 @@ type (
 	}
 )
 
+type MyInt int
+
 type (
 	// Arbitrary types may be embedded like interfaces.
 	_ interface{int}
 	_ interface{~int}
 
 	// Types may be combined into a union.
-	_ interface{int|~string}
+	union interface{int|~string}
 
-	// Union terms must be unique independent of whether they are ~ or not.
-	_ interface{int|int /* ERROR duplicate term int */ }
-	_ interface{int|~ /* ERROR duplicate term int */ int }
-	_ interface{~int|~ /* ERROR duplicate term int */ int }
+	// Union terms must describe disjoint (non-overlapping) type sets.
+	_ interface{int|int /* ERROR overlapping terms int */ }
+	_ interface{int|~ /* ERROR overlapping terms ~int */ int }
+	_ interface{~int|~ /* ERROR overlapping terms ~int */ int }
+	_ interface{~int|MyInt /* ERROR overlapping terms p.MyInt and ~int */ }
+	_ interface{int|interface{}}
+	_ interface{int|~string|union}
+	_ interface{int|~string|interface{int}}
+	_ interface{union|union /* ERROR overlapping terms p.union and p.union */ }
 
 	// For now we do not permit interfaces with methods in unions.
 	_ interface{~ /* ERROR invalid use of ~ */ interface{}}
@@ -45,6 +52,15 @@ type (
 	_ interface{~ /* ERROR invalid use of ~ */ bar }
 )
 
+// Stand-alone type parameters are not permitted as elements or terms in unions.
+type (
+	_[T interface{ *T } ] struct{}        // ok
+	_[T interface{ int | *T } ] struct{}  // ok
+	_[T interface{ T /* ERROR cannot embed a type parameter */ } ] struct{}
+	_[T interface{ ~T /* ERROR cannot embed a type parameter */ } ] struct{}
+	_[T interface{ int|T /* ERROR cannot embed a type parameter */ }] struct{}
+)
+
 // Multiple embedded union elements are intersected. The order in which they
 // appear in the interface doesn't matter since intersection is a symmetric
 // operation.
@@ -58,3 +74,18 @@ func _[T interface{ ~int; myInt1|myInt2 }]() T { return T(0) }
 // Here the intersections are empty - there's no type that's in the type set of T.
 func _[T interface{ myInt1|myInt2; int }]() T { return T(0 /* ERROR cannot convert */ ) }
 func _[T interface{ int; myInt1|myInt2 }]() T { return T(0 /* ERROR cannot convert */ ) }
+
+// Union elements may be interfaces as long as they don't define
+// any methods or embed comparable.
+
+type (
+	Integer interface{ ~int|~int8|~int16|~int32|~int64 }
+	Unsigned interface{ ~uint|~uint8|~uint16|~uint32|~uint64 }
+	Floats interface{ ~float32|~float64 }
+	Complex interface{ ~complex64|~complex128 }
+	Number interface{ Integer|Unsigned|Floats|Complex }
+	Ordered interface{ Integer|Unsigned|Floats|~string }
+
+	_ interface{ Number | error /* ERROR cannot use error in union */ }
+	_ interface{ Ordered | comparable /* ERROR cannot use comparable in union */ }
+)
diff --git a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue41124.go2 b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue41124.go2
index ab535049dd..60650432a4 100644
--- a/src/cmd/compile/internal/types2/testdata/fixedbugs/issue41124.go2
+++ b/src/cmd/compile/internal/types2/testdata/fixedbugs/issue41124.go2
@@ -47,7 +47,7 @@ type _ struct{
 }
 
 type _ struct{
-	I3 // ERROR interface contains type constraints
+	I3 // ERROR interface is .* comparable
 }
 
 // General composite types.
@@ -59,19 +59,19 @@ type (
 	_ []I1 // ERROR interface is .* comparable
 	_ []I2 // ERROR interface contains type constraints
 
-	_ *I3 // ERROR interface contains type constraints
+	_ *I3 // ERROR interface is .* comparable
 	_ map[I1 /* ERROR interface is .* comparable */ ]I2 // ERROR interface contains type constraints
-	_ chan I3 // ERROR interface contains type constraints
+	_ chan I3 // ERROR interface is .* comparable
 	_ func(I1 /* ERROR interface is .* comparable */ )
 	_ func() I2 // ERROR interface contains type constraints
 )
 
 // Other cases.
 
-var _ = [...]I3 /* ERROR interface contains type constraints */ {}
+var _ = [...]I3 /* ERROR interface is .* comparable */ {}
 
 func _(x interface{}) {
-	_ = x.(I3 /* ERROR interface contains type constraints */ )
+	_ = x.(I3 /* ERROR interface is .* comparable */ )
 }
 
 type T1[_ any] struct{}
diff --git a/src/cmd/compile/internal/types2/type.go b/src/cmd/compile/internal/types2/type.go
index a943926189..7ae2db3412 100644
--- a/src/cmd/compile/internal/types2/type.go
+++ b/src/cmd/compile/internal/types2/type.go
@@ -44,28 +44,21 @@ func under(t Type) Type {
 // 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.
+// Type parameters, the operational type is the structural
+// type, if any; otherwise it's the top type.
+// The result is never the incoming type parameter.
 func optype(typ Type) Type {
 	if t := asTypeParam(typ); t != nil {
+		// TODO(gri) review accuracy of this comment
 		// If the optype is typ, return the top type as we have
 		// no information. It also prevents infinite recursion
 		// via the asTypeParam converter function. This can happen
 		// for a type parameter list of the form:
 		// (type T interface { type T }).
 		// See also issue #39680.
-		if a := t.iface().typeSet().types; 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.Term(0)
-			}
-			if a != typ {
-				// a != typ and a is a type parameter => under(a) != typ, so this is ok
-				return under(a)
-			}
+		if u := t.structuralType(); u != nil {
+			assert(u != typ) // "naked" type parameters cannot be embedded
+			return u
 		}
 		return theTop
 	}
diff --git a/src/cmd/compile/internal/types2/typeparam.go b/src/cmd/compile/internal/types2/typeparam.go
index 2614f467b1..27e6e35588 100644
--- a/src/cmd/compile/internal/types2/typeparam.go
+++ b/src/cmd/compile/internal/types2/typeparam.go
@@ -67,7 +67,7 @@ func (t *TypeParam) Constraint() Type {
 		if n, _ := t.bound.(*Named); n != nil {
 			pos = n.obj.pos
 		}
-		computeTypeSet(t.check, pos, iface)
+		computeInterfaceTypeSet(t.check, pos, iface)
 	}
 	return t.bound
 }
@@ -80,14 +80,6 @@ func (t *TypeParam) SetConstraint(bound Type) {
 	t.bound = bound
 }
 
-// iface returns the constraint interface of t.
-func (t *TypeParam) iface() *Interface {
-	if iface, _ := under(t.Constraint()).(*Interface); iface != nil {
-		return iface
-	}
-	return &emptyInterface
-}
-
 // Bound returns the constraint interface of t.
 // Deprecated. Only here for the compiler.
 // TODO(gri) remove in favor of uses of Constraint.
@@ -136,6 +128,23 @@ func bindTParams(list []*TypeName) *TypeParams {
 // ----------------------------------------------------------------------------
 // Implementation
 
+// iface returns the constraint interface of t.
+func (t *TypeParam) iface() *Interface {
+	if iface, _ := under(t.Constraint()).(*Interface); iface != nil {
+		return iface
+	}
+	return &emptyInterface
+}
+
+// structuralType returns the structural type of the type parameter's constraint; or nil.
+func (t *TypeParam) structuralType() Type {
+	return t.iface().typeSet().structuralType()
+}
+
+func (t *TypeParam) is(f func(*term) bool) bool {
+	return t.iface().typeSet().is(f)
+}
+
 func (t *TypeParam) underIs(f func(Type) bool) bool {
 	return t.iface().typeSet().underIs(f)
 }
diff --git a/src/cmd/compile/internal/types2/typeset.go b/src/cmd/compile/internal/types2/typeset.go
index 5a334b2f53..6e19115ff5 100644
--- a/src/cmd/compile/internal/types2/typeset.go
+++ b/src/cmd/compile/internal/types2/typeset.go
@@ -18,31 +18,32 @@ import (
 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
+	methods []*Func  // all methods of the interface; sorted by unique ID
+	terms   termlist // type terms of the type set
 }
 
-// IsTop reports whether type set s is the top type set (corresponding to the empty interface).
-func (s *TypeSet) IsTop() bool { return !s.comparable && len(s.methods) == 0 && s.types == nil }
+// IsEmpty reports whether type set s is the empty set.
+func (s *TypeSet) IsEmpty() bool { return s.terms.isEmpty() }
+
+// IsTop reports whether type set s is the set of all types (corresponding to the empty interface).
+func (s *TypeSet) IsTop() bool { return !s.comparable && len(s.methods) == 0 && s.terms.isTop() }
+
+// TODO(gri) IsMethodSet is not a great name for this predicate. Find a better one.
 
 // IsMethodSet reports whether the type set s is described by a single set of methods.
-func (s *TypeSet) IsMethodSet() bool { return !s.comparable && s.types == nil }
+func (s *TypeSet) IsMethodSet() bool { return !s.comparable && s.terms.isTop() }
 
 // IsComparable reports whether each type in the set is comparable.
 func (s *TypeSet) IsComparable() bool {
-	if s.types == nil {
+	if s.terms.isTop() {
 		return s.comparable
 	}
-	tcomparable := s.underIs(func(u Type) bool {
-		return Comparable(u)
+	return s.is(func(t *term) bool {
+		return Comparable(t.typ)
 	})
-	if !s.comparable {
-		return tcomparable
-	}
-	return s.comparable && tcomparable
 }
 
-// TODO(gri) IsTypeSet is not a great name. Find a better one.
+// TODO(gri) IsTypeSet is not a great name for this predicate. 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 {
@@ -63,15 +64,21 @@ func (s *TypeSet) LookupMethod(pkg *Package, name string) (int, *Func) {
 }
 
 func (s *TypeSet) String() string {
-	if s.IsTop() {
+	switch {
+	case s.IsEmpty():
+		return "∅"
+	case s.IsTop():
 		return "⊤"
 	}
 
+	hasMethods := len(s.methods) > 0
+	hasTerms := s.hasTerms()
+
 	var buf bytes.Buffer
 	buf.WriteByte('{')
 	if s.comparable {
 		buf.WriteString(" comparable")
-		if len(s.methods) > 0 || s.types != nil {
+		if hasMethods || hasTerms {
 			buf.WriteByte(';')
 		}
 	}
@@ -82,41 +89,77 @@ func (s *TypeSet) String() string {
 		buf.WriteByte(' ')
 		buf.WriteString(m.String())
 	}
-	if len(s.methods) > 0 && s.types != nil {
+	if hasMethods && hasTerms {
 		buf.WriteByte(';')
 	}
-	if s.types != nil {
-		buf.WriteByte(' ')
-		writeType(&buf, s.types, nil, nil)
+	if hasTerms {
+		buf.WriteString(s.terms.String())
 	}
+	buf.WriteString(" }") // there was at least one method or term
 
-	buf.WriteString(" }") // there was a least one method or type
 	return buf.String()
 }
 
 // ----------------------------------------------------------------------------
 // Implementation
 
-// underIs reports whether f returned true for the underlying types of the
-// enumerable types in the type set s. If the type set comprises all types
-// f is called once with the top type; if the type set is empty, the result
-// is false.
+func (s *TypeSet) hasTerms() bool             { return !s.terms.isTop() }
+func (s *TypeSet) structuralType() Type       { return s.terms.structuralType() }
+func (s *TypeSet) includes(t Type) bool       { return s.terms.includes(t) }
+func (s1 *TypeSet) subsetOf(s2 *TypeSet) bool { return s1.terms.subsetOf(s2.terms) }
+
+// TODO(gri) TypeSet.is and TypeSet.underIs should probably also go into termlist.go
+
+var topTerm = term{false, theTop}
+
+func (s *TypeSet) is(f func(*term) bool) bool {
+	if len(s.terms) == 0 {
+		return false
+	}
+	for _, t := range s.terms {
+		// Terms represent the top term with a nil type.
+		// The rest of the type checker uses the top type
+		// instead. Convert.
+		// TODO(gri) investigate if we can do without this
+		if t.typ == nil {
+			t = &topTerm
+		}
+		if !f(t) {
+			return false
+		}
+	}
+	return true
+}
+
 func (s *TypeSet) underIs(f func(Type) bool) bool {
-	switch t := s.types.(type) {
-	case nil:
-		return f(theTop)
-	default:
-		return f(t)
-	case *Union:
-		return t.underIs(f)
+	if len(s.terms) == 0 {
+		return false
+	}
+	for _, t := range s.terms {
+		// see corresponding comment in TypeSet.is
+		u := t.typ
+		if u == nil {
+			u = theTop
+		}
+		// t == under(t) for ~t terms
+		if !t.tilde {
+			u = under(u)
+		}
+		if debug {
+			assert(Identical(u, under(u)))
+		}
+		if !f(u) {
+			return false
+		}
 	}
+	return true
 }
 
 // topTypeSet may be used as type set for the empty interface.
-var topTypeSet TypeSet
+var topTypeSet = TypeSet{terms: topTermlist}
 
-// computeTypeSet may be called with check == nil.
-func computeTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
+// computeInterfaceTypeSet may be called with check == nil.
+func computeInterfaceTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
 	if ityp.tset != nil {
 		return ityp.tset
 	}
@@ -152,7 +195,7 @@ func computeTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
 	// have valid interfaces. Mark the interface as complete to avoid
 	// infinite recursion if the validType check occurs later for some
 	// reason.
-	ityp.tset = new(TypeSet) // TODO(gri) is this sufficient?
+	ityp.tset = &TypeSet{terms: topTermlist} // TODO(gri) is this sufficient?
 
 	// Methods of embedded interfaces are collected unchanged; i.e., the identity
 	// of a method I.m's Func Object of an interface I is the same as that of
@@ -213,7 +256,7 @@ func computeTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
 	}
 
 	// collect embedded elements
-	var allTypes Type
+	var allTerms = topTermlist
 	for i, typ := range ityp.embeddeds {
 		// The embedding position is nil for imported interfaces
 		// and also for interface copies after substitution (but
@@ -222,25 +265,22 @@ func computeTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
 		if ityp.embedPos != nil {
 			pos = (*ityp.embedPos)[i]
 		}
-		var types Type
+		var terms termlist
 		switch t := under(typ).(type) {
 		case *Interface:
-			tset := computeTypeSet(check, pos, t)
+			tset := computeInterfaceTypeSet(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
 			}
-			types = tset.types
+			terms = tset.terms
 		case *Union:
-			// 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
+			tset := computeUnionTypeSet(check, pos, t)
+			terms = tset.terms
 		case *TypeParam:
-			// Embedding stand-alone type parameters is not permitted for now.
+			// Embedding stand-alone type parameters is not permitted.
 			// This case is handled during union parsing.
 			unreachable()
 		default:
@@ -251,9 +291,11 @@ func computeTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
 				check.errorf(pos, "%s is not an interface", typ)
 				continue
 			}
-			types = typ
+			terms = termlist{{false, typ}}
 		}
-		allTypes = intersect(allTypes, types)
+		// The type set of an interface is the intersection
+		// of the type sets of all its elements.
+		allTerms = allTerms.intersect(terms)
 	}
 	ityp.embedPos = nil // not needed anymore (errors have been reported)
 
@@ -270,7 +312,7 @@ func computeTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *TypeSet {
 		sortMethods(methods)
 		ityp.tset.methods = methods
 	}
-	ityp.tset.types = allTypes
+	ityp.tset.terms = allTerms
 
 	return ityp.tset
 }
@@ -294,3 +336,34 @@ type byUniqueMethodName []*Func
 func (a byUniqueMethodName) Len() int           { return len(a) }
 func (a byUniqueMethodName) Less(i, j int) bool { return a[i].less(&a[j].object) }
 func (a byUniqueMethodName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
+
+// computeUnionTypeSet may be called with check == nil.
+func computeUnionTypeSet(check *Checker, pos syntax.Pos, utyp *Union) *TypeSet {
+	if utyp.tset != nil {
+		return utyp.tset
+	}
+
+	// avoid infinite recursion (see also computeInterfaceTypeSet)
+	utyp.tset = new(TypeSet)
+
+	var allTerms termlist
+	for _, t := range utyp.terms {
+		var terms termlist
+		switch u := under(t.typ).(type) {
+		case *Interface:
+			terms = computeInterfaceTypeSet(check, pos, u).terms
+		case *TypeParam:
+			// A stand-alone type parameters is not permitted as union term.
+			// This case is handled during union parsing.
+			unreachable()
+		default:
+			terms = termlist{t}
+		}
+		// The type set of a union expression is the union
+		// of the type sets of each term.
+		allTerms = allTerms.union(terms)
+	}
+	utyp.tset.terms = allTerms
+
+	return utyp.tset
+}
diff --git a/src/cmd/compile/internal/types2/typestring.go b/src/cmd/compile/internal/types2/typestring.go
index b7e32c9860..558da50528 100644
--- a/src/cmd/compile/internal/types2/typestring.go
+++ b/src/cmd/compile/internal/types2/typestring.go
@@ -158,9 +158,10 @@ func writeType(buf *bytes.Buffer, typ Type, qf Qualifier, visited []Type) {
 		writeSignature(buf, t, qf, visited)
 
 	case *Union:
-		if t.IsEmpty() {
-			buf.WriteString("⊥")
-			break
+		// Unions only appear as (syntactic) embedded elements
+		// in interfaces and syntactically cannot be empty.
+		if t.NumTerms() == 0 {
+			panic("internal error: empty union")
 		}
 		for i, t := range t.terms {
 			if i > 0 {
@@ -198,13 +199,21 @@ func writeType(buf *bytes.Buffer, typ Type, qf Qualifier, visited []Type) {
 				writeSignature(buf, m.typ.(*Signature), qf, visited)
 				empty = false
 			}
-			if !empty && tset.types != nil {
+			if !empty && tset.hasTerms() {
 				buf.WriteString("; ")
 			}
-			if tset.types != nil {
-				buf.WriteString("type ")
-				writeType(buf, tset.types, qf, visited)
-			}
+			first := true
+			tset.is(func(t *term) bool {
+				if !first {
+					buf.WriteByte('|')
+				}
+				first = false
+				if t.tilde {
+					buf.WriteByte('~')
+				}
+				writeType(buf, t.typ, qf, visited)
+				return true
+			})
 		} else {
 			// print explicit interface methods and embedded types
 			for i, m := range t.methods {
diff --git a/src/cmd/compile/internal/types2/typexpr.go b/src/cmd/compile/internal/types2/typexpr.go
index c55d5c093a..fa4a1638b6 100644
--- a/src/cmd/compile/internal/types2/typexpr.go
+++ b/src/cmd/compile/internal/types2/typexpr.go
@@ -147,18 +147,18 @@ func (check *Checker) varType(e syntax.Expr) Type {
 // ordinaryType reports an error if typ is an interface type containing
 // type lists or is (or embeds) the predeclared type comparable.
 func (check *Checker) ordinaryType(pos syntax.Pos, typ Type) {
-	// We don't want to call under() (via Interface) or complete interfaces while we
+	// We don't want to call under() (via asInterface) or complete interfaces while we
 	// are in the middle of type-checking parameter declarations that might belong to
 	// interface methods. Delay this check to the end of type-checking.
 	check.later(func() {
 		if t := asInterface(typ); t != nil {
-			tset := computeTypeSet(check, pos, t) // TODO(gri) is this the correct position?
-			if tset.types != nil {
-				check.softErrorf(pos, "interface contains type constraints (%s)", tset.types)
-				return
-			}
-			if tset.IsComparable() {
-				check.softErrorf(pos, "interface is (or embeds) comparable")
+			tset := computeInterfaceTypeSet(check, pos, t) // TODO(gri) is this the correct position?
+			if !tset.IsMethodSet() {
+				if tset.comparable {
+					check.softErrorf(pos, "interface is (or embeds) comparable")
+				} else {
+					check.softErrorf(pos, "interface contains type constraints")
+				}
 			}
 		}
 	})
diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go
index aa9a23d243..75b9a12197 100644
--- a/src/cmd/compile/internal/types2/unify.go
+++ b/src/cmd/compile/internal/types2/unify.go
@@ -361,9 +361,6 @@ func (u *unifier) nify(x, y Type, p *ifacePair) bool {
 				u.nify(x.results, y.results, p)
 		}
 
-	case *Union:
-		panic("unimplemented: unification with type sets described by types")
-
 	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
@@ -371,7 +368,7 @@ func (u *unifier) nify(x, y Type, p *ifacePair) bool {
 		if y, ok := y.(*Interface); ok {
 			xset := x.typeSet()
 			yset := y.typeSet()
-			if !Identical(xset.types, yset.types) {
+			if !xset.terms.equal(yset.terms) {
 				return false
 			}
 			a := xset.methods
diff --git a/src/cmd/compile/internal/types2/union.go b/src/cmd/compile/internal/types2/union.go
index 1215ef9057..fcd83ce688 100644
--- a/src/cmd/compile/internal/types2/union.go
+++ b/src/cmd/compile/internal/types2/union.go
@@ -9,17 +9,17 @@ import "cmd/compile/internal/syntax"
 // ----------------------------------------------------------------------------
 // API
 
-// A Union represents a union of terms.
+// A Union represents a union of terms embedded in an interface.
 type Union struct {
-	terms []*term
+	terms []*term  // list of syntactical terms (not a canonicalized termlist)
+	tset  *TypeSet // type set described by this union, computed lazily
 }
 
 // NewUnion returns a new Union type with the given terms (types[i], tilde[i]).
-// The lengths of both arguments must match. An empty union represents the set
-// of no types.
+// The lengths of both arguments must match. It is an error to create an empty
+// union; they are syntactically not possible.
 func NewUnion(types []Type, tilde []bool) *Union { return newUnion(types, tilde) }
 
-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 }
 
@@ -29,12 +29,10 @@ func (u *Union) String() string   { return TypeString(u, nil) }
 // ----------------------------------------------------------------------------
 // Implementation
 
-var emptyUnion = new(Union)
-
 func newUnion(types []Type, tilde []bool) *Union {
 	assert(len(types) == len(tilde))
 	if len(types) == 0 {
-		return emptyUnion
+		panic("empty union")
 	}
 	t := new(Union)
 	t.terms = make([]*term, len(types))
@@ -44,52 +42,23 @@ func newUnion(types []Type, tilde []bool) *Union {
 	return t
 }
 
-// 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 _, t := range u.terms {
-		if !f(t) {
-			return false
-		}
-	}
-	return true
-}
-
-// underIs 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.IsEmpty() {
-		return false
-	}
-	for _, t := range u.terms {
-		if !f(under(t.typ)) {
-			return false
-		}
-	}
-	return true
-}
-
 func parseUnion(check *Checker, tlist []syntax.Expr) Type {
-	var types []Type
-	var tilde []bool
+	var terms []*term
 	for _, x := range tlist {
-		t, d := parseTilde(check, x)
-		if len(tlist) == 1 && !d {
-			return t // single type
+		tilde, typ := parseTilde(check, x)
+		if len(tlist) == 1 && !tilde {
+			return typ // single type
 		}
-		types = append(types, t)
-		tilde = append(tilde, d)
+		terms = append(terms, &term{tilde, typ})
 	}
 
-	// Ensure that each type is only present once in the type list.
-	// It's ok to do this check later because it's not a requirement
-	// for correctness of the code.
+	// Check validity of terms.
+	// Do this check later because it requires types to be set up.
 	// Note: This is a quadratic algorithm, but unions tend to be short.
 	check.later(func() {
-		for i, t := range types {
-			t := expand(t)
-			if t == Typ[Invalid] {
+		for i, t := range terms {
+			typ := expand(t.typ)
+			if typ == Typ[Invalid] {
 				continue
 			}
 
@@ -105,16 +74,16 @@ func parseUnion(check *Checker, tlist []syntax.Expr) Type {
 				}
 			}
 
-			u := under(t)
+			u := under(typ)
 			f, _ := u.(*Interface)
-			if tilde[i] {
+			if t.tilde {
 				if f != nil {
-					check.errorf(x, "invalid use of ~ (%s is an interface)", t)
+					check.errorf(x, "invalid use of ~ (%s is an interface)", typ)
 					continue // don't report another error for t
 				}
 
-				if !Identical(u, t) {
-					check.errorf(x, "invalid use of ~ (underlying type of %s is %s)", t, u)
+				if !Identical(u, typ) {
+					check.errorf(x, "invalid use of ~ (underlying type of %s is %s)", typ, u)
 					continue // don't report another error for t
 				}
 			}
@@ -127,19 +96,18 @@ func parseUnion(check *Checker, tlist []syntax.Expr) Type {
 				continue // don't report another error for t
 			}
 
-			// Complain about duplicate entries a|a, but also a|~a, and ~a|~a.
-			// TODO(gri) We should also exclude myint|~int since myint is included in ~int.
-			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)
+			// Report overlapping (non-disjoint) terms such as
+			// a|a, a|~a, ~a|~a, and ~a|A (where under(A) == a).
+			if j := overlappingTerm(terms[:i], t); j >= 0 {
+				check.softErrorf(pos, "overlapping terms %s and %s", t, terms[j])
 			}
 		}
 	})
 
-	return newUnion(types, tilde)
+	return &Union{terms, nil}
 }
 
-func parseTilde(check *Checker, x syntax.Expr) (typ Type, tilde bool) {
+func parseTilde(check *Checker, x syntax.Expr) (tilde bool, typ Type) {
 	if op, _ := x.(*syntax.Operation); op != nil && op.Op == syntax.Tilde {
 		x = op.X
 		tilde = true
@@ -153,116 +121,20 @@ func parseTilde(check *Checker, x syntax.Expr) (typ Type, tilde bool) {
 	return
 }
 
-// intersect computes the intersection of the types x and y,
-// A nil type stands for the set of all types; an empty union
-// stands for the set of no types.
-func intersect(x, y Type) (r Type) {
-	// If one of the types is nil (no restrictions)
-	// the result is the other type.
-	switch {
-	case x == nil:
-		return y
-	case y == nil:
-		return x
-	}
-
-	// Compute the terms which are in both x and y.
-	// TODO(gri) This is not correct as it may not always compute
-	//           the "largest" intersection. For instance, for
-	//           x = myInt|~int, y = ~int
-	//           we get the result myInt but we should get ~int.
-	xu, _ := x.(*Union)
-	yu, _ := y.(*Union)
-	switch {
-	case xu != nil && yu != nil:
-		return &Union{intersectTerms(xu.terms, yu.terms)}
-
-	case xu != nil:
-		if r, _ := xu.intersect(y, false); r != nil {
-			return y
-		}
-
-	case yu != nil:
-		if r, _ := yu.intersect(x, false); r != nil {
-			return x
-		}
-
-	default: // xu == nil && yu == nil
-		if Identical(x, y) {
-			return x
-		}
-	}
-
-	return emptyUnion
-}
-
-// includes reports whether typ is in list.
-func includes(list []Type, typ Type) bool {
-	for _, e := range list {
-		if Identical(typ, e) {
-			return true
-		}
-	}
-	return false
-}
-
-// 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 _, x := range u.terms {
-		xt := x.tilde
-		// determine which types xx, yy to compare
-		xx := x.typ
-		if yt {
-			xx = under(xx)
-		}
-		yy := y
-		if xt {
-			yy = under_y
-		}
-		if Identical(xx, yy) {
-			//  T ∩  T =  T
-			//  T ∩ ~t =  T
-			// ~t ∩  T =  T
-			// ~t ∩ ~t = ~t
-			return xx, xt && yt
-		}
-	}
-	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
+// overlappingTerm reports the index of the term x in terms which is
+// overlapping (not disjoint) from y. The result is < 0 if there is no
+// such term.
+func overlappingTerm(terms []*term, y *term) int {
+	for i, x := range terms {
+		// disjoint requires non-nil, non-top arguments
+		if debug {
+			if x == nil || x.typ == nil || y == nil || y.typ == nil {
+				panic("internal error: empty or top union term")
 			}
 		}
-		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)
-			}
+		if !x.disjoint(y) {
+			return i
 		}
 	}
-	return
+	return -1
 }
diff --git a/src/cmd/compile/internal/types2/universe.go b/src/cmd/compile/internal/types2/universe.go
index a3dd4bd0d6..7b6c297d05 100644
--- a/src/cmd/compile/internal/types2/universe.go
+++ b/src/cmd/compile/internal/types2/universe.go
@@ -89,7 +89,7 @@ func defPredeclaredTypes() {
 		sig := NewSignature(nil, nil, NewTuple(res), false)
 		err := NewFunc(nopos, nil, "Error", sig)
 		ityp := &Interface{obj, []*Func{err}, nil, nil, true, nil}
-		computeTypeSet(nil, nopos, ityp) // prevent races due to lazy computation of tset
+		computeInterfaceTypeSet(nil, nopos, ityp) // prevent races due to lazy computation of tset
 		typ := NewNamed(obj, ityp, nil)
 		sig.recv = NewVar(nopos, nil, "", typ)
 		def(obj)
@@ -99,7 +99,7 @@ func defPredeclaredTypes() {
 	{
 		obj := NewTypeName(nopos, nil, "comparable", nil)
 		obj.setColor(black)
-		ityp := &Interface{obj, nil, nil, nil, true, &TypeSet{true, nil, nil}}
+		ityp := &Interface{obj, nil, nil, nil, true, &TypeSet{true, nil, topTermlist}}
 		NewNamed(obj, ityp, nil)
 		def(obj)
 	}
diff --git a/test/typeparam/mincheck.dir/main.go b/test/typeparam/mincheck.dir/main.go
index 72d8effcc5..9cf2c6bafd 100644
--- a/test/typeparam/mincheck.dir/main.go
+++ b/test/typeparam/mincheck.dir/main.go
@@ -28,11 +28,11 @@ func main() {
 	}
 
 	const want2 = "ay"
-	if got := a.Min[string]("bb", "ay"); got != want2 { // ERROR "string does not satisfy interface{int|int64|float64}"
+	if got := a.Min[string]("bb", "ay"); got != want2 { // ERROR "string does not satisfy"
 		panic(fmt.Sprintf("got %d, want %d", got, want2))
 	}
 
-	if got := a.Min("bb", "ay"); got != want2 { // ERROR "string does not satisfy interface{int|int64|float64}"
+	if got := a.Min("bb", "ay"); got != want2 { // ERROR "string does not satisfy"
 		panic(fmt.Sprintf("got %d, want %d", got, want2))
 	}
 }
-- 
cgit v1.2.3-54-g00ecf