Алгоритм объединения CVS

Question

Какой алгоритм использует CVS при объединении двух ветвей (используя -j)?

• Знает ли тег CVS, ветвь или дата?
• Делает ли это просто diff разного текста (например, с помощью инструмента diff unix)?
• Использует ли он 2-х или 3-х сторонний дифференциал?
• Если он использует 3-стороннюю разность, какую базовую версию он использует?

Спасибо

Answer 1

Я помню, как читал некоторое время назад, что слияние CVS на самом деле использует алгоритм diff3 для выполнения слияния.

Эта статья в PDF Официальное исследование Diff3, выполненное Сандживом Ханной, Кешавом Куналом и Бенджамином С. Пирсом * из Университета Пенсильвании , подробно описывает алгоритм diff3.

Если основное внимание уделяется свойствам самого алгоритма слияния, а не тому, как он интегрируется с CVS.

В ответ на ваши вопросы:

Метка, дата осведомленности

со справочной страницы CVS:

-j tag [: date] Объединить изменения из ревизий, указанных тегом или, когда дата указана, а метка является веткой тег, версия из тега ветки как оно существовало на дату

2-х или 3-х сторонняя и текстовая / бинарная осведомленность

diff3 по умолчанию представляет собой простой текстовый diff. Сравнивает (различает) 3 версии файла.

со страницы руководства diff3:

Если `diff3 'считает, что любой из файлы, которые он сравнивает, являются двоичными ( нетекстовый файл), обычно ошибка, потому что такие сравнения обычно не полезно. Как и в случае с «diff», Вы можете заставить 'diff3' рассмотреть все файлы должны быть текстовыми файлами и сравнить они строка за строкой, используя '-a' или Опции '--text'.

Базовая версия при сравнении

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

Тогда (цитата из статьи) это:

... берет регионы, где O отличается от А или В и объединяет те, которые перекрываются, приводя к чередующейся последовательности стабильный (все реплики равны) и нестабильный (одна или обе реплики изменено) фрагменты показаны на рисунке 1 (с) .3 Наконец, он изучает, что изменилось в каждом куске и решает, что изменится может распространяться, как показано на рисунке 1 (d) - здесь, второй кусок изменен только в A (вставив 4, 5), так что это изменение может быть распространено на B, но четвертый кусок имеет изменения как в А, так и B, так что ничего нельзя распространять.

Answer 2

Вы можете использовать две разные формы команды «слияние», которые делают слегка разные вещи:

1. cvs up -j TAG
2. cvs up -j TAG1 -j TAG2

Разница между вариантами заключается в том, как выбирается "базовая" ревизия, но основной алгоритм любого варианта заключается в том, что для каждого файла различие между двумя ревизиями, выбранными CVS, применяется поверх вашей текущей рабочей копии.

В первой форме база слияния является общим предком данного TAG и редакции рабочей копии. Итак, допустим, ваша локальная ревизия - 1.38 (рев. № 38 на HEAD), а вы объединяете 1.34.4.2 (рев. 2 на 4-й ветке ред. № 34 на HEAD) - общий предок будет 1.34. Я полагаю, что этот вариант выполняет трехстороннее слияние с использованием двух разностей 1.34..1.38 и 1.34..1.34.4.2, что приводит к конфликтам, когда они не совпадают.

Во второй форме вы сами указываете базовую ревизию, поэтому конечный результат примерно такой же, как у cvs diff -r TAG1 -r TAG2 | patch, за исключением получения маркеров конфликта из CVS.

Answer 3

CVS использует три ревизии файла, объединяя различия между двумя в третью. Фактическое слияние не использует никакой информации, кроме трех проверенных файлов. Вы можете увидеть детали в CVS исходном коде. Рассматриваемая функция - RCS_merge в src/rcscmds.c, которая использует call_diff3 из diff/diff3.c (или что-то в этом роде). Вы, конечно, можете удовлетворить свое любопытство, посмотрев CVS источников самостоятельно.