tessl/npm-fast-diff
Fast Javascript text diff using Myers' O(ND) Difference Algorithm
- Workspace
- tessl
- Visibility
- Public
- Created
- Last updated
- Describes
To install, run
npx @tessl/cli install tessl/npm-fast-diff@1.3.0index.mddocs/
Fast Diff
Fast Diff is a high-performance JavaScript text differencing library that implements Myers' O(ND) Difference Algorithm. It provides efficient text comparison functionality by finding the minimal set of changes needed to transform one string into another.
Package Information
- Package Name: fast-diff
- Package Type: npm
- Language: JavaScript (with TypeScript definitions)
- Installation:
npm install fast-diff
Core Imports
const diff = require('fast-diff');For TypeScript:
import * as diff from 'fast-diff';
// or
import diff = require('fast-diff');Basic Usage
const diff = require('fast-diff');
// Basic diff comparison
const result = diff('Good dog', 'Bad dog');
// Returns: [[-1, "Goo"], [1, "Ba"], [0, "d dog"]]
// Using operation constants
const operations = result.map(([op, text]) => {
switch (op) {
case diff.DELETE: return `Delete: "${text}"`;
case diff.INSERT: return `Insert: "${text}"`;
case diff.EQUAL: return `Keep: "${text}"`;
}
});Architecture
Fast Diff is built on a sophisticated implementation of Myers' O(ND) Difference Algorithm with several key optimizations:
- Core Algorithm: Uses Myers' O(ND) Difference Algorithm to find the shortest edit script between two strings, where N is the sum of string lengths and D is the number of differences
- Prefix/Suffix Optimization: Automatically detects and strips common prefixes and suffixes before diffing, significantly improving performance for texts with shared beginnings or endings
- Half-Match Detection: Implements half-match optimization for long texts to break them into smaller, more manageable segments
- Unicode Handling: Properly handles surrogate pairs and multi-byte Unicode characters to prevent splitting characters incorrectly
- Cursor-Aware Diffing: When provided with cursor position information, respects edit locations to produce more intuitive diff results for text editors and user interfaces
- Semantic Cleanup: Optional post-processing to merge adjacent operations and improve diff readability by eliminating trivial equalities
Capabilities
Main Diff Function
Compares two strings and returns an array of diff operations indicating insertions, deletions, and unchanged parts.
/**
* Find the differences between two texts using Myers' O(ND) Difference Algorithm
* @param {string} text1 - Old string to be diffed
* @param {string} text2 - New string to be diffed
* @param {number|CursorInfo} [cursor_pos] - Edit position in text1 or cursor info object
* @param {boolean} [cleanup] - Apply semantic cleanup before returning
* @returns {Array<[number, string]>} Array of diff tuples [operation, text]
*/
function diff(text1, text2, cursor_pos, cleanup);Usage Examples:
// Basic text comparison
const result = diff('abc', 'aec');
// Returns: [[0, "a"], [-1, "b"], [1, "e"], [0, "c"]]
// With cursor position (respects edit location for better results)
const result = diff('aaa', 'aaaa', 1);
// Returns: [[0, "a"], [1, "a"], [0, "aa"]]
// Insertion is positioned at cursor location
// With semantic cleanup (improves readability)
const result = diff('The quick brown fox', 'A quick brown fox', null, true);
// Applies semantic cleanup to make changes more meaningful
// Using cursor info object for complex edits
const result = diff('hello world', 'hello there world', {
oldRange: { index: 6, length: 0 },
newRange: { index: 6, length: 6 }
});Operation Constants
Constants representing the type of operation in each diff tuple.
/** Constant representing a delete operation (-1) */
const DELETE = -1;
/** Constant representing an insert operation (1) */
const INSERT = 1;
/** Constant representing an equality/no change (0) */
const EQUAL = 0;Usage Examples:
const result = diff('old text', 'new text');
result.forEach(([operation, text]) => {
switch (operation) {
case diff.DELETE:
console.log(`Remove: "${text}"`);
break;
case diff.INSERT:
console.log(`Add: "${text}"`);
break;
case diff.EQUAL:
console.log(`Keep: "${text}"`);
break;
}
});
// Check for specific operations
const hasInsertions = result.some(([op]) => op === diff.INSERT);
const hasDelations = result.some(([op]) => op === diff.DELETE);Types
/**
* Main diff function signature for TypeScript
*/
declare function diff(
text1: string,
text2: string,
cursorPos?: number | diff.CursorInfo,
cleanup?: boolean
): diff.Diff[];
/**
* Diff tuple representing an operation and its associated text
*/
type Diff = [-1 | 0 | 1, string];
/**
* Interface for providing detailed cursor position information
*/
interface CursorInfo {
/** Range in the old text */
oldRange: { index: number; length: number };
/** Range in the new text */
newRange: { index: number; length: number };
}
/**
* Operation constants
*/
const DELETE: -1;
const INSERT: 1;
const EQUAL: 0;Return Value Format
The diff function returns an array of tuples where each tuple contains:
- Operation code:
-1(delete),1(insert), or0(equal) - Text: The string content for this operation
// Example return value for diff('abc', 'ac'):
[
[-1, "b"], // Delete "b"
[0, "ac"] // Keep "ac"
]
// Example return value for diff('ac', 'abc'):
[
[0, "a"], // Keep "a"
[1, "b"], // Insert "b"
[0, "c"] // Keep "c"
]Performance Characteristics
- Algorithm: Myers' O(ND) Difference Algorithm with optimizations
- Time Complexity: O(ND) where N is the sum of string lengths and D is the number of differences
- Optimizations:
- Common prefix/suffix detection for faster processing
- Half-match optimization for long texts
- Unicode-aware character handling
- Semantic cleanup for more readable diffs
Error Handling
The library handles various edge cases gracefully:
- Empty strings: Returns appropriate insert/delete operations
- Identical strings: Returns single equality operation or empty array
- Unicode characters: Properly handles surrogate pairs and multi-byte characters
- Invalid cursor positions: Gracefully handles out-of-bounds cursor positions