Mercurialのextdiffツールを改良する

先日、自作のextdiffツールcudiffを公開しました。
Mercurialのextdiffツールを自作する - Mercurial Advent Calendar 2013

これにはひとつ心残りがありました。行内差分を比較するペアの決定方法が単純で、関係ない行を比較してしまうことです。
たとえば行の追加と行の変更が続くと、以下のように残念なことになります。

f:id:toruot:20131208202125p:plain

比較しているペアは、
['aaa','aaaa'],['bbb','xxxx'],[ None,'bbbb']となっています。ここは、
['aaa','aaaa'],[ None,'xxxx'],['bbb','bbbb']となってほしいところです。

difflibのドキュメントをぼんやり眺めていたら、ndiffがまさに期待する通りに動作していました。
6.3. difflib — 差分の計算を助ける — Python 3.3 documentation

>>> diff = difflib.ndiff(["aaa" ,       "bbb" ],
...                      ["aaaa","xxxx","bbbb"])
>>> for line in diff:
...     print(line)
- aaa
+ aaaa
?    +
+ xxxx
- bbb
+ bbbb
?    +

さっそくdifflibのソースコードLib/difflib.pyを見ると、以下のようになっていました。

def ndiff(a, b):
    return Differ().compare(a, b)

class Differ:
    def compare(self, a, b):
        cruncher = SequenceMatcher(a, b)

SequenceMatcherは文字列を引数にとるものだと思っていたので、配列を入れていることに面食らったのですが、考えてみれば文字列とは「文字の配列」でもあるわけで、文字列の比較ができるなら「文字列の配列」の比較もできるわけですね。

Differクラスを読んだところ、Differ.compare()で行レベルの比較をして、変更のある行についてはDiffer._fancy_replace()で文字レベルの比較をしている、ということがわかりました。
_fancy_replaceには、どの行とどの行を比較するかペアを決めるアルゴリズムがあり、この機能を組み込むため移植することにしました。
行レベルの差分はdiffコマンドに丸投げしているので、compareの処理は特に必要ありません。

ちなみに、difflibにはもともとside-by-side形式のHTMLを出力する機能があるのですが、ソースコードを見たところ嫌な予感がしたので再利用するのは避けました。
処理の流れは軽くしか追ってないのですが、HtmlDiffはndiffの出力結果をわざわざパースしています。

class HtmlDiff:
    def make_table(self,fromlines,tolines):
        diffs = _mdiff(fromlines,tolines)
        # diffsを解析する長い処理...

def _mdiff(fromlines, tolines):
    diff_lines_iterator = ndiff(fromlines,tolines)
    # diff_lines_iteratorを解析する長い処理...

ndiffはDifferを使い、DifferはSequenceMatcherの解析データをもとに出力文字列を生成しています。SequenceMatcherの解析データを直接利用すれば、Differの出力する文字列を解析する手間はかからないわけです。
まあ、unified diffをわざわざパースするプログラム書いてる私が言うのもなんですが。

移植にあたり、_fancy_replacecutoffの値を変えました。
この値が高すぎると、行内差分が見たいのにまるごと置き換わったことになってしまいますし、低すぎると、内容はまったく関係の無い行なのに句読点が一致しているといった意味のない行内差分を見せられることになります。
もともと0.75なのですが、高すぎると感じたので0.59にしてみました。difflibのドキュメントには「経験によると、ratio() の値が0.6を超えると、シーケンスがよく似ていることを示します」とあります。

移植は成功し、めでたく気の利いたdiffが見れるようになりました。

f:id:toruot:20131208202143p:plain

変更したソースコードはBitbucketで公開しています。
cudiff.py

difflibのソースコードと翻訳ドキュメントを公開してくれている方々に感謝。