はじめに

この記事はGo5 Advent Calendar 2019 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のブログが参考になる
とにかく動かしたい、基礎を理解したい → 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

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

このパッケージに関してはGoにおける静的解析のモジュール化について - Mercari Engineering Blogが非常によくまとまっていて分かりやすいので一読をおすすめします。

Package ast/astutil

astutil - GoDoc

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

Package ast/inspector

inspector - GoDoc

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

Package callgraph

callgraph - GoDoc

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

Package cfg

cfg - GoDoc

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

Package packages

packages - GoDoc

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

Package ssa

ssa - GoDoc

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

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パッケージを使うと同じことがより簡単かつ正確にできますが、あくまでサンプルとして見ていただければ幸いです。

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で静的解析に入門しましょう！