Goを読むその2：compileコマンド（構文解析まで）

# はじめに

のらりくらりと読んでいるうちにバージョンが1.10.2になってしまいました(笑)

[前回](https://qiita.com/junjis0203/items/de55bb69945f08a9166c)はgo install時に何が行われているかを見てきました。結果、コンパイル処理は別コマンドのcompileコマンドで行われていることがわかりました。というわけで今回はcompileコマンドを見ていきます。
と言っても長くなると思うので今回は構文解析までを見ていきます。

ちなみに、compileコマンドにどのようなオプションが渡されるか確認したい場合はgo installに-nオプションを付けると表示されます。

```
cat >$WORK\b001\importcfg << 'EOF' # internal
# import config
packagefile fmt=D:\Go\pkg\windows_386\fmt.a
packagefile math/rand=D:\Go\pkg\windows_386\math\rand.a
packagefile runtime=D:\Go\pkg\windows_386\runtime.a
EOF
cd D:\work\go\src\montecarlo
"D:\\Go\\pkg\\tool\\windows_386\\compile.exe" -o "$WORK\\b001\\_pkg_.a" -trimpath "$WORK\\b001" -p main -complete -buildid tZ47rz089ryhLjQsSfSl/tZ47rz089ryhLjQsSfSl -goversion go1.10 -D "" -importcfg "$WORK\\b001\\importcfg" -pack -c=4 "D:\\work\\go\\src\\montecarlo\\main.go"
```

Windowsなのにどうやってcatコマンドとか実行してるんだ？と思ったら表示用に出力しているだけのようですね。\$WORKも実際のディレクトリパスが逆に\$WORKに置き換えられているようです。

# cmd/compile

スタート地点はcmd/compileの[main.go](https://github.com/golang/go/blob/go1.10/src/cmd/compile/main.go)です。
注目箇所のコードを貼り付けますが、前回と同様に一部カットした状態で貼り付けていることがあります。完全なコードはリンク先を参照してください。

まず先頭。各アーキテクチャのパッケージをインポートしており、それらのパッケージで定義されているInit関数[^1]を使ってマップを定義しています。マップは「string」から「func(*gc.Arch)」へのマップ、「func(*gc.Arch)」とは「gcパッケージに定義されているArch構造体へのポインタを引数に取る関数」の型です。Goの場合こういうの関数ポインタって言うのかな。
なお各アーキテクチャに埋もれてしまって少しわかりにくいですが、gcはアーキテクチャの一つではなくコンパイル処理の本体を行うパッケージです。うーむ、アーキテクチャはarchみたいなディレクトリに分けた方がいいような気がするのですが。

[^1]: ややこしいですが、InitとIが大文字のため、この関数はmain関数の前に自動的に実行されるinit関数とは別物です。

```go:cmd/compile/main.goより
import (
	"cmd/compile/internal/amd64"
	"cmd/compile/internal/arm"
	"cmd/compile/internal/arm64"
	"cmd/compile/internal/gc"
	(省略)
)

var archInits = map[string]func(*gc.Arch){
	"386":      x86.Init,
	(省略)
	"s390x":    s390x.Init,
}
```

main関数では[GOARCHをキーにアーキテクチャの対応Initを取り出してgcパッケージのMain関数を呼び出しています](https://github.com/golang/go/blob/go1.10/src/cmd/compile/main.go#L43)。このMain関数が実質的なmain関数です。ともかくこの時点でどのアーキテクチャ向けにコンパイルするかが決定され、以降はアーキテクチャ別の処理は渡されたArch構造体に設定された内容が使われるという仕組みのようです。

```go:cmd/compile/main.goより
	archInit, ok := archInits[objabi.GOARCH]
	gc.Main(archInit)
```

# cmd/compile/internal/gc

というわけでgcパッケージ。Main関数が書いてあるのはこちらも[main.go](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/main.go)です。

Main関数は500行以上あります。何をしているかは[Main関数の上のコメント](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/main.go#L128)に書かれています。

```go:cmd/compile/internal/gc/main.goより
// Main parses flags and Go source files specified in the command-line
// arguments, type-checks the parsed Go package, compiles functions to machine
// code, and finally writes the compiled package definition to disk.
```

日本語に訳すと以下のようになります。

1. コマンドラインフラグの解析
2. Goソースの解析
3. 解析したGoソースの型チェック
4. 関数を機械語に変換、ファイルに書き出し

## アーキテクチャ別処理構造

Main関数を先頭から見ていくと初めに[以下の処理](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/main.go#L136)が行われています。

```go:cmd/compile/internal/gc/main.goより
	archInit(&thearch)

	Ctxt = obj.Linknew(thearch.LinkArch)
```

archInitは先ほど確認したアーキテクチャごとのInit関数です。その関数にthearch（Arch構造体）を渡すことでアーキテクチャごとの内容を設定しています。ちなみに、Arch構造体は[go.go](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/go.go#L243)に定義されています。

その中のLinkArchとはなんぞやと確認すると、パッケージ変わってcmd/internal/objに定義されている構造体であることがわかります。より具体的には、[link.go](https://github.com/golang/go/blob/go1.10/src/cmd/internal/obj/link.go#L605)で定義されています。

```go:cmd/internal/obj/link.goより
// LinkArch is the definition of a single architecture.
type LinkArch struct {
	*sys.Arch
	Init           func(*Link)
	Preprocess     func(*Link, *LSym, ProgAlloc)
	Assemble       func(*Link, *LSym, ProgAlloc)
	Progedit       func(*Link, *Prog, ProgAlloc)
	UnaryDst       map[As]bool // Instruction takes one operand, a destination.
	DWARFRegisters map[int16]int16
}
```

linkという名前ではあるものの、実際にはアセンブラなどのソースコードをオブジェクトファイルに変換するために必要な情報（アーキテクチャごとの具体的なアセンブリへの変換方法）が設定されている雰囲気です。それはLinkArch構造体の少し上に書かれている[Link構造体のコメント](https://github.com/golang/go/blob/go1.10/src/cmd/internal/obj/link.go#L543)でも確認できます。

```go:cmd/internal/obj/link.goより
// Link holds the context for writing object code from a compiler
// to be linker input or for reading that input into the linker.
type Link struct {
```

つまり、Ctxtとは、contextの略であるということがわかります。
構文解析の時点ではアーキテクチャ別の処理は多分行われないと思うのでここら辺の確認は一旦ここまでとします。

## 構文解析処理概要

その後、

1. パッケージに対応する構造体の準備
2. 渡されたコマンドラインオプションの解析

が行われています。

[パッケージ構造体を作っている部分](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/main.go#L143)を見てみましょう。

```go:cmd/compile/internal/gc/main.goより
	localpkg = types.NewPkg("", "")
	localpkg.Prefix = "\"\""

	// pseudo-package, for scoping
	builtinpkg = types.NewPkg("go.builtin", "") // TODO(gri) name this package go.builtin?
	builtinpkg.Prefix = "go.builtin"            // not go%2ebuiltin
```

第2引数はnameです。ローカルパッケージ（つまり今コンパイル対象となっているパッケージ）、また、ビルトインの関数は「パッケージ名.名前」の形式ではなく「名前」とパッケージ名を付けないで指定するのでその仕組みのようです。ただし、ここではパッケージの作成だけしてビルトイン関数の登録は行われていないようです。

コマンドラインオプション解析についてはそこまで注目するものはないので飛ばして、Main関数を読み進めていくと[以下の部分](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/main.go#L447)があります。

```go:cmd/compile/internal/gc/main.goより
	initUniverse()

	loadsys()

	lines := parseFiles(flag.Args())

	finishUniverse()

```

parseFilesとあるので明らかにここで構文解析をしてそうですね。initUniverse, finishUniverseも対応しているので構文解析の初期化と終了処理をしてそうです。loadsysは何かロードしてるのでしょう（そのまんま）
というわけでinitUniverseに進みましょう、と読んでいったのですが、その結果、純粋に文法的な構文解析ではinitUniverse、loadsysで読み込まれている内容は使われていなかったのでこれらの関数で何が行われているかについては一旦保留しparseFilesに進みます。

# parseFiles

parseFiles関数は[noder.go](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/noder.go)に書かれています。
眺めてみましょう。まずは[前半](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/noder.go#L22)

```go:cmd/compile/internal/gc/noder.goより
func parseFiles(filenames []string) uint {
	var noders []*noder
	// Limit the number of simultaneously open files.
	sem := make(chan struct{}, runtime.GOMAXPROCS(0)+10)

	for _, filename := range filenames {
		p := &noder{err: make(chan syntax.Error)}
		noders = append(noders, p)

		go func(filename string) {
			sem <- struct{}{}
			defer func() { <-sem }()
			defer close(p.err)
			base := src.NewFileBase(filename, absFilename(filename))

			f, err := os.Open(filename)
			if err != nil {
				p.error(syntax.Error{Pos: src.MakePos(base, 0, 0), Msg: err.Error()})
				return
			}
			defer f.Close()

			p.file, _ = syntax.Parse(base, f, p.error, p.pragma, fileh, syntax.CheckBranches) // errors are tracked via p.error
		}(filename)
	}
```

ゴルーチン来ました。まあこれについてはコンパイルを並列実行しているなという程度なので、行っていることという点とGoのプログラム的に気になる点を挙げます。

まず行っていること、

- ファイル1つに対し1つの[noder構造体](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/noder.go#L22)が割り当てられる
- 解析した一連のファイルはnoders配列にまとめられている
- 解析処理本体はsyntaxパッケージ（cmd/compile/internal/syntax）に書かれている

次にGoプログラム的に気になる点です。

- forのループ変数filenameはゴルーチンとして起動している関数に引数で渡されている。次のループになるとfilenameの値が変わってしまうためか？
- 一方で変数p（noder構造体のポインタ）は引数として渡さずにクロージャ外の変数を参照している。これはポインタなので毎回アドレスが変わるのか？（変わるから引数で渡さなくてもいいのか？）

これを調べるためにはクロージャはどうコンパイルされて（どういう機械語になって）実行されるかを見ていかないといけないのでここでは「何かこの書き方気になるな」程度におさめておきます。

さて、[parseFiles関数後半](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/gc/noder.go#L48)

```go:cmd/compile/internal/gc/noder.goより
	var lines uint
	for _, p := range noders {
		for e := range p.err {
			yyerrorpos(e.Pos, "%s", e.Msg)
		}

		p.node()
		lines += p.file.Lines
		p.file = nil // release memory

		if nsyntaxerrors != 0 {
			errorexit()
		}
		// Always run testdclstack here, even when debug_dclstack is not set, as a sanity measure.
		testdclstack()
	}

	return lines
}
```

前半で作成したnoder構造体に対してnodeメソッド呼び出しを行っています。このnodeメソッドについてはまた後で見ますが、ここでGoプログラム的に気になるのは返しているのが構文解析したファイルの総行数だという点、別の言い方をすると解析したノード情報が返されていない点です。まあそれは戻り値ではなくパッケージレベルの変数に設定されるわけですが、戻り値で返さない理由がいまいちわかりません。Goのプログラムでは普通なのですかね？

ところで、これから見ていくわけですが、「名前.名前」という書き方について、どこで

- パッケージ内の関数呼び出し
- 型に対して定義されているメソッド呼び出し
- 構造体アクセス

を区別しているのかなと気になりました。感覚的には上記3つは構文解析レベルでは区別することは不可能なので意味解析のところでどういう呼び出しなのかが決定されるのかなと思われます。

# syntax.Parse

前半、syntaxパッケージの[Parse関数](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/syntax.go#L66)から見ていきましょう。

```go:cmd/compile/internal/syntax/syntax.goより
func Parse(base *src.PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, fileh FilenameHandler, mode Mode) (_ *File, first error) {
	var p parser
	p.init(base, src, errh, pragh, fileh, mode)
	p.next()
	return p.fileOrNil(), p.first
}
```

parserの変数作って、初期化して、なんか解析してると予想通りな記述です。
予想通りではあるのですが、実際にどう動いているかはよく確認する必要があります。

## 構造体の確認

まず、[parser構造体](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L18)の定義を確認しましょう。

```go:cmd/compile/internal/syntax/parser.goより
type parser struct {
	base  *src.PosBase
	errh  ErrorHandler
	fileh FilenameHandler
	mode  Mode
	scanner

	first  error  // first error encountered
	errcnt int    // number of errors encountered
	pragma Pragma // pragma flags

	fnest  int    // function nesting level (for error handling)
	xnest  int    // expression nesting level (for complit ambiguity resolution)
	indent []byte // tracing support
}
```

メンバーの5つ目に注意が必要です。scanner構造体が埋め込まれています。これにより、parser構造体はscanner構造体でもある、つまり、scanner構造体に対して定義されているメソッドを呼び出すことができるようになっています。実は先のnextというメソッドはparser構造体ではなくscanner構造体に対して定義されています。

次に[scanner構造体](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/scanner.go#L22)を確認してみましょう。こちらは[source構造体](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/source.go#L30)が埋め込まれています。source構造体は1文字（1ルーン）の読み込みを扱っているようです。

```go:cmd/compile/internal/syntax/scanner.goより
type scanner struct {
	source
	pragh  func(line, col uint, msg string)
	nlsemi bool // if set '\n' and EOF translate to ';'

	// current token, valid after calling next()
	line, col uint
	tok       token
	lit       string   // valid if tok is _Name, _Literal, or _Semi ("semicolon", "newline", or "EOF")
	kind      LitKind  // valid if tok is _Literal
	op        Operator // valid if tok is _Operator, _AssignOp, or _IncOp
	prec      int      // valid if tok is _Operator, _AssignOp, or _IncOp
}
```

## fileOrNilメソッド

source構造体で1文字読み込んで、scanner構造体ではsource構造体を利用して1トークン読み込んで、構文解析はどこでしてるの？nextを実行するとフック的に何かが実行されるのか？と思ったのですが違うようです。答えは、[fileOrNilメソッド](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L271)で構文解析処理が行われている、というものでした。

```go:cmd/compile/internal/syntax/parser.goより
// SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
func (p *parser) fileOrNil() *File {
```

コメントを見ると、なにやらBNFっぽいものが書かれています。Goのソースは確かにこの、パッケージ定義、インポート、トップレベルの定義（変数や関数）になっていますね。

[パッケージ定義の処理部分](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L280)を見てみましょう。

```go:cmd/compile/internal/syntax/parser.goより
	// PackageClause
	if !p.got(_Package) {
		p.syntax_error("package statement must be first")
		return nil
	}
	f.PkgName = p.name()
	p.want(_Semi)

	// don't bother continuing if package clause has errors
	if p.first != nil {
		return nil
	}
```

使われているメソッド等について確認していくと、

- 現在のコンテキストで出現するべきトークン（キーワードや名前など）は[gotメソッド](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L91)で指定する。類似品に[wantメソッド](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L99)がある。wantメソッドはトークンがないとエラーが設定される（firstメンバが設定される）
- トークン（tokメンバ）は[nextメソッド](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/scanner.go#L55)を呼び出すと設定される。キーワード周りについて追いかけていくと、identメソッドにて[キーワードかのチェック](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/scanner.go#L338)が行われている。キーワードのマップは[init関数](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/scanner.go#L376)で設定される。また、キーワード関連の変数は[tokens.go](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/tokens.go)に書かれている。
- 改行はセミコロンと同じ意味を持つ（多少の違いはあるが同じトークンとして扱われる）

## appendGroupメソッドと解析メソッド

次に[インポートの処理部分](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L293)です。

```go:cmd/compile/internal/syntax/parser.goより
	// { ImportDecl ";" }
	for p.got(_Import) {
		f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
		p.want(_Semi)
	}
```

単純にリストに追加しているように見えてよく見ると何をしているのかわかりません。どこで構文解析をしているのでしょうか。

答えは、[appendGroupメソッド](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L388)に進むとわかります。

```go:cmd/compile/internal/syntax/parser.goより
// appendGroup(f) = f | "(" { f ";" } ")" . // ";" is optional before ")"
func (p *parser) appendGroup(list []Decl, f func(*Group) Decl) []Decl {
	if p.tok == _Lparen {
		g := new(Group)
		p.list(_Lparen, _Semi, _Rparen, func() bool {
			list = append(list, f(g))
			return false
		})
	} else {
		list = append(list, f(nil))
	}

	return list
}
```

importが()で囲まれているかどうかの違いはありますが、ともかくappendGroupに渡される第2引数は関数であることがわかります。appendGroupには関数として渡されてくる（実際にはメソッド）ので、何らかの方法で紐づいている構造体の情報を保持しているということになります。

とりあえず、[importDeclメソッド](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L411)を見てみる。

```go:cmd/compile/internal/syntax/parser.goより
// ImportSpec = [ "." | PackageName ] ImportPath .
// ImportPath = string_lit .
func (p *parser) importDecl(group *Group) Decl {
	d := new(ImportDecl)
	d.pos = p.pos()

	switch p.tok {
	case _Name:
		d.LocalPkgName = p.name()
	case _Dot:
		d.LocalPkgName = p.newName(".")
		p.next()
	}
	d.Path = p.oliteral()
	if d.Path == nil {
		p.syntax_error("missing import path")
		p.advance(_Semi, _Rparen)
		return nil
	}
	d.Group = group

	return d
}
```

前半部分はパッケージに別名を付ける際の処理のようですね（[参考記事](https://qiita.com/taji-taji/items/5a4f17bcf5b819954cc1)）。メインはoliteralメソッドでこれによりインポートするパッケージのパスを記録しています。DeclやImportDeclの定義は[nodes.go](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/nodes.go)にあります。

これでパッケージとインポートの解析処理は終わりで、後はファイルを読み進めると遭遇するconst, type, var, funcに応じて同じように対応するDeclを作成していくことで構文解析を行っています。

## 注目メソッド

ざーっと眺めて興味深いものを挙げると、

- [typeOrNil](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L1021)：型の解析を行う。単純な型だけではなく、ポインタ、配列なども再帰呼び出しを用いて解析している。

- [funcDeclOrNil](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L506)：関数の解析を行う。関数の型についてはfuncType、関数本体についてはfuncBodyを呼び出し解析が行われます。また、メソッドの解析もこの関数で行われます。
  - [funcType](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L1122)：関数の型の解析を行う。関数の型は、引数リストと戻り値リスト（いわゆるシグニチャ）から構成されています。つまり、「func foo(n int) int」のうち、「(n int) int」について解析を行っています。
  - [funcBody](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L548)：関数本体解析のトップ。[blockStmt](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L1684)→[stmtList](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L2063)→[stmtOrNil](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L1961)と進んでいき、個々の文の解析が行われる。
- [pexpr](https://github.com/golang/go/blob/go1.10/src/cmd/compile/internal/syntax/parser.go#L802)：PrimaryExpressionの解析。Primaryとはついていますが「foo.bar(123)」のようなピリオド付きの関数呼び出しもすべてここで解析が行われています。この時点ではそれが別パッケージの関数なのかメソッド呼び出しなのかの区別は行われていないようです。

以上がsyntax.Parseで行われる処理の概要ということで、実際に手動で初回に挙げたモンテカルロプログラムを構文解析してみました。長いので手動解析結果はgistに置いておきます。

https://gist.github.com/junjis0203/d97c4fc5384ccaff231b60c2c9e6d2b4

# ここまでのまとめと感想

compileコマンドの手始めとして構文解析処理を見てきました。一部この後で必要になるアーキテクチャ別の処理や意味解析っぽい部分にも触れました。コンパイルはこの後、

- コード生成用の内部形式への変換
- 型チェックなどの意味解析
- コード生成

が行われると思われます（まだ読んでません）
一つ目の「コード生成用の内部形式への変換」というのはつまりparseFilesの後半部分、nodeメソッドを呼び出している部分なのですが一つの記事でこちらも扱うと長くなるので次回に回します（ざっと見た感じでは意味解析的な要素も絡んでくるようです）

読んでいて疑問だった点として、Rubyだといきなり内部形式にしてるのに何故一度純粋に文法的な構文木を作っているのだろうということがありました。
よく思うとその部分（文法が合っているかのチェック）はRubyの場合yaccがやってくれるんですね。つまり、Goの場合はyaccを使わないので文法的に正しいかのチェックを初めに自分で行い、文法的に正しいもののみ次の意味解析ステップに進めるということのようです。

この他、Goのプログラムとしての感想

- 処理が本格的になってきたので、ファイルが複数に分割されており、使われている関数、変数がどこで定義されているか探すのに少し苦労する。godef使えばいいわけですが。
- 構造体埋め込み、それによるオブジェクト指向的な振る舞い（？）と言語を駆使している感がある。