R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。

JSON Diff Kit:几个简单算法的组合

以下语言可用: 简体中文 正體中文 English
注意:本文发布于 835 天前,文章中的一些内容可能已经过时。

背景

最近我收到一个需求:展示两个 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 有很多类型:numberstringbooleannullobjectarray。如果两个值的类型不同,那它们显然是不相等的,没有必要递归地 diff 它们,只需输出“左边被删除,右边被添加”。如果它们是同一种原始类型,我们也能很方便地知道它俩是否相等,只需在不等时输出“左边被删除,右边被添加”。

现在只剩两个 objectarray 的场景了。我们先从 object 开始。

对象 Diff 算法

假设我们有两个对象 leftright,这是一个很直观的 diff 算法:

  1. leftright 的所有 key 排序,假设结果是 keysLeftkeysRight
  2. 用两个指针 pq 分别指向 keysLeft[0]keysRight[0]
  3. 如果 keysLeft 没有更多的值,输出“keysRight 的剩余部分是多出来的”;如果 keysRight 没有更多的值,输出“keysLeft 的剩余部分被删除”。
  4. 比较两个指向的值:
  5. 如果 p 更小,p++,输出“p 被删除”,为 q 添加一个空行;
  6. 如果 q 更小,q++,输出“q 被添加”,为 p 添加一个空行;
  7. 如果它们相等,增加它们并……

    • 如果值也相等:输出“相等”;
    • 如果值不是同一种类型:输出“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 算法

与对象相比,数组似乎更容易处理。假设我们有两个数组 leftright

  1. pq 分别指向 left[0]right[0]
  2. 如果 left 没有更多的值,输出“right 的剩余部分是多出来的”;如果 right 没有更多的值,输出“left 的剩余部分被删除”。
  3. 如果 pq 不同:

    • 如果 pq 都是对象,调用对象 diff;
    • 如果 pq 都是数组,递归地 diff 它们;
    • 否则,输出“p 被删除,q 被添加”。
  4. 否则,输出“相等”。

上面的算法应该可以处理大多数情况。🎉

锦上添花

虽然这算法可以给出一个不错的结果,但有时候结果可能会让我们感到困惑。

符合直觉

对两个 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

如果相邻的两行 xyx[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 中的当前元素应该被添加。

LCS 的回溯过程

搞定!

识别“修改”

Git diff 是一个很好的展示结果的方式,但对于 JSON 字符串,其实还可以更进一步。例如,对于 {"a":1}{"a":2},我们可以告诉用户“字段 a 从 1 改为了 2”。

回顾一下“对象”那一部分,看是否有地方可以改进:

如果 pq 不同:

  • ...
  • 输出“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`
    />
  );
};

结果很清晰:

一个好的 diff 结果

总结

我整合了几个简单的算法(或受到了它们的启发):

  • 归并排序中的合并过程
  • 冒泡排序
  • LCS 和回溯
  • 递归

这些算法足以针对两个 JSON 字符串,得到一个好的 diff 结果。

Disqus 加载中……如未能加载,请将 disqus.com 和 disquscdn.com 加入白名单。

这是我们共同度过的

第 3105 天