JSON Patch Diff And Apply (RFC 6902)

export type JsonValue =
  | null
  | boolean
  | number
  | string
  | JsonValue[]
  | { [key: string]: JsonValue };

export type JsonPatchOperation =
  | { op: "add"; path: string; value: JsonValue }
  | { op: "remove"; path: string }
  | { op: "replace"; path: string; value: JsonValue };

function isPlainObject(value: unknown): value is Record<string, JsonValue> {
  if (value === null || typeof value !== "object" || Array.isArray(value)) return false;
  const prototype = Object.getPrototypeOf(value);
  return prototype === Object.prototype || prototype === null;
}

function deepEqual(left: unknown, right: unknown): boolean {
  if (Object.is(left, right)) return true;
  if (Array.isArray(left) && Array.isArray(right)) {
    return left.length === right.length &&
      left.every((value, index) => deepEqual(value, right[index]));
  }
  if (isPlainObject(left) && isPlainObject(right)) {
    const leftKeys = Object.keys(left);
    const rightKeys = Object.keys(right);
    return leftKeys.length === rightKeys.length &&
      leftKeys.every((key) =>
        Object.prototype.hasOwnProperty.call(right, key) && deepEqual(left[key], right[key]));
  }
  return false;
}

function encodeToken(token: string): string {
  return token.replace(/~/g, "~0").replace(/\//g, "~1");
}

function decodeToken(token: string): string {
  return token.replace(/~1/g, "/").replace(/~0/g, "~");
}

function joinPath(base: string, key: string): string {
  return base + "/" + encodeToken(key);
}

function cloneJson(value: JsonValue): JsonValue {
  return structuredClone(value);
}

export function diffJson(
  before: JsonValue,
  after: JsonValue,
  basePath: string = "",
): JsonPatchOperation[] {
  if (deepEqual(before, after)) return [];
  if (isPlainObject(before) && isPlainObject(after)) {
    const operations: JsonPatchOperation[] = [];
    for (const key of Object.keys(before)) {
      if (!Object.prototype.hasOwnProperty.call(after, key)) {
        operations.push({ op: "remove", path: joinPath(basePath, key) });
      }
    }
    for (const [key, value] of Object.entries(after)) {
      const path = joinPath(basePath, key);
      if (!Object.prototype.hasOwnProperty.call(before, key)) {
        operations.push({ op: "add", path, value: cloneJson(value) });
      } else {
        operations.push(...diffJson(before[key], value, path));
      }
    }
    return operations;
  }
  return [{ op: "replace", path: basePath, value: cloneJson(after) }];
}

function arrayIndex(token: string, length: number, allowEnd: boolean): number {
  if (token === "-") {
    if (!allowEnd) throw new RangeError("append is only valid for add");
    return length;
  }
  if (!/^(0|[1-9]\d*)$/.test(token)) throw new SyntaxError("invalid array index: " + token);
  const index = Number(token);
  const maximum = allowEnd ? length : length - 1;
  if (index > maximum) throw new RangeError("array index out of range: " + token);
  return index;
}

export function applyJsonPatch(
  document: JsonValue,
  operations: readonly JsonPatchOperation[],
): JsonValue {
  let result = cloneJson(document);
  for (const operation of operations) {
    if (operation.path !== "" && !operation.path.startsWith("/")) {
      throw new SyntaxError("invalid JSON Pointer: " + operation.path);
    }
    const tokens = operation.path === ""
      ? []
      : operation.path.slice(1).split("/").map(decodeToken);
    if (tokens.length === 0) {
      if (operation.op === "remove") throw new TypeError("cannot remove the document root");
      result = cloneJson(operation.value);
      continue;
    }

    let parent: JsonValue = result;
    for (let index = 0; index < tokens.length - 1; index += 1) {
      const token = tokens[index];
      if (token === "__proto__" || token === "constructor" || token === "prototype") {
        throw new TypeError("unsafe patch path: " + operation.path);
      }
      if (Array.isArray(parent)) {
        parent = parent[arrayIndex(token, parent.length, false)];
      } else if (isPlainObject(parent)) {
        if (!Object.prototype.hasOwnProperty.call(parent, token)) {
          throw new RangeError("missing patch path: " + operation.path);
        }
        parent = parent[token];
      } else {
        throw new RangeError("patch parent is not a container");
      }
    }

    const last = tokens[tokens.length - 1];
    if (last === "__proto__" || last === "constructor" || last === "prototype") {
      throw new TypeError("unsafe patch path: " + operation.path);
    }
    if (Array.isArray(parent)) {
      const index = arrayIndex(last, parent.length, operation.op === "add");
      if (operation.op === "add") parent.splice(index, 0, cloneJson(operation.value));
      else if (operation.op === "remove") parent.splice(index, 1);
      else parent[index] = cloneJson(operation.value);
    } else if (isPlainObject(parent)) {
      if (operation.op === "remove") {
        if (!Object.prototype.hasOwnProperty.call(parent, last)) {
          throw new RangeError("missing patch path: " + operation.path);
        }
        delete parent[last];
      } else {
        if (operation.op === "replace" &&
          !Object.prototype.hasOwnProperty.call(parent, last)) {
          throw new RangeError("replace target does not exist: " + operation.path);
        }
        parent[last] = cloneJson(operation.value);
      }
    } else {
      throw new RangeError("patch parent is not a container");
    }
  }
  return result;
}