go/types/objectpath: break cycles through type parameters in find
When searching for objects, we naively traversed through type parameter
constraints. This leads to infinite recursion when there are cycles
through type parameter constraints.
Break these cycles by tracking type parameter names that have previously
been encountered. This ensures we walk type parameter constraints at
most once. Note that if the desired object was not found on the first
search of the constraint, there is no need to search again.
Note: this cherry-pick also adjusts a test error message to match
go1.18.
Updates golang/go#51727
Change-Id: Ifcdf4b138a0e95441e485bbb9ee21c01b04eaed4
Reviewed-on: https://go-review.googlesource.com/c/tools/+/393376
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
(cherry picked from commit d67eab4bcee20484daf13001afb781a117bc49ec)
Reviewed-on: https://go-review.googlesource.com/c/tools/+/393635
Reviewed-by: Dmitri Shuralyov <dmitshur@golang.org>
diff --git a/go/types/objectpath/objectpath.go b/go/types/objectpath/objectpath.go
index 7e96fc2..557202b 100644
--- a/go/types/objectpath/objectpath.go
+++ b/go/types/objectpath/objectpath.go
@@ -254,18 +254,18 @@
if tname.IsAlias() {
// type alias
- if r := find(obj, T, path); r != nil {
+ if r := find(obj, T, path, nil); r != nil {
return Path(r), nil
}
} else {
if named, _ := T.(*types.Named); named != nil {
- if r := findTypeParam(obj, typeparams.ForNamed(named), path); r != nil {
+ if r := findTypeParam(obj, typeparams.ForNamed(named), path, nil); r != nil {
// generic named type
return Path(r), nil
}
}
// defined (named) type
- if r := find(obj, T.Underlying(), append(path, opUnderlying)); r != nil {
+ if r := find(obj, T.Underlying(), append(path, opUnderlying), nil); r != nil {
return Path(r), nil
}
}
@@ -279,7 +279,7 @@
if _, ok := o.(*types.TypeName); !ok {
if o.Exported() {
// exported non-type (const, var, func)
- if r := find(obj, o.Type(), append(path, opType)); r != nil {
+ if r := find(obj, o.Type(), append(path, opType), nil); r != nil {
return Path(r), nil
}
}
@@ -299,7 +299,7 @@
if m == obj {
return Path(path2), nil // found declared method
}
- if r := find(obj, m.Type(), append(path2, opType)); r != nil {
+ if r := find(obj, m.Type(), append(path2, opType), nil); r != nil {
return Path(r), nil
}
}
@@ -316,41 +316,44 @@
}
// find finds obj within type T, returning the path to it, or nil if not found.
-func find(obj types.Object, T types.Type, path []byte) []byte {
+//
+// The seen map is used to short circuit cycles through type parameters. If
+// nil, it will be allocated as necessary.
+func find(obj types.Object, T types.Type, path []byte, seen map[*types.TypeName]bool) []byte {
switch T := T.(type) {
case *types.Basic, *types.Named:
// Named types belonging to pkg were handled already,
// so T must belong to another package. No path.
return nil
case *types.Pointer:
- return find(obj, T.Elem(), append(path, opElem))
+ return find(obj, T.Elem(), append(path, opElem), seen)
case *types.Slice:
- return find(obj, T.Elem(), append(path, opElem))
+ return find(obj, T.Elem(), append(path, opElem), seen)
case *types.Array:
- return find(obj, T.Elem(), append(path, opElem))
+ return find(obj, T.Elem(), append(path, opElem), seen)
case *types.Chan:
- return find(obj, T.Elem(), append(path, opElem))
+ return find(obj, T.Elem(), append(path, opElem), seen)
case *types.Map:
- if r := find(obj, T.Key(), append(path, opKey)); r != nil {
+ if r := find(obj, T.Key(), append(path, opKey), seen); r != nil {
return r
}
- return find(obj, T.Elem(), append(path, opElem))
+ return find(obj, T.Elem(), append(path, opElem), seen)
case *types.Signature:
- if r := findTypeParam(obj, typeparams.ForSignature(T), path); r != nil {
+ if r := findTypeParam(obj, typeparams.ForSignature(T), path, seen); r != nil {
return r
}
- if r := find(obj, T.Params(), append(path, opParams)); r != nil {
+ if r := find(obj, T.Params(), append(path, opParams), seen); r != nil {
return r
}
- return find(obj, T.Results(), append(path, opResults))
+ return find(obj, T.Results(), append(path, opResults), seen)
case *types.Struct:
for i := 0; i < T.NumFields(); i++ {
- f := T.Field(i)
+ fld := T.Field(i)
path2 := appendOpArg(path, opField, i)
- if f == obj {
+ if fld == obj {
return path2 // found field var
}
- if r := find(obj, f.Type(), append(path2, opType)); r != nil {
+ if r := find(obj, fld.Type(), append(path2, opType), seen); r != nil {
return r
}
}
@@ -362,7 +365,7 @@
if v == obj {
return path2 // found param/result var
}
- if r := find(obj, v.Type(), append(path2, opType)); r != nil {
+ if r := find(obj, v.Type(), append(path2, opType), seen); r != nil {
return r
}
}
@@ -374,7 +377,7 @@
if m == obj {
return path2 // found interface method
}
- if r := find(obj, m.Type(), append(path2, opType)); r != nil {
+ if r := find(obj, m.Type(), append(path2, opType), seen); r != nil {
return r
}
}
@@ -384,7 +387,14 @@
if name == obj {
return append(path, opObj)
}
- if r := find(obj, T.Constraint(), append(path, opConstraint)); r != nil {
+ if seen[name] {
+ return nil
+ }
+ if seen == nil {
+ seen = make(map[*types.TypeName]bool)
+ }
+ seen[name] = true
+ if r := find(obj, T.Constraint(), append(path, opConstraint), seen); r != nil {
return r
}
return nil
@@ -392,11 +402,11 @@
panic(T)
}
-func findTypeParam(obj types.Object, list *typeparams.TypeParamList, path []byte) []byte {
+func findTypeParam(obj types.Object, list *typeparams.TypeParamList, path []byte, seen map[*types.TypeName]bool) []byte {
for i := 0; i < list.Len(); i++ {
tparam := list.At(i)
path2 := appendOpArg(path, opTypeParam, i)
- if r := find(obj, tparam, path2); r != nil {
+ if r := find(obj, tparam, path2, seen); r != nil {
return r
}
}
diff --git a/go/types/objectpath/objectpath_go118_test.go b/go/types/objectpath/objectpath_go118_test.go
index 829dd13..d9735df 100644
--- a/go/types/objectpath/objectpath_go118_test.go
+++ b/go/types/objectpath/objectpath_go118_test.go
@@ -34,7 +34,7 @@
type A = T[int, N]
-func F[FP0, FP1 any](FP0, FP1) {}
+func F[FP0 any, FP1 interface{ M() }](FP0, FP1) {}
`},
}
paths := []pathTest{
@@ -46,6 +46,8 @@
// {"b", "T.T0O", "type TP0 b.TP0", ""},
// {"b", "T.T1O", "type TP1 b.TP1", ""},
{"b", "T.T1CM0", "func (interface).M0()", ""},
+ {"b", "F.T0O", "type parameter FP0 any", ""},
+ {"b", "F.T1CM0", "func (interface).M()", ""},
// Obj of an instance is the generic declaration.
// {"b", "A.O", "type b.T[b.TP0 interface{}, b.TP1 interface{M0(); M1()}] struct{}", ""},
{"b", "A.M0", "func (b.T[int, b.N]).M()", ""},
@@ -79,7 +81,7 @@
wantErr string
}{
{types.Universe.Lookup("any"), "predeclared type any = interface{} has no path"},
- {types.Universe.Lookup("comparable"), "predeclared type comparable interface{} has no path"},
+ {types.Universe.Lookup("comparable"), "predeclared type comparable interface{comparable} has no path"},
} {
path, err := objectpath.For(test.obj)
if err == nil {
@@ -92,3 +94,44 @@
}
}
}
+
+func TestGenericPaths_Issue51717(t *testing.T) {
+ pkgs := map[string]map[string]string{
+ "p": {"p.go": `
+package p
+
+type S struct{}
+
+func (_ S) M() {
+ // The go vet stackoverflow crash disappears when the following line is removed
+ panic("")
+}
+
+func F[WL interface{ N(item W) WL }, W any]() {
+}
+
+func main() {}
+`},
+ }
+ paths := []pathTest{
+ {"p", "F.T0CM0.RA0", "var WL", ""},
+ {"p", "F.T0CM0.RA0.CM0", "func (interface).N(item W) WL", ""},
+
+ // Finding S.M0 reproduced the infinite recursion reported in #51717,
+ // because F is searched before S.
+ {"p", "S.M0", "func (p.S).M()", ""},
+ }
+
+ conf := loader.Config{Build: buildutil.FakeContext(pkgs)}
+ conf.Import("p")
+ prog, err := conf.Load()
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ for _, test := range paths {
+ if err := testPath(prog, test); err != nil {
+ t.Error(err)
+ }
+ }
+}
