> Source: https://www.ymotongpoo.com/works/goblog-ja/deadcode/ # deadcodeで到達不能な関数を見つける [Finding unreachable functions with deadcode](https://go.dev/blog/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](https://go.dev/blog/gopls-scalability)の構造に対して、私たちは数多くの変更を加えてきました。 典型的な変更では、既存の関数を書き換える際に、その新しい振る舞いが既存の呼び出し元すべての要求を 満たすように注意を払います。しかし時には、そこまで手間をかけたにもかかわらず、 呼び出し元の一つがそもそもどの実行でも到達していなかった、つまり安全に削除できたはずだと気づき、 がっかりすることがありました。これを前もって知っていれば、リファクタリング作業はもっと楽だったはずです。 この問題を示す単純なGoプログラムが次のものです。 ```go module example.com/greet go 1.21 ``` ```go 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` コマンドは、指定されたパッケージを [読み込み](https://pkg.go.dev/golang.org/x/tools/go/packages)、 [パース](https://pkg.go.dev/go/parser)し、 [型検査](https://pkg.go.dev/go/types)したうえで、 一般的なコンパイラが用いるものに似た [中間表現](https://pkg.go.dev/golang.org/x/tools/go/ssa)に変換します。 そして [Rapid Type Analysis](https://pkg.go.dev/golang.org/x/tools/go/callgraph/rta)（RTA） というアルゴリズムを使って、到達可能な関数の集合を構築していきます。この集合は最初、 それぞれの `main` パッケージのエントリーポイントである `main` 関数と、 グローバル変数への代入や `init` という名前の関数の呼び出しを行うパッケージ初期化関数だけを含んでいます。 RTAは到達可能と判定された各関数の本体にある文を調べ、次の3種類の情報を収集します。 その関数が直接呼び出す関数の集合、インターフェースのメソッド経由で行う動的呼び出しの集合、 そしてインターフェースへ変換する型の集合です。 直接の関数呼び出しは簡単です。呼び出し先を到達可能な関数の集合に追加するだけで、 もしそれが初めて出会った呼び出し先であれば、 `main` のときと同様にその関数本体を調べます。 インターフェースのメソッドを介した動的呼び出しはより厄介です。そのインターフェースを実装している型の 集合がわからないからです。型がマッチするというだけでプログラム中のすべてのメソッドを、その呼び出しの 潜在的な対象だと仮定するわけにはいきません。なぜなら、そうした型の中にはデッドコードからしか インスタンス化されないものもありうるからです。だからこそ、インターフェースに変換される型の集合を 収集するのです。その変換によって、それぞれの型が `main` から到達可能になり、その結果、 その型のメソッドが動的呼び出しの対象になりうるようになります。 これは鶏と卵のような状況を生みます。到達可能な関数を新たに発見するたびに、より多くの インターフェースメソッド呼び出しと、具象型からインターフェース型への変換が見つかります。 そして、この2つの集合の直積（インターフェースメソッド呼び出し×具象型）がどんどん大きくなるにつれて、 新たに到達可能な関数が見つかります。この種の問題は「動的計画法」と呼ばれ、 （概念的には）大きな2次元の表にチェックマークをつけながら、行と列を必要に応じて追加していき、 これ以上追加するチェックがなくなるまで続けることで解けます。最終的な表の中のチェックマークが 到達可能なものを示し、空白のセルがデッドコードということになります。 ![illustration of Rapid Type Analysis](./deadcode_rta.svg) *`main` 関数によって `Helloer` がインスタンス化され、`g.Greet` の呼び出しは、これまでに インスタンス化された各型の `Greet` メソッドへとディスパッチされます。* （メソッドではない）関数への動的呼び出しは、単一のメソッドを持つインターフェースと同様の扱いを受けます。 そして[reflectionを使った](https://pkg.go.dev/reflect#Value.Call)呼び出しは、インターフェースへの 変換で使われた型、あるいは `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` フラグは、出力を正規表現にマッチするパッケージに絞り込みます。デフォルトでは、 このツールは初期モジュール内のすべてのパッケージを報告します。） ## 健全性 すべての静的解析ツールは、対象プログラムが取りうる動的な振る舞いについて、 [必然的に](https://en.wikipedia.org/wiki/Rice%27s_theorem)不完全な近似しか生み出せません。 あるツールの前提や推論は「健全」（sound）、すなわち保守的だが場合によっては過度に慎重、 であることもあれば、「不健全」（unsound）、すなわち楽観的だが必ずしも正しいとは限らない、 であることもあります。 `deadcode` ツールも例外ではありません。関数値やインターフェース値、あるいはreflectionを介した 動的呼び出しの対象の集合を近似する必要があります。この点において、このツールは健全です。 言い換えると、もしある関数をデッドコードとして報告した場合、それはこうした動的な仕組みを通しても その関数を呼び出せないということを意味します。ただしこのツールは、実際にはけっして実行されえない 関数の一部を報告し損なうことがあります。 `deadcode` ツールは、Go以外の言語で書かれた関数からの呼び出しの集合についても近似する必要があります。 これはツールから見えないためです。この点において、このツールは健全ではありません。 このツールの解析は、アセンブリコードから排他的に呼び出される関数や、 [`go:linkname` ディレクティブ](https://pkg.go.dev/cmd/compile#hdr-Compiler_Directives)によって 生じる関数のエイリアスについては認識しません。幸いなことに、これらの機能はGoランタイムの外で 使われることはほとんどありません。 ## 試してみる 私たちは、特にリファクタリング作業のあとに、プログラム中でもう不要になった部分を特定する助けとして、 自分たちのプロジェクトに対して定期的に `deadcode` を実行しています。 デッドコードを弔ったあとは、寿命を迎えているのに頑なに生き続け、生命力を吸い取り続けるような コードを排除することに集中できます。私たちはこうしたアンデッドな関数を「バンパイアコード」と 呼んでいます。 ぜひ試してみてください。 ``` $ go install golang.org/x/tools/cmd/deadcode@latest ``` 私たちはこのツールを役立つと感じています。皆さんにもそう感じていただければ幸いです。 By Alan Donovan