合併 (版本控制)

維基百科,自由的百科全書
跳至導覽 跳至搜尋
例子:一個項目的版本控制的歷史。合併為紅色箭頭

合併版本控制中是指當一個文件在多個獨立分支中被修改後如何合併這些修改成為一個文件的操作。

合併可以是版本控制軟件自動執行,但如果有衝突英語conflict (version control),就需要考慮手工合併。

合併算法[編輯]

合併算法是一個熱點研究領域,有多種不同的算法。

三路合併[編輯]

三路合併示意圖
C是最初, A與B是從C派生, D是最新輸出版本

三路合併(three-way merge),首先考慮對文件A、文件B以及它們的共同祖先文件C做差異分析。對於文件中的每節(sector),如果上述三個文件中有兩個文件該節的內容一致,那麼拋棄文件C中該節的內容,保留與文件C中不同的內容放到結果文件中。如果該節在三個文件中都不同,那麼這個衝突需要手工合併。

三路合併被程序diff3英語diff3實現,是基於文件鎖的版本控制系統到基於合併的版本控制系統轉變的核心。[1]CVS廣泛使用.

遞歸三路合併[編輯]

三路合併算法的基礎技術是找到被合併文件的共同祖先文件。在遇到十字交叉合併(criss-cross merge)[2]時,不存在獨一無二最小共同祖先。

"Criss-cross-merge「問題。在左半邊,2個區域被修改, . 是兩個連續修改版本。右半邊是解決辦法:一個虛擬祖先(選線圓圈)被創建.

Git採取了遞歸三路合併(Recursive three-way merge),對沒有共同祖先的一對文件遞歸創建虛擬祖先。這一方法還可以用於有向無環圖

模糊修補包算法[編輯]

修補包是一個文件,包含另一個文件的改變的描述。Unix傳統使用修補包傳播一個文本文件的改變,這個修補包可用命令"diff -u"生成,然後用命令patch把修補包應用到一個文本文件。

patch程序也可以把一個修補包用於與最初產生該包的文件不是完全相同的文件。這稱作模糊修補包應用(fuzzy patch application)。 GNU arch採用了這種方法。但模糊修補包應用是一種不太可信的辦法,在上下文太少情況下可能會誤用。

編織合併[編輯]

編織合併(Weave merge)算法跟蹤每行是被增加或是刪除,產生結果信息。如果在一個版本中該行被刪除,則結果文件就不包含該行。BitKeeperGNU BazaarCodeville採用了此方法,對三路合併出錯的情形能產生正確結果。

修補包交換[編輯]

修補包交換(Patch commutation)改變修補包的應用順序,形成一線性歷史。效果上,當兩個修補包產生於同一個環境,合併時,一個修補包被重寫以便它可以在另一個修補包執行完畢後才使用。例如,修補包A在文件F的行7之後增加了行"X",修補包B在文件F的行310之後增加了行"Y",B需要重寫為對文件F的行311之後增加行"Y",以便能在修補包A使用後再使用修補包B。

DarcsGit (稱作"rebasing")採用了這一方法。

"patchutils" package中的Unix程序flipdiff實現了修補包交換.

參考文獻[編輯]

  1. ^ Sink, Eric. Source Control HOWTO. [5 Feb 2013]. 
  2. ^ Cohen, Bram. The criss-cross merge case. Git (郵件列表). 2005-04-28. Message-ID <Pine.LNX.4.44.0504271254120.4678-100000@wax.eds.org>. 

外部連結[編輯]