ASTを取得する方法を調べる #golang

## はじめに

みなさん、メリークリスマス！
22日の枠に欠員が出たので、[`go/parser`](https://golang.org/pkg/go/parser/)パッケージを使ってAST（抽象構文木）を取得する方法についてまとめたいと思います。

[`go`](https://golang.org/pkg/go/)パッケージについては、[簡単な式の評価機を作ってみる](http://qiita.com/tenntenn/items/a312d2c5381e36cf4cd3)という記事も書いているので、そちらもぜひ読んで下さい。

なお、この記事を執筆時点のGoの最新バージョンは1.7.4です。

## ノード

`go/parser`パッケージでは、いくつかの`Parse`と名前のついた関数でAST(抽象構文木)を取得することができます。ASTの各ノードを表す型は、[`go/ast`](https://golang.org/pkg/go/ast/)パッケージで提供されています。そしてそれらの型は、以下の[`ast.Node`](https://golang.org/pkg/go/ast/#Node)インタフェースを実装するように定義されています。

```go
type Node interface {
        Pos() token.Pos // position of first character belonging to the node
        End() token.Pos // position of first character immediately after the node
}
```

`ast.Node`インタフェースは、`Pos`メソッドと`End`メソッドを持ち、共に[`token.Pos`](https://golang.org/pkg/go/token/#Pos)型の値を返します。`token.Pos`はノードのコード上の位置を表します。

`token.Pos`が具体的にどんな値を表すかは後述しますので、ここでは、ノードのコード上の位置という理解でよいでしょう。

`go/ast`パッケージの[ドキュメント](https://golang.org/pkg/go/ast/#pkg-index)を見ると分かるように、`ast.Node`インタフェースを実装した型が多数存在することが分かります。

ドキュメントを見るだけでは、一体どの型が何を表し、どうやったら取得できるのか謎だと思いますが、それは`go/parse`パッケージが提供する`Parse`系の関数から取得できるノードから順にみていくとよいでしょう。

そこで、この記事では`go/parser`パッケージの提供する`Parse`系の関数について詳しくみていきたいと思います。

## パースする

ASTを取得するには、いくつか方法があります。
[簡単な式の評価機を作ってみる](http://qiita.com/tenntenn/items/a312d2c5381e36cf4cd3)で紹介した、[`ParseExpr`](https://golang.org/pkg/go/parser/#ParseExpr)は、式を表すASTのノードである、`ast.Expr`を返します。

この他にも、`Parse`系のメソッドは以下のように、いくつかあります。

* [`ParseDir`](https://golang.org/pkg/go/parser/#ParseDir)
* [`ParseFile`](https://golang.org/pkg/go/parser/#ParseFile)
* [`ParseExpr`](https://golang.org/pkg/go/parser/#ParseExpr)
* [`ParseExprFrom`](https://golang.org/pkg/go/parser/#ParseExprFrom)

上記の何が違うのかというと、パースの対象となるソースコードの範囲です。
`ParseDir`はディレクトリ以下にあるファイルが対象であるのに対して、`ParseFile`はファイルを対象としています。また、`ParseExpr`と`ParseExprFrom`は式を対象にしています。

そして、それぞれの関数によって、返されるノードの種類が異なります。
各関数のシグニチャを並べて、比べてみましょう。

```go
func ParseDir(fset *token.FileSet, path string, filter func(os.FileInfo) bool, mode Mode) (pkgs map[string]*ast.Package, first error)
func ParseFile(fset *token.FileSet, filename string, src interface{}, mode Mode) (f *ast.File, err error)
func ParseExpr(x string) (ast.Expr, error)
func ParseExprFrom(fset *token.FileSet, filename string, src interface{}, mode Mode) (ast.Expr, error)
```

`ast.ParseExpr`以外は、[`token.FileSet`](https://golang.org/pkg/go/token/#FileSet)型のポインタを引数に取るようです。まずは、この`token.FileSet`が何者なのかみてみましょう。

ちなみに、`ast.ParseExpr`は内部で以下のように[`ast.ParseExprFrom`を呼んでいる](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L234-L236)ようです。

```go
func ParseExpr(x string) (ast.Expr, error) {
	return ParseExprFrom(token.NewFileSet(), "", []byte(x), 0)
}
```

## token.FileSet

[サンプル](https://golang.org/pkg/go/parser/#example_ParseFile)をみる限り、`Parse`系に渡す`token.File`は、どうやら[`token.NewFileSet`](https://golang.org/pkg/go/token/#NewFileSet)関数で生成するようです。

つまり、初期化したものをそのまま渡すということは、`Parse`系の関数によって、渡した`token.FileSet`に何かしらの変更が加えられることが予想できます。

具体的に、`go/parser`パッケージのソースコードを読むと以下のように、`*token.FileSet`型の[`AddFile`](https://golang.org/pkg/go/token/#FileSet.AddFile)メソッドが[呼ばれていること](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/parser.go#L74)が分かります。

```go
func (p *parser) init(fset *token.FileSet, filename string, src []byte, mode Mode) {
	p.file = fset.AddFile(filename, -1, len(src))
	...
}
```

`*parser`型の`init`メソッドは、[`ast.ParseFile`から](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L120)と[`ast.ParseExprFrom`から](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L204)呼ばれています。なお、`ast.ParseDir`はファイルごとの処理を、`ast.ParseFile`にまかせているので、実質`ast.ParseDir`を読んでも`*token.FileSet`型の`AddFile`メソッドが呼ばれます。

さて、`AddFile`メソッドは何をしているのでしょうか？
[ソースコード](https://github.com/golang/go/blob/release-branch.go1.7/src/go/token/position.go#L364-L384)をみてみると、以下のようになっています。

```go
func (s *FileSet) AddFile(filename string, base, size int) *File {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	if base < 0 {
		base = s.base
	}
	if base < s.base || size < 0 {
		panic("illegal base or size")
	}
	// base >= s.base && size >= 0
	f := &File{s, filename, base, size, []int{0}, nil}
	base += size + 1 // +1 because EOF also has a position
	if base < 0 {
		panic("token.Pos offset overflow (> 2G of source code in file set)")
	}
	// add the file to the file set
	s.base = base
	s.files = append(s.files, f)
	s.last = f
	return f
}
```

`*.parser`型の`init`メソッドでは、`base`として`-1`を渡しています。そのため、上記のコードを読む限り、それまで追加されたファイルのサイズの合計+新しく追加されるファイルのサイズをそのファイルの`base`として計算しています。そして、その`base`を元に[`token.File`](https://golang.org/pkg/go/token/#File)型の値を生成し、内部に記録していきます。

どうやら、この`base`は、`*token.FileSet`型の`Position`メソッドで使用され、`ast.Node`インタフェースの`Pos`メソッドや`End`メソッドから取得できる`token.Pos`からファイル名や行数などを取得するために用いられるようです。
つまり、`*token.FileSet`型の`AddFile`メソッドで追加された順に、`base`をどんどんファイルサイズで加算していき、その値を元にノードの位置を`token.Pos`という値で表すことで、1つ数値でどのファイルのどの行なのかという情報を表せるようにしているようです。

さて、`token.FileSet`についてなんとなく分かったところで、各`Parser`系の関数についてみていきましょう。

## parser.ParseDir

`parser.ParseDir`関数のシグニチャは以下の通りです。

```go
func ParseDir(fset *token.FileSet, path string, filter func(os.FileInfo) bool, mode Mode) (pkgs map[string]*ast.Package, first error)
```

第2引数にパス、第3引数にフィルター関数、最後にモードを返しています。
モードについては後述するとして、第2引数と第3引数について説明したいと思います。

第2引数のパスは、パース対象の`.go`ファイルが入ったディレクトリです。このパスは、`os.Open`によって開かれ、内部のファイル一覧が取得されます。

そして、`.go`ファイルかつ第3引数のフィルターが`true`を返すファイルのみを対象にパースが行われます。なお、フィルターが`nil`の場合には、`.go`ファイルが対象になります。具体的には、ドキュメントか[ソースコード](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L153)を見るとわかるでしょう。

`ast.ParseDir`関数の戻り値は、`map[string]*ast.Package`とエラーです。
第1戻り値は、キーがパッケージ名で値が`*ast.Package`型の値のマップです。
上述のとおり、`ast.ParserDir`関数は内部で`ast.ParseFile`関数を呼び出しているため、その結果が`ast.Package`としてまとめられ、このマップに格納されています。

なお、第2戻り値の名前が`first`になっていることから分かるように、`ast.ParseFile`関数を呼んだ結果のうち最初のエラーのみが返却されます。また、エラーが置きてもすべてのファイルについて`ast.ParseFile`が実行されるようです。

戻り値の[`ast.Package`](https://golang.org/pkg/go/ast/#Package)は以下のように定義されている構造体です。もちろん、`ast.Node`インタフェースを実装しています。

```
type Package struct {
        Name    string             // package name
        Scope   *Scope             // package scope across all files
        Imports map[string]*Object // map of package id -> package object
        Files   map[string]*File   // Go source files by filename
}
```

どうやら[ソースコード](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L159-L162)を見る限り、`parser.ParseDir`関数で取得した、`ast.Package`には、`Imports`と`Scope`は設定されていないようです。

## parser.ParseFile

続いて、`parser.ParseFile`関数についてみてましょう。
シグニチャは以下のようになっていました。

```go
func ParseFile(fset *token.FileSet, filename string, src interface{}, mode Mode) (f *ast.File, err error)
```

第2引数と第3引数が謎ですね。
ドキュメントと[ソースコード](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L25-L47)を読むと、第3引数の`src`が`nil`の場合、第2引数のファイル名を使ってソースコードが`os.ReadFile`されるようです。

そして、`src`は、以下の4種類を受け付けるようです。

* `string`
* `[]byte`
* `*bytes.Buffer`
* `io.Reader`

いずれも最終的には`[]byte`型としてソースコードを扱っているようです。

また、`ast.ParseFile`関数の戻り値は、`*ast.File`型の値とエラーです。
[`ast.File`](https://golang.org/pkg/go/ast/#File)（`token.File`とは違うので注意）は、以下のように定義されています。

```go
type File struct {
        Doc        *CommentGroup   // associated documentation; or nil
        Package    token.Pos       // position of "package" keyword
        Name       *Ident          // package name
        Decls      []Decl          // top-level declarations; or nil
        Scope      *Scope          // package scope (this file only)
        Imports    []*ImportSpec   // imports in this file
        Unresolved []*Ident        // unresolved identifiers in this file
        Comments   []*CommentGroup // list of all comments in the source file
}
```

`Decls`フィールドから定義された関数や変数や型が取得できそうです。
また、`Comments`からはファイル中のコメントの一覧が取得できるようです。色々使えそうですね。

## parser.ParseExpr

`parser.ParseExpr`と`parser.ParseExprFrom`についてはここでは詳しく述べません。
[簡単な式の評価機を作ってみる](http://qiita.com/tenntenn/items/a312d2c5381e36cf4cd3)にも挙動を書いているので、ぜひそちらをご覧ください。

## parser.Mode

さて、`parser.ParseExpr`以外の`Parse`系の関数の最後の引数が[`parser.Mode`](https://golang.org/pkg/go/parser/#Mode)です。
これは、パースする際にどうパースするのかを表したフラグで以下のように定義されています。

```go
type Mode uint
const (
        PackageClauseOnly Mode             = 1 << iota // stop parsing after package clause
        ImportsOnly                                    // stop parsing after import declarations
        ParseComments                                  // parse comments and add them to AST
        Trace                                          // print a trace of parsed productions
        DeclarationErrors                              // report declaration errors
        SpuriousErrors                                 // same as AllErrors, for backward-compatibility
        AllErrors         = SpuriousErrors             // report all errors (not just the first 10 on different lines)
)
```

それぞれの意味を説明していきましょう。

* `PackageClauseOnly`: `package`の部分までパースする
* `ImportsOnly`: `import`の部分までパースする
* `ParseComments`: コメントをパースして、[ASTに追加する](https://play.golang.org/p/zOHRjjEnGS)
* `Trace`: パースの過程を[トレースする](https://play.golang.org/p/hDOLdrJtwP)
* `DeclarationErrors`: 定義エラーを見つける（多重定義とか）
* `SpuriousErrors`: 互換のためにある。`AllErrors`と同じ
* `AllErrors`: すべてのエラーを出す。そうじゃないと10個まで。

`ast.Mode`はフラグのため、上記の機能を追加しない場合は、基本的に`0`を指定しておけば問題ありません。
なお、エラーについては実際には、[`scanner.ErrorList`](https://golang.org/pkg/go/scanner/#ErrorList)が返却されるため、`parser.AllErrors`を指定した場合には、以下のように取得すると良いでしょう。

```go
fset := token.NewFileSet()
_, err := parser.ParseFile(fset, "sample.go", []byte(src), parser.DeclarationErrors|parser.AllErrors)
if err != nil {
	switch err := err.(type) {
	case scanner.ErrorList:
		for _, e := range err {
			fmt.Printf("%s:%d:%d %s\n", e.Pos.Filename, e.Pos.Line, e.Pos.Column, e.Msg)
		}
	default:
		fmt.Println(err)
	}
	return
}
```

ちなみに、`parser.AllErrors`を指定しない場合には、10個目のエラーまでしか、`scanner.ErrorList`に含まれません。その10個目までしか返却されないようにするのに、`panic`を使って大域脱出（[ここ](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/parser.go#L365-L367)と[ここ](https://github.com/golang/go/blob/release-branch.go1.7/src/go/parser/interface.go#L97-L102)）をしていたのが面白かったです。

## まとめ

この記事では、主に`go/parser`が提供する`Parse`系関数をベースにその周辺の型や関数について説明しました。
`Parse`系の関数で得られた、`ast.Node`インタフェースを実装したASTのノードをいじることで色々楽しいことができるので、ぜひやってみてください。

`go`パッケージの他のサブパッケージについてもまた記事を書きたいと思います。