読者です 読者をやめる 読者になる 読者になる

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のソースコードと翻訳ドキュメントを公開してくれている方々に感謝。

Mercurialのextdiffツールを自作する

このエントリーはMercurial Advent Calendar 2013の4日目です。

概要

Mac環境のdiffツールで満足な行内差分を得ることができなかったので、extdiff用のツールを自作しました。
個人的な要件として、日本語のプレーンテキストの差分を見たいのですが、これを満たすツールがMacだと意外とありません。マルチバイト文字と行の折り返しで躓くことが多いです。

環境

ソースコード

Bitbucketで公開しています。
cudiff.py

解説

まずは.hgrcにプログラムを登録します。

[extdiff]
cmd.cudiff = /your/directory/cudiff.py

コマンドラインでhg cudiffと打ち込むとcudiff.pyが実行されます。

プログラムには引数が二つ渡されます。比較対象となるファイル(またはディレクトリ)のパスです。
Mercurial側で比較対象のファイルを一時ディレクトリに生成してくれるので、ツール側はそのパスを引数として受け取り、普通にファイルの内容を比較すればいいようになっています。
引数は絶対パスだったり相対パスだったりします。カレントディレクトリが一時ディレクトリに移動しているので、そこからの相対パスとして処理できなければなりません。
複数ファイルを比較する場合、必要なファイルだけが入った一時ディレクトリが2つ生成されて、そのディレクトリのパスが引数となります。
hg cudiffのオプションはMercurial側で解釈されます。たとえばhg cudiff -c 9999とした場合、リビジョン9999とそのparentを比較するための一時ディレクトリが生成され、プログラムにはそのパスが渡されます。

cudiff.pyの説明に移りましょう。

比較処理はdiffコマンドにブン投げました。

proc = subprocess.Popen(['diff', '-r', '-u', sys.argv[1], sys.argv[2]])

-rオプションで、ディレクトリを再帰的に比較します。
-uオプションでunified diff形式で出力します。

サブプロセスの標準出力を受け取り、一行一行解析してside-by-side形式で表示するHTMLを組み立てていきます。このあたりは自前で実装しました。

行内差分の抽出は以下のようにします。

class CUDiffer:
    def compare(self, a, b):
        sm = difflib.SequenceMatcher(None, a, b)
        for tag, a1,a2, b1,b2 in sm.get_opcodes():
            if   tag == 'delete':
            elif tag == 'insert':
            elif tag == 'replace':
            elif tag == 'equal':

Python標準ライブラリのdifflibDiffer.compare()メソッドを基にしています。Python本体ソースコードLib/difflib.pyにあります。
SequenceMatcherで文字列a,bの行内差分の位置を取得して、<span>タグで囲ってCSSで色を付けます。
今回、プログラムを作成する言語はどれを選んでもよかったのですが、このdifflib目当てでPythonに決めました。

生成したHTMLをテンポラリファイルに書き出して、Webブラウザで開きます。

temp_file = tempfile.mkstemp()
webbrowser.open('file://' + temp_file[1])
os.remove(temp_file[1])

裏でファイルを削除してコマンドは終了します。
ユーザーの操作はコマンド入力とブラウザのタブを閉じることだけです。

表示はこのようになります。

f:id:toruot:20131204225025p:plain

試してみたdiffツール

既存のツールもあれこれ試しましたが、しっくりくるものはありませんでした。

SourceTree

http://www.sourcetreeapp.com/
行内差分は見られません。同じAtlassianのBitbucketならWeb上で行内差分が見られるのですが、この扱いの差は一体。

FileMerge.app

[extdiff]
cmd.odiff = opendiff

opendiffコマンドで、MacのXcodeに標準で付属しているFileMerge.appを起動させることができます。
なかなかいいのですが、マルチバイト文字の行内差分表示がズレることがあるのが難です。
また、ファイルに非ascii文字があると確認ダイアログが出ます。これは抑制することができないようで、非常に鬱陶しいです。

PyCharm

[extdiff]
cmd.pdiff = /Applications/PyCharm CE.app/Contents/MacOS/pycharm
opts.pdiff = diff

Python IDEのPyCharmは、コマンドラインからdiffツールとして呼び出すことが可能です。
Running PyCharm as a Diff or Merge Command Line Tool
行内差分も出るのですが、スペース区切りで判断しているようで、日本語の文章が一単語と見なされるのが難です。
また、カレントディレクトリを考慮しないらしく、extdiffからの引数が相対パスだと、ファイルが見つからずエラーになります。
PyCharmを起動した状態で実行しないと、コマンドライン上にエラーが出ます。一応動きますが注意が必要です。

vimdiff

[extdiff]
cmd.vimdiff = vimdiff

Macだとはじめから入っているvimですが、diffツールとして使えるとは知りませんでした。
起動時にnowrapになるため、~/.vimrcに以下を記述します。

au FilterWritePre * if &diff | set wrap | endif

行内差分の表示はかなりいいのですが、折り返して物理行数に差がでると、左右のペインがズレていくのが難です。

docdiff

[extdiff]
cmd.docdiff = docdiff
opts.docdiff = --utf8 --lf --digest --format=tty --display=multi

Rubyで書かれたdiffツールです。
http://hisashim.org/2011/02/23/docdiff-040.html
差分抽出はいいのですが、結果の表示が好みでないので避けていました。Rubyを書けばいろいろできるはずですが、先にcudiffができてしまいました。

wdiff, dwdiff

[extdiff]
cmd.wdiff = wdiff
cmd.dwdiff = dwdiff
opts.dwdiff = -c -C4 -d "、。「」\n"

diffコマンドの親戚のようなものです。Homebrewで入れて試しました。
日本語の文章が一単語とみなされるのが難です。dwdiffで、-Pしてみたり、-dで改行文字などを追加すると、少しはよくなりますが。

kdiff3

[extdiff]
cmd.kdiff = /Applications/kdiff3.app/Contents/MacOS/kdiff3

何が不満だったか確かめようと思い実行したら、エラーで動きませんでした。

p4merge

[extdiff]
cmd.fdiff = /Applications/p4merge.app/Contents/MacOS/p4merge

マルチバイト文字の扱いに難があります。

diffc

[extdiff]
cmd.cdiff = /your/directory/diffc

Pythonで書かれたdiffツールです。
http://code.google.com/p/diffc/
文字化けしてしまいました。

その他のdiffツール

WinMerge

[extdiff]
cmd.wdiff = C:\Program Files\WinMerge\WinMergeU.exe
opts.wdiff = /r

会社はWindows環境なのでWinMergeを使っています。Mac版もあればいいんですどねえ。

Kaleidoscope

http://www.kaleidoscopeapp.com/
有償のツールは試してないのですが、これは良さそうですね。バージョン管理システムとの連携機能が組み込まれているようです。

終わりに

普段使いのツールを自分で書くというのは久しぶりで、とても楽しかったです。MercurialPythonに感謝。

明日の担当は flyingfoozy さんです。

2013/12/08(日)追記

ちょっと改良しました。
Mercurialのextdiffツールを改良する

Unified Diff に色を付ける Python スクリプト

バックアップ代わりに。

cudiff.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-

# cudiff - Coloring Unified DIFF
# 標準入力から unified diff を受け取って色を付ける

import sys
import difflib

import codecs
sys.stdin  = codecs.getreader('utf_8')(sys.stdin)
sys.stdout = codecs.getwriter('utf_8')(sys.stdout)

class TermColor:
    BG_RED     = "\x1b[41m"  # BackGround
    BG_GREEN   = "\x1b[42m"
    BG_YELLOW  = "\x1b[43m"
    BG_BLUE    = "\x1b[44m"
    BG_MAGENTA = "\x1b[45m"
    BG_CYAN    = "\x1b[46m"
    BG_WHITE   = "\x1b[47m"
    FG_BLACK   = "\x1b[30m"  # ForeGround
    FG_RED     = "\x1b[31m"
    FG_GREEN   = "\x1b[32m"
    FG_BLUE    = "\x1b[34m"
    FG_MAGENTA = "\x1b[35m"
    FG_CYAN    = "\x1b[36m"
    FG_WHITE   = "\x1b[37m"
    DEFAULT    = "\x1b[0m"   # DEFAULT

class CUDiffer:  # difflib.Differクラス参照
    def __init__(self):
        self.set_mode_terminal()
        # lf.set_mode_html()

    def set_mode_terminal(self):
        # Embedded text {DELete, INSert, REPlace, EQUal, TERMination}
        self.e_del_a = TermColor.BG_RED     + TermColor.FG_WHITE
        self.e_ins_b = TermColor.BG_MAGENTA + TermColor.FG_WHITE
        self.e_rep_a = TermColor.BG_RED     + TermColor.FG_WHITE
        self.e_rep_b = TermColor.BG_MAGENTA + TermColor.FG_WHITE
        self.e_equ_a = TermColor.BG_WHITE   + TermColor.FG_BLACK
        self.e_equ_b = TermColor.BG_WHITE   + TermColor.FG_BLACK
        self.e_term  = TermColor.DEFAULT

    def compare(self, a, b):
        r_a = ""  # Result A
        r_b = ""  # Result B

        sm = difflib.SequenceMatcher(None, a, b)
        for tag, a1,a2, b1,b2 in sm.get_opcodes():
            if   tag == 'delete':
                r_a += self.e_del_a + a[a1:a2] + self.e_term
            elif tag == 'insert':
                r_b += self.e_ins_b + b[b1:b2] + self.e_term
            elif tag == 'replace':
                r_a += self.e_rep_a + a[a1:a2] + self.e_term
                r_b += self.e_rep_b + b[b1:b2] + self.e_term
            elif tag == 'equal':
                r_a += self.e_equ_a + a[a1:a2] + self.e_term
                r_b += self.e_equ_b + b[b1:b2] + self.e_term
            else:
                raise ValueError('unknown tag %r' % (tag,))

        return (r_a, r_b)

class Liner:
    def __init__(self):
        self.differ = CUDiffer()
        self.buff_old = []
        self.buff_new = []
        self.output = ""
    
    def do(self, line):
        ignore = (line.find('+++ ', 0,4) >= 0 or 
                  line.find('--- ', 0,4) >= 0 )
        # TODO 行の先頭が"++ "だった場合に誤判定する。
        if   line.find('-', 0,1) == 0 and not ignore:
            self.buff_old.append(line)
        elif line.find('+', 0,1) == 0 and not ignore:
            self.buff_new.append(line)
        else:
            self.clear_buffer()
            self.output += line

    def clear_buffer(self):
        buff_len_old = len(self.buff_old)
        buff_len_new = len(self.buff_new)
        if buff_len_old == 0 and buff_len_new == 0:
            return
        buff_len = buff_len_old if buff_len_old > buff_len_new else buff_len_new

        outputs_old = ""
        outputs_new = ""
        for i in range(buff_len):
            i_o = self.buff_old[i] if i < buff_len_old else ''
            i_n = self.buff_new[i] if i < buff_len_new else ''

            (o_o, o_n) = self.differ.compare(i_o, i_n)
            outputs_old += o_o
            outputs_new += o_n

        self.buff_old = []
        self.buff_new = []

        self.output += outputs_old + outputs_new

def main():
    liner = Liner()
    for line in sys.stdin:
        liner.do(line)
    liner.clear_buffer()
    print liner.output

main()

MercurialとSubversionのメンタルモデルの違い

このエントリは Mercurial Advent Calendar 2012 の17日目です。


SubversionからDVCSへの乗り換えを勧める言説は数多くありますが、以前の私はどれを読んでもピンと来ませんでした。なるほど利点はいろいろあるのだろうけど、そこまでクリティカルなのかな、と。
しかし自分でMercurialを触るようになると、「確かにこれはSubversionには戻れない」と感じるようになりました。
この感覚はどこから来るのか。思うに、それはバージョン管理のモデルの違いです。
私がSubversionを使う際のメンタルモデルは「ディレクトリツリー」です。一方、Mercurialを使う際のメンタルモデルは「リビジョングラフ」です。本来、この二つのモデルに優劣はないでしょうが、ことバージョン管理においてはリビジョングラフの方が都合がよいのです。


Subversionリポジトリの中にディレクトリツリーがあります。
トランクは /trunk というディレクトリのことであり、ブランチは /branches/topicA, /branches/topicB といったディレクトリのことです。これはシステムによって規定されるわけではなく、標準的な構成として広く知られている、いわば「お約束」です。
ブランチやタグの作成とはすなわちディレクトリのコピーです。これもシステムに認識されるわけではなく、「/trunkを/branches/下にコピーして開発を進めるのがブランチである」、「/tags/下にコピーして、以後編集しないものがタグである」といったお約束があるだけです。
なお、ここで言うディレクトリツリーとは、バージョン管理対象となっているファイル・ディレクトリのツリーとは異なる概念です。(ただし、シームレスにつながっています。ブランチやタグを作るのと同じコマンドで、任意のサブディレクトリ(たとえば/trunk/foo/bar)をコピーすることも可能です。)

Subversionでも、TortoiseSVNなどのツールを使えばリビジョングラフを見ることができます。しかし、ディレクトリツリーをもとにグラフを作っているために、Mercurialを知った今にして思えば物足りないところがあります。
たとえば、リビジョングラフの分岐はありますが、合流がありません。そのままではマージしたブランチの履歴をたどることができないため、ファイル・ディレクトリに付属する属性情報にmergeinfoを書き込んでいます。
もうひとつ、ブランチを作成した時点でリビジョングラフが分岐してしまいます。このため、ファイル単位でリビジョングラフを見ると、ブランチ内で一度も更新されてないのに分岐していて不自然です。
Subversionのディレクトリツリーが、ブランチを扱うのに向いてないことの査証といえるでしょう。

リポジトリのクローンが複数あり、それぞれに独立したコミットが追加されたとして、それを統合することを考えてみましょう。
Mercurialでは、マルチプルヘッドが増えることを厭わなければ機械的に統合が可能です。
Subversionは機械的な統合ができません。リポジトリ全体で一意なリビジョン番号を持っており、別のクローンから来たコミットを置く場所がありません。事前にマージしてどちらかを棄却しなければ統合は不可能です。単一のコミットならばどうにかなるかもしれませんが、コミット群だったりブランチができていたりマージされていたりすると、絶望的に面倒でしょう。
Subversionが集中型なのはもともとそれを意図して作られたからというのもあると思いますが、ディレクトリツリーでは分散型に対応できないからである、という面もあると思います。


全てはつながっています。ディレクトリツリーであること、マージがやりにくいこと、集中型であること。リビジョングラフであること、マージがやりやすいこと、分散型であること。
総じてリビジョングラフの方がバージョン管理にふさわしいメンタルモデルであり、ディレクトリツリーによる制約や回り道から解放されると感じます。

(ただ、ディレクトリツリーの利点として、普段使っているファイルシステムのメンタルモデルを流用できるので始めるコストが低い、というのはあるかもしれません。Mercurialは、リビジョングラフという、ファイルシステムとは関係のないメンタルモデルを一から構築する必要があるため、学習コストが比較的高い気がします。)

私はバージョン管理システムをそれほどハードに使っているわけではなく、Subversionでもマージ地獄にハマったりした経験はありません。それでもMercurialの方がバージョン管理をキメてる爽快感があって好きです。