What are the files in the Staging Area after a merge conflict?

This output is peculiar, and part of it is due to something I consider a bit of a bug in git ls-files (not enough of a bug to care about, though, and it's not clear to me what I would do differently—maybe include an extra column for the C letter, a la git status --short having two columns for status letters?). In particular, when you use the -t option you get a state flag, but when you use the -m flag you get an extra line with the C state for some files (those for which the working tree copy does not match the index copy). This means that you can see a file name twice.

Here, though, you're seeing one file name five times. You would see it three times, except for this -m flag inserting the extra line (twice). That gets us to the question you put in the title:

What are the files in the Staging Area after a merge conflict?

This is where the term staging area falls apart a little bit. Mostly, it's a better term than the meaningless word index or the overused (and, as a result, meaningless) word cache: the staging area holds files staged for commit. That makes sense. But when there's a merge conflict going on, the files in the index/staging-area/cache aren't "staged for commit" at all, so the term staging area is now just wrong. I like to drop back to the first meaningless term, "index", in this case.

The real key here is the staging slot number, which appears after the blob hash ID and before the file's name:

4111d50ada6cc03ec6079f226c23efa3142c9c94 1 file1.txt

These "staging slot numbers" allow one file to appear more than once in the index / staging-area: each entry has a different slot number, which allows us to access it using Git's :1:file.txt, :2:file.txt, and :3:file.txt syntax (in git rev-parse / gitrevisions).

The "normal" slot number, when the staging area is not expanded for merging purposes, is always zero. (Try git ls-files -s when not in the middle of a conflicted merge.) A slot-zero file is properly staged and ready to be committed. You can access this "copy" (the blob instance, really) as :file.txt with the gitrevisions syntax.

Blob 4111 appears to be the version common to both branches before they went separate ways. Blob 74a9 is the version in the master branch, and blob 0d02 is the version in the b2 branch.

That's correct, and that's the idea here. It would be more accurate to say that the file in slot 1 is the file that is in the merge base commit. The file in slot 2 is that from the tip commit of the current branch master, i.e., from the current commit, and the file in slot 3 is that from the commit being merged, i.e., the tip commit of b2.

This gets right to the heart of how git merge works, when doing a real merge:

• Git locates the two commits to be merged. One of them is the current or HEAD commit, and the other is the commit you named on the command line (git merge b2).

• Git uses the metadata stored in those two commits, and in earlier commits found via those two commits, to locate the common-starting-point commit.

• Having thus located exactly three commits,¹ the merge can now begin:

  • Git reads the merge base commit into the index at "slot 1".
  • Git reads the current commit into the index at "slot 2". Note that since git merge requires that everything be "clean", this is equivalent to moving each slot-0 entry to a slot-2 entry.
  • Git reads the other commit into the index at "slot 3".

  So now we have all three instances of each file in the index, in the three slots. The next step is to figure out if there's a shortcut for how the final merged file should look.

This "short-cut" step actually happens early on, without a lot of index entry creation and shuffling-about, as an optimization, but we can pretend it doesn't. Remembering that the goal of merging is to combine changes, and that if we have three copies of some file, they could be all identical, or two of them might match, we can take the following short-cuts:

• If all three copies match, use any copy. Nobody changed anything so we're done! (Stop here, don't go on to the remaining tests.)
• If the merge base copy matches our copy, use their copy. We didn't touch the file, and they did, so the merge result is their file.
• If the merge base copy matches their copy, use our copy. They didn't touch the file, and we did, so the merge result is our file.
• If our copy and their copy match, use either of these copies: we both made the same changes to the file, so either one works.
• None of the three copies match: we need to do real, actual, hard work.

If the short-cut method finds the right resulting file, the merge code moves that version of the file to slot zero, erases the entries for the other two slots, and if needed, updates the working tree copy of the file as well. That file is now fully merged and nothing else has to happen.

If the short-cut method fails to find the right resulting file, the merge code leaves all three files in the index, in those three slots. It then uses more code—the same code you can run yourself, using git merge-file, if you like—to attempt to do a full three-way merge, combining the changes you made with the changes they made:

• This full three-way merge can succeed, in which case, the merged file is there in the working tree, and the merge code does an internal git add to write this copy to slot zero of the index, which also erases slots 1-3.

• Or, this full three-way merge can fail, in which case, the merge attempt is there in the working tree complete with conflict markers, and the merge code does nothing (except remember to call the merge "conflicted").

The merge code repeats this for every file in the three staging slots. Ignoring all the other special cases—such as detecting renames or handling new or deleted files, or the items mentioned in footnote 1—this covers everything needed. In the end, either all the files have been merged and everything is at slot zero now, or the merge has a conflict and git merge stops and makes you fix up the mess.

What do the tags C and M mean in this context?

M means unmerged, i.e., the slot number is not zero. That's all it means, so with -s, this flag is kind of useless, since you can just look at the slot number.

C means changed, i.e., this file does not match the working tree copy.

¹What do we do if there aren't exactly three commits?

This case occurs in multiple different ways. One obvious way is Git's so-called octopus merge, where you run:

git merge b1 b2 b3

to merge three other branch tips with the current (HEAD) commit to make a four-parent merge commit. This kind of merge is done by the git-merge-octopus strategy, which doesn't use the index in the same way at all, and generally does not permit the kinds of conflicts that we'd try to resolve with git merge-file. So that one, fortunately, sidesteps all of this. Explaining how git-merge-octopus actually works is ... tricky, especially since I don't understand the octopus merge base computation myself.²

But even with a two-commits-as-inputs merge, the automatic merge-base finding can have a problem. Git defines the merge base as the best common ancestor, using the Lowest Common Ancestor algorithm as extended for DAGs. This algorithm is described here on Wikipedia with an example graph. The LCA of nodes x and y is not just one node, but rather two. In this case, git merge-base --all will find both of these "best common ancestor" commits. (In general, in a sufficiently complex graph, there could be many merge bases. The two-merge-base case definitely arises now and then due to criss-cross merges.)

Git has, at the moment, two answers to this problem:

1. Using git-merge-resolve, we pick one of the N merge bases, and pretend that is the sole merge base.
2. Using git-merge-recursive, we pick all of the merge bases, and merge them with git merge. This makes a new, but temporary, commit, which we then use as the merge base for our original problem.

When using method 2, merging the merge bases can again find multiple merge bases; if so, Git merges these merge bases and uses the resulting temporary commit as the merge base for merging the two merge bases. That in turn can recurse, but since each one "nibbles away" at the DAG, the recursion is guaranteed to terminate.

(The new git-merge-ort code—not yet in standard use in any released version of Git; if you have it, you have to call for it with -s ort—does the same kind of recursion, as I understand it, but I have not looked at the code itself.)

²Running git merge-base --octopus can do one computation for you, and running git merge-base without --octopus can do another computation for you. These produce different results. I never delved enough into the octopus strategy code to figure out whether it uses one of these two algorithms, or perhaps even some third algorithm.