Diff

Article on other languages:

del.icio.us del.icio.us
Digg Digg
Furl Furl
Reddit Reddit
Rojo Rojo
Add to OnlyWire

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

目次

歴史

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（SCCS）はそのようなアイデアを実装したものとして、1970年代後半に実装がなされた。

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

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

使用法

以下のようにコマンドラインで2つのファイル名を指定して実行する。

diff original new

コマンドからの出力はファイルoriginalをファイルnewに変更するのに必要な箇所を示す。

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

利用例

以下、2つのファイル（original と new）を例に説明する:

original:

This part of the
document has stayed the
same from version to
version. It shouldn't
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.
Nothing in the rest of
this paragraph needs to
be changed. Things can
be added after it.

new:

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
version. It shouldn't
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.
Nothing in the rest of
this paragraph needs to
be changed. Things can
be added after it.

This paragraph contains
important new additions
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
24a25,28
>
> This paragraph contains
> important new additions
> to this document.

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

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

変種

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

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

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

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

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

コンテキスト形式（Context format）

「コンテキスト形式」の出力では、変更された行部分に加えて、その前後の変更されていない数行も示される。この呼称は、変更されていない行を加えることが「文脈（コンテキスト）」をパッチに与えることによる。この出力形式が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.

ユニファイド形式 (Unified format)

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

ユニファイド形式diffを最初に開発したのはウェイン・デイヴィソンで、1990年8月のことであった（comp.sources.miscのVolume 14にunidiffとして投稿）。リチャード・ストールマンがGNUプロジェクトのdiffコマンドにこの機能を1ヶ月後に加え、1991年1月リリースのGNU diff 1.15から使えるようになった。GNU diffではその後、任意の形式のdiff出力を扱えるようコンテキスト出力サポートの拡張が進められた。GNU diffおよびdiff3は現在、他のdiff系ツールやpatch系ツールと共に、difutilsパッケージに含まれている。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

通常、ユニファイド形式の出力は"-u"オプションで指定される。この出力形式はpatchプログラムへの入力形式として使われることが多い。

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

--- original timestamp
+++ 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.

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

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

関連項目

参考文献

外部リンク

"http://ja.wikipedia.org/wiki/Diff" より作成

Questions for article: c-diff, mackenzie et al. binary files and forcing text comparison in comparing and merging files with gnu diff and patch. downloaded 28 april 2007, cbc with diff, mackenzie et al. binary files and forcing text comparison in comparing and merging files with gnu diff and patch. downloaded 28 april 2007, cbc with diff

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car
James Bond Guide
This site monitored by SitePinger.net