Diff-Match-Patch in Typescript with full budget and surrogate pairs support

Javascript diff-match-patch, made suitable for use in production:

• Modern typescript with unit tests, thanks to diff-match-patch-typescript.
• Full unicode support, thanks to PR 80
• I added full diffTimeout support, which is only partially implemented elsewhere, and is critical for production use (since otherwise your server or browser can be easily stuck at 100% for minutes). See big.test.ts.
• A deterministic work budget (diffWorkLimit, or a DiffWorkBudget passed in) in place of the clock. Off by default; without it, results are byte-identical to 1.0.1. See work-budget.test.ts. With it:
  • The contract: diffWorkLimit bounds the abstract, charged algorithm steps of diff_main and the cleanups (and so of patch_make's diff and patch_apply's fuzzy diffs): at most diffWorkLimit + BUDGET_STEP_UNITS × (n + 2) units, where n is the length of the call's texts (for a cleanup, of its diffs) and BUDGET_STEP_UNITS is 24. The units track the characters the algorithm examines and copies and the diffs it moves. Engine-level work is not metered: string concatenation and flattening, ===, the semantic score's regular expressions, array reads and writes, and the line encoding's hashing. Its cost may vary by engine, so the units bound the algorithm's steps, not total CPU.
  • How: every step is either paid for ahead with a bound on its work (and skipped, leaving the trivial diff, if the budget can't cover it), or runs only while the budget isn't spent and is charged as it runs. So the charged units are the limit plus at most one step. One budget is shared by everything a call does, and the clock is never read.
  • Not covered: patch_make's assembly and its context search (patch_addContext_, O(N) per patch) are outside the budget, and so is patch_apply's matching (match_main). The budget bounds the diff, not all of patch_make.
  • Speed: on V8 (Node) on an AMD EPYC 7B13 core, roughly 135,000 to 180,000 units take a millisecond, so diffWorkLimit: 25_000_000 is about diffTimeout: 0.2 there. That figure is calibrated and measured there, not guaranteed, and not part of the contract.
• Modern api for creating dmp object (still backward compatible).

Installation

pnpm i @cocalc/diff-match-patch

import { DiffMatchPatch } from "@cocalc/diff-match-patch";
const dmp = new DiffMatchPatch({ diffTimeout: 0.5 });
const patch = dmp.patch_make("ello", "hello world");
console.log(JSON.stringify(patch));
// [{"diffs":[[1,"h"],[0,"ello"],[1," world"]],"start1":0,"start2":0,"length1":4,"length2":11}]
dmp.patch_apply(patch, "ello");
// [ 'hello world', [ true ] ]

Documentation

Official Repository.