Даже для одних и тех же двух файлов результат зависит от алгоритма diff. Все варианты «правильные», но они по-разному решают, какие строки считать совпадающими, и поэтому читаются с разной лёгкостью. В git опция --diff-algorithm предлагает четыре варианта.
| Значение | Описание в документации git | Особенности |
|---|---|---|
myers (default) | Базовый жадный (greedy) алгоритм, используется по умолчанию | Быстрый, результат обычно близок к минимальному |
minimal | Тратит больше времени, чтобы получить наименьший diff | Всегда минимальный, на больших входах может быть медленным |
patience | Алгоритм patience diff | Опирается на уникальные строки |
histogram | Расширяет patience поддержкой редко встречающихся общих элементов | Опирается на редкие строки |
Есть и короткие формы — git diff --patience, git diff --histogram, а значение по умолчанию меняется командой git config diff.algorithm histogram.
Myers: минимальное редактирование по умолчанию
Алгоритм Майерса ищет путь с минимальным числом удалений и добавлений (принцип описан в статье Как работает diff). Сложность возникает, когда есть несколько вариантов, какие строки считать одинаковыми. В коде много очень частых строк — }, {, пустые строки, return, — и алгоритм может сопоставить никак не связанные по смыслу строки, а число правок всё равно будет минимальным.
Одно изменение — два результата
Допустим, между функциями f и g вставили новую функцию h. Оба diff ниже содержат 4 добавленные строки, то есть число правок одинаково.
@@ -1,6 +1,10 @@ int f() { return 1; }++int h() {+ return 3;+} int g() { return 2;@@ -1,5 +1,9 @@ int f() { return 1;+}++int h() {+ return 3; } int g() {В первом новая функция видна целиком, а во втором закрывающая скобка существующей функции f принята за скобку новой, и добавленный фрагмент разрезан неестественно. Такая форма возникает из-за порядка поиска; современный git во многом исправляет это эвристикой, которая сдвигает границы изменённого блока по отступам для удобства чтения (--indent-heuristic, включена по умолчанию).
Patience: сначала уникальные строки
Patience diff предложил Брэм Коэн (Bram Cohen). Сначала алгоритм находит строки, которые встречаются ровно один раз в каждом из файлов: у уникальной строки, вроде объявления функции int h() {, пара определяется однозначно. Среди этих уникальных строк выбирается самый длинный список с согласованным порядком (наибольшая возрастающая подпоследовательность), он служит опорными точками, а заново сравниваются только небольшие участки между ними.
- Плюс: алгоритм не «цепляется» за частые строки вроде
}или пустых, поэтому изменения на уровне функций и абзацев видны цельными блоками. - Минус: на входе почти без уникальных строк (данные с повторами, логи) опорных точек не находится, и результат не отличается от обычного diff или даже сливается в крупные блоки.
Histogram: приоритет редким строкам
Алгоритм histogram был разработан в JGit (реализации git на Java) и затем появился в git. В отличие от patience, который смотрит только на строки, встречающиеся «ровно один раз», histogram подсчитывает, сколько раз встречается каждая строка, и выбирает опорными самые редкие. Поэтому даже при отсутствии уникальных строк он может опереться на относительно редкие. Документация git описывает его как расширение алгоритма patience, «поддерживающее редко встречающиеся общие элементы». На практике он, как и patience, часто хорошо сохраняет структуру кода.
Что выбрать
- Обычное ревью кода: достаточно значения по умолчанию. Если результат выглядит странно разрезанным, посмотрите ещё раз с
--histogram. - Крупный рефакторинг с переносом или добавлением нескольких функций:
--histogramили--patienceлучше сохраняют блоки. - Когда нужно получить строго минимальное число изменённых строк:
--minimal. - Файлы данных с большим числом повторов: сортировка и нормализация могут значить больше, чем алгоритм. Для JSON см. Сравнение JSON.
Какой бы алгоритм вы ни выбрали, файл восстанавливается одинаково. Меняется только то, как результат выглядит для человека.
В этом инструменте
Этот сайт сравнивает строки алгоритмом семейства Myers, затем по сходству содержимого объединяет изменённые строки в пары «изменено» и ещё раз сравнивает их содержимое. Поэтому даже если построчный результат разрезан не очень удачно, сразу видно, какое слово поменялось. Вставьте пример выше в сравнение текстов и сравните, как он выглядит в объединённом и боковом виде. Как читать результат, описано в статье Как читать unified diff.