From: "Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: Elijah Newren <newren@gmail.com>,
Derrick Stolee <stolee@gmail.com>,
Johannes Schindelin <Johannes.Schindelin@gmx.de>,
Elijah Newren <newren@gmail.com>,
Elijah Newren <newren@gmail.com>
Subject: [PATCH v3 3/3] merge-ort: implement merge_incore_recursive()
Date: Wed, 16 Dec 2020 17:17:14 +0000 [thread overview]
Message-ID: <59216a155ae4f17b959b646e484dfe4a6038751d.1608139034.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.814.v3.git.1608139034.gitgitgadget@gmail.com>
From: Elijah Newren <newren@gmail.com>
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@gmail.com>
---
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@tvgsbejvaqbjf.bet/
+ * [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
next prev parent reply other threads:[~2020-12-16 17:19 UTC|newest]
Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-12-15 17:53 [PATCH 0/3] merge-ort: implement recursive merges Elijah Newren via GitGitGadget
2020-12-15 17:53 ` [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c Elijah Newren via GitGitGadget
2020-12-16 1:16 ` Junio C Hamano
2020-12-16 16:12 ` Johannes Schindelin
2020-12-16 16:24 ` Elijah Newren
2020-12-16 13:30 ` Derrick Stolee
2020-12-16 17:43 ` Junio C Hamano
2020-12-16 18:54 ` Felipe Contreras
2020-12-16 19:20 ` Elijah Newren
2020-12-16 20:41 ` Junio C Hamano
2020-12-16 21:25 ` Felipe Contreras
2020-12-16 21:34 ` Elijah Newren
2020-12-15 17:53 ` [PATCH 2/3] merge-ort: make clear_internal_opts() aware of partial clearing Elijah Newren via GitGitGadget
2020-12-15 17:53 ` [PATCH 3/3] merge-ort: implement merge_incore_recursive() Elijah Newren via GitGitGadget
2020-12-16 2:07 ` Junio C Hamano
2020-12-16 4:09 ` Elijah Newren
2020-12-16 4:44 ` Elijah Newren
2020-12-16 5:52 ` [PATCH v2 0/3] merge-ort: implement recursive merges Elijah Newren via GitGitGadget
2020-12-16 5:52 ` [PATCH v2 1/3] merge-ort: copy a few small helper functions from merge-recursive.c Elijah Newren via GitGitGadget
2020-12-16 5:52 ` [PATCH v2 2/3] merge-ort: make clear_internal_opts() aware of partial clearing Elijah Newren via GitGitGadget
2020-12-16 5:52 ` [PATCH v2 3/3] merge-ort: implement merge_incore_recursive() Elijah Newren via GitGitGadget
2020-12-16 18:09 ` Junio C Hamano
2020-12-16 18:37 ` Elijah Newren
2020-12-16 17:17 ` [PATCH v3 0/3] merge-ort: implement recursive merges Elijah Newren via GitGitGadget
2020-12-16 17:17 ` [PATCH v3 1/3] merge-ort: copy a few small helper functions from merge-recursive.c Elijah Newren via GitGitGadget
2020-12-16 17:17 ` [PATCH v3 2/3] merge-ort: make clear_internal_opts() aware of partial clearing Elijah Newren via GitGitGadget
2020-12-16 17:17 ` Elijah Newren via GitGitGadget [this message]
2020-12-16 20:35 ` [PATCH v4 0/3] merge-ort: implement recursive merges Elijah Newren via GitGitGadget
2020-12-16 20:35 ` [PATCH v4 1/3] merge-ort: copy a few small helper functions from merge-recursive.c Elijah Newren via GitGitGadget
2020-12-16 20:35 ` [PATCH v4 2/3] merge-ort: make clear_internal_opts() aware of partial clearing Elijah Newren via GitGitGadget
2020-12-16 20:35 ` [PATCH v4 3/3] merge-ort: implement merge_incore_recursive() Elijah Newren via GitGitGadget
2020-12-16 22:27 ` [PATCH v5 0/4] merge-ort: implement recursive merges Elijah Newren via GitGitGadget
2020-12-16 22:27 ` [PATCH v5 1/4] commit: move reverse_commit_list() from merge-recursive Elijah Newren via GitGitGadget
2020-12-17 14:03 ` Derrick Stolee
2020-12-16 22:28 ` [PATCH v5 2/4] merge-ort: copy a few small helper functions from merge-recursive.c Elijah Newren via GitGitGadget
2020-12-16 22:28 ` [PATCH v5 3/4] merge-ort: make clear_internal_opts() aware of partial clearing Elijah Newren via GitGitGadget
2020-12-16 22:28 ` [PATCH v5 4/4] merge-ort: implement merge_incore_recursive() Elijah Newren via GitGitGadget
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=59216a155ae4f17b959b646e484dfe4a6038751d.1608139034.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail.com \
--cc=Johannes.Schindelin@gmx.de \
--cc=git@vger.kernel.org \
--cc=newren@gmail.com \
--cc=stolee@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).