merge: reverse merge bases for recursive merge

When the commits being merged have multiple merge bases, reverse the
order when creating the virtual merge base.  This is for compatibility
with git's merge-recursive algorithm, and ensures that we build
identical trees.

Git does this to try to use older merge bases first.  Per 8918b0c:

> It seems to be the only sane way to do it: when a two-head merge is
> done, and the merge-base and one of the two branches agree, the
> merge assumes that the other branch has something new.
>
> If we start creating virtual commits from newer merge-bases, and go
> back to older merge-bases, and then merge with newer commits again,
> chances are that a patch is lost, _because_ the merge-base and the
> head agree on it. Unlikely, yes, but it happened to me.

4 files changed, 32 insertions, 28 deletions

diff --git a/src/merge.c b/src/merge.c
index aae5d764a..37c83eccd 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -2263,7 +2263,7 @@ static int compute_base(
 	git_oidarray bases = {0};
 	git_annotated_commit *base = NULL, *other = NULL, *new_base = NULL;
 	git_merge_options opts = GIT_MERGE_OPTIONS_INIT;
-	size_t i;
+	size_t i, base_count;
 	int error;
 
 	*out = NULL;
@@ -2272,16 +2272,20 @@ static int compute_base(
 		memcpy(&opts, given_opts, sizeof(git_merge_options));
 
 	if ((error = insert_head_ids(&head_ids, one)) < 0 ||
-		(error = insert_head_ids(&head_ids, two)) < 0)
+		(error = insert_head_ids(&head_ids, two)) < 0 ||
+		(error = git_merge_bases_many(&bases, repo,
+			head_ids.size, head_ids.ptr)) < 0)
 		goto done;
 
-	if ((error = git_merge_bases_many(&bases, repo,
-			head_ids.size, head_ids.ptr)) < 0 ||
-		(error = git_annotated_commit_lookup(&base, repo, &bases.ids[0])) < 0 ||
-		(opts.flags & GIT_MERGE_NO_RECURSIVE))
+	base_count = (opts.flags & GIT_MERGE_NO_RECURSIVE) ? 0 : bases.count;
+
+	if (base_count)
+		git_oidarray__reverse(&bases);
+
+	if ((error = git_annotated_commit_lookup(&base, repo, &bases.ids[0])) < 0)
 		goto done;
 
-	for (i = 1; i < bases.count; i++) {
+	for (i = 1; i < base_count; i++) {
 		recursion_level++;
 
 		if (opts.recursion_limit && recursion_level > opts.recursion_limit)
diff --git a/tests/merge/conflict_data.h b/tests/merge/conflict_data.h
index 7d404c81f..27f19c1b0 100644
--- a/tests/merge/conflict_data.h
+++ b/tests/merge/conflict_data.h
@@ -70,22 +70,22 @@
 	"This is a mighty fine recipe!\n" \
 	">>>>>>> branchF-2\n"
 
-#define CONFLICTING_RECURSIVE_H1_TO_H2_WITH_DIFF3 \
+#define CONFLICTING_RECURSIVE_H2_TO_H1_WITH_DIFF3 \
 	"VEAL SOUP.\n" \
 	"\n" \
 	"<<<<<<< HEAD\n" \
-	"put into a pot three quarts of water, three onions cut small, one\n" \
+	"Put Into A Pot Three Quarts of Water, Three Onions Cut Small, One\n" \
 	"||||||| merged common ancestors\n" \
 	"<<<<<<<<< Temporary merge branch 1\n" \
-	"Put into a pot three quarts of water, THREE ONIONS CUT SMALL, one\n" \
+	"PUT INTO A POT three quarts of water, three onions cut small, one\n" \
 	"||||||||| merged common ancestors\n" \
 	"Put into a pot three quarts of water, three onions cut small, one\n" \
 	"=========\n" \
-	"PUT INTO A POT three quarts of water, three onions cut small, one\n" \
+	"Put into a pot three quarts of water, THREE ONIONS CUT SMALL, one\n" \
 	">>>>>>>>> Temporary merge branch 2\n" \
 	"=======\n" \
-	"Put Into A Pot Three Quarts of Water, Three Onions Cut Small, One\n" \
-	">>>>>>> branchH-2\n" \
+	"put into a pot three quarts of water, three onions cut small, one\n" \
+	">>>>>>> branchH-1\n" \
 	"spoonful of black pepper pounded, and two of salt, with two or three\n" \
 	"slices of lean ham; let it boil steadily two hours; skim it\n" \
 	"occasionally, then put into it a shin of veal, let it boil two hours\n" \
diff --git a/tests/merge/trees/recursive.c b/tests/merge/trees/recursive.c
index 1d54d87b1..5ff0bfaf8 100644
--- a/tests/merge/trees/recursive.c
+++ b/tests/merge/trees/recursive.c
@@ -312,7 +312,7 @@ void test_merge_trees_recursive__conflicting_merge_base(void)
 		{ 0100644, "4b7c5650008b2e747fe1809eeb5a1dde0e80850a", 0, "bouilli.txt" },
 		{ 0100644, "c4e6cca3ec6ae0148ed231f97257df8c311e015f", 0, "gravy.txt" },
 		{ 0100644, "68af1fc7407fd9addf1701a87eb1c95c7494c598", 0, "oyster.txt" },
-		{ 0100644, "ba5714aa3d5aebfd8e19d19cb1ddcfda63426a44", 1, "veal.txt" },
+		{ 0100644, "cfc01b0976122eae42a82064440bbf534eddd7a0", 1, "veal.txt" },
 		{ 0100644, "d604c75019c282144bdbbf3fd3462ba74b240efc", 2, "veal.txt" },
 		{ 0100644, "37a5054a9f9b4628e3924c5cb8f2147c6e2a3efc", 3, "veal.txt" },
 	};
@@ -339,14 +339,14 @@ void test_merge_trees_recursive__conflicting_merge_base_with_diff3(void)
 		{ 0100644, "4b7c5650008b2e747fe1809eeb5a1dde0e80850a", 0, "bouilli.txt" },
 		{ 0100644, "c4e6cca3ec6ae0148ed231f97257df8c311e015f", 0, "gravy.txt" },
 		{ 0100644, "68af1fc7407fd9addf1701a87eb1c95c7494c598", 0, "oyster.txt" },
-		{ 0100644, "adb1bf17d112a0b4ecbd4e75bef6db3335d8ddcf", 1, "veal.txt" },
-		{ 0100644, "d604c75019c282144bdbbf3fd3462ba74b240efc", 2, "veal.txt" },
-		{ 0100644, "37a5054a9f9b4628e3924c5cb8f2147c6e2a3efc", 3, "veal.txt" },
+		{ 0100644, "0b01d2f70a1c6b9ab60c382f3f9cdc8173da6736", 1, "veal.txt" },
+		{ 0100644, "37a5054a9f9b4628e3924c5cb8f2147c6e2a3efc", 2, "veal.txt" },
+		{ 0100644, "d604c75019c282144bdbbf3fd3462ba74b240efc", 3, "veal.txt" },
 	};
 
 	opts.file_flags |= GIT_MERGE_FILE_STYLE_DIFF3;
 
-	cl_git_pass(merge_commits_from_branches(&index, repo, "branchH-1", "branchH-2", &opts));
+	cl_git_pass(merge_commits_from_branches(&index, repo, "branchH-2", "branchH-1", &opts));
 
 	cl_assert(merge_test_index(index, merge_index_entries, 8));
 
@@ -392,16 +392,16 @@ void test_merge_trees_recursive__recursionlimit(void)
 		{ 0100644, "ffb36e513f5fdf8a6ba850a20142676a2ac4807d", 0, "asparagus.txt" },
 		{ 0100644, "68f6182f4c85d39e1309d97c7e456156dc9c0096", 0, "beef.txt" },
 		{ 0100644, "4b7c5650008b2e747fe1809eeb5a1dde0e80850a", 0, "bouilli.txt" },
-		{ 0100644, "ce7e553c6feb6e5f3bd67e3c3be04182fe3094b4", 1, "gravy.txt" },
-		{ 0100644, "d8dd349b78f19a4ebe3357bacb8138f00bf5ed41", 2, "gravy.txt" },
-		{ 0100644, "e50fbbd701458757bdfe9815f58ed717c588d1b5", 3, "gravy.txt" },
+		{ 0100644, "c4e6cca3ec6ae0148ed231f97257df8c311e015f", 0, "gravy.txt" },
 		{ 0100644, "68af1fc7407fd9addf1701a87eb1c95c7494c598", 0, "oyster.txt" },
-		{ 0100644, "a7b066537e6be7109abfe4ff97b675d4e077da20", 0, "veal.txt" },
+		{ 0100644, "53217e8ac3f52bccf7603b8fff0ed0f4817f9bb7", 1, "veal.txt" },
+		{ 0100644, "898d12687fb35be271c27c795a6b32c8b51da79e", 2, "veal.txt" },
+		{ 0100644, "68a2e1ee61a23a4728fe6b35580fbbbf729df370", 3, "veal.txt" },
 	};
 
 	opts.recursion_limit = 1;
 
-	cl_git_pass(merge_commits_from_branches(&index, repo, "branchE-1", "branchE-2", &opts));
+	cl_git_pass(merge_commits_from_branches(&index, repo, "branchC-1", "branchC-2", &opts));
 
 	cl_assert(merge_test_index(index, merge_index_entries, 8));
 
diff --git a/tests/merge/workdir/recursive.c b/tests/merge/workdir/recursive.c
index 3c745947c..d47a0c50b 100644
--- a/tests/merge/workdir/recursive.c
+++ b/tests/merge/workdir/recursive.c
@@ -62,22 +62,22 @@ void test_merge_workdir_recursive__conflicting_merge_base_with_diff3(void)
 		{ 0100644, "4b7c5650008b2e747fe1809eeb5a1dde0e80850a", 0, "bouilli.txt" },
 		{ 0100644, "c4e6cca3ec6ae0148ed231f97257df8c311e015f", 0, "gravy.txt" },
 		{ 0100644, "68af1fc7407fd9addf1701a87eb1c95c7494c598", 0, "oyster.txt" },
-		{ 0100644, "adb1bf17d112a0b4ecbd4e75bef6db3335d8ddcf", 1, "veal.txt" },
-		{ 0100644, "d604c75019c282144bdbbf3fd3462ba74b240efc", 2, "veal.txt" },
-		{ 0100644, "37a5054a9f9b4628e3924c5cb8f2147c6e2a3efc", 3, "veal.txt" },
+		{ 0100644, "0b01d2f70a1c6b9ab60c382f3f9cdc8173da6736", 1, "veal.txt" },
+		{ 0100644, "37a5054a9f9b4628e3924c5cb8f2147c6e2a3efc", 2, "veal.txt" },
+		{ 0100644, "d604c75019c282144bdbbf3fd3462ba74b240efc", 3, "veal.txt" },
 	};
 
 	opts.file_flags |= GIT_MERGE_FILE_STYLE_DIFF3;
 	checkout_opts.checkout_strategy |= GIT_CHECKOUT_CONFLICT_STYLE_DIFF3;
 
-	cl_git_pass(merge_branches(repo, GIT_REFS_HEADS_DIR "branchH-1", GIT_REFS_HEADS_DIR "branchH-2", &opts, &checkout_opts));
+	cl_git_pass(merge_branches(repo, GIT_REFS_HEADS_DIR "branchH-2", GIT_REFS_HEADS_DIR "branchH-1", &opts, &checkout_opts));
 
 	cl_git_pass(git_repository_index(&index, repo));
 	cl_assert(merge_test_index(index, merge_index_entries, 8));
 
 	cl_git_pass(git_futils_readbuffer(&conflicting_buf, "merge-recursive/veal.txt"));
 
-	cl_assert_equal_s(CONFLICTING_RECURSIVE_H1_TO_H2_WITH_DIFF3, conflicting_buf.ptr);
+	cl_assert_equal_s(CONFLICTING_RECURSIVE_H2_TO_H1_WITH_DIFF3, conflicting_buf.ptr);
 
 	git_index_free(index);
 	git_buf_free(&conflicting_buf);