Repository: goadesign/goa (go)

Issue:
v3.2.0: stack overflow on OpenAPI3 generator when used recursive UserType.
It caused a stack overflow when I defined this DSL and executed `goa gen`.

DSL:
```go
var recursiveUserType = Type("recursiveUserType", func() {
	Attribute("children", ArrayOf("recursiveUserType"))
})

var arrResultType = ResultType("recursiveArrayResultType", func() {
	Attribute("result", recursiveUserType)
})

var _ = Service(svc, func() {
	Method(met, func() {
		Result(arrResultType)
		HTTP(func() {
			GET("/")
		})
	})
})
```

Trace:
```
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc020460338 stack=[0xc020460000, 0xc040460000]
fatal error: stack overflow

runtime stack:
runtime.throw(0xa48cf0, 0xe)
	/home/pyyoshi/.gopath/src/runtime/panic.go:1116 +0x72
runtime.newstack()
	/home/pyyoshi/.gopath/src/runtime/stack.go:1034 +0x6ce
runtime.morestack()
	/home/pyyoshi/.gopath/src/runtime/asm_amd64.s:449 +0x8f

goroutine 58 [running]:
runtime.heapBitsSetType(0xc0014a4400, 0x10, 0x10, 0x95faa0)
	/home/pyyoshi/.gopath/src/runtime/mbitmap.go:947 +0xa4d fp=0xc020460348 sp=0xc020460340 pc=0x41811d
runtime.mallocgc(0x10, 0x95faa0, 0x1, 0x0)
	/home/pyyoshi/.gopath/src/runtime/malloc.go:1066 +0x53e fp=0xc0204603e8 sp=0xc020460348 pc=0x40e17e
runtime.makeslice(0x95faa0, 0x1, 0x1, 0x0)
	/home/pyyoshi/.gopath/src/runtime/slice.go:49 +0x6c fp=0xc020460418 sp=0xc0204603e8 pc=0x44d9ec
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c580, 0xb33ca0, 0xc00030b5d8, 0xb38080)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:334 +0xbe fp=0xc0204604d0 sp=0xc020460418 pc=0x8a9bfe
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c6e0, 0xb33ca0, 0xc00030b5d8, 0xc00030b5d8)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:373 +0x62b fp=0xc020460588 sp=0xc0204604d0 pc=0x8aa16b
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c630, 0xb33ca0, 0xc00030b5d8, 0xc00042c630)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:357 +0x427 fp=0xc020460640 sp=0xc020460588 pc=0x8a9f67
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c580, 0xb33ca0, 0xc00030b5d8, 0xb38080)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:342 +0x239 fp=0xc0204606f8 sp=0xc020460640 pc=0x8a9d79
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c6e0, 0xb33ca0, 0xc00030b5d8, 0xc00030b5d8)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:373 +0x62b fp=0xc0204607b0 sp=0xc0204606f8 pc=0x8aa16b
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c630, 0xb33ca0, 0xc00030b5d8, 0xc00042c630)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:357 +0x427 fp=0xc020460868 sp=0xc0204607b0 pc=0x8a9f67
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c580, 0xb33ca0, 0xc00030b5d8, 0xb38080)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:342 +0x239 fp=0xc020460920 sp=0xc020460868 pc=0x8a9d79
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c6e0, 0xb33ca0, 0xc00030b5d8, 0xc00030b5d8)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:373 +0x62b fp=0xc0204609d8 sp=0xc020460920 pc=0x8aa16b
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c630, 0xb33ca0, 0xc00030b5d8, 0xc00042c630)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:357 +0x427 fp=0xc020460a90 sp=0xc0204609d8 pc=0x8a9f67
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c580, 0xb33ca0, 0xc00030b5d8, 0xb38080)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:342 +0x239 fp=0xc020460b48 sp=0xc020460a90 pc=0x8a9d79
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c6e0, 0xb33ca0, 0xc00030b5d8, 0xc00030b5d8)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:373 +0x62b fp=0xc020460c00 sp=0xc020460b48 pc=0x8aa16b
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c630, 0xb33ca0, 0xc00030b5d8, 0xc00042c630)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:357 +0x427 fp=0xc020460cb8 sp=0xc020460c00 pc=0x8a9f67
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c580, 0xb33ca0, 0xc00030b5d8, 0xb38080)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:342 +0x239 fp=0xc020460d70 sp=0xc020460cb8 pc=0x8a9d79
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c6e0, 0xb33ca0, 0xc00030b5d8, 0xc00030b5d8)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:373 +0x62b fp=0xc020460e28 sp=0xc020460d70 pc=0x8aa16b
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c630, 0xb33ca0, 0xc00030b5d8, 0xc00042c630)
	/home/pyyoshi/.gopath/src/goa.design/goa/v3/http/codegen/openapi/v3/types.go:357 +0x427 fp=0xc020460ee0 sp=0xc020460e28 pc=0x8a9f67
goa.design/goa/v3/http/codegen/openapi/v3.hashAttribute(0xc00042c580, 0xb33ca0, 0xc00030b5d8, 0xb38080)

...

```

---

Please excuse me for my poor English. 


Pull request description:
Handle recursive type definitions in OpenAPI v3
Protect against recursive type definitions when computing the hash value
Fix #2629

Patch:
diff --git a/http/codegen/openapi/v3/types.go b/http/codegen/openapi/v3/types.go
index dd428566..71ac3a8e 100644
--- a/http/codegen/openapi/v3/types.go
+++ b/http/codegen/openapi/v3/types.go
@@ -5,7 +5,6 @@ import (
 	"fmt"
 	"hash"
 	"hash/fnv"
-	"sort"
 	"strconv"
 	"strings"
 
@@ -174,7 +173,7 @@ func (sf *schemafier) schemafy(attr *expr.AttributeExpr) *openapi.Schema {
 		s.Type = openapi.Object
 		s.AdditionalProperties = true
 	case expr.UserType:
-		h := hashAttribute(attr, fnv.New64())
+		h := sf.hashAttribute(attr, fnv.New64())
 		if ref, ok := sf.hashes[h]; ok {
 			s.Ref = ref
 		} else {
@@ -325,61 +324,67 @@ func toString(val interface{}) string {
 // structurally equivalent element types, maps with structurally equivalent key
 // and value types or object with identical attribute names and structurally
 // equivalent types and identical set of required attributes.
-func hashAttribute(att *expr.AttributeExpr, h hash.Hash64) uint64 {
+func (sf *schemafier) hashAttribute(att *expr.AttributeExpr, h hash.Hash64) uint64 {
+	return *hashAttribute(att, h, make(map[string]*uint64))
+}
+
+func hashAttribute(att *expr.AttributeExpr, h hash.Hash64, seen map[string]*uint64) *uint64 {
 	t := att.Type
-	switch t.Kind() {
+	if h, ok := seen[t.Hash()]; ok {
+		return h
+	}
+	var res *uint64
+	{
+		var tmp uint64
+		res = &tmp
+	}
+	seen[t.Hash()] = res
 
+	switch t.Kind() {
 	case expr.ObjectKind:
 		o := expr.AsObject(t)
-		keys := make([]string, len(*o))
-		for i, m := range *o {
-			keys[i] = m.Name
-		}
-		sort.Strings(keys)
-		var res uint64
-		for _, k := range keys {
-			kh := hashString(k, h)
-			vh := hashAttribute(o.Attribute(k), h)
-			res = res ^ orderedHash(kh, vh, h)
+		for _, m := range *o {
+			kh := hashString(m.Name, h)
+			vh := hashAttribute(m.Attribute, h, seen)
+			*res = *res ^ orderedHash(kh, *vh, h)
 		}
 		// Objects with a different set of required attributes should produce
 		// different hashes.
 		if att.Validation != nil {
 			for _, req := range att.Validation.Required {
 				rh := hashString(req, h)
-				res = res ^ rh
+				*res = *res ^ rh
 			}
 		}
-		return res
 
 	case expr.ArrayKind:
 		kh := hashString("[]", h)
-		vh := hashAttribute(expr.AsArray(t).ElemType, h)
-		return orderedHash(kh, vh, h)
+		vh := hashAttribute(expr.AsArray(t).ElemType, h, seen)
+		*res = orderedHash(kh, *vh, h)
 
 	case expr.MapKind:
 		m := expr.AsMap(t)
-		kh := hashAttribute(m.KeyType, h)
-		vh := hashAttribute(m.ElemType, h)
-		return orderedHash(kh, vh, h)
+		kh := hashAttribute(m.KeyType, h, seen)
+		vh := hashAttribute(m.ElemType, h, seen)
+		*res = orderedHash(*kh, *vh, h)
 
 	case expr.UserTypeKind:
-		return hashAttribute(t.(expr.UserType).Attribute(), h)
+		*res = *hashAttribute(t.(expr.UserType).Attribute(), h, seen)
 
 	case expr.ResultTypeKind:
 		// The identifier specified in the design for result types should drive
 		// the computation of the hash.
 		rt := t.(*expr.ResultTypeExpr)
-		res := hashString(rt.Identifier, h)
-		view := rt.AttributeExpr.Meta["view"]
-		if len(view) > 0 {
-			return orderedHash(res, hashString(view[0], h), h)
+		*res = hashString(rt.Identifier, h)
+		if view := rt.AttributeExpr.Meta["view"]; len(view) > 0 {
+			*res = orderedHash(*res, hashString(view[0], h), h)
 		}
-		return res
 
 	default: // Primitives or Any
-		return hashString(t.Name(), h)
+		*res = hashString(t.Name(), h)
 	}
+
+	return res
 }
 
 func hashString(s string, h hash.Hash64) uint64 {


Test patch:
diff --git a/http/codegen/openapi/v3/builder_test.go b/http/codegen/openapi/v3/builder_test.go
index 4e320ddd..9e184181 100644
--- a/http/codegen/openapi/v3/builder_test.go
+++ b/http/codegen/openapi/v3/builder_test.go
@@ -135,20 +135,35 @@ func TestBuildOperation(t *testing.T) {
 		Name: "request_string_body",
 		DSL:  dsls.RequestStringBody(svcName, "request_string_body"),
 
-		ExpectedRequestBody: &requestBody{"body", typ{Type: "string"}, true},
+		ExpectedRequestBody: &requestBody{"body", tstring, true},
 		ExpectedResponses:   responses{"200": {}},
 	}, {
 		Name: "request_object_body",
 		DSL:  dsls.RequestObjectBody(svcName, "request_object_body"),
 
-		ExpectedRequestBody: &requestBody{"", typ{Type: "object", Props: mtyp{"name": typ{Type: "string"}}}, true},
+		ExpectedRequestBody: &requestBody{"", tobj("name", tstring), true},
 		ExpectedResponses:   responses{"200": {}},
 	}, {
 		Name: "request_streaming_string_body",
 		DSL:  dsls.RequestObjectBody(svcName, "request_streaming_string_body"),
 
-		ExpectedRequestBody: &requestBody{"", typ{Type: "object", Props: mtyp{"name": typ{Type: "string"}}}, true},
+		ExpectedRequestBody: &requestBody{"", tobj("name", tstring), true},
 		ExpectedResponses:   responses{"200": {}},
+	}, {
+		Name: "response_array_of_string",
+		DSL:  dsls.ResponseArrayOfString(svcName, "response_array_of_string"),
+
+		ExpectedResponses: responses{"200": {"", tobj("result", tobj("children", tarray)), nil}},
+	}, {
+		Name: "response_recursive_user_type",
+		DSL:  dsls.ResponseRecursiveUserType(svcName, "response_recursive_user_type"),
+
+		ExpectedResponses: responses{"200": {"", tobj("recursive", tobj()), nil}},
+	}, {
+		Name: "response_recursive_array_user_type",
+		DSL:  dsls.ResponseRecursiveArrayUserType(svcName, "response_recursive_array_user_type"),
+
+		ExpectedResponses: responses{"200": {"", tobj("result", tobj("children", tarray)), nil}},
 	}}
 	for _, c := range cases {
 		t.Run(c.Name, func(t *testing.T) {
diff --git a/http/codegen/openapi/v3/testdata/dsls/operations.go b/http/codegen/openapi/v3/testdata/dsls/operations.go
index 60610b17..6321a175 100644
--- a/http/codegen/openapi/v3/testdata/dsls/operations.go
+++ b/http/codegen/openapi/v3/testdata/dsls/operations.go
@@ -99,3 +99,62 @@ var ResponseObjectBody = func(svc, met string) func() {
 		})
 	}
 }
+
+var ResponseArrayOfString = func(svc, met string) func() {
+	return func() {
+		var arrayOfType = Type("arrayOfString", func() {
+			Attribute("children", ArrayOf(String))
+		})
+
+		var arrResultType = ResultType("arrResultType", func() {
+			Attribute("result", arrayOfType)
+		})
+
+		var _ = Service(svc, func() {
+			Method(met, func() {
+				Result(arrResultType)
+				HTTP(func() {
+					GET("/")
+				})
+			})
+		})
+	}
+}
+
+var ResponseRecursiveUserType = func(svc, met string) func() {
+	return func() {
+		var recursiveType = Type("recursiveType", func() {
+			Attribute("recursive", "recursiveType")
+		})
+
+		var _ = Service(svc, func() {
+			Method(met, func() {
+				Result(recursiveType)
+				HTTP(func() {
+					GET("/")
+				})
+			})
+		})
+	}
+}
+
+var ResponseRecursiveArrayUserType = func(svc, met string) func() {
+	return func() {
+		var recursiveType = Type("recursiveType", func() {
+			Attribute("children", ArrayOf("recursiveType"))
+		})
+
+		var arrResultType = ResultType("recursiveArrayResultType", func() {
+			Attribute("result", recursiveType)
+		})
+
+		var _ = Service(svc, func() {
+			Method(met, func() {
+				Result(arrResultType)
+				HTTP(func() {
+					GET("/")
+				})
+			})
+		})
+	}
+}
diff --git a/http/codegen/openapi/v3/types_test.go b/http/codegen/openapi/v3/types_test.go
index 45291d6b..5ac617fb 100644
--- a/http/codegen/openapi/v3/types_test.go
+++ b/http/codegen/openapi/v3/types_test.go
@@ -13,16 +13,47 @@ import (
 
 // describes a type for comparison in tests.
 type typ struct {
-	Type  string
-	Props mtyp
+	Type      string
+	Props     []attr
+	SkipProps bool
 }
 
-// convenience
-type mtyp map[string]typ
+type attr struct {
+	Name string
+	Val  typ
+}
 
 // types mapped by response code.
 type rt map[int]typ
 
+// helpers
+var (
+	tempty  typ
+	tstring = typ{Type: "string"}
+	tint    = typ{Type: "integer"}
+	tarray  = typ{Type: "array"}
+)
+
+func tobj(attrs ...interface{}) typ {
+	res := typ{Type: "object"}
+	if len(attrs) == 0 {
+		res.SkipProps = true
+	}
+	for i := 0; i < len(attrs); i += 2 {
+		res.Props = append(res.Props, attr{Name: attrs[i].(string), Val: attrs[i+1].(typ)})
+	}
+	return res
+}
+
+func (tt typ) Prop(n string) (typ, bool) {
+	for _, att := range tt.Props {
+		if att.Name == n {
+			return att.Val, true
+		}
+	}
+	return tempty, false
+}
+
 func TestBuildBodyTypes(t *testing.T) {
 	const svcName = "test service"
 
@@ -36,62 +67,62 @@ func TestBuildBodyTypes(t *testing.T) {
 		Name: "string_body",
 		DSL:  dsls.StringBodyDSL(svcName, "string_body"),
 
-		ExpectedType:          typ{"string", nil},
-		ExpectedResponseTypes: rt{204: {"", nil}},
+		ExpectedType:          tstring,
+		ExpectedResponseTypes: rt{204: tempty},
 	}, {
 		Name: "object_body",
 		DSL:  dsls.ObjectBodyDSL(svcName, "object_body"),
 
-		ExpectedType:          typ{"object", mtyp{"name": {"string", nil}, "age": {"integer", nil}}},
-		ExpectedResponseTypes: rt{204: {"", nil}},
+		ExpectedType:          tobj("name", tstring, "age", tint),
+		ExpectedResponseTypes: rt{204: tempty},
 	}, {
 		Name: "streaming_string_body",
 		DSL:  dsls.RequestStreamingStringBody(svcName, "streaming_string_body"),
 
-		ExpectedType:          typ{"string", nil},
-		ExpectedResponseTypes: rt{204: {"", nil}},
+		ExpectedType:          tstring,
+		ExpectedResponseTypes: rt{204: tempty},
 	}, {
 		Name: "streaming_object_body",
 		DSL:  dsls.RequestStreamingObjectBody(svcName, "streaming_object_body"),
 
-		ExpectedType:          typ{"object", mtyp{"name": {"string", nil}, "age": {"integer", nil}}},
-		ExpectedResponseTypes: rt{204: {"", nil}},
+		ExpectedType:          tobj("name", tstring, "age", tint),
+		ExpectedResponseTypes: rt{204: tempty},
 	}, {
 		Name: "string_response_body",
 		DSL:  dsls.StringResponseBodyDSL(svcName, "string_response_body"),
 
-		ExpectedType:          typ{"", nil},
-		ExpectedResponseTypes: rt{200: {"string", nil}},
+		ExpectedType:          tempty,
+		ExpectedResponseTypes: rt{200: tstring},
 	}, {
 		Name: "object_response_body",
 		DSL:  dsls.ObjectResponseBodyDSL(svcName, "object_response_body"),
 
-		ExpectedType:          typ{"", nil},
-		ExpectedResponseTypes: rt{200: {"object", mtyp{"name": typ{"string", nil}, "age": typ{"integer", nil}}}},
+		ExpectedType:          tempty,
+		ExpectedResponseTypes: rt{200: tobj("name", tstring, "age", tint)},
 	}, {
 		Name: "string_streaming_response_body",
 		DSL:  dsls.StringStreamingResponseBodyDSL(svcName, "string_streaming_response_body"),
 
-		ExpectedType:          typ{"", nil},
-		ExpectedResponseTypes: rt{200: {"string", nil}},
+		ExpectedType:          tempty,
+		ExpectedResponseTypes: rt{200: tstring},
 	}, {
 		Name: "object_streaming_response_body",
 		DSL:  dsls.ObjectResponseBodyDSL(svcName, "object_streaming_response_body"),
 
-		ExpectedType:          typ{"", nil},
-		ExpectedResponseTypes: rt{200: {"object", mtyp{"name": typ{"string", nil}, "age": typ{"integer", nil}}}},
+		ExpectedType:          tempty,
+		ExpectedResponseTypes: rt{200: tobj("name", tstring, "age", tint)},
 	}, {
 		Name: "string_error_response",
 		DSL:  dsls.StringErrorResponseBodyDSL(svcName, "string_error_response"),
 
-		ExpectedType:          typ{"", nil},
-		ExpectedResponseTypes: rt{204: {"", nil}, 400: {"string", nil}},
+		ExpectedType:          tempty,
+		ExpectedResponseTypes: rt{204: tempty, 400: tstring},
 	}, {
 		Name: "object_error_response",
 		DSL:  dsls.ObjectErrorResponseBodyDSL(svcName, "object_error_response"),
 
-		ExpectedType:          typ{"", nil},
-		ExpectedResponseTypes: rt{204: {"", nil}, 400: {"object", mtyp{"name": typ{"string", nil}, "age": typ{"integer", nil}}}},
+		ExpectedType:          tempty,
+		ExpectedResponseTypes: rt{204: tempty, 400: tobj("name", tstring, "age", tint)},
 	}}
 
 	for _, c := range cases {
@@ -156,8 +187,16 @@ func matchesSchemaWithPrefix(t *testing.T, ctx string, s *openapi.Schema, types
 		t.Errorf("%s: %sgot type %q, expected %q", ctx, prefix, s.Type, tt.Type)
 	}
 	if tt.Type == "object" {
+		if tt.SkipProps {
+			return
+		}
 		for n, v := range s.Properties {
-			matchesSchemaWithPrefix(t, ctx, v, types, tt.Props[n], n+": ")
+			p, ok := tt.Prop(n)
+			if !ok {
+				t.Errorf("%s: %sgot unexpected field %q", ctx, prefix, n)
+				continue
+			}
+			matchesSchemaWithPrefix(t, ctx, v, types, p, n+": ")
 		}
 	}
 }
@@ -212,9 +251,10 @@ func TestHashAttribute(t *testing.T) {
 		{"result-same", newRT("id", newObj("foo", expr.Int, true)), h5},
 	}
 	h := fnv.New64()
+	sf := newSchemafier(expr.NewRandom("test"))
 	for _, c := range cases {
 		t.Run(c.Name, func(t *testing.T) {
-			got := hashAttribute(c.att, h)
+			got := sf.hashAttribute(c.att, h)
 			if got != c.h {
 				t.Errorf("got %v, expected %v", got, c.h)
 			}