Слияние (контроль версий) - Merge (version control)
В системе управления версиями , слияние (также называемая интеграции) является фундаментальной операцией , которая примиряет несколько изменений , внесенных в версию контролируемой коллекции файлов. Чаще всего это необходимо, когда файл изменяется в двух независимых ветвях и впоследствии объединяется. В результате получается единый набор файлов, содержащий оба набора изменений.
В некоторых случаях слияние может быть выполнено автоматически, поскольку имеется достаточно исторической информации для восстановления изменений, и изменения не конфликтуют . В других случаях человек должен решить, что именно должны содержать полученные файлы. Многие программные инструменты для контроля версий включают возможности слияния.
Типы слияний
Есть два типа слияния: автоматическое и ручное.
Автоматическое слияние
Автоматическое слияние - это то, что делает программное обеспечение для контроля версий, когда оно согласовывает изменения, которые произошли одновременно (в логическом смысле). Кроме того, в других программах используется автоматическое объединение, если они позволяют редактировать один и тот же контент одновременно. Например, Википедия позволяет двум людям редактировать одну и ту же статью одновременно; когда последний участник сохраняет, их изменения объединяются в статью вместо перезаписи предыдущего набора изменений.
Ручное слияние
Ручное слияние - это то, к чему люди должны прибегать (возможно, с помощью инструментов слияния), когда им нужно согласовать файлы, которые отличаются друг от друга. Например, если две системы имеют немного разные версии файла конфигурации, и пользователь хочет иметь хорошие возможности в обеих, это обычно может быть достигнуто путем объединения файлов конфигурации вручную, путем выбора необходимых изменений из обоих источников (это также называется двусторонним слиянием). Ручное слияние также требуется, когда автоматическое слияние приводит к конфликту изменений; например, очень немногие инструменты автоматического слияния могут объединить два изменения в одной и той же строке кода (скажем, один, который изменяет имя функции, а другой, который добавляет комментарий). В этих случаях системы контроля версий прибегают к помощи пользователя, чтобы указать предполагаемый результат слияния.
Алгоритмы слияния
Есть много разных подходов к автоматическому слиянию с небольшими различиями. Наиболее известные алгоритмы слияния включают трехстороннее слияние, рекурсивное трехстороннее слияние, применение нечетких исправлений, слияние с переплетением и коммутацию исправлений.
Трехстороннее слияние
Трехстороннее слияние выполняется после автоматического анализа различий между файлом «A» и файлом «B» с учетом происхождения или общего предка обоих файлов «C». Это грубый метод слияния, но он широко применим, поскольку для воссоздания изменений, которые должны быть слиты, требуется только один общий предок.
Трехстороннее слияние ищет разделы, которые совпадают только в двух из трех файлов. В этом случае есть две версии раздела, и версия, которая находится в общем предке "C", отбрасывается, а отличающаяся версия сохраняется в выводе. Если «A» и «B» совпадают, это то, что появляется на выходе. Раздел, который совпадает в «A» и «C», выводит измененную версию в «B», и аналогично раздел, который совпадает в «B» и «C», выводит версию в «A».
Разделы, которые различаются во всех трех файлах, помечаются как конфликтная ситуация и оставляются на усмотрение пользователя.
Трехстороннее слияние реализуется повсеместной программой diff3 и было центральным нововведением, позволившим перейти от систем контроля версий на основе блокировки файлов к системам контроля версий на основе слияния. Он широко используется Системой одновременных версий (CVS).
Рекурсивное трехстороннее слияние
Инструменты контроля версий, основанные на трехстороннем слиянии, широко распространены, но методика в основном зависит от поиска общего предка версий, которые будут слиты.
Бывают неудобные случаи, особенно «перекрестное слияние», когда уникальный последний общий предок модифицированных версий не существует.
К счастью, в этом случае можно показать, что существует не более двух возможных предков-кандидатов, а рекурсивное трехстороннее слияние создает виртуального предка , сначала объединяя неуникальные предки. Это слияние само может иметь ту же проблему, поэтому алгоритм рекурсивно объединяет их. Поскольку в истории есть конечное число версий, процесс гарантированно завершится. Этот метод используется инструментом контроля версий Git .
(Реализация рекурсивного слияния Git также справляется с другими неудобными случаями, например, когда файл изменяется в одной версии и переименовывается в другой, но они являются расширениями его реализации трехстороннего слияния, а не частью метода поиска трех версий для слияния.)
Рекурсивное трехстороннее слияние можно использовать только в ситуациях, когда инструмент знает об общем ациклическом графе, ориентированном на предков (DAG) производных, которые необходимо слить. Следовательно, его нельзя использовать в ситуациях, когда производные инструменты или слияния не полностью определяют своих родительских (их) родителя (ов).
Приложение Fuzzy patch
Пластырь представляет собой файл , который содержит описание изменений в файл. В мире Unix существует традиция распространять изменения в текстовые файлы в виде исправлений в формате, который создается командой " diff -u". Затем этот формат может использоваться программой исправления для повторного применения (или удаления) изменений в текстовом файле (или из него) или структуре каталогов, содержащей текстовые файлы.
Однако программа исправления также имеет некоторые средства для применения исправления к файлу, который не совсем похож на исходный файл, который использовался для создания исправления. Этот процесс называется применением нечеткого исправления и приводит к своего рода асимметричному трехстороннему слиянию, при котором изменения в исправлении отбрасываются, если программа исправления не может найти место, в котором их можно применить.
Подобно тому, как CVS начиналась как набор сценариев на diff3 , GNU arch начиналась как набор сценариев на патче. Однако приложение нечетких исправлений - относительно ненадежный метод, иногда неправильно применяющие исправления со слишком малым контекстом (особенно те, которые создают новый файл), иногда отказываясь применять удаления, которые сделали обе производные.
Коммутация патча
Коммутация патчей используется в Darcs для объединения изменений, а также реализована в git (но называется «перебазированием»). Слияние коммутации исправлений означает изменение порядка исправлений (т. Е. Описаний изменений) так, чтобы они образовывали линейную историю. Фактически, когда два патча создаются в контексте общей ситуации, при слиянии один из них перезаписывается так, что кажется, что он выполняется в контексте другого.
Коммутация патчей требует, чтобы точные изменения, внесенные в производные файлы, сохранялись или могли быть восстановлены. По этим точным изменениям можно вычислить, как следует изменить одно из них, чтобы переустановить его на другое. Например, если патч A добавляет строку «X» после строки 7 файла F, а патч B добавляет строку «Y» после строки 310 файла F, B должен быть переписан, если он перебазирован на A: строка должна быть добавлена на строка 311 файла F, потому что строка, добавленная в A, смещает номера строк на единицу.
Коммутация патчей хорошо изучена формально, но алгоритмы решения конфликтов слияния при коммутации патчей все еще остаются открытыми вопросами исследования. Однако можно доказать, что коммутация патчей дает «правильные» результаты слияния, тогда как другие стратегии слияния в основном представляют собой эвристику, пытающуюся произвести то, что хотят видеть пользователи.
Программа flipdiff для Unix из пакета "patchutils" реализует коммутацию исправлений для традиционных исправлений, созданных командой diff -u.
Плетение слияния
Слияние плетения - это алгоритм, который не использует общего предка для двух файлов. Вместо этого он отслеживает, как отдельные строки добавляются и удаляются в производных версиях файлов, и создает объединенный файл на основе этой информации.
Для каждой строки в производных файлах weave merge собирает следующую информацию: какие строки предшествуют ей, какие следуют за ней, и была ли она удалена на каком-то этапе истории производной. Если в какой-то момент строка из какого-либо производного инструмента была удалена, она не должна присутствовать в объединенной версии. Для остальных строк они должны присутствовать в объединенной версии.
Строки сортируются в порядке, в котором каждая строка находится после всех строк, которые предшествовали ей в какой-то момент истории, и перед всеми строками, которые следовали за ней в какой-то момент истории. Если эти ограничения не дают полного упорядочения для всех строк, то строки, не имеющие упорядочения по отношению друг к другу, являются конфликтующими дополнениями.
Слияние Weave, по-видимому, использовалось коммерческим инструментом контроля версий BitKeeper и может справиться с некоторыми проблемными случаями, когда трехстороннее слияние дает неправильные или плохие результаты. Это также один из вариантов слияния инструмента контроля версий GNU Bazaar , который используется в Codeville .