Как git сравнивает два файла при слиянии? - PullRequest
0 голосов
/ 04 июля 2019

Как git сравнивает два файла. Какие алгоритмы используются для сравнения двух файлов? Сравнивается ли строка за строкой при объединении?

Я не могу быть уверен, вызывает ли сравнение двух файлов конфликт или нет при объединении.

Ответы [ 3 ]

1 голос
/ 05 июля 2019

Ключ к пониманию git merge в том, что Git не сравнивает две вещи. Git сравнивает три вещи.

Git не может сравнить все три напрямую. Он должен сравнивать их по два за раз. Две вещи - это две версии файлов с подсказками ветвей (или коммиты с ветвями веток; я расскажу об этом чуть позже), но Git не сравнивает эти друг с другом . Вот где появляется третий: третий файл - версия слияния версия файла.

Помните, что цель объединения - объединить изменения . Но Git не хранит изменения. Git хранит снимки . Каждый коммит хранит каждый файл целиком и без изменений: при одном коммите Git получает весь README.md, весь main.py, какие бы другие файлы ни были в этом конкретном коммите, это версия в коммите.

Чтобы получить изменения из снимков, нам нужно два снимка: старый и новый. Затем мы играем в игру Найди отличия . Для Git это git diff: вы даете ему идентификатор хэша старого коммита и идентификатор хэша нового коммита, и он создает diff для каждого файла, который изменяется между ними. Вывод git diff представляет собой серию инструкций: удалить эти строки, добавить эти остальные строки . Если вы берете оригинальный снимок и применяете инструкции, вы получаете новый снимок.

Когда мы объединяем , мы хотим взять работу, выполненную (скажем) Алисой, и объединить ее с работой, проделанной Бобом. Итак, что делает Git:

  • Найдите лучший общий коммит, с которого начинали Алиса и Боб.
  • Сравните файлы shared commit с файлами Алисы. Это что Алиса изменила .
  • Сравните файлы shared commit с файлами Боба. Это то, что Боб изменил.

Мы называем общий коммит - тот, с которого начинали Алиса и Боб, - база слияния . Это третий вход для слияния. Git находит этот базовый коммит слияния автоматически, используя историю - коммиты - в вашем хранилище. Это означает, что вам необходимо иметь как коммиты Алисы и Боба, так и все коммиты, которые ведут к этим двум подсказкам ветвления, так что у вас также есть общий стартовый коммит.

Помните, что каждый коммит вместе со своим снимком записывает некоторую информацию о снимке: например, имя и адрес электронной почты человека, который его сделал. Есть отметка даты и времени для , когда они сделали это, и лог-сообщение, которое они могут использовать, чтобы объяснить , почему они сделали это. Он также хранит необработанный хэш-идентификатор своего непосредственного родительского коммита: коммит, который они использовали, через git checkout, чтобы начать с того момента, как они сделали их коммит. Эти родительские хеш-идентификаторы образуют обратную цепочку: если Алиса и Боб начали с коммита H, а Алиса сделала два коммита I и J, а Боб сделал два коммита K и L, обратный цепочки выглядят так:

                I <-J   <-- (Alice's latest)
               /
... <-F <-G <-H
               \
                K <-L   <-- (Bob's latest)

Git автоматически найдет H, отсюда и Алиса, и Боб. 1

Найдя H, Git теперь, по сути, запускает эти две git diff команды:

  • git diff --find-renames <em>hash-of-H</em> <em>hash-of-J</em>: что изменила Алиса
  • git diff --find-renames <em>hash-of-H</em> <em>hash-of-L</em>: что Боб изменил

Процесс слияния теперь объединяет эти изменения. Для каждого файла в H:

  • Алиса изменила файл? Боб изменил файл?
  • Если файл не был изменен, используйте любую копию файла: все три одинаковы.
  • Если Алиса изменила файл, а Боб нет, используйте версию Алисы.
  • Если Боб изменил файл, а Алиса - нет, используйте версию Боба.
  • Если оба изменили файл, объединит их изменения. Именно здесь может возникнуть конфликт слияния .

Сравнивает ли [Git] строку за строкой при объединении?

ThОтвет на этот вопрос - и нет, и да.Как вы можете видеть, нет сравнения версии Алисы с версией Боба. - это сравнение - сортировка построчно;это то, что git diff делает для сравнения - версии base с Алисой, и есть сравнение идентичной версии base с Бобом.Весь процесс начинается с полного сравнения всей пары двух пар коммитов .В рамках этого сравнения на уровне коммитов выяснилось, что Алиса и Боб изменили некоторый конкретный файл (ы) , , теперь построчно или действительно diff-hunk-by-diff-hunk, сравнения имеют значение.Но они из третьей версии.

Я не хочу проверять каждый раз вручную, используя "git diff".

Youне надоВы можете, если вы хотите , но для этого вам нужно найти коммит слиянием, возможно, используя git merge-base.Но если ты не хочешь, то ... не надо. Git найдет коммит на основе слияния; Git выполнит две отдельные операции git diff; Git объединит изменения Алисы с изменениями Боба и объявит конфликт, если измененные строки перекрываются - или в некоторых случаях abut , или если оба охватывают конец файла.

(Для Git, если Алиса и Боб внесли точно одинаковые изменения в точно одинаковых строк, Git просто берет одну копию изменения. Другие VCS могут объявитьконфликтуйте здесь, либо из-за лени - они не проверяют, чтобы изменения были одинаковыми, просто они перекрывались - или из-за паранойи: если оба изменили одни и те же строки, возможно, правильный результат - , а не просто для использованияодна копия изменения. Git просто говорит: «правильный результат - одна копия изменения».)

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

Наконец, обратите внимание на --find-renames в двух командах git diff.Git попытается определить, переименовал ли Алиса и / или Боб 1173 * какие-либо файлы в коммите слияния.Если это так, Git попытается сохранить переименование в конечном результате.Это верно независимо от того, переименовывала ли Алиса или Боб.Если Алиса и Боб переименовали файл, Git не знает, какое окончательное имя использовать, и объявляет конфликт переименование / переименование .Существуют похожие проблемы, если Алиса или Боб удаляют файл, в то время как другой изменяет его, и возникает последний конфликт, если Алиса и Боб добавляют новый файл с одинаковым именем,Эти типы конфликтов я называю конфликтами high level : они затрагивают целые файлы (и / или их имена), а не отдельные строки в файле.Эта разница между конфликтом низкого уровня (строки в файле) и конфликтом высокого уровня имеет значение, если и когда вы используете опцию -Xours или -Xtheirs.


1 Это работает, даже если Алиса сделала один коммит, скажем J, поверх (скажем) одного Кэрола I, который Кэрол сделала поверх H.Общая отправная точка по-прежнему H.Git даже не смотрит на авторство каждого коммита: он просто работает в двух направлениях.

0 голосов
/ 05 июля 2019

Существует несколько стратегий слияния.В Git по умолчанию используется рекурсивный алгоритм трехстороннего слияния.

Трехсторонний алгоритм использует последнюю общую фиксацию.

Например:

master: A -> B -> C

Создать новую ветвь

master: A -> B -> C
                   \
branch:             D

Некоторые новые коммиты

master: A -> B -> C -> E
                   \
branch:             D -> F

Предполагается, что все изменения сделаны в .txt (пустая ячейка соответствует пустой строке)

 commit C         commit E         commit F 
----------       ----------       ----------
  line a                            line a
  line b         new line d
  line c                          new line e
                   line a           line b
                   line b         new line f
                   line c           
                 new line g         line c

Что произойдет, если мы объединяемдве ветви (коммит E, коммит F).Это вызывает конфликт слияния?Ответ - нет.Потому что git не сравнивает файл построчно.Он сравнивает контекст строк.

Выровнять файл a.txt

 commit C         commit E         commit F 
----------       ----------       ----------

                 new line d

  line a-----------line a-----------line a

                                  new line e
  line b-----------line b-----------line b
                                  new line f

  line c-----------line c-----------line c
                 new line g

В приведенной выше таблице изменения выровнены.строки в коммите C (предок коммит) являются нашими ссылками.git сравнивает соседа с контрольными линиями.В этом примере у нас есть 4 слота:

  • над строкой a: commit e добавляет новую строку d
  • ниже строки a: commit f добавляет новую строку e
  • ниже строки b: commit e добавляет новую строку f
  • ниже строки c: commit g добавляет новую строку g

Как видите, только одна из ветвей (commitE, коммит F) может добавить что-то новое или оба могут добавить одно и то же.В противном случае возникает конфликт слияния.

0 голосов
/ 04 июля 2019

Используется дельта-сжатие . Мы должны понимать, что когда мы add получаем файл get, мы создаем объект, чья сумма sha рассчитывается и записывается в индекс. Что делает git, так это то, что через git-repack он принимает сжатые объекты (сжатые с помощью дельта-сжатия) в пакет (файл). Когда вы делаете коммиты, git берет не сжатые объекты и использует некоторые внутренние правила, он создает файл, содержащий различия и сходства между объектами. Это создание пакета использует дельта-сжатие.

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

Алгоритмы дельта-сжатия

Как git обрабатывает каждый файл

ГИТ-репака

дельта-дифференцирование

...