跳到主要内容

如何用 MoonBit 实现 diff?

你使用过 Unix 下的小工具 diff 吗?

没有也没关系,简而言之,它是一个比对两个文本文件之间有什么不同之处的工具。它的作用不止于此,Unix 下还有一个叫 patch 的小工具。

时至今日,很少有人手动为某个软件包打补丁了,但 diff 在另一个地方仍然保留着它的作用:版本管理系统。能够看见某一次提交之后的源码文件发生了哪些变化(并且用不同颜色标出来)是个很有用的功能。我们以当今最流行的版本管理系统 git 为例,它可以:

diff --git a/main/main.mbt b/main/main.mbt
index 99f4c4c..52b1388 100644
--- a/main/main.mbt
+++ b/main/main.mbt
@@ -3,7 +3,7 @@

fn main {
let a = lines("A\nB\nC\nA\nB\nB\nA")
- let b = lines("C\nB\nA\nB\nA\nC")
+ let b = lines("C\nB\nA\nB\nA\nA")
let r = shortst_edit(a, b)
println(r)
}

但是,究竟怎样计算出两个文本文件的差别呢?

git 的默认 diff 算法是 Eugene W. Myers在他的论文An O(ND) Difference Algorithm and Its Variations 中所提出的,这篇论文的 pdf 可以在网上找到,但论文内容主要集中于证明该算法的正确性。

在下文中,我们将以不那么严谨的方式了解该算法的基本框架,并且使用 MoonBit 编写该算法的一个简单实现。

01 定义"差别"及其度量标准

当我们谈论两段文本的"差别"时,我们说的其实是一系列的编辑动作,通过执行这段动作,我们可以把文本 a 转写成文本 b。

假设文本 a 的内容是:

A
B
C
A
B
B
A

文本 b 的内容是:

C
B
A
B
A
C

要把文本 a 转写成文本 b,最简单的编辑序列是删除每一个 a 中的字符(用减号表示),然后插入每一个 b 中的字符(用加号表示)。

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

但这样的结果对阅读代码的程序员可能没有什么帮助,而下面这个编辑序列就好很多,至少它比较短。

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

实际上,它是最短的可以将文本 a 转写成文本 b 的编辑序列之一,总共有5个动作。如果仅仅以编辑序列长度作为衡量标准,这个结果足以让我们满意。但当我们审视现实中已经存在的各种编程语言,我们会发现在此之外还有一些对用户体验同样重要的指标,让我们看看下面这两个例子:

// 质量好
struct RHSet[T] {
set : RHTable[T, Unit]
}
+
+ fn RHSet::new[T](capacity : Int) -> RHSet[T] {
+ let set : RHTable[T, Unit]= RHTable::new(capacity)
+ { set : set }
+ }

// 质量不好
struct RHSet[T] {
set : RHTable[T, Unit]
+ }
+
+ fn RHSet::new[T](capacity : Int) -> RHSet[T] {
+ let set : RHTable[T, Unit]= RHTable::new(capacity)
+ { set : set }
}

当我们在文件末尾处插入了一个新的函数定义,那计算出的编辑序列最好把更改都集中在后面。还有些类似的情况,当同时存在删除和插入时,最好不要计算出一个两种操作交织穿插的编辑序列,下面是另一个例子。

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

myers 的 diff 算法能够满足我们在上面提到的这些需求,它是一种贪心算法,会尽可能地跳过相同的行(避免了在 { 前面插入文本的情况),同时它还会尽可能地把删除安排在插入前面,这又避免了后面一种情况。

02 算法概述

Myers 论文的基本想法是构建一张编辑序列构成的网格图,然后在这条图上搜索一条最短路径。我们沿用上面的例子 a = ABCABBA 和 b = CBABAC,建立一个 (x, y) 坐标网格。

    0     1     2     3     4     5     6     7

0 o-----o-----o-----o-----o-----o-----o-----o
| | | \ | | | | |
| | | \ | | | | | C
| | | \ | | | | |
1 o-----o-----o-----o-----o-----o-----o-----o
| | \ | | | \ | \ | |
| | \ | | | \ | \ | | B
| | \ | | | \ | \ | |
2 o-----o-----o-----o-----o-----o-----o-----o
| \ | | | \ | | | \ |
| \ | | | \ | | | \ | A
| \ | | | \ | | | \ |
3 o-----o-----o-----o-----o-----o-----o-----o
| | \ | | | \ | \ | |
| | \ | | | \ | \ | | B
| | \ | | | \ | \ | |
4 o-----o-----o-----o-----o-----o-----o-----o
| \ | | | \ | | | \ |
| \ | | | \ | | | \ | A
| \ | | | \ | | | \ |
5 o-----o-----o-----o-----o-----o-----o-----o
| | | \ | | | | |
| | | \ | | | | | C
| | | \ | | | | |
6 o-----o-----o-----o-----o-----o-----o-----o

A B C A B B A

这张网格中左上方为起点(0, 0), 右下方为终点(7, 6)。沿着 x 轴向右前进一步为删除 a 中对应位置文本,沿 y 轴向下前进一步为插入 b 中对应位置文本,对角斜线标记的则是相同的文本,这些斜线可以直接跳过,它们不会触发任何编辑。

在编写实际执行搜索的代码之前,让我们先手动执行两轮搜索:

  • 第一轮搜索起点为(0, 0),移动一步可以到达(0,1)和(1,0)。
  • 第二轮搜索起点为(0,1)和(1,0),从(0,1)出发下移可以到达(0,2), 但是那里有一条通向(1,3)的斜线,所以最终落点为(1,3)。

03 实现

虽然我们已经敲定了算法的基本思路,但仍有一些关键的设计需要考虑。算法的输入是两个字符串,但搜索需要在图上进行,如果真的把图构造出来再去搜索,这既非常浪费内存,也很费时间。

myers 算法的实现使用了一个聪明的想法,它定义了一个新的坐标 k = x - y。

  • 右移一步会让k加一
  • 左移一步会让k减一
  • 沿对角线向左下方移动k值不变

让我们再定义一个坐标 d 用于代表搜索的深度,以 d 为横轴 k 为纵轴画出搜索过程的树状图:

    |      0     1     2     3     4     5
----+--------------------------------------
|
4 | 7,3
| /
3 | 5,2
| /
2 | 3,1 7,5
| / \ / \
1 | 1,0 5,4 7,6
| / \ \
0 | 0,0 2,2 5,5
| \ \
-1 | 0,1 4,5 5,6
| \ / \
-2 | 2,4 4,6
| \
-3 | 3,6

可以看出来,在每一轮搜索中,k都严格地处于[-d, d]区间中(因为一次移动中最多也就能在上一轮的基础上加一或者减一), 且各点之间的k值间隔为2。myers算法的基本思路便源于此:通过遍历d和k进行搜索。当然了,它还需要保存每轮搜索的x坐标供下一轮搜索使用。

让我们首先定义Line结构体,它表示文本中的一行。

struct Line {
number : Int // 行号
text : String // 不包含换行
} derive(Debug, Show)

fn Line::new(number : Int, text : String) -> Line {
Line::{ number : number, text : text }
}

然后定义一个辅助函数,它将一个字符串按照换行符分割成 Array[Line]。这里需要注意的是,行号是从1开始的。

fn lines(str : String) -> Array[Line] {
let mut line_number = 0
let buf = Buffer::make(50)
let vec = []
for i = 0; i < str.length(); i = i + 1 {
let ch = str[i]
buf.write_char(ch)
if ch == '\n' {
let text = buf.to_string()
buf.reset()
line_number = line_number + 1
vec.push(Line::new(line_number, text))
}
} else {
// 可能文本不以换行符为结尾
let text = buf.to_string()
if text != "" {
line_number = line_number + 1
vec.push(Line::new(line_number, text))
}
vec
}
}

接下来我们需要包装一下数组,使其支持负数索引,原因是我们要用k的值做索引。

type BPArray[T] Array[T] // BiPolar Array

fn BPArray::make[T](capacity : Int, default : T) -> BPArray[T] {
let arr = Array::make(capacity, default)
BPArray(arr)
}

fn op_get[T](self : BPArray[T], idx : Int) -> T {
let BPArray(arr) = self
if idx < 0 {
arr[arr.length() + idx]
} else {
arr[idx]
}
}

fn op_set[T](self : BPArray[T], idx : Int, elem : T) -> Unit {
let BPArray(arr) = self
if idx < 0 {
arr[arr.length() + idx] = elem
} else {
arr[idx] = elem
}
}

现在我们可以开始编写搜索函数了,不过,搜索出完整的路径是比较复杂的,我们的第一个目标是搜索出最短路径的长度(大小和搜索深度一样)。我们先展示它的基本框架:

fn shortst_edit(a : Array[Line], b : Array[Line]) -> Int {
let n = a.length()
let m = b.length()
let max = n + m
let v = BPArray::make(2 * max + 1, 0)
for d = 0; d < max + 1; d = d + 1 {
for k = -d; k < d + 1; k = k + 2 {
......
}
}
}

通过最极端的情况(两段文本没有相同的行)可以推出最多需要搜索n + m步,最少需要搜索0步。故设变量max = n + m。数组v是以k为索引保存x值的历史记录,因为k的范围是[-d, d],这个数组的大小被设为2 * max + 1。

但即使到了这一步,接下来该怎么做还是挺不好想,所以我们暂且只考虑d = 0; k = 0的情况。此时一定在(0, 0)点。同时,假如两段文本的开头相同,那就允许直接跳过。我们将这一轮的最终坐标写入数组v。

if d == 0 { // d等于0 k也一定等于0
x = 0
y = x - k
while x < n && y < m && a[x].text == b[y].text {
// 跳过所有相同的行
x = x + 1
y = y + 1
}
v[k] = x
}

在d > 0时,就需要用到上一轮存储的坐标信息了。当我们知道一个点的k值以及上一轮搜索中点的坐标时,v[k]的值其实很好推算。因为搜索每深入一步k的值只能加一或者减一,所以v[k]在搜索树中一定是从v[k - 1]或者v[k + 1]延伸出来的。接下来的问题是:以v[k - 1]为末端的和以v[k + 1]为末端的这两条路径,应该如何选择?

有两种边界情况:k == -d和k == d

  • k == -d时,只能选择v[k + 1]
  • k == d时,只能选择v[k - 1]

回顾一下我们之前提到的要求:尽可能地把删除安排在插入前面,这基本上意味着我们应该选择x值最大的前一个位置。

if k == -d {
x = v[k + 1]
} else if k == d {
x = v[k - 1] + 1 // 横向移动需要加一
} else if v[k - 1] < v[k + 1] {
x = v[k + 1]
} else {
x = v[k - 1] + 1
}

合并一下这四个分支,我们得到这样的代码:

if k == -d || (k != d && v[k - 1] < v[k + 1]) {
x = v[k + 1]
} else {
x = v[k - 1] + 1
}

综合上面的所有步骤,我们可以得到这样的代码:

fn shortst_edit(a : Array[Line], b : Array[Line]) -> Int {
let n = a.length()
let m = b.length()
let max = n + m
let v = BPArray::make(2 * max + 1, 0)
// v[1] = 0
for d = 0; d < max + 1; d = d + 1 {
for k = -d; k < d + 1; k = k + 2 {
let mut x = 0
let mut y = 0
// if d == 0 {
// x = 0
// }
if k == -d || (k != d && v[k - 1] < v[k + 1]) {
x = v[k + 1]
} else {
x = v[k - 1] + 1
}
y = x - k
while x < n && y < m && a[x].text == b[y].text {
x = x + 1
y = y + 1
}
v[k] = x
if x >= n && y >= m {
return d
}
}
} else {
abort("impossible")
}
}

由于数组的初始值为0,我们可以省略 d == 0 这个分支。

04 尾声

我们实现了一个不完整的myers算法,它完成了正向的路径搜索,在下一篇文章中,我们将实现回溯,还原出完整的编辑路径,并写一个可以输出彩色diff的打印函数。

本篇文章参考了:The Myers diff algorithm: part 2

感谢这篇博客的作者James Coglan。