В системе контроля версий слияние (также называемое интеграцией) — это фундаментальная операция, которая согласовывает многочисленные изменения , внесенные в коллекцию файлов с контролем версий. Чаще всего это необходимо, когда файл модифицируется в двух независимых ветвях и впоследствии объединяется. В результате получается единая коллекция файлов, содержащая оба набора изменений.
В некоторых случаях слияние может выполняться автоматически, поскольку имеется достаточная историческая информация для восстановления изменений, и изменения не конфликтуют . В других случаях человек должен решить, что именно должны содержать полученные файлы. Многие программные инструменты контроля версий включают возможности слияния.
Существует два типа слияний: неструктурированные и структурированные.
Неструктурированное слияние работает с необработанным текстом, обычно используя строки текста в качестве атомарных единиц. Это то, что используют инструменты Unix (diff/patch) и инструменты CVS (SVN, Git). Это ограничено, поскольку строка текста не представляет структуру исходного кода.
Инструменты структурированного слияния, или слияние AST, превращают исходный код в полностью разрешенный AST . Это позволяет осуществлять детальное слияние, исключающее ложные конфликты.
Автоматическое слияние — это то, что делает программное обеспечение для контроля версий, когда оно согласовывает изменения, произошедшие одновременно (в логическом смысле). Кроме того, другие программы используют автоматическое объединение, если они позволяют одновременно редактировать один и тот же контент. Например, Википедия позволяет двум людям одновременно редактировать одну и ту же статью; когда последний участник сохраняет изменения, их изменения объединяются со статьей, а не перезаписывают предыдущий набор изменений. [1] Ручное слияние — это то, к чему людям приходится прибегать (возможно, с помощью инструментов слияния), когда им приходится согласовывать отличающиеся файлы. Например, если две системы имеют слегка отличающиеся версии файла конфигурации, и пользователь хочет иметь хорошие вещи в обеих, этого обычно можно достичь, объединив файлы конфигурации вручную, выбрав нужные изменения из обоих источников (это также называется двусторонним слиянием). Ручное слияние также требуется, когда автоматическое слияние сталкивается с конфликтом изменений; например, очень немногие инструменты автоматического слияния могут объединить два изменения в одну и ту же строку кода (скажем, одно меняет имя функции, а другое добавляет комментарий). В этих случаях системы контроля версий обращаются к пользователю с просьбой указать предполагаемый результат слияния.
Существует много разных подходов к автоматическому слиянию с небольшими различиями. Наиболее известные алгоритмы слияния включают трехстороннее слияние, рекурсивное трехстороннее слияние, применение нечетких патчей, переплетение и коммутацию патчей.
Трехстороннее слияние выполняется после автоматического анализа различий между файлом «A» и файлом «B», а также с учетом происхождения или общего предка обоих файлов «C». Это грубый метод слияния, но он широко применим, поскольку для реконструкции объединяемых изменений требуется только один общий предок. Трехстороннее слияние можно выполнить для необработанного текста (последовательности строк) или структурированных деревьев. [2]
Трехстороннее слияние ищет разделы, одинаковые только в двух из трех файлов. В этом случае существует две версии раздела, причем версия, находящаяся в общем предке «C», отбрасывается, а отличающаяся версия сохраняется в выходных данных. Если «A» и «B» согласны, это то, что появляется в выходных данных. Раздел, одинаковый в «A» и «C», выводит измененную версию в «B», а также раздел, одинаковый в «B» и «C», выводит версию в «A».
Разделы, которые во всех трёх файлах различаются, помечаются как конфликтная ситуация и оставляются на усмотрение пользователя.
Трехстороннее слияние реализовано вездесущей программой diff3 и стало центральным нововведением, которое позволило перейти от систем контроля версий, основанных на блокировке файлов, к системам контроля версий, основанным на слиянии. Он широко используется системой параллельных версий (CVS).
Инструменты контроля версий на основе трехстороннего слияния широко распространены, но этот метод в основном зависит от поиска общего предка объединяемых версий.
Бывают неловкие случаи, особенно «перекрестное слияние» [3] , когда уникального последнего общего предка модифицированных версий не существует.
К счастью, в этом случае можно показать, что существует не более двух возможных предков-кандидатов, и рекурсивное трехстороннее слияние создает виртуального предка , сначала объединяя неуникальных предков. Это слияние само по себе может столкнуться с той же проблемой, поэтому алгоритм объединяет их рекурсивно . Поскольку в истории имеется конечное число версий, процесс гарантированно в конечном итоге завершится. Этот метод используется инструментом контроля версий 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, смещает номера строк на единицу.
Коммутация патчей формально хорошо изучена, но алгоритмы разрешения конфликтов слияния при коммутации патчей все еще остаются открытыми исследовательскими вопросами. Тем не менее, можно доказать, что коммутация патчей дает «правильные» результаты слияния, тогда как другие стратегии слияния в основном представляют собой эвристики, которые пытаются создать то, что хотят видеть пользователи.
Программа Unix flipdiffиз пакета «patchutils» реализует коммутацию исправлений для традиционных исправлений , создаваемых командой diff -u.
Слияние с переплетением — это алгоритм, который не использует общего предка для двух файлов. Вместо этого он отслеживает, как отдельные строки добавляются и удаляются в производных версиях файлов, и на основе этой информации создает объединенный файл.
Для каждой строки в производных файлах weave merge собирает следующую информацию: какие строки предшествуют ей, какие следуют за ней, а также была ли она удалена на каком-то этапе истории производной строки. Если в какой-то момент в какой-либо производной строке была удалена строка, она не должна присутствовать в объединенной версии. Остальные строки должны присутствовать в объединенной версии.
Строки сортируются в таком порядке, где каждая строка находится после всех строк, которые предшествовали ей в определенный момент истории, и перед всеми строками, которые следовали за ней в определенный момент истории. Если эти ограничения не обеспечивают полного порядка для всех строк, то строки, которые не упорядочены друг относительно друга, являются конфликтующими дополнениями.
Слияние Weave, очевидно, использовалось коммерческим инструментом контроля версий BitKeeper и может справиться с некоторыми проблемными случаями, когда трехстороннее слияние дает неверные или плохие результаты. Это также один из вариантов слияния инструмента контроля версий GNU Bazaar , который используется в Codeville. [ нужна цитата ]
