В системе управления версиями слияние (также называемое интеграцией) является фундаментальной операцией, которая согласовывает множественные изменения, внесенные в коллекцию файлов с контролем версий. Чаще всего это необходимо, когда файл изменяется в двух независимых ветвях и затем объединяется. Результатом является единая коллекция файлов, которая содержит оба набора изменений.
В некоторых случаях слияние может быть выполнено автоматически, поскольку имеется достаточно исторической информации для реконструкции изменений, и изменения не конфликтуют . В других случаях человек должен решить, что именно должны содержать полученные файлы. Многие программные средства контроля версий включают возможности слияния.
Существует два типа слияний: неструктурированные и структурированные.
Неструктурированное слияние работает с сырым текстом, обычно используя строки текста как атомарные единицы. Это то, что используют инструменты Unix (diff/patch) и инструменты CVS (SVN, Git). Это ограниченное [ мнение ] , так как строка текста не представляет структуру исходного кода.
Инструменты структурированного слияния или слияние AST превращают исходный код в полностью решенный AST . Это позволяет выполнять мелкозернистое слияние, избегая ложных конфликтов. [ необходима цитата ]
Автоматическое слияние — это то, что делает программное обеспечение для контроля версий, когда оно согласовывает изменения, которые произошли одновременно (в логическом смысле). Кроме того, другие части программного обеспечения развертывают автоматическое слияние, если они позволяют редактировать один и тот же контент одновременно. Например, Wikipedia позволяет двум людям редактировать одну и ту же статью одновременно; когда последний участник сохраняет, его изменения объединяются в статью, а не перезаписывают предыдущий набор изменений. [1] Ручное слияние — это то, к чему людям приходится прибегать (возможно, с помощью инструментов слияния), когда им нужно согласовать файлы, которые различаются. Например, если две системы имеют немного отличающиеся версии файла конфигурации, и пользователь хочет иметь хороший материал в обеих, этого обычно можно достичь, объединив файлы конфигурации вручную и выбрав нужные изменения из обоих источников (это также называется двусторонним слиянием). Ручное слияние также требуется, когда автоматическое слияние сталкивается с конфликтом изменений; например, очень немногие автоматические инструменты слияния могут объединить два изменения в одной и той же строке кода (например, одно, которое изменяет имя функции, и другое, которое добавляет комментарий). В этих случаях системы контроля версий прибегают к тому, чтобы пользователь указал предполагаемый результат слияния.
Существует много различных подходов к автоматическому слиянию с тонкими различиями. Наиболее заметные алгоритмы слияния включают трехстороннее слияние, рекурсивное трехстороннее слияние, применение нечетких патчей, слияние сплетений и коммутацию патчей.
Трехстороннее слияние выполняется после автоматизированного анализа различий между файлом "A" и файлом "B", при этом также учитывается происхождение или общий предок обоих файлов "C". Это грубый метод слияния, но широко применимый, поскольку для реконструкции изменений, которые должны быть объединены, требуется только один общий предок. Трехстороннее слияние может быть выполнено для необработанного текста (последовательности строк) или для структурированных деревьев. [2]
Трехстороннее слияние ищет разделы, которые совпадают только в двух из трех файлов. В этом случае есть две версии раздела, и версия, которая находится в общем предке "C", отбрасывается, в то время как версия, которая отличается, сохраняется в выводе. Если "A" и "B" совпадают, то это то, что появляется в выводе. Раздел, который совпадает в "A" и "C", выводит измененную версию в "B", и аналогично раздел, который совпадает в "B" и "C", выводит версию в "A".
Разделы, которые различаются во всех трех файлах, помечаются как конфликтная ситуация и оставляются на усмотрение пользователя.
Трехстороннее слияние реализовано вездесущей программой diff3 и стало центральным нововведением, позволившим перейти от систем контроля версий на основе блокировки файлов к системам контроля версий на основе слияния. Оно широко используется в Concurrent Versions System (CVS).
Широко распространены инструменты контроля версий, основанные на трехстороннем слиянии, но в основе этой методики лежит поиск общего предка версий, подлежащих слиянию.
Существуют неловкие случаи, в частности, «перекрестное слияние» [3], когда уникального последнего общего предка модифицированных версий не существует.
К счастью, в этом случае можно показать, что существует максимум два возможных предка-кандидата, и рекурсивное трехстороннее слияние создает виртуального предка , сначала объединяя неуникальных предков. Это слияние само может страдать от той же проблемы, поэтому алгоритм рекурсивно объединяет их. Поскольку в истории есть конечное число версий, процесс гарантированно в конечном итоге завершится. Этот метод используется инструментом контроля ревизий Git .
(Реализация рекурсивного слияния Git также обрабатывает другие неудобные случаи, например, когда файл изменяется в одной версии и переименовывается в другой, но это расширения его реализации трехстороннего слияния; они не являются частью метода поиска трех версий для слияния.)
Рекурсивное трехстороннее слияние может использоваться только в ситуациях, когда инструмент имеет знания о полном ациклическом графе предков (DAG) производных, которые должны быть объединены. Следовательно, его нельзя использовать в ситуациях, когда производные или слияния не полностью определяют своего родителя(ей).
Патч — это файл, содержащий описание изменений в файле. В мире Unix существовала традиция распространять изменения в текстовых файлах как патчи в формате, который создается " diff -u". Этот формат затем может использоваться программой патча для повторного применения (или удаления) изменений в (или из) текстового файла или структуры каталогов, содержащей текстовые файлы.
Однако программа патча также имеет некоторые возможности для применения патча в файле, который не совсем похож на исходный файл, который использовался для создания патча. Этот процесс называется нечетким применением патча и приводит к своего рода асимметричному трехстороннему слиянию, где изменения в патче отбрасываются, если программа патча не может найти место, в котором их можно применить.
Как CVS начинался как набор скриптов на diff3 , GNU arch начинался как набор скриптов на patch. Однако применение нечетких патчей является относительно ненадежным методом, иногда неправильно применяющим патчи, которые имеют слишком мало контекста (особенно те, которые создают новый файл), иногда отказывающимся применять удаления, которые сделали оба производных.
Коммутация патчей используется в Darcs для слияния изменений, а также реализована в git (но называется «перебазированием»). Слияние коммутации патчей означает изменение порядка патчей (т. е. описаний изменений) так, чтобы они формировали линейную историю. По сути, когда два патча создаются в контексте общей ситуации, при слиянии один из них переписывается так, что кажется, что он сделан в контексте другого.
Коммутация патчей требует, чтобы точные изменения, которые сделали производные файлы, были сохранены или могли быть реконструированы. Из этих точных изменений можно вычислить, как один из них должен быть изменен, чтобы перебазировать его на другой. Например, если патч A добавляет строку "X" после строки 7 файла F, а патч B добавляет строку "Y" после строки 310 файла F, B должен быть переписан, если он перебазирован на A: строка должна быть добавлена на строку 311 файла F, потому что строка, добавленная в A, смещает номера строк на единицу.
Коммутация патчей была изучена формально, но алгоритмы для решения конфликтов слияния при коммутации патчей все еще остаются открытыми исследовательскими вопросами. Однако можно доказать, что коммутация патчей дает «правильные» результаты слияния [4], тогда как другие стратегии слияния в основном являются эвристиками, которые пытаются производить то, что хотят видеть пользователи.
Программа Unix flipdiffиз пакета «patchutils» реализует коммутацию патчей для традиционных патчей , созданных с помощью diff -u.
Weave merge — это алгоритм, который не использует общего предка для двух файлов. Вместо этого он отслеживает, как добавляются и удаляются отдельные строки в производных версиях файлов, и создает объединенный файл на основе этой информации.
Для каждой строки в производных файлах weave merge собирает следующую информацию: какие строки предшествуют ей, какие следуют за ней и была ли она удалена на каком-то этапе истории любой производной. Если какая-либо производная имела удаленную строку в какой-то момент, она не должна присутствовать в объединенной версии. Для других строк они должны присутствовать в объединенной версии.
Строки сортируются в порядке, где каждая строка находится после всех строк, которые предшествовали ей в какой-то момент истории, и перед всеми строками, которые следовали за ней в какой-то момент истории. Если эти ограничения не дают общего порядка для всех строк, то строки, которые не имеют порядка относительно друг друга, являются дополнениями, которые конфликтуют.
Weave merge, по-видимому, использовался коммерческим инструментом контроля версий BitKeeper и может справиться с некоторыми проблемными случаями, когда трехстороннее слияние дает неправильные или плохие результаты. Это также один из вариантов слияния инструмента контроля версий GNU Bazaar , и он используется в Codeville. [ необходима цитата ]
