Git命令解析-patch、apply、diff

無(wú)論是merge還是rebase，都是在同一個(gè)工作目錄中協(xié)調(diào)差異，處理變更歷史。而git的另一些命令，允許開(kāi)發(fā)者單獨(dú)保存，或者通過(guò)文件或郵件的方式與別人分享這些差異。

這有助于更靈活的選擇和使用某些較為獨(dú)立的更改。這有點(diǎn)類似另一類版本控制系統(tǒng)的工作方式：存儲(chǔ)差異而不是快照。

可以使用 git diff > patchfile 將差異輸出到patch文件，保存或者分享給他人。使用 git diff 命令可以查看工作區(qū)修改的內(nèi)容，git diff —cached 命令查看添加到暫存區(qū)但還未提交的內(nèi)容。這兩種命令會(huì)生成兼容unix系統(tǒng)的標(biāo)準(zhǔn)格式patch。類似這樣：

git apply --stat patchfile

git apply --check patchfile

git apply patchfile

這三條命令分別是，檢查patch文件格式，測(cè)試patch是否能應(yīng)用到當(dāng)前分支，應(yīng)用此patch。

這種方式傳遞的修改將會(huì)丟失提交信息和作者信息，但可以兼容非git管理的代碼。除此之外，git還提供另一個(gè)命令更便于git庫(kù)之間的patch傳遞。

git format-patch commit-id

git format-patch -s commit-id

生成指定提交之后的所有提交的patch。把 -s 改為 -n，n為任意數(shù)字，則會(huì)生成每個(gè)提交之前的n個(gè)patch。每個(gè)patch是單獨(dú)的文件，命名類似于:

0001-commit message.patch

format-patch生成的patch保存了更多提交信息。因此除了git apply之外，還可以用更智能的git am命令使用此patch。git am 命令會(huì)在應(yīng)用patch失敗時(shí)給出詳細(xì)的錯(cuò)誤信息，并允許手動(dòng)解決沖突，是官方較為推薦的補(bǔ)丁應(yīng)用方式。

我們?cè)谑褂冒姹究刂乒ぞ邥r(shí)，總會(huì)花費(fèi)很多時(shí)間來(lái)處理diff，比如檢查正在進(jìn)行的未提交的工作，查看單個(gè)提交中發(fā)生了什么變更，在執(zhí)行合并之前比較兩個(gè)分支，等等。

diff是版本控制的核心概念，但可能大多數(shù)使用者沒(méi)有考慮過(guò)它是如何生成的。請(qǐng)思考一下如何編寫一個(gè)函數(shù)來(lái)計(jì)算diff。很容易發(fā)現(xiàn)，更準(zhǔn)確的需求是只顯示發(fā)生了什么變化，忽略其他保持不變的部分。那么，如何確定文件的哪些部分沒(méi)有更改？如果從某行開(kāi)始發(fā)現(xiàn)了差異，如何在每個(gè)版本中找到再次匹配的部分？

對(duì)修改者來(lái)說(shuō)，哪些東西應(yīng)該標(biāo)記為更改似乎是顯而易見(jiàn)的。比如向文件中插入新代碼、刪除冗余語(yǔ)句或重寫部分函數(shù)，作為代碼的貢獻(xiàn)者，我們總會(huì)有一個(gè)直觀的心理模型。然而，如同大多數(shù)程序員所知，只會(huì)執(zhí)行指令的機(jī)器要得到一個(gè)符合人類直覺(jué)的結(jié)果，通常比看上去要困難的多。而且總會(huì)存在很多可供選擇的實(shí)現(xiàn)方法，會(huì)產(chǎn)生完全不同的結(jié)果。

例如：有原序列ABCABBA，記做a，長(zhǎng)度記為N，修改后的序列CBABAC，記做b，長(zhǎng)度記為M。以單個(gè)字符為最小單位，把刪除和添加兩個(gè)步驟作為變更的基本操作。從a到b顯然有很多種方法，比如可以直接簡(jiǎn)單粗暴的刪除a，再添加b，那么編輯腳本看起來(lái)會(huì)是這樣：

一共需要 N+M 步，這顯然不是我們想要的最簡(jiǎn)操作。再繼續(xù)觀察，發(fā)現(xiàn)操作中出現(xiàn)了對(duì)同一個(gè)字符的刪除和新增操作，這些字符可以看做不變的部分，省略編輯步驟。

但是又出現(xiàn)了新的問(wèn)題，比如僅看新串的前三個(gè)字符CBA，它可以看做原串第3-7字符刪掉中間AB，也可以看做2-4字符的前面加C同時(shí)刪除中間的C。這兩者雖然步數(shù)相同，但不同的看待方式會(huì)影響其他字符的變更步數(shù)。另外，就算全部步數(shù)相同，也可能存在一些方式比另一些方式更直觀更容易理解。

形式上，問(wèn)題的關(guān)鍵是找到一個(gè)最長(zhǎng)公共子序列，或者等價(jià)地，找到將一個(gè)序列轉(zhuǎn)換成另一個(gè)序列的符號(hào)的最少步驟。這是一個(gè)已有廣泛研究基礎(chǔ)的問(wèn)題，git使用的默認(rèn)算法由Eugene W. Myers 在1986年的論文（http://www.xmailserver.org/diff2.pdf）中提出。

Myers的算法就是這樣一種策略，它的速度很快，而且它產(chǎn)生的變更大部分情況下都是最直觀的。它通過(guò)貪心的方式來(lái)實(shí)現(xiàn)這一點(diǎn)，即優(yōu)先嘗試使用相同的行數(shù)，并且在處理等價(jià)步驟時(shí)優(yōu)先選擇刪除而不是插入。

下面嘗試較為直觀的展示該算法的基本步驟，并通過(guò)一個(gè)示例表現(xiàn)它如何計(jì)算從一個(gè)版本到另一個(gè)版本的最簡(jiǎn)變更。

令x軸為原序列a，y軸為新序列b，兩個(gè)序列之間的轉(zhuǎn)換就可以表示為下圖。向右表示刪除一個(gè)字符，而向下則表示新增，對(duì)角邊對(duì)應(yīng)那些允許不變的部分。

原問(wèn)題就轉(zhuǎn)化為找從點(diǎn)(0,0)到點(diǎn)(N,M)的最多對(duì)角邊，同時(shí)也等于找從點(diǎn)(0,0)到點(diǎn)(N,M)的最少非對(duì)角邊。對(duì)應(yīng)更少變更操作的要求，設(shè)置對(duì)角邊的權(quán)值為0，非對(duì)角邊的權(quán)值為1。這樣，問(wèn)題也等價(jià)于在圖中找一條從點(diǎn)(0,0)到(N,M)的權(quán)值最小的路徑，屬于單源最短路問(wèn)題的一個(gè)特例。

下面引入幾個(gè)概念：

D：待求得的最小權(quán)值，也就是原問(wèn)題中的最小操作步數(shù)。（取值范圍從0到MAX，MAX = M+N）

k ：k = x - y，使用橫縱坐標(biāo)的差來(lái)標(biāo)記對(duì)角線，無(wú)論線上是否存在對(duì)角邊。它的范圍是從-M到N。

snake ：連續(xù)的對(duì)角邊序列(可以為空，為空時(shí)即等于終止點(diǎn))

D-path：用來(lái)表示一個(gè)權(quán)重?cái)?shù)為D的路徑，也就是水平垂直邊數(shù)為D的路徑。比如D=0的0-path就是一條只有對(duì)角邊的路徑?；趯?duì)角線的概念，任意D-path的結(jié)束點(diǎn)都會(huì)在某個(gè)k值對(duì)應(yīng)的對(duì)角線上。

這里比較容易混淆的概念就是對(duì)角線和對(duì)角邊，對(duì)應(yīng)到上圖，對(duì)角線指的是穿過(guò)所有點(diǎn)，公式為 x=y+k 的一系列等距斜線。而對(duì)角邊或snake僅表示那些連接相同字符的實(shí)線線段。如下圖：

一條D-path的終止點(diǎn)，所在的對(duì)角線的k值和D的差一定是偶數(shù)，并且范圍在-D和D之間?；谶@些概念，原論文中先論證了兩條理論：

若一條D-path的最遠(yuǎn)結(jié)束點(diǎn)對(duì)應(yīng)的對(duì)角線為k，那么最遠(yuǎn)的(D-1)-path必然達(dá)到了對(duì)角線 k±1 。

第一條很容易理解，參照上圖，構(gòu)思一個(gè)D=3的D-path，會(huì)發(fā)現(xiàn)它的終止點(diǎn)不可能在-2，0，2這些k值對(duì)應(yīng)的線上。

第二條基于上一條結(jié)論，(D-1)-path或(D+1)-path必定會(huì)和D-path相差一條水平或垂直邊，必然會(huì)導(dǎo)致 k值有±1的變動(dòng)。

基于這兩個(gè)結(jié)論，論文作者給出一種時(shí)間復(fù)雜度O((M+N)D)的貪心算法。基本步驟如下：

讓步數(shù)D從0開(kāi)始增長(zhǎng)，最大值為MAX。

對(duì)應(yīng)每個(gè)D值，讓k從-D到D以步數(shù)為2增長(zhǎng)。在圖上體現(xiàn)為從右上向左下依次循環(huán)。

對(duì)每個(gè)D值的所有k值，保存或更新對(duì)應(yīng)D-path達(dá)到的最大x坐標(biāo)。這保證了D-path優(yōu)先向右延伸，即優(yōu)先刪除。

隨著循環(huán)進(jìn)行，D值不斷增長(zhǎng)，D-path不斷延伸，直到 x >= N 并且 y >= M，說(shuō)明最遠(yuǎn)D-path的終止點(diǎn)已經(jīng)可以到達(dá)終點(diǎn)(N,M)，算法終止。

文中的偽代碼如下：

整個(gè)步驟也可以表示為下圖，其中(0,-1)的虛擬點(diǎn)和超出圖范圍的部分，是處于遍歷中邊界條件的需要，把終止點(diǎn)為(0,0)和全圖不含對(duì)角邊的情況包含其中。

對(duì)于最開(kāi)始舉的例子，可以找到的最佳diff路徑類似這樣：

現(xiàn)在結(jié)合上面的偽代碼詳述一下計(jì)算過(guò)程：

循環(huán)D=0：

k=0。根據(jù)if條件k = -D，和預(yù)先賦值的V[1] = 0，待判定點(diǎn)的x設(shè)置為0。

第8行，y=x-k=0。

第9行判斷是否存在(0,0)->(1,1)的對(duì)角邊，不存在這個(gè)邊，所以不變更終止點(diǎn)。

第10行保存D=0,k=0時(shí)的最大x坐標(biāo)值：V[0] = 0。

第一輪D=0結(jié)束時(shí)，唯一最遠(yuǎn)終止點(diǎn)為(0,0)

循環(huán)D=1：

k取值-1或1。分別對(duì)應(yīng)上圖D=1時(shí)與橫縱軸相交的兩個(gè)點(diǎn)。

k = -1，滿足條件 k=-D，所以 x =V[0] = 0, y = x-k = 1。而(0,1)->(1,2)不存在對(duì)角邊。

記錄D=1，k=-1時(shí)的x值，V[-1] = 0。

k = 1，不滿足第4行的條件，跳轉(zhuǎn)到第7行，x = V[0] + 1 = 1, y = x-k = 0。

記錄D=1，k=1的x值，V[1] = 1。

第二輪D=1結(jié)束時(shí)，達(dá)到過(guò)的最遠(yuǎn)終止點(diǎn)為(1,0)和(0,1)。

但因?yàn)閂數(shù)組僅保存最大x坐標(biāo)，以實(shí)現(xiàn)優(yōu)先刪除，記錄最遠(yuǎn)終止點(diǎn)為(1,0)

此時(shí) V[-1] = 0, V[0] = 0, V[1] = 1

循環(huán)D=2：

k取值-2，0，2。

k = -2，滿足條件 k=-D，設(shè)置 x =V[-1] = 0, y = x-k = 2。

第9行循環(huán)判斷，(0,2)->(1,3)->(2,4)存在連續(xù)對(duì)角邊。所以此條件下終止點(diǎn)為(2,4)。

記錄D=2，k=-2時(shí)的x值，V[-2] = 2。

k = 0，判斷第4行”or”之后的條件，V[-1] < V[1]，即 0 < 1，成立。設(shè)置 x = 1，y = x-k = 1。

此點(diǎn)存在對(duì)角邊(1,1)->(2,2)，記錄D=2，k=0時(shí)的x值，V[0] = 2。

k = 2，不滿足第4行條件，執(zhí)行第7行設(shè)置 x = V[1]+1 = 2，y = x-k = 0。

此點(diǎn)存在對(duì)角邊(2,0)->(3,1)，記錄D=2，k=2時(shí)的x值，V[2] = 3。

此輪D=2結(jié)束時(shí)，達(dá)到過(guò)的最遠(yuǎn)終止點(diǎn)為(2,4)(2,2)和(3,1)。

V數(shù)組僅保存最大x坐標(biāo)，所以記錄最遠(yuǎn)終止點(diǎn)為(3,1)。

以下依次循環(huán)，直到足以到達(dá)(N,M)點(diǎn)。

細(xì)心的讀者可能會(huì)發(fā)現(xiàn)，以上步驟僅保存了最遠(yuǎn)終止點(diǎn)及對(duì)應(yīng)D值，為了明確列出具體路徑，還需要保存每一步的終止點(diǎn)和方向，這還需要額外O(D*D)的空間復(fù)雜度。于是作者繼續(xù)提出一種優(yōu)化方案。

方案基于作者提出的第三條理論：

從序列a到序列b的最佳D-path，與b到a的最佳D-path，必然重合(或翻轉(zhuǎn)重合)在最佳的終止點(diǎn)或snake對(duì)角邊上。

作者針對(duì)這一理論給出了詳細(xì)論證。因?yàn)樽髡咭矝](méi)太讀懂公式，有興趣可以繼續(xù)查閱原論文。

這一優(yōu)化方式把上一部分的單向搜索，轉(zhuǎn)化為從起點(diǎn)和終點(diǎn)向中間搜索公共snake的問(wèn)題。只要找到一對(duì)相反并且同時(shí)達(dá)到最遠(yuǎn)的重合路徑，就可以停止并輸出這個(gè)snake或終止點(diǎn)。最差情況需計(jì)算兩條D-path，這對(duì)時(shí)間復(fù)雜度影響不大。

優(yōu)化后的算法采用二分法遞歸查找最佳路徑，只需要線性的存儲(chǔ)空間，和O((M+N)D)的時(shí)間復(fù)雜度。這對(duì)于較大數(shù)據(jù)量的對(duì)比十分有利。是git和unix系統(tǒng)共同采用的diff方式。