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/gopls: guarantee that metadata is acyclic #59675

Closed
findleyr opened this issue Apr 17, 2023 · 2 comments
Closed

x/tools/gopls: guarantee that metadata is acyclic #59675

findleyr opened this issue Apr 17, 2023 · 2 comments
Assignees
@adonovan
Labels
FrozenDueToAge gopls Issues related to the Go language server, gopls. release-blocker Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
gopls/v0.12.0

Comments

@findleyr
Copy link
Contributor

Tracking issue: so much of the new type-checking logic in the incremental gopls design relies on metadata being acyclic; and yet I believe the check for cycles may be incomplete when the package graph is built incrementally across multiple calls to go/packages.Load. We must break cycles explicitly in metadataGraph.build.

Enforcing this invariant explicitly should block the release.

CC @adonovan
@findleyr findleyr added this to the gopls/v0.12.0 milestone Apr 17, 2023
@gopherbot gopherbot added Tools This label describes issues relating to any tools in the x/tools repository. gopls Issues related to the Go language server, gopls. labels Apr 17, 2023
@gopherbot
Copy link

Change https://go.dev/cl/486636 mentions this issue: gopls/internal/lsp/cache: break metadata cycles

@findleyr

This comment was marked as outdated.

Sign in to view
@findleyr findleyr reopened this Apr 20, 2023
gopherbot pushed a commit to golang/tools that referenced this issue Apr 21, 2023
@adonovan
gopls/internal/lsp/cache: break metadata cycles
4e3238a 
This change adds a defensive check for cycles in the
metadata graph formed during the Clone (update) operation,
as many algorithms in gopls assume acyclicity and
will otherwise crash or deadlock.

We use Tarjan's algorithm (for the second time within
a fortnight!) to find the cycles, and break them by
removing all edges within an SCC whose tail is an
updated Metadata node. We cannot modify the other
Metadata nodes as they are shared.

Self-import edges are deleted at Metadata construction.

Also, an internal test.

Fixes golang/go#59675

Change-Id: Ifd25345761e8b058bcbc07ed07d4d10cdd5dbd8b
Reviewed-on: https://go-review.googlesource.com/c/tools/+/486636
Run-TryBot: Alan Donovan <adonovan@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Alan Donovan <adonovan@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@golang golang locked and limited conversation to collaborators Apr 20, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@adonovan adonovan

Labels
FrozenDueToAge gopls Issues related to the Go language server, gopls. release-blocker Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
gopls/v0.12.0
Development

No branches or pull requests
3 participants
@adonovan @gopherbot @findleyr