diff

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В вычислительной технике diff — утилита сравнения файлов, выводящая разницу между двумя файлами. Эта программа выводит построчно изменения, сделанные в файле (для текстовых файлов). Современные реализации поддерживают также двоичные файлы. Вывод утилиты называется «diff», или, что более распространено, патч, так как он может быть применён с программой patch. Вывод похожих утилит сравнения файлов также часто называется «diff».

История[править | править вики-текст]

Утилита diff была разработана в начале 1970-х годов для операционной системы Unix, которая была плодом работы AT&T Bell Labs, в Мюррей Хилл (Нью-Джерси). Финальная версия, распространяемая с 5ой версией Unix в 1974, была полностью написана Дугласом Макилроем.

Алгоритм[править | править вики-текст]

Работа diff основана на нахождении наибольшей общей подпоследовательности (англ. longest common subsequence, проблема LCS). Например, у вас имеется две последовательности элементов:

       a b c d f g h j q z
       a b c d e f g i j k r x y z

и вы хотите найти наиболее длинную последовательность элементов, которая представлена в обеих последовательностях в одинаковом порядке. Это означает, что вы хотите найти новую последовательность, которая может быть получена из первой последовательности удалением некоторых элементов или из второй последовательности удалением других элементов. В данном случае такой последовательностью будет являться

       a b c d f g j z

После получения наибольшей общей последовательности остаётся только небольшой шаг до получения похожего на diff вывода:

       e   h i   k   q r x y 
       +   - +   +   - + + +

Использование[править | править вики-текст]

diff вызывается из командной строки с именами двух файлов в качестве аргументов: diff original new. Вывод команды представляет собой изменения, которые нужно произвести в исходном файле original, чтобы получить новый файл new. Если original и new — директории, то diff автоматически будет применён к каждому файлу, который существует в обоих директориях. Все примеры в этой статье используют следующие два файла, 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 производит следующий нормальный дифф-вывод:

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 означает добавлено (от англ. add), d — удалено, с — изменено. Перед буквами a, d или c стоят номера строк исходного файла, после них — номера строк конечного файла. Каждая строка, которая была добавлена, удалена или изменена, предваряется угловыми скобками.

По умолчанию, общие для исходного и конечного файлов номера строк не указываются. Строки, которые перемещены, показываются как добавленные на своём новом месте и удалённые из своего прошлого расположения.[1]

Варианты[править | править вики-текст]

Большинство реализаций diff остаются внешне неизменными с 1975 года. Модификации включают в себя улучшения основного алгоритма, добавление новых ключей команды, новые форматы вывода. Базовый алгоритм изложен в книгах An O(ND) Difference Algorithm and its Variations Юджина В. Майерса,[2] и в A File Comparison Program Вебба Миллера и Майерса.[3] Алгоритм был независимо открыт и описан в Algorithms for Approximate String Matching Е. Укконеном[4] Первые версии программы diff были разработаны для сравнения строк текстовых файлов, использующий символ новой строки как разделитель строк. В 1980-х, поддержка двоичных файлов привела к изменениям в схеме работы и реализации программы.

Контекстный формат[править | править вики-текст]

В BSD версии 2.8 (выпущенной в июле 1981 года) появился контекстный формат (-c) и возможность рекурсивного обхода дерева каталогов файловой системы (-r).

В контекстном формате изменённые строки показываются вместе с незатронутыми строками до и после изменённого фрагмента. Вставка любого количества незатронутых строк предоставляет контекст для патча. Контекст, состоящий из незатронутых строк, служит ссылкой для определения положения изменяемого фрагмента в целевом файле, даже если номера изменяемых строк в исходном и целевом файлах не совпадают. Контекстный формат представляет большую читабельность для людей и большую надежность при применении патча, а вывод принимается в качестве входа для программы patch.

Число незатронутых строк до и после изменённого фрагмента может задаваться пользователем и быть даже нулем, но обычно по умолчанию равно трем строкам. Если контекст незатронутых строк во фрагменте пересекается с соседним фрагментом, то diff избежит копирования незатронутых строк и объединит фрагменты в один фрагмент.

Вывод команды 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.

Универсальный формат[править | править вики-текст]

Универсальный формат (или unidiff) включает в себя технические улучшения, сделанные в контекстном формате, но разницу между старым и новым текстом выдает в более компактом виде. Универсальный формат обычно вызывается использованием "-u" опции командной строки. Этот вывод часто используется как patch для программ. Многие проекты специально просят присылать им "diffs" в универсальном формате, делая, тем самым, универсальный формат самым распространенным для обмена между разработчиками программного обеспечения.

Универсальные контекстные diff'ы впервые были разработаны Wayne Davison в августе 1990 (unidiff появляется в главе 14 comp.sources.misc). Столлман добавил поддержку универсального формата в GNU Project's diff утилиту одним месяцем позже и эта функциональность дебютировала в GNU diff 1.15, выпущенная в январе 1991. GNU diff has since generalized the context format to allow arbitrary formatting of diffs.

Формат начинается с тех же самых двух линий header как и контекстный формат, за исключением того, что оригинальный файл начинается с "---", а новый файл начинается с "+++". Следом за ними следует один или больше измененных кусков, которые содержат по-линейные изменения в файлах. Линии без изменений начинаются с пробела, добавленные линии начинаются со знака плюс, удаленные линии начинаются со знака минус.

Кусок начинается с информации о диапазоне и сразу за ним следуют добавленные линии, удаленные линии и любое количество контекстных линий. Информация о диапазоне окружена двойными-@ знаками и сгруппирована в одну линию в отличии от двух линий в (контекстном формате). Информация о диапазоне имеет следующий формат:

@@ -l,s +l,s @@ optional section heading

Информация о диапазоне состоит из двух частей. Часть для оригинального файла начинается с минуса, а часть для нового файла начинается с плюса. Каждая часть в формате l,s, где l номер линии, с которой начинаем, а s количество линий, которые были изменены в текущем куске для каждого из файлов соответственно(то есть в первой случае это сумма выведенных строк начинающихся с пробела и с минуса, во втором - строк, начинающихся с пробела и с плюса). Во многих версиях GNU diff в каждом диапазоне запятая и замыкающая s может быть опущена. В этом случае s по умолчанию равна 1. Обратите внимание, что единственное полезное значение только у l - номер линии первого диапазона, остальные значения могут быть вычислены из diff'а.

Кусок диапазона для оригинального файла должен быть суммой всех контекстных и удаленных (включая измененные) линий куска. Кусок диапазона для нового файла должен включать сумму все контекстных и добавленных (включая измененные) линий куска.

Необязательно, но кусок диапазона может быть предварен заголовком секции или функции, частью которой является кусок. Это обычно полезно для чтения самого куска. Когда создается diff с использованием GNU diff заголовок определяется регулярным выражением[5]

Если линия была изменена, она показывается и как удаленная и как добавленная. С тех пор, как кусок оригинального и нового файлов появились в одном куске, такие изменения будут идти рядом друг с другом.[6] Например:

-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.

Обратите внимание, чтобы нормально отделить имена файлов от временных меток используется табуляция. Это незаметно на экране и может быть утеряно при копировании/вставки из консоли.

Есть несколько изменений и расширений для diff форматов, которые используют и понимают различные программы. Например, некоторые cистемы управления версиями, такие как Subversion, указывают номер версии, "рабочую копию" или любой другой комментарий в дополнение к временной метке в заголовке diff'a.

Некоторые программы позволяют создавать diff'ы для нескольких разных файлов и сливают их в один, используя заголовок для каждого измененного файла, который может выглядеть примерно так:

Index: path/to/file.cpp

Специальный вид файлов, которые не заканчиваются новой линией, не поддерживается. Ни unidiff утилита, ни POSIX diff стандарт не определяют способ обработки таких файлов (более того, такой тип файлов не "текстовые" файлы в определении POSIX.[7])

Программа patch ничего не знает о реализации специального вывода команды diff.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. David MacKenzie, Paul Eggert, and Richard Stallman Comparing and Merging Files with GNU Diff and Patch. — 1997. — ISBN ISBN 0-9541617-5-0.
  2. E. Myers (1986). «An O(ND) Difference Algorithm and Its Variations». Algorithmica 1 (2): 251–266.
  3. Webb Miller and Eugene W. Myers (1985). «A File Comparison Program». Software — Practice and Experience 15 (11): 1025–1040.
  4. E. Ukkonen (1985). «Algorithms for Approximate String Matching». Information and Control 64: 100–118.
  5. 2.2.3 Showing Which Sections Differences Are in, GNU diffutils manual
  6. Unified Diff Format by Guido van Rossum, Июнь 14, 2006
  7. http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_205 Section 3.205

Ссылки[править | править вики-текст]