Goを読むその1：go installの流れ

はじめに

最近、Goに興味が出てきました。
今のところ私がGoについて学んだこととしては、

• 『みんなのGo言語』読んだ
• 「A Tour of Go」一通りやった
• 『Go言語によるWebアプリケーション開発』読んだ

程度となります。

私が言語を学ぶ方法の一つとして「その言語で書かれたメジャーなソフトのソースを読む」というものがあります。また、「その言語の処理系のソースを読む」という学習方法もあります。実際、Python（CPython）のソースを読んだことでPythonに対する理解はかなり深まりました。

さて、Goで何かいいソフトないかな、とりあえずコンパイラ読んでみようかな、と調べてみたところ、なんとGoのコンパイラはGoで書かれていることがわかりました（Go1.5以降）。つまり、Goで書かれたメジャーなソフトとはGo自身だったのです！
というわけで一石二鳥にGoのコンパイラを読みながらGoに対する理解を深めたいと思います。

読むバージョンは現状最新の1.10。多分読んでるうちにバージョン上がると思いますがこのバージョンで最後まで読みたいと思います。

コンパイラに食わせるソース

コンパイラの動作を確認する際にはソースコードを用意しそれがどのように構文解析、バイナリコード生成されていくかを自分で追っかけてみるのが有効です。というわけで今回はGoの特徴が出るようなプログラムとして以下のソースを考えました。

montecarlo/main.go

package main

import (
	"fmt"
	"math/rand"
)

func worker(n int, ch chan int) {
	count := 0
	for i := 0; i < n; i++ {
		x := rand.Float64()
		y := rand.Float64()
		if x*x+y*y <= 1 {
			count += 1
		}
	}
	ch <- count
}

func montecarlo(n, proc int) float64 {
	work := n / proc
	ch := make(chan int, proc)
	for i := 0; i < proc; i++ {
		go worker(work, ch)
	}
	sum := 0
	for i := 0; i < proc; i++ {
		sum += <-ch
	}
	return (float64(sum) / float64(n)) * 4
}

func main() {
	pi := montecarlo(10000*10000, 100)
	fmt.Printf("pi = %v\n", pi)
}

モンテカルロ法を使って円周率を計算するプログラムです。Goの特徴であるゴルーチンを用いており、チャネルを使って結果を集約しています。

一方で以下の機能は使っていません。これらについては可能であればコードを読んでいく際に寄り道して、不可能であれば別途眺めるようにしたいと思います。

• defer
• スライス
• マップ
• ポインタ
• メソッド
• 構造体
• インターフェース

コードリーディングのスタートライン

ではGo処理系のソースコードを読んでいきましょう。と言っても一気に全部読むわけにもいかないのでまずはとっかかり、

$ go install montecarlo

とした際にどうパッケージがビルドされるのかについて見ていく（ソースコードのコンパイルとかは次回以降で踏み込むとしてコンパイルも含めた全体的な流れを見ていく）ことにしましょう。
なお、以下に貼り付けているソースはひとまとまりが長すぎるなと思ったら断りなく省略している場合があります。完全なコードはリンク先を参照してください。

goコマンドに対応するmainパッケージはcmd/goにあります。その中のmain.goにmain関数が書かれています。

main.goを見るとすぐに目につくのはcmd/go/internalにあるパッケージをインポートしているということ

cmd/go/main.goより

import (
	(省略)

	"cmd/go/internal/base"
	"cmd/go/internal/bug"
	(省略)
	"cmd/go/internal/vet"
	"cmd/go/internal/work"
)

そしてinit関数でbase.Commandの配列を定義していることです。

cmd/go/main.goより

func init() {
	base.Commands = []*base.Command{
		work.CmdBuild,
		clean.CmdClean,
		(省略)
		work.CmdInstall,
		(省略)
	}
}

これらのことから引数で指定したサブコマンドに処理がディスパッチされるんだろうなと推測できますし実際にそうなっています。

補足。

• Goの「インポートパス」と「パッケージ名」は直接は関係ありません。つまり、「cmd/go/internal/base」とはそういうディレクトリにあるパッケージをインポートするということであり、インポートされるパッケージはソースにpackage文で書かれている名前です。ただし混乱のないように通常はインポートパスの最後とパッケージ名は揃えるそうです。『Go言語によるWebアプリケーション開発』に書いてありました。
• init関数はmain関数の前に実行される関数です（参考記事）。パッケージの依存関係を考慮した実行スケジューリングがどうなってるか気になりますが機会があればそちらも見てみたいと思います。

main関数でサブコマンドを確認している部分。

cmd/go/main.goより

	for _, cmd := range base.Commands {
		if cmd.Name() == args[0] && cmd.Runnable() {
			cmd.Flag.Usage = func() { cmd.Usage() }
			if cmd.CustomFlags {
				args = args[1:]
			} else {
				cmd.Flag.Parse(args[1:])
				args = cmd.Flag.Args()
			}
			cmd.Run(cmd, args)
			base.Exit()
			return
		}
	}

Name、Runnable、Usageはメソッドです。一方、Runは関数・・・、Goの場合は関数オブジェクトっていうのかな？、です。
Command構造体はcmd/internal/baseのbase.goに書かれています。

cmd/internal/base/base.goより

// A Command is an implementation of a go command
// like go build or go fix.
type Command struct {
	// Run runs the command.
	// The args are the arguments after the command name.
	Run func(cmd *Command, args []string)

	(省略)
}

とまあそんなこんなで次に見るのはcmd/internal/workにあるworkパッケージであるとわかります。

workパッケージ

workパッケージ中、CmdInstallはbuild.goに書かれています。Runはinit関数でrunInstallに設定されています。てわけでrunInstall関数。

cmd/internal/work/build.goより

func runInstall(cmd *base.Command, args []string) {
	BuildInit()
	InstallPackages(args, false)
}

ツールチェーンの設定

BuildInit関数はinit.goに書かれています¹。さらにbuildModeInit関数を呼び出して初期化が行われているわけですが、

cmd/internal/work/init.goより

func buildModeInit() {
	gccgo := cfg.BuildToolchainName == "gccgo"
	(省略)
}

gccgoかはともかく、いつのまにツールチェーンが設定されたのか。ツールチェーンとして何が使われるかは大事なのでちゃんと見てみましょう。
・・・あ、ツールチェーンってわかりますよね？コンパイラとかリンカのことです。

build.goで「Toolchain」を検索してみたら以下のコードがありました。

cmd/internal/work/build.goより

type buildCompiler struct{}

func (c buildCompiler) Set(value string) error {
	switch value {
	case "gc":
		BuildToolchain = gcToolchain{}
	case "gccgo":
		BuildToolchain = gccgoToolchain{}
	default:
		return fmt.Errorf("unknown compiler %q", value)
	}
	cfg.BuildToolchainName = value
	(省略)
}

func init() {
	switch build.Default.Compiler {
	case "gc", "gccgo":
		buildCompiler{}.Set(build.Default.Compiler)
	}
}

init関数は何個書いてもいいんですね。
BuildToolchainの型はtoolchainインターフェースでgcを使うのかgccgoを使うのかに関わらず共通のインターフェースを提供する目的で使われています。また、上記コードでは省略していますがbuildCompiler構造体はflag.Varインターフェースに即しており、コマンドラインで-compilerオプションを指定するとSetメソッドが呼ばれるようです。早速Goの威力を発揮した書き方がありましたね。

さて続いて、で結局デフォルトはgcなの？gccgoなの？という問題を片付けましょう。そのためにはbuildパッケージを見る必要があります。こいつのパスはgo/buildです。その中のbuild.go（ややこしい）のDefaultの定義、

go/build/build.goより

var Default Context = defaultContext()

func defaultContext() Context {
	var c Context

	(省略)
	c.Compiler = runtime.Compiler

	(省略)

	return c
}

さらにruntimeパッケージ・・・、はファイルが非常にたくさんあるのですがCompilerって書いてあるんだからcompiler.goに書いてあるんだろうとあたりをつけて

runtime/compiler.goより

const Compiler = "gc"

はい、というわけでgcToolchainが使われるようです。実際にツールチェーンを使う部分はまた後で。

InstallPackages関数

話をrunInstall関数まで戻して、その後呼ばれているのはInstallPackages関数です。エラー処理とかコメントとか削って骨格だけ示すと以下のようになります。

cmd/internal/work/build.goより

func InstallPackages(args []string, forGet bool) {
	pkgs := pkgsFilter(load.PackagesForBuild(args))

	var b Builder
	b.Init()
	depMode := ModeBuild
	a := &Action{Mode: "go install"}
	for _, p := range pkgs {
		a1 := b.AutoAction(ModeInstall, depMode, p)
		a.Deps = append(a.Deps, a1)
	}
	b.Do(a)
}

BuilderとActionが次の鍵のようです。
でもその前に、loadパッケージのPackagesForBuild関数を追いかけてみましょう。なお、pkgsFilterは普通にgo installするときは何もフィルタしない（つまりPackagesForBuildが返したものをそのまま通す）はず。

パッケージの読み込みと依存関係の構築

PackagesForBuild関数

パスはcmd/go/internal/load、PackagesForBuild関数はpkg.goにあります。
実際の処理はPackagesForBuildから呼び出されてるPaclagesAndErrors関数で行われています。

cmd/internal/load/pkg.goより

func PackagesAndErrors(args []string) []*Package {
	args = ImportPaths(args)
	var (
		pkgs    []*Package
		stk     ImportStack
		seenArg = make(map[string]bool)
		seenPkg = make(map[*Package]bool)
	)

	for _, arg := range args {
		if seenArg[arg] {
			continue
		}
		seenArg[arg] = true
		pkg := LoadPackage(arg, &stk)
		if seenPkg[pkg] {
			continue
		}
		seenPkg[pkg] = true
		pkgs = append(pkgs, pkg)
	}

	return pkgs
}

ImportPaths関数はファイルが変わってsearch.goに書かれていますが今の場合はそのまま返ってくるはず。

LoadPackage関数

LoadPackage関数。何個かif文がありますが今回はいずれも該当しないので省くと、

cmd/internal/load/pkg.goより

func LoadPackage(arg string, stk *ImportStack) *Package {
	(省略)
	return LoadImport(arg, base.Cwd, nil, stk, nil, 0)
}

というわけでLoadImport関数に続きます。
LoadImport関数は長いのでまた骨格だけ示すと、

cmd/internal/load/pkg.goより

func LoadImport(path, srcDir string, parent *Package, stk *ImportStack, importPos []token.Position, mode int) *Package {
	stk.Push(path)
	defer stk.Pop()

	importPath := path

	p := packageCache[importPath]
	if p != nil {
		p = reusePackage(p, stk)
	} else {
		p = new(Package)
		packageCache[importPath] = p

		var bp *build.Package
		var err error
		(省略)
		} else {
			buildMode := build.ImportComment
			bp, err = cfg.BuildContext.Import(path, srcDir, buildMode)
		}
		p.load(stk, bp, err)
	}

	return p
}

ポイントは以下の2点です。インポートをしているということはつまりファイルの中身を読んでいる→構文解析をしているということですがその部分は次回以降で読んでいくので今は見ないことにします。

• cfgパッケージのBuidContextを使ってパッケージのインポートをしている。なお、BuildContextとは先ほども出てきたgo/buildのbuildパッケージのDefaultです。
• 読み込んだパッケージ情報をloadしている。PackageはloadパッケージのPackage構造体（上の変数で言うとp）とbuildパッケージのPackage構造体（同bp）があるので注意です。

go/buildのImportメソッドは400行近くあるので要点だけ示します。

• 前半でGOPATHなどから指定されたパスに対応するパッケージの絶対パスを決定
• 後半でパッケージディレクトリ内のファイルをスキャンしてインポートしているパッケージパスを収集

loadメソッド

loadメソッドも300行近くあります。特に注目すべきところを2点挙げるとするとまず中盤、

cmd/internal/load/pkg.goより

	importPaths := p.Imports
	addImport := func(path string) {
		for _, p := range importPaths {
			if path == p {
				return
			}
		}
		importPaths = append(importPaths, path)
	}

	if p.Name == "main" && !p.Internal.ForceLibrary {
		for _, dep := range LinkerDeps(p) {
			addImport(dep)
		}
	}

LinkerDeps関数を確認すると以下のようになっています。これで実行ファイルを作る際にruntimeパッケージがリンクされるということになっているようです。

cmd/internal/load/pkg.goより

func LinkerDeps(p *Package) []string {
	// Everything links runtime.
	deps := []string{"runtime"}

	(省略)

	return deps
}

loadメソッドに戻ってもうひとつの注目箇所。以下のようにしてインポートしているパッケージがさらにインポートしているパッケージ、と再帰的に依存関係を構築しています。

cmd/internal/load/pkg.goより

	// Build list of imported packages and full dependency list.
	imports := make([]*Package, 0, len(p.Imports))
	for i, path := range importPaths {
		p1 := LoadImport(path, p.Dir, p, stk, p.Internal.Build.ImportPos[path], UseVendor)

		imports = append(imports, p1)
	}
	p.Internal.Imports = imports

BuilderとAction

さてというわけでパッケージとその依存関係が構築できたのでworkパッケージに戻ってビルドです。ページ戻るの面倒なのでInstallPackages関数（の骨格）を再掲します。

cmd/internal/work/build.goより

func InstallPackages(args []string, forGet bool) {
	pkgs := pkgsFilter(load.PackagesForBuild(args))

	var b Builder
	b.Init()
	depMode := ModeBuild
	a := &Action{Mode: "go install"}
	for _, p := range pkgs {
		a1 := b.AutoAction(ModeInstall, depMode, p)
		a.Deps = append(a.Deps, a1)
	}
	b.Do(a)
}

Builder.AutoActionメソッド

action.goに書かれているAutoActionメソッドを見てみましょう。

cmd/internal/work/action.goより

func (b *Builder) AutoAction(mode, depMode BuildMode, p *load.Package) *Action {
	if p.Name == "main" {
		return b.LinkAction(mode, depMode, p)
	}
	return b.CompileAction(mode, depMode, p)
}

mainパッケージなのでLinkActionに丸投げもとい移譲

cmd/internal/work/action.goより

// LinkAction returns the action for linking p into an executable
// and possibly installing the result (according to mode).
// depMode is the action (build or install) to use when compiling dependencies.
func (b *Builder) LinkAction(mode, depMode BuildMode, p *load.Package) *Action {
	// Construct link action.
	a := b.cacheAction("link", p, func() *Action {
		a := &Action{
			Mode:    "link",
			Package: p,
		}

		a1 := b.CompileAction(ModeBuild, depMode, p)
		a.Func = (*Builder).link
		a.Deps = []*Action{a1}
		a.Objdir = a1.Objdir

		name := "a.out"
		(省略)
		a.Target = a.Objdir + filepath.Join("exe", name) + cfg.ExeSuffix
		a.built = a.Target
		b.addTransitiveLinkDeps(a, a1, "")

		// Sequence the build of the main package (a1) strictly after the build
		// of all other dependencies that go into the link. It is likely to be after
		// them anyway, but just make sure. This is required by the build ID-based
		// shortcut in (*Builder).useCache(a1), which will call b.linkActionID(a).
		// In order for that linkActionID call to compute the right action ID, all the
		// dependencies of a (except a1) must have completed building and have
		// recorded their build IDs.
		a1.Deps = append(a1.Deps, &Action{Mode: "nop", Deps: a.Deps[1:]})
		return a
	})

	if mode == ModeInstall || mode == ModeBuggyInstall {
		a = b.installAction(a, mode)
	}

	return a
}

Go1.10からビルド時にキャッシュされるようになったようですがそれは無視するとして（実際キャッシュされてなかったら渡している関数がすぐに実行されてActionが返されます）、構築されているものとしては以下のようになっています。

• インストールする（installAction）ためにはリンク（cacheActionに渡されてる関数で作られてるAction）が必要だ
• リンクするためにはソースのコンパイル（CompileAction）が必要だ
• mainパッケージがリンクできるためには依存パッケージのビルドが全部終わっている必要がある（CompileAction内での依存設定およびaddTransitiveLinkDepsでの処理、また最後に依存を調整している箇所）

といった感じにActionの依存関係が構築されているようです。ActionのFuncに設定している書き方が見慣れないですがなんとなくメソッドを関数として設定しているんだろうなということは想像できます。

この先のAction構築詳細は長くなるので省略。

Builder.Doメソッド

Actionの依存関係が構築できたので後は実行するだけです。exec.goに書かれているDoメソッドに進みます。Doメソッド長いですが端折れるところがあまりないので順に見ていきます。

まずDoメソッドのすぐ上に書かれているactionList関数を使ってツリー構造（依存関係表現）になっているActionをリストに変換しています。

cmd/internal/work/exec.goより

func (b *Builder) Do(root *Action) {
	all := actionList(root)
	for i, a := range all {
		a.priority = i
	}

次にチャネルを作成しています。SemaはSemaphoreの略かな？依存するActionがない場合は実行準備OKとしている雰囲気です。

cmd/internal/work/exec.goより

	b.readySema = make(chan bool, len(all))

	// Initialize per-action execution state.
	for _, a := range all {
		for _, a1 := range a.Deps {
			a1.triggers = append(a1.triggers, a)
		}
		a.pending = len(a.Deps)
		if a.pending == 0 {
			b.ready.push(a)
			b.readySema <- true
		}
	}

handle関数を定義しています。Actionに設定されたFuncを実行して、そのActionに依存しているActionのpending数を減らし先ほどのreadySemaに値を送っています。

cmd/internal/work/exec.goより

	// Handle runs a single action and takes care of triggering
	// any actions that are runnable as a result.
	handle := func(a *Action) {
		var err error

		if a.Func != nil && (!a.Failed || a.IgnoreFail) {
			if err == nil {
				err = a.Func(b, a)
			}
		}

		// The actions run in parallel but all the updates to the
		// shared work state are serialized through b.exec.
		b.exec.Lock()
		defer b.exec.Unlock()

		if err != nil {
			(省略)
			a.Failed = true
		}

		for _, a0 := range a.triggers {
			if a.Failed {
				a0.Failed = true
			}
			if a0.pending--; a0.pending == 0 {
				b.ready.push(a0)
				b.readySema <- true
			}
		}

		if a == root {
			close(b.readySema)
		}
	}

ゴルーチン来ました。準備ができているActionを取り出し実行、を並行で行っているようです。なお、BuildPのデフォルト値はruntime.NumCPU()です。

cmd/internal/work/exec.goより

	var wg sync.WaitGroup

	// Kick off goroutines according to parallelism.
	par := cfg.BuildP
	for i := 0; i < par; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for {
				select {
				case _, ok := <-b.readySema:
					if !ok {
						return
					}
					// Receiving a value from b.readySema entitles
					// us to take from the ready queue.
					b.exec.Lock()
					a := b.ready.pop()
					b.exec.Unlock()
					handle(a)
				case <-base.Interrupted:
					base.SetExitStatus(1)
					return
				}
			}
		}()
	}

	wg.Wait()

Builder.buildメソッド

Action.Funcの実例としてCompileActionで設定されているbuildを、と思ったけどこれも長いですね。また注目部分だけ載せます。

cmd/internal/work/exec.goより

	// Compile Go.
	objpkg := objdir + "_pkg_.a"
	ofile, out, err := BuildToolchain.gc(b, a, objpkg, icfg.Bytes(), len(sfiles) > 0, gofiles)

Goコードのビルドに関わる部分は多分これだけなはず。

最後にツールチェーンの確認をしておきましょう。gcToolchainを使っているのでgc.goです。gc関数、標準パッケージ対応とかしているところをさっくり削ると、

cmd/internal/work/gc.goより

func (gcToolchain) gc(b *Builder, a *Action, archive string, importcfg []byte, asmhdr bool, gofiles []string) (ofile string, output []byte, err error) {
	p := a.Package
	objdir := a.Objdir
	if archive != "" {
		ofile = archive
	}

	pkgpath := p.ImportPath
	if cfg.BuildBuildmode == "plugin" {
		pkgpath = pluginPath(a)
	} else if p.Name == "main" && !p.Internal.ForceLibrary {
		pkgpath = "main"
	}
	gcargs := []string{"-p", pkgpath}

	extFiles := len(p.CgoFiles) + len(p.CFiles) + len(p.CXXFiles) + len(p.MFiles) + len(p.FFiles) + len(p.SFiles) + len(p.SysoFiles) + len(p.SwigFiles) + len(p.SwigCXXFiles)
	if extFiles == 0 {
		gcargs = append(gcargs, "-complete")
	}
	if strings.HasPrefix(runtimeVersion, "go1") && !strings.Contains(os.Args[0], "go_bootstrap") {
		gcargs = append(gcargs, "-goversion", runtimeVersion)
	}

	gcflags := str.StringList(forcedGcflags, p.Internal.Gcflags)

	args := []interface{}{cfg.BuildToolexec, base.Tool("compile"), "-o", ofile, "-trimpath", trimDir(a.Objdir), gcflags, gcargs, "-D", p.Internal.LocalPrefix}
	if importcfg != nil {
		if err := b.writeFile(objdir+"importcfg", importcfg); err != nil {
			return "", nil, err
		}
		args = append(args, "-importcfg", objdir+"importcfg")
	}
	if ofile == archive {
		args = append(args, "-pack")
	}

	// Add -c=N to use concurrent backend compilation, if possible.
	if c := gcBackendConcurrency(gcflags); c > 1 {
		args = append(args, fmt.Sprintf("-c=%d", c))
	}

	for _, f := range gofiles {
		args = append(args, mkAbs(p.Dir, f))
	}

	output, err = b.runOut(p.Dir, p.ImportPath, nil, args...)
	return ofile, output, err
}

というわけでコマンドラインを構築しています。
base.Tool("compile")でcompileコマンドがあるパスが返されます。$GOROOT/pkg/tool/$GOOS_$GOARCH/compileです。

ここまでのまとめと感想

Goコンパイラを読むの手始めとしてgo install時の流れについて見てきました。linkとinstall見てませんがまあやっていることはbuildと同じようなもの、linkの中身については今後見ていくかもしれません。

さて、ここまで読んできて深入りしなかったインポートパスの取得以外はコンパイラ的要素は出てきていません。途中で気づいたのですがgo installってC言語などで言うmakeそのものなんですね。最後に見たように実際のコンパイル等は別コマンドで行われているようです。

ここまでで出てきたGo言語っぽい要素としては以下があります。

• init関数を使ったパッケージの初期化
• インターフェースを使ったツールチェーンの切り替え
• メソッド
• ゴルーチンとチャネルによるビルドの並行化。どうやらコンパイル自体も並行化しているらしい
• defer
• 関数内関数（クロージャ）の利用

GoコンパイラはちゃんとGoっぽいソースになっていますね。
もうひとつ、たびたび書いていますがなんとなくひとつの関数（メソッド）が長い印象がありました。いろんなコマンドラインオプションなどを考慮して処理が流れているからだとは思うのですが。

1. 初め読み始めたのは1.9で、その時は初期化もbuild.goに書かれていたのですが、1.10になって複数のファイルに分割整理されたようですね。 ↩