Analyzing and Evaluating the Behavior of Git Diff and Merge

Despite being widely used, the algorithms that enable collaboration with Git are not well understood. The diff and merge algorithms are particularly interesting, as they could be applied in other contexts. In this thesis, I document the main functionalities of Git: how diffs are computed, how they are used to run merges, and how merges enable more complex operations. In the process, I show multiple unexpected behaviors in Git, including the following: The histogram diff algorithm has pathological cases where a single-line change can cause the entire rest of the file to be marked as changed. The default merge strategy (ort) can result in merges requiring exponential time in the number of commits in the history. Merges and rebases are not commutative, and even when merges do not result in a conflict, the result is not specified but depends on the diff algorithm used. And finally, sometimes when two sides of a merge add different lines at the same position, the result is not a conflict, but a merge containing both changes after each other, in arbitrary order.