Adelphos - Text Differencing and Edit Library

A TypeScript library for text differencing and edit operations based on Microsoft's VSCode diff algorithm. This library implements the LCS (Longest Common Subsequence) algorithm described in "An O(ND) Difference Algorithm and its variations" by Eugene W. Myers.

Features

• String Differencing: Compute differences between strings using the LCS algorithm
• Levenshtein Distance: Calculate edit distance between strings with optimized bit-parallel implementation
• Unified Diff Parsing: Parse and apply unified diff format patches
• VSCode-Compatible String Edits: Advanced string editing with offset ranges, edit composition, and inversion
• Line-based Operations: Work with line-based diffs and edits
• Edit Optimization: Automatic common prefix/suffix removal for efficient edits
• Edit Neutrality Detection: Check if edits produce no actual changes
• Range Operations: Comprehensive offset range manipulation (intersection, delta, etc.)
• TypeScript Support: Full type definitions included

Installation

npm install adelphos

Usage

Basic String Differencing

import { stringDiff, computeLevenshteinDistance } from 'adelphos';

// Compute differences between two strings
const changes = stringDiff('hello world', 'hello there', true);
console.log(changes);
// Output: [{ originalStart: 6, originalLength: 5, modifiedStart: 6, modifiedLength: 5 }]

// Compute Levenshtein distance
const distance = computeLevenshteinDistance('kitten', 'sitting');
console.log(distance); // Output: 3

String Edits

import { stringEditFromDiff, applyStringEdits } from 'adelphos';

const original = 'hello world';
const modified = 'hello there';

// Create string edits from diff
const stringEdit = await stringEditFromDiff(original, modified);

// Apply edits to original text
const result = applyStringEdits(original, stringEdit.edits);
console.log(result); // Output: 'hello there'

Unified Diff Parsing

import { createEditsFromRealDiff, applyLineEdits, textToLines, linesToText } from 'adelphos';

const code = textToLines(`line1
line2
line3`);

const diff = [
  '@@ -1,3 +1,3 @@',
  ' line1',
  '-line2',
  '+modified line2',
  ' line3'
];

// Parse unified diff
const edits = createEditsFromRealDiff(code, diff);

// Apply edits
const result = applyLineEdits(code, edits);
const resultText = linesToText(result);
console.log(resultText);
// Output:
// line1
// modified line2
// line3

Working with Reporters

import { createEditsFromRealDiff, createConsoleReporter } from 'adelphos';

const reporter = createConsoleReporter();
const edits = createEditsFromRealDiff(code, diff, reporter);
// Will log warnings and recovery information to console

Custom Reporter

import { Reporter } from 'adelphos';

const customReporter: Reporter = {
  warning: (message: string) => {
    console.error(`Custom warning: ${message}`);
  },
  recovery: (originalIndex: number, recoveredIndex: number) => {
    console.log(`Recovered line ${originalIndex} at ${recoveredIndex}`);
  }
};

API Reference

Core Functions

stringDiff(original: string, modified: string, pretty: boolean): IDiffChange[]

Computes differences between two strings using the LCS algorithm.

computeLevenshteinDistance(firstString: string, secondString: string): number

Computes the Levenshtein (edit) distance between two strings.

stringEditFromDiff(original: string, modified: string, diffService?: IDiffService, timeoutMs?: number): Promise<StringEdit>

Creates string edits from diff results.

createEditsFromRealDiff(code: Lines, diff: Lines, reporter?: Reporter): LinesEdit[]

Parses unified diff format and creates line edits.

Utility Functions

textToLines(text: string): string[]

Splits text into an array of lines.

linesToText(lines: string[], eol?: string): string

Joins lines into text with specified end-of-line character.

applyStringEdits(text: string, edits: StringReplacement[]): string

Applies string edits to text.

applyLineEdits(lines: Lines, edits: LinesEdit[]): Lines

Applies line edits to an array of lines.

Types

interface IDiffChange {
  originalStart: number;
  originalLength: number;
  modifiedStart: number;
  modifiedLength: number;
}

interface StringReplacement {
  range: OffsetRange;
  newText: string;
}

interface LinesEdit {
  start: number;
  end: number;
  replacement: string[];
  eol?: string;
}

interface Reporter {
  warning(message: string): void;
  recovery(originalIndex: number, recoveredIndex: number): void;
}

Performance

• The LCS algorithm has O(ND) time complexity where N is the sequence length and D is the number of differences
• Memory usage is optimized with configurable history limits
• Levenshtein distance uses bit-parallel algorithms for strings ≤32 characters for optimal performance

License

MIT License - Based on Microsoft's Visual Studio Code implementation.

Contributing

Contributions are welcome! Please ensure tests pass and follow the existing code style.

# Run tests
npm test

# Build the library
npm run build

# Run tests with coverage
npm run test:coverage