Слияние (контроль версий)

В версий системе контроля слияние (также называемое интеграцией) — это фундаментальная операция, которая согласовывает многочисленные изменения, внесенные в коллекцию файлов с контролем версий. Чаще всего это необходимо, когда файл модифицируется в двух независимых ветвях и впоследствии объединяется. В результате получается единая коллекция файлов, содержащая оба набора изменений.

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

Виды слияний

Существует два типа слияний: неструктурированные и структурированные.

Неструктурированное слияние

Неструктурированное слияние работает с необработанным текстом, обычно используя строки текста как атомарные. единицы. Это то, что используют инструменты Unix (diff/patch) и инструменты CVS (SVN, Git). Это ограничено ^{[ мнение ]}, поскольку строка текста не представляет структуру исходного кода.

Структурированное слияние

Инструменты структурированного слияния, или слияние AST, превращают исходный код в полностью решен AST . Это позволяет осуществлять детальное слияние, исключающее ложные конфликты. ^{[ нужна ссылка ]}

Рабочий процесс

Автоматическое слияние — это то, что делает программное обеспечение для контроля версий, когда оно согласовывает изменения, произошедшие одновременно (в логическом смысле). Кроме того, другие программы используют автоматическое объединение, если они позволяют одновременно редактировать один и тот же контент. Например, Arc.Ask3.Ru позволяет двум людям одновременно редактировать одну и ту же статью; когда последний участник сохраняет изменения, их изменения объединяются со статьей, а не перезаписывают предыдущий набор изменений. ^{[ 1 ]} Ручное слияние — это то, к чему людям приходится прибегать (возможно, с помощью инструментов слияния), когда им приходится согласовывать отличающиеся файлы. Например, если две системы имеют немного отличающиеся версии файла конфигурации, и пользователь хочет иметь хорошие результаты в обеих, этого обычно можно достичь, объединив файлы конфигурации вручную и выбрав нужные изменения из обоих источников (это также называемое двусторонним слиянием). Ручное слияние также требуется, когда автоматическое слияние сталкивается с конфликтом изменений; например, очень немногие инструменты автоматического слияния могут объединить два изменения в одну и ту же строку кода (скажем, одно меняет имя функции, а другое добавляет комментарий). В этих случаях системы контроля версий обращаются к пользователю с просьбой указать предполагаемый результат слияния.

Алгоритмы слияния

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

Трехстороннее слияние

Схема трехстороннего слияния — C — это источник, A и B — производные от C, а D — новая выходная версия.

Трехстороннее слияние выполняется после автоматического анализа различий между файлом «A» и файлом «B», а также с учетом происхождения или общего предка обоих файлов «C». Это грубый метод слияния, но он широко применим, поскольку для реконструкции объединяемых изменений требуется только один общий предок. Трехстороннее слияние можно выполнить для необработанного текста (последовательности строк) или структурированных деревьев. ^{[ 2 ]}

Трехстороннее слияние ищет разделы, одинаковые только в двух из трех файлов. В этом случае существует две версии раздела, причем версия, находящаяся в общем предке «C», отбрасывается, а отличающаяся версия сохраняется в выходных данных. Если «A» и «B» согласны, это то, что появляется в выходных данных. Раздел, одинаковый в «A» и «C», выводит измененную версию в «B», а также раздел, одинаковый в «B» и «C», выводит версию в «A».

Разделы, которые во всех трёх файлах различаются, помечаются как конфликтная ситуация и оставляются на усмотрение пользователя.

Трехстороннее слияние реализовано вездесущей программой diff3 и стало центральным нововведением, которое позволило перейти от систем контроля версий, основанных на блокировке файлов, к системам контроля версий, основанным на слиянии. Он широко используется системой параллельных версий (CVS).

Рекурсивное трехстороннее слияние

Инструменты контроля версий на основе трехстороннего слияния широко распространены, но этот метод в основном зависит от поиска общего предка объединяемых версий.

Бывают неловкие случаи, особенно «перекрестное слияние», ^{[ 3 ]} где не существует уникального последнего общего предка модифицированных версий.

Проблема «перекрестного слияния» в системе контроля версий программного обеспечения. В левой половине изменяются 2 области, $X$ и $Y$ . $X'$ и $X''$ представляют собой последовательно модифицированные версии. Решение показано в правой половине: создается виртуальный предок (пунктирный круг).

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

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

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

Приложение нечеткого патча

Патч — это файл, содержащий описание изменений файла. В мире Unix существует традиция распространять изменения в текстовых файлах в виде исправлений в формате, создаваемом командой « diff -u». Этот формат затем может использоваться программой исправления для повторного применения (или удаления) изменений в (или из) текстового файла или структуры каталогов, содержащей текстовые файлы.

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

Подобно тому, как CVS начинался как набор скриптов в diff3 , GNU Arch начинался как набор скриптов в патче. Однако применение нечетких патчей — относительно ненадежный метод, иногда неправильно применяющий патчи, которые имеют слишком мало контекста (особенно те, которые создают новый файл), иногда отказывается применять удаления, которые сделали оба производных.

Патч коммутации

Коммутация патчей используется в Darcs для объединения изменений, а также реализована в git (но называется «перебазированием»). Объединение коммутации патчей означает изменение порядка патчей (т.е. описаний изменений) таким образом, чтобы они формировали линейную историю. Фактически, когда два патча создаются в контексте общей ситуации, при слиянии один из них перезаписывается так, что кажется, что он сделан в контексте другого.

Коммутация исправлений требует, чтобы точные изменения, внесшие производные файлы, были сохранены или могли быть восстановлены. На основе этих точных изменений можно вычислить, как следует изменить одно из них, чтобы перебазировать его на другое. Например, если патч A добавляет строку «X» после строки 7 файла F, а патч B добавляет строку «Y» после строки 310 файла F, B необходимо переписать, если он основан на A: строка должна быть добавлена в строка 311 файла F, поскольку строка, добавленная в A, смещает номера строк на единицу.

Коммутация патчей формально хорошо изучена, но алгоритмы разрешения конфликтов слияния при коммутации патчей все еще остаются открытыми исследовательскими вопросами. Однако можно доказать, что коммутация патчей дает «правильные» результаты слияния. ^{[ 4 ]} где другие стратегии слияния в основном представляют собой эвристики, пытающиеся создать то, что хотят видеть пользователи.

Программа Unix flipdiff из пакета «patchutils» реализует коммутацию патчей для традиционных патчей, созданных с помощью diff -u.

Переплетение слияния

Слияние с переплетением — это алгоритм, который не использует общего предка для двух файлов. Вместо этого он отслеживает, как отдельные строки добавляются и удаляются в производных версиях файлов, и на основе этой информации создает объединенный файл.

Для каждой строки в производных файлах weave merge собирает следующую информацию: какие строки предшествуют ей, какие следуют за ней, а также была ли она удалена на каком-то этапе истории производной строки. Если в какой-то момент из какой-либо производной строки была удалена строка, она не должна присутствовать в объединенной версии. Остальные строки должны присутствовать в объединенной версии.

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

Слияние Weave, очевидно, использовалось коммерческим инструментом контроля версий BitKeeper и может справиться с некоторыми проблемными случаями, когда трехстороннее слияние дает неверные или плохие результаты. Это также один из вариантов слияния инструмента контроля версий GNU Bazaar , который используется в Codeville. ^{[ нужна ссылка ]}

См. также

Ссылки

^ Справка:Редактировать конфликт#Предотвращение
^ Линдхольм, Танкред (2004). «Трёхстороннее слияние XML-документов» . Материалы симпозиума ACM 2004 года по разработке документов . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 1–10. дои : 10.1145/1030397.1030399 . ISBN 1581139381 . S2CID 2863413 .
^ Коэн, Брэм (28 апреля 2005 г.). «Дело о перекрестном слиянии» . Git (список рассылки). Идентификатор сообщения < [адрес электронной почты защищен] >.
^ «Некоторые свойства теории заплат Дарка» (PDF) . , следствие 2

[1] Справка:Редактировать конфликт#Предотвращение

[2] Линдхольм, Танкред (2004). «Трёхстороннее слияние XML-документов» . Материалы симпозиума ACM 2004 года по разработке документов . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 1–10. дои : 10.1145/1030397.1030399 . ISBN 1581139381 . S2CID 2863413 .

[3] Коэн, Брэм (28 апреля 2005 г.). «Дело о перекрестном слиянии» . Git (список рассылки). Идентификатор сообщения < [адрес электронной почты защищен] >.

[4] «Некоторые свойства теории заплат Дарка» (PDF) . , следствие 2

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]