pkg/compiler: fix almost infinite recursion in template instantiation

Fix another cases where recurion is finite but fan out factor is large,
so our recursion check would take 5^10 iterations to handle this.

3 files changed, 48 insertions, 25 deletions

diff --git a/pkg/compiler/check.go b/pkg/compiler/check.go
index fcc1d0f16..75857be40 100644
--- a/pkg/compiler/check.go
+++ b/pkg/compiler/check.go
@@ -902,12 +902,25 @@ func (comp *compiler) checkTypeArgs(t *ast.Type, desc *typeDesc, flags checkFlag
 
 func (comp *compiler) replaceTypedef(ctx *checkCtx, t *ast.Type, flags checkFlags) {
 	typedefName := t.Ident
+	typedef := comp.typedefs[typedefName]
+	fullTypeName := ast.SerializeNode(t)
+	if comp.brokenTypedefs[fullTypeName] {
+		// We've already produced some errors for this exact type instantiation.
+		// Don't produce duplicates, also helps to prevent exponential
+		// slowdown due to some cases of recursion. But increment the number
+		// of errors so that callers can understand that we did not succeed.
+		comp.errors++
+		return
+	}
 	comp.usedTypedefs[typedefName] = true
+	err0 := comp.errors
+	defer func() {
+		comp.brokenTypedefs[fullTypeName] = err0 != comp.errors
+	}()
 	if len(t.Colon) != 0 {
 		comp.error(t.Pos, "type alias %v with ':'", t.Ident)
 		return
 	}
-	typedef := comp.typedefs[typedefName]
 	// Handling optional BASE argument.
 	if len(typedef.Args) > 0 && typedef.Args[len(typedef.Args)-1].Name == argBase {
 		if flags&checkIsArg != 0 && len(t.Args) == len(typedef.Args)-1 {
@@ -920,7 +933,6 @@ func (comp *compiler) replaceTypedef(ctx *checkCtx, t *ast.Type, flags checkFlag
 		}
 	}
 	recursion := 0
-	fullTypeName := ast.SerializeNode(t)
 	ctx.instantiationStack = append(ctx.instantiationStack, fullTypeName)
 	for i, prev := range ctx.instantiationStack[:len(ctx.instantiationStack)-1] {
 		if typedefName == templateBase(prev) {
@@ -963,7 +975,6 @@ func (comp *compiler) replaceTypedef(ctx *checkCtx, t *ast.Type, flags checkFlag
 			if !comp.instantiate(inst, typedef.Args, args) {
 				return
 			}
-			err0 := comp.errors
 			comp.checkStruct(*ctx, inst)
 			if err0 != comp.errors {
 				return
diff --git a/pkg/compiler/compiler.go b/pkg/compiler/compiler.go
index a361b3928..62a102d40 100644
--- a/pkg/compiler/compiler.go
+++ b/pkg/compiler/compiler.go
@@ -49,20 +49,21 @@ func createCompiler(desc *ast.Description, target *targets.Target, eh ast.ErrorH
 	}
 	desc.Nodes = append(builtinDescs.Clone().Nodes, desc.Nodes...)
 	comp := &compiler{
-		desc:         desc,
-		target:       target,
-		eh:           eh,
-		ptrSize:      target.PtrSize,
-		unsupported:  make(map[string]bool),
-		resources:    make(map[string]*ast.Resource),
-		typedefs:     make(map[string]*ast.TypeDef),
-		structs:      make(map[string]*ast.Struct),
-		intFlags:     make(map[string]*ast.IntFlags),
-		strFlags:     make(map[string]*ast.StrFlags),
-		used:         make(map[string]bool),
-		usedTypedefs: make(map[string]bool),
-		structVarlen: make(map[string]bool),
-		structTypes:  make(map[string]prog.Type),
+		desc:           desc,
+		target:         target,
+		eh:             eh,
+		ptrSize:        target.PtrSize,
+		unsupported:    make(map[string]bool),
+		resources:      make(map[string]*ast.Resource),
+		typedefs:       make(map[string]*ast.TypeDef),
+		structs:        make(map[string]*ast.Struct),
+		intFlags:       make(map[string]*ast.IntFlags),
+		strFlags:       make(map[string]*ast.StrFlags),
+		used:           make(map[string]bool),
+		usedTypedefs:   make(map[string]bool),
+		brokenTypedefs: make(map[string]bool),
+		structVarlen:   make(map[string]bool),
+		structTypes:    make(map[string]prog.Type),
 		builtinConsts: map[string]uint64{
 			"PTR_SIZE": target.PtrSize,
 		},
@@ -121,14 +122,15 @@ type compiler struct {
 	warnings []warn
 	ptrSize  uint64
 
-	unsupported  map[string]bool
-	resources    map[string]*ast.Resource
-	typedefs     map[string]*ast.TypeDef
-	structs      map[string]*ast.Struct
-	intFlags     map[string]*ast.IntFlags
-	strFlags     map[string]*ast.StrFlags
-	used         map[string]bool // contains used structs/resources
-	usedTypedefs map[string]bool
+	unsupported    map[string]bool
+	resources      map[string]*ast.Resource
+	typedefs       map[string]*ast.TypeDef
+	structs        map[string]*ast.Struct
+	intFlags       map[string]*ast.IntFlags
+	strFlags       map[string]*ast.StrFlags
+	used           map[string]bool // contains used structs/resources
+	usedTypedefs   map[string]bool
+	brokenTypedefs map[string]bool
 
 	structVarlen  map[string]bool
 	structTypes   map[string]prog.Type
diff --git a/pkg/compiler/compiler_test.go b/pkg/compiler/compiler_test.go
index 8045bf608..79735d10a 100644
--- a/pkg/compiler/compiler_test.go
+++ b/pkg/compiler/compiler_test.go
@@ -136,6 +136,16 @@ func TestFuzz(t *testing.T) {
 	t.Parallel()
 	for _, data := range []string{
 		`
+type H b[A]
+type b[L] {
+	m b[u:L]
+	l b[z:L]
+	m b[V:L]
+	m b[0:L]
+	H b[o:L]
+}
+`,
+		`
 type p b[L]
 type b[L]{
 	e b[3:L]