protogen: drop dependency on golang.org/x/tools/go/ast/astutil

To keep the dependency tree of Go protobufs as small as possible,
avoid depending on astutil. Most of the complexity of astutil.AddNamedImport
was for identifying an existing import block to insert imports into,
which is not relevant for our use-case.

Assuming that we always create a new import block after the package
statement, the logic for doing the AST manipulation is relatively simple.
This re-write properly handles an inline comment after the
package statement, which astutil.AddNamedImport (see golang.org/issue/30724)
currently fails to do.

Change-Id: I894e733aa82a241719b6f0c23de8d2fbfb67b778
Reviewed-on: https://go-review.googlesource.com/c/protobuf/+/166522
Reviewed-by: Damien Neil <dneil@google.com>
diff --git a/go.mod b/go.mod
index e71ffb4..062debc 100644
--- a/go.mod
+++ b/go.mod
@@ -3,7 +3,6 @@
 require (
 	github.com/golang/protobuf v1.2.1-0.20190228215449-22c36ed95480
 	github.com/google/go-cmp v0.2.1-0.20181101181452-745b8ec83783
-	golang.org/x/tools v0.0.0-20190114222345-bf090417da8b
 	google.golang.org/genproto v0.0.0-20180831171423-11092d34479b // indirect
 	google.golang.org/grpc v1.19.0
 )
diff --git a/go.sum b/go.sum
index 46ce4b6..ea3b7b2 100644
--- a/go.sum
+++ b/go.sum
@@ -24,9 +24,7 @@
 golang.org/x/text v0.3.0 h1:g61tztE5qeGQ89tm6NTjjM9VPIm088od1l6aSorWRWg=
 golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
 golang.org/x/tools v0.0.0-20180904205237-0aa4b8830f48/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
-golang.org/x/tools v0.0.0-20180928181343-b3c0be4c978b h1:hjfKpJoTfQ2QXKPX9eCDFBZ0t9sDrZL/viAgrN962TQ=
 golang.org/x/tools v0.0.0-20180928181343-b3c0be4c978b/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
-golang.org/x/tools v0.0.0-20190114222345-bf090417da8b h1:qMK98NmNCRVDIYFycQ5yVRkvgDUFfdP8Ip4KqmDEB7g=
 golang.org/x/tools v0.0.0-20190114222345-bf090417da8b/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
 google.golang.org/appengine v1.1.0/go.mod h1:EbEs0AVv82hx2wNQdGPgUI5lhzA/G0D9YwlJXL52JkM=
 google.golang.org/genproto v0.0.0-20180817151627-c66870c02cf8/go.mod h1:JiN7NxoALGmiZfu7CAH4rXhgtRTLTxftemlI0sWmxmc=
diff --git a/protogen/protogen.go b/protogen/protogen.go
index a61baa0..cf1e809 100644
--- a/protogen/protogen.go
+++ b/protogen/protogen.go
@@ -34,7 +34,6 @@
 	"github.com/golang/protobuf/v2/reflect/protodesc"
 	"github.com/golang/protobuf/v2/reflect/protoreflect"
 	"github.com/golang/protobuf/v2/reflect/protoregistry"
-	"golang.org/x/tools/go/ast/astutil"
 
 	descriptorpb "github.com/golang/protobuf/v2/types/descriptor"
 	pluginpb "github.com/golang/protobuf/v2/types/plugin"
@@ -973,28 +972,66 @@
 		return nil, fmt.Errorf("%v: unparsable Go source: %v\n%v", g.filename, err, src.String())
 	}
 
-	// Add imports.
-	var importPaths []string
-	for importPath := range g.packageNames {
-		importPaths = append(importPaths, string(importPath))
-	}
-	sort.Strings(importPaths)
+	// Collect a sorted list of all imports.
+	var importPaths [][2]string
 	rewriteImport := func(importPath string) string {
 		if f := g.gen.opts.ImportRewriteFunc; f != nil {
 			return string(f(GoImportPath(importPath)))
 		}
 		return importPath
 	}
-	for _, importPath := range importPaths {
-		astutil.AddNamedImport(fset, file, string(g.packageNames[GoImportPath(importPath)]), rewriteImport(importPath))
+	for importPath := range g.packageNames {
+		pkgName := string(g.packageNames[GoImportPath(importPath)])
+		pkgPath := rewriteImport(string(importPath))
+		importPaths = append(importPaths, [2]string{pkgName, pkgPath})
 	}
 	for importPath := range g.manualImports {
-		if _, ok := g.packageNames[importPath]; ok {
-			continue
+		if _, ok := g.packageNames[importPath]; !ok {
+			pkgPath := rewriteImport(string(importPath))
+			importPaths = append(importPaths, [2]string{"_", pkgPath})
 		}
-		astutil.AddNamedImport(fset, file, "_", rewriteImport(string(importPath)))
 	}
-	ast.SortImports(fset, file)
+	sort.Slice(importPaths, func(i, j int) bool {
+		return importPaths[i][1] < importPaths[j][1]
+	})
+
+	// Modify the AST to include a new import block.
+	if len(importPaths) > 0 {
+		// Insert block after package statement or
+		// possible comment attached to the end of the package statement.
+		pos := file.Package
+		tokFile := fset.File(file.Package)
+		pkgLine := tokFile.Line(file.Package)
+		for _, c := range file.Comments {
+			if tokFile.Line(c.Pos()) > pkgLine {
+				break
+			}
+			pos = c.End()
+		}
+
+		// Construct the import block.
+		impDecl := &ast.GenDecl{
+			Tok:    token.IMPORT,
+			TokPos: pos,
+			Lparen: pos,
+			Rparen: pos,
+		}
+		for _, importPath := range importPaths {
+			impDecl.Specs = append(impDecl.Specs, &ast.ImportSpec{
+				Name: &ast.Ident{
+					Name:    importPath[0],
+					NamePos: pos,
+				},
+				Path: &ast.BasicLit{
+					Kind:     token.STRING,
+					Value:    strconv.Quote(importPath[1]),
+					ValuePos: pos,
+				},
+				EndPos: pos,
+			})
+		}
+		file.Decls = append([]ast.Decl{impDecl}, file.Decls...)
+	}
 
 	var out bytes.Buffer
 	if err = (&printer.Config{Mode: printer.TabIndent | printer.UseSpaces, Tabwidth: 8}).Fprint(&out, fset, file); err != nil {