go/analysis/analysistest: RunWithSuggestedFixes cannot handle overlapping fixes (such as ones that add imports); need diff3

[lfolger]

Go version

gc-tip (should reproduce with all versions)

Output of go env in your module/workspace:

N/A

What did you do?

Running the inline analyzer on a package where it would inline multiple functions leads to duplicate suggested fixes that some tools cannot deal with (including the analysistest package). As far as I can tell it tries to remove the import twice. In general it seems to be an issue that it always tries to remove the import even if it is still needed (see example below).

Here is a self contained reproducer test:

func TestRemovingImport(t *testing.T) {
	files := map[string]string{
		"some/package/pkg/foo.go": `package pkg

			// inlineme
			func ToInline () {}

			func Bar () {}
		`,
		"b/c/foo.go": `package c

			import (
				"some/package/pkg"
			)

			func foo() {
				pkg.ToInline() // want "inline call of pkg.ToInline"
			}

			func bar() {
				pkg.ToInline() // want "inline call of pkg.ToInline"
				pkg.Bar() // ok
			}
		`,
		"b/c/foo.go.golden": `package c
			func foo() {
			}

			func bar() {
			}`,
	}
	dir, cleanup, err := analysistest.WriteFiles(files)
	if err != nil {
		t.Fatal(err)
	}
	analysistest.RunWithSuggestedFixes(t, dir, analyzer.Analyzer, "b/c")
	cleanup()
}

What did you see happen?

The example fails with:

...analysistest.go:263: /tmp/analysistest3675113240/src/b/c/foo.go: error applying fixes: diff has overlapping edits (see possible explanations at RunWithSuggestedFixes)

What did you expect to see?

I expected the analyzer to not remove the import when it is still needed and if it is no longer needed to only remove the import once.

[lfolger]

cc: @adonovan

[adonovan]

I plan to improve the API for the inliner so that it includes (for example) options to control literalization, consideration of side effects, and suchlike. I think it might also be useful (and I seem to recall writing a TODO comment to this effect) to return not just one but diff, but a more structured result that separates the diff around the call site from the logical changes to the import declaration. This would also allow Bazel/Blaze to interpose their visibiliity checking.

[adonovan]

We may also need to make the -fix conflict checker more tolerant to redundant but identical diff chunks.

[gopherbot]

Change https://go.dev/cl/581802 mentions this issue: internal/refactor/inline: extensible API

[lfolger]

So what you are saying is that it is not the Analyzer to deduplicate these findings but it is the user of that analyzer to determine this?

I think it is a general problem that you want fixes to be independent of each other so that you can apply them independently?

I don't think this works because following that, you can never generate an import removal unless it is the only usage of that import in the file. Because as soon as there are two or more usages, removing any of them (independently) would require keeping the import because of the other usage.

In other words, the inliner should only ever remove the import if it is removing the only usage of that import. If it is removing something and there is another usage, it should not generate an import removal (even if there are other suggested fixes removing all other usages).

Side note: especially in case where there are usages that are not removed by the inliner, it should not generate a suggested fix to remove the import as it does right now.

[adonovan]

You raise a number of good questions. You're right that in general two fixes may be safe individually but not together, for example because they each remove the second-last reference to an import. Or that two fixes may spuriously conflict with each other because they each try to remove the same import; a simple conflict resolution strategy would work in this case.

We don't yet have a good calculus for composing fixes. Perhaps analyzers shouldn't even try to solve the goimports problem (since it isn't composable), and the driver's -fix flag should run goimports after any batch of fixes.

In other words, the inliner should only ever remove the import if it is removing the only usage of that import. If it is removing something and there is another usage, it should not generate an import removal (even if there are other suggested fixes removing all other usages).
Side note: especially in case where there are usages that are not removed by the inliner, it should not generate a suggested fix to remove the import as it does right now.

I totally agree, but it sounds like you are describing a plain and simple bug. If the tool prematurely removes an import while there is still an existing use, please file a bug report and I will fix it.

[lfolger]

I totally agree, but it sounds like you are describing a plain and simple bug. If the tool prematurely removes an import while there is still an existing use, please file a bug report and I will fix it.

I thought saw a but while preparing this example and then was to lazy file a separate bug which is why I folded this into this one. You prompted me to look into this again and while I was trying to reproduce this, I noticed that my report here is incorrect.

The duplicate findings are not the import removal but the formatting changes.

To summarize:

• The inliner does not generate any import removals for the given example. Even when you remove the call to pkg.Bar, it does not remove the import.
• The inliner produces duplicate suggested fixes to remove the identation. Note that all of the files are not properly indented so that they fit better into the test structure. All lines are indented by three \t and the inline analyzer attempts to remove these \t on each suggested fix.

I'm not sure if this is considered a bug or if the inliner is only supposed to work on files that a formated with gofmt.

Feel free to close this issue if you think this is intended behavior and sorry for the noise.

PS: I think I got confused because the test framework just reports diff has overlapping edits but not what theses diffs are.

[metonymic-smokey]

I plan to improve the API for the inliner so that it includes (for example) options to control literalization, consideration of side effects, and suchlike. I think it might also be useful (and I seem to recall writing a TODO comment to this effect) to return not just one but diff, but a more structured result that separates the diff around the call site from the logical changes to the import declaration. This would also allow Bazel/Blaze to interpose their visibiliity checking.

@adonovan is this the TODO you're referring to -
https://cs.opensource.google/go/x/tools/+/master:internal/refactor/inline/inline.go;l=55-58?
I was looking to contribute to the inlining part of the codebase and came across this when I was trying to understand it.

[adonovan]

In our meeting today we decided on an agreed interpretation of multiple fixes:

Each Diagnostic has a set of associated SuggestedFixes, each of which are logical alternatives; if there are more than one, the user must choose at most one. Once these choices have been made, we have a set of fixes to apply. Conceptually, all of these fixes are independent changes to the baseline file state, analogous to git commits with the same parent.

To combine them, we must merge them in some order, analogous to a git merge. Each merge may succeed, if the accumulated changes and the latest change do not overlap, or if the overlapping parts are changed in the same way; or it may fail, in which case the user must be informed of the conflict, and the latest change must be rejected. (It's up to the tool whether it proceeds as best it can with the next change, or aborts the whole operation, so long as it reports the error.)

• x/tools: implement three-way merge and use in all tools that apply fixes #68765

Naturally, the quality of the merge algorithm will determine how robust it is. Our existing conflict logic can de-duplicate identical changes, such as redundant additions of the same import at the same place, but nothing more; by contrast git-mergetool can often successfully resolve more complicated conflicts.

I propose to document this approach at analysis.SuggestedFix, and (eventually) to implement it in checker -fix and in gopls. Though I expect some common logic to resolve a set of fixes will be usefully shared among the various tools, we needn't discuss it here since we don't plan to share it.

The original problem in this thread is that RunWithSuggestedFixes tries to apply all the chosen fixes at once. I hit a related problem this morning in the context of https://go.dev/cl/592155; the solution in that case was to rewrite the test to use a txtar file as the .golden file, with one section per alternative suggested fix, using the description of the fix as the section title. But I don't think that will work here, because in this case we have multiple chosen fixes (not alternatives), all with the same description, and RunWithSuggestedFixes assumes that the descriptions are unique.

There is still a lot of room for improvement of the ergonomics of analysistest. Also, we have four open issues related to the difficulty of using modules in analysis tests:

• proposal: x/tools/go/analysis/analysistest: improved, module-aware API #61336
• x/tools/go/analysis/analysistest: add module-aware analyzer test runners #53063
• x/tools/go/analysis/analysistest: analysistest.Run failing with modules #46041
• x/tools/go/analysis/analysistest: support modules #37054

The situation was improved @timothy-king's recent change to make it easy to extract testdata files from .txtar files, so that go.mod files needn't be part of the source tree. However, that solution is incompatible with the use of .txtar files in RunWithSuggestedFixes, since txtar files do not nest. Definitely more work to do here.

(apologies for prematurely published first draft)

[gopherbot]

Change https://go.dev/cl/592495 mentions this issue: go/analysis: document interpretation of multiple diagnostics

[gopherbot]

Change https://go.dev/cl/593655 mentions this issue: go/analysis: deal with multiple fixes for same diagnostic

[gopherbot]

Change https://go.dev/cl/643196 mentions this issue: go/analysis/internal/checker: implement three-way merge

[gopherbot]

Change https://go.dev/cl/643695 mentions this issue: go/analysis: preparatory cleanups

[gopherbot]

Change https://go.dev/cl/644835 mentions this issue: go/analysis/internal/checker: implement three-way merge

[gopherbot]

Change https://go.dev/cl/647798 mentions this issue: go/analysis/analysistest: RunWithSuggestedFix: 3-way merge