すべての diff は最短経路問題 — Myers アルゴリズムと LCS
あなたがこれまで読んだほぼすべての diff — git diff、GNU diff、下の出力 — は、1986 年のたった一本の論文に由来します。Eugene Myers の "An O(ND) Difference Algorithm and Its Variations" です。この論文が解く問題は最短編集スクリプト(shortest edit script)の探索、つまりテキスト A をテキスト B に変えるために必要な最小の行挿入・削除回数を求めることです。これは数学的には最長共通部分列(LCS)を求める問題と同じです — 両方のテキストに同じ順序で(必ずしも隣接せずに)現れる最長の行の並びです。LCS に含まれる行は変更なしのコンテキストになり、それ以外はすべて赤のマイナスか緑のプラスになります。
Myers は 2 つのテキストを編集グラフ(edit graph)としてモデル化します。右への移動は A から 1 行削除、下への移動は B の 1 行挿入、行が一致する場所ではコストゼロの対角線移動が使えます。最短編集スクリプトは角から角への最も安い経路であり、アルゴリズムはこれを 1 編集ずつ貪欲に探索します。O(ND) という名前が肝心な性質を表しています。N は全体の長さ、D は差分の数なので、テキスト同士が似ているほど — 同じ文書の改訂版という最も一般的なケース — 非常に高速で、2 つの入力がほとんど何も共有しない場合にだけ遅くなります。
知っておくべき機微がひとつ: 最短スクリプトはたいてい一意ではありません。複数の異なる diff がすべて最小編集数を持ちうるため、どれが表示されるかは実装内部のタイブレークに依存します。2 つの diff ツールがどちらも「正しい」のに、同じ入力に対して異なる出力を出すのはこのためです。
old: A B C A B B A new: C B A B A C
LCS: C A B A (longest common subsequence, length 4)
shortest edit script (D = 5 edits):
-A -B C +B A B -B A +C
del del keep ins keep keep del keep ins → C B A B A CPatience diff — 最短の diff が最も読みやすいとは限らない
最適と読みやすさは別物です。Myers は編集回数を最小化しますが、コードは繰り返しの行だらけです — 閉じ波括弧、空行、"end"、"return nil"。アルゴリズムにとってはどれも同一の行なので、新しい関数の閉じ括弧を平然と別の関数の閉じ括弧とマッチさせます。典型的な症状は、既存の関数の上に新しい関数を挿入したとき、2 つの関数の境界がおかしな場所に引かれた diff が出ることです。技術的には最小でも、人間の目には間違っています。
Bram Cohen の patience diff は、ノイズにアンカーを打つことを拒否する方法でこれに対処します。まず両方のファイルに正確に 1 回だけ現れる行 — 関数シグネチャ、特徴的な文 — のみを対象に、その一意なマッチの最長増加部分列を求め(アルゴリズム名の由来であるカードゲーム、patience ソートを使用)、それらをアンカーとして固定し、アンカーの間を再帰的に処理します。波括弧や空行は一意ではないので、偽のアンカーになれません。結果は Myers より編集数が少し多くなることがありますが、人間が見る意味構造と揃います。
同じ発想を git が磨いた histogram diff は、アンカーを(厳密に一意でない)低頻度の行にまで広げ、実践ではより高速です。JGit の既定であり、git config diff.algorithm の人気の選択肢でもあります。移動・重複したコードの diff がぐちゃぐちゃに見えたら、git diff --patience か --histogram を試してください — 同じ入力から劇的に違う物語が得られます。
# Same change, two algorithms
git diff file.py git diff --patience file.py
def totals(): def totals():
return sum(rows) return sum(rows)
+
+def averages(): +def averages():
+ return sum(rows)/n + return sum(rows)/n
+ +
def render(): def render():
# Myers may anchor on the shared 'return sum(rows)' line and
# split the new function across the old one; patience anchors
# on the unique 'def' lines and keeps each function intact.行・単語・文字 — 適切な粒度を選ぶ
行ベースの diff が既定なのは、コードが行単位で変わるからでもあり、安上がりだからでもあります。行全体をハッシュ化すれば、高価なアルゴリズムが走る前に各ファイルは短いトークン列に縮みます。しかし行の粒度には盲点があります — 300 文字の行の 1 文字を変えただけで、diff はその行全体を削除+追加として報告し、どこが違うかは目で探すはめになります。
コードレビューツールが使う解決策は 2 パスの diff です。行レベルのパスでどの行が変わったかを特定し、削除/追加された行のペアごとにだけ文字または単語レベルのパスを走らせてインラインハイライトを作ります。ファイル全体に文字単位の diff を直接かけるのは割に合いません — 編集グラフは入力長の二乗で成長し、無関係な行同士の 1 文字のアラインメントは洞察ではなくノイズを生みます。git は単語レベルのビューを git diff --word-diff(トークン出力)と --color-words(インライン着色)として提供しており、「1 行」が実質段落である散文・Markdown・翻訳文で重宝します。
第三の軸は構造です。2 つの JSON 文書は意味的に同一でもテキストとしては異なりえます — キーの順序、インデント、末尾カンマ。生の JSON のテキスト diff は、ほとんどフォーマットを測っているだけです。堅牢なワークフローは先に正規化すること: 両方の文書を同じフォーマッタ(安定したキー順、固定インデント)に通してから diff します。SQL、XML、異なるツールで整形されたコードにも同じ手が使えますし、コードにはフォーマットを完全に無視する difftastic のような AST レベルの differ もあります。diff の意味は、その前に行った正規化の分だけしかありません。
空白・改行コード・見えない差分
最も混乱する diff は、両側がまったく同じに見える diff です。一番よくある犯人は改行コード。Windows のツールは CRLF(\r\n)を、Unix は LF を書き込むため、間違った OS で一度保存されたファイルは全行が変更として表示されます。git の防御策は core.autocrlf、さらに良いのは明示的な eol ルールを書いてコミットした .gitattributes で、チーム全体が同じ正規化をするようになります。生の diff 出力では、紛れ込んだキャリッジリターンは行末の ^M として現れます。
第二の一族は行末スペースとタブ対スペースのインデントです。これらを抑える標準フラグがあります: diff -b は空白量の変化を無視、diff -w は空白を完全に無視、git diff は -w、-b、--ignore-blank-lines をサポートします。これらは調査用の道具であって修正ではありません — 空白ノイズが diff を汚すなら、永遠に -w で diff するのではなく、フォーマッタと .editorconfig でソースを直しましょう。Python や YAML では、その「ノイズ」が本物の意味変化かもしれないのです。
第三の一族は Unicode です。Web ページから貼り付けたノーブレークスペース(U+00A0)、ゼロ幅スペース(U+200B)、ファイル先頭のバイト順マーク(U+FEFF)は、見た目は普通の文字と同じままミスマッチを引き起こします。同様に、アクセント付き文字は 1 コードポイント(NFC)のことも、基底文字+結合記号(NFD)のこともあります — macOS のファイル API が NFD を生むのは有名です。差が見えない行を diff が指したら、目を信じるのをやめて両方の行を hexdump してください。答えはいつもバイトの中にあります。
# Both lines render as "hello" — the bytes disagree
$ printf 'hello \n' | xxd # trailing space: ...6f 20 0a
$ printf 'hello\r\n' | xxd # CRLF ending: ...6f 0d 0a
# Ignore whitespace while investigating
git diff -w # all whitespace
git diff -b --ignore-blank-lines # amount + blank lines
# Normalize line endings for the whole team (.gitattributes)
* text=auto
*.sh text eol=lfUnified diff 出力をネイティブのように読む
unified フォーマット — GNU diffutils のために発明され、git が採用して以来普遍的になった形式 — は、少数の記号に多くの情報を詰め込みます。@@ -117,6 +117,8 @@ のようなハンク(hunk)ヘッダはこう読みます: このハンクは元ファイルの 117 行目から 6 行、新バージョンの 117 行目から 8 行をカバーする。この行数には変更なしのコンテキスト行(既定で上下各 3 行、-U で調整可能)が含まれます。置換された行はマイナス 1 つ+プラス 1 つなので、追加数から削除数を引いた値は常に 2 つの行数の差と等しくなります — パッチを手で編集するときの手軽な検算です。
つまずきやすいマーカーが 2 つあります。2 つ目の @@ の後のテキストは diff の一部ではなく、位置把握のために示される、その箇所を囲む関数やセクションの見出しです。また "\ No newline at end of file" という行は実際の内容ではなく、直前の行に末尾改行がないことを示すフラグです。ファイル末尾に改行を 1 つ足しただけで 2 行分の diff が出るのはこのためです。
ハンクが分かればパッチ適用の謎も解けます。patch や git apply は行番号を盲信しません。記載位置の近くでコンテキスト行を検索し、ファイルがずれていればオフセット付きで、コンテキストが部分一致なら fuzz 付きで適用します — 先週のファイルに対して書かれたパッチが今日でも当たるのはこの仕組みです。コンテキストがマージで重要な理由でもあります。3-way マージの衝突(<<<<<<< / ======= / >>>>>>>)は、まさに同じコンテキスト領域が異なる 2 つのハンクを受け取ったケースであり、git の diff3 スタイル(merge.conflictStyle = diff3)はマーカーの間に共通祖先を追加して、双方が何から何へ変えたのかを見せてくれます。
@@ -117,6 +117,8 @@ function render() {
const rows = fetchRows(); ← context (3 lines above)
const total = sum(rows);
- return format(total); ← removed from old file
+ const avg = total / rows.length;
+ return format(total, avg); ← added in new file
}
// counts: old 6 = 3+1+2 ctx, new 8 = 3+2+2 ctx +1
\ No newline at end of file