Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
adonovan opened this issue Oct 5, 2022 · 6 comments
Closed

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

adonovan opened this issue Oct 5, 2022 · 6 comments
Assignees
@adonovan
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
Go1.20

Comments

@adonovan
Copy link
Member

adonovan commented Oct 5, 2022 

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
@griesemer griesemer self-assigned this Oct 5, 2022
@griesemer griesemer added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 5, 2022
@griesemer griesemer added this to the Go1.20 milestone Oct 5, 2022
@findleyr
Copy link
Contributor

findleyr commented Oct 5, 2022

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

@findleyr findleyr changed the title go/types: Interface.NumMethods crashes on cyclic interface type x/tools/go/types/typeutil: infinite recursion with cyclic interface type Oct 5, 2022
@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Oct 5, 2022
@adonovan
Copy link
Member Author

adonovan commented Oct 5, 2022

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

@griesemer griesemer assigned adonovan and unassigned griesemer Oct 5, 2022
@adonovan
Copy link
Member Author

adonovan commented Oct 5, 2022 •
edited

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
Copy link
Member

dominikh commented Oct 5, 2022

Is this related to #26863?

@gopherbot
Copy link

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

@adonovan
Copy link
Member Author

adonovan commented Oct 5, 2022

Thanks @dominikh, seems like a dup.

gopherbot pushed a commit to golang/tools that referenced this issue Oct 28, 2022
@adonovan
go/types/typeutil: break recursion through anonymous interfaces
e172e97 
In a type such as
    type X interface { m() []*interface { X } }
the traversal never encounters the named type X in the result of m
since Interface.Methods expands it to a set of methods, one that
includes m, causing the traversal to get stuck.

This change uses an alternative, shallow hash function on the types
of interface methods to avoid the possibility of getting stuck in
such a cycle.

(An earlier draft used a stack of interface types to detect cycles,
but the logic of caching made this approach quite tricky.)

Fixes golang/go#56048
Fixes golang/go#26863

Change-Id: I28a604e6affae5dfdd05a62e405d49a3efc8d709
Reviewed-on: https://go-review.googlesource.com/c/tools/+/439117
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Tim King <taking@google.com>
Run-TryBot: Alan Donovan <adonovan@google.com>
@golang golang locked and limited conversation to collaborators Oct 28, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@adonovan adonovan

Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
Go1.20
Development

No branches or pull requests
5 participants
@dominikh @adonovan @griesemer @gopherbot @findleyr