From: Elijah Newren <newren@xxxxxxxxx>
Implement merge_incore_recursive(), mostly through the use of a new
helper function, merge_ort_internal(), which itself is based off
merge_recursive_internal() from merge-recursive.c.
This drops the number of failures in the testsuite when run under
GIT_TEST_MERGE_ALGORITHM=ort from around 1500 to 647.
Signed-off-by: Elijah Newren <newren@xxxxxxxxx>
---
merge-ort.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++--
merge-ort.h | 10 +++++
2 files changed, 115 insertions(+), 3 deletions(-)
diff --git a/merge-ort.c b/merge-ort.c
index 7679c1d08e2..f01307f2ee0 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -1356,7 +1356,6 @@ static inline void set_commit_tree(struct commit *c, struct tree *t)
c->maybe_tree = t;
}
-MAYBE_UNUSED
static struct commit *make_virtual_commit(struct repository *repo,
struct tree *tree,
const char *comment)
@@ -1369,7 +1368,6 @@ static struct commit *make_virtual_commit(struct repository *repo,
return commit;
}
-MAYBE_UNUSED
static struct commit_list *reverse_commit_list(struct commit_list *list)
{
struct commit_list *previous = NULL, *current, *backup;
@@ -1478,6 +1476,91 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,
}
}
+/*
+ * Originally from merge_recursive_internal(); somewhat adapted, though.
+ */
+static void merge_ort_internal(struct merge_options *opt,
+ struct commit_list *merge_bases,
+ struct commit *h1,
+ struct commit *h2,
+ struct merge_result *result)
+{
+ struct commit_list *iter;
+ struct commit *merged_merge_bases;
+ const char *ancestor_name;
+ struct strbuf merge_base_abbrev = STRBUF_INIT;
+
+ if (!merge_bases) {
+ merge_bases = get_merge_bases(h1, h2);
+ /* See merge-ort.h:merge_incore_recursive() declaration NOTE */
+ merge_bases = reverse_commit_list(merge_bases);
+ }
+
+ merged_merge_bases = pop_commit(&merge_bases);
+ if (merged_merge_bases == NULL) {
+ /* if there is no common ancestor, use an empty tree */
+ struct tree *tree;
+
+ tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);
+ merged_merge_bases = make_virtual_commit(opt->repo, tree,
+ "ancestor");
+ ancestor_name = "empty tree";
+ } else if (opt->ancestor && !opt->priv->call_depth) {
+ ancestor_name = opt->ancestor;
+ } else if (merge_bases) {
+ ancestor_name = "merged common ancestors";
+ } else {
+ strbuf_add_unique_abbrev(&merge_base_abbrev,
+ &merged_merge_bases->object.oid,
+ DEFAULT_ABBREV);
+ ancestor_name = merge_base_abbrev.buf;
+ }
+
+ for (iter = merge_bases; iter; iter = iter->next) {
+ const char *saved_b1, *saved_b2;
+ struct commit *prev = merged_merge_bases;
+
+ opt->priv->call_depth++;
+ /*
+ * When the merge fails, the result contains files
+ * with conflict markers. The cleanness flag is
+ * ignored (unless indicating an error), it was never
+ * actually used, as result of merge_trees has always
+ * overwritten it: the committed "conflicts" were
+ * already resolved.
+ */
+ saved_b1 = opt->branch1;
+ saved_b2 = opt->branch2;
+ opt->branch1 = "Temporary merge branch 1";
+ opt->branch2 = "Temporary merge branch 2";
+ merge_ort_internal(opt, NULL, prev, iter->item, result);
+ if (result->clean < 0)
+ return;
+ opt->branch1 = saved_b1;
+ opt->branch2 = saved_b2;
+ opt->priv->call_depth--;
+
+ merged_merge_bases = make_virtual_commit(opt->repo,
+ result->tree,
+ "merged tree");
+ commit_list_insert(prev, &merged_merge_bases->parents);
+ commit_list_insert(iter->item,
+ &merged_merge_bases->parents->next);
+
+ clear_or_reinit_internal_opts(opt->priv, 1);
+ }
+
+ opt->ancestor = ancestor_name;
+ merge_ort_nonrecursive_internal(opt,
+ repo_get_commit_tree(opt->repo,
+ merged_merge_bases),
+ repo_get_commit_tree(opt->repo, h1),
+ repo_get_commit_tree(opt->repo, h2),
+ result);
+ strbuf_release(&merge_base_abbrev);
+ opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */
+}
+
void merge_incore_nonrecursive(struct merge_options *opt,
struct tree *merge_base,
struct tree *side1,
@@ -1495,5 +1578,24 @@ void merge_incore_recursive(struct merge_options *opt,
struct commit *side2,
struct merge_result *result)
{
- die("Not yet implemented");
+ /*
+ * merge_incore_nonrecursive() exists for cases where we always
+ * know there is a well-defined single merge base. However,
+ * despite a similar structure, merge-recursive.c noted that some
+ * callers preferred to call the recursive logic anyway and still
+ * set a special name for opt->ancestor that would appear in
+ * merge.conflictStyle=diff3 output.
+ *
+ * git-am was one such example (it wanted to set opt->ancestor to
+ * "constructed merge base", since it created a fake merge base);
+ * it called the recursive merge logic through a special
+ * merge_recursive_generic() wrapper.
+ *
+ * Allow the same kind of special case here.
+ */
+ int num_merge_bases_is_1 = (merge_bases && !merge_bases->next);
+ assert(opt->ancestor == NULL || num_merge_bases_is_1);
+
+ merge_start(opt, result);
+ merge_ort_internal(opt, merge_bases, side1, side2, result);
}
diff --git a/merge-ort.h b/merge-ort.h
index 55ae7ee865d..d53a0a339f3 100644
--- a/merge-ort.h
+++ b/merge-ort.h
@@ -34,6 +34,16 @@ struct merge_result {
/*
* rename-detecting three-way merge with recursive ancestor consolidation.
* working tree and index are untouched.
+ *
+ * merge_bases will be consumed (emptied) so make a copy if you need it.
+ *
+ * NOTE: empirically, the recursive algorithm will perform better if you
+ * pass the merge_bases in the order of oldest commit to the
+ * newest[1][2].
+ *
+ * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@xxxxxxxxxxxxxxxxx/
+ * [2] commit 8918b0c9c2 ("merge-recur: try to merge older merge bases
+ * first", 2006-08-09)
*/
void merge_incore_recursive(struct merge_options *opt,
struct commit_list *merge_bases,
--
gitgitgadget
