【Go】go fmt でフォーマット化された後のimportの順番について

以前、[【Go】 go fmt でコード整形](http://qiita.com/taji-taji/items/6d286bf4483a4c6ceed6)という投稿をしました。
その際に、「importの順番が変わる」という点に触れましたが、どういう順番になるか詳細はわかっていなかったためソースを見て調べてみました。

## go fmt コマンドについて

### go fmt
go fmt コマンドを実行すると 'gofmt -l -w' が実行されます。
[go fmt ドキュメント](http://golang.org/cmd/go/#hdr-Run_gofmt_on_package_sources)

ですので、 gofmt のソースを見ていくことにします。

### gofmt

まずは gofmt 概要を。
[gofmt 日本語ドキュメント](http://golang-jp.org/cmd/gofmt/)

>gofmtはGoのソースコードをフォーマット（整形）するツールです。

とのことです。

オプションについては次のとおりです。

```
-d
        フォーマットした内容を標準出力へ出力しません。
        もしファイルのフォーマットがgofmtに通したものと異なる場合は、
        diffを標準出力します。
-e
        すべてのエラーを表示します。
-l
        フォーマットした内容を標準出力へ出力しません。
        もしファイルのフォーマットがgofmtに通したものと異なる場合は、
        そのファイル名を標準出力します。
-r rule
        再フォーマット前のソースコードへ置き換えルールを指定します。
        (Exampleを参照)
-s
        もし該当するコードがあれば、置き換えルールを適用した後にコードの簡素化を試みます。
        (The simplify commandを参照)
-w
        フォーマットした内容を標準出力へ出力しません。
        もしファイルのフォーマットがgofmtに通したものと異なる場合は、
        gofmtのもので上書き保存します。
```

## gofmt のコードを見てみる

### gofmt
https://golang.org/src/cmd/gofmt/gofmt.go
こちらを見ていくと、import順に関係がありそうな箇所がありました。
https://golang.org/src/cmd/gofmt/gofmt.go#L104

```go
ast.SortImports(fileSet, file)
```

ということで次に ast パッケージを見ていきます。

### go/ast

https://golang.org/pkg/go/ast/#SortImports

> SortImports sorts runs of consecutive import lines in import blocks in f. It also removes duplicate imports when it is possible to do so without data loss.

ファイル内のimportブロックの連続した行単位でソートし、重複したimportをなくすという感じでしょうか？
それでは、SortImports部分のコードを見ていきましょう。


#### SortImports

https://golang.org/src/go/ast/import.go?s=378:424#L5
以下、src/go/ast/import.go の SortImports 部分のみ抜粋です。

```go:src/go/ast/import.go(line13-51)

// SortImports sorts runs of consecutive import lines in import blocks in f.
// It also removes duplicate imports when it is possible to do so without data loss.
func SortImports(fset *token.FileSet, f *File) {
	for _, d := range f.Decls {
		d, ok := d.(*GenDecl)
		if !ok || d.Tok != token.IMPORT {
			// Not an import declaration, so we're done.
			// Imports are always first.
			break
		}

		if !d.Lparen.IsValid() {
			// Not a block: sorted by default.
			continue
		}

		// Identify and sort runs of specs on successive lines.
		i := 0
		specs := d.Specs[:0]
		for j, s := range d.Specs {
			if j > i && fset.Position(s.Pos()).Line > 1+fset.Position(d.Specs[j-1].End()).Line {
				// j begins a new run.  End this one.
				specs = append(specs, sortSpecs(fset, f, d.Specs[i:j])...)
				i = j
			}
		}
		specs = append(specs, sortSpecs(fset, f, d.Specs[i:])...)
		d.Specs = specs

		// Deduping can leave a blank line before the rparen; clean that up.
		if len(d.Specs) > 0 {
			lastSpec := d.Specs[len(d.Specs)-1]
			lastLine := fset.Position(lastSpec.Pos()).Line
			if rParenLine := fset.Position(d.Rparen).Line; rParenLine > lastLine+1 {
				fset.File(d.Rparen).MergeLine(rParenLine - 1)
			}
		}
	}
}
```

この中にsortSpecsという関数があります。
この関数も見てみましょう。

#### sortSpecs

```go:src/go/ast/import.go(line90-172)
func sortSpecs(fset *token.FileSet, f *File, specs []Spec) []Spec {
	// Can't short-circuit here even if specs are already sorted,
	// since they might yet need deduplication.
	// A lone import, however, may be safely ignored.
	if len(specs) <= 1 {
		return specs
	}

	// Record positions for specs.
	pos := make([]posSpan, len(specs))
	for i, s := range specs {
		pos[i] = posSpan{s.Pos(), s.End()}
	}

	// Identify comments in this range.
	// Any comment from pos[0].Start to the final line counts.
	lastLine := fset.Position(pos[len(pos)-1].End).Line
	cstart := len(f.Comments)
	cend := len(f.Comments)
	for i, g := range f.Comments {
		if g.Pos() < pos[0].Start {
			continue
		}
		if i < cstart {
			cstart = i
		}
		if fset.Position(g.End()).Line > lastLine {
			cend = i
			break
		}
	}
	comments := f.Comments[cstart:cend]

	// Assign each comment to the import spec preceding it.
	importComment := map[*ImportSpec][]*CommentGroup{}
	specIndex := 0
	for _, g := range comments {
		for specIndex+1 < len(specs) && pos[specIndex+1].Start <= g.Pos() {
			specIndex++
		}
		s := specs[specIndex].(*ImportSpec)
		importComment[s] = append(importComment[s], g)
	}

	// Sort the import specs by import path.
	// Remove duplicates, when possible without data loss.
	// Reassign the import paths to have the same position sequence.
	// Reassign each comment to abut the end of its spec.
	// Sort the comments by new position.
	sort.Sort(byImportSpec(specs))

	// Dedup. Thanks to our sorting, we can just consider
	// adjacent pairs of imports.
	deduped := specs[:0]
	for i, s := range specs {
		if i == len(specs)-1 || !collapse(s, specs[i+1]) {
			deduped = append(deduped, s)
		} else {
			p := s.Pos()
			fset.File(p).MergeLine(fset.Position(p).Line)
		}
	}
	specs = deduped

	// Fix up comment positions
	for i, s := range specs {
		s := s.(*ImportSpec)
		if s.Name != nil {
			s.Name.NamePos = pos[i].Start
		}
		s.Path.ValuePos = pos[i].Start
		s.EndPos = pos[i].End
		for _, g := range importComment[s] {
			for _, c := range g.List {
				c.Slash = pos[i].End
			}
		}
	}

	sort.Sort(byCommentPos(comments))

	return specs
}
```

こちらを見ると

```go
sort.Sort(byImportSpec(specs))
```

と

```go
sort.Sort(byCommentPos(comments))
```

があります。

sortパッケージが使われていますね。
それでは、「byImportSpec」部分と「byCommentPos」部分を見てみましょう。
以下に抜粋します。

```go:src/go/ast/import.go(line174-190)
type byImportSpec []Spec // slice of *ImportSpec

func (x byImportSpec) Len() int      { return len(x) }
func (x byImportSpec) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
func (x byImportSpec) Less(i, j int) bool {
	ipath := importPath(x[i])
	jpath := importPath(x[j])
	if ipath != jpath {
		return ipath < jpath
	}
	iname := importName(x[i])
	jname := importName(x[j])
	if iname != jname {
		return iname < jname
	}
	return importComment(x[i]) < importComment(x[j])
}
```

```go:src/go/ast/import.go(line192-196)
ype byCommentPos []*CommentGroup

func (x byCommentPos) Len() int           { return len(x) }
func (x byCommentPos) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
func (x byCommentPos) Less(i, j int) bool { return x[i].Pos() < x[j].Pos() }
```

byImportSpecでは、まずimportのPathを比較し、同じ場合にはimportのローカルネームを比較するようです。
それでも同じ場合はコメント部分を比較してソートされるようですね。（たぶん）

たとえば、

```go
import (
    "string"
    b "fmt" // fmt dayo
    a "fmt"
    b "fmt" // aaaa
    "fmt"
)
```

のようなimportは go fmt をすると

```go
import (
    "fmt"
    a "fmt"
    b "fmt" // aaaa
    b "fmt" // fmt dayo
    "string"
)
```

こうなります。
（同じPathのパッケージをimportすることってあるんですかね...？）


## 結論

つまり、「type ImportSpec」の「Path -> Name -> Comment」の順にソートされるようです。

```go
type ImportSpec struct {
        Doc     *CommentGroup // associated documentation; or nil
        Name    *Ident        // local package name (including "."); or nil
        Path    *BasicLit     // import path
        Comment *CommentGroup // line comments; or nil
        EndPos  token.Pos     // end of spec (overrides Path.Pos if nonzero)
}
```
http://golang.org/pkg/go/ast/#ImportSpec


素人なりにソースを読んでいったのですが、読み解け切れてもいないので間違いなどあればご指摘ください。m(__)m