Diff

A diffing library for MoonBit.

Features

This library provides several diffing algorithms and hooks to generate and process differences between sequences.

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

Diff hooks are used to process the raw output of the diffing algorithms. You can chain them to achieve different output formats.

• 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

The library also exposes simple-to-use functions for common use cases, such as diff_line for comparing arrays of strings (lines of a file).

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