x/tools/go/types/typeutil: infinite recursion with cyclic interface type

[adonovan]

xtools$ cat a.go
package main

type I interface{ m() interface { I } }

var _ = I.m

xtools$ go run ./cmd/ssadump/ a.go 2>&1 | head -n 32
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0x140203604d0 stack=[0x14020360000, 0x14040360000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x1051ef038?, 0x1054204a0?})
	/usr/local/go/src/runtime/panic.go:1047 +0x40 fp=0x16ae4f400 sp=0x16ae4f3d0 pc=0x104fe3300
runtime.newstack()
	/usr/local/go/src/runtime/stack.go:1103 +0x464 fp=0x16ae4f5b0 sp=0x16ae4f400 pc=0x104ffd484
runtime.morestack()
	/usr/local/go/src/runtime/asm_arm64.s:316 +0x70 fp=0x16ae4f5b0 sp=0x16ae4f5b0 pc=0x105010a30

goroutine 1 [running]:
go/types.computeInterfaceTypeSet(0x0, 0x0?, 0x14000184370)
	/usr/local/go/src/go/types/typeset.go:153 +0xa40 fp=0x140202e04d0 sp=0x140202e04d0 pc=0x102613cb0
go/types.(*Interface).typeSet(...)
	/usr/local/go/src/go/types/interface.go:28
go/types.(*Interface).NumMethods(...)
	/usr/local/go/src/go/types/interface.go:112
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0x140001834d0?, 0x14000183500?, 0x0?}, {0x1027a8c98?, 0x14000184370?})
	go/types/typeutil/map.go:331 +0xe4 fp=0x140202e06a0 sp=0x140202e04d0 pc=0x10267c1c4
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0x140001834d0?, 0x14000183500?, 0x0?}, {0x1027a8c98, 0x14000184370})
	go/types/typeutil/map.go:239 +0x78 fp=0x140202e0710 sp=0x140202e06a0 pc=0x10267c068
golang.org/x/tools/go/types/typeutil.Hasher.hashTuple({0x140001834d0?, 0x14000183500?, 0x0?}, 0x1400019d110)
	go/types/typeutil/map.go:377 +0x78 fp=0x140202e0780 sp=0x140202e0710 pc=0x10267ca48
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0x140001834d0?, 0x14000183500?, 0x0?}, {0x1027a8d38?, 0x14000181640?})
	go/types/typeutil/map.go:319 +0x5a8 fp=0x140202e0950 sp=0x140202e0780 pc=0x10267c688
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0x140001834d0?, 0x14000183500?, 0x0?}, {0x1027a8d38, 0x14000181640})
	go/types/typeutil/map.go:239 +0x78 fp=0x140202e09c0 sp=0x140202e0950 pc=0x10267c068
golang.org/x/tools/go/types/typeutil.Hasher.hashFor({0x140001834d0?, 0x14000183500?, 0x0?}, {0x1027a8c98?, 0x14000184370?})
	go/types/typeutil/map.go:335 +0x680 fp=0x140202e0b90 sp=0x140202e09c0 pc=0x10267c760
golang.org/x/tools/go/types/typeutil.Hasher.Hash({0x140001834d0?, 0x14000183500?, 0x0?}, {0x1027a8c98, 0x14000184370})

@gri @findleyr @mdempsky @timothy-king

[findleyr]

This crash isn't in NumMethods. It's an infinite recursion in typeutil.Hasher.Hash.

[adonovan]

You're right, NumMethods just happens to be the frame the broke the camel's stack, as it were.

[adonovan]

The root cause is that it is not sufficient to break cycles at Named types, because Interface.Methods "looks through" the named type of an embedded interface, thus typeutil's hasher will never encounter the named type X during its traversal of a type such as interface { m() interface { X } } and thus will never prune the recursion: the type checker will already have expanded X into a set of methods that includes m.

I notice a nice comment to this effect in types.Identical:

				// Interface types are the only types where cycles can occur
				// that are not "terminated" via named types; and such cycles
				// can only be created via method parameter types that are
				// anonymous interfaces (directly or indirectly) embedding
				// the current interface. Example:
				//
				//    type T interface {
				//        m() interface{T}
				//    }
				//
				// If two such (differently named) interfaces are compared,
				// endless recursion occurs if the cycle is not detected.

So we may need to prune the recursion at method names too. We should also document the subtleties of the correct approach to bounded recursion over types in go/types.

typeutil test case:

diff --git a/go/types/typeutil/map_test.go b/go/types/typeutil/map_test.go
index 8cd643e5b..8437ec8c4 100644
--- a/go/types/typeutil/map_test.go
+++ b/go/types/typeutil/map_test.go
@@ -244,6 +244,11 @@ func Bar[P Constraint[P]]() {}
 func Baz[Q any]() {} // The underlying type of Constraint[P] is any.
 // But Quux is not.
 func Quux[Q interface{ quux() }]() {}
+
+
+type Issue56048_I interface{ m() interface { Issue56048_I } }
+var Issue56048 = Issue56048_I.m
+
 `
 
        fset := token.NewFileSet()
@@ -302,6 +307,7 @@ func Quux[Q interface{ quux() }]() {}
                Bar        = scope.Lookup("Foo").Type()
                Baz        = scope.Lookup("Foo").Type()
                Quux       = scope.Lookup("Quux").Type()
+               Issue56048 = scope.Lookup("Issue56048").Type()
        )
 
        tmap := new(typeutil.Map)
@@ -371,6 +377,8 @@ func Quux[Q interface{ quux() }]() {}
                {Bar, "Bar", false},
                {Baz, "Baz", false},
                {Quux, "Quux", true},
+
+               {Issue56048, "Issue56048", true},
        }
 
        for _, step := range steps {

[dominikh]

Is this related to #26863?

[gopherbot]

Change https://go.dev/cl/439117 mentions this issue: go/types/typeutil: break recursion through anonymous interfaces

[adonovan]

Thanks @dominikh, seems like a dup.