When would you use the different git merge strategies?

Question

I'm not familiar with resolve, but I've used the others:

Recursive

Recursive is the default for non-fast-forward merges. We're all familiar with that one.

Octopus

I've used octopus when I've had several trees that needed to be merged. You see this in larger projects where many branches have had independent development and it's all ready to come together into a single head.

An octopus branch merges multiple heads in one commit as long as it can do it cleanly.

For illustration, imagine you have a project that has a master, and then three branches to merge in (call them a, b, and c).

A series of recursive merges would look like this (note that the first merge was a fast-forward, as I didn't force recursion):

However, a single octopus merge would look like this:

commit ae632e99ba0ccd0e9e06d09e8647659220d043b9
Merge: f51262e... c9ce629... aa0f25d...

Ours

Ours == I want to pull in another head, but throw away all of the changes that head introduces.

This keeps the history of a branch without any of the effects of the branch.

(Read: It is not even looked at the changes between those branches. The branches are just merged and nothing is done to the files. If you want to merge in the other branch and every time there is the question "our file version or their version" you can use git merge -X ours)

Subtree

Subtree is useful when you want to merge in another project into a subdirectory of your current project. Useful when you have a library you don't want to include as a submodule.

Actually the only two strategies you would want to choose are ours if you want to abandon changes brought by branch, but keep the branch in history, and subtree if you are merging independent project into subdirectory of superproject (like 'git-gui' in 'git' repository).

octopus merge is used automatically when merging more than two branches. resolve is here mainly for historical reasons, and for when you are hit by recursive merge strategy corner cases.

"Resolve" vs "Recursive" merge strategy

Recursive is the current default two-head strategy, but after some searching I finally found some info about the "resolve" merge strategy.

Taken from O'Reilly book Version Control with Git (Amazon) (paraphrased):

Originally, "resolve" was the default strategy for Git merges.

In criss-cross merge situations, where there is more than one possible merge basis, the resolve strategy works like this: pick one of the possible merge bases, and hope for the best. This is actually not as bad as it sounds. It often turns out that the users have been working on different parts of the code. In that case, Git detects that it's remerging some changes that are already in place and skips the duplicate changes, avoiding the conflict. Or, if these are slight changes that do cause conflict, at least the conflict should be easy for the developer to handle..

I have successfully merged trees using "resolve" that failed with the default recursive strategy. I was getting fatal: git write-tree failed to write a tree errors, and thanks to this blog post (mirror) I tried "-s resolve", which worked. I'm still not exactly sure why... but I think it was because I had duplicate changes in both trees, and resolve "skipped" them properly.

With Git 2.30 (Q1 2021), there will be a new merge strategy: ORT ("Ostensibly Recursive's Twin").

git merge -s ort

This comes from this thread from Elijah Newren:

For now, I'm calling it "Ostensibly Recursive's Twin", or "ort" for short. > At first, people shouldn't be able to notice any difference between it and the current recursive strategy, other than the fact that I think I can make it a bit faster (especially for big repos).

But it should allow me to fix some (admittedly corner case) bugs that are harder to handle in the current design, and I think that a merge that doesn't touch $GIT_WORK_TREE or $GIT_INDEX_FILE will allow for some fun new features.
That's the hope anyway.

Problem:

In the ideal world, we should:

• ask unpack_trees() to do "read-tree -m" without "-u";

• do all the merge-recursive computations in-core and prepare the resulting index, while keeping the current index intact;

• compare the current in-core index and the resulting in-core index, and notice the paths that need to be added, updated or removed in the working tree, and ensure that there is no loss of information when the change is reflected to the working tree;
  E.g. the result wants to create a file where the working tree currently has a directory with non-expendable contents in it, the result wants to remove a file where the working tree file has local modification, etc.;
  And then finally

• carry out the working tree update to make it match what the resulting in-core index says it should look like.

Result:

See commit 14c4586 (02 Nov 2020), commit fe1a21d (29 Oct 2020), and commit 47b1e89, commit 17e5574 (27 Oct 2020) by Elijah Newren (newren).
^{(Merged by Junio C Hamano -- gitster -- in commit a1f9595, 18 Nov 2020)}

merge-ort: barebones API of new merge strategy with empty implementation

^{Signed-off-by: Elijah Newren}

This is the beginning of a new merge strategy.

While there are some API differences, and the implementation has some differences in behavior, it is essentially meant as an eventual drop-in replacement for merge-recursive.c.

However, it is being built to exist side-by-side with merge-recursive so that we have plenty of time to find out how those differences pan out in the real world while people can still fall back to merge-recursive.
(Also, I intend to avoid modifying merge-recursive during this process, to keep it stable.)

The primary difference noticable here is that the updating of the working tree and index is not done simultaneously with the merge algorithm, but is a separate post-processing step.
The new API is designed so that one can do repeated merges (e.g. during a rebase or cherry-pick) and only update the index and working tree one time at the end instead of updating it with every intermediate result.

Also, one can perform a merge between two branches, neither of which match the index or the working tree, without clobbering the index or working tree.

And:

See commit 848a856, commit fd15863, commit 23bef2e, commit c8c35f6, commit c12d1f2, commit 727c75b, commit 489c85f, commit ef52778, commit f06481f (26 Oct 2020) by Elijah Newren (newren).
^{(Merged by Junio C Hamano -- gitster -- in commit 66c62ea, 18 Nov 2020)}

t6423, t6436: note improved ort handling with dirty files

^{Signed-off-by: Elijah Newren}

The "recursive" backend relies on unpack_trees() to check if unstaged changes would be overwritten by a merge, but unpack_trees() does not understand renames -- and once it returns, it has already written many updates to the working tree and index.
As such, "recursive" had to do a special 4-way merge where it would need to also treat the working copy as an extra source of differences that we had to carefully avoid overwriting and resulting in moving files to new locations to avoid conflicts.

The "ort" backend, by contrast, does the complete merge inmemory, and only updates the index and working copy as a post-processing step.
If there are dirty files in the way, it can simply abort the merge.

t6423: expect improved conflict markers labels in the ort backend

^{Signed-off-by: Elijah Newren}

Conflict markers carry an extra annotation of the form REF-OR-COMMIT:FILENAME to help distinguish where the content is coming from, with the :FILENAME piece being left off if it is the same for both sides of history (thus only renames with content conflicts carry that part of the annotation).

However, there were cases where the :FILENAME annotation was accidentally left off, due to merge-recursive's every-codepath-needs-a-copy-of-all-special-case-code format.

t6404, t6423: expect improved rename/delete handling in ort backend

^{Signed-off-by: Elijah Newren}

When a file is renamed and has content conflicts, merge-recursive does not have some stages for the old filename and some stages for the new filename in the index; instead it copies all the stages corresponding to the old filename over to the corresponding locations for the new filename, so that there are three higher order stages all corresponding to the new filename.

Doing things this way makes it easier for the user to access the different versions and to resolve the conflict (no need to manually 'git rm '^(man) the old version as well as 'git add'^(man) the new one).

rename/deletes should be handled similarly -- there should be two stages for the renamed file rather than just one.
We do not want to destabilize merge-recursive right now, so instead update relevant tests to have different expectations depending on whether the "recursive" or "ort" merge strategies are in use.

---

With Git 2.30 (Q1 2021), Preparation for a new merge strategy.

See commit 848a856, commit fd15863, commit 23bef2e, commit c8c35f6, commit c12d1f2, commit 727c75b, commit 489c85f, commit ef52778, commit f06481f (26 Oct 2020) by Elijah Newren (newren).
^{(Merged by Junio C Hamano -- gitster -- in commit 66c62ea, 18 Nov 2020)}

merge tests: expect improved directory/file conflict handling in ort

^{Signed-off-by: Elijah Newren}

merge-recursive.c is built on the idea of running unpack_trees() and then "doing minor touch-ups" to get the result.
Unfortunately, unpack_trees() was run in an update-as-it-goes mode, leading merge-recursive.c to follow suit and end up with an immediate evaluation and fix-it-up-as-you-go design.

Some things like directory/file conflicts are not well representable in the index data structure, and required special extra code to handle.
But then when it was discovered that rename/delete conflicts could also be involved in directory/file conflicts, the special directory/file conflict handling code had to be copied to the rename/delete codepath.
...and then it had to be copied for modify/delete, and for rename/rename(1to2) conflicts, ...and yet it still missed some.
Further, when it was discovered that there were also file/submodule conflicts and submodule/directory conflicts, we needed to copy the special submodule handling code to all the special cases throughout the codebase.

And then it was discovered that our handling of directory/file conflicts was suboptimal because it would create untracked files to store the contents of the conflicting file, which would not be cleaned up if someone were to run a 'git merge --abort'^(man) or 'git rebase --abort'^(man).

It was also difficult or scary to try to add or remove the index entries corresponding to these files given the directory/file conflict in the index.
But changing merge-recursive.c to handle these correctly was a royal pain because there were so many sites in the code with similar but not identical code for handling directory/file/submodule conflicts that would all need to be updated.

I have worked hard to push all directory/file/submodule conflict handling in merge-ort through a single codepath, and avoid creating untracked files for storing tracked content (it does record things at alternate paths, but makes sure they have higher-order stages in the index).

---

With Git 2.31 (Q1 2021), the merge backend "done right" starts to emerge.
Example:

See commit 6d37ca2 (11 Nov 2020) by Junio C Hamano (gitster).
See commit 89422d2, commit ef2b369, commit 70912f6, commit 6681ce5, commit 9fefce6, commit bb470f4, commit ee4012d, commit a9945bb, commit 8adffaa, commit 6a02dd9, commit 291f29c, commit 98bf984, commit 34e557a, commit 885f006, commit d2bc199, commit 0c0d705, commit c801717, commit e4171b1, commit 231e2dd, commit 5b59c3d (13 Dec 2020) by Elijah Newren (newren).
^{(Merged by Junio C Hamano -- gitster -- in commit f9d29da, 06 Jan 2021)}

merge-ort: add implementation of record_conflicted_index_entries()

^{Signed-off-by: Elijah Newren}

After checkout(), the working tree has the appropriate contents, and the index matches the working copy.
That means that all unmodified and cleanly merged files have correct index entries, but conflicted entries need to be updated.

We do this by looping over the conflicted entries, marking the existing index entry for the path with CE_REMOVE, adding new higher order staged for the path at the end of the index (ignoring normal index sort order), and then at the end of the loop removing the CE_REMOVED-marked cache entries and sorting the index.

---

With Git 2.31 (Q1 2021), rename detection is added to the "ORT" merge strategy.

See commit 6fcccbd, commit f1665e6, commit 35e47e3, commit 2e91ddd, commit 53e88a0, commit af1e56c (15 Dec 2020), and commit c2d267d, commit 965a7bc, commit f39d05c, commit e1a124e, commit 864075e (14 Dec 2020) by Elijah Newren (newren).
^{(Merged by Junio C Hamano -- gitster -- in commit 2856089, 25 Jan 2021)}

Example:

merge-ort: add implementation of normal rename handling

^{Signed-off-by: Elijah Newren}

Implement handling of normal renames.
This code replaces the following from merge-recurisve.c:

• the code relevant to RENAME_NORMAL in process_renames()
• the RENAME_NORMAL case of process_entry()

Also, there is some shared code from merge-recursive.c for multiple different rename cases which we will no longer need for this case (or other rename cases):

• handle_rename_normal()
• setup_rename_conflict_info()

The consolidation of four separate codepaths into one is made possible by a change in design: process_renames() tweaks the conflict_info entries within opt->priv->paths such that process_entry() can then handle all the non-rename conflict types (directory/file, modify/delete, etc.) orthogonally.

This means we're much less likely to miss special implementation of some kind of combination of conflict types (see commits brought in by 66c62ea ("Merge branch 'en/merge-tests'", 2020-11-18, Git v2.30.0-rc0 -- merge listed in batch #6), especially commit ef52778 ("merge tests: expect improved directory/file conflict handling in ort", 2020-10-26, Git v2.30.0-rc0 -- merge listed in batch #6) for more details).

That, together with letting worktree/index updating be handled orthogonally in the merge_switch_to_result() function, dramatically simplifies the code for various special rename cases.

(To be fair, the code for handling normal renames wasn't all that complicated beforehand, but it's still much simpler now.)

And, still with Git 2.31 (Q1 2021), With Git 2.31 (Q1 2021), oRT merge strategy learns more support for merge conflicts.

See commit 4ef88fc, commit 4204cd5, commit 70f19c7, commit c73cda7, commit f591c47, commit 62fdec1, commit 991bbdc, commit 5a1a1e8, commit 23366d2, commit 0ccfa4e (01 Jan 2021) by Elijah Newren (newren).
^{(Merged by Junio C Hamano -- gitster -- in commit b65b9ff, 05 Feb 2021)}

merge-ort: add handling for different types of files at same path

^{Signed-off-by: Elijah Newren}

Add some handling that explicitly considers collisions of the following types:

• file/submodule
• file/symlink
• submodule/symlink> Leaving them as conflicts at the same path are hard for users to resolve, so move one or both of them aside so that they each get their own path.

Note that in the case of recursive handling (i.e.
call_depth > 0), we can just use the merge base of the two merge bases as the merge result much like we do with modify/delete conflicts, binary files, conflicting submodule values, and so on.