3988: Differ doesn't align lines properly and displays diff based off of the misaligned lines


What version are you running?

2.0.19; also tested on 2.5 beta 3.

What's the URL of the page containing the problem?


What steps will reproduce the problem?

  1. Create a change of at least medium complexity that spans multiple lines. For example, split one function call into a variable assignment followed by a function call.
  2. Upload diff to reviewboard.
  3. View the diff on the reviewboard site.

What is the expected output? What do you see instead?

Expected: the diff viewer graphically displays the changes in a sensible way.
Instead: it often displays the changes in a bizarre, unhelpful way that misses actual correspondences and adds spurious ones.

See attached images for an example comparison of a reviewboard diff display vs a much more sensible diff display by p4merge.

What operating system are you using? What browser?


Please provide any additional information below.

Finding the shortest way to convert file A to file B is a solved problem. In fact, reviewboard's code does just that: it uses Myers's algorithm to find its initial diff.

HOWEVER, reviewboard then splits up its diff into lines. Every line that's in one file and not the other at all gets categorized as an insert or delete as appropriate. Lines with changes in both directions are categorized as edited lines. So far this is OK. But the next step is that the sections of edited lines are forced to match up; unmatching lines are relabeled as inserts or deletes. Let me explain with an example. Suppose that I edited 3 lines into 6 lines. E.g. I started with AA\nBB\nCC, and modified it to Aa\nAa\nBb\nBb\nCc\nCc. The correct correspondence, which the initial diff pass correctly surmises, is that line 1 gets broken up into 2 lines which are each slightly modified, as does line 2, and as does line 3. But reviewboard's algorithm calls the 3 left lines and the 6 right lines "modified", then tries to line them up. The result is it decides that AA goes to Aa, BB goes to Aa, CC goes to Bb, and then there are three new inserted lines Bb, Cc, and Cc.

This step was really bad! It turned a very useful diff into a completely useless one. Remember, the only reason we called these lines "modified" in the first place was that there actually was some element on each of them that carried over from one version to the next. But now in this relabeling and realigning step, we have lost that. It doesn't make any sense whatsoever to call the new line "Bb" an edit of the original line "CC". At the very least, CC should be a delete and Bb an insert. But in fact we have this great information about the closest diff from the Myers algorithm and we should really just be using that to show that CC becomes the two lines Cc\nCc.

Again, this is a solved problem and the work is already being done, it's just being thrown away afterwards. Please check out the attached images for an example!

#1 david

I think you've just managed to find a case where our algorithm performs particularly badly. The heuristics we use are the same that GNU diff does, for better or worse. If you think you can improve it, we'd be happy to look at a patch.

#2 scmccarthy

Yes, the initial heuristics used to find the diff are typical and fine. The problem, like I said, is that the display code is screwing it up afterwards.

Gotta admit I'm a bit miffed that the effort I put in to figure out what you're screwing up that other diff utilities aren't is completely ignored in your response. I understand not wanting to fix the bug (after all, no one else seems to have complained about it in over a year, and I'm not currently using reviewboard now either), just wish it seemed like you'd read the description I put together. Regardless, thanks for taking a look.

#3 mkoerner

Wanted to pitch in that there's at least one other person who would appreciate a fix for this. I think scmccarthy summarizes the problem very nicely.

Maybe I'm missing context that would make this bug hard to fix, but david's response doesn't make me confident that this is necessarily a fundamental issue with the algorithm.