Switch to Eugene Myer's O(ND) diff algorithm

Review Request #79 — Created June 17, 2007 and submitted — Latest diff uploaded


Review Board SVN (deprecated)


Python's SequenceMatcher had a lot of flaws we had to work around and produced unoptimal diffs. It also prevented us from doing intelligent whitespace trimming or extending it for function name scanning (which we'd like to do someday).

I added an implementation of Eugene Myers's O(ND) diff algorithm, which is used in GNU diff and other diff programs. While the diffs aren't always necessarily better, they're a step in the right direction. The whitespace trimming alone should improve many diffs though, especially when indenting code.

We remain compatible with the old SequenceMatcher diff wrapper code. A version compatibility flag is stored in the DiffSet model that indicates whether to use the old SequenceMatcher or the new MyersDiffer. This will keep existing review requests and comments intact.
Unit tests passed. I tested several diffs I have here and they all rendered as correctly as one can expect.