A high-performance core diff engine based on Myers' algorithm, with plugin support for custom strategies (e.g., Patience, Preserve Structure).
npm install @fishan/myers-core-diff
cdiff but can be used for any task requiring fast and accurate sequence comparison (lines, tokens, DNA, etc.).
patienceDiff
preserveStructure
engine._recursiveDiff(...)
engine._findAnchors(...)
engine._guidedCalculateDiff(...)
engine._createDeletions(...) / engine._createAdditions(...)
MyersCoreDiff)
DiffOptions)
Uint32Array (integers) instead of strings for CPU-native comparisons.
commonSES (default), patienceDiff, and preserveStructure as ready-to-use examples.
@fishan/cdiff
cdiff is a powerful comparison tool, its primary strength is as an advanced patching system built on this core.
cdiff leverages the engine's precision to create highly optimized, invertible patches. Thanks to this architecture, cdiff consistently creates the smallest patches among its competitors (see Benchmarks below).
cdiff are a direct result of the @fishan/myers-core-diff engine design.
cdiff tool, which uses @fishan/myers-core-diff as its engine.
cdiff consistently produces the smallest patches (🥇) across a wide range of scenarios. This is a direct result of the core engine's precision, its advanced tokenization, and its character-level diffing capabilities, which libraries like jsdiff (unified) lack.
Total (ms) in some isolated cases (by generating larger, less precise patches), cdiff and this core are optimized for patch size and correctness, especially in complex scenarios involving whitespace, block moves, and low-entropy data.
.diff(), the engine first "tokenizes" your input arrays of strings (string[]) into arrays of integers (Uint32Array). Each unique string gets a unique integer ID.
"hello" === "world") is slow. It requires byte-by-byte checking. Comparing two 32-bit integers (12345 === 12346) is one of the fastest operations a CPU can perform.
cdiff).
bash
npm install @fishan/myers-core-diff
`
Basic Usage
The engine operates on arrays of strings (tokens).
`typescript
import { MyersCoreDiff, DiffOperation } from '@fishan/myers-core-diff';
// 1. Initialize the engine
// The engine automatically registers 'commonSES' by default
const differ = new MyersCoreDiff();
const oldTokens = ["a", "b", "c", "d", "e"];
const newTokens = ["a", "X", "c", "d", "Y", "e"];
// 2. Calculate the diff
const result = differ.diff(oldTokens, newTokens);
// 3. The result
console.log(result);
/*
[
[ 0, 'a' ], // EQUAL
[ 2, 'b' ], // REMOVE
[ 1, 'X' ], // ADD
[ 0, 'c' ], // EQUAL
[ 0, 'd' ], // EQUAL
[ 1, 'Y' ], // ADD
[ 0, 'e' ] // EQUAL
]
*/
`
---
Plugin System (Strategies)
This is the most powerful feature. You can completely change the diff logic without changing the core engine.
$3
The core ships with two powerful strategies besides commonSES: patienceDiff and preserveStructure. They must be registered before use.
$3
Excellent for code, as it focuses on unique lines that haven't changed and ignores "noise" (e.g., shifted blocks).
`typescript
import { MyersCoreDiff, registerPatienceDiffStrategy } from '@fishan/myers-core-diff';
// 1. Register the plugin
registerPatienceDiffStrategy(MyersCoreDiff);
// 2. Initialize the engine
const differ = new MyersCoreDiff();
// 3. Call diff, specifying the strategy
const options = { diffStrategyName: 'patienceDiff' };
const result = differ.diff(oldCode, newCode, false, options);
`
$3
A hybrid strategy that attempts to maintain positional stability (L2 anchors) but uses floating L1 and L3 anchors to find matches within modified blocks.
`typescript
import { MyersCoreDiff, registerPreserveStructureStrategy } from '@fishan/myers-core-diff';
// 1. Register the plugin
registerPreserveStructureStrategy(MyersCoreDiff);
// 2. Initialize
const differ = new MyersCoreDiff();
// 3. Call
const options = { diffStrategyName: 'preserveStructure' };
const result = differ.diff(oldText, newText, false, options);
`
---
Developer Guide: The Toolbox API
When you build a plugin, you receive the engine instance. This is your "Toolbox". It provides direct, low-level access to the core's optimized functions. This allows you to mix-and-match core logic to create new, powerful strategies.
All Toolbox methods (like _recursiveDiff, _findAnchors) operate on tokenized Uint32Array inputs for maximum performance.
$3
* What it is: The main, classic Myers' O(ND) algorithm, implemented with the "middle snake" optimization.
* Principle: This function is guaranteed to find the Shortest Edit Script (SES). It works by finding a "middle snake" (a common subsequence) near the center of the diff region, which divides the problem (A vs B) into two smaller, independent problems (A-prefix vs B-prefix and A-suffix vs B-suffix). It then calls itself recursively on these smaller problems.
* When to use it: This is your precision tool. Use it for small-to-medium sized "gaps" between anchors (e.g., N+M < hugeDiffThreshold).
* Advantages: 100% accurate (finds the shortest possible list of edits).
* Disadvantages: Can be computationally expensive. Its performance is O(ND), where D is the number of differences. In worst-case scenarios (low similarity), D approaches N, and performance degrades to O(N^2).
$3
* What it is: The L1 Anchor generation system. This is the key to high performance on large files.
Principle: This function scans both sequences to find large, high-confidence common subsequences ("anchors"). It uses a rolling hash (huntChunkSize) and confidence scoring (minAnchorConfidence) to identify these blocks without* running a full O(ND) diff.
When to use it: Call this first in any custom plugin. It breaks a single, massive diff problem (e.g., 10,000 lines vs. 10,000 lines) into several small, independent diff problems (the "gaps" between* the anchors).
* Advantages: Drastically improves performance from O(N^2) to something closer to O(N) in common cases by allowing you to skip diffing large, identical blocks.
$3
* What it is: A heuristic-based, linear-time O(N) diff algorithm. It is not a Myers' algorithm.
* Principle: This is a "corridor" scan. It's a greedy algorithm that scans forward, trying to find small matches within a narrow lookahead window. It is not guaranteed to find the SES. It is designed for speed, not accuracy.
* When to use it: Use this for "chaotic" or very low-similarity gaps where N+M > hugeDiffThreshold. In such cases, finding a precise SES is computationally infeasible, and a "good enough" linear-time result is preferable to crashing or freezing.
* Advantages: Extremely fast, O(N). Prevents catastrophic performance degradation on worst-case inputs.
* Disadvantages: Fails badly on moved or swapped blocks. It's designed for massive, contiguous additions, deletions, or replacements.
$3
* What it is: Simple utility functions for "flushing" tokens.
* Principle: They iterate over a token range (start to end) and create a DiffResult array, marking every single token as DiffOperation.REMOVE or DiffOperation.ADD.
* When to use it: Use these to "flush" remaining tokens at the beginning or end of your logic. For example, if your plugin processes all anchors and gaps, and you are left with a final un-matched range at the end of the old file, you would pass it to _createDeletions.
---
Core API (
MyersCoreDiff)
$3
Creates a new diff engine instance.
$3
The main method.
* oldTokens: string[]: Array of "old" tokens.
* newTokens: string[]: Array of "new" tokens.
* debug?: boolean: (default false) Enables verbose logging to the console.
* options?: DiffOptions: Configuration object.
Example:
`typescript
import { MyersCoreDiff, registerPatienceDiffStrategy, type DiffOptions } from '@fishan/myers-core-diff';
registerPatienceDiffStrategy(MyersCoreDiff);
const differ = new MyersCoreDiff();
const options: DiffOptions = {
diffStrategyName: 'patienceDiff',
minMatchLength: 10,
hugeDiffThreshold: 100000,
useAnchors: false
};
const result = differ.diff(oldCode, newCode, false, options);
`
$3
Static method to register a new plugin strategy.
---
Options (
DiffOptions)
You can pass these options into the diff() method:
| Option | Type | Default | Description |
| :--- | :--- | :--- | :--- |
| diffStrategyName | string | 'commonSES' | The name of the strategy plugin to use. |
| minMatchLength | number | 30 | Minimum token length for an L1 anchor. |
| quickDiffThreshold | number | 64 | N+M threshold below which to use quick O(ND) diff. |
| hugeDiffThreshold | number | 256 | N+M gap threshold above which to use _guidedCalculateDiff. |
| lookahead | number | 10 | (For _guidedCalculateDiff) How far to look ahead. |
| corridorWidth | number | 10 | (For _guidedCalculateDiff) Width of the search "corridor". |
| skipTrimming | boolean | false | Skip trimming common prefixes/suffixes. |
| jumpStep | number | 30 | (For _findAnchors) Scan step when searching for anchors. |
| huntChunkSize | number | 10 | (For _findAnchors) Chunk size for hashing. |
| minAnchorConfidence | number | 0.8 | (For _findAnchors) Minimum anchor confidence (0.0–1.0). |
| useAnchors | boolean | true | Whether to use L1 anchors (global search). |
| localLookahead | number | 50 | (For preserveStructure) How far to search for L2 (positional) anchors. |
| anchorSearchMode | 'floating' \| 'positional' \| 'combo' | 'combo' | L1 anchor search mode. |
| positionalAnchorMaxDrift | number | 20 | (For positional mode) Max drift for an L1 positional anchor. |
---
Test Suite
The engine is validated by a comprehensive suite of 126 tests, designed to ensure correctness, reliability, and performance—from the lowest-level primitives to the high-level strategy plugins.
$3
This project uses mocha and ts-node for testing.
#### 1. Development Tests (Fast)
This command runs tests directly against the un-compiled src/ files using ts-node. It is ideal for rapid development and debugging, as it does not require a build step.
`bash
npm run test:dev
`
2. Production Build Tests (Verification)
This command first builds the entire project, creating a minified, production-ready bundle in dist/. It then runs the test suite against that minified bundle. This is the official verification step to ensure the build process or minification did not break any functionality.
`bash
npm test
(or npm run test:prod)
`
The test methodology is built on three pillars:
- White-Box (Direct) Tests: Validate internal primitives like _findMiddleSnake.
- Black-Box (Unit) Tests: Assert exact diff output matches expected snapshots.
- Black-Box (Functional) Tests: Apply the diff as a patch and verify the result matches the expected new content byte-for-byte.
All tests are run for each built-in strategy (commonSES, patienceDiff, preserveStructure) to guarantee production readiness.
View Test Results (126 passing)
`bash
Direct Test: _findMiddleSnake
✔ should find a snake with odd delta (N > M)
✔ should find a snake with even delta (N > M)
✔ should find a snake when change is at the beginning
✔ should find a snake when change is at the end
✔ should find a snake in a large, complete replacement scenario
Direct Test: _guidedCalculateDiff
✔ should handle huge additions
✔ should handle huge deletions
✔ should handle a chaotic mix of small changes in a large string
✔ should handle low-similarity content
✔ should handle repetitive patterns
✔ should fail on swapped blocks
✔ should fail on an interleaved sequence
✔ should fail when a block is moved to the end
✔ should fail with two completely different, complex strings
Direct Test: calculateDiff
✔ should handle simple insertion
✔ should handle simple deletion
✔ should handle simple substitution
✔ should handle empty old string
✔ should handle empty new string
✔ should handle identical strings
✔ should handle reversed string
✔ should handle overlapping changes
✔ should handle changes at the start and end
✔ should handle unicode characters
✔ should handle multiple edits
✔ should handle long common subsequence with small changes
✔ should handle one string being a substring of another
✔ should handle highly repetitive content
✔ should handle strings with only whitespace and newlines
✔ should handle a move-like operation
Direct Test: MyersCoreDiff.diff on Complex Scenarios
✔ should correctly handle a simple block swap
✔ should correctly handle a complete replacement
✔ should correctly handle a block move operation
MyersDiff Functional Tests (Patch Correctness)
✔ should handle simple addition
✔ should handle simple deletion
✔ should handle simple replacement
✔ should handle whitespace-only line replacement
✔ should handle move (complex change)
✔ should handle multiple non-contiguous modifications
✔ should handle changes involving only whitespace
✔ should handle complete rewrite
✔ should handle deletion of all content
✔ should handle creation from empty
✔ should handle changes with unicode characters
✔ should return no changes for identical inputs
✔ should handle addition at the beginning
✔ should handle deletion from the end
✔ should handle a moved block of tokens
✔ should handle changes in repeating patterns
✔ should handle multiple partial replacements
✔ should handle binary-like data stress test
✔ should handle changes with long common prefix/suffix (trimmer test)
✔ should handle interleaved changes
✔ should handle large block deletion from the middle
MyersDiff Unit Tests (Exact Match)
✔ should handle simple addition
✔ should handle simple deletion
✔ should handle simple replacement
✔ should handle whitespace-only line replacement
✔ should handle move (complex change)
✔ should handle multiple non-contiguous modifications
✔ should handle changes involving only whitespace
✔ should handle complete rewrite
✔ should handle deletion of all content
✔ should handle creation from empty
✔ should handle changes with unicode characters
✔ should return no changes for identical inputs
✔ should handle addition at the beginning
✔ should handle deletion from the end
✔ should handle changes in repeating patterns
✔ should correctly handle changes with common prefix/suffix (trimmer test)
✔ should handle interleaved changes
✔ should handle large block deletion from the middle
MyersDiff: Middle Snake Stress Tests
✔ should correctly handle a large block replacement in the middle
✔ should correctly handle moving a large block of tokens
✔ should correctly handle multiple small interleaved changes in a large file
✔ should handle a complete rewrite of one large file to another
✔ should handle deleting large blocks from multiple locations
MyersDiff Functional Tests (Patch Correctness) - Strategy: patienceDiff
✔ should handle simple addition
✔ should handle simple deletion
✔ should handle simple replacement
✔ should handle move (complex change) - expecting correct reconstruction
✔ should handle a moved block of tokens (Block Move test case)
✔ should handle multiple non-contiguous modifications
✔ should handle changes involving only whitespace (indentation)
✔ should handle complete rewrite
✔ should handle deletion of all content
✔ should handle creation from empty
✔ should handle identical inputs
MyersDiff Unit Tests (Exact Match) - Strategy: patienceDiff
✔ should handle simple addition (unit)
✔ should handle simple deletion (unit)
✔ should handle simple replacement (unit)
✔ should handle a simple block move (unit)
✔ should ignore surrounding noise and find LIS (unit)
MyersDiff Functional Tests (Patch correctness) - Strategy: preserveStructure
✔ should handle simple addition
✔ should handle simple deletion
✔ should handle simple replacement
✔ should handle whitespace-only line replacement
✔ should handle move (complex change) - expecting correct reconstruction
✔ should handle multiple non-contiguous modifications
✔ should handle changes involving only whitespace (indentation)
✔ should handle complete rewrite
✔ should handle deletion of all content
✔ should handle creation from empty
✔ should handle changes with unicode characters
✔ should return no changes for identical inputs
✔ should prioritize local change over larger replacement
✔ should handle a moved block of tokens (Block Move test case)
MyersDiff Unit Tests (Exact Match) - Strategy: preserveStructure
✔ should handle simple addition (unit)
✔ should handle simple deletion (unit)
✔ should handle simple replacement (unit)
✔ should handle indentation change (unit - expecting line replace)
✔ should prioritize local change over larger replacement (unit)
126 passing (275ms)
`
---
License
MIT © Aleks Fishan
View License Text
`text
MIT License
Copyright (c) 2025 Aleks Fishan
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
``