Diffing

Diffing is the process of computing differences between two sequences, most commonly text files. A diff identifies insertions, deletions, and modifications, and can be used to produce a patch that, when applied to the original, yields the new version. Diffing underpins many software development tasks, including version control, code review, and file synchronization.

Common algorithms aim to find a maximal set of unchanged elements. The Longest Common Subsequence (LCS) concept forms the basis for many diffs, while the Myers diff algorithm, introduced in 1986, remains influential for its efficiency in producing a minimal edit script. Diff tools can operate at different granularities, such as line-based or character-based comparisons, depending on the level of detail needed.

Output formats typically include unified diff and context diff. A unified diff shows a sequence of hunk headers and lines prefixed with minus signs for deletions and plus signs for additions, with several context lines to aid readability. The patch file produced by a diff can be applied to the original file to reconstruct the new version, using tools such as patch or built-in version control features.

Applications are broad. Version control systems like Git and Subversion rely on diffing to display changes, merge divergent histories, and generate patches for review or distribution. Diffing also supports code reviews, synchronization across devices or systems, and various backup workflows. For binary files, diff concepts may indicate changes or delegate to binary deltas.

Limitations include difficulty in detecting moves or refactors with simple diffs, and interpreting edits without understanding semantic intent. Advanced approaches extend diffing with rename detection, reordering awareness, or structural differencing based on abstract syntax trees to better capture meaningful changes.