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

Jump to bottom

go/parser: isolate object resolution from parsing #45104

Closed
3 of 4 tasks
findleyr opened this issue Mar 18, 2021 · 11 comments
Closed
3 of 4 tasks

go/parser: isolate object resolution from parsing #45104

findleyr opened this issue Mar 18, 2021 · 11 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Backlog

Comments

@findleyr
Copy link
Contributor

findleyr commented Mar 18, 2021 •
edited

This issue relates to an implementation detail of go/parser, but one that is fundamental enough to track independently.

Currently go/parser does a bit more than just parse and produce an AST: while parsing it creates *ast.Scopes and uses them to map identifiers to declarations (object resolution), storing the result of this resolution in ast.Ident.Obj, and reporting some declaration errors if, for example, there's no new identifier on the left side of ':='. There's a fair bit of overlap with go/types, which has its own more robust concept of scopes.

Furthermore:

  • identifier resolution is not really complete, missing e.g. struct fields or imported identifiers
  • based on some quick benchmarking, it takes somewhere from 20-40% of parsing time
  • being intermixed with parsing, it complicates the code, and makes it harder to align go/parser with cmd/compile/internal/syntax
  • since ident.Obj is used in some places, any alternative parser to go/parser must also implement the logic of object resolution (for example, @mvdan experimented with using the syntax parser and mapping to go/ast, and was blocked on this)
  • the test coverage for object resolution is limited

I'm working on improving go/parser error recovery (and to a lesser extent, performance), and it's proving to be easier if identifier resolution is moved out of the parsing pass into a separate post-processing pass (thanks @griesemer for the suggestion).

At this point I have a working version of go/parser that achieves this, albeit hacked-up so that I can run in both paradigms and compare the result. Here's the plan forward:

  • add additional tests for object resolution
  • finish extracting object resolution and label tracking from the parsing pass
  • add a new parser mode that allows skipping object resolution entirely if the caller knows it will not be needed (something like SkipResolution).
  • (maybe) expose object resolution as an independent API (something like func Resolve(*ast.Node, *ast.Scope), so that alternate parsers can use the same logic to enrich the AST with objects.

It's worth noting that gopls can't quite disable object resolution, as there are a few analyzers that use it.
@mvdan
Copy link
Member

mvdan commented Mar 18, 2021

I'd love this. I assume the vast majority of the Parse API users could skip object resolution. It would certainly help with syntax-only tools like gofmt and gofumpt.

I assume we can't change the default behavior because of the backwards compatibility guarantee.

Have you thought about go/packages? Since it supports go/types, I imagine practically noone should be relying on go/parser's object resolution.

@findleyr
Copy link
Contributor Author

Have you thought about go/packages? Since it supports go/types, I imagine practically noone should be relying on go/parser's object resolution.

Not really. There's a pretty big gap between practically noone and noone. Given that parsing is generally a fraction of type checking (5-15% perhaps), I'm not sure it's worth skipping object resolution if it adds complexity to the API. However, for tools such as gofumpt (which needs only syntax) or maybe gopls, which manages parsing independently of go/packages, there is an opportunity for performance gains. We certainly can't change the default behavior for either the parser or go/packages.

Were the only benefit performance I'm not sure this would be worth doing. Also, in my prototype there appears to be a small but statistically significant cost of resolving in a post processing pass, simply due to the extra traversal -- maybe 2-5%. I'm sure I can make that cost up elsewhere if necessary :)

@mvdan
Copy link
Member

mvdan commented Mar 18, 2021

Given that parsing is generally a fraction of type checking (5-15% perhaps), I'm not sure it's worth skipping object resolution if it adds complexity to the API

That's true, but it's also true that a good portion of go/packages users load syntax without loading type information. Whether or not it's worth adding API complexity is a fair point.

I'm sure I can make that cost up elsewhere if necessary :)

I'd even go as far as saying that a <10% slow-down is okay. Anywhere where the added cost will really matter can likely just enable the flag to skip object resolution and get a speed-up instead.

@cherrymui cherrymui added the NeedsFix The path to resolution is known, but the work has not been done. label Mar 18, 2021
@cherrymui cherrymui added this to the Backlog milestone Mar 18, 2021
@findleyr findleyr self-assigned this Mar 18, 2021
This was referenced Mar 19, 2021
Closed
Open
@findleyr
Copy link
Contributor Author

Ok, now I've got everything matching the current behavior identically (after normalizing for bugs in the current implementation).
Quick update on timing (benchmarking with go/types/expr.go):

  • Disabling object resolution reduces parse time by 18.5%. The other half of the 40% number I was seeing earlier was, unfortunately, just a regression in 1.17 that was fixed by https://golang.org/cl/302629.
  • With no optimizations, resolving in a second pass through the AST increases parse time by 4%.
  • I have an optimization for object resolution that neutralizes this 4% slowdown, but it's somewhat complicated (it transposes the spaghetti stack to replace multiple map lookups with a single map lookup and slice scan). I don't think anyone will actually notice the 4% slowdown, so this probably isn't worth it.

CLs incoming, once I can reassemble these changes into a sensible chain.

@mvdan
Copy link
Member

mvdan commented Mar 22, 2021

Happy to help review these, though I assume you want gri's approval on them anyway.

@findleyr findleyr mentioned this issue Mar 24, 2021
Closed
@gopherbot
Copy link

Change https://golang.org/cl/304455 mentions this issue: go/parser: switch to resolving objects as a post-processing pass

@gopherbot
Copy link

Change https://golang.org/cl/304453 mentions this issue: go/parser: add resolution tests for type params

@gopherbot
Copy link

Change https://golang.org/cl/304450 mentions this issue: go/parser: add data-driven tests for object resolution

@findleyr
Copy link
Contributor Author

Happy to help review these, though I assume you want gri's approval on them anyway.

Feel free to review if you want, but yes I will require gri's approval :)

gopherbot pushed a commit that referenced this issue Mar 30, 2021
@findleyr
go/parser: add data-driven tests for object resolution
0fdd371 
Add new tests for object resolution driven by source files with
declarations and uses marked via special comments. This made it easier
to add test coverage while refactoring object resolution for #45104.

Tests are added to a new resolver_test.go file. In a subsequent CL the
resolver.go file will be added, making this choice of file name more
sensible.

For #45104
For #45136
For #45160

Change-Id: I240fccc0de95aa8f2d03e39c77146d4c61f1ef9e
Reviewed-on: https://go-review.googlesource.com/c/go/+/304450
Trust: Robert Findley <rfindley@google.com>
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Mar 31, 2021
@findleyr
go/parser: add resolution tests for type params
152ca79 
For #45104
For #45221

Change-Id: I8966555f4e8844d5b6766d00d48f7a81868ccf40
Reviewed-on: https://go-review.googlesource.com/c/go/+/304453
Trust: Robert Findley <rfindley@google.com>
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
gopherbot pushed a commit that referenced this issue Mar 31, 2021
@findleyr
go/parser: switch to resolving objects as a post-processing pass
4acefa0 
Coupling object resolution to parsing complicates the parsing code, and
is a barrier to improvement. It requires passing around context such as
'lhs' or 'keyOk', and even then sometimes requires guess-work, such as
whether to resolve the key in a composite literal.

In this CL we delay object resolution to a separate pass after the file
parse completes. This makes it easier to see logic of scoping, and
removes state from the parsing code. This can enable subsequent
improvements such as optionally skipping object resolution, aligning the
parser with cmd/compile/internal/syntax, and allowing alternative
parsers to reuse object resolution.

The additional AST traversal appears to slow down parsing by around 4%.
That seems small enough not to worry about, especially since performance
sensitive users may eventually be able to disable object resolution
entirely, saving around 18% off the previous baseline. I'll also mail a
speculative CL showing how we can significantly mitigate the cost of
object resolution by transposing scopes.

For #45104

Change-Id: I98d9143fd77ae29e84ec7c3ae2fdb1139510da37
Reviewed-on: https://go-review.googlesource.com/c/go/+/304455
Trust: Robert Findley <rfindley@google.com>
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
@gopherbot
Copy link

Change https://golang.org/cl/306149 mentions this issue: go/parser: add a SkipResolution method to bypass object resolution

@ianlancetaylor ianlancetaylor mentioned this issue May 28, 2021
Closed
@findleyr findleyr mentioned this issue Jun 1, 2021
Closed
@findleyr
Copy link
Contributor Author

findleyr commented Jun 1, 2021

We had a bit of discussion on #46298, and the addition of SkipObjectResolution does warrant a proper proposal, which I've filed as #46485. Sorry, initially we thought this wasn't necessary for such a minor change.

I also think it could be beneficial to more formally consider the change. As I wrote in that proposal, I think it's a small benefit for smaller cost, but I'd like to hear from others. If the discussion is one-sided in favor of the new mode, we can perhaps still add it for 1.17, but I don't want to rush it.

@rsc rsc mentioned this issue Jun 10, 2021
Closed
83 tasks
@findleyr findleyr mentioned this issue Sep 2, 2021
Closed
@golang golang locked and limited conversation to collaborators Jun 1, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
4 participants
@mvdan @gopherbot @cherrymui @findleyr