Diff returns an anchored diff of the two texts old and new
in the “unified diff” format. If old and new are identical,
Diff returns a nil slice (no output).
Unix diff implementations typically look for a diff with
the smallest number of lines inserted and removed,
which can in the worst case take time quadratic in the
number of lines in the texts. As a result, many implementations
either can be made to run for a long time or cut off the search
after a predetermined amount of work.
In contrast, this implementation looks for a diff with the
smallest number of “unique” lines inserted and removed,
where unique means a line that appears just once in both old and new.
We call this an “anchored diff” because the unique lines anchor
the chosen matching regions. An anchored diff is usually clearer
than a standard diff, because the algorithm does not try to
reuse unrelated blank lines or closing braces.
The algorithm also guarantees to run in O(n log n) time
instead of the standard O(n²) time.
Some systems call this approach a “patience diff,” named for
the “patience sorting” algorithm, itself named for a solitaire card game.
We avoid that name for two reasons. First, the name has been used
for a few different variants of the algorithm, so it is imprecise.
Second, the name is frequently interpreted as meaning that you have
to wait longer (to be patient) for the diff, meaning that it is a slower algorithm,
when in fact the algorithm is faster than the standard one.
The pages are generated with Goldsv0.6.6. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.