Compressing JSON Patches Without State

readme.md

https://iq.opengenus.org/radix-tree/

https://medium.com/@dedels/using-immer-to-compress-immer-patches-f382835b6c69

mobxjs/mobx-state-tree#1976

mobxjs/mobx-state-tree#586

example.ts

/**
 * Compresses JsonPatches using a Radix Trie.
 * @param patches
 * @returns
 */
export function compressPatches(patches: Patch[]) {
  const trie = new PatchRadixTrie(patches);
  return  trie.getPatches();
}

const patches = []
onPatch(state, patch => patches.push(patch))

const compressed = compressPatches(patches.map(getImmerPatch)).map(getMSTPatch);

immer.ts

import { applyPatches, enablePatches, Patch, produceWithPatches } from "immer";
import { joinJsonPath, splitJsonPath, type IJsonPatch, isStateTreeNode, getSnapshot } from "mobx-state-tree";

export const getImmerPatch = ({ path, ...patch }: IJsonPatch) => ({ path: splitJsonPath(path), ...patch });
export const getMSTPatch = ({ path, ...patch }: Patch) => ({ path: joinJsonPath(path as string[]), ...patch });

/**
 * Compresses JsonPatches using immer. Requires snapshot of previous state.
 * https://medium.com/@dedels/using-immer-to-compress-immer-patches-f382835b6c69
 * @param prevState
 * @param patches
 * @returns
 */
export function compressImmerPatches(prevState: IEditorState, patches: Patch[]) {
  const snapshot = isStateTreeNode(prevState) ? getSnapshot(prevState) : prevState;
  const [next, compressed, inverse] = produceWithPatches<IEditorState>(snapshot, draft => applyPatches(draft, patches));
  return compressed;
}

const patches = []
onPatch(state, patch => patches.push(patch))

const lastSnapshot = state.toJSON();
onSnapshot(state, snapshot => {
  const compressed compressImmerPatches(lastSnapshot, patches.map(getImmerPatch)).map(getMSTPatch)
  lastSnapshot = snapshot
})

PatchRadixTrie.ts

/* eslint-disable max-classes-per-file */
import { applyPatches, Patch } from "immer";
import invariant from "tiny-invariant";

class TrieNode {
  children: Map<string | number, TrieNode>;

  label: Patch["path"];

  patch: Patch | undefined;

  // eslint-disable-next-line default-param-last
  constructor(label = [""], patch?: Patch) {
    this.children = new Map();
    this.label = label;
    this.patch = patch;
  }
}

/**
 * Finds index at which arrays differ. Returns -1 if they are equal or one contains the other.
 */
function splitIndex(partsA: Patch["path"], partsB: Patch["path"]) {
  const maxLength = Math.min(partsA.length, partsB.length);
  for (let i = 0; i < maxLength; i++) {
    if (partsA[i] !== partsB[i]) {
      return i;
    }
  }
  return -1;
}

export class PatchRadixTrie {
  root: TrieNode;

  constructor(patches: Patch[] = []) {
    this.root = new TrieNode([""]);
    patches.forEach(patch => this.insert(patch));
  }

  insert(patch: Patch) {
    let node = this.root;
    let depth = 0;
    if (patch.path.length === 0) {
      node.patch = patch;
      node.children = new Map();
      return;
    }
    while (depth < patch.path.length) {
      // Get path that is currently being processed, and unprocessed path parts.
      const path = patch.path[depth];
      const pathSuffix = patch.path.slice(depth);
      if (!node.children.has(path)) {
        node.children.set(path, new TrieNode(pathSuffix, patch));
        return;
      }
      const parent = node;
      node = node.children.get(path)!;
      // Check if existing path contains incoming path or vice versa.
      let index = splitIndex(pathSuffix, node.label);
      if (index === -1) {
        // Incoming patch should replace existing node as paths are equal.
        if (pathSuffix.length === node.label.length) {
          const other = node.patch;
          if (other) {
            if (other.op === "add" && patch.op === "remove") {
              node.patch = undefined;
            }
            if (other.op === "add" && patch.op === "replace") {
              node.patch = { ...patch, op: "add" };
            }
            // This can only happen when the parent value is an array.
            // Re-insert existing patch at next index.
            if (other.op === "add" && patch.op === "add") {
              node.patch = patch;
              const index = Number(other.path.at(-1));
              invariant(!Number.isNaN(index), `Index should be a number if parent value is array.`);
              const nextPath = other.path.slice(0, -1).concat(index + 1);
              this.insert({ ...other, path: nextPath });
            }
            if (other.op === "remove" && patch.op === "add") {
              node.patch = { ...patch, op: "replace" };
            }
            // This can only happen when the parent value is an array.
            // Re-insert existing patch at next index.
            if (other.op === "remove" && patch.op === "remove") {
              node.patch = patch;
              const index = Number(other.path.at(-1));
              invariant(!Number.isNaN(index), `Index should be a number if parent value is array.`);
              const nextPath = other.path.slice(0, -1).concat(index + 1);
              this.insert({ ...other, path: nextPath });
            }
            // This can only happen when the parent value is an array.
            if (other.op === "remove" && patch.op === "replace") {
              const index = Number(other.path.at(-1));
              invariant(!Number.isNaN(index), `Index should be a number if parent value is array.`);
              const nextPath = patch.path.slice(0, -1).concat(index + 1);
              this.insert({ ...patch, path: nextPath });
            }
            // This can only happen when the parent value is an array.
            if (other.op === "replace" && patch.op === "add") {
              node.patch = patch;
              const index = Number(other.path.at(-1));
              invariant(!Number.isNaN(index), `Index should be a number if parent value is array.`);
              const nextPath = other.path.slice(0, -1).concat(index + 1);
              this.insert({ ...other, path: nextPath });
            }
            if (other.op === "replace" && patch.op === "remove") {
              node.patch = { ...patch, op: "remove" };
            }
            if (other.op === "replace" && patch.op === "replace") {
              node.patch = patch;
            }
          } else {
            node.patch = patch;
          }
          node.children = new Map();
          return;
        }
        // Incoming patch should be parent of existing node as incoming path is shorter.
        if (pathSuffix.length < node.label.length) {
          const prefix = pathSuffix;
          const prefixNode = new TrieNode(prefix, patch);
          const suffix = node.label.slice(prefix.length);
          node.label = suffix;
          // If patch is parent, discard child patch as its redundant.
          // prefixNode.children.set(suffix[0], node);
          parent.children.set(path, prefixNode);
          return;
        }
        // Incoming patch should be child of existing node as incoming path is longer.
        if (pathSuffix.length > node.label.length) {
          index = node.label.length;
        }
      } else {
        // Incoming patch splits existing node into two.
        const prefix = node.label.slice(0, index);
        const suffix = node.label.slice(index);
        node.label = suffix;
        const prefixNode = new TrieNode(prefix);
        prefixNode.children.set(suffix[0], node);
        parent.children.set(path, prefixNode);
        // Insert incoming patch as child of prefix node in next iteration.
        node = prefixNode;
      }
      depth += index;
    }
  }

  find(patch: Patch) {
    let node = this.root;
    let depth = 0;
    while (depth < patch.path.length) {
      const path = patch.path[depth];
      if (!node.children.has(path)) {
        return node.patch && node;
      }
      node = node.children.get(path)!;
      const pathSuffix = patch.path.slice(depth);
      const index = splitIndex(pathSuffix, node.label);
      if (index !== -1) {
        return undefined;
      }
      depth += node.label.length;
    }
    return node;
  }

  getPatches() {
    return this.traverseTrie(this.root);
  }

  traverseTrie(node: TrieNode) {
    const { patch, children } = node;
    const iter = this.traverseTrie.bind(this);
    const childPatches: Patch[] = Array.from(children.values()).flatMap(iter);

    if (patch) {
      if (children.size) {
        if (patch.op === "remove") throw RangeError("Patch with op remove cannot have children patches.");
        // Normalize child patches relative to patch.path.
        const patches = childPatches.map(p => ({ ...p, path: p.path.slice(patch.path.length) }));
        return [
          {
            ...patch,
            value: applyPatches(patch.value, patches),
          },
        ];
      }
      return [patch];
    }
    return childPatches;
  }
}