# Diff removes a space when it shouldn't

This is a pathetic bug, I know, but each and every... The diff engine is removing a space here.

Screenshot of the infelicity for your delectation:

In the source there is no space:

<p>... the checks are done in codeor not.</p>


and the diff engine thinks that the space has been added:

<p>... the checks are done in code<span class="diff-add">, </span>or not.</p>


Some regex being a bit greedy?

-
Stop blaming regexes for everything -- they're good guys :) And they have nothing to do with this. This behavior is sort of by design (part of the reason here), but you've actually found an edge case that I'd like to prevent. I'll have a look whether it's solvable, but not at the cost of creating on-off-on-off diffs. –  balpha Feb 9 '13 at 16:14
You mean there's something you can't blame regexes for @balpha? You scare me :-). –  ben is uǝq backwards Feb 9 '13 at 16:35
I saw it happening for long time and can swear I saw a bug report about it long time ago but can't find it anymore. –  Shadow Wizard Feb 13 '13 at 9:42
@balpha THE <CENTER> CANNOT HOLD IT IS TOO LATE –  Doorknob Feb 14 '13 at 0:50

Fixed in the next build.

So here's the problem. Before we diff a text, we have to split it into unbreakable tokens, which basically means words and punctuation (if we didn't do that, we'd end up with an unreadable character-by-character diff).

But between two words, there's usually a space. If we considered this space a token on its own, and you replaced one sentence with another, the diff engine would say "all these spaces haven't changed, so we'll show them as unchanged." Which unfortunately would give you something like this:

And you can imagine how unreadable this would be for longer sentences. That's why so far, we have considered the space after the word to be part of the token, so the diff engine doesn't see unchanged content interspersed with changed words. Thus we get this much more readable version:

Enter the next problem: With trailing spaces being part of the token, the fairly common edit of adding or removing punctuation suddenly looks like this:

because "bar " and "bar" are different. This diff is actually correct (removing a word and re-adding it is a valid representation of "no change"), but it isn't clear.

What we'd like such a diff to show is that "bar" wasn't changed. To solve this, when we compare two words, we "cheated" by telling the diff engine to consider them identical if the only difference is the trailing space.

This creates precisely the problem you noticed (note that the "code or not" in your diff is exactly this punctuation example). The diff engine is told that "bar " and "bar" are identical, and thus when outputting "here's an unchanged word", it'll just output one of the two (it thinks it doesn't matter which one). This works fine in the inline diff:

– while that's not 100% correct (since the space after the comma was not actually added), it's good enough to understand the diff.

In the side-by-side diff however (which didn't exist yet when our diff engine was created in its current form), this "cheating" is mercilessly visible:

So much for where the problem comes from. Now here's what I've changed: I realized that to solve the "add punctuation" problem without the cheating, while still solving the "unchanged spaces" problem, we just have to tie the preceding, not the trailing space to any particular word.

That way, you're comparing " bar" and " bar", and don't have to lie to the diff engine, causing problems along the way.

That's why from the next build on, you won't be seeing this anymore:

but this:

There's just one new problematic edge case:

There we are again – comparing "Jeff" to " Jeff". Same problem, right? Kind of, but it's much more narrow: Trailing whitespace can differ much more often then leading whitespace; the only interesting case is at the beginning of a paragraph.

But hey: At the beginning of a paragraph, a browser won't render a space anyway. So if we just always make sure that the first word in a paragraph is preceded by a silent space, we solve this problem as well:

Note that this isn't 100% accurate either: the space after "and" should be green. But that's the only issue, and it doesn't hinder diff readability.

On a final note: I'm very aware that there are lots of edge cases that won't give you a perfect diff with this system. But that's fine. What we want is the usual text editing diffs to be easily readable. That's why "add a comma" should be easily understandble, but I don't care so much about "add the missing space after the comma" – because the latter is much less common. And even that one is correct:

– it's just not as clear.

-
Yayyyyyy better diffs –  Ben Brocka Feb 13 '13 at 21:28
I’m interested in the theory here: intuitively, this looks like an easily solvable problem (any human would be able to see the optimal diff rendering immediately) – then again, substring matching problems are often hard. So is “render an optimally compact diff” a hard (as in, NP complete) problem? –  Konrad Rudolph Feb 13 '13 at 22:15
@KonradRudolph The diff algorithm (xmailserver.org/diff2.pdf) guarantees to find the (rather, a) shortest possible edit script (which you could also call an optimally compact diff) of whatever you throw at it. That algorithm is O(ND) (some details here). If we wanted the shorted possible version, we would just throw character by character at the algorithm (ignoring the issue of diffing HTML for a moment). But what we want is not the shortest, but an as readable as possible version while retaining a well-performant algorithm. –  balpha Feb 13 '13 at 22:28
@balpha Yes, I meant finding the “optimal” rendering (group changes meaningfully, which probably means largest possible batches), not the shortest diffing. (I’m a bioinformatician, the diff algorithm is my daily bread ;) – easily seen by the fact that Gene Myers, its author, is bioinformatician) –  Konrad Rudolph Feb 13 '13 at 22:30
That sir, is an amazin' answer; as they always are when you're talking about diffs! –  ben is uǝq backwards Feb 14 '13 at 8:16
Seems to me that it's more intuitive to see punctuation treated as after a word, not before. Perhaps another solution is to lose the tokenization, but "merge" areas of diffness that are separated only by a space (to remove the effect you detail in your paragraph beginning But between two words), as a post-production step. –  Lightness Races in Orbit Feb 15 '13 at 12:44

In the revision history to Which ending should come if I kill all of the NPCs in Fallout: New Vegas?, the space between "Fallout" and "New Vegas" that appeared in the original post appears to disappear in the "before" column in the side-by-side diff view. In addition, the space between "endings" and the deleted "to come" in the body of the question also appears to be gone.

-