Git是怎样生成 diff 的

diff是如何定义的

日常工作中，git中的diff命令是使用率最高的几个命令之一了。我们常常会在提交代码或者review代码的时候，常常通过查看相关的diff提交确保没有问题才进行commit或者merge。

但是这个diff的结果是如何生成的呢，这个看起来习以为常的事情里面也有相关的算法逻辑。

什么是好的diff

首先我们根据自己的需求，来定义什么是好的diff。

我们先简单定义一下什么是 diff：diff 就是目标文本和源文本之间的区别，也就是将源文本变成目标文本所需要的操作。diff文件不光是能够将源文本转化为目标文本，更重要的是具有可读性。

所以什么样的diff是一个直观易读的diff文件呢？

举个简单的例子，源文本为 ABCABBA，目标文本为 CBABAC，他们之间的 diff 其实有无穷多种（我们以字符为单位，一般情况下是以行为单位）。比如

1.  - A       2.  - A       3.  + C
    - B           + C           - A
      C             B             B
    - A           - C           - C
      B             A             A
    + A             B             B
      B           - B           - B
      A             A             A
    + C           + C           + C

上面三种都是有效的diff，都可以将源文本变成目标文本，但是第二种和第三种没有第一种看起来“直观易读”。

删除后新增，比新增后删除要好，也就是说，上面的例子 2 比例子 3 看起来要直观

当修改一块代码时，整块的删除然后新增，比删除新增交叉在一起要好，例如：

  Good: - one            Bad: - one
        - two                 + four
        - three               - two
        + four                + five
        + five                + six
        + six                 - three

一个比较简单的例子

  Good: 
  
class Foo
    def initialize(name) 
        @name = name   
    end     
+
+   def inspect
+       @name 
+   end
end


  Bad:

class Foo
    def initialize(name) 
        @name = name   
+   end     
+
+   def inspect
+       @name 
    end
end

并且我们还希望diff能够尽可能的短，能够用少量的信息即可表明文件的异同。

那么问题来了，“怎样寻找最短的直观易读的 diff？”

如何寻找理想的diff

寻找diff抽象逻辑

现在我们发现这个问题仍然非常模糊，我们需要把这个问题抽象为一个具体的数学问题，然后再来寻找算法解决。

具体的抽象过程我们按下不表，我们现在只关心抽象后的结果：

寻找 diff 的过程可以被表示为图搜索

我们以两个字符串，src=ABCABBA，dst=CBABAC 为例，根据这两个字符串我们可以构造下面一张图，横轴是 src 内容，纵轴是 dst 内容。

那么，图中每一条从左上角到右下角的路径，都表示一个 diff。向右表示“删除”，向下表示”新增“，对角线则表示“原内容保持不动“。


比如，我们选择这样一条路径：

(0, 0) -> (1, 0)
(1, 0) -> (2, 0) -> (3, 1)
(3, 1) -> (3, 2) -> (4, 3) -> (5, 4)
(5, 4) -> (6, 4) -> (7, 5)
(7, 5) -> (7, 6)
这条路径代表的 diff 如下。

- A
- B
  C
+ B
  A
  B
- B
  A
+ C

现在我们把生成diff的过程抽象成“寻找图的路径”。

而理想的diff满足这两个条件：

  • 路径长度最短（对角线不算长度）
  • 先向右，再向下（先删除，后新增）

Myers 算法

算法定义

首先，定义参数 d 和 k，d 代表路径的长度，k 代表当前坐标 x - y 的值。定义一个”最优坐标“的概念，最优坐标表示 d 和 k 值固定的情况下，x 值最大的坐标。x 大，表示向右走的多，表示优先删除。

还是用上面那张图为例。我们从坐标 (0, 0) 开始，此时，d=0，k=0，然后逐步增加 d，计算每个 k 值下对应的最优坐标。

最优路径计算

因为每一步要么向右\(（x + 1）\)，要么向下\(（y + 1）\)，对角线不影响路径长度，所以，当 d=1 时，k 只可能有两个取值，要么是 1，要么是 -1。

当 \(d=1，k=1\) 时，最优坐标是 \((1, 0)\)。

当 \(d=1，k=-1\) 时，最优坐标是 \((0, 1)\)。

因为 d=1 时，k 要么是 1，要么是 -1，当 d=2 时，表示在 d=1 的基础上再走一步，k 只有三个可能的取值，分别是 -2，0，2。

当 \(d=2，k=-2\) 时，最优坐标是\( (2, 4)\)。

当 \(d=2，k=0\) 时，最优坐标是 \((2, 2)\)。

当 \(d=2，k=2\) 时，最优坐标是 \((3, 1)\)。

以此类推，直到我们找到一个 \(d\) 和 \(k\) 值，达到最终的目标坐标 \((7, 6)\)。

其实 Myers 算法是一个典型的”动态规划“算法，也就是说，父问题的求解归结为子问题的求解。要知道 d=5 时所有 k 对应的最优坐标，必须先要知道 d=4 时所有 k 对应的最优坐标，要知道 d=4 时的答案，必须先求解 d=3，以此类推。

具体的算法实现

#  返回 2 个列表 e 和 f 之间差异的最小列表
#  需要 O(min(len(e),len(f))) 空间，O(min(len(e),len(f)) * D) 最坏情况的执行时间，其中 D 是差异的数量
def diff(e, f, i=0, j=0):
  # 
  N,M,L,Z = len(e),len(f),len(e)+len(f),2*min(len(e),len(f))+2
  if N > 0 and M > 0:
    w,g,p = N-M,[0]*Z,[0]*Z
    for h in range(0, (L//2+(L%2!=0))+1):
      for r in range(0, 2):
        c,d,o,m = (g,p,1,1) if r==0 else (p,g,0,-1)
        for k in range(-(h-2*max(0,h-M)), h-2*max(0,h-N)+1, 2):
          a = c[(k+1)%Z] if (k==-h or k!=h and c[(k-1)%Z]<c[(k+1)%Z]) else c[(k-1)%Z]+1
          b = a-k
          s,t = a,b
          while a<N and b<M and e[(1-o)*N+m*a+(o-1)]==f[(1-o)*M+m*b+(o-1)]:
            a,b = a+1,b+1
          c[k%Z],z=a,-(k-w)
          if L%2==o and z>=-(h-o) and z<=h-o and c[k%Z]+d[z%Z] >= N:
            D,x,y,u,v = (2*h-1,s,t,a,b) if o==1 else (2*h,N-a,M-b,N-s,M-t)
            if D > 1 or (x != u and y != v):
              return diff(e[0:x],f[0:y],i,j)+diff(e[u:N],f[v:M],i+u,j+v)
            elif M > N:
              return diff([],f[N:M],i+N,j+N)
            elif M < N:
              return diff(e[M:N],[],i+M,j+M)
            else:
              return []
  elif N > 0: # 如果您想要不同的编辑脚本格式，请修改下面的 return 语句
    return [{"operation": "delete", "position_old": i+n} for n in range(0,N)]
  else:
    return [{"operation": "insert", "position_old": i,"position_new":j+n} for n in range(0,M)]
    
def print_edit_sequence(es, s1, s2):
    RED = '\033[0;31m'
    GREEN = '\033[0;32m'
    BLACK = '\033[0;30m'
    old = 0
    for e in es:
        for i in range(old, e["position_old"]):
            print(f"{BLACK}  {s1[i]}")
        old = e["position_old"]
        if e["operation"] == "delete":
           print(f"{RED}- {s1[old]}")
           old += 1
        else:
           print(f"{GREEN}+ {s2[e['position_new']]}")
    for s in s1[old:]:
        print(f"{BLACK}  {s}")

算法讲解

diff_doc

总结

上述的算法流程主要归纳为以下：

基本流程如下：

  1. 迭代 d，d 的取值范围为 0 到 n+m，其中 n 和 m 分别代表源文本和目标文本的长度（这里我们选择以行为单位）
  2. 每个 d 内部，迭代 k，k 的取值范围为 -d 到 d，以 2 为步长，也就是 -d，-d + 2，-d + 2 + 2…
  3. 使用一个字典 v，以 k 值为索引，存储最优坐标的 x 值
  4. 将每个 d 对应的 v 字典存储起来，后面回溯的时候需要用
  5. 当我们找到一个 d 和 k，到达目标坐标 (n, m) 时就跳出循环
  6. 使用上面存储的 v 字典（每个 d 对应一个这样的字典），从终点反向得出路径

Git 真正用的是标准 Myers 算法的一个变体。标准的算法有一个很大的缺点，就是空间消耗很大，因为我们需要存储每一个 d 对应的 v 字典。如果输入文件比较大，这样的空间开销是不能接受的。因此 Myers 在他的 论文 中，同时提供了一个算法变体，这个变体需要的空间开销要小得多。但是在某些情况下，变体产生的 diff 会和标准算法有所不同。也就是说，如果你按照上面的算法实现的程序，出来的结果和 git diff 的结果有所不同是正常的。

其他相关内容

对于有些场景，Myers算法生成的diff输出并不直观。

所以就引入另一种与Myers非常不同的diff算法, 因为它在某些输入下, 比线性空间的Myers算法要好. 这个算法称为patience diff。

patience diff实际上不算是一种算法, 而是一种在对比两个文本时如何在应用diff算法(例如Myers)前, 将文本分为合理的小文本的手段. 做这种预先处理的原因是, Myers经常将一些无意义的行匹配起来, 例如空行和括号, 这会导致一些恼人的匹配结果以及导致合并冲突的结果.

Patience diff 的改进是: 对两个文本都进行一次全扫描, 得到一组共有的, 在各自文本里都只出现了一次的行, 这将助于得到更有意义而不是生硬的内容划分。

参考资料：

https://blog.robertelder.org/diff-algorithm/
https://neil.fraser.name/writing/diff/myers.pdf
https://cjting.me/2017/05/13/how-git-generate-diff/
https://bramcohen.livejournal.com/73318.html

2025/01/28

Copyright © 2015 Powered by MWeb,  Theme used GitHub CSS.