Version Control Blog

Bram Cohen announces:

Those of you who have used version control systems for a long time, or anything which has to diff extensively for that matter, know that once in a while they completely bungle a diff and give output which is, to put it charitably, extremely confusing.

Coming up with an algorithm which reliably gives good diffs is far from trivial, but is a problem which has now thankfully been solved. If you get the latest version of bazaar and use its diff utility it will give reasonable diff output on almost anything. All other version control systems (and I mean all others) should switch to using bazaar’s diff algorithm as a swap-in replacement, a change which has essentially no downside. (It also has better asymptotic runtime, and code which is easier to understand and debug.)

Later in comments he briefly explain new algorithm:

Instead of doing a longest common subsequence on everything, it does a longest common subsequence on lines which occur exactly once on both sides, then recurses between lines which got matched on that pass.

Read at: Bram Cohen: “The diff problem has been solved”.

I’d like to try it out when it becomes available for Subversion or Git.

This entry was posted on Sunday, June 24th, 2007 at 9:14 pm and is filed under Bazaar/bzr, Ideas. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.