Доступны ли более умные алгоритмы конфликта слияния для git? - PullRequest
Новая
       5

Доступны ли более умные алгоритмы конфликта слияния для git?

2 голосов
/ 14 января 2020

Когда перебазирование и Git генерируют конфликты слияния, они иногда представляются довольно запутанными. Например, если у меня есть этот код: 

async loadDirectory({ commit }, path: string) {
  ...

В master Я делаю это sync: 

loadDirectory({ commit }, path: string): void {
  ...

И в some_branch (на основе исходного кода) I добавьте еще одну функцию перед ним: 

async fetchData({ commit }) {
  lots();
  of();
  code();
},

async loadDirectory({ commit }, path: string) {
  ...

Теперь, если я попытаюсь перебазировать some_branch на master, git покажет этот конфликт: 

<<<<<<< HEAD
loadDirectory({ commit }, path: string): void {
=======
async fetchData({ commit }) {
  lots();
  of();
  code();
},

async loadDirectory({ commit }, path: string) {
>>>>>>> Add data fetching function

Это довольно запутанно ! Было бы намного легче понять, если бы он представил конфликт следующим образом: 

<<<<<<< HEAD
=======
async fetchData({ commit }) {
  lots();
  of();
  code();
},
>>>>>>> Add data fetching function

<<<<<<< HEAD
loadDirectory({ commit }, path: string): void {
=======
async loadDirectory({ commit }, path: string) {
>>>>>>> Add data fetching function

Я на самом деле не изучал алгоритм Git, но подозреваю, что он оптимизирует для сложности алгоритмов c, и небольшое количество конфликтных участков. Но каким бы ни был алгоритм, этот пример показывает, что его можно улучшить (возможно, за счет снижения производительности).

Мой вопрос: теоретически возможно ли использовать другой алгоритм с Git, и работает ли кто-нибудь над ним? что?

Ответы [ 3 ]

3 голосов
/ 14 января 2020

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

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

На верхнем уровне мы вызываем git merge с использованием командной строки, включая эти параметры. Существуют и другие варианты, но я хочу их особо назвать:

git merge [-s <em>strategy</em>] [-X <em>extended-options</em>] <em>commit-specifier</em>

Аргумент -s принимает стратегию , и там пять встроенных стратегий, но на самом деле имеет значение только одна (или две или три в зависимости от того, как вы считаете):

  • recursive и resolve по сути одинаковы, за исключением случаев, когда существует более одной базы слияния (случай, который я не буду здесь обсуждать). Это те, которые имеют значение, и для рассматриваемого нами случая они практически идентичны.

  • octopus предназначен для использования при указании более одного commit-specifier аргумент; он строит слияние осьминога , то есть с более чем двумя родителями. Я также не буду обсуждать это, потому что слияния осьминога не разрешают разрешение конфликтов в любом случае.

  • ours полностью игнорирует все другие коммиты и просто сохраняет текущее дерево, поэтому оно здесь не подходит .

  • subtree - это своего рода взломанный вариант recursive для переименования поддеревьев, и, следовательно, действительно относится к категории recursive.

Вы можете предоставить свою собственную стратегию слияния! Все, что вам нужно сделать, это написать команду, назвать ее git-merge-<em>whatever</em> и запустить git merge -s <em>whatever</em>, а Git вызовет вашу стратегию слияния. Однако если вы делаете и пишете свою собственную стратегию слияния, вы должны заставить ее делать все , и это довольно сложно, о чем свидетельствует тот факт, что третьего, кажется, не существует. -страницы доступны как Git дополнения. Другими словами, фраза все, что вам нужно сделать , охватывает множество грехов, некоторые из которых, по-видимому, довольно серьезны. : -)

extended-options - Git называет эти опции стратегии , что мне кажется плохим именем, поскольку -s означает опция стратегии - просто передается стратегии как опции. Стандартная стратегия (или стратегии, в зависимости от того, считаете ли вы разрешение и / или поддерево как отдельные стратегии), позволяет -X ours и -X theirs, что в данном случае не то, что вам нужно, но стоит упомянуть, плюс целый хост дополнительных -X опций для настройки параметров в алгоритмах.

Однако, по большей части, стандартная стратегия работает следующим образом:

  • нахождение базы слияния (или оснований, множественное число , для -s recursive), чтобы мы имели один коммит для использования в качестве базы слияния;
  • сравнение базы слияния с HEAD и с другим коммитом, как будто на два git diff --find-rename операций;
  • объединение наборов изменений, произведенных двумя git diff s.

Если рекурсивная стратегия находит две или более базисов слияния, она объединяет их, как если бы git merge -s recursive, по одной паре коммитов за раз, фиксируя каждый результат. Каждый такой коммит является временным и не имеет имени ветви. Он имеет необработанный га sh ID— каждый коммит, так что этот временный коммит делает тоже самое - и окончательный результат результата слияния ha sh ID является базовым коммитом слияния. В основном, однако, мы в итоге -s recursive находим некоторую существующую (единственную) базу слияния, поэтому в качестве базы слияния используется тот коммит. Если стратегия разрешения находит две или более баз слияния, она выбирает одну из них, что также может быть случайным. (Это на самом деле не случайно, но это то, что сначала выходит из алгоритма поиска базы, и порядок не указан, а алгоритм поиска базы может измениться в будущем.)

Итак: на данный момент у нас есть три коммита:

  • база слияния;
  • текущий коммит, который всегда HEAD, как --ours; и
  • коммит, который вы указали в командной строке, как --theirs.

В базе существует некоторый набор файлов. Эти файлы в паре с некоторым набором файлов в --ours, в соответствии с алгоритмом поиска переименования. Любые файлы, которые остаются непарными - которые не могут быть идентифицированы как «один и тот же файл» слева и справа - либо добавляются (ничего слева, новый файл справа), либо удаляются (ничего справа, файл левой стороны удаляется). Файлы, чье имя изменилось, переименовываются. Файлы, которые были объединены в пару и которые имеют измененное содержимое, «модифицируются» (и, возможно, также переименовываются). Оставшиеся спаренные файлы вообще не изменены.

То же самое происходит с базовым коммитом и --theirs коммитом, создавая списки файлов, которые изменены и / или переименованы, добавлены, удалены или неизменны вообще.

Обратите внимание, что в принципе на этом этапе все три коммита попадают в индекс. (Существует оптимизация, при которой индекс фактически не расширяется, если это возможно, но результат этого оптимизированного подхода должен соответствовать результату фактического помещения всех трех коммитов в индекс.) Способ, которым это работает, заключается в том, что каждая запись в Индекс имеет номер промежуточного слота . Таким образом, файл может занимать промежуточные слоты 1 (база слияния), 2 (--ours) и 3 (--theirs) одновременно. Это три копии файла или, если быть точным, три ссылки на BLOB-объекты, все из которых используют одно и то же имя файла в индексе.

Нулевой интервал подготовки индекса используется для разрешено файлов. В этом случае нет конфликта слияния для этого файла.

Следующим шагом является операция слияния high level : файлы, которые переименованы, должны быть переименованы из базы в конечный коммит. Если обе стороны переименовали файл, у нас возникает конфликт переименования / переименования. Git объявляет конфликт для этих файлов и выбирает одно из двух новых имен в качестве целевого имени для использования в рабочем дереве. Однако внутри index исходное имя в базе слияния занимает слот 1 для имени base-commit, новое имя в --ours занимает слот 2 для имени ours-commit и новое имя в --theirs занимает слот 3 для имени их коммита. Это просто тот факт, что файл рабочего дерева должен иметь некоторое имя, которое заставляет Git выбрать одно (и я думаю, Git использует здесь имя --ours, но я должен был поэкспериментировать чтобы быть уверенным).

Если одна сторона добавила файл с именем F , а другая - нет, конфликт отсутствует, но если обе стороны добавили файл с именем F существует конфликт добавления / добавления файла F .

Если одна сторона удалила файл, а другая сторона изменила и / или переименовала файл, происходит изменение / удаление или конфликт переименования / удаления для этого файла.

Во всех этих случаях конфликта высокого уровня все три файла остаются в индексе под разными именами. Файл рабочего дерева может также иметь или не содержать некоторые конфликты слияния, если он также существует на низком уровне. Но к этому моменту все конфликты высокого уровня регистрируются в индексе и объявляются как конфликты, которые остановят слияние и получат помощь; файл не будет разрешен в индексе. Примечание: все это находится под контролем стратегии слияния.

Теперь, когда обрабатываются конфликты высокого уровня, мы переходим к тому, существуют ли конфликты низкого уровня:

  • Если ни одна из сторон не изменила файл - если он имеет одинаковое значение ha sh во всех трех слотах индекса - то здесь нет проблем. Файл можно переместить в нулевой слот, используя идентификатор ha sh из любого из трех промежуточных слотов (если, конечно, нет конфликтов высокого уровня).

  • Если одна сторона слияния изменила файл, а другая - нет, тогда проблем нет. Файл можно переместить из любого промежуточного слота, содержащего измененный файл , в нулевой слот подготовки. То есть файл F имеет три хэша в трех слотах. Какой бы из них не совпадал с в слоте-1 га sh, мы отбрасываем его и принимаем другой в качестве результата слияния. Это переходит к нулевому слоту, а остальные три слота стираются (опять же, только если нет конфликтов высокого уровня). Файл рабочего дерева заменяется сохраненной индексной копией.

  • В последнем случае, когда все три входных файла различаются, мы (наконец!) Вызываем фактическое слияние низкого уровня driver.

Драйвер слияния низкого уровня отвечает за фактическое слияние

Именно здесь ваша цель становится видимой. Низкоуровневый драйвер слияния по умолчанию - это линейный драйвер, который генерирует конфликты слияния, которые вы видели. Эта программа встроена в стратегию, но доступна и как вызываемая программа, используя git merge-file. Он принимает три имени входных файлов, объединяет их, как может, самостоятельно, записывает результат обратно в одно из трех имен файлов и завершает работу с нулевым статусом, если считает, что слил три файла правильно, или ненулевой, если он оставил некоторые маркеры конфликта в копии рабочего дерева.

Когда стратегия слияния вызывает этот драйвер слияния низкого уровня, если драйвер слияния выходит из нуля, стратегия слияния копирует полученный файл в нулевой слот индекса и стирает слоты 1 –3, чтобы отметить разрешенный файл. Вы никогда не видите конфликта здесь. Однако, когда он выходит из нуля, файл рабочего дерева не является правильным результатом. Три входа остаются в индексе в слотах 1–3, и объединение в конечном итоге прекратится с конфликтом. (Конечно, стратегия в первую очередь переходит к оставшимся необработанным файлам.)

Если вы установите драйвер слияния , Git будет запускать вашу команду вместо использования его встроенный эквивалент git merge-file. Ваш драйвер должен выйти из нуля или отличного от нуля, как обычно, и независимо от того, как он выходит, должен приложить все усилия для фактического объединения трех файлов в рабочем дереве. Вы можете достичь этого так, как вам нравится: весь процесс зависит от вас.

Итак, если вам нужен более изящный драйвер слияния, который может понимать используемый язык программирования, или использовать слово-ориентированный diff вместо line diff, напиши один! Это просто маленький вопрос программирования .

1 голос
/ 07 февраля 2020

Я обнаружил несколько вещей, которые могут сделать работу по слиянию проще / лучше / более автоматизированной c. Ничто из этого не решит конкретную проблему, с которой вы столкнулись:

  1. При использовании стратегии рекурсивного слияния git (что вы получаете по умолчанию при объединении одной ветви ), вы можете передать -Xpatience -Xdiff-algorithm=patience, что должно заставить его стараться изо всех сил избегать конфликтов.

  2. git subline-merge - замечательный маленький инструмент который сливается с более высокой степенью детализации, чем в каждой строке.

  3. Если у вас есть широко расходящиеся истории изменений git погружение разбивает конфликты на их логические части, так что вы можете иметь дело с ними по одному, и даже может быть в состоянии вообще избежать некоторых конфликтов, выбрав лучший путь через решетку слияния. Требуется время, но оно того стоит, когда все становится сложнее. Это особенно хорошо, когда две истории - все рабочие состояния, потому что вы можете проверить промежуточные точки слияния.

0 голосов
/ 14 января 2020

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

Вы начинаете с файла, который имеет следующее содержание: 

X
...

измените одну сторону на 

Z
...

, а другую сторону на 

A
B
C
X
...

Обратите внимание, что пустые строки ни в коем случае не являются особенными. Теперь вы ожидаете, что новая строка Z с одной стороны совпадает с новой строкой D с другой стороны, эта строка C с другой стороны должна быть в конечном результате (ваш пустой line), и что новые строки A и B являются новыми?

Как Git предположить, что Z должно соответствовать X, а не A, B или C?

Довольно сильно растянутый sh, не так ли?

...