Kengo's blog

Technical articles about original projects, JVM, Static Analysis and TypeScript.

処理の流れに関連したFindBugsプラグインを作る

端午节3連休中に調べたことのメモ。たぶんこれで@WillCloseと@WilCloseWhenClosedをサポートするdetectorが実装できるはず。


資源が確実に開放されるかを調べるDetectorを実装するときなど、ありうる処理の流れを列挙してその全てに対して正しい処理が行われるかを確認したいことがある。例えば

Closeable resource = load();
try {
  use(resource);
  use2(resource);
} finally {
  resource.close();
}

というコードの場合、取りうる処理の流れは何通りかある。

  1. load()が例外を投げる
  2. use()が例外を投げる
  3. use2()が例外を投げる
  4. use()が例外を投げ、close()も例外を投げる
  5. use2()が例外を投げ、close()も例外を投げる
  6. すべての処理が正しく流れる

f:id:eller:20130612104435p:plain

これらすべての流れにおいて、資源が開放されるか(close()が実行されるか)を確認したい。FindBugsプラグインではCFGDetectorを継承する形でDetectorを実装することによりこれを実現できる。

以下、自分が突っかかった点の解説を試みる。

FactとTop&Bottomについて

Factとは特定時点での事実を表すための可変オブジェクトで、DataflowならびにDataflowAnalysisが用いる。control pathが合流するところで2つのFactがmeetして(演算されて)新しいFactになる。

Topは何とmeetしても相手そのものになる値。乗算における1。Bottomは何とmeetしてもBottomになる値。乗算における0。AbstractDataflowAnalysis#isValidFactのjavadocによると、TopとBottomはinvalidな値であるという。Factがinvalidだと、AbstractDataflowAnalysis#transferが実行されない、つまり#transferInstructionも呼び出されないので注意。

AbstractDataflowAnalysisのサブクラスを作るなら、このクラスの動作とinvalidの定義を理解するためにAbstractDataflowAnalysis#transferのコードはひと通り読んでおいたほうがいい。DataflowAnalysis#transferのJavadocも。

Bottomは「もうダメだ」を表すのに使えそう。例えば2つのpathのうち1つにバグがあると判明しているなら合流後のpathもバグを持つことになり、すなわちこの「バグがある」ことを表すFactはBottomとして振る舞うことになる。Topは「まだ初期化されてない」とか?

上記PDFに格子(lattice)との説明があるように、Top→validな値→Bottomという上から下への状態遷移とvalidな値同士の横方向の状態遷移があり、格子を形成している。……とは言っても、この表現に実用上の意味はないと思われる。

AbstractDataflowAnalysis#transferInstructionとDataflowAnalysis#transfer

前者が細かくinstructionすなわちバイトコードごとに処理を走らせるためのもの、後者が粗くBasicBlockごとに処理を走らせるためのもの。後者にどういうニーズがあるのかちょっと不明。

DetectorとDataflowAnalysisの住み分けについて

DataflowAnalysisとFactで状態を管理してDetectorが判断を下す、というのがシンプルっぽい。上記PDFのサンプルにある通り、DataflowAnalysisからFactにアクセスすることも可能なので、境界線はわりと曖昧。DataflowAnalysisやFactを複数のDetectorから共用するという想定を持つこと、BugReporterは基本的にDetectorだけが持つこと、の2つをルールとして持つと責務を考えやすいかも。あと、おそらく、DetectorがFactを直接更新することは想定されていない(上記PDFでは参照だけだった)。

なおfinishPassメソッド内ではFactに触る手段がないので、必要に応じてDetectorのフィールドにバグレポートを作るための情報を突っ込んでおく必要がある。あるいはtransferInstructionの中でさっさとバグレポートを上げるようにする。

TODO

  • AbstractDataflowAnalysis#getFactAtLocationの理解、というかBasicAbstractDataflowAnalysis#getStartFactがなんで再帰的に前のBasicBlockを辿らないでいいんだろうという疑問。
    • BasicBlockの理解が曖昧かもしれない。
      • 今の理解はBasicBlock=分岐に挟まれた処理の単位(上記グラフで言うノード)。BasicBlock#isJSRSubroutineの存在を考えると、確かに違うかもしれない(Subroutineが複数のBlockに別れることを想定するならisInJSRSubroutineとか名づけそう)。メソッドやサブルーチンひとつがBasicBlock?
      • メソッドやサブルーチンがBasicBlockなら、Edgeの定義がさっぱりわからなくなるので根本的に理解を確認し直すこと。今の理解が正しいなら、各BasicBlockごとにFactを計算しておいてあとでmeetさせるという話になるので、この辺りのロジックを読めば決着は付くだろう。
    • CFGに@see BasicBlock @see Edgeとあるので、BasicBlockはEdgeとともにCFGを構成する要素であることは確実。
    • ついでにEdgeの意味も再確認すること。今のところ分岐を伴うバイトコード呼び出しのことだろうという理解。
    • そもそも、なんでgetStartFactとgetResultFactの実装が同じなんだろう……?
  • loopをどう解析するのかよくわかってない。
    • 例えば資源を複数回開放しないことを明確にするなら、どう解析する?
  • makeFactTopメソッドの存在から、TopはFactにつきひとつだけだと思われるが、Bottomは複数あってもいいのだろうか?
    • 「もうダメだ」にも種類があるはず(誰も閉じてない or 2回以上閉じてる)
    • 調べたいものが複数あるならDetectorも複数にしろという主張は通りそう
  • 演算(meet)をひとつ持つ値の集合とか、格子というより群論っぽいです……
    • 単位元(Top)はあるけど逆元はないので、違うはず
    • 結合則は成り立っているのだろうか?
    • 格子論という(私にとって)未知の学問があるのかもしれない→あった!が、違う気がする。

ひょんなところでLLVMっぽさ(Blockが遷移先を複数持つとか)が出てきて面白かった。やっぱこの界隈はこういう構造をこねくりまわすのがいい。