codepointdiff

A faithful TypeScript port of CPython 3.14's difflib module that compares strings by Unicode code point instead of UTF-16 code unit.

import { SequenceMatcher } from 'codepointdiff';

const sm = new SequenceMatcher(null, 'hello \u{1F600} world', 'hello \u{1F603} world');
console.log(sm.ratio()); // 0.9230769230769231 — matches CPython exactly

Why

JavaScript strings are UTF-16: an astral character (code point >= 0x10000, including most emoji) is stored as a surrogate pair — two 16-bit code units. A diff library that walks a JS string by .length/index, or by str.split(''), silently walks those halves instead of characters, and reports similarity scores and edit-script indices that disagree with CPython's own difflib, which compares Python str — already a sequence of code points.

Two npm packages already port difflib to JS: difflib (0.2.4, published 2022-06-15) and difflib-ts (1.0.3, published 2022-04-28). Both split strings this way, so both inherit the bug.

Measured: node bench/measure-astral-gap.mjs (3000 random string pairs per bucket, edits applied to about 75% of pairs, compared against CPython 3.14.7's SequenceMatcher.ratio() on the same inputs, exact float equality):

=== BMP-only text (n=3000) ===
npm difflib    mismatches: 0/3000 (0.00%)
npm difflib-ts mismatches: 57/3000 (1.90%) [57 threw an exception]

=== Text with astral characters (n=3000) ===
npm difflib    mismatches: 1843/3000 (61.43%)
npm difflib-ts mismatches: 1869/3000 (62.30%) [26 threw an exception]
  example (difflib):    a="ø😍" b="丣G🤔ôø丗þ丏k丨😃丘Ý𠀀" -> npm ratio=0.2 cpython ratio=0.125
  example (difflib-ts): a="ø😍" b="丣G🤔ôø丗þ丏k丨😃丘Ý𠀀" -> npm ratio=0.2 cpython ratio=0.125

=== specific example ===
a="hello 😀 world" b="hello 😃 world"
npm difflib ratio:    0.9285714285714286
npm difflib-ts ratio: 0.9285714285714286
CPython ratio:        0.9230769230769231

Both packages agree with CPython on plain BMP text (difflib: 0/3000 mismatches; difflib-ts: 0 ratio mismatches, but 57 inputs — any pair where the second string is empty — throw an exception instead of returning a result). On text containing astral characters, both disagree with CPython on roughly 61-62% of pairs. This package's SequenceMatcher splits input strings with Array.from() (code-point-aware) before comparing, so it agrees with CPython on every case in this measurement and in the 10,100-case fixture suite below.

Neither incumbent exports HtmlDiff or diff_bytes; both otherwise cover unified_diff/context_diff/ndiff/restore/get_close_matches and support autojunk/isjunk/real_quick_ratio.

Installation

npm install codepointdiff

Usage

Comparing two strings

import { SequenceMatcher } from 'codepointdiff';

const sm = new SequenceMatcher(null, 'private Thread t;', 'private volatile Thread t;');
sm.ratio(); // 0.7906976744186046
sm.getOpcodes(); // [['equal', 0, 9, 0, 9], ['insert', 9, 9, 9, 18], ['equal', 9, 18, 18, 27]]

A plain string passed to SequenceMatcher, getCloseMatches, set_seq1 or set_seq2 is split into code points with Array.from() first, so every index reported by getOpcodes()/getMatchingBlocks() is a code-point index, not a UTF-16 offset. Pass an array directly (of strings, numbers, or booleans) to compare a pre-tokenized sequence — lines of a file, for example.

Diffing lines: unified, context, and ndiff formats

import { unifiedDiff, contextDiff, ndiff } from 'codepointdiff';

const a = 'one\ntwo\nthree\nfour\n'.split(/(?<=\n)/);
const b = 'zero\none\ntree\nfour\n'.split(/(?<=\n)/);

[...unifiedDiff(a, b, { fromfile: 'a.txt', tofile: 'b.txt' })].join('');
[...contextDiff(a, b)].join('');
[...ndiff(a, b)].join(''); // includes '?' intraline-hint lines

Restoring an original file from an ndiff delta

import { ndiff, restore } from 'codepointdiff';

const delta = [...ndiff(aLines, bLines)];
const original = [...restore(delta, 1)].join(''); // == aLines.join('')

Finding close matches

import { getCloseMatches } from 'codepointdiff';

getCloseMatches('appel', ['ape', 'apple', 'peach', 'puppy']); // ['apple', 'ape']

HTML side-by-side diff

import { HtmlDiff } from 'codepointdiff';

const html = new HtmlDiff().makeFile(aLines, bLines, 'a.txt', 'b.txt');

Diffing raw bytes

import { diffBytes, unifiedDiffLines } from 'codepointdiff';

const result = [...diffBytes(unifiedDiffLines, aByteLines, bByteLines)];

diffBytes losslessly maps arbitrary bytes (including invalid UTF-8) to and from strings the way CPython's 'ascii', 'surrogateescape' codec does, so inputs of unknown or inconsistent encoding compare correctly.

Getting UTF-16 offsets instead of code-point offsets

import { SequenceMatcher, opcodesToUtf16 } from 'codepointdiff';

const a = 'a\u{1F600}b';
const b = 'a\u{1F603}b';
const codePointOps = new SequenceMatcher(null, a, b).getOpcodes();
const utf16Ops = opcodesToUtf16(codePointOps, a, b); // usable with a.slice()/b.slice()

Reference

SequenceMatcher<T>

Member	Description
new SequenceMatcher(isjunk?, a?, b?, autojunk = true)	isjunk: (x: T) => boolean | null. a/b: a string (split into code points) or an array.
setSeqs(a, b) / setSeq1(a) / setSeq2(b)	Replace one or both sequences; cached state is invalidated as needed.
findLongestMatch(alo?, ahi?, blo?, bhi?)	Returns { a, b, size } for the longest junk-free matching block in the given ranges.
getMatchingBlocks()	Returns { a, b, size }[], terminated by a zero-size dummy at (a.length, b.length, 0).
getOpcodes()	Returns ['replace' | 'delete' | 'insert' | 'equal', i1, i2, j1, j2][].
getGroupedOpcodes(n = 3)	Generator of opcode groups with up to n lines of context. Mutates the cached opcodes list in place on first call, exactly as CPython does — call it after, not before, reading getOpcodes() if you need the untrimmed result.
ratio() / quickRatio() / realQuickRatio()	Similarity in [0, 1]; each is a cheaper upper bound on the next.

Functions

Function	Description
getCloseMatches(word, possibilities, n = 3, cutoff = 0.6)	Best n fuzzy matches with ratio() >= cutoff, most similar first.
ndiff(a, b, linejunk?, charjunk = IS_CHARACTER_JUNK)	Line-by-line delta with ' '/'- '/'+ '/'? ' prefixes.
restore(delta, which: 1 | 2)	Recovers one of the two original sequences from an ndiff/Differ delta.
unifiedDiff(a, b, options?)	options: { fromfile, tofile, fromfiledate, tofiledate, n = 3, lineterm = '\n' }.
contextDiff(a, b, options?)	Same options as unifiedDiff.
diffBytes(dfunc, a, b, fromfile?, tofile?, fromfiledate?, tofiledate?, n?, lineterm?)	Byte-oriented wrapper around unifiedDiffLines/contextDiffLines.
IS_LINE_JUNK(line)	True for a blank line or a line that is only whitespace and at most one #.
IS_CHARACTER_JUNK(ch, ws = ' \t')	True if ch is in ws.
toCodePoints(s) / toUtf16Units(s)	Split a string into single-code-point or single-UTF-16-unit strings.
codePointIndexToUtf16(codePoints, index) / opcodesToUtf16(opcodes, aStr, bStr)	Convert code-point indices back to UTF-16 offsets.

Differ

new Differ(linejunk?, charjunk?), with .compare(a, b) returning a generator of the same delta lines as ndiff (which is Differ with charjunk defaulted to IS_CHARACTER_JUNK).

HtmlDiff

new HtmlDiff(tabsize = 8, wrapcolumn = null, linejunk?, charjunk = IS_CHARACTER_JUNK), with .makeTable(fromlines, tolines, fromdesc?, todesc?, context = false, numlines = 5) returning an HTML <table> string, and .makeFile(...) wrapping that table in a full HTML document. Output matches CPython's HtmlDiff byte-for-byte for the same inputs, including the anchor-prefix counter, which is shared across all HtmlDiff instances in a process (as it is in CPython).

How it works

SequenceMatcher is the same "gestalt pattern matching" algorithm CPython uses: find the longest contiguous junk-free matching block, recurse on the pieces to either side, and apply the "autojunk" popularity heuristic (elements making up more than 1% of a 200+-element sequence are excluded as sync points, matching CPython's exact threshold and arithmetic) unless disabled. The only behavioral difference from a plain re-implementation is deliberate: every algorithm, cache, and even known CPython implementation quirks (getGroupedOpcodes mutating the cached opcode list on first call) are reproduced exactly, because "faithful port" includes the quirks.

String inputs are split into code points via Array.from(), which uses the iterator protocol JS strings implement over code points (pairing surrogates correctly), rather than .length/charCodeAt, which count UTF-16 units. Everything downstream — matching blocks, opcodes, ratios — then operates on that code-point array, so all reported indices are code-point indices.

Limitations

• Sequence elements must be string | number | boolean (compared with === and usable as a Map/Set key by value), not arbitrary objects — Python's broader "hashable" constraint doesn't map directly onto JS value equality.
• IS_LINE_JUNK/Differ's tab handling use JS's \s/.trim() for "whitespace", which is not identical to Python's str.isspace()/.strip() Unicode whitespace set (a few rare separator characters differ); ordinary text is unaffected.
• HtmlDiff's tab expansion does not special-case tabsize <= 0 (CPython's str.expandtabs(0) deletes tabs outright; untested here since HtmlDiff always uses the default tabsize = 8 unless told otherwise).
• No CLI; this is a library only.
• Not a byte-for-byte copy of CPython's source — a structural TypeScript port, verified case-by-case against it (see Development).

Compatibility

Tested locally with Node v24.20.0 and Python 3.14.7 (used only to generate the reference fixtures; not a runtime dependency). The CI workflow in this repository also runs the built dist/ smoke tests on Node 20.6 and 22 — that is "runs in CI", not independently verified here.

Development

npm install
npx tsc --noEmit
npm test               # runs test/*.test.ts against test/fixtures/*.json
npm run build && npm run test:dist

Fixtures are pre-generated and committed under test/fixtures/. To regenerate them (requires a local python3 with difflib, i.e. any stock Python 3 install; verified against 3.14.7):

python3 test/generate-fixtures.py

This writes 10,100 cases across six JSON files, covering ratio/quickRatio/realQuickRatio/getOpcodes/getMatchingBlocks/getGroupedOpcodes, the autojunk heuristic on 200+ item sequences, getCloseMatches with varying n/cutoff, unifiedDiff/contextDiff/ndiff/restore with varying n, lineterm, and dates, diffBytes on arbitrary (including invalid-UTF-8) byte sequences, and HtmlDiff output — over random text and lines including astral characters, combining marks, CRLF, empty inputs, and duplicates. All 10,100 cases pass with exact float equality (verified: npm test reports pass 22, 0 failures, covering all fixture files plus doctest-derived unit tests).

To reproduce the astral-character gap measurement in ## Why:

npm install   # also installs the two npm incumbents as devDependencies, for the bench only
node bench/measure-astral-gap.mjs

License

MIT — see LICENSE. The ported algorithm and behavior are CPython's; the original PSF license is reproduced verbatim in LICENSE-python, and its notice is kept in each source file that ports Lib/difflib.py.