はじめに
タイトル大きく出過ぎたかな…と本編を書く前から感じてます。さんぽしです
最近、先日のインターンをきっかけにGo の静的解析ツールの開発を行っています。
これは「えっ、静的解析ツール開発って難しくない？」「どうやって作ったの？」という記事です
- Go の静的解析ツール開発の流れ
- 具体的に開発した Go の静的解析ツールを元に解説
という流れで進めていきます。
いくつかの静的解析ツールを作成しましたが、今回は以下の wastedassign という静的解析ツールを例にしていきます
そもそもどういうツールなの
題材にする静的解析ツールを軽く紹介します
wastedassign は無駄な代入を発見してくれる静的解析ツールです。
wastedassignでは主に
- 代入されたけど return までその代入された値が使用されることはなかった
- 代入されたけど代入された値が用いられることなく、別の値に変更された
と言った二種類の無駄な代入を検出します。
Golang は完全な未使用変数は教えてくれるけど、「定義されてから一度使われている変数に対する再代入&その後未使用なもの」は教えてくれないよね。というモチベです
以下サンプルです
package a
func f() {
useOutOfIf := 0 // "wasted assignment"
err := doHoge()
if err != nil {
useOutOfIf = 10 // "reassigned, but never used afterwards"
return
}
err = doFuga() // "reassigned, but never used afterwards"
useOutOfIf = 12
println(useOutOfIf)
return
}コメントのように、このコードに対しては 3 回ツールによる警告が行われます。
- 1 つ目はどのルートを通っても
useOutOfIfがもう一度定義されるので 1 行目で定義する必要性がない - 2 つ目は
useOutOfIfに対して再代入が行われているが、その後すぐに return されているので再代入の必要性がない - 3 つ目は
doHoge()の返り値として受け取った変数errを使いまわしてdoFuga()のエラーを受け取っているが、その後使用されていないので再代入の必要性がない
以下のようなケースに役立ちます
- 無駄な代入文を省くことによる可読性アップ
- 無駄な再代入を検出することによる使用忘れの確認
前者に関しては必ずしも可読性がアップするかというと議論の余地はあるかもしれませんが、個人的には使用しないのであればブランク変数で受け取るなりした方が読む方としては明示的に使わないということがわかり、読みやすいと思います。
また、使用しないことが明示的にわかることで、
- なぜ使用しないのか
- 関数の返り値として返す必要がそもそもないのではないか（上記 Sample で言うと、doFuga()はそもそもエラーを返す必要がないのではないか
などの議論が生まれるきっかけとなることを期待します
Go の静的解析について
と言ったツールの宣伝はさておき…
他の言語の静的解析事情に詳しいわけではないですが、Go は静的解析の環境がかなり充実しています。
詳しくはインターンでも使用された資料(14 章)や、インターンで講師を務めていただいた@tenntenn さんの以下の記事をみるのが早いです（丸投げ go パッケージで簡単に静的解析して世界を広げよう #golang
そのためかなり静的解析ツールを作成する敷居は低いです。 本当に簡単なものを雑に作るだけであれば後述のskeletonを用いれば 1 時間もかからないと思います
skeleton を使用した静的解析ツールの開発の流れ
やっと本題です
そう言った Go の充実したライブラリ達を用いて具体的にどのように実装して行ったのかを説明しつつ、Go における静的解析ツールの開発の流れを紹介します
skeleton という静的解析ツールの雛形を用意してくれる便利ライブラリがあります。
README を見てもらうのが正確ですが
$ skeleton sample
sample
├── cmd
│ └── sample
│ └── main.go
├── go.mod
├── sample.go
├── sample_test.go
├── plugin
│ └── main.go
└── testdata
└── src
└── a
├── a.go
└── go.modこのようにツールの雛形を作成してくれます
実際に静的解析のコードを書いていくのは以下の sample.go になります、少し内容を覗いてみます
package sample
import (
"go/ast"
"golang.org/x/tools/go/analysis"
"golang.org/x/tools/go/analysis/passes/inspect"
"golang.org/x/tools/go/ast/inspector"
)
const doc = "sample is ..."
// Analyzer is ...
var Analyzer = &analysis.Analyzer{
Name: "sample",
Doc: doc,
Run: run,
Requires: []*analysis.Analyzer{
inspect.Analyzer,
},
}
func run(pass *analysis.Pass) (interface{}, error) {
inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
nodeFilter := []ast.Node{
(*ast.Ident)(nil),
}
inspect.Preorder(nodeFilter, func(n ast.Node) {
switch n := n.(type) {
case *ast.Ident:
if n.Name == "gopher" {
pass.Reportf(n.Pos(), "identifier is gopher")
}
}
})
return nil, nil
}skeleton によって作成されるテンプレートでははじめに「gophorという変数が使用されている箇所を見つける静的解析のコード」が入っています
また、testdata/src/a/a.goには以下のファイルが入っています
package a
func f() {
// The pattern can be written in regular expression.
var gopher int // want "pattern"
print(gopher) // want "identifier is gopher"
}こちらはテストで静的解析の対象となるファイルです コメントで
// The pattern can be written in regular expression.とあるように、静的解析ツールの出力を期待する文字列を want "pattern" という形で記述できます
試しにテストを回してみましょう、skeleton で生成されたコードは何もいじらずともテストが回るようになっています
$ go test
--- FAIL: TestAnalyzer (0.03s)
analysistest.go:419: a/a.go:5:6: diagnostic "identifier is gopher" does not match pattern "pattern"
analysistest.go:483: a/a.go:5: no diagnostic was reported matching "pattern"
FAIL
exit status 1
FAIL github.com/sanposhiho/sample 0.437sテストは落ちます、理由はテストファイルに
var gopher int // want "pattern"となっている行があるからですね
var gopher int // want "identifier is gopher"このように書き直すことでテストを通すことができます
$ go test
PASS
ok github.com/sanposhiho/sample 0.303s実際に skeleton を元にした静的解析ツールを開発する際は
sample.goをいじるgo testを回してみる
を繰り返して開発していくことになります
他のファイルはほとんど触らずに開発が進められるので、skeleton に感謝です
「ソースコードから不要な代入を発見する静的解析ツール」を支える技術
ここから実際に開発した静的解析ツールの仕組みに触れていきます
ソースコードから †完全に理解した† 状態になるには、先に前述の資料を読み、尚且つ僕のクソコードを読み解く読解力が必要になります。 なのでここではざっくりと雰囲気で説明していきます。
再三の説明になりますが、このツールが発見する対象は
- 代入されたけど return までその代入された値が使用されることはなかった
- 代入されたけど代入された値が用いられることなく、別の値に変更された
の二種類です。
ツールでは主に 静的単一代入形式（ssa） での解析を行いました
大まかな流れとしては以下の仕組みになります
ssa.Storeの命令を探す-
見つかった箇所から飛びうる Block へその変数が次に使用される箇所を探す
- 遷移の可能性がある Block のいずれかで使用されている場合、必要な代入である
- 遷移の可能性があるどの Block でも使用されることなく再代入されている場合、不要な代入であるである
- 遷移の可能性があるどの Block でも使用されることなく関数が終了（return)する場合、不要な代入である
急に難しくなりましたね、これらのパターンに関しては後半に図を用いた説明があるのでさらっと読み飛ばして頂いて構いません。
用語を簡単に補足します
ssa.Store の命令
ssa パッケージの型の内の 1 つですごく噛み砕くと変数への代入です（ここでいう変数は実際にソースコードに定義されている変数とは異なり、詳しくは前述の資料を…）
Block
Wikipediaより引用
上記のようなグラフでソースコードを扱っていると考えるとわかりやすいです。Block は ↑ でいうところのそれぞれの四角形です
具体的に実装を覗いてみよう
説明に戻り、上記の大まかな流れがどのように実装されているかをみていきます
ここからの説明は以下のソースコード全体を閲覧した方がわかりやすいと思います
ssa.Store の命令を探す
こちらはシンプルにループと type-switch を使用して探していきます 該当のコードは以下です
for _, sf := range s.SrcFuncs {
for _, bl := range sf.Blocks {
blCopy := *bl
for _, ist := range bl.Instrs {
blCopy.Instrs = rmInstrFromInstrs(blCopy.Instrs, ist)
switch ist.(type) {
case *ssa.Store:
var buf [10]*ssa.Value
for _, op := range ist.Operands(buf[:0]) {
if (*op) != nil && opInLocals(sf.Locals, op) {
if reason := isNextOperationToOpIsStore([]*ssa.BasicBlock{&blCopy}, op, nil); reason != notWasted {
if ist.Pos() != 0 && !typeSwitchPos[pass.Fset.Position(ist.Pos()).Line] {
wastedAssignMap = append(wastedAssignMap, wastedAssignStruct{
pos: ist.Pos(),
reason: reason.String(),
})
}
}
}
}
}
}
}
}for 文がネストしまくってます。
最終的にブロックの Instrs を type-switch して *ssa.Store を探していることがわかります
細かい処理を説明していると長くなるので色々省略し、isNextOperationToOpIsStoreが次の見つかった箇所から飛びうる Block へその変数が次に使用される箇所を探すを行う関数です
見つかった箇所から飛びうる Block へその変数が次に使用される箇所を探す
isNextOperationToOpIsStoreの目的は
- 見つかった箇所から飛びうる Block へその変数が次に使用される箇所を探す
- 探した結果に応じて適切な
wastedReasonを返す
です
大まかにこの関数の流れを説明します
- bls で渡ってきた Block を 1 つ 1 つ見ていき、指定の変数(Store 命令が発生していた変数)に対する命令を探す
- その Block 内に命令がなかった場合はその Block の遷移先の Block（
bl.Succs）をisNextOperationToOpIsStoreに渡して再帰的に調べる
ここからは以下の条件に別れます
- 遷移の可能性がある Block のいずれかで使用されている場合、必要な代入である
- 遷移の可能性があるどの Block でも使用されることなく再代入されている場合、不要な代入である
- 遷移の可能性があるどの Block でも使用されることなく関数が終了（return)する場合、不要な代入である
1. いずれかで使用
図で表現すると以下のようになります
この場合は t0 に対する store 命令は必要なため報告の対象になりません
2. 再代入されてる
図で表現すると以下のようになります
この場合はどのルートを通っても使用されることはなく再代入が発生しているので不要な代入であると報告されます
3. どこでも使用されず関数が終了
図で表現すると以下のようになります
return まで探索しても t0 は使用されないため、不要な代入であると報告されます
※「あれ、Go って使われないのに代入されていたらエラー出してくれなかったっけ？」と思われた方もいるかと思いますが、以下のような再代入の場合には Go は教えてくれません
コーナーケースへの対応が大変
Go はある程度シンプルな言語だとは思いますが、いくつかのコーナーケースが見つかり、一筋縄では行きませんでした
具体的には以下のコーナーケースに対応しました
終わりに
Go に標準で備わる静的解析に関する豊富なライブラリに加えて Skeleton を用いるとかなり簡単に静的解析ツールを行える
後半は少しややこしい実装の話になってしまいました。 実際のコードを覗くと少し難しく見えるかもしれないですが、本質的には再帰でフィールドを追っているだけであり、リファレンスなどを覗きながら実装をやってみるとかなり簡単に開発が行えることに気が付く…はず！です！
静的解析ツールって敷居高く見えるけどそんなことないやん！となれば嬉しいです
記事内で何か間違っているところなりありましたらコメントや Twitter でそっと優しく教えてください
役立つサイト集
「プログラミング言語 Go 完全入門」の「完全」公開のお知らせ → こちらの 14 章が静的解析の回になります
go パッケージで簡単に静的解析して世界を広げよう #golang
GoAst Viewer → wastedassign ではメインでは使用しませんでしたが、Go のコードを入力すると、対応する抽象構文木（AST）を確認できます
Go SSA Viewer → 上記の SSA 版になります
[番外編]紹介しなかった別の静的解析ツール
以下番外編です
Golangのソースに対して、さくっとデバッグ文を追加してくれるツールを公開しましたhttps://t.co/fdL3Vl2PEn
— さんぽし (@sanpo_shiho) September 5, 2020
全ての変数への代入文の後にデバッグ用の文が追加され、追加した全てのデバック文の削除も行うことができます#mercari_intern pic.twitter.com/x39JXzRUiy
静的解析ツールというよりは静的解析を利用したツールというのが正しいかもしれません ツイートにあるように変数の代入文の後にその変数をデバックする関数を入れてくれるというツールです。
軽く仕組みを紹介
かなりシンプルな仕組みです。 こちらは SSA 形式ではなく AST の形式で解析を行いました。
wastedassign と似たような感じで変数の代入文を探して、その次の行にデバックの関数を差し込むという処理になります。
なぜ SSA ではなく AST？
- SSA までの解析を必要としなかった
- AST だと、
format.Nodeを使用してさくっと AST→ ソースコードの変換ができる
と言った理由でした
