deadcodeで到達不能な関数を見つける

Finding unreachable functions with deadcode by Alan Donovan

プロジェクトのソースコードの一部ではあるものの、どの実行パスをたどってもけっして到達できない関数のことを 「デッドコード」と呼びます。デッドコードはコードベースの保守作業の足を引っ張る存在です。 今日は、そうした関数を見つけ出すための deadcode という新しいツールを紹介します。

$ go install golang.org/x/tools/cmd/deadcode@latest
$ deadcode -help
The deadcode command reports unreachable functions in Go programs.

Usage: deadcode [flags] package...

例

ここ1年ほど、VS Codeなどのエディタを支えるGoの言語サーバーである goplsの構造に対して、私たちは数多くの変更を加えてきました。 典型的な変更では、既存の関数を書き換える際に、その新しい振る舞いが既存の呼び出し元すべての要求を 満たすように注意を払います。しかし時には、そこまで手間をかけたにもかかわらず、 呼び出し元の一つがそもそもどの実行でも到達していなかった、つまり安全に削除できたはずだと気づき、 がっかりすることがありました。これを前もって知っていれば、リファクタリング作業はもっと楽だったはずです。

この問題を示す単純なGoプログラムが次のものです。

module example.com/greet
go 1.21

package main

import "fmt"

func main() {
    var g Greeter
    g = Helloer{}
    g.Greet()
}

type Greeter interface{ Greet() }

type Helloer struct{}
type Goodbyer struct{}

var _ Greeter = Helloer{}  // Helloer  implements Greeter
var _ Greeter = Goodbyer{} // Goodbyer implements Greeter

func (Helloer) Greet()  { hello() }
func (Goodbyer) Greet() { goodbye() }

func hello()   { fmt.Println("hello") }
func goodbye() { fmt.Println("goodbye") }

このプログラムを実行すると、helloと表示されます。

$ go run .
hello

出力を見れば、このプログラムが hello 関数を実行し、 goodbye 関数は実行していないことは明らかです。 しかし一見してわかりにくいのは、 goodbye 関数がけっして呼び出されえないという点です。 とはいえ、単純に goodbye を削除するわけにはいきません。なぜなら goodbye は Goodbyer.Greet メソッドから必要とされており、さらにそのメソッドは Greeter インターフェースを実装するために必要で、 そのインターフェースの Greet メソッドが main から呼び出されているのが見て取れるからです。 ただし main から前方向にたどっていくと、 Goodbyer の値はどこでも生成されていないことがわかります。 したがって main 内の Greet の呼び出しは Helloer.Greet にしか到達しえません。 これが deadcode ツールが使っているアルゴリズムの背後にある考え方です。

このプログラムに対して deadcode を実行すると、 goodbye 関数と Goodbyer.Greet メソッドの 両方が到達不能であることが報告されます。

$ deadcode .
greet.go:23: unreachable func: goodbye
greet.go:20: unreachable func: Goodbyer.Greet

この情報があれば、この2つの関数、そして Goodbyer 型そのものも安全に削除できます。

このツールは、 hello 関数がなぜ生存しているのかも説明できます。 main を起点として hello に到達する関数呼び出しの連鎖を返してくれます。

$ deadcode -whylive=example.com/greet.hello .
                  example.com/greet.main
dynamic@L0008 --> example.com/greet.Helloer.Greet
 static@L0019 --> example.com/greet.hello

この出力はターミナル上で読みやすいように設計されていますが、 -json フラグや -f=template フラグを使えば、他のツールで利用するためのより詳細な出力形式を指定できます。

仕組み

deadcode コマンドは、指定されたパッケージを 読み込み、 パースし、 型検査したうえで、 一般的なコンパイラが用いるものに似た 中間表現に変換します。

そして Rapid Type Analysis（RTA） というアルゴリズムを使って、到達可能な関数の集合を構築していきます。この集合は最初、 それぞれの main パッケージのエントリーポイントである main 関数と、 グローバル変数への代入や init という名前の関数の呼び出しを行うパッケージ初期化関数だけを含んでいます。

RTAは到達可能と判定された各関数の本体にある文を調べ、次の3種類の情報を収集します。 その関数が直接呼び出す関数の集合、インターフェースのメソッド経由で行う動的呼び出しの集合、 そしてインターフェースへ変換する型の集合です。

直接の関数呼び出しは簡単です。呼び出し先を到達可能な関数の集合に追加するだけで、 もしそれが初めて出会った呼び出し先であれば、 main のときと同様にその関数本体を調べます。

インターフェースのメソッドを介した動的呼び出しはより厄介です。そのインターフェースを実装している型の 集合がわからないからです。型がマッチするというだけでプログラム中のすべてのメソッドを、その呼び出しの 潜在的な対象だと仮定するわけにはいきません。なぜなら、そうした型の中にはデッドコードからしか インスタンス化されないものもありうるからです。だからこそ、インターフェースに変換される型の集合を 収集するのです。その変換によって、それぞれの型が main から到達可能になり、その結果、 その型のメソッドが動的呼び出しの対象になりうるようになります。

これは鶏と卵のような状況を生みます。到達可能な関数を新たに発見するたびに、より多くの インターフェースメソッド呼び出しと、具象型からインターフェース型への変換が見つかります。 そして、この2つの集合の直積（インターフェースメソッド呼び出し×具象型）がどんどん大きくなるにつれて、 新たに到達可能な関数が見つかります。この種の問題は「動的計画法」と呼ばれ、 （概念的には）大きな2次元の表にチェックマークをつけながら、行と列を必要に応じて追加していき、 これ以上追加するチェックがなくなるまで続けることで解けます。最終的な表の中のチェックマークが 到達可能なものを示し、空白のセルがデッドコードということになります。

main 関数によって Helloer がインスタンス化され、g.Greet の呼び出しは、これまでに インスタンス化された各型の Greet メソッドへとディスパッチされます。

（メソッドではない）関数への動的呼び出しは、単一のメソッドを持つインターフェースと同様の扱いを受けます。 そしてreflectionを使った呼び出しは、インターフェースへの 変換で使われた型、あるいは reflect パッケージを使ってそこから導出できる型の、任意のメソッドに 到達しうるものとして扱われます。しかし原理はすべての場合で同じです。

テスト

RTAはプログラム全体を対象にした解析です。つまり、常に main 関数を起点として前方向に処理を進めます。 encoding/json のようなライブラリパッケージを起点にすることはできません。

しかし、ほとんどのライブラリパッケージにはテストがあり、テストには main 関数があります。 これは go test の裏側で生成されるため普段は目にしませんが、 -test フラグを使えばそれを解析に 含められます。

これによってライブラリパッケージ内のある関数がデッドコードだと報告された場合、それはテストカバレッジを 改善できる余地があるという兆候です。たとえば、次のコマンドは encoding/json のテストのどれからも 到達しない、 encoding/json 内のすべての関数を列挙します。

$ deadcode -test -filter=encoding/json encoding/json
encoding/json/decode.go:150:31: unreachable func: UnmarshalFieldError.Error
encoding/json/encode.go:225:28: unreachable func: InvalidUTF8Error.Error

（-filter フラグは、出力を正規表現にマッチするパッケージに絞り込みます。デフォルトでは、 このツールは初期モジュール内のすべてのパッケージを報告します。）

健全性

すべての静的解析ツールは、対象プログラムが取りうる動的な振る舞いについて、 必然的に不完全な近似しか生み出せません。 あるツールの前提や推論は「健全」（sound）、すなわち保守的だが場合によっては過度に慎重、 であることもあれば、「不健全」（unsound）、すなわち楽観的だが必ずしも正しいとは限らない、 であることもあります。

deadcode ツールも例外ではありません。関数値やインターフェース値、あるいはreflectionを介した 動的呼び出しの対象の集合を近似する必要があります。この点において、このツールは健全です。 言い換えると、もしある関数をデッドコードとして報告した場合、それはこうした動的な仕組みを通しても その関数を呼び出せないということを意味します。ただしこのツールは、実際にはけっして実行されえない 関数の一部を報告し損なうことがあります。

deadcode ツールは、Go以外の言語で書かれた関数からの呼び出しの集合についても近似する必要があります。 これはツールから見えないためです。この点において、このツールは健全ではありません。 このツールの解析は、アセンブリコードから排他的に呼び出される関数や、 go:linkname ディレクティブによって 生じる関数のエイリアスについては認識しません。幸いなことに、これらの機能はGoランタイムの外で 使われることはほとんどありません。

試してみる

私たちは、特にリファクタリング作業のあとに、プログラム中でもう不要になった部分を特定する助けとして、 自分たちのプロジェクトに対して定期的に deadcode を実行しています。

デッドコードを弔ったあとは、寿命を迎えているのに頑なに生き続け、生命力を吸い取り続けるような コードを排除することに集中できます。私たちはこうしたアンデッドな関数を「バンパイアコード」と 呼んでいます。

ぜひ試してみてください。

$ go install golang.org/x/tools/cmd/deadcode@latest

私たちはこのツールを役立つと感じています。皆さんにもそう感じていただければ幸いです。

By Alan Donovan