Diff Algorithms

Summary

For software engineers, diffs are a ubiquitous method for representing changes: We use diffs to compare different versions of the same file (e.g., during code review or when trying to understand the history of a file), to visualize the difference of a failing test compared with its expectation, or to apply changes to source files automatically. Every project I worked on professionally or privately eventually needed a diff to visualize a change or to apply a patch. However, I have never been satisfied with any of the freely available diff libraries. This was never really a problem professionally, but for private projects, I have copied and modified my own library from project to project until I mentioned this to a colleague who set me on the path to publish my Go library (a port of a previous C++ library I used to copy and modify). Boy, did I underestimate how close my library was to publishability! Anyway, I did it and I learned a whole lot about diff algorithms. You can find my library at znkr.io/diff and what I learned in this article. I am not finished learning yet, so I plan to update this article as my understanding continues to evolve. Existing Diff Libraries Let me start by explaining why I am dissatisfied with existing diff libraries. There are a number of attributes that are important to me. Not all of these attributes are important for every use case, but a diff library that I can use for all of my use cases needs to fulfill all of them. Usually, the input to a diff algorithm is text, and most diff libraries only support that. However, I occasionally have use cases where I need to compare things that are not text. So any diff library that only supports text doesn't meet my needs; instead, I need support for arbitrary sequences. The resulting diff output is intended to be readable by humans. Quite often, especially for text, a good way to present a diff is in the unified format. However, it's not always the best presentation. A diff library should make it e...