[dev.typeparams] cmd/compile/internal/types2: limit termlist lengths

At the moment, operations on termlists are O(n^2).
This is fine for normal-sized unions, but overlong
termlist lenghts will lead to excessive type checking
times.

Limit the length of termlists to avoid "compilations
that don't finish".

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

5 files changed, 117 insertions, 5 deletions

diff --git a/src/cmd/compile/internal/types2/interface.go b/src/cmd/compile/internal/types2/interface.go
index f763f8ff44..89cf846598 100644
--- a/src/cmd/compile/internal/types2/interface.go
+++ b/src/cmd/compile/internal/types2/interface.go
@@ -140,7 +140,7 @@ func (check *Checker) interfaceType(ityp *Interface, iface *syntax.InterfaceType
 	for _, f := range iface.MethodList {
 		if f.Name == nil {
 			// We have an embedded type; possibly a union of types.
-			addEmbedded(f.Type.Pos(), parseUnion(check, flattenUnion(nil, f.Type)))
+			addEmbedded(posFor(f.Type), parseUnion(check, flattenUnion(nil, f.Type)))
 			continue
 		}
 		// f.Name != nil
diff --git a/src/cmd/compile/internal/types2/testdata/check/unions.go2 b/src/cmd/compile/internal/types2/testdata/check/unions.go2
new file mode 100644
index 0000000000..bcd7de6644
--- /dev/null
+++ b/src/cmd/compile/internal/types2/testdata/check/unions.go2
@@ -0,0 +1,66 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Check that overlong unions don't bog down type checking.
+// Disallow them for now.
+
+package p
+
+type t int
+
+type (
+	t00 t; t01 t; t02 t; t03 t; t04 t; t05 t; t06 t; t07 t; t08 t; t09 t
+	t10 t; t11 t; t12 t; t13 t; t14 t; t15 t; t16 t; t17 t; t18 t; t19 t
+	t20 t; t21 t; t22 t; t23 t; t24 t; t25 t; t26 t; t27 t; t28 t; t29 t
+	t30 t; t31 t; t32 t; t33 t; t34 t; t35 t; t36 t; t37 t; t38 t; t39 t
+	t40 t; t41 t; t42 t; t43 t; t44 t; t45 t; t46 t; t47 t; t48 t; t49 t
+	t50 t; t51 t; t52 t; t53 t; t54 t; t55 t; t56 t; t57 t; t58 t; t59 t
+	t60 t; t61 t; t62 t; t63 t; t64 t; t65 t; t66 t; t67 t; t68 t; t69 t
+	t70 t; t71 t; t72 t; t73 t; t74 t; t75 t; t76 t; t77 t; t78 t; t79 t
+	t80 t; t81 t; t82 t; t83 t; t84 t; t85 t; t86 t; t87 t; t88 t; t89 t
+	t90 t; t91 t; t92 t; t93 t; t94 t; t95 t; t96 t; t97 t; t98 t; t99 t
+)
+
+type u99 interface {
+	t00|t01|t02|t03|t04|t05|t06|t07|t08|t09|
+	t10|t11|t12|t13|t14|t15|t16|t17|t18|t19|
+	t20|t21|t22|t23|t24|t25|t26|t27|t28|t29|
+	t30|t31|t32|t33|t34|t35|t36|t37|t38|t39|
+	t40|t41|t42|t43|t44|t45|t46|t47|t48|t49|
+	t50|t51|t52|t53|t54|t55|t56|t57|t58|t59|
+	t60|t61|t62|t63|t64|t65|t66|t67|t68|t69|
+	t70|t71|t72|t73|t74|t75|t76|t77|t78|t79|
+	t80|t81|t82|t83|t84|t85|t86|t87|t88|t89|
+	t90|t91|t92|t93|t94|t95|t96|t97|t98
+}
+
+type u100a interface {
+	u99|float32
+}
+
+type u100b interface {
+	u99|float64
+}
+
+type u101 interface {
+	t00|t01|t02|t03|t04|t05|t06|t07|t08|t09|
+	t10|t11|t12|t13|t14|t15|t16|t17|t18|t19|
+	t20|t21|t22|t23|t24|t25|t26|t27|t28|t29|
+	t30|t31|t32|t33|t34|t35|t36|t37|t38|t39|
+	t40|t41|t42|t43|t44|t45|t46|t47|t48|t49|
+	t50|t51|t52|t53|t54|t55|t56|t57|t58|t59|
+	t60|t61|t62|t63|t64|t65|t66|t67|t68|t69|
+	t70|t71|t72|t73|t74|t75|t76|t77|t78|t79|
+	t80|t81|t82|t83|t84|t85|t86|t87|t88|t89|
+	t90|t91|t92|t93|t94|t95|t96|t97|t98|t99|
+        int // ERROR cannot handle more than 100 union terms
+}
+
+type u102 interface {
+        int /* ERROR cannot handle more than 100 union terms */ |string|u100a
+}
+
+type u200 interface {
+        u100a /* ERROR cannot handle more than 100 union terms */ |u100b
+}
diff --git a/src/cmd/compile/internal/types2/typeset.go b/src/cmd/compile/internal/types2/typeset.go
index da364699ce..5955bbe805 100644
--- a/src/cmd/compile/internal/types2/typeset.go
+++ b/src/cmd/compile/internal/types2/typeset.go
@@ -268,9 +268,9 @@ func computeInterfaceTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *T
 			pos = (*ityp.embedPos)[i]
 		}
 		var terms termlist
-		switch t := under(typ).(type) {
+		switch u := under(typ).(type) {
 		case *Interface:
-			tset := computeInterfaceTypeSet(check, pos, t)
+			tset := computeInterfaceTypeSet(check, pos, u)
 			if tset.comparable {
 				ityp.tset.comparable = true
 			}
@@ -279,7 +279,10 @@ func computeInterfaceTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *T
 			}
 			terms = tset.terms
 		case *Union:
-			tset := computeUnionTypeSet(check, pos, t)
+			tset := computeUnionTypeSet(check, pos, u)
+			if tset == &invalidTypeSet {
+				continue // ignore invalid unions
+			}
 			terms = tset.terms
 		case *TypeParam:
 			// Embedding stand-alone type parameters is not permitted.
@@ -297,6 +300,8 @@ func computeInterfaceTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *T
 		}
 		// The type set of an interface is the intersection
 		// of the type sets of all its elements.
+		// Intersection cannot produce longer termlists and
+		// thus cannot overflow.
 		allTerms = allTerms.intersect(terms)
 	}
 	ityp.embedPos = nil // not needed anymore (errors have been reported)
@@ -339,7 +344,13 @@ 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] }
 
+// invalidTypeSet is a singleton type set to signal an invalid type set
+// due to an error. It's also a valid empty type set, so consumers of
+// type sets may choose to ignore it.
+var invalidTypeSet TypeSet
+
 // computeUnionTypeSet may be called with check == nil.
+// The result is &invalidTypeSet if the union overflows.
 func computeUnionTypeSet(check *Checker, pos syntax.Pos, utyp *Union) *TypeSet {
 	if utyp.tset != nil {
 		return utyp.tset
@@ -359,11 +370,21 @@ func computeUnionTypeSet(check *Checker, pos syntax.Pos, utyp *Union) *TypeSet {
 			// This case is handled during union parsing.
 			unreachable()
 		default:
+			if t.typ == Typ[Invalid] {
+				continue
+			}
 			terms = termlist{(*term)(t)}
 		}
 		// The type set of a union expression is the union
 		// of the type sets of each term.
 		allTerms = allTerms.union(terms)
+		if len(allTerms) > maxTermCount {
+			if check != nil {
+				check.errorf(pos, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
+			}
+			utyp.tset = &invalidTypeSet
+			return utyp.tset
+		}
 	}
 	utyp.tset.terms = allTerms
 
diff --git a/src/cmd/compile/internal/types2/typeset_test.go b/src/cmd/compile/internal/types2/typeset_test.go
new file mode 100644
index 0000000000..0e14d523c8
--- /dev/null
+++ b/src/cmd/compile/internal/types2/typeset_test.go
@@ -0,0 +1,15 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types2
+
+import "testing"
+
+func TestInvalidTypeSet(t *testing.T) {
+	if !invalidTypeSet.IsEmpty() {
+		t.Error("invalidTypeSet is not empty")
+	}
+}
+
+// TODO(gri) add more tests
diff --git a/src/cmd/compile/internal/types2/union.go b/src/cmd/compile/internal/types2/union.go
index 102826947c..85aa3d9104 100644
--- a/src/cmd/compile/internal/types2/union.go
+++ b/src/cmd/compile/internal/types2/union.go
@@ -43,12 +43,22 @@ func (t *Term) String() string { return (*term)(t).String() }
 // ----------------------------------------------------------------------------
 // Implementation
 
+// Avoid excessive type-checking times due to quadratic termlist operations.
+const maxTermCount = 100
+
+// parseUnion parses the given list of type expressions tlist as a union of
+// those expressions. The result is a Union type, or Typ[Invalid] for some
+// errors.
 func parseUnion(check *Checker, tlist []syntax.Expr) Type {
 	var terms []*Term
 	for _, x := range tlist {
 		tilde, typ := parseTilde(check, x)
 		if len(tlist) == 1 && !tilde {
-			return typ // single type
+			return typ // single type (optimization)
+		}
+		if len(terms) >= maxTermCount {
+			check.errorf(x, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
+			return Typ[Invalid]
 		}
 		terms = append(terms, NewTerm(tilde, typ))
 	}