Diff

In computing, the utility diff is a data comparison tool that computes and displays the differences between the contents of files. Unlike edit distance notions used for other purposes, diff is line-oriented rather than character-oriented, but it is like Levenshtein distance in that it tries to determine the smallest set of deletions and insertions to create one file from the other. The utility displays the changes in one of several standard formats, such that both humans or computers can parse the changes, and use them for patching.
Typically, "diff" is used to show the changes between two versions of the same file. Modern implementations also support binary files. The output is called a "diff", or a patch, since the output can be applied with the Unix program . The output of similar file comparison utilities is also called a "diff"; like the use of the word "grep" for describing the act of searching, the word "diff" became a generic term for calculating data difference and the results thereof. The POSIX standard specifies the behavior of the "diff" and "patch" utilities and their file formats.
History.
diff was developed in the early 1970s on the Unix operating system which was emerging from Bell Labs in Murray Hill, New Jersey. The final version, first shipped with the 5th Edition of Unix in 1974, was entirely written by Douglas McIlroy. This research was published in a 1976 paper co-written with James W. Hunt who developed an initial prototype of . The algorithm this paper described became known as the Hunt–Szymanski algorithm.
McIlroy's work was preceded and influenced by Steve Johnson's comparison program on GECOS and Mike Lesk's program. also originated on Unix and, like , produced line-by-line changes and even used angle-brackets (">" and "<") for presenting line insertions and deletions in the program's output. The heuristics used in these early applications were, however, deemed unreliable. The potential usefulness of a diff tool provoked McIlroy into researching and designing a more robust tool that could be used in a variety of tasks but perform well in the processing and size limitations of the PDP-11's hardware. His approach to the problem resulted from collaboration also with individuals at Bell Labs including Alfred Aho, Elliot Pinson, Jeffrey Ullman, and Harold S. Stone.
In the context of Unix, the use of the line editor provided with the natural ability to create machine-usable "edit scripts". These edit scripts, when saved to a file, can, along with the original file, be reconstituted by into the modified file in its entirety. This greatly reduced the secondary storage necessary to maintain multiple versions of a file. McIlroy considered writing a post-processor for where a variety of output formats could be designed and implemented, but he found it more frugal and simpler to have be responsible for generating the syntax and reverse-order input accepted by the command.
Late in 1984 Larry Wall created a separate utility, patch,
releasing its source code on the "mod.sources" and "net.sources" newsgroups.
This program generalized and extended the ability to modify files with output from .
Modes in Emacs also allow for converting the format of patches and even editing patches interactively.
In 's early years, common uses included comparing changes in the source of software code and markup for technical documents, verifying program debugging output, comparing filesystem listings and analyzing computer assembly code. The output targeted for was motivated to provide compression for a sequence of modifications made to a file. The Source Code Control System (SCCS) and its ability to archive revisions emerged in the late 1970s as a consequence of storing edit scripts from .
Algorithm.
The operation of is based on solving the longest common subsequence problem.
In this problem, given two sequences of items:
 h q 
 e i k r x y 
and we want to find a longest sequence of items that is present in both original sequences in the same order. That is, we want to find a new sequence which can be obtained from the first original sequence by deleting some items, and from the second original sequence by deleting other items. We also want this sequence to be as long as possible. In this case it is
 a b c d f g j z
From a longest common subsequence it is only a small step to get -like output: if an item is absent in the subsequence but present in the first original sequence, it must have been deleted (as indicated by the '-' marks, below). If it is absent in the subsequence but present in the second original sequence, it must have been inserted (as indicated by the '+' marks).
 e h i q k r x y
Usage.
The codice_1 command is invoked from the command line, passing it the names of two files: codice_2. The output of the command represents the changes required to transform the "original" file into the "new" file.
If "original" and "new" are directories, then will be run on each file that exists in both directories. An option, codice_3, will recursively descend any matching subdirectories to compare files between directories.
Any of the examples in the article use the following two files, "original" and "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 the size of the
changes.
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.
The command codice_4 produces the following "normal diff output":
 "Here, the diff output is shown with colors to make it easier to read. The diff utility does not produce colored output; its output is plain text. However, many tools can show the output with colors by using syntax highlighting."
In this traditional output format, <samp>a</samp> stands for "added", <samp>d</samp> for "deleted" and <samp>c</samp> for "changed". Line numbers of the original file appear before <samp>a</samp>/<samp>d</samp>/<samp>c</samp> and those of the new file appear after. The less-than and greater-than signs (at the beginning of lines that are added, deleted or changed) indicate which file the lines appear in. Addition lines are added to the original file to appear in the new file. Deletion lines are deleted from the original file to be missing in the new file.
By default, lines common to both files are not shown. Lines that have moved are shown as added at their new location and as deleted from their old location. However, some diff tools highlight moved lines.
Output.
Edit script.
An ed script can still be generated by modern versions of diff with the codice_5 option. The resulting edit script for this example is as follows:
 24a
 "This paragraph contains"
 "important new additions"
 "to this document."
 17c
 "check this document. On"
 11,15d
 0a
 "This is an important"
 "notice! It should"
 "therefore be located at"
 "the beginning of this"
 "document!"
 .
In order to transform the content of file "original" into the content of file "new" using , we should append two lines to this diff file, one line containing a codice_6 (write) command, and one containing a codice_7 (quit) command (e.g. by ). Here we gave the diff file the name "mydiff" and the transformation will then happen when we run .
Context format.
The Berkeley distribution of Unix made a point of adding the "context format" () and the ability to recurse on filesystem directory structures (), adding those features in 2.8 BSD, released in July 1981. The context format of diff introduced at Berkeley helped with distributing patches for source code that may have been changed minimally.
In the context format, any changed lines are shown alongside unchanged lines before and after. The inclusion of any number of unchanged lines provides a "context" to the patch. The "context" consists of lines that have not changed between the two files and serve as a reference to locate the lines' place in a modified file and find the intended location for a change to be applied regardless of whether the line numbers still correspond. The context format introduces greater readability for humans and reliability when applying the patch, and an output which is accepted as input to the patch program. This intelligent behavior isn't possible with the traditional diff output.
The number of unchanged lines shown above and below a change "hunk" can be defined by the user, even zero, but three lines is typically the default. If the context of unchanged lines in a hunk overlap with an adjacent hunk, then diff will avoid duplicating the unchanged lines and merge the hunks into a single hunk.
A " represents a change between lines that correspond in the two files. A " represents the addition of a line, while a blank space represents an unchanged line. At the beginning of the patch is the file information, including the full path and a time stamp delimited by a tab character. At the beginning of each hunk are the line numbers that apply for the corresponding change in the files. A number range appearing between sets of three asterisks applies to the original file, while sets of three dashes apply to the new file. The hunk ranges specify the starting and ending line numbers in the respective file.
The command produces the following output:
--- /path/to/new timestamp
--- 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
 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.
--- 14,21 ----
 compress the size of the
 changes.
 It is important to spell
! check this document. On
 the other hand, a
 misspelled word isn't
 the end of the world.
--- 23,29 ----
 this paragraph needs to
 be changed. Things can
 be added after it.
+ This paragraph contains
+ important new additions
+ to this document.
 "Here, the diff output is shown with colors to make it easier to read. The diff utility does not produce colored output; its output is plain text. However, many tools can show the output with colors by using syntax highlighting."
Unified format.
The "unified format" (or "unidiff") inherits the technical improvements made by the context format, but produces a smaller diff with old and new text presented immediately adjacent. Unified format is usually invoked using the "codice_8" command line option. This output is often used as input to the patch program. Many projects specifically request that "diffs" be submitted in the unified format, making unified diff format the most common format for exchange between software developers.
Unified context diffs were originally developed by Wayne Davison in August 1990 (in unidiff which appeared in Volume 14 of comp.sources.misc). Richard Stallman added unified diff support to the GNU Project's diff utility one month later, and the feature debuted in GNU diff 1.15, released in January 1991. GNU diff has since generalized the context format to allow arbitrary formatting of diffs.
The format starts with the same two-line header as the context format, except that the original file is preceded by "<samp>---</samp>" and the new file is preceded by "<samp>+++</samp>". Following this are one or more change hunks that contain the line differences in the file. The unchanged, contextual lines are preceded by a space character, addition lines are preceded by a plus sign, and deletion lines are preceded by a minus sign.
A hunk begins with range information and is immediately followed with the line additions, line deletions, and any number of the contextual lines. The range information is surrounded by double at signs, and combines onto a single line what appears on two lines in the context format (above). The format of the range information line is as follows:
 @@ -l,s +l,s @@ "optional section heading"