git merge: how did I get a conflict in BASE file?

Question

I have the following in the BASE file of a git merge:

<<<<<<<<< Temporary merge branch 1
    - _modifiedTimeWeak = 4.25.2019::11:41:6;
    - _lastID = 3;
    - weakCGTime = 4.25.2019::11:42:20;
    - strongCGTime = 1.2.1990::0:0:0;
=========
    - _modifiedTimeWeak = 5.1.2019::8:52:36;
    - _lastID = 3;
    - weakCGTime = 5.1.2019::8:52:36;
    - strongCGTime = 3.20.2019::17:13:20;
>>>>>>>>> Temporary merge branch 2

I've performed a baseless merged of the file now, so there are no outstanding issues but I would like to understand what could have gone wrong.

I have checked the BASE commit as identified by git merge-base, and it did not include merge conflicts as presented, so that is ruled out. This is also the first time this has been encountered despite many merges having been done in this repository prior to this occurring.

It may be worth noting that I was using git merge merge-tool.

What could cause a BASE file when performing a merge to have merge conflicts appear within it, and what steps can be taken to avoid this from occurring in the future?

Answer 1

Jargon answer

These occur when there are multiple merge bases and merging the merge bases produces a merge conflict. The merge base candidates are the LCAs of the commits you choose to merge, in the subgraph induced by the commits:

DEFINITION 3.1. Let G = (V; E) be a DAG, and let x; y ∈ V. Let G_{x; y} be the subgraph of G induced by the set of all common ancestors of x and y. Define SLCA(x; y) to be the set of out-degree 0 nodes (leafs) in G_{x; y}. The lowest common ancestors of x and y are the elements of SLCA(x; y).

(see https://www3.cs.stonybrook.edu/~bender/pub/JALG05-daglca.pdf). Here G is the directed acyclic graph formed by the commits in your repository, and x and y are the two commits you're choosing to merge. I actually prefer definition 3.2 a bit, though it uses posets, and might be even more jargon-y: it feels more relatable (and in fact is used for genealogy, which is what Git is doing).

The recursive merge strategy, -s recursive, uses all the merge bases, merging each merge base—and committing the result, complete with merge conflicts—and using this temporary commit as the new merge base. So that's the answer to the first part of the question ("What could cause a base file ... to have merge conflicts").

To avoid this, you have several options, but let's describe the problem more understandably first.

Long but more useful answer

You mention that you used git merge-base. By default, git merge-base picks one of the best-merge-base commit candidates and prints that one's hash ID. If you run git merge-base --all on the two branch tip commits, you'll see that there are multiple best-merge-base commit candidates.

In a typical, easy, branch-and-merge pattern we have:

             o--o--o   <-- branch-A
            /
...--o--o--*
            \
             o--o--o   <-- branch-B

The common merge base—as found by either 3.1 or 3.2 in the cited paper; with 3.2, you can just walk back from the two branch tips until you find a commit that's on both branches—is of course commit * and Git merely needs to diff * against the two tip commits of branch-A and branch-B respectively.

Not all graphs are so neat and simple. The easiest way to get two merge bases is to have is a criss-cross merge in the history chain, as illustrated here:

...--o--o--*---o--o--o   <-- branch-C
            \ /
             X
            / \
...--o--o--*---o--o--o   <-- branch-D

Note that both starred commits are on both branches, and both commits are equally close to the two branch tips. Running git merge-base --all branch-C branch-D will print the two hash IDs. Which commit should Git use as the merge base?

Git's default answer is: Let's use them all! Git will run, in effect:

git merge <hash-of-first-base> <hash-of-second-base>

as a recursive (inner) merge. This merge can have conflicts!

If the merge does have conflicts, Git doesn't stop and get help from you, the user. It just commits the conflicted result. This becomes the input to the outer git merge, the one you're directly asking-for:

...--o--o--*---o--o--o   <-- branch-C
            \ /
             M   <-- temporarily-committed merge result
            / \
...--o--o--*---o--o--o   <-- branch-D

The temporary commit isn't actually in the graph, but for the purpose of your outer merge, it might as well be.

How to avoid the problem

Now that we see how the problem arises, the ways to avoid it are clearer—not exactly clear, but clearer than they were, at least:

• Method 1: avoid criss-cross merges.

  By avoiding anything that creates multiple merge bases, you never get into the situation in the first place. That criss-cross merge was created by, at some point, having branch-C and branch-D in this situation:

         o--o--o   <-- branch-C
        /
  ...--o
        \
         o--o--o   <-- branch-D
  

  Someone—let's say person C—ran git checkout branch-C; git merge branch-D to get:

         o--o--o---M1   <-- branch-C
        /         /
  ...--o         /
        \       /
         o--o--o   <-- branch-D
  

  Then, someone—probably someone else, who didn't have the new commit on their branch-C; let's call this one person D—ran git checkout branch-D; git merge <commit that was the previous tip of branch-C before the new merge was just added>, to get:

         o--o--o   <-- branch-C
        /       \
  ...--o         \
        \         \
         o--o--o---M2   <-- branch-D
  

  Once persons C and D shared their new commits, the result was:

         o--o--o---M1   <-- branch-C
        /       \ /
  ...--o         X
        \       / \
         o--o--o---M2   <-- branch-D
  

  and the time bomb was set. It did not go off until you, later, tried to merge commits down the line, but this is what set it up.

• Method 2: if you do make such merges, be careful with them. Edit: this won't actually help: Git is still using the commits that come before commits M1 and M2, and re-merging them. Still, it's worth thinking about a bit. I'll leave some of this text in.

  Merges in general are mostly symmetric. Note that when persons C and D ran their two git merge commands, they had the same commits forming the same graph. They started from the same merge base, with the same two branch-tip commits. The two diffs produced by comparing that merge base to each branch tip were the same diffs.

  So persons C and D had to resolve some conflict, the same one you saw in your own merged-merge-base. They may have done so automatically: For instance, person C might have run git merge -X ours to prefer his tip commit change, for the conflicted file you found, in M1, while person D might have also run git merge -X ours to prefer her tip commit change in M2.

  These asymmetric results were harmless, except for the time bomb itself plus the fact that you later ran a recursive merge. You get to see the conflict. It's up to you to resolve it—again—but this time there's no easy ours/theirs trick, if that worked for persons C and D.

• Method 3 (easy but arguably wrong): use a different merge strategy.

  The recursive merge strategy, -s recursive, is the one that takes this graph, finds all the merge base commit candidates, and if there are more than one, merges them and uses the result as the input for your merge. There is a strategy called resolve (-s resolve) that shares almost all of its code with the recursive strategy. The difference is that when (or after) computing all the merge bases, it takes just one of the multiple bases.

  In this case, with two merge candidates M1 and M2, -s resolve will just pick M1 or M2 apparently-randomly (not actually random, just whichever one pops out first, but not in a well-controlled manner: there's no obvious reason to choose one vs the other). Git will use that one commit as the merge base.

  The problem here is obvious: by using that one commit—person C's, or person D's—you're ignoring the conflict resolution that the other person chose. The two people left you this time bomb, and your answer with -s resolve is let the bomb destroy one of the two results, without me looking to see who was really right, or whether something better should be done instead.

In any case there's no single right answer, which is the same as with any merge conflict. The issue is that you're now resolving a conflict that probably should have been resolved at some point in the past, when these two conflicting merges were made.