2つのJSONからRFC 6902（JSON Patch）を生成するアルゴリズムを実装した

はじめに

Torinoa Tools に、2つのJSONを比較してRFC 6902（JSON Patch）形式の差分を自動生成するJSON Patch Generatorというツールがあります。「変更前JSON」と「変更後JSON」を貼り付けると、add / remove / replace の操作列を出力し、その場で適用結果を検証できます。

この記事では、差分生成アルゴリズムと、生成したパッチを実際に適用する処理の実装を紹介します。

JSON Patchとは

RFC 6902は、JSONドキュメントに対する変更を表現するための標準フォーマットです。例えば以下のような操作列で「あるJSONから別のJSONへの変更」を表現します。

[
  { "op": "replace", "path": "/user/age", "value": 26 },
  { "op": "add", "path": "/user/roles/-", "value": "admin" },
  { "op": "remove", "path": "/user/tempFlag" }
]

パスの指定にはRFC 6901（JSON Pointer）を使うため、キー名に ~ や / を含む場合はエスケープが必要です。

// RFC 6901: ~ → ~0, / → ~1
export function escapePointer(key: string): string {
  return key.replace(/~/g, "~0").replace(/\//g, "~1");
}

~を先に置換してから/を置換する順序が重要です。逆にすると、/をエスケープして生まれた~1の~がさらにエスケープされてしまい、二重エスケープになってしまいます。

差分生成: オブジェクトはキー単位、配列はインデックス単位で再帰

差分生成の中心は generateOps という再帰関数です。オブジェクトと配列で扱いを分けています。

オブジェクトの場合

if (
  original !== null &&
  modified !== null &&
  typeof original === "object" &&
  typeof modified === "object" &&
  !Array.isArray(original) &&
  !Array.isArray(modified)
) {
  const orig = original as Record<string, unknown>;
  const mod = modified as Record<string, unknown>;
  const allKeys = new Set([...Object.keys(orig), ...Object.keys(mod)]);

  for (const key of allKeys) {
    const childPath = buildPath(path, key);
    if (!(key in orig)) {
      ops.push({ op: "add", path: childPath, value: mod[key] });
    } else if (!(key in mod)) {
      ops.push({ op: "remove", path: childPath, value_from: orig[key] });
    } else if (!deepEqual(orig[key], mod[key])) {
      generateOps(orig[key], mod[key], childPath, ops);
    }
  }
  return;
}

両方のオブジェクトのキーを Set で合成し、和集合に対してループします。キーが片方にしかなければ add/remove、両方にあって値が違えば再帰、というシンプルな構造です。値の比較には JSON.stringify を使った簡易 deepEqual を使っており、オブジェクトのキー順序が違うと別物と判定される制約はありますが、実用上は十分機能します。

配列の場合: 末尾から処理するのがポイント

配列は「要素ごとのインデックス」で管理されるため、途中の要素を削除・追加すると後続のインデックスがずれてしまいます。このツールでは、末尾側から削除を処理することでインデックスのずれを回避しています。

if (Array.isArray(original) && Array.isArray(modified)) {
  const origArr = original as unknown[];
  const modArr = modified as unknown[];

  // 末尾から削除する方が安全（インデックスずれを防ぐ）
  for (let i = origArr.length - 1; i >= modArr.length; i--) {
    ops.push({ op: "remove", path: buildPath(path, i), value_from: origArr[i] });
  }
  // 共通部分は値が違えば再帰的にreplace/add/removeを積む
  for (let i = 0; i < Math.min(origArr.length, modArr.length); i++) {
    if (!deepEqual(origArr[i], modArr[i])) {
      generateOps(origArr[i], modArr[i], buildPath(path, i), ops);
    }
  }
  // 末尾追加は "-" （配列末尾を表すJSON Pointerの特殊トークン）
  for (let i = origArr.length; i < modArr.length; i++) {
    ops.push({ op: "add", path: buildPath(path, "-"), value: modArr[i] });
  }
  return;
}

なお、これは要素の並び替え（LCSベースの最小差分検出など）までは行わない、位置ベースの単純な比較です。配列の要素が「増減」した場合は末尾の増減として扱われ、途中への挿入・削除は「その位置以降がすべてreplaceされた」という形の差分になります。厳密な最小差分ではなく、「実装がシンプルで、生成したパッチが確実に正しい結果を再現する」ことを優先した設計です。

生成したパッチが正しいかをその場で検証する

差分を生成するだけでなく、生成したパッチを実際に元のJSONへ適用し、期待した結果になるかをツール内で検証できるようにしています。

export function applyPatch(
  original: unknown,
  ops: PatchOp[],
): { ok: boolean; result: unknown } {
  let doc = JSON.parse(JSON.stringify(original)); // シンプルなdeep clone

  try {
    for (const op of ops) {
      const parts = op.path
        .split("/")
        .slice(1)
        .map((p) => p.replace(/~1/g, "/").replace(/~0/g, "~")); // Pointerのデコード

      if (op.op === "add") doc = applyAdd(doc, parts, op.value);
      else if (op.op === "remove") doc = applyRemove(doc, parts);
      else if (op.op === "replace") doc = applyReplace(doc, parts, op.value);
    }
    return { ok: true, result: doc };
  } catch {
    return { ok: false, result: doc };
  }
}

JSON Pointerのデコードは、エスケープ時と逆順に行う必要があります。エスケープ時は ~ → ~0 の後に / → ~1 でしたが、デコード時は ~1 → / を先に処理してから ~0 → ~ を処理します。この順序を間違えると、元々 ~1 という文字列を含んでいたキーが誤って / として復元されてしまいます。

パスの各セグメントから親オブジェクト（または配列）と最終キーを求める処理は、共通ロジックとして切り出しています。

function getParentAndKey(doc: unknown, parts: string[]) {
  let cur: unknown = doc;
  for (let i = 0; i < parts.length - 1; i++) {
    const k = parts[i];
    cur = Array.isArray(cur) ? (cur as unknown[])[Number(k)] : (cur as Record<string, unknown>)[k];
  }
  const last = parts[parts.length - 1];
  if (Array.isArray(cur)) {
    // "-" は配列の末尾（新規追加位置）を表すRFC 6901の特殊トークン
    return { parent: cur, key: last === "-" ? cur.length : Number(last) };
  }
  return { parent: cur as Record<string, unknown>, key: last };
}

配列に対する add は splice で挿入位置に差し込み、remove は該当インデックスを取り除く、replace は該当インデックスを上書きする、という素直な実装です。この applyPatch を生成直後に自動実行し、「生成したパッチを適用した結果が、本当に変更後JSONと一致するか」をUI上で常に検証できるようにしています。差分生成ロジックにバグがあっても、目視で気づけるようにする狙いです。

おわりに

JSON Patchの差分生成自体は、「オブジェクトはキー単位、配列は末尾優先」というルールさえ決めてしまえば実装は素直です。むしろ手間がかかったのは、RFC 6901のエスケープ処理をエンコードとデコードで逆順にするという、地味だけど間違えると静かに壊れる部分でした。生成したパッチをその場で適用検証できるようにしたことで、実装ミスに気づきやすくなったのも良かった点です。

ツールはこちらから試せます: https://tools.torinoa.com/tools/json-patch-generator/