java-ja温泉

 もう先週のことになるけどhttp://java-ja.yoshiori.org/index.php?%E7%AC%AC%E5%8D%81%E4%B8%89%E5%9B%9Eにいってきた。

 自分は現地までバイクでツーリング。往復で900kmぐらい。最近走っていなかったから大分ツーリング欲が満たされた感じ。現地では和服姿で過ごしてました。和服いいよ、和服。

プログラムしてたもの

 自分は構文解析型のdiffツールを作ろうとしていて、java-ja温泉ではその基礎研究を進めてた。

 diffのアルゴリズムについては•¶‘”äŠridiffjƒAƒ‹ƒSƒŠƒYƒ€あたりを参考にしているのだけど、抽象構文木のような木構造の比較だといくらか工夫がいる。階層ごとにわけて比較する手*1もあるんだけど、例えばソースの一部をtry-catchで囲ったりした場合に階層が変わってマッチしなくなるようだと嬉しくない。

 とりあえず、木構造を深さ優先で走査して、配列のようなデータ構造に変換してからdiffをとるという手法を部分適用することでそこそこうまく比較をとれそうだ。無名クラスとかあるから、もうちょっと処理は複雑になると思うけども。

 配列的なデータ構造といえばIteratorだろう、ということでランダムアクセス可能な配列ではなく、シーケンシャルな読み込みをするItaratorで効率よく処理できるdiffのアルゴリズムがないかとか考えて挫折。抽象構文木の走査はVisitorパターンでやるのだけど、VisitorをItaratorに変換する手法とかまで考案したのにどうも没っぽい。

 まぁいいや。このへんは疎結合に設計しておけばあとからチューニングは容易にできるからとりあえずは機能性の実現を優先してまず作ってしまえばいいんだよ。そう割り切ることができたのが収穫と言えば収穫。

抽象構文木とか

 抽象構文木の作成はSunのJDKのtools.jarに収録されているCompiler Tree APIを利用している。これだとopenSUSEの標準搭載のJava開発環境だと使えないという罠が。Eclipseにもこの手の機能があるようだからそれを使う方がいいのだろうか。情報が少なくてよく分からないのだけど。

 んで、Compiler Tree APIの抽象構文木を操作する場合はTreeVisitorってのを実装するわけなんだけど実装しないといけない抽象メソッドが50近くあってかなり大変。

 構文要素ごとにさらに配下の構文要素にaccept()しないといけないのだけど、それが構文要素ごとに違うわけで、これだけの数を個別に対処するのか、うへーって感じ。難易度的な難しさはないのだけど、実装には結構時間がかかりそう。とりあえず、最小限の実装だけやってそれで実験していた。

今後の見通し

 そんなわけでプロトタイプのプロトタイプぐらいの粗末な代物ができたのだけど、GUIとかないので比較結果を確認するのも一苦労。あぁそうだ。GUIがいるんだよ。欲を言えばEclipseプラグインにしたいのだけど、これまた大変そうだなぁ。

 そもそも構文解析を伴うdiffを作ったとしてどうやって図示すればいいんだろう?GUIのプログラム特有の大変さもあるにはあるけど、どちらかというとどんな感じにプレゼンするのって方が苦しい。

 とはいえ、とっかかりの動くものが作れたのはよかった。ちゃんと一歩踏み出せた感じ。早いところ公開できるところにまでこぎつけたいものだね。

*1:文章比較の場合は行単位の比較をまずやって、それから1行の文字列同士を比較するような2階層diffがよく行われている。木構造の場合、木の階層ごとにdiffをとる手もある。