Differences between plain-text diff and formatted diff

Question

Plain-text diff and formatted diff produce different results in what they consider was added.

---

I wondered about the following editing diff in a recent post of mine:

I clearly added a sentence to the end of the paragraph, but the diff thinks I added something between the three final words.

---

The plain-text diff shows a saner result: The edit is clearly a sentence added to the end:

Answer 1

To you and me, it's obvious that the diff engine didn't find the optimal solution here; however, to the computer it's not. Let's break this down to the simplest example. Consider you wrote this:

A B

and later edited it to be this:

A B A C B

(essentially, "A" is the word "Finder" and "B" is the word "running" in your case). Obviously, what we'd like to see the diff engine show is this, where the highlight means "this letter was added":

A B A C B

But what the diff engine gives us is this:

A B A C B

Both solutions are correct, and both solutions – as far as the diff engine is concerned – are equally good, since they both consist of "adding three letters" (in technical terms, they are both shortest edit scripts).

The diff algorithm guarantees to find one such shortest edit script, but it doesn't guarantee which one. It's pretty much a question of chance¹.

Fixing this would pretty much mean using a different algorithm, which also (in some way) considers subsequent additions to be better than separated additions. This would have some drawbacks, though:

1. It's guaranteed to have other edge cases. There will always be examples where a human being actually looking at the text will find a better diff than an algorithm. So we may fix this very example, but may just as well break another one.

2. It will probably be slower. The diff algorithm we use has pretty good performance characteristics (if you're interested, here's the description of the algorithm; we're using a slightly modified version of this implementation), and we wouldn't like to give that up.

3. Even setting 1. and 2. aside, this would mean quite some effort for something that works well in the 99% case. We're quite happy with the diff engine's work, especially after our recent improvements, and even though there are edge cases like the one you found, the diff is almost always good.

4. The diff in your example is not an uncomprehensible mess. Sure, it's not what you'd expect, but it's a result we can live with. Not to forget that despite looking weird, it's actually correct², and that you also have the choice of another diff view.

With those reasons in mind, I'll have to make this wontfix – it's just not worth it, sorry.

---

^{1 The algorithm is deterministic, so it's not truly random. But which of the solutions is found depends on many things, including what comes before and what comes after the content in question. If you actually run the diff engine over the ABACB example, for instance, it realy does find the "better" solution; if you run it over "ABC -> ABCBDC", it finds the "worse" solution.
2 The additional space before the period (you mention this in a comment) is somewhat related to this; the diff engine is set to be a bit lenient about whitespace, since this in most cases makes the diff more readable.}