From 9bd1817e417e9f07c6b3aba0189576bbf06f1592 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Thu, 5 Aug 2021 18:14:28 -0700 Subject: [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 Run-TryBot: Robert Griesemer TryBot-Result: Go Bot Reviewed-by: Robert Findley --- src/cmd/compile/internal/types2/interface.go | 2 +- .../internal/types2/testdata/check/unions.go2 | 66 ++++++++++++++++++++++ src/cmd/compile/internal/types2/typeset.go | 27 ++++++++- src/cmd/compile/internal/types2/typeset_test.go | 15 +++++ src/cmd/compile/internal/types2/union.go | 12 +++- 5 files changed, 117 insertions(+), 5 deletions(-) create mode 100644 src/cmd/compile/internal/types2/testdata/check/unions.go2 create mode 100644 src/cmd/compile/internal/types2/typeset_test.go 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)) } -- cgit v1.2.3-54-g00ecf