以下语言可用: 简体中文 正體中文 English
背景
最近我收到一个需求:展示两个 JSON 字符串的 diff,这两个字符串基本上是一个 API 的请求和响应数据。此外,我们还应该以 Git 的风格显示 diff。
然而,经过简单的搜索,我并没有发现合适的库。
那我只好自己实现了。
Git 的方式
JSON 字符串可能非常不规范。例如这两个 JSON 字符串是等价的:
{"a":1,"b":2}
{ "a" :1, "b": 2}
幸好我们有一个强大的内置函数 JSON.stringify
,可以将一个 JavaScript 对象序列化为标准的 JSON 字符串。此外,它还可以根据给定的缩进级别格式化字符串:
const original = `{ "a" :1, "b": 2}`;
const formatted = JSON.stringify(JSON.parse(original), null, 4);
console.log(formatted);
// ……结果是:
// {
// "a": 1,
// "b": 2
// }
结果看起来非常像上面截图中右下角的样子。我们只需要找到一个合适的方法来执行 diff 就可以了。
既然我需要显示的是 Git 风格,那么直接使用 Git 的 diff 算法如何?
Git 使用了 Myers 算法 来生成一个美观的 diff 结果;似乎我也可以直接用 Git 的库,但我很快就发现了两个缺点:
首先它不能完美地处理末尾逗号:当我发起一个合并请求时,我在 package.json
中看到了很多冲突。在下面的例子中,a
行被识别为“不同”只是因为末尾逗号。
{ | {
- "a": 1 |
| + "a": 1,
| + "b": 2
} | }
其次,JSON.stringify
不能处理不同的 key 顺序。例如:
// 结果不同!
JSON.stringify(JSON.parse({"a":1,"b":2}))
JSON.stringify(JSON.parse({"b":2,"a":1}))
所以 Git 的方式并不适用;我需要自己实现一个 diff 方法。
一个基本的 JSON Diff 方法
首先,JSON 有很多类型:number
、string
、boolean
、null
、object
、array
。如果两个值的类型不同,那它们显然是不相等的,没有必要递归地 diff 它们,只需输出“左边被删除,右边被添加”。如果它们是同一种原始类型,我们也能很方便地知道它俩是否相等,只需在不等时输出“左边被删除,右边被添加”。
现在只剩两个 object
或 array
的场景了。我们先从 object
开始。
对象 Diff 算法
假设我们有两个对象 left
和 right
,这是一个很直观的 diff 算法:
- 对
left
和right
的所有 key 排序,假设结果是keysLeft
和keysRight
。 - 用两个指针
p
和q
分别指向keysLeft[0]
和keysRight[0]
。 - 如果
keysLeft
没有更多的值,输出“keysRight
的剩余部分是多出来的”;如果keysRight
没有更多的值,输出“keysLeft
的剩余部分被删除”。 - 比较两个指向的值:
- 如果
p
更小,p++
,输出“p
被删除”,为q
添加一个空行; - 如果
q
更小,q++
,输出“q
被添加”,为p
添加一个空行; 如果它们相等,增加它们并……
- 如果值也相等:输出“相等”;
- 如果值不是同一种类型:输出“
p
被删除,q
被添加”。 - 如果值都是对象:递归地 diff 它们。
- 否则(如果值都是数组):使用数组 diff 方法(稍后再说)。
举个例子:
[开始]
p: ↓
keysLeft: a d f g i j k l
keysRight: a b c d i
q: ↑
[第 1 步]
p: ↓
keysLeft: a d f g i j k l
keysRight: a b c d i
q: ↑
[第 2 步]
p: ↓
keysLeft: a _ d f g i j k l
keysRight: a b c d i
q: ↑
[...跳过了若干步]
[结果]
p: ↓
keysLeft: a _ _ d f g i j k l
keysRight: a b c d _ _ i _ _ _
q: ↑
这个算法看起来就像“归并排序”算法中的合并过程。它通过添加空行来确保左右两边的结果有相同的行数。
数组 Diff 算法
与对象相比,数组似乎更容易处理。假设我们有两个数组 left
和 right
:
- 用
p
和q
分别指向left[0]
和right[0]
。 - 如果
left
没有更多的值,输出“right
的剩余部分是多出来的”;如果right
没有更多的值,输出“left
的剩余部分被删除”。 如果
p
和q
不同:- 如果
p
和q
都是对象,调用对象 diff; - 如果
p
和q
都是数组,递归地 diff 它们; - 否则,输出“
p
被删除,q
被添加”。
- 如果
- 否则,输出“相等”。
上面的算法应该可以处理大多数情况。🎉
锦上添花
虽然这算法可以给出一个不错的结果,但有时候结果可能会让我们感到困惑。
符合直觉
对两个 JSON 做 diff 可能会有多种结果:
- 1 | - 1 | | + 3
- 2 | | + 3 | + 4
| + 3 - 2 | | + 5
| + 4 | + 4 - 1 |
| + 5 | + 5 - 2 |
✅ 🤔 🤔
显然第一个结果是最好的,它符合我们的直觉:1)先“删除”再“添加”,2)尽可能多的连续行具有相同的操作。Mayers 算法产生的输出就是这个样子。那能不能通过调整一下输出来达到相同的效果呢?我想到了一个跟冒泡排序算法相似的解决方案。
如果我们已经有了一个 diff 结果,我们可以交换两行来得到一个更好的结果(在这个例子中,我们交换了第 2 行和第 3 行):
- 1 | - 1 |
| + 3 - 2 |
- 2 | => | + 3
| + 4 | + 4
| + 5 | + 5
如果相邻的两行 x
和 y
,x
是 [empty, added]
,y
是 [removed, empty]
,那它们就可以交换顺序。结果是一个 [removed, empty]
后面跟着一个 [empty, added]
。
整个交换过程可能会执行多次。但就像冒泡排序一样,如果在当前循环中没有交换,算法就可以提前终止。
更好的数组匹配算法
有时候两个数组的差异仅仅是由于少量元素的插入或删除。例如在这种情况下我们不应该输出“删除”:
- 2 | | + 1
- 3 | 2 | 2
| + 1 3 | 3
| + 2
| + 3
🤔 ✅
一个动态规划算法 LCS(最长公共子序列)可以帮助我们找到两个数组的最长公共子序列。例如在上面的两个数组中,LCS 是 [2, 3]
。
大概的思路是:找到 LCS,然后用 LCS 和两个数组做 diff。a
中多出来的元素应该被识别为“删除”,b
中多出来的元素应该被识别为“添加”。
但有一个更简单的方法。在 LCS 计算过程中,我们使用一个 backtrack
矩阵来记录当前的状态(“left”、“up”、“diag”)。在回溯时,我们可以知道如果当前状态是“left”,那么 a
中的当前元素应该被删除;如果当前状态是“up”,那么 b
中的当前元素应该被添加。
搞定!
识别“修改”
Git diff 是一个很好的展示结果的方式,但对于 JSON 字符串,其实还可以更进一步。例如,对于 {"a":1}
和 {"a":2}
,我们可以告诉用户“字段 a
从 1 改为了 2”。
回顾一下“对象”那一部分,看是否有地方可以改进:
如果
p
和q
不同:
- ...
- 输出“
p
被删除,q
被添加”。
此时输出应该是“p
被修改为 q
”。
数组的部分则稍微复杂一点。如果我们使用普通的匹配,只需要输出“a[i]
被修改为 b[i]
”就可以了。但如果我们使用 LCS 匹配,我们需要稍微改变一下回溯过程。
如果当前状态是“left”,那么a
中的当前元素应该被删除;如果当前状态是“up”,那么b
中的当前元素应该被添加。
在回溯时,我们如何识别“有一个 a remove
后面跟着一个 b add
”呢?解决方案很简单:当遇到一个“up”时,我们向前走一步,看看下一步(实际上是“上一步”,因为我们在回溯)是不是一个“left”。如果一个“left”后面跟着一个“up”出现在一个路径中,我们就可以知道“a[i]
被删除,b[j]
被添加”。然后它可以被优化为“a[i]
被修改为 b[j]
”。
到目前为止,我们已经找到了一个足够好的算法来处理 JSON 字符串的 diff。我们可以为每一行输出这些字段:
- 类型(添加、修改、删除、相等);
- 行号;
- 缩进级别;
- 文本;
- 是否有末尾逗号。
至于 diff 结果的 interface 可以这么写:
export interface DiffResult {
level: number;
type: 'modify' | 'add' | 'remove' | 'equal';
text: string;
comma?: boolean;
lineNumber?: number;
}
Differ 和 Viewer
为了解耦 diff 和显示逻辑,我写了一个 Differ
类来计算 diff 结果,还有一个 Viewer
组件来显示 diff 结果。我将这些逻辑打包到了一个库 json-diff-kit 中(更复杂的用法在 这里),开发者可以很容易地使用这个库:
import { Differ } from 'json-diff-kit';
const before = {
a: 1,
b: 2,
d: [1, 5, 4],
e: ['1', 2, { f: 3, g: null, h: [5], i: [] }, 9],
};
const after = {
b: 2,
c: 3,
d: [1, 3, 4, 6],
e: ['1', 2, 3, { f: 4, g: false, i: [7, 8] }, 10],
};
// 所有的配置都是可选的
const differ = new Differ({
detectCircular: true, // 默认 `true`
maxDepth: Infinity, // 默认 `Infinity`
showModifications: true, // 默认 `true`
arrayDiffMethod: 'lcs', // 默认 `"normal"`
});
const diff = differ.diff(before, after);
import { Viewer } from 'json-diff-kit';
import type { DiffResult } from 'json-diff-kit';
import 'json-diff-kit/dist/viewer.css';
interface PageProps {
diff: [DiffResult[], DiffResult[]];
}
const Page: React.FC<PageProps> = props => {
return (
<Viewer
diff={props.diff} // 必填
indent={4} // 默认 `2`
lineNumbers={true} // 默认 `false`
/>
);
};
结果很清晰:
总结
我整合了几个简单的算法(或受到了它们的启发):
- 归并排序中的合并过程
- 冒泡排序
- LCS 和回溯
- 递归
这些算法足以针对两个 JSON 字符串,得到一个好的 diff 结果。