x/tools/go/types/typeutil: stack overflow when hashing recursive embedded type interface

[dominikh]

What did you do?

Run ssadump on https://play.golang.org/p/TjieYyL9ily

What did you expect to see?

No crash

What did you see instead?

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x70d2b9, 0xe)
	/home/dominikh/go/src/runtime/panic.go:608 +0x72
runtime.newstack()
	/home/dominikh/go/src/runtime/stack.go:1008 +0x729
runtime.morestack()
	/home/dominikh/go/src/runtime/asm_amd64.s:429 +0x8f

goroutine 1 [running]:
runtime.mapaccess2(0x6b5a00, 0xc000087b00, 0xc020140360, 0x0, 0x0)
	/home/dominikh/go/src/runtime/map.go:439 +0x22a fp=0xc020140320 sp=0xc020140318 pc=0x40da5a
golang.org/x/tools/go/types/typeutil.Hasher.Hash(0xc000087b00, 0x75d5a0, 0xc0000878f0, 0x756ea170f9470b)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:224 +0x59 fp=0xc020140380 sp=0xc020140320 pc=0x601329
golang.org/x/tools/go/types/typeutil.Hasher.hashFor(0xc000087b00, 0x75d4a0, 0xc0000cbae0, 0x95f2e0)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:285 +0x267 fp=0xc020140430 sp=0xc020140380 pc=0x601667
golang.org/x/tools/go/types/typeutil.Hasher.Hash(0xc000087b00, 0x75d4a0, 0xc0000cbae0, 0x0)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:226 +0x9a fp=0xc020140490 sp=0xc020140430 pc=0x60136a
golang.org/x/tools/go/types/typeutil.Hasher.hashTuple(0xc000087b00, 0xc00009c840, 0xc0000023b1)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:310 +0x70 fp=0xc0201404d8 sp=0xc020140490 pc=0x601cd0
golang.org/x/tools/go/types/typeutil.Hasher.hashFor(0xc000087b00, 0x75d5a0, 0xc0000878f0, 0x95f2e0)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:276 +0x33e fp=0xc020140588 sp=0xc0201404d8 pc=0x60173e
golang.org/x/tools/go/types/typeutil.Hasher.Hash(0xc000087b00, 0x75d5a0, 0xc0000878f0, 0x756ea170f9470b)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:226 +0x9a fp=0xc0201405e8 sp=0xc020140588 pc=0x60136a
golang.org/x/tools/go/types/typeutil.Hasher.hashFor(0xc000087b00, 0x75d4a0, 0xc0000cbae0, 0x95f2e0)
	/home/dominikh/prj/src/golang.org/x/tools/go/types/typeutil/map.go:285 +0x267 fp=0xc020140698 sp=0xc0201405e8 pc=0x601667
[...]
...additional frames elided...

/cc @alandonovan @griesemer

[adonovan]

I was going to ask if you (gri) could look into this, since it relates to what you've been thinking about a lot recently: cycles in types. What's the correct way to hash a cyclic type? Alternatively, what data structure should typeutil.Map use so that the issue doesn't arise? I can make the code change.

[griesemer]

@alandonovan In Go, type cycles can only be constructed via type names (which may be aliases). I think that implies that those type names have to flow into the construction of the hash (even if they are aliases), and that we can't "simplify" interfaces containing named embedded interfaces by expanding the methods out. Or put differently, the text of a type's original (source code) declaration is a form of not very dense hash (except of course for names that need to be canonicalized, and formatting ignored, etc.).

[gopherbot]

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