Crate fc_diff 

fc-diff — line diffing, Myers’ O(ND) algorithm.

Why this is in Rust and what that buys

A diff is the one place in this system where the cost is superlinear in the input. Myers is O(ND) rather than the O(N*M) a dynamic-programming table would need, but on a 20,000-line file that is still ~400M comparisons in JavaScript’s worst case. In Rust the same walk is memory-safe, allocation-free on the hot path, and roughly an order of magnitude faster — which is what makes live diffing while a user types viable at all.

The invariants, and why they are the whole contract

A diff that is subtly wrong is worse than no diff: a reviewer cannot tell a missing line from a mis-attributed one. Two properties are therefore asserted on every test case rather than described:

1. Reconstruction. Dropping the Add lines reproduces the original; dropping the Remove lines reproduces the revision. This single property catches every possible backtracking off-by-one at once.
2. Text preservation. No line’s text is altered, only its attribution.

Line numbers are 1-based

What a human reads, and what git blame prints. The algorithm works in 0-based indices internally; the conversion is part of the public contract. None means the line does not exist on that side, and callers must render nothing rather than 0 — inventing a line number is how a reviewer is misled about where a change landed.

Structs

DiffLine

One line of output. old_line/new_line are 1-based, or None when the line does not exist on that side.

DiffStats

Counts for a diff header.

Enums

DiffKind

How a line relates to the other side of the diff.

Functions

diff_lines

Compute a line diff between two texts.

diff_stats

Counts for a diff header.

js_diff_identical

Whether the two inputs are identical after line splitting.

js_diff_kinds

The per-line kinds, as a flat Int32Array of length lineCount.

js_diff_new_lines

1-based line numbers in the revision; -1 where the line was removed.

js_diff_old_lines

1-based line numbers in the original; -1 where the line is new.

js_diff_stats

[added, removed] as a flat two-element array.

js_diff_text_at

The text of line index, or "" when out of range.

js_line_count

Line count without materialising the text array.

split_lines

Split text into lines, without a phantom trailing empty line.