Module diff 

Lining two releases of the same header up, so the merge can see what moved and what did not.

The merge needs, for two sequences of code lines, the pairs that are the same line. What it does with them is in merge.rs; this is only the lining up, and it is the part where an easy implementation is too slow on the files that matter. elf.h is four thousand lines and changes at every release, and the textbook table of one cell per pair of lines is sixteen million cells for one file and one release, eight times over.

So three steps, cheapest first, which is what every diff worth using does:

1. The common prefix and the common suffix. Two releases of a header agree about almost all of it, and agreeing at the ends is free to notice.
2. The lines that appear exactly once in each of what is left. Those are anchors: a line that is unique on both sides and in increasing order on both sides cannot be anything but itself. This is Bram Cohen’s patience diff, and the reason it is right for header text rather than merely fast is that it refuses to match the eighth #endif with the third one.
3. The table, for what is left between two anchors, which after the first two steps is small. A region with no unique line at all and more cells than the cap is left unmatched, which makes the merge write that region out per release. That is coarser and never wrong.

Every step narrows the problem and no step can match two lines that are not equal, so the worst this can do is a bigger tree than necessary.

Functions

aligned

The pairs of positions that hold the same line, in increasing order on both sides.