pkg/compiler: fix infinite recursion in template instantiation

Fix a bug found by OSS-Fuzz:
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=17240

We handled the case of infinite recursion in templates
but only if the full type name matches precisely (A -> B -> A).
In this case the name constantly changes due to different
template arguments. Per se this is a not an error
(and we have real cases that use this, e.g. when an nlattr_t
contains nested nlattr_t's), but it's an error if it recurses
infinitely. Restrict recursion on the same template to 10 levels.

3 files changed, 41 insertions, 18 deletions

diff --git a/pkg/compiler/check.go b/pkg/compiler/check.go
index 6da7e3ddf..fcc1d0f16 100644
--- a/pkg/compiler/check.go
+++ b/pkg/compiler/check.go
@@ -318,13 +318,17 @@ type parentDesc struct {
 	fields []*ast.Field
 }
 
-func parentTargetName(s *ast.Struct) string {
-	parentName := s.Name.Name
-	if pos := strings.IndexByte(parentName, '['); pos != -1 {
-		// For template parents name is "struct_name[ARG1, ARG2]", strip the part after '['.
-		parentName = parentName[:pos]
+// templateName return the part before '[' for full template names.
+func templateBase(name string) string {
+	if pos := strings.IndexByte(name, '['); pos != -1 {
+		return name[:pos]
 	}
-	return parentName
+	return name
+}
+
+func parentTargetName(s *ast.Struct) string {
+	// For template parents name is "struct_name[ARG1, ARG2]", strip the part after '['.
+	return templateBase(s.Name.Name)
 }
 
 func (comp *compiler) checkLenType(t0, t *ast.Type, parents []parentDesc,
@@ -915,22 +919,23 @@ func (comp *compiler) replaceTypedef(ctx *checkCtx, t *ast.Type, flags checkFlag
 			comp.checkTypeArg(t, t.Args[len(t.Args)-1], typeArgBase)
 		}
 	}
+	recursion := 0
 	fullTypeName := ast.SerializeNode(t)
-	for i, prev := range ctx.instantiationStack {
-		if prev == fullTypeName {
-			ctx.instantiationStack = append(ctx.instantiationStack, fullTypeName)
-			path := ""
-			for j := i; j < len(ctx.instantiationStack); j++ {
-				if j != i {
-					path += " -> "
-				}
-				path += ctx.instantiationStack[j]
+	ctx.instantiationStack = append(ctx.instantiationStack, fullTypeName)
+	for i, prev := range ctx.instantiationStack[:len(ctx.instantiationStack)-1] {
+		if typedefName == templateBase(prev) {
+			recursion++
+			if recursion > 10 {
+				comp.error(t.Pos, "type instantiation recursion: %v", strings.Join(ctx.instantiationStack, " -> "))
+				return
 			}
-			comp.error(t.Pos, "type instantiation loop: %v", path)
-			return
 		}
+		if prev != fullTypeName {
+			continue
+		}
+		comp.error(t.Pos, "type instantiation loop: %v", strings.Join(ctx.instantiationStack[i:], " -> "))
+		return
 	}
-	ctx.instantiationStack = append(ctx.instantiationStack, fullTypeName)
 	nargs := len(typedef.Args)
 	args := t.Args
 	if nargs != len(t.Args) {
@@ -958,7 +963,11 @@ 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
+			}
 			comp.desc.Nodes = append(comp.desc.Nodes, inst)
 			comp.structs[fullTypeName] = inst
 		}
diff --git a/pkg/compiler/compiler_test.go b/pkg/compiler/compiler_test.go
index 131270939..8045bf608 100644
--- a/pkg/compiler/compiler_test.go
+++ b/pkg/compiler/compiler_test.go
@@ -135,6 +135,15 @@ func TestData(t *testing.T) {
 func TestFuzz(t *testing.T) {
 	t.Parallel()
 	for _, data := range []string{
+		`
+type p b[L]
+type b[L]{
+	e b[3:L]
+	e b[2:L]
+	e b[1[L]]
+	k b[H]
+	k b[Q]
+}`,
 		"d~^gB̉`i\u007f?\xb0.",
 		"da[",
 		"define\x98define(define\x98define\x98define\x98define\x98define)define\tdefin",
diff --git a/pkg/compiler/testdata/errors.txt b/pkg/compiler/testdata/errors.txt
index 670cc0193..db653c180 100644
--- a/pkg/compiler/testdata/errors.txt
+++ b/pkg/compiler/testdata/errors.txt
@@ -334,6 +334,11 @@ foo$210(a ptr[in, templ11[0, 1, int8]])		### template templ11 needs 2 arguments
 foo$211(a ptr[in, templ9])			### template templ9 needs 1 arguments instead of 0
 foo$212(a ptr[in, templ11[1]])			### template templ11 needs 2 arguments instead of 1
 
+type TR[A, B] {
+	f TR[A, A[B]]		### type instantiation recursion: TR[X, Y] -> TR[X, X[Y]] -> TR[X, X[X[Y]]] -> TR[X, X[X[X[Y]]]] -> TR[X, X[X[X[X[Y]]]]] -> TR[X, X[X[X[X[X[Y]]]]]] -> TR[X, X[X[X[X[X[X[Y]]]]]]] -> TR[X, X[X[X[X[X[X[X[Y]]]]]]]] -> TR[X, X[X[X[X[X[X[X[X[Y]]]]]]]]] -> TR[X, X[X[X[X[X[X[X[X[X[Y]]]]]]]]]] -> TR[X, X[X[X[X[X[X[X[X[X[X[Y]]]]]]]]]]] -> TR[X, X[X[X[X[X[X[X[X[X[X[X[Y]]]]]]]]]]]]
+}
+type TU TR[X, Y]
+
 foo$glob001(a ptr[in, glob[1]])			### unexpected int 1, string arg must be a string literal or string flags
 foo$glob002(a ptr[in, glob])			### glob only accepts 1 arg, provided 0
 foo$glob003(a ptr[in, glob["/sys", 5]])		### glob only accepts 1 arg, provided 2