Go Modules時代の静的解析

# はじめに

この記事は[Go5 Advent Calendar 2019](https://qiita.com/advent-calendar/2019/go5) 4日目の記事です。

Go Modulesがデフォルトで有効になったGo1.13がリリースされてはや３ヶ月。皆さんいかがお過ごしでしょうか。私は「Modules何もわからん」となっててんやわんやでした。
この記事ではModulesの変化の影響を受けやすいGoプログラムの静的解析について、入門〜中級者向けに解説していきます。

# 静的解析とは？

プログラムを実行せずにその内容を解析することを静的解析と言います。コンパイラによる構文解析や型チェックをはじめ、エディタがタイポを検出したり補完機能を提供したりするのも静的解析です。これらとは逆に、ユニットテストや性能評価などはプログラムを実行しているので動的解析と呼ばれます。
Goは`gofmt`や`goimports`など静的解析ツールが豊富なことでも有名です。

# Go Modulesとは？

Go公式の依存パッケージのバージョン管理システムです。Go 1.11から導入され、Go 1.13よりデフォルトで有効になっています。
初期のGoは「常に最新版を使えばええやろ！互換性のない変更を加えるなら別のパッケージを作れ！」と強気な姿勢をとっていましたが、色々あってvendorやgo depsなど準公式ツールでの試行錯誤の末ついに公式に導入されたのがGo Modulesというわけです。

# 静的解析とModulesの関係

静的解析に際してソースコードまたはパッケージファイル(*.a)を読み込むわけですが、当然依存しているパッケージの情報がないと解析を行えないので、静的解析の実行はパッケージ管理システムに依存します。
つまり、Go 1.10以前の静的解析プログラムはModulesに対応していない場合があるということです。そこで本稿ではModulesに対応済みの(標準・準標準)ライブラリとその使い方を紹介します。

# TL; DR

- レールに乗っかりたい、モジュール化された静的解析ライブラリを作りたい → `analysis`
  - [Mercariのブログ](https://tech.mercari.com/entry/2018/12/16/150000)が参考になる
- とにかく動かしたい、基礎を理解したい → `go/*`, `packages`

# Package go/*

Goが公式にサポートする静的解析用のパッケージ群です。基本的にこの後に紹介するパッケージの内部で使用されるため、`ast`, `token`, `types`の型を提供するパッケージをメインにさわることになります。

|go/*|説明|
|:--|:--|
| ast | ASTを構成する型とそれらに対する操作 |
| build | GOPATHやビルドタグなどの情報 |
| constant | 型の指定されていない定数に対する操作 |
| doc | ソースコードからドキュメントを収集 |
| format | Go標準のフォーマッタ |
| importer | コンパイラ実装(gc, gccgo)ごとのimport処理を抽象化 |
| parser | 文字列/ファイル/ディレクトリを読み込んでASTを返す |
| printer | ASTを整形して表示 |
| scanner | 字句解析の実装 |
| token | 字句解析結果の型とそれらに対する操作 |
| types | 型チェッカーの実装と結果の型 |

注意：これらのうち、`importer`はModules対応で変更が入っており、`importer.For()`は`importer.ForCompiler()`に修正する必要があります……が、そもそも`importer.Default()`を使っている場合が多いと思うのでそんなに影響はないのではないでしょうか。

# Package golang.org/x/tools/go/*

Goの準標準パッケージです。上記の標準パッケージを利用したハイレベルな機能が数多く提供されています。ここではその中でも特に知っていると得するパッケージを紹介します。
標準ライブラリではないため後方互換性が保証されていないと注意書きされてますが、それこそModulesを使えば勝手にアップデートされて動かなくなるということはないので大体の人は心配しなくてもいいでしょう。
Modules対応に際し大きな変更が入り、`loader`パッケージが廃止されて代わりに`packages`パッケージが新たに用意されました。

## Package analysis

[analysis - GoDoc](https://godoc.org/golang.org/x/tools/go/analysis)

静的解析プログラムを抽象化し、再利用可能性を高めて他の解析と簡単に組み合わせられるようにします。サブパッケージ`analysis/analysistest`では複雑になりがちな静的解析プログラムのテストの記述を支援します。また、サブパッケージ`analysis/passes/*`としてよく用いられる解析処理を提供しています。
`analysis/passes/*`の多くは`go vet`コマンドにより利用できます。例外である`buildssa`, `ctrlflow`, `inspect`は他のAnalyzerに利用されることを前提としたAnalyzerで、新たに静的解析ツールを自作する場合も利用できます。それぞれ後で解説する`ssa`、`cfg`、`ast/inspector`が実装の本体となっています。

このパッケージに関しては[Goにおける静的解析のモジュール化について - Mercari Engineering Blog](https://tech.mercari.com/entry/2018/12/16/150000)が非常によくまとまっていて分かりやすいので一読をおすすめします。

## Package ast/astutil

[astutil - GoDoc](https://godoc.org/golang.org/x/tools/go/ast/astutil)

既存のASTを改変して新しいASTを作る関数`Apply()`や式(Expr)の括弧を外して中身を取り出す関数`Unparen()`などASTに関するをユーティリティ提供します。

## Package ast/inspector

[inspector - GoDoc](https://godoc.org/golang.org/x/tools/go/ast/inspector)

ASTをトラバースするためのデータ構造を提供します。標準パッケージの`ast.Inspect()`に比べて、メモ化による複数呼び出しの高速化とノードのフィルタリング、探索スタック付きのトラバースをサポートします。`analysis/passes/inspect`で利用されているのはこちらになります。
メモ化のためのオーバーヘッドがあるので、同じASTに対して数回しか呼び出さない場合は`ast.Inspect()`のほうが高速なことに注意です。

## Package callgraph

[callgraph - GoDoc](https://godoc.org/golang.org/x/tools/go/callgraph)

関数Aの内部で関数Bが呼び出されている、といった関係をグラフとして表現します。グラフの生成の実装はサブパッケージとして`cha`, `rta`, `static`の３種類のアルゴリズムが提供されています。

## Package cfg

[cfg - GoDoc](https://godoc.org/golang.org/x/tools/go/cfg)

ある関数内での`if`や`switch`による分岐をグラフで表現します。ある処理が必ず呼び出されているか検査したいときなどに便利です。ただし論理演算子の短絡評価や`panic`による分岐などはサポートされていないため、それらが必要な場合後述する`golang.org/x/tools/go/ssa`を使います。

## Package packages

[packages - GoDoc](https://godoc.org/golang.org/x/tools/go/packages)

ファイルの探索から字句解析、構文解析そして型チェックを一括で処理してくれる上位APIです。`analysis`パッケージを用いない場合はこのパッケージが解析の起点になると思います。

## Package ssa

[ssa - GoDoc](https://godoc.org/golang.org/x/tools/go/ssa)

静的単一代入(Static Single-Assignment: SSA)形式の中間表現を生成します。これによりコード解析が容易になります。例えば次のようなコードを解析したときに、`str`に代入されうる値が`"Hello, world!"`か `"Hello, 世界!"`のどちらかであることが分かります。こういった複数部分にまたがる解析を実行するにはほぼ必須と言えるでしょう。

```go
func hello(world string) {
    str := "Hello, " + world + "!"
    fmt.Println(str)
}

const DEFAULT_WORLD = "world"

func main() {
    var lang string
    fmt.Scan(&lang)
    if lang == "Japanese" {
        hello("世界")
    } else {
        hello(DEFAULT_WORLD)
    }
}
```

# `analysis`を使わない場合のサンプルコード

`analysis`を使う場合は上記のMercariさんのブログを見れば十分なので、ここでは`packages`を起点にコードを解析するサンプルプログラムを紹介します。
簡単に説明すると、関数とそれを呼び出している関数を見つけてprintしています。`ssa`パッケージを使うと同じことがより簡単かつ正確にできますが、あくまでサンプルとして見ていただければ幸いです。

```go
package main

import "fmt"
import "go/ast"
import "go/types"
import "golang.org/x/tools/go/packages"

func main() {
	dir := "."
	conf := &packages.Config{
		Dir: dir,
		Mode: packages.NeedName |
			packages.NeedFiles |
			packages.NeedImports |
			packages.NeedDeps |
			packages.NeedTypes |
			packages.NeedSyntax |
			packages.NeedTypesInfo,
	}
	pkgs, err := packages.Load(conf)
	if err != nil {
		fmt.Println("failed to parse dir %s: %w", dir, err)
		return
	}
	if packages.PrintErrors(pkgs) > 0 {
		fmt.Println("Some packages have errors")
		return
	}

	for _, pkg := range pkgs {
		for _, file := range pkg.Syntax {
			scope2fn := make(map[*types.Scope]*types.Func)
			// スコープの情報にアクセス
			filescope, _ := pkg.TypesInfo.Scopes[file]
			// 定義情報にアクセス
			for _, obj := range pkg.TypesInfo.Defs {
				fn, ok := obj.(*types.Func)
				if !ok {
					continue
				}
				if fn.Scope().Parent() == filescope {
					// トップレベルの関数定義を集める
					scope2fn[fn.Scope()] = fn
				}
			}
			// ASTを探索
			ast.Inspect(file, func(n ast.Node) bool {
				switch expr := n.(type) {
				case *ast.CallExpr:
					var caller, callee string
					callee = types.ExprString(expr)
					scope := pkg.Types.Scope().Innermost(expr.Pos())
					if scope == nil {
						return true
					}
					// forやif、無名関数のスコープは無視
					for scope.Parent() != nil {
						if fn, ok := scope2fn[scope]; ok {
							caller = fn.Name()
						}
						scope = scope.Parent()
					}
					fmt.Println(caller + " -> " + callee)
				}
				return true
			})
		}
	}
}

```

# まとめ

Goはシンプルな言語仕様のために静的解析がとてもやりやすい言語だと思います。ぜひ皆さんもGoで静的解析に入門しましょう！