chkbuild の diff で unified diff をやめた。
diff は順序に敏感なので、zfs とかで build log 内の順番が不安定だと変化として検出されるのが多すぎる。
以前から、minitest のテスト順とか、不安定なところはいくつかあって個々に対処していたのだが、もう順序はまったく気にしないことにする。(また、同じ行が何行あるかも気にしないことにする)
で、順序に依存しない形式に変えた。
これにより、変更点を抽出するという問題はより簡単になる。
ファイル A, B があったとして、B の各行について、A に同じ行が含まれるかどうか印をつけたい。(また同様に、A の各行について、B に同じ行が含まれるかどうか印をつけたい)
さて、どうするか。
気楽にやるなら、A の各行をハッシュテーブルに登録し、B の各行についてハッシュテーブルを参照すればいい。
しかし、それだと A 全体をメモリに読み込むことになる。A が大きくなりうる状況だと、避けたいところである。
それを避けるにはハッシュテーブルに dbm の類を使う、というのが考えられる。が、Ruby のは、あったりなかったりしたり、制約が強かったり、ちょっと微妙なので使いたくない。それに、激しくランダムアクセスしそうで、なんとなく遅そうな気がする。(測ってないので気のせいかもしれない)
では、ということで、ソートでやってみた。A, B をそれぞれソートして、そのときに元の行番号もつけておく。両方ソート済みであれば、同じ行が含まれるかどうかはシーケンシャルに読むだけで分かるので印をつけられる。そんで、印をつけた後に行番号でソートしなおすと元の順番に戻る。行番号を除去すればできあがり。
ここで、ソートには sort コマンドを使うので、ソートに ruby のメモリ空間は消費しない。そして、sort コマンドはきっとマージソートなので、そっちもそれほど消費しないはずである。たぶん。
図示すると、こんなかんじでデータが流れる。
changes.dot:
digraph g {
a1 [label = "A"]
b1 [label = "B"]
a2 [label = "lnum,line in A\nsorted by lnum"]
b2 [label = "lnum,line in B\nsorted by lnum"]
a3 [label = "lnum,line in A\nsorted by line"]
b3 [label = "lnum,line in B\nsorted by line"]
cmp [label = "compare line and add mark", shape=record]
a4 [label = "lnum,mark,line in A\nsorted by line"]
b4 [label = "lnum,mark,line in B\nsorted by line"]
a5 [label = "lnum,mark,line in A\nsorted by lnum"]
b5 [label = "lnum,mark,line in B\nsorted by lnum"]
a6 [label = "A with mark"]
b6 [label = "B with mark"]
a1->a2 [label="add lnum"]
a2->a3 [label="sort"]
a3->cmp->a4
a4->a5 [label="sort"]
a5->a6 [label="delete lnum"]
b1->b2 [label="add lnum"]
b2->b3 [label="sort"]
b3->cmp->b4
b4->b5 [label="sort"]
b5->b6 [label="delete lnum"]
}
で、それを実現するコードの抜粋が、こうである。
a2 = encode_lines(path_a) a3 = sort_by_content(a2.path) a2.close(true) b2 = encode_lines(path_b) b3 = sort_by_content(b2.path) b2.close(true) a4, b4 = add_mark(a3, b3) a3.close(true) b3.close(true) a5 = sort_by_linenum(a4.path) a4.close(true) b5 = sort_by_linenum(b4.path) b4.close(true)
- ここで呼んでいるだいたいの関数は Tempfile を生成して返す
- ところどころに close(true) とあるのは Tempfile を削除している (ファイルは大きくなるかもしれないという前提なので、いらなくなったら即座に消す。GC は待たない)
思うに、このコードの残念なところは、図に示した構造をプログラムの構文木やインデントという視覚的構造で表現できていないことである。close(true) が邪魔なのもあるが、それがなくてもフラットな構造でよろしくない。
表現したいものが木なのだから、プログラムの木構造でそれを表現できてもいけなくはないはずである。というかそうできるようにどうにかするというのが工夫ではないか。
さて、どうデザインすれば、プログラムの木構造とデータの流れを合わせることができ、また、テンポラリファイルを自動的に (不要になった時点で即座に) 削除できるか。あぁ、データが小さかったらテンポラリファイルからメモリ内で済ます方が良くて、それも自動的にやってほしいという要求もある。