libgit2/libgit2 — pull request #1389 by ethomson (2013-03-04 02:56:08+00:00)
Title: Merge trees

I'm trying to break that big nasty merge PR into smaller, more manageable PRs. These two commits will take 2 trees and an optional common ancestor tree, and produce a `git_merge_index` that represents the changes.

A `git_merge_index` is *remarkably* similar to a `git_index`, however conflicts are tracked differently. A `git_index` records conflicts by filename only, which makes determining what happened during a rename conflict impossible. A `git_merge_index`, in contrast, keeps track of the files as they were renamed.

Consider that there exists some file where file `A1` is renamed to `B1` in one side and `C1` in the other, while the file `A2` is renamed to `A2` and `A3`. The resultant `git_index` will contain the following entries:

100644 1bdef746acfcabf0c1229b6afa34164bf8f3ce7b 1	A1
100644 8c4bc39a4ee424d8a5d550c73f471dafbc5023e0 1	A2
100644 1bdef746acfcabf0c1229b6afa34164bf8f3ce7b 3	B1
100644 8c4bc39a4ee424d8a5d550c73f471dafbc5023e0 3	B2
100644 1bdef746acfcabf0c1229b6afa34164bf8f3ce7b 2	C1
100644 8c4bc39a4ee424d8a5d550c73f471dafbc5023e0 2	C2

A `git_merge_index`, however, contains conflict grouped *by the conflict* instead of *by the filename*. For example:

{
100644 1bdef746acfcabf0c1229b6afa34164bf8f3ce7b A1
100644 1bdef746acfcabf0c1229b6afa34164bf8f3ce7b B1
100644 1bdef746acfcabf0c1229b6afa34164bf8f3ce7b C1
},
{
100644 8c4bc39a4ee424d8a5d550c73f471dafbc5023e0 A2
100644 8c4bc39a4ee424d8a5d550c73f471dafbc5023e0 B2
100644 8c4bc39a4ee424d8a5d550c73f471dafbc5023e0 C2
},

This has additional data above a `git_merge_index` and is trivially convertable to a `git_index` that would represent the merged output or - like an index - into a `git_tree`.

Looking only at the above example, one could make an argument that we could somehow tie the conflict entries back together using the same algorithm that determined that they were rename conflicts in the first place. Even if you wanted to take the computational hit of recomputing the similarity each time you reload the index (and you probably don't), it's not deterministic.

In a rename 2 -> 1 conflict, for example, the ancestors of the conflict isn't even recorded. Consider files `A` and `B` both renamed to `C` in the two branches. The resultant conflicts only show the two sides - presumably as a result of these being treated like add/add conflicts:

100644 bcf3dc80800397ab485dd453c822a437c03662e6 2	C
100644 9141c522b4f783453452c318d190288383b8c5d5 3	C

Further, since core git treats these conflicts as separate between the ours and theirs side, once you began resolving these sides independently, it's still more difficult to pair these sides back up.

Thus, I think it makes more sense to track conflicts as conflicts and not track the conflicts by filename.