One of the most critical features of modern day version control relies on a poorly understood algorithm –
diff3. What is it, how it works, and why it could be improved.
There are two critical operations that need to know the differences between files:
- Reviewing new changes
- Merging multiple changes
First, version control systems like
git don't actually store the patched differences between files. Instead,
git stores completely new files for every revision and computes the differences at runtime. That's why you can switch between really old revisions and new revisions quickly – otherwise every patch would need to be sequentially applied.
So how does
git know the differences between files? For comparing two files,
git uses a a set of algorithms called
diff2 that mostly follow Myers' An O(ND) Difference Algorithm and Its Variations. It's closely related to a common interview question, the longest common subsequence problem.
But one of the most challenging aspects of version control is the 3-way merge. Let's say you and a coworker independently make different revisions to a common document and then try to reconcile the differences. It's possible that some changes can be merged together automatically, but there might exist conflicts.
One merge tool that
git uses is called
diff3 or sometimes
kdiff3, which, as you can guess, produces a merged output of 3 different files that share a common ancestor.
diff3 was originally written in 1976 in Version 7 of Unix. The algorithm is a set of heuristics that tries to capture most edge cases of merging text together, but it's not straightforward or easy to understand. Doug McIlroy (or an engineer named Paul Jensen) wrote the first version of
diff3 for Unix. You can read McIlroy's paper, An Algorithm for Differential File Comparison.
You can enable printing merge conflicts in
diff3 format with the command. This has the benefit of showing you the diff output that includes the common ancestor, which usually helps when resolving conflicts.
$ git config --global merge.conflictstyle diff3
You can browse the source code of