CODEWITHSUNDEEP
gitgit-merge
stealegi
stealegi

Reputation: 53

Git merge strategy what is the "resolve" strategy?

One of the merge strategies of git merge is resolve:

This can only resolve two heads (i.e. the current branch and another branch you pulled from) using a 3-way merge algorithm. It tries to carefully detect criss-cross merge ambiguities and is considered generally safe and fast.

This strategy seems to be based on the 3-way merge algorithm as well as the default recursive, but unlike recursive, it is not clear how it handles criss-cross merge situations.

What algorithm does resolve handle criss-cross merges?

Upvotes: 2

Views: 1909

Answers (1)

torek
torek

Reputation: 488253

First, let's note what a "criss-cross merge" is. In Git, a branch name simply identifies the last (or tip) commit that is part of that branch. The remaining commits that are part of the branch are determined by following that commit's parent, its parent's parent (grandparent), the next-step-back parent (the great-grandparent), and so on:

... <-F <-G <-H   <--branch

Here branch name branch identifies a commit whose real hash ID is something big and ugly, but we'll just call it H. That is, Git reads the contents of the name branch:

$ git rev-parse branch
<some big ugly hash ID here>

Git uses that hash ID to read commit H from the repository. Commit H says that its parent commit is another big ugly random-looking hash ID, but we'll just call it G, so Git can use H to find G's hash ID. Git can now read G—H's parent—from the repository. Commit G stores F's hash ID, so that Git can read F, and so on.

When we have two branches with a single best common ancestor, this tends to look like this:

          I--J   <-- branch1
         /
...--G--H
         \
          K--L   <-- branch2

By starting at J and working backwards, Git enumerates commits J, then I, then H, then G, and so on. By starting at L and working backwards, Git enumerates L, then K, then H, then G, and so on.

Commits H and earlier are on both branches. Commit H is the last such commit, so it is the merge base. Both -s resolve and -s recursive will therefore choose commit H as the merge base. (Merging would then make a new commit M whose parents would be both J and L.)

But not all graphs are so nice. In particular, we can have the following series of commits:

...--G--H---K--L   <-- branch1
         \ /
          x
         / \
...--I--J---M--N   <-- branch2

To determine which commit to use as the merge base, Git starts at L and walks back: L, K, H-and-J, G-and-I. That is, Git follows both parents of merge commit K. At the same time, Git starts at N and works backwards: N, M, then H-and-J, and so on.

Clearly H-and-J are better than G-and-I, but there is no easy way to break the tie between H and J as "best" common ancestor. This is where recursive and resolve differ.

The recursive strategy picks both commits as the merge base. To achieve this, it calls an internal, inner git merge on commits H and J. This merge operation finds the merge base of H and J, and merges them to make a temporary commit that sits right where the x is. That new, but temporary, commit is now the merge base for the outer merge.

The resolve strategy is the one you're asking about in your subject line. It picks one of H or J at, apparently, random. Which one you get depends on the algorithm used, which is not specified and may change from one Git release to another.

What algorithm does resolve handle criss-cross merges?

That's the -s recursive strategy, which is the default. As noted above, it handles them by merging the merge bases.

You can run git merge-base --all branch1 branch2 (with the example above) and you'll see the two hash IDs of the two merge bases. In some situations (very hard to draw or, for that matter, to achieve), there could be three or more merge bases. (There is no theoretical upper limit here.) It's also possible for each merge-base pair to have multiple merge bases. The recursive strategy handles all these cases, by repeatedly merging merge bases until it's eventually left with a single best (but temporary) commit.

When recursive merge does a recursive merge, conflicts that occur during the inner merges are quietly committed—complete with conflict markers—into the final merge base used for the merge. The result is very confusing.

Upvotes: 5

Related Questions