理解 Darcs/補丁理論和衝突



衝突

到目前為止，我們只處理了合併彼此不衝突的補丁。下一個感興趣的問題是 darcs 在它們確實發生衝突時應該如何表現。

考慮之前的 darcs 駭客馬拉松示例，與往常一樣，Arjan 決定購物清單需要一些啤酒。在這種情況下，Ganesh 決定你不能只靠蘋果和餅乾生活，並記錄了一個將“義大利麵”新增到 s_list 檔案的補丁。現在他想知道 Arjan 在做什麼，因此將啤酒補丁拉到他的倉庫中，但糟糕！Arjan 和 Ganesh 的補丁衝突了！darcs 在這裡應該如何表現？

Arjan 和 Ganesh 的補丁衝突

darcs 的答案是，兩個補丁都互相抵消，因此它們都沒有任何效果。最終的購物清單既沒有啤酒，也沒有義大利麵。這聽起來可能令人震驚，但並不像你想象的那麼糟糕。Darcs 不會靜默地刪除你的程式碼。在取消兩個補丁後，它會在你的工作目錄中新增第三個補丁，該補丁指示衝突的雙方，以便你可以選擇你想要的那個。因此，你應用的任何解決方案都是一個依賴於兩個衝突補丁的第三個補丁。如果你在此時對 Ganesh 的倉庫執行了 darcs whatsnew，你將得到類似以下內容

v v v v v v 
beer
-----------
pasta
^ ^ ^ ^ ^ ^ 

我們如何知道我們有衝突？

直觀地顯而易見的是，Arjan 的補丁與 Ganesh 的衝突，但如果直覺不能轉化為實際的 Haskell 程式碼，那麼直覺就毫無用處。因此，第一個問題是首先知道我們是否發生了衝突。

所有這些都歸結為交換。如果兩個補丁的交換未定義，我們就會有衝突。讓我們簡要回顧一下上一章中描述的合併過程。上一章。當 Ganesh 試圖拉取 Arjan 的補丁時，他試圖透過執行以下順序來使補丁適應他的環境：反轉他自己的補丁，應用 Arjan 的補丁 $A$，將反轉的補丁與 Arjan 的補丁交換，並丟棄他反轉的補丁的邪惡繼姐妹。正如我們所知，反轉補丁很容易。Ganesh 的補丁被反轉為一些從 s_list 檔案的第 3 行刪除“義大利麵”的內容。另一方面，當我們嘗試將其與 Arjan 的補丁交換時，我們遇到了故障。

為什麼？僅僅因為這就是我們定義兩種型別的補丁之間的交換方式。例如，Ganesh 和 Arjan 的補丁都是塊補丁。兩個相同檔案塊補丁的交換在 darcs 中使用類似於以下內容的 Haskell 程式碼定義（從 PatchCommute.lhs 簡化而來）

commuteHunk :: FileName -> (FilePatchType, FilePatchType) -> Maybe (Patch, Patch)
commuteHunk f (p1@(Hunk line2 old2 new2), p2@(Hunk line1 old1 new1))
  | line1 + lengthnew1 < line2 = Just ...
  | line1 + lengthnew1 == line2 && nonZero = Just ...
  | line2 + lengthold2 < line1 = Just ...
  | line2 + lengthold2 == line1 && nonZero = Just ...
  | otherwise = Nothing
  where nonZero = lengthold2 /= 0 && lengthold1 /= 0 && lengthnew2 /= 0 && lengthnew1 /= 0 
        lengthnew1 = length new1
        lengthnew2 = length new2
        lengthold1 = length old1
        lengthold2 = length old2

只定義了四種情況。前兩種情況涵蓋了 p1 發生在 p2 之前檔案部分的情況（即使像第二種情況那樣撞到它）。後兩種情況涵蓋了相反的情況（p2 位於檔案中的 p1 之前的部分）。但是，p1 和 p2 重疊的情況根本沒有落入其中一種可能性。因此，我們遇到了衝突。

強制交換

現在我們知道我們遇到了衝突，我們現在需要以一種明智的方式處理這種衝突。我們不僅要處理手頭的衝突，還要以一種允許衝突乾淨地傳播到整個補丁序列的方式來處理它。好吧，darcs 基於交換，因此為了使一切順利執行，我們需要確保事物繼續交換。因此，我們將定義一個輔助的強制交換操作，我們只在發生衝突時使用它。

回想一下上一章中交換的定義

強制換向將執行類似的操作，但會帶有一些奇怪的轉折。與補丁$Y_{1}$和$X_{1}$執行與它們各自的祖先$Y$和$X$相同的更改不同，強制換向將為我們提供補丁，每個補丁都執行其他補丁執行的更改。也就是說，普通換向希望$Y_{1}$執行與$Y$大致相同的事情，但強制換向使其執行與$X$相同的事情。

操作	$Y_{1}$的效果	$X_{1}$的效果
正常換向	$Y$	$X$
強制換向	$X$	$Y$

效果

順便說一句，我們需要一些術語來避免我們口誤。總是談論一個補丁與另一個補丁執行相同的更改並不是很方便，而這正是我們將會經常提到的東西。所以讓我們簡化一些內容。與其說補丁$Y_{1}$執行與$X$相同的更改，我們簡單地說$Y_{1}$的**效果**是$X$。它是同一個想法，只是術語稍微平滑一些。

合併中的強制換向

讓我們看看這對 Ganesh 和 Arjan 的影響。我們想對 Ganesh 的補丁進行反向運算（$B^{-1}$）與 Arjan 的補丁進行運算。由於這兩個補丁衝突，我們必須訴諸強制運算，這將產生兩個補丁 ${A_{1}}$ 和 ${B_{1}}^{-1}$，它們具有以下奇怪的特性

• $A_{1}$ 的作用是 $B^{-1}$；它從購物清單中刪除了 Ganesh 的“義大利麵”。
• 同樣，${B_{1}}^{-1}$ 的作用是 $A$；它將 Arjan 的“啤酒”新增到購物清單中。

透過強制運算合併衝突

這非常方便，因為我要提醒你，我們真正想要的是取消補丁。如果我們使用標準的合併技術簡單地刪除 ${B_{1}}^{-1}$（這樣我們就不會再新增啤酒了），我們就能成功地撤銷 Ganesh 的義大利麵補丁。合併完成！

解決 Arjan 和 Ganesh 的衝突

標記衝突

等等！我們不能就這樣把事情放下。如果 darcs 透過撤銷操作來處理衝突，可憐的開發者怎麼知道是否有衝突？答案是我們不會止步於此。撤銷衝突是一個非常重要的第一步，正如我們將在下面更詳細地看到的那樣。這樣想吧。我們知道存在衝突，因為運算的定義方式，我們也知道哪些補丁參與了衝突。所以，每當這種情況發生時，我們先撤銷所有操作，然後檢查衝突補丁的內容，並利用它來建立一個新的衝突標記補丁。

FIXME: 在這裡插入顯示衝突標記補丁的影像

Darcs 2

:TODO: introduce this section

指數級合併問題

不幸的是，darcs 1 的合併演算法具有以下屬性：某些合併——人們在現實生活中經歷過的合併——對於衝突的大小（以衝突補丁的數量來衡量）而言是指數級的。這導致一些使用者遇到了這樣的問題：使用者會執行darcs pull令人費解的是，darcs 只是在那裡掛起...

那麼新的 darcs 2 如何解決這個問題？幕後發生了什麼？

衝突者

衝突者的概念本質上是，我們會特殊處理包含其衝突補丁列表的補丁

使用廣義代數資料型別來提高程式碼安全性

• 另請參閱Haskell/GADT 和 http://wiki.darcs.net/Ideas/GADTPlan