text_diff.h

What it is for

An undo step for a text field that stores what was typed rather than two copies of the whole text; a preset browser showing what an edit changed in a patch's description; state sent to a remote editor as edits instead of as the whole document. The reference has it for the third; a plugin has more use for the first two.

How

Myers' O(ND) algorithm in its linear-space form: find the "middle snake" of the edit graph from both ends at once, split there, recurse on the two halves. Memory is proportional to the inputs, not to their product, and the edit script is MINIMAL -- no shorter list of inserted plus removed characters turns the original into the target. Minimal in characters, not in changes: where two equally short scripts exist, one may split an edit a person would call one ("abcab" to "ab" removes "cab" or "abc" -- or "c" and "ab" apart -- at the same cost). The common prefix and suffix are stripped first, which is most of the work for the usual case of one small edit in a long text.

The comparison is by CHARACTER (UTF-8 code point), so a change never starts or ends in the middle of one and inserted text is always whole characters. Invalid UTF-8 is compared byte by byte, so any std::string round-trips exactly.

The size guard

Myers is fast when the strings are similar and slow -- N times D -- when they are not, and both strings may come from outside. So the search runs on a work budget, and a differing region of more than two million characters is not searched at all (the search's memory grows with the region). Either way, whatever is still unresolved is described as one replacement: the changes still reproduce the target exactly, they are just no longer the fewest possible, and isMinimal() says so. A budget of operations rather than of time, so the same inputs give the same changes on every machine.