cmd/goimports, imports: make goimports great again

I felt the burn of my laptop on my legs, spinning away while processing
goimports, and felt that it was time to make goimports great again.

Over the past few years goimports fell into a slow state of disrepair
with too many feature additions and no attention to the performance
death by a thousand cuts. This was particularly terrible on OS X with
its lackluster filesystem buffering.

This CL makes goimports stronger, together with various optimizations
and more visibility into what goimports is doing.

* adds more internal documentation

* avoids scanning $GOPATH for answers when running goimports on a file
  under $GOROOT (for Go core hackers)

* don't read all $GOROOT & $GOPATH directories' Go code looking for
  their package names until much later. Require the package name of
  missing imports to be present in the last two directory path
  components.  Then only try importing them in order from best to
  worst (shortest to longest, as before), so we can stop early.

* when adding imports, add names to imports when the imported package name
  doesn't match the baes of its import path. For example:
        import foo "example.net/foo/v1"

* don't read all *.go files in a package directory once the first file
  in a directory has revealed itself to be a package we're not looking
  for. For example, if we're looking for the right "client" for "client.Foo",
  we used to consider a directory "bar/client" as a candidate and read
  all 50 of its *.go files instead of stopping after its first *.go
  file had a "package main" line.

* add some fast paths to remove allocations

* add some fast paths to remove disk I/O when looking up the base
  package name of a standard library import (of existing imports in a
  file, which are very common)

* adds a special case for import "C", to avoid some disk I/O.

* add a -verbose flag to goimports for debugging

On my Mac laptop with a huge $GOPATH, with a test file like:

	package foo
	import (
	       "fmt"
	       "net/http"
	)

	/*

	*/
	import "C"

	var _ = cloudbilling.New
	var _ = http.NewRequest
	var _ = client.New

... this took like 10 seconds before, and now 1.3 seconds. (Still
slow; disk-based caching can come later)

Updates golang/go#16367 (goimports is slow)
Updates golang/go#16384 (refactor TestRename is broken on Windows)

Change-Id: I97e85d3016afc9f2ad5501f97babad30c7989183
Reviewed-on: https://go-review.googlesource.com/24941
Reviewed-by: Andrew Gerrand <adg@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
4 files changed