Repository: google/go-flow-levee (go)

Issue:
Stack Overflow in internal/pkg/sourcetype/sourcetype.go
## Bug report

**Describe the bug**
There appears to be a stack overflow in internal/pkg/sourcetype/sourcetype.go, as a result of infinite recursion between line 36 and line 45 (checking whether `type.Named` type is a source type and checking whether a `map` element is a source type). This may be triggered by creating a named map type where which stores elements of its own type.

**To Reproduce**
Run go-flow-levee on the following code:

```go
package main

type Tree map[string]Tree

func main() {
	_ = make(Tree)
}
```

**Additional context**
Stacktrace:

```
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc02288e470 stack=[0xc02288e000, 0xc04288e000]
fatal error: stack overflow

runtime stack:
runtime.throw(0x1424e9f, 0xe)
        /usr/local/opt/go/libexec/src/runtime/panic.go:1116 +0x72
runtime.newstack()
        /usr/local/opt/go/libexec/src/runtime/stack.go:1060 +0x78d
runtime.morestack()
        /usr/local/opt/go/libexec/src/runtime/asm_amd64.s:449 +0x8f

goroutine 6 [running]:
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:32 +0x5db fp=0xc02288e480 sp=0xc02288e478 pc=0x12915db
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:36 +0x5b6 fp=0xc02288e608 sp=0xc02288e480 pc=0x12915b6
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:45 +0x24f fp=0xc02288e790 sp=0xc02288e608 pc=0x129124f
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:36 +0x5b6 fp=0xc02288e918 sp=0xc02288e790 pc=0x12915b6
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:45 +0x24f fp=0xc02288eaa0 sp=0xc02288e918 pc=0x129124f
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:36 +0x5b6 fp=0xc02288ec28 sp=0xc02288eaa0 pc=0x12915b6
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:45 +0x24f fp=0xc02288edb0 sp=0xc02288ec28 pc=0x129124f
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:36 +0x5b6 fp=0xc02288ef38 sp=0xc02288edb0 pc=0x12915b6
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:45 +0x24f fp=0xc02288f0c0 sp=0xc02288ef38 pc=0x129124f
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:36 +0x5b6 fp=0xc02288f248 sp=0xc02288f0c0 pc=0x12915b6
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:45 +0x24f fp=0xc02288f3d0 sp=0xc02288f248 pc=0x129124f
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:36 +0x5b6 fp=0xc02288f558 sp=0xc02288f3d0 pc=0x12915b6
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a00, 0xc000677c20, 0x0)
        /base/go/pkg/mod/github.com/google/go-flow-levee@v0.1.5/internal/pkg/sourcetype/sourcetype.go:45 +0x24f fp=0xc02288f6e0 sp=0xc02288f558 pc=0x129124f
github.com/google/go-flow-levee/internal/pkg/sourcetype.IsSourceType(0xc0001bc2d0, 0xc0010f8120, 0x1497a40, 0xc00068b7c0, 0x0)
```


Pull request description:
Avoid stack overflow in sourcetype.IsSourceType.
Fixes #320.

In my understanding, a stack overflow can occur whenever we have a value of a type that is self-referential. Not all self-referential types are allowed by the compiler, e.g. `type A A` (which is nonsensical) is not allowed, but `type A map[string]A` is allowed (consider a tree-like type).

This PR adds a `map[types.Type]bool` of seen types to the type traversal to handle any cyclical types.

While testing this PR, I discovered a similar issue in `utils.Dereference`, which leads to an infinite loop: #321.

- [x] Running against a large codebase such as [Kubernetes](https://github.com/kubernetes/kubernetes) does not error out. (See [DEVELOPING.md](https://github.com/google/go-flow-levee/blob/master/DEVELOPING.md) for instructions on how to do that.)
- [x] (N/A) Appropriate changes to README are included in PR


Patch:
diff --git a/internal/pkg/sourcetype/sourcetype.go b/internal/pkg/sourcetype/sourcetype.go
index 1cb9496..c80a280 100644
--- a/internal/pkg/sourcetype/sourcetype.go
+++ b/internal/pkg/sourcetype/sourcetype.go
@@ -30,28 +30,41 @@ import (
 // - A Struct Type that contains a tagged field
 // - A composite type that contains a Source Type
 func IsSourceType(c *config.Config, tf fieldtags.ResultType, t types.Type) bool {
-	deref := utils.Dereference(t)
-	switch tt := deref.(type) {
+	seen := map[types.Type]bool{}
+	return isSourceType(c, tf, t, seen)
+}
+
+// isSourceType is a helper method for IsSourceType.
+// The set of seen types is kept track of to prevent infinite recursion on
+// types such as `type A map[string]A`, which refer to themselves.
+func isSourceType(c *config.Config, tf fieldtags.ResultType, t types.Type, seen map[types.Type]bool) bool {
+	// If a type has been seen, then its status as a Source has already
+	// been evaluated. Return to avoid infinite recursion.
+	if seen[t] {
+		return false
+	}
+	seen[t] = true
+
+	switch tt := t.(type) {
 	case *types.Named:
-		return c.IsSourceType(utils.DecomposeType(tt)) || IsSourceType(c, tf, tt.Underlying())
+		return c.IsSourceType(utils.DecomposeType(tt)) || isSourceType(c, tf, tt.Underlying(), seen)
 	case *types.Array:
-		return IsSourceType(c, tf, tt.Elem())
+		return isSourceType(c, tf, tt.Elem(), seen)
 	case *types.Slice:
-		return IsSourceType(c, tf, tt.Elem())
+		return isSourceType(c, tf, tt.Elem(), seen)
 	case *types.Chan:
-		return IsSourceType(c, tf, tt.Elem())
+		return isSourceType(c, tf, tt.Elem(), seen)
 	case *types.Map:
-		key := IsSourceType(c, tf, tt.Key())
-		elem := IsSourceType(c, tf, tt.Elem())
+		key := isSourceType(c, tf, tt.Key(), seen)
+		elem := isSourceType(c, tf, tt.Elem(), seen)
 		return key || elem
+	case *types.Pointer:
+		return isSourceType(c, tf, tt.Elem(), seen)
 	case *types.Struct:
 		return hasTaggedField(tf, tt)
 	case *types.Basic, *types.Tuple, *types.Interface, *types.Signature:
 		// These types do not currently represent possible source types
 		return false
-	case *types.Pointer:
-		// This should be unreachable due to the dereference above
-		return false
 	default:
 		// The above should be exhaustive.  Reaching this default case is an error.
 		fmt.Printf("unexpected type received: %T %v; please report this issue\n", tt, tt)


Test patch:
diff --git a/internal/pkg/sourcetype/sourcetype_test.go b/internal/pkg/sourcetype/sourcetype_test.go
new file mode 100644
index 0000000..aecc190
--- /dev/null
+++ b/internal/pkg/sourcetype/sourcetype_test.go
@@ -0,0 +1,52 @@
+// Copyright 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package sourcetype
+
+import (
+	"testing"
+
+	"github.com/google/go-flow-levee/internal/pkg/config"
+	"github.com/google/go-flow-levee/internal/pkg/fieldtags"
+	"golang.org/x/tools/go/analysis"
+	"golang.org/x/tools/go/analysis/analysistest"
+	"golang.org/x/tools/go/analysis/passes/buildssa"
+)
+
+var Analyzer = &analysis.Analyzer{
+	Name:     "sourcetype_test",
+	Doc:      "This analyzer is used to test the sourcetype package.",
+	Run:      run,
+	Requires: []*analysis.Analyzer{buildssa.Analyzer},
+}
+
+func run(pass *analysis.Pass) (interface{}, error) {
+	ssaInput := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
+
+	c := &config.Config{}
+	tf := make(fieldtags.ResultType)
+
+	for _, fn := range ssaInput.SrcFuncs {
+		for _, p := range fn.Params {
+			_ = IsSourceType(c, tf, p.Type())
+		}
+	}
+
+	return nil, nil
+}
+
+func TestSourceTypeDoesNotStackOverflow(t *testing.T) {
+	testdata := analysistest.TestData()
+	analysistest.Run(t, testdata, Analyzer, "./...")
+}
diff --git a/internal/pkg/sourcetype/testdata/test_stackoverflow.go b/internal/pkg/sourcetype/testdata/test_stackoverflow.go
new file mode 100644
index 0000000..945652d
--- /dev/null
+++ b/internal/pkg/sourcetype/testdata/test_stackoverflow.go
@@ -0,0 +1,31 @@
+// Copyright 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package test
+
+type SelfReferential map[string]SelfReferential
+
+func selfReferential(s SelfReferential) {
+}
+
+type CoReferentialA CoReferentialB
+type CoReferentialB *CoReferentialA
+
+func coReferential(c CoReferentialA) {
+}
+
+type DeepSelfReferential [1][]chan DeepSelfReferential
+
+func deepSelfReferential(d DeepSelfReferential) {
+}