#Diff

#Features

#Core Algorithms

• Myers' Algorithm: A classic and efficient diffing algorithm with a time complexity of O((N+M)D) and space complexity of O(N+M), where N and M are the lengths of the sequences and D is the number of differences. It finds a guaranteed shortest edit script.
• Patience Algorithm: An algorithm designed to produce more human-readable diffs, especially for code or text with a lot of noise or moved blocks. It works by finding unique common elements (like a Longest Common Subsequence) to anchor the diff, and then recursively diffs the sections between these anchors.

#Diff Hooks

• Capture: A basic hook that captures the raw sequence of Equal, Insert, and Delete operations generated by a diffing algorithm.
• Replace: A hook that builds upon Capture. It processes the operation list to merge adjacent Delete and Insert operations into a more semantic Replace operation.
• Compact: An advanced hook that produces a more concise and readable diff. It intelligently shifts Insert and Delete operations to expand adjacent Equal blocks, making the final output as clean and minimal as possible. This is especially effective for line-by-line diffs of text files where changes might be slightly offset.

#High-Level API

#Examples

// diff array
let a = [1, 2, 3, 4, 5, 8, 9]
let b = [1, 2, 0, 4, 5, 6, 7]
let diffs = diff(a, b)
println(diffs)

// diff lines
let old = ["0", "1", "2", "3", "4", "5"]
let new = ["9", "1", "2", "5", "6", "7"]
print_diff_line(old, new)

#Reference

• MoonBit Myers Diff
• Rust similar