背景

最近我收到一個需求：展示兩個 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 演算法：

1. 對 left 和 right 的所有 key 排序，假設結果是 keysLeft 和 keysRight。
2. 用兩個指標 p 和 q 分別指向 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 演算法

與物件相比，陣列似乎更容易處理。假設我們有兩個陣列 left 和 right：

1. 用 p 和 q 分別指向 left[0] 和 right[0]。
2. 如果 left 沒有更多的值，輸出“right 的剩餘部分是多出來的”；如果 right 沒有更多的值，輸出“left 的剩餘部分被刪除”。

3. 如果 p 和 q 不同：

   • 如果 p 和 q 都是物件，呼叫物件 diff；
   • 如果 p 和 q 都是陣列，遞迴地 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

如果相鄰的兩行 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 結果。