This page looks best with JavaScript enabled

「Goの静的解析ツール開発」を支える技術

 ·   ·  ☕ 10 min read  ·  ✍️ さんぽし

はじめに

タイトル大きく出過ぎたかな…と本編を書く前から感じてます。さんぽしです

最近、先日のインターンをきっかけにGo の静的解析ツールの開発を行っています。

これは「えっ、静的解析ツール開発って難しくない?」「どうやって作ったの?」という記事です

  • Go の静的解析ツール開発の流れ
  • 具体的に開発した Go の静的解析ツールを元に解説

という流れで進めていきます。

いくつかの静的解析ツールを作成しましたが、今回は以下の wastedassign という静的解析ツールを例にしていきます

sanposhiho / wastedassign

そもそもどういうツールなの

題材にする静的解析ツールを軽く紹介します

wastedassign は無駄な代入を発見してくれる静的解析ツールです。

wastedassignでは主に

  • 代入されたけど return までその代入された値が使用されることはなかった
  • 代入されたけど代入された値が用いられることなく、別の値に変更された

と言った二種類の無駄な代入を検出します。

Golang は完全な未使用変数は教えてくれるけど、「定義されてから一度使われている変数に対する再代入&その後未使用なもの」は教えてくれないよね。というモチベです

以下サンプルです

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 という静的解析ツールの雛形を用意してくれる便利ライブラリがあります。

gostaticanalysis / 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 になります、少し内容を覗いてみます

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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には以下のファイルが入っています

1
2
3
4
5
6
7
8
9
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

テストは落ちます、理由はテストファイルに

1
	var gopher int // want "pattern"

となっている行があるからですね

1
	var gopher int // want "identifier is gopher"

このように書き直すことでテストを通すことができます

$ go test
PASS
ok  	github.com/sanposhiho/sample	0.303s

実際に skeleton を元にした静的解析ツールを開発する際は

  • sample.goをいじる
  • go testを回してみる

を繰り返して開発していくことになります

他のファイルはほとんど触らずに開発が進められるので、skeleton に感謝です

「ソースコードから不要な代入を発見する静的解析ツール」を支える技術

ここから実際に開発した静的解析ツールの仕組みに触れていきます

sanposhiho / wastedassign

ソースコードから †完全に理解した† 状態になるには、先に前述の資料を読み、尚且つ僕のクソコードを読み解く読解力が必要になります。
なのでここではざっくりと雰囲気で説明していきます。

再三の説明になりますが、このツールが発見する対象は

  • 代入されたけど return までその代入された値が使用されることはなかった
  • 代入されたけど代入された値が用いられることなく、別の値に変更された

の二種類です。

ツールでは主に 静的単一代入形式(ssa) での解析を行いました

大まかな流れとしては以下の仕組みになります

  • ssa.Storeの命令を探す
  • 見つかった箇所から飛びうる Block へその変数が次に使用される箇所を探す
    1. 遷移の可能性がある Block のいずれかで使用されている場合、必要な代入である
    2. 遷移の可能性があるどの Block でも使用されることなく再代入されている場合、不要な代入であるである
    3. 遷移の可能性があるどの Block でも使用されることなく関数が終了(return)する場合、不要な代入である

急に難しくなりましたね、これらのパターンに関しては後半に図を用いた説明があるのでさらっと読み飛ばして頂いて構いません。

用語を簡単に補足します

ssa.Store の命令

ssa パッケージの型の内の 1 つですごく噛み砕くと変数への代入です(ここでいう変数は実際にソースコードに定義されている変数とは異なり、詳しくは前述の資料を…)

Block

image.png

Wikipediaより引用

上記のようなグラフでソースコードを扱っていると考えるとわかりやすいです。Block は↑でいうところのそれぞれの四角形です

具体的に実装を覗いてみよう

説明に戻り、上記の大まかな流れがどのように実装されているかをみていきます

ここからの説明は以下のソースコード全体を閲覧した方がわかりやすいと思います

sanposhiho / wastedassign

ssa.Storeの命令を探す

こちらはシンプルにループと type-switch を使用して探していきます
該当のコードは以下です

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 に渡して再帰的に調べる

ここからは以下の条件に別れます

  1. 遷移の可能性がある Block のいずれかで使用されている場合、必要な代入である
  2. 遷移の可能性があるどの Block でも使用されることなく再代入されている場合、不要な代入である
  3. 遷移の可能性があるどの Block でも使用されることなく関数が終了(return)する場合、不要な代入である
1. いずれかで使用

図で表現すると以下のようになります

wasted (1).png

この場合は t0 に対する store 命令は必要なため報告の対象になりません

2. 再代入されてる

図で表現すると以下のようになります

wasted (2).png

この場合はどのルートを通っても使用されることはなく再代入が発生しているので不要な代入であると報告されます

3. どこでも使用されず関数が終了

図で表現すると以下のようになります

wasted (3).png

return まで探索しても t0 は使用されないため、不要な代入であると報告されます

※「あれ、Go って使われないのに代入されていたらエラー出してくれなかったっけ?」と思われた方もいるかと思いますが、以下のような再代入の場合には Go は教えてくれません

wasted (4).png

コーナーケースへの対応が大変

Go はある程度シンプルな言語だとは思いますが、いくつかのコーナーケースが見つかり、一筋縄では行きませんでした

具体的には以下のコーナーケースに対応しました

  • for ループ内に別のブロックが存在すると無限に探索してしまう(→ 対応PR
  • type-switch では内部実装的に確実に wastedassign が避けられない(→ 対応PR

終わりに

Go に標準で備わる静的解析に関する豊富なライブラリに加えて Skeleton を用いるとかなり簡単に静的解析ツールを行える

後半は少しややこしい実装の話になってしまいました。
実際のコードを覗くと少し難しく見えるかもしれないですが、本質的には再帰でフィールドを追っているだけであり、リファレンスなどを覗きながら実装をやってみるとかなり簡単に開発が行えることに気が付く…はず!です!

静的解析ツールって敷居高く見えるけどそんなことないやん!となれば嬉しいです

記事内で何か間違っているところなりありましたらコメントや Twitter でそっと優しく教えてください

役立つサイト集

「プログラミング言語Go完全入門」の「完全」公開のお知らせ
→ こちらの 14 章が静的解析の回になります

goパッケージで簡単に静的解析して世界を広げよう #golang

GoAst Viewer
→ wastedassign ではメインでは使用しませんでしたが、Go のコードを入力すると、対応する抽象構文木(AST)を確認できます

Go SSA Viewer
→ 上記の SSA 版になります

[番外編]紹介しなかった別の静的解析ツール

以下番外編です

sanposhiho / easydebug

静的解析ツールというよりは静的解析を利用したツールというのが正しいかもしれません
ツイートにあるように変数の代入文の後にその変数をデバックする関数を入れてくれるというツールです。

軽く仕組みを紹介

かなりシンプルな仕組みです。
こちらは SSA 形式ではなく AST の形式で解析を行いました。

wastedassign と似たような感じで変数の代入文を探して、その次の行にデバックの関数を差し込むという処理になります。

なぜSSAではなくAST?

  • SSA までの解析を必要としなかった
  • AST だと、format.Nodeを使用してさくっと AST→ソースコードの変換ができる

と言った理由でした

Share on

さんぽし
WRITTEN BY
さんぽし
Web Developer /w Elixir, Go