Сравнить два файла

«Diffs» — это лингва франка изменений. Это компактные повествования, которые говорят вам, что переместилось между двумя версиями чего-либо — исходного кода, прозы, набора данных — без необходимости перечитывать все. За этими несколькими символами (+, -, @@) скрывается глубокий стек алгоритмов, эвристик и форматов, которые балансируют оптимальность, скорость и человеческое понимание. Эта статья — практический тур по diffs от алгоритмов до рабочих процессов: как они вычисляются, как форматируются, как их используют инструменты слияния и как их настраивать для лучших обзоров. Попутно мы будем обосновывать утверждения на первоисточниках и официальных документах — потому что мелкие детали (например, учитываются ли пробелы) действительно имеют значение.

Что такое «diff» на самом деле

Формально diff описывает кратчайший сценарий редактирования (SES) для преобразования «старой» последовательности в «новую» с использованием вставок и удалений (а иногда и замен, которые можно смоделировать как удаление+вставку). На практике большинство diff, с которыми сталкиваются программисты,ориентированы на строки, а затем при необходимости уточняются до слов или символов для удобочитаемости. Каноническими выходными данными являются форматы контекста и унифицированный ; последний — то, что вы обычно видите при проверке кода — сжимает вывод с помощью краткого заголовка и «чанков», каждый из которых показывает окрестности контекста вокруг изменений. Унифицированный формат выбирается с помощью -u/--unified и является стандартом де-факто для исправлений; patch обычно выигрывает от строк контекста для надежного применения изменений.

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

От LCS до Майерса: как вычисляются diff

Большинство текстовых diff основаны на абстракции наибольшей общей подпоследовательности (LCS) . Классическое динамическое программирование решает LCS за время и пространство O(mn), но это слишком медленно и требует много памяти для больших файлов. Алгоритм Хиршберга показал, как вычислять оптимальные выравнивания в линейном пространстве (все еще время O(mn)), используя метод «разделяй и властвуй», фундаментальную технику экономии пространства, которая повлияла на практические реализации diff.

Прорывом в скорости и качестве стал алгоритм Юджина В. Майерса 1986 года, который находит SES за время O(ND) (N ≈ общее количество строк, D ≈ расстояние редактирования) и почти линейное пространство. Майерс моделирует правки в «графе правок» и продвигается посамым дальним границам, получая результаты, которые одновременно быстры и близки к минимальным в контексте diff по строкам. Вот почему «Майерс» остается по умолчанию во многих инструментах.

Существует также семейство Ханта-Шимански , которое ускоряет LCS, когда совпадает мало позиций (путем предварительной индексации совпадений и преследования возрастающих подпоследовательностей), и исторически связано с ранними вариантами diff. Эти алгоритмы проливают свет на компромиссы: во входных данных с редкими совпадениями они могут работать субквадратично. Для обзора практика, соединяющего теорию и реализацию, см. заметки Нила Фрейзера.

Когда «оптимальный» нечитаем: стратегии терпения и гистограммы

Майерс нацелен на минимальные сценарии редактирования, но «минимальный» ≠ «самый читаемый». Большие переставленные или дублированные блоки могут обмануть чистый алгоритм SES, заставив его сделать неуклюжие выравнивания. Введите patience diff, приписываемый Брэму Коэну: он закрепляется на уникальных, низкочастотных строках, чтобы стабилизировать выравнивания, часто создавая diff, которые люди находят более чистыми — особенно в коде с перемещенными функциями или реорганизованными блоками. Многие инструменты предоставляют это через опцию «терпение» (например,diff.algorithm).

Гистограммный diff расширяет терпение с помощью гистограммы частот для лучшей обработки элементов с низкой встречаемостью, оставаясь при этом быстрым (популяризирован в JGit). Если вы когда-либо обнаруживали, что --histogram создает более четкие чанки для зашумленных файлов, это сделано намеренно. В современном Git вы можете выбрать алгоритм глобально или для каждого вызова:git config diff.algorithm myers|patience|histogram или git diff --patience.

Четкость на уровне слов, контроль пробелов и выделение перемещенного кода

Diff по строкам кратки, но могут скрывать мелкие правки. Diff на уровне слов (--word-diff) окрашивает внутристрочные изменения, не загромождая обзор вставками/удалениями целых строк — отлично подходит для прозы, длинных строк или однострочников.

Пробелы могут загромождать diff после переформатирования. И Git, и GNU diff позволяют вам игнорировать изменения пробелов в разной степени, а опции пробелов GNU diff (-b, -w, -B) помогают, когда работает форматер; вы увидителогические правки вместо шума выравнивания.

Когда код перемещается целиком, Git может выделять перемещенные блоки с помощью --color-moved, визуально отделяя «перемещенное» от «измененного», что помогает рецензентам убедиться, что перемещение не скрыло непреднамеренных правок. Сохраните это с помощью diff.colorMoved.

Diff на службе слияний: двустороннее и трехстороннее слияние и diff3

Двусторонний diff сравнивает ровно две версии; он не может сказать, редактировали ли обе стороны одну и ту же базовую строку, поэтому часто возникает слишком много конфликтов. Трехстороннее слияние (используемое современными VCS) вычисляет diff от общего предкак каждой стороне, а затем согласовывает два набора изменений. Это значительно уменьшает ложные конфликты и обеспечивает лучший контекст. Классическим алгоритмическим ядром здесь является diff3, который объединяет изменения из «O» (базы) в «A» и «B» и при необходимости помечает конфликты.

Академическая и промышленная работа продолжает формализовать и улучшать правильность слияния; например, проверенные трехсторонние слияния предлагают семантические понятия свободы от конфликтов. В повседневной работе с Git современная стратегия слияния ort основана на diff и обнаружении переименований для создания слияний с меньшим количеством сюрпризов. Для пользователей ключевые советы: показывать базовые строки в конфликтах с помощью merge.conflictStyle=diff3и часто интегрироваться, чтобы diff оставались небольшими.

Обнаружение переименований и его пороги

Традиционные diff не могут «видеть» переименования, потому что адресация по содержимому рассматривает файлы как блобы; они видят только удаление и добавление. Эвристики обнаружения переименований преодолевают этот разрыв, сравнивая сходство между добавленными/удаленными парами. В Git включите или настройте с помощью -M/--find-renames[=<n>] (по умолчанию ~50% сходства). Уменьшите его для более шумных перемещений. Вы можете ограничить сравнения кандидатов с помощью diff.renameLimit (и merge.renameLimit во время слияний). Чтобы отслеживать историю через переименования, используйте git log --follow -- <path>. Недавний Git также выполняет обнаружение переименования каталогов для распространения перемещений папок во время слияний.

Бинарные и дельта-diff: rsync, VCDIFF/xdelta, bsdiff

Меняется не только текст. Для бинарных файлов обычно требуется дельта-кодирование — выдача инструкций копирования/добавления для восстановления цели из источника. Алгоритм rsync стал пионером эффективного удаленного сравнения с использованием скользящих контрольных сумм для выравнивания блоков по сети, минимизируя пропускную способность.

IETF стандартизировал общий формат дельты, VCDIFF (RFC 3284), описывающий байт-код ADD, COPY и RUN, с реализациями, такими как xdelta3 , использующими его для бинарных исправлений. Для компактных исправлений на исполняемых файлах bsdiff часто создает очень маленькие дельты с помощью суффиксных массивов и сжатия; выбирайте его, когда размер исправления доминирует, а генерация может происходить в автономном режиме.

Текстовые diff за пределами исходного кода: нечеткое сопоставление и исправление

Когда вам нужно надежное исправление в условиях одновременных правок или немного несогласованных контекстов — подумайте о редакторах или совместных системах — рассмотрите diff-match-patch. Он сочетает сравнение в стиле Майерса с Bitap нечетким сопоставлением для поиска близких совпадений и применения исправлений «по мере возможности», плюс ускорения перед diff и очистки после diff, которые обменивают немного минимальности на более приятный человеческий вывод. О том, как объединить diff и нечеткое исправление в непрерывных циклах синхронизации, см. в Дифференциальной синхронизацииФрейзера.

Структурированные diff данных: таблицы и деревья

Diff по строкам в CSV/TSV хрупки, потому что изменение одной ячейки может выглядеть как правка всей строки. Инструменты diff, осведомленные о таблицах (daff) рассматривают данные как строки/столбцы, выдавая исправления, нацеленные на определенные ячейки, и отображая визуализации, которые делают добавления, удаления и изменения очевидными (см. виньетку R). Для быстрой проверки специализированные средства сравнения CSV могут выделять изменения по ячейкам и сдвиги типов; они не являются алгоритмически экзотическими, но они увеличивают сигнал обзора, сравнивая структуру, которая вас действительно волнует.

Практическая настройка Git diff: контрольный список рецензента

• Выберите правильный алгоритм: начните с Майерса (по умолчанию), попробуйте --patience , если перестановки или зашумленные блоки сбивают с толку вывод, или --histogram для быстрых, читаемых diff на повторяющемся тексте. Установите по умолчанию с помощью git config diff.algorithm ….
• Уменьшите шум: для правок только стиля используйте флаги пробелов (-b, -w, --ignore-blank-lines), чтобы сосредоточиться на существенных изменениях. Вне Git см. элементы управления пробелами GNU diff.
• Загляните внутрь строки: --word-diff помогает для длинных строк и прозы.
• Проверьте перемещенный код: --color-moved (или diff.colorMoved) отделяет «перемещенное» от «измененного».
• Обрабатывайте переименования: при просмотре рефакторинга добавьте -M или измените порог сходства (-M90%, -M30%), чтобы поймать переименования; помните, что по умолчанию это около 50%. Для глубоких деревьев установите diff.renameLimit.
• Следите за историей через переименования: git log --follow -- <path>.

Как слияния на самом деле используют diff (и что делать, если они этого не делают)

Слияние вычисляет два diff (BASE→OURS, BASE→THEIRS) и пытается применить оба к BASE. Стратегии, такие как ort , организуют это в масштабе, включая обнаружение переименований (включая перемещения на уровне каталогов) и эвристики для минимизации конфликтов. Когда возникают конфликты, --conflict=diff3 обогащает маркеры базовым контекстом, который бесценен для понимания намерения. Глава Pro Git о расширенном слиянии рассматривает шаблоны разрешения, а документы Git перечисляют такие ручки, как -X ours и -X theirs. Чтобы сэкономить время на повторяющихся конфликтах, включите rerere для записи и воспроизведения ваших решений.

За пределами файлов: удаленные и инкрементные сценарии

Если вы синхронизируете большие активы по сети, вы ближе к rsync миру, чем к локальному diff. Rsync вычисляет скользящие контрольные суммы для обнаружения совпадающих блоков удаленно, а затем передает только то, что необходимо. Для упакованных дельт VCDIFF/xdelta дает вам стандартный байт-код и зрелые инструменты; выбирайте его, когда вы контролируете и кодировщик, и декодер. И если размер исправления имеет первостепенное значение (например, прошивка по воздуху), bsdiff обменивает процессор/память во время сборки на очень маленькие исправления.

Краткое слово о «нечетком» и «дружелюбном»

Библиотеки, такие как diff-match-patch , признают, что в реальном мире файл, который вы исправляете, мог измениться. Комбинируя надежный diff (часто Майерса) с нечетким сопоставлением (Bitap) и настраиваемыми правилами очистки, они могут найти правильное место для применения исправления и сделать diff более читабельным — что критически важно для совместного редактирования и синхронизации.

«Настольные ставки», которые вы должны усвоить

1. Знайте свои форматы. Унифицированные diff (-u/-U<n>) компактны и удобны для исправлений; это то, чего ожидают проверка кода и CI (справка).
2. Знайте свои алгоритмы. Майерс для быстрых минимальных правок (статья); терпение/гистограмма для удобочитаемости при перестановках или зашумленных блоках (терпение, гистограмма); Хиршберг для трюка с линейным пространством (статья); Хант-Шимански для ускорения редких совпадений (статья).
3. Знайте свои переключатели. Элементы управления пробелами, word-diff и color-moved — это множители обзора (документация git diff; опции пробелов GNU).
4. Знайте свои слияния. Трехстороннее слияние в стиле diff3 менее запутанно; ort плюс обнаружение переименований уменьшает отток; rerere экономит время.
5. Выберите правильный инструмент для данных. Для CSV/таблиц используйте daff; для бинарных файлов используйте VCDIFF/xdelta или bsdiff.

Приложение: крошечная поваренная книга команд

Потому что мышечная память имеет значение:

# Показать стандартный унифицированный diff с дополнительным контекстом
  git diff -U5
  diff -u -U5 a b
  
  # Получить четкость на уровне слов для длинных строк или прозы
  git diff --word-diff
  
  # Игнорировать шум пробелов после переформатирования
  git diff -b -w --ignore-blank-lines
  diff -b -w -B a b
  
  # Выделить перемещенный код во время обзора
  git diff --color-moved
  git config --global diff.colorMoved default
  
  # Укротить рефакторинг с помощью обнаружения переименований и отслеживать историю через переименования
  git diff -M
  git log --follow -- <file>
  
  # Предпочесть алгоритм для удобочитаемости
  git diff --patience
  git diff --histogram
  git config --global diff.algorithm patience
  
  # Посмотреть базовые строки в маркерах конфликтов
  git config --global merge.conflictStyle diff3

Заключительная мысль

Отличные diff — это не столько доказательство минимальности, сколько максимизация понимания рецензента при минимальных когнитивных затратах. Вот почему экосистема развила несколько алгоритмов (Майерс, терпение, гистограмма), несколько представлений (унифицированный, word-diff, color-moved) и инструменты, осведомленные о домене (daff для таблиц, xdelta/bsdiff для бинарных файлов). Изучите компромиссы, настройте ручки, и вы потратите больше времени на размышления об намерении и меньше времени на восстановление контекста из красных и зеленых строк.