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.

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

go/types: NewMethodSet doesn't terminate for recursively embedded generics #52715

Closed
dominikh opened this issue May 4, 2022 · 7 comments
Closed
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Milestone

Comments

@dominikh
Copy link
Member

dominikh commented May 4, 2022

What version of Go are you using (go version)?

$ go version
go version devel go1.19-fbb47e81c1 Wed May 4 20:20:28 2022 +0000 linux/amd64

What did you do?

https://go.dev/play/p/cFb8uD0dfU1

What did you expect to see?

For types.NewMethodSet to terminate.

What did you see instead?

It doesn't terminate.

/cc @griesemer @findleyr

@findleyr
Copy link
Contributor

findleyr commented May 4, 2022

Thank you for reporting. This is unfortunate. Lazy expansion of the embedded types allows the search to expand infinitely, as it uses pointer identity.

This should be straightforward to fix.

@gopherbot
Copy link

Change https://go.dev/cl/404099 mentions this issue: go/types: use Contexts to dedupe embedded instances in method lookup

@dr2chase dr2chase added the NeedsFix The path to resolution is known, but the work has not been done. label May 5, 2022
@gopherbot
Copy link

Change https://go.dev/cl/404335 mentions this issue: internal/lsp/source/completion: use typeutil.Map for short-circuiting

@findleyr
Copy link
Contributor

findleyr commented May 5, 2022

Related: #51580

gopherbot pushed a commit to golang/tools that referenced this issue May 6, 2022
While working on golang/go#52715, I discovered an infinite recursion in
gopls' completion logic: eachField assumes a finiteness of type pointers.

It is almost certainly a go/types bug that type-checked types expand
infinitely, but nevertheless we should use the more accurate
typeutil.Map for short-circuiting our search.

Change-Id: Ib1c7125e624f42882869acd4e0476e317d4da056
Reviewed-on: https://go-review.googlesource.com/c/tools/+/404335
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
@findleyr
Copy link
Contributor

findleyr commented May 9, 2022

@gopherbot please backport to 1.18. This is an infinite recursion via valid usage of the go/types API.

@gopherbot
Copy link

Backport issue(s) opened: #52804 (for 1.18).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

@gopherbot
Copy link

Change https://go.dev/cl/405117 mentions this issue: [release-branch.go1.18] go/types, types2: use a type lookup by identity in method lookup

gopherbot pushed a commit that referenced this issue May 10, 2022
…ty in method lookup

Named type identity is no longer canonical. For correctness, named types
need to be compared with types.Identical. Our method set algorithm was
not doing this: it was using a map to de-duplicate named types, relying
on their pointer identity. As a result it was possible to get incorrect
results or even infinite recursion, as encountered in #52715.

To fix this, look up types by identity in NewMethodSet and
LookupFieldOrMethod. This does a linear search among types with equal
origin. Alternatively we could use a *Context to do a hash lookup, but
in practice we will be considering a small number of types, and so
performance is not a concern and a linear lookup is simpler. This also
means we don't have to rely on our type hash being perfect, which we
don't depend on elsewhere.

Also add more tests for NewMethodSet and LookupFieldOrMethod involving
generics.

Fixes #52804

Change-Id: I04dfeff54347bc3544d95a30224c640ef448e9b7
Reviewed-on: https://go-review.googlesource.com/c/go/+/404099
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
(cherry picked from commit f088f49)
Reviewed-on: https://go-review.googlesource.com/c/go/+/405117
Reviewed-by: Alan Donovan <adonovan@google.com>
@golang golang locked and limited conversation to collaborators Jun 22, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Projects
None yet
Development

No branches or pull requests

4 participants