Summary

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

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

Information

Owner

chipx86

Repository

Review Board SVN (deprecated)

Branch

trunk

Bugs

Depends On

Reviewers

Groups

reviewboard

People

Description

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.

Testing Done

Unit tests passed. I tested several diffs I have here and they all rendered as correctly as one can expect.

A bunch of nits.  I don't know this algorithm, but I'm assuming it works since you spent so much time pulling your hair out.

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 1)

Is this really necessary?  Won't list(self.get_opcodes()) work?

chipx86 June 17, 2007, 5:42 p.m.

Yep. Silly me. Removed this function. I actually meant to add the [opcode for ...] to the unit tests, but I was using this from the python shell to test. Should have realized list() would work though.

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 1)
```
Private functions should just use single underscores
```
1. chipx86 June 17, 2007, 5:42 p.m.
  Fixed.

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 1)

I'd rather see a "class NotReachedError(Exception)" somewhere and raise that, instead of a typeless string.

chipx86 June 17, 2007, 5:44 p.m.

Agreed. I was surprised this didn't exist in some form already. Any idea where we should put this? Djblets?

david June 18, 2007, 12:26 p.m.

How about just reviewboard.utils.  It's so tiny that putting it in djblets seems silly

/trunk/reviewboard/diffviewer/diffutils.py (Diff revision 1)

difflib's a standar library module, and should stay in that group

chipx86 June 17, 2007, 5:44 p.m.

Not sure what you mean? That I should just "import difflib"?

david June 18, 2007, 12:26 p.m.

No, just keep in the group with the other system modules
(a-la PEP-8).  You moved it down into the local module
group.

/trunk/reviewboard/diffviewer/diffutils.py (Diff revision 1)

raise "string" is deprecated.

Use raise Exception("string")

chipx86 June 17, 2007, 5:45 p.m.

Ok. Should probably use NotReachedError here too.

david June 18, 2007, 12:27 p.m.

This isn't really a not-reached, just a normal input validation error.

/trunk/reviewboard/diffviewer/diffutils.py (Diff revision 1)

Does this mean we're diffing twice?

chipx86 June 17, 2007, 5:46 p.m.

This is only for the interline diffs. We'd never use the same differ for the files and for the lines.

david June 18, 2007, 12:27 p.m.
```
Ok, cool.
```

One question; do we need to do anything for migration to work when updating the database schema or will default=0 handle that for us?

chipx86 June 17, 2007, 5:41 p.m.

default=0 looks to handle it in my tests. All my old diffs used SequenceMatcher, but new ones used MyersDiffer.

david June 18, 2007, 12:26 p.m.
```
Awesome.
```

Ship it!

Man, now that I look a little closer this really does feel like C code.  Oh well.  After you do the tests you talked to me about, this looks fine.  There are certainly little style cleanups that can be done, and I'm sure some careful examination could yield some more pythonic code, but you're the maintainer of this bit, not me ;-)

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 4)

You're inconsistent in your number of lines between methods in this class.

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 4)

What does the comment here mean?  It's not apparent whether it's explaining anything or just old code.

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 4)

This can be made a little bit sexier using "for i, item in enumerate(data)"

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 4)
```
Same here with enumerate
```

Ship it!

It looks like this change was already checked in, but...

/trunk/reviewboard/diffviewer/myersdiff.py (Diff revision 4)
```
s/dicards/discards/
```
1. chipx86 June 20, 2007, 7:48 p.m.
  Eep, good catch, thanks.

Are there any tests that demonstrate how this new diff is better than before?

chipx86 June 20, 2007, 7:48 p.m.

No good unit tests or anything, but any diff containing code that had indentation changed should be much improved, for one. The algorithm we now use is the same that GNU diff and many other programs use, which produces much better results than SequenceMatcher. I guess you'd just have to try and compare, but at VMware we had a number of people complain about some of the diffs SequenceMatcher generated.