Diff

diffは、ファイルの比較を行うためのコマンドで2つのファイル間の違いを出力できるプログラム。diffプログラムは行単位でテキストファイル間の差異を表示する。最近の実装ではバイナリファイルもサポートしている。プログラムからの出力も「diff」と呼ばれるが出力をそのままpatchプログラムで適用できるため、「patch」との呼称も一般的である。また、diffコマンド以外からの出力であっても差分表示プログラムの出力はdiffと呼ばれることがある。"grep"が文字列探索そのものの代名詞になっているように、"diff"という語も差分検出一般を指すジャーゴンとなっている。

1. 歴史
-----

diffプログラムは1970年代初頭に、ニュージャージー州マーレイ・ヒルにあったAT&Tのベル研究所で開発されたUNIX上で開発されたもので、1974年のUNIX第5版に同梱され最初に公開された最終バージョンはダグラス・マキルロイが開発したものであった。このバージョンのdiff実装については1976年にdiffの初期のプロトタイプ実装を行ったジェームズ・W・ハントとの共著による論文の中で研究成果として発表された。

マキロイの研究はスティーブ・ジョンソンによるGCOS上の比較プログラムやマイク・レスクによるproofプログラムの先行する研究の影響を受けたものだった。proofは元々UNIX上で開発されdiffのような行単位の変更箇所を出力するもので、行の挿入・削除を示すのにブラケットによる出力も用いられていた。これらの初期のアプリケーションではヒューリスティクスが使われていたが、その出力の安定性は低いものだった。ファイル比較ツールの潜在的な有用性に触発されたマキロイはより頑健で様々な対象に使用でき、かつPDP-11のハードウェア的な制約上でもうまく動作するようなツールの研究、設計に取り組んだ。このアプローチによる研究にはベル研の同僚であったアルフレッド・エイホ、エリオット・ピンソン、ジェファーソン・ウルマン、ハロルド・S・ストーンの研究者らとの協力を受けて取り組んだ。

Unixにおいては、edラインエディタの利用が「編集スクリプト」機能という概念と自然に結びつくようなdiff機能を提供することとなった。edによる編集スクリプトと元ファイルとを両方保存しておけば、edコマンドだけで変更後のファイルを完全に再構成できることになる。これを利用することによりファイルの複数改版履歴を保存するのに必要なディスク容量を相当減らすことができる。マキロイは元々様々な形式で出力できるようなdiffを作りその出力を処理できるようなポストプロセッサを作ろうと考えていたが、文法そのものをdiff形式として規定してしまい、さらにedコマンドが解釈できるような逆順入力に対応するようなdiffコマンドを実装する方がずっと単純で楽にできると判断した。1985年にはラリー・ウォールがこのdiff出力を入力として受け取ってファイルを変更するというアイデアを一般化、拡張して別コマンドとしてpatchを作成した。

diffが作られてしばらくは、ソフトウェアコードや技術文書のマークアップのソース部分の変更箇所を比較する、プログラムのデバッグ出力の検証、ファイルシステム中のファイル一覧の比較といった使い方が一般的であった。ed用の出力により、ファイルへの一連の変更をひとまとめにしてファイル容量を節約するというアイデアが出てきた。Source Code Control Systemはそのようなアイデアを実装したものとして1970年代後半に実装がなされた。

diffは概念的にはザナドゥ計画の思想を受けたものである。Xanaduは1960年に出現したハイパーテキストプロジェクトでその「相互参照ウィンドウ」機能に必要な履歴版の管理・追跡という概念を示していた。ファイルの相違点の提示はこの機能の一部としてより広い用語「トランスクルージョン」に含まれていた。トランスクルージョンとはある文書が他の文書もしくは他の版の一部の中に含まれることを指す。

電子化時代の人文科学においては、コンピュータによる比較ツールは過去に大部で出版された文学作品に対しても用いられている。

2. 使用法
------

以下のようにコマンドラインで2つのファイル名を指定して実行する。 diff //original// //new// コマンドからの出力はファイル //original// をファイル //new// に変更するのに必要な箇所を示す。

//original// と //new// がディレクトリを指していた場合diffは両ディレクトリに存在するファイル個々について実行されることになる。オプション-rを指定するとさらにサブディレクトリ以下を全て辿りディレクトリ内のファイル間についての差分を出力する。

3. 利用例
------

以下、2つのファイルを例に説明する://original//:1 This part of the2 document has stayed the3 same from version to4 version. It shouldn't5 be shown if it doesn't6 change. Otherwise, that7 would not be helping to8 compress the size of the9 changes.1011 This paragraph contains12 text that is outdated.13 It will be deleted in the14 near future.1516 It is important to spell17 check this dokument. On18 the other hand, a19 misspelled word isn't20 the end of the world.21 Nothing in the rest of22 this paragraph needs to23 be changed. Things can24 be added after it.//new//:1 This is an important2 notice! It should3 therefore be located at4 the beginning of this5 document!67 This part of the8 document has stayed the9 same from version to10 version. It shouldn't11 be shown if it doesn't12 change. Otherwise, that13 would not be helping to14 compress anything.15
16 It is important to spell17 check this document. On18 the other hand, a19 misspelled word isn't20 the end of the world.21 Nothing in the rest of22 this paragraph needs to23 be changed. Things can24 be added after it.2526 This paragraph contains27 important new additions28 to this document.

コマンド diff original new を実行すると、以下の通常のdiff出力が生成される:

0a1,6 > This is an important > notice! It should > therefore be located at > the beginning of this > document! > 8,14c14 < compress the size of the < changes. < < This paragraph contains < text that is outdated. < It will be deleted in the < near future.

---> compress anything. 17c17 < check this dokument. On

---> check this document. On 24c24,28 < be added after it.

---> be added after it. > > This paragraph contains > important new additions > to this document.

<WtXmlEndTag />

この伝統的な出力形式では、a は追加、d は削除、c は変更を意味する。a/d/cの各文字の前には元ファイルでの行番号が書かれ、後ろに変更後ファイルでの行番号が出力される。行頭の山括弧はその行が追加されたのか、または削除されたのかを示している。追加行とは新しいファイルで新たに出現した部分、つまり元のファイルに付け加えられた部分のことで、削除行は新しいファイルでは無くなった、つまり元ファイルから除かれた行のことを指す。

標準では新旧両ファイルに共通する箇所は出力されない。行を移動した場合は新しい場所へは追記として示され、以前の箇所では削除行として示される。

4. 変種
-----

大半のdiff実装の仕様は1975年以来ほとんど変わらずにそのままである。主な変更点としてはコアアルゴリズムの改良、コマンドとして便利な機能の追加、新出力形式の設計がある。基本的なアルゴリズムは論文 "An O Difference Algorithm and its Variations"および "A File Comparison Program" で説明されている。このアルゴリズムはこれとは別に独立してE.ウッコネンが発見して、 "Algorithms for Approximate String Matching" において説明している。diffプログラムの最初のバージョンはテキストファイルの行単位での比較用に設計された。ここでの行は改行コードによって区切られていることを前提としていた。1980年までにはバイナリファイルへの対応も加えられた。

ポストプロセッサ sdiff は個々のdiff項目を並べて出力するものであり、 diffmk の方は印刷文書に変更箇所マークを挿入するためのものである。両者とも1981年以前にベル研外で開発されたものである。

Berkeley distribution of Unix ではコンテキスト形式の追加とファイルシステム中のディレクトリ構造を辿る機能が加わった。これらの機能は1981年7月にリリースされた2.8BSDから加わった。とりわけバークレーでコンテキスト形式が開発されたことによって、微細な変更が行われただけのソースコードへの改変をパッチの形で配布するような活動ができるようになった。

diff3コマンドは1ファイルを他の2つのファイルと比較する。これは1つのソースファイルを2人の人が変更したものを処理するためポール・ジェンセンが最初に開発した。直接実行されることはあまりなく大半はmergeプログラムから呼び出されて起動される。同様に、他の多くの履歴管理システムでも内部的に使われている。

Wdiffはテキスト中の単語単位・フレーズ単位での変更を見るためのツールであり、特に行折り返しや表幅などに相違がある場合に効果を発揮する。Spiff はさらに、浮動小数の精度桁数の違いやプログラムファイルでの空白やコメントなどを無視した比較ができる。

4.1. コンテキスト形式
-------------

「コンテキスト形式」の出力では変更された行部分に加えてその前後の変更されていない数行も示される。この呼称は、変更されていない行を加えることが「文脈」をパッチに与えることによる。この出力形式がpatchプログラムへの入力として使用される。また人間にとってもこの形式は読みやすく、パッチの適用にも適している。2ファイル間で変更のなかった箇所の行も出力されるため変更後のファイルでの変更箇所を特定するのが容易になる。これにより行番号の対応が取れなかったとしても変更点を追いやすくなり、変更を適用すべきかどうかの判断も行いやすくなる。

「変更内容の出力部」の上下に出力される変更のなかった行を何行分表示されるかはユーザが指定でき、全く出力しない「0」指定も可能であるが、標準では3行が出力される。変更箇所提示部において非変更行のコンテキストが隣接する変更箇所部分と重なる場合は、非変更箇所を2重に提示することはせず変更箇所を一つにまとめて提示する。

「!」から始まる行は2ファイル間での変更があった行、「+」から始まる行は行の挿入、行頭がスペースから始まる行は非変更行を示す。パッチの先頭行にはファイルのパスやタイムスタンプといったファイルに関する情報が書かれる。各変更箇所の先頭にはそれぞれのファイルにおける変更箇所の対応行番号が書かれる。3つのアスタリスクから始まる行では変更前ファイルでの行番号に対応する数字が出力され、3つのダッシュから始まる行では変更後ファイルでの行番号が出力される。出力行番号の数値はそれぞれのファイルにおける変更箇所の先頭行の行番号と先頭行からの行数を示す。

diff -c original newというコマンドを実行した際は、以下のような出力が行われる。

/path/to/original //timestamp// --- /path/to/new //timestamp//
1,3  --- 1,9 ----+ This is an important + notice! It should + therefore be located at + the beginning of this + document! + This part of the document has stayed the same from version to

5,20 be shown if it doesn't change. Otherwise, that would not be helping to ! compress the size of the ! changes. ! ! This paragraph contains ! text that is outdated. ! It will be deleted in the ! near future.

It is important to spell ! check this dokument. On the other hand, a misspelled word isn't the end of the world.

--- 11,20 ----be shown if it doesn't change. Otherwise, that would not be helping to ! compress anything.

It is important to spell ! check this document. On the other hand, a misspelled word isn't the end of the world.

22,24  --- 22,28 ----this paragraph needs to be changed. Things can be added after it. + + This paragraph contains + important new additions + to this document.<WtXmlEndTag />

4.2. ユニファイド形式 
------------------------------

ユニファイド形式はコンテキスト形式における技術的改良を継承し、より少量の出力でより読みやすい形式を追求し生まれた。通常、ユニファイド形式は「-u」オプションにより指定される。この出力形式はpatchプログラムへの入力形式として使われることが多い。現在、多くのプロジェクトにおいてdiff出力によるパッチを投稿する際にはこのユニファイド形式を使うよう推奨している。このため、このユニファイド形式がソフトウェア開発者の間でのいわば共通形式となっている。

ユニファイド形式diffを最初に開発したのはウェイン・デイヴィソンで、1990年8月のことであった。リチャード・ストールマンがGNUプロジェクトのdiffコマンドにこの機能を1ヶ月後に加え、1991年1月リリースのGNU diff 1.15から使えるようになった。GNU diffではその後、任意の形式のdiff出力を扱えるようコンテキスト出力サポートの拡張が進められた。GNU diffおよびdiff3は現在他のdiff系ツールやpatch系ツールと共にdiffutilsパッケージに含まれている。Emacsはインタフェースを備え、Ediffツールとしてパッチが変更する内容を表示しユーザが動的にパッチファイルの変更点を編集・マージすることができる。

ユニファイド出力形式ではヘッダの2行はコンテキスト形式と同一のもので始まるものの、元ファイルは「---」で示され新ファイルは「+++」で示される。これに続く変更箇所ではファイル間の相違が示されるが、非変更箇所は「 」、挿入行は「+」、削除行は「-」で始まる行で示される。

変更箇所ではその範囲を示す行番号・行数の情報に続いて行の挿入・削除、非変更箇所などが出力される。範囲を示す情報は2つの@マークで囲まれて出力され、前述のコンテキスト出力で示された内容は1行にまとめられた形で出力される。変更箇所の範囲情報の出力形式を以下に示す:

@@ -R +R @@

変更箇所の範囲情報は2つの範囲についての情報を含んでいる。一方はマイナス記号が頭に付いた元ファイルにおける変更箇所を示すものであり、もう一方はプラス記号が頭に付いた変更後のファイルにおける変更箇所を示している。範囲を示す//R//は//l,s//という形式となり、//l//は変更箇所の開始行、//s//はそれぞれのファイルにおける変更箇所の行数を示している。GNU diffの大半のバージョンでは、//R//において//s//がデフォルトの1である場合にはカンマ以降を省略した形式も使える。

元ファイルの変更箇所の範囲を示す情報では非変更箇所行・削除行についての行数分も含んだ情報が提示される。一方、変更後ファイルにおける範囲情報でも非変更箇所行・挿入行の分も含んだ情報が出力される。変更箇所における行数と範囲情報が示している行数が一致しない場合、その出力は不正な形式として拒絶される。

ある行が変更された場合、削除+挿入として表現される。元ファイルと変更後ファイルの変更箇所が同一の場所に現われ相互に隣り合って出力されることになる。以下のその一例を示す。

-check this dokument. On +check this document. On

diff -u original newというコマンドを実行した際は、以下のような出力が行われる。:

--- /path/to/original //timestamp//+++ /path/to/new //timestamp// @@ -1,3 +1,9 @@ +This is an important +notice! It should +therefore be located at +the beginning of this +document! + This part of the document has stayed the same from version to @@ -5,16 +11,10 @@ be shown if it doesn't change. Otherwise, that would not be helping to -compress the size of the -changes. - -This paragraph contains -text that is outdated. -It will be deleted in the -near future. +compress anything.

It is important to spell -check this dokument. On +check this document. On the other hand, a misspelled word isn't the end of the world. @@ -22,3 +22,7 @@ this paragraph needs to be changed. Things can be added after it. + +This paragraph contains +important new additions +to this document.<WtXmlEndTag />

diff出力形式の中には特定のプログラムや一定の利用法の中で変更や拡張が加えられているものもある。例えばバージョン管理システムでは、diffのヘッダ出力部分のタイプスタンプの箇所に版番号・バージョン番号や「ワーキングコピー」その他のコメント類を出力する場合もある。また複数のdiff出力を一つにまとめた形式が使えるものもある。この場合各変更ファイルのヘッダとして以下のような形式が使われる。:

Index: path/to/file.cpp ===================================================================

5. 実装
-----

5.1. GNU Diffutils
------------------

GNUではDiffutilsパッケージが製作されている。この中には、以下のものが含まれている。

cmp
diff
diff3
patch

6. 脚注
-----

7. 関連項目
-------

編集距離
差分符号化
rsync
マージ 

8. 参考文献
-------

[1] - MyersのSES/LCSアルゴリズムにHirschbergの改良アルゴリズムを加えた一般的な実装
[2] by Guido van Rossum, June 14, 2006

9. 外部リンク
--------

[3] - Free Software Foundation提供
[4]
[5] - 日本語対応で簡単に差分が確認できるテキスト比較ツール
[6] - Java用のdiffライブラリ