Myers Diff for JSON Arrays: Limits and Implementation

1. Problem: an array is not an unordered object

When ["a","b"] becomes ["a","x","b"], an insertion is usually more useful than replacing every later index. Myers builds a shortest sequence of insert, delete, and equal operations. It does not define object-field equality or business identity automatically.

2. Minimal reproduction: values in a new position are a new sequence

The arrays contain the same strings but in a different order. Set comparison hides that change; sequence diff must retain position.

const before = ["a", "b", "c"];
const after = ["a", "c", "b"];
console.log(new Set(before).size === new Set(after).size); // true
console.log(JSON.stringify(before) === JSON.stringify(after)); // false

3. Root cause: a shortest edit script walks an edit graph

The two sequences form the axes of an edit graph. A diagonal is an equal element; horizontal and vertical moves are deletion and insertion. Myers expands reachable diagonals by edit distance. A replacement is commonly represented as a neighboring delete and insert, then optionally combined by a presentation layer.

4. Recommended policy: define equality before creating a patch

Scalars can use Object.is. For object arrays, supply a stable identity or equality function, such as id equality; JSON.stringify reintroduces key-order semantics. Keep values and the array path in operations, and document whether patch indexes refer to the current or original array.

5. Complete code: sequence edits with an array path

This small TypeScript Myers implementation is suitable for learning and small arrays. It returns a shortest edit script; toArrayPatch only adds a JSON path and does not mutate an array.

type Edit<T> = { kind: "equal" | "insert" | "delete"; value: T };
type ArrayPatch<T> = Edit<T> & { path: string };
function myers<T>(before: readonly T[], after: readonly T[], same: (a: T, b: T) => boolean = Object.is): Edit<T>[] {
  const max = before.length + after.length;
  const trace: Map<number, number>[] = [];
  let frontier = new Map<number, number>([[1, 0]]);
  for (let distance = 0; distance <= max; distance += 1) {
    trace.push(new Map(frontier));
    for (let diagonal = -distance; diagonal <= distance; diagonal += 2) {
      const down = frontier.get(diagonal + 1) ?? Number.NEGATIVE_INFINITY;
      const right = (frontier.get(diagonal - 1) ?? Number.NEGATIVE_INFINITY) + 1;
      let x = diagonal === -distance || (diagonal !== distance && down > right) ? down : right;
      let y = x - diagonal;
      while (x < before.length && y < after.length && same(before[x], after[y])) { x += 1; y += 1; }
      frontier.set(diagonal, x);
      if (x >= before.length && y >= after.length) {
        const edits: Edit<T>[] = [];
        let endX = before.length;
        let endY = after.length;
        for (let d = trace.length - 1; d > 0; d -= 1) {
          const previous = trace[d]; const k = endX - endY;
          const previousK = k === -d || (k !== d && (previous.get(k - 1) ?? -1) < (previous.get(k + 1) ?? -1)) ? k + 1 : k - 1;
          const previousX = previous.get(previousK) ?? 0; const previousY = previousX - previousK;
          while (endX > previousX && endY > previousY) {
            endX -= 1; endY -= 1;
            edits.push({ kind: "equal", value: before[endX] });
          }
          if (endX === previousX) edits.push({ kind: "insert", value: after[--endY] }); else edits.push({ kind: "delete", value: before[--endX] });
          endX = previousX; endY = previousY;
        }
        while (endX > 0 && endY > 0) edits.push({ kind: "equal", value: before[--endX] });
        return edits.reverse();
      }
    }
  }
  return [];
}
function toArrayPatch<T>(path: string, edits: Edit<T>[]): ArrayPatch<T>[] { return edits.map((edit) => ({ ...edit, path })); }
console.log(toArrayPatch("/items", myers(["a", "b"], ["a", "x", "b"])));

6. Incorrect approaches

Calling recursive object comparison Myers hides the distinction between key sets and sequences. Position-only object comparison turns one leading insertion into many replacements; supply identity instead. A display layer must not always collapse delete plus insert into replace.

7. Boundaries: duplicates, large arrays, and equality

Repeated values can have multiple equally short scripts, so one result is not the only business interpretation. Equality by id ignores changes inside the matching object, which need a later object diff. Large or highly different arrays need memory and interaction evaluation; no fixed threshold applies everywhere.

8. Verification

Test empty arrays, insertion only, deletion only, reordering, duplicates, and object ids. Replay equal/insert/delete operations to reconstruct the target sequence, then verify the path. An in-place patcher needs separate tests for index bases.

9. FAQ

Can Myers compare JSON objects? It compares sequences; use it at array nodes after object paths are handled.

Is replace native to Myers? No; insert, delete, and equal are the base operations.

How should object arrays compare? Match stable identities first, then diff fields of matching objects.

10. Summary

Myers supplies a shortest insert/delete script for ordered JSON arrays, not a universal recursive-object algorithm. Define equality first, preserve path and operation semantics, and test duplicates, identities, and index rules.