{"thread":{"id":"54831","subject":"[PATCH 3/3] merge-ort: implement merge_incore_recursive()","startedAt":"2020-12-15T17:54:48Z","lastAt":"2020-12-17T14:04:38Z","messageCount":37,"participants":["Elijah Newren via GitGitGadget","Junio C Hamano","Elijah Newren","Derrick Stolee","Johannes Schindelin","Felipe Contreras"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"412272","messageId":"82a773d8972b6641a25b3c84121dd38703a9286c.1608054807.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.git.1608054807.gitgitgadget@gmail.com","subject":"[PATCH 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-15T17:53:27Z","receivedAt":"2020-12-15T17:54:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nImplement merge_incore_recursive(), mostly through the use of a new\nhelper function, merge_ort_internal(), which itself is based off\nmerge_recursive_internal() from merge-recursive.c.\n\nThis drops the number of failures in the testsuite when run under\nGIT_TEST_MERGE_ALGORITHM=ort from around 1500 to 647.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 89 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 10a97e944c4..65f7ce2b223 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1476,6 +1476,90 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n \n+/*\n+ * Originally from merge_recursive_internal(); somewhat adapted, though.\n+ */\n+static void merge_ort_internal(struct merge_options *opt,\n+\t\t\t struct commit_list *merge_bases,\n+\t\t\t struct commit *h1,\n+\t\t\t struct commit *h2,\n+\t\t\t struct merge_result *result)\n+{\n+\tstruct commit_list *iter;\n+\tstruct commit *merged_merge_bases;\n+\tconst char *ancestor_name;\n+\tstruct strbuf merge_base_abbrev = STRBUF_INIT;\n+\n+\tif (!merge_bases) {\n+\t\tmerge_bases = get_merge_bases(h1, h2);\n+\t\tmerge_bases = reverse_commit_list(merge_bases);\n+\t}\n+\n+\tmerged_merge_bases = pop_commit(&merge_bases);\n+\tif (merged_merge_bases == NULL) {\n+\t\t/* if there is no common ancestor, use an empty tree */\n+\t\tstruct tree *tree;\n+\n+\t\ttree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n+\t\t\t\t\t\t\t \"ancestor\");\n+\t\tancestor_name = \"empty tree\";\n+\t} else if (opt->ancestor && !opt->priv->call_depth) {\n+\t\tancestor_name = opt->ancestor;\n+\t} else if (merge_bases) {\n+\t\tancestor_name = \"merged common ancestors\";\n+\t} else {\n+\t\tstrbuf_add_unique_abbrev(&merge_base_abbrev,\n+\t\t\t\t\t &merged_merge_bases->object.oid,\n+\t\t\t\t\t DEFAULT_ABBREV);\n+\t\tancestor_name = merge_base_abbrev.buf;\n+\t}\n+\n+\tfor (iter = merge_bases; iter; iter = iter->next) {\n+\t\tconst char *saved_b1, *saved_b2;\n+\t\tstruct commit *prev = merged_merge_bases;\n+\n+\t\topt->priv->call_depth++;\n+\t\t/*\n+\t\t * When the merge fails, the result contains files\n+\t\t * with conflict markers. The cleanness flag is\n+\t\t * ignored (unless indicating an error), it was never\n+\t\t * actually used, as result of merge_trees has always\n+\t\t * overwritten it: the committed \"conflicts\" were\n+\t\t * already resolved.\n+\t\t */\n+\t\tsaved_b1 = opt->branch1;\n+\t\tsaved_b2 = opt->branch2;\n+\t\topt->branch1 = \"Temporary merge branch 1\";\n+\t\topt->branch2 = \"Temporary merge branch 2\";\n+\t\tmerge_ort_internal(opt, NULL, prev, iter->item, result);\n+\t\tif (result->clean < 0)\n+\t\t\treturn;\n+\t\topt->branch1 = saved_b1;\n+\t\topt->branch2 = saved_b2;\n+\t\topt->priv->call_depth--;\n+\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo,\n+\t\t\t\t\t\t\t result->tree,\n+\t\t\t\t\t\t\t \"merged tree\");\n+\t\tcommit_list_insert(prev, &merged_merge_bases->parents);\n+\t\tcommit_list_insert(iter->item,\n+\t\t\t\t &merged_merge_bases->parents->next);\n+\n+\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n+\t}\n+\n+\topt->ancestor = ancestor_name;\n+\tmerge_ort_nonrecursive_internal(opt,\n+\t\t\t\t\trepo_get_commit_tree(opt->repo,\n+\t\t\t\t\t\t\t merged_merge_bases),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h1),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h2),\n+\t\t\t\t\tresult);\n+\tstrbuf_release(&merge_base_abbrev);\n+\topt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n+}\n+\n void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n@@ -1493,7 +1577,9 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n-\t(void)reverse_commit_list;\n-\t(void)make_virtual_commit;\n-\tdie(\"Not yet implemented\");\n+\tassert(opt->ancestor == NULL ||\n+\t !strcmp(opt->ancestor, \"constructed merge base\"));\n+\n+\tmerge_start(opt, result);\n+\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n }\n-- \ngitgitgadget\n"},{"id":"412273","messageId":"fc26c1a11db76843b0a439d2c69567fcd7ad9ac2.1608054807.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.git.1608054807.gitgitgadget@gmail.com","subject":"[PATCH 2/3] merge-ort: make clear_internal_opts() aware of partial clearing","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-15T17:53:26Z","receivedAt":"2020-12-15T17:54:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to handle recursive merges, after merging merge-bases we need\nto clear away most of the data we had built up but some of it needs to\nbe kept -- in particular the \"output\" field. Rename the function to\nreflect its future change in use.\n\nFurther, since \"reinitialize\" means we'll be reusing the fields\nimmediately, take advantage of this to only partially clear maps,\nleaving the hashtable allocated and pre-sized. (This may be slightly\nout-of-order since the speedups aren't realized until there are far\nmore strmaps in use, but the patch submission process already went out\nof order because of various questions and requests for strmap. Anyway,\nsee commit 6ccdfc2a20 (\"strmap: enable faster clearing and reusing of\nstrmaps\", 2020-11-05), for performance details about the use of\nstrmap_partial_clear().)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 05ba92c91a6..10a97e944c4 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -253,10 +253,11 @@ static void free_strmap_strings(struct strmap *map)\n \t}\n }\n \n-static void clear_internal_opts(struct merge_options_internal *opti,\n-\t\t\t\tint reinitialize)\n+static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n+\t\t\t\t\t int reinitialize)\n {\n-\tassert(!reinitialize);\n+\tvoid (*strmap_func)(struct strmap *, int) =\n+\t\treinitialize ? strmap_partial_clear : strmap_clear;\n \n \t/*\n \t * We marked opti->paths with strdup_strings = 0, so that we\n@@ -266,14 +267,14 @@ static void clear_internal_opts(struct merge_options_internal *opti,\n \t * to deallocate them.\n \t */\n \tfree_strmap_strings(&opti->paths);\n-\tstrmap_clear(&opti->paths, 1);\n+\tstrmap_func(&opti->paths, 1);\n \n \t/*\n \t * All keys and values in opti->conflicted are a subset of those in\n \t * opti->paths. We don't want to deallocate anything twice, so we\n \t * don't free the keys and we pass 0 for free_values.\n \t */\n-\tstrmap_clear(&opti->conflicted, 0);\n+\tstrmap_func(&opti->conflicted, 0);\n \n \t/*\n \t * opti->paths_to_free is similar to opti->paths; we created it with\n@@ -1344,7 +1345,7 @@ void merge_finalize(struct merge_options *opt,\n \n \tassert(opt->priv == NULL);\n \n-\tclear_internal_opts(opti, 0);\n+\tclear_or_reinit_internal_opts(opti, 0);\n \tFREE_AND_NULL(opti);\n }\n \n-- \ngitgitgadget\n\n"},{"id":"412274","messageId":"0b455bd6fe7dff72c1849eb8466b97b96b2b90a9.1608054807.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.git.1608054807.gitgitgadget@gmail.com","subject":"[PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-15T17:53:25Z","receivedAt":"2020-12-15T17:54:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn a subsequent commit, we will implement the traditional recursiveness\nthat gave merge-recursive its name, namely merging non-unique\nmerge-bases to come up with a single virtual merge base. Copy a few\nhelper functions from merge-recursive.c that we will use in the\nimplementation.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 32 ++++++++++++++++++++++++++++++++\n 1 file changed, 32 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 414e7b7eeac..05ba92c91a6 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,8 +17,10 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"alloc.h\"\n #include \"blob.h\"\n #include \"cache-tree.h\"\n+#include \"commit.h\"\n #include \"commit-reach.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n@@ -1348,6 +1350,34 @@ void merge_finalize(struct merge_options *opt,\n \n /*** Function Grouping: helper functions for merge_incore_*() ***/\n \n+static inline void set_commit_tree(struct commit *c, struct tree *t)\n+{\n+\tc->maybe_tree = t;\n+}\n+\n+static struct commit *make_virtual_commit(struct repository *repo,\n+\t\t\t\t\t struct tree *tree,\n+\t\t\t\t\t const char *comment)\n+{\n+\tstruct commit *commit = alloc_commit_node(repo);\n+\n+\tset_merge_remote_desc(commit, comment, (struct object *)commit);\n+\tset_commit_tree(commit, tree);\n+\tcommit->object.parsed = 1;\n+\treturn commit;\n+}\n+\n+static struct commit_list *reverse_commit_list(struct commit_list *list)\n+{\n+\tstruct commit_list *next = NULL, *current, *backup;\n+\tfor (current = list; current; current = backup) {\n+\t\tbackup = current->next;\n+\t\tcurrent->next = next;\n+\t\tnext = current;\n+\t}\n+\treturn next;\n+}\n+\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n \t/* Sanity checks on opt */\n@@ -1462,5 +1492,7 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n+\t(void)reverse_commit_list;\n+\t(void)make_virtual_commit;\n \tdie(\"Not yet implemented\");\n }\n-- \ngitgitgadget\n\n"},{"id":"412275","messageId":"pull.814.git.1608054807.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":null,"subject":"[PATCH 0/3] merge-ort: implement recursive merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-15T17:53:24Z","receivedAt":"2020-12-15T17:55:00Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-2 (it does NOT depend on en/merge-ort-3\nand can thus be reviewed/merged independently of it).\n\nThis short series adds handling of recursive merges (merging of multiple\nmerge-bases to create a virtual merge base) to merge-ort. With this short\nseries the number of test failures under GIT_TEST_MERGE_ALGORITHM=ort drops\nby 801 (from 1448 to 647).\n\nElijah Newren (3):\n merge-ort: copy a few small helper functions from merge-recursive.c\n merge-ort: make clear_internal_opts() aware of partial clearing\n merge-ort: implement merge_incore_recursive()\n\n merge-ort.c | 133 +++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 126 insertions(+), 7 deletions(-)\n\n\nbase-commit: c5a6f65527aa3b6f5d7cf25437a88d8727ab0646\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-814%2Fnewren%2Fort-recursive-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-814/newren/ort-recursive-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/814\n-- \ngitgitgadget\n"},{"id":"412322","messageId":"xmqqh7om5z50.fsf@gitster.c.googlers.com","threadId":"54831","inReplyTo":"0b455bd6fe7dff72c1849eb8466b97b96b2b90a9.1608054807.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-16T01:16:11Z","receivedAt":"2020-12-16T01:17:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> From: Elijah Newren \n>\n> In a subsequent commit, we will implement the traditional recursiveness\n> that gave merge-recursive its name, namely merging non-unique\n> merge-bases to come up with a single virtual merge base. Copy a few\n> helper functions from merge-recursive.c that we will use in the\n> implementation.\n>\n> Signed-off-by: Elijah Newren \n> ...\n> @@ -1462,5 +1492,7 @@ void merge_incore_recursive(struct merge_options *opt,\n> \t\t\t struct commit *side2,\n> \t\t\t struct merge_result *result)\n> {\n> +\t(void)reverse_commit_list;\n> +\t(void)make_virtual_commit;\n\nTo keep these symbols referenced? Cute ;-)\n\n> \tdie(\"Not yet implemented\");\n> }\n"},{"id":"412324","messageId":"xmqqbleu5wrs.fsf@gitster.c.googlers.com","threadId":"54831","inReplyTo":"82a773d8972b6641a25b3c84121dd38703a9286c.1608054807.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-16T02:07:19Z","receivedAt":"2020-12-16T02:08:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> +/*\n> + * Originally from merge_recursive_internal(); somewhat adapted, though.\n> + */\n> +static void merge_ort_internal(struct merge_options *opt,\n> +\t\t\t struct commit_list *merge_bases,\n> +\t\t\t struct commit *h1,\n> +\t\t\t struct commit *h2,\n> +\t\t\t struct merge_result *result)\n> +{\n> +\tstruct commit_list *iter;\n> +\tstruct commit *merged_merge_bases;\n> +\tconst char *ancestor_name;\n> +\tstruct strbuf merge_base_abbrev = STRBUF_INIT;\n> +\n> +\tif (!merge_bases) {\n> +\t\tmerge_bases = get_merge_bases(h1, h2);\n> +\t\tmerge_bases = reverse_commit_list(merge_bases);\n\nDo we want to say why we reverse here, or is the reason so well\nknown why in the original merge-recursive case?\n\n> +\t}\n> +\n> +\tmerged_merge_bases = pop_commit(&merge_bases);\n> +\tif (merged_merge_bases == NULL) {\n> +\t\t/* if there is no common ancestor, use an empty tree */\n> +\t\tstruct tree *tree;\n> +\n> +\t\ttree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n> +\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n> +\t\t\t\t\t\t\t \"ancestor\");\n> +\t\tancestor_name = \"empty tree\";\n> +\t} else if (opt->ancestor && !opt->priv->call_depth) {\n> +\t\tancestor_name = opt->ancestor;\n> +\t} else if (merge_bases) {\n> +\t\tancestor_name = \"merged common ancestors\";\n> +\t} else {\n> +\t\tstrbuf_add_unique_abbrev(&merge_base_abbrev,\n> +\t\t\t\t\t &merged_merge_bases->object.oid,\n> +\t\t\t\t\t DEFAULT_ABBREV);\n> +\t\tancestor_name = merge_base_abbrev.buf;\n> +\t}\n\nSo, up to this point we learned:\n\n - merge bases either given by the caller, or computed from h1 and\n h2 when the caller just told us to figure it out ourselves.\n\n - if we have\n\n - 0 merge base between h1 and h2, in which case we would use an\n empty tree as an imaginary common\n\n - 1 merge base between h1 and h2, in which case the common\n ancestor of the resuting merge between h1 and h2 is that single\n merge base\n\n - 2 or more bases, in which case we'd use that would eventually\n come back when we merged recursively all bases.\n\nand the primary products of the above procedure are\n\n - ancestor_name (the string used when presenting conflicts while\n merging h1 and h2)\n\n - merged_merge_bases (one starting commit among the merge bases)\n\nAnd then the loop will iterate over the remaining merge bases,\nmerging one popped from it in the current merged_merge_bases,\nuntil we run out. At that point when we leave the loop, we'd\nhave merged_merge_bases that is a virtual commit to be used as\na single merge base to use while merging trees of h1 and h2.\n\n> +\tfor (iter = merge_bases; iter; iter = iter->next) {\n> +\t\tconst char *saved_b1, *saved_b2;\n> +\t\tstruct commit *prev = merged_merge_bases;\n> +\n> +\t\topt->priv->call_depth++;\n> +\t\t/*\n> +\t\t * When the merge fails, the result contains files\n> +\t\t * with conflict markers. The cleanness flag is\n> +\t\t * ignored (unless indicating an error), it was never\n> +\t\t * actually used, as result of merge_trees has always\n> +\t\t * overwritten it: the committed \"conflicts\" were\n> +\t\t * already resolved.\n> +\t\t */\n> +\t\tsaved_b1 = opt->branch1;\n> +\t\tsaved_b2 = opt->branch2;\n> +\t\topt->branch1 = \"Temporary merge branch 1\";\n> +\t\topt->branch2 = \"Temporary merge branch 2\";\n> +\t\tmerge_ort_internal(opt, NULL, prev, iter->item, result);\n> +\t\tif (result->clean < 0)\n> +\t\t\treturn;\n> +\t\topt->branch1 = saved_b1;\n> +\t\topt->branch2 = saved_b2;\n> +\t\topt->priv->call_depth--;\n> +\n> +\t\tmerged_merge_bases = make_virtual_commit(opt->repo,\n> +\t\t\t\t\t\t\t result->tree,\n> +\t\t\t\t\t\t\t \"merged tree\");\n> +\t\tcommit_list_insert(prev, &merged_merge_bases->parents);\n> +\t\tcommit_list_insert(iter->item,\n> +\t\t\t\t &merged_merge_bases->parents->next);\n\nWe need to record these parents because...? When merged_merge_bases\nwe just created is used as one side of a merge in the next iteration,\nwe'd need to compute the merge base between it and the one we'd pop\nout of merge_bases, and that is why.\n\n> +\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n> +\t}\n\nOK. I think I understood this loop. It looks mostly straight-forward.\n\n> +\topt->ancestor = ancestor_name;\n\nAnd the label to be used, that was computed before the above loop,\nis used here...\n\n> +\tmerge_ort_nonrecursive_internal(opt,\n> +\t\t\t\t\trepo_get_commit_tree(opt->repo,\n> +\t\t\t\t\t\t\t merged_merge_bases),\n> +\t\t\t\t\trepo_get_commit_tree(opt->repo, h1),\n> +\t\t\t\t\trepo_get_commit_tree(opt->repo, h2),\n> +\t\t\t\t\tresult);\n\n... to finally compute the 3-way merge between h1 and h2.\n\n> +\tstrbuf_release(&merge_base_abbrev);\n\nAnd the storage that may have been holding the .ancestor name is\ncleared, as we no longer need it.\n\n> +\topt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n> +}\n> +\n> void merge_incore_nonrecursive(struct merge_options *opt,\n> \t\t\t struct tree *merge_base,\n> \t\t\t struct tree *side1,\n> @@ -1493,7 +1577,9 @@ void merge_incore_recursive(struct merge_options *opt,\n> \t\t\t struct commit *side2,\n> \t\t\t struct merge_result *result)\n> {\n> -\t(void)reverse_commit_list;\n> -\t(void)make_virtual_commit;\n> -\tdie(\"Not yet implemented\");\n> +\tassert(opt->ancestor == NULL ||\n> +\t !strcmp(opt->ancestor, \"constructed merge base\"));\n\nWhere does this string come from? The recursive backend does\nasssign a fixed string with that value to opt->ancestor, but we\ndon't expect that string to come here, no?\n\n> +\tmerge_start(opt, result);\n> +\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n> }\n"},{"id":"412331","messageId":"CABPp-BHW61zA+MefvWK47iVZKY97rxc2XZ-NjXzuJxEhgSLqUw@mail.gmail.com","threadId":"54831","inReplyTo":"xmqqbleu5wrs.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-16T04:09:14Z","receivedAt":"2020-12-16T04:10:23Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Dec 15, 2020 at 6:07 PM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > +/*\n> > + * Originally from merge_recursive_internal(); somewhat adapted, though.\n> > + */\n> > +static void merge_ort_internal(struct merge_options *opt,\n> > + struct commit_list *merge_bases,\n> > + struct commit *h1,\n> > + struct commit *h2,\n> > + struct merge_result *result)\n> > +{\n> > + struct commit_list *iter;\n> > + struct commit *merged_merge_bases;\n> > + const char *ancestor_name;\n> > + struct strbuf merge_base_abbrev = STRBUF_INIT;\n> > +\n> > + if (!merge_bases) {\n> > + merge_bases = get_merge_bases(h1, h2);\n> > + merge_bases = reverse_commit_list(merge_bases);\n>\n> Do we want to say why we reverse here, or is the reason so well\n> known why in the original merge-recursive case?\n\nOh, good point. After starting on merge-ort, I shifted back and forth\nbetween it and cleaning up merge-recursive for a while...and it looks\nlike this is one of the things I forgot to copy over. The reason was\ntotally opaque to me until Johannes spelled it out over here:\nhttps://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n\nNote that the same reversing of merge bases is done in builtin/merge.c\nand sequencer.c as well. It resulted in me adding the following note\nto the declaration of merge_recursive() in merge-recursive.h:\n\n * NOTE: empirically, about a decade ago it was determined that with more\n * than two merge bases, optimal behavior was found when the\n * merge_bases were passed in the order of oldest commit to newest\n * commit. Also, merge_bases will be consumed (emptied) so make a\n * copy if you need it.\n\nbut I never copied that comment over to merge_incore_recursive(). I\nshould do that, and perhaps reference that comment at this point in\nthe code.\n\n> > + }\n> > +\n> > + merged_merge_bases = pop_commit(&merge_bases);\n> > + if (merged_merge_bases == NULL) {\n> > + /* if there is no common ancestor, use an empty tree */\n> > + struct tree *tree;\n> > +\n> > + tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n> > + merged_merge_bases = make_virtual_commit(opt->repo, tree,\n> > + \"ancestor\");\n> > + ancestor_name = \"empty tree\";\n> > + } else if (opt->ancestor && !opt->priv->call_depth) {\n> > + ancestor_name = opt->ancestor;\n> > + } else if (merge_bases) {\n> > + ancestor_name = \"merged common ancestors\";\n> > + } else {\n> > + strbuf_add_unique_abbrev(&merge_base_abbrev,\n> > + &merged_merge_bases->object.oid,\n> > + DEFAULT_ABBREV);\n> > + ancestor_name = merge_base_abbrev.buf;\n> > + }\n>\n> So, up to this point we learned:\n>\n> - merge bases either given by the caller, or computed from h1 and\n> h2 when the caller just told us to figure it out ourselves.\n>\n> - if we have\n>\n> - 0 merge base between h1 and h2, in which case we would use an\n> empty tree as an imaginary common\n>\n> - 1 merge base between h1 and h2, in which case the common\n> ancestor of the resuting merge between h1 and h2 is that single\n> merge base\n>\n> - 2 or more bases, in which case we'd use that would eventually\n> come back when we merged recursively all bases.\n>\n> and the primary products of the above procedure are\n>\n> - ancestor_name (the string used when presenting conflicts while\n> merging h1 and h2)\n>\n> - merged_merge_bases (one starting commit among the merge bases)\n>\n> And then the loop will iterate over the remaining merge bases,\n> merging one popped from it in the current merged_merge_bases,\n> until we run out. At that point when we leave the loop, we'd\n> have merged_merge_bases that is a virtual commit to be used as\n> a single merge base to use while merging trees of h1 and h2.\n>\n> > + for (iter = merge_bases; iter; iter = iter->next) {\n> > + const char *saved_b1, *saved_b2;\n> > + struct commit *prev = merged_merge_bases;\n> > +\n> > + opt->priv->call_depth++;\n> > + /*\n> > + * When the merge fails, the result contains files\n> > + * with conflict markers. The cleanness flag is\n> > + * ignored (unless indicating an error), it was never\n> > + * actually used, as result of merge_trees has always\n> > + * overwritten it: the committed \"conflicts\" were\n> > + * already resolved.\n> > + */\n> > + saved_b1 = opt->branch1;\n> > + saved_b2 = opt->branch2;\n> > + opt->branch1 = \"Temporary merge branch 1\";\n> > + opt->branch2 = \"Temporary merge branch 2\";\n> > + merge_ort_internal(opt, NULL, prev, iter->item, result);\n> > + if (result->clean < 0)\n> > + return;\n> > + opt->branch1 = saved_b1;\n> > + opt->branch2 = saved_b2;\n> > + opt->priv->call_depth--;\n> > +\n> > + merged_merge_bases = make_virtual_commit(opt->repo,\n> > + result->tree,\n> > + \"merged tree\");\n> > + commit_list_insert(prev, &merged_merge_bases->parents);\n> > + commit_list_insert(iter->item,\n> > + &merged_merge_bases->parents->next);\n>\n> We need to record these parents because...? When merged_merge_bases\n> we just created is used as one side of a merge in the next iteration,\n> we'd need to compute the merge base between it and the one we'd pop\n> out of merge_bases, and that is why.\n>\n> > + clear_or_reinit_internal_opts(opt->priv, 1);\n> > + }\n>\n> OK. I think I understood this loop. It looks mostly straight-forward.\n>\n> > + opt->ancestor = ancestor_name;\n>\n> And the label to be used, that was computed before the above loop,\n> is used here...\n>\n> > + merge_ort_nonrecursive_internal(opt,\n> > + repo_get_commit_tree(opt->repo,\n> > + merged_merge_bases),\n> > + repo_get_commit_tree(opt->repo, h1),\n> > + repo_get_commit_tree(opt->repo, h2),\n> > + result);\n>\n> ... to finally compute the 3-way merge between h1 and h2.\n>\n> > + strbuf_release(&merge_base_abbrev);\n>\n> And the storage that may have been holding the .ancestor name is\n> cleared, as we no longer need it.\n>\n> > + opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n> > +}\n> > +\n> > void merge_incore_nonrecursive(struct merge_options *opt,\n> > struct tree *merge_base,\n> > struct tree *side1,\n> > @@ -1493,7 +1577,9 @@ void merge_incore_recursive(struct merge_options *opt,\n> > struct commit *side2,\n> > struct merge_result *result)\n> > {\n> > - (void)reverse_commit_list;\n> > - (void)make_virtual_commit;\n> > - die(\"Not yet implemented\");\n> > + assert(opt->ancestor == NULL ||\n> > + !strcmp(opt->ancestor, \"constructed merge base\"));\n>\n> Where does this string come from? The recursive backend does\n> asssign a fixed string with that value to opt->ancestor, but we\n> don't expect that string to come here, no?\n\nIt's specifically the merge_recursive_generic() function from\nmerge-recursive.c that sets this, which was part of the\nmerge-recursive API. merge-ort does not (yet?) have an equivalent\nfunction (anything calling merge_recursive_generic() just can't use\nmerge-ort right now -- a list that includes 'am', 'stash', and\n'merge-recursive'). For now, I am just letting those callers continue\nto use merge-recursive.c. I never figured out if I wanted to make\nthat function part of merge-ort's API, whether I just wanted to add a\nwrapper to merge-ort-wrappers.[ch] for it, or if I should rewrite the\ncallers to do something else.\n\nHowever, looking a little closer, the name for opt->ancestor is\nslightly phony -- I think it only makes sense for \"am\", not for either\nof \"stash\" or \"merge-recursive\". Perhaps I should instead count the\nnumber of merge_bases, and assert that either opt->ancestor == NULL\n(exclusive)OR num_merge_bases == 1. merge_recursive_generic() should\nalso be made to stop setting opt->ancestor, and then callers like\n\"am\", \"stash\", and \"merge-recursive\" should be responsible to provide\na reasonable ancestor name for merge.conflictStyle=diff3 to use when\nit's clear they are providing the sole ancestor.\n\nThen at some point I can decide what to do with\nmerge_recursive_generic(). I'll probably just make it a wrapper at\nsome point; since that lets me kick the can down the road even\nfurther. :-)\n\n> > + merge_start(opt, result);\n> > + merge_ort_internal(opt, merge_bases, side1, side2, result);\n> > }\n"},{"id":"412332","messageId":"CABPp-BEk514YEdgDHmrD-sD7tZ=xnJxfV8cpS9-_qP-xQYTKxQ@mail.gmail.com","threadId":"54831","inReplyTo":"CABPp-BHW61zA+MefvWK47iVZKY97rxc2XZ-NjXzuJxEhgSLqUw@mail.gmail.com","subject":"Re: [PATCH 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-16T04:44:45Z","receivedAt":"2020-12-16T04:45:43Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Dec 15, 2020 at 8:09 PM Elijah Newren wrote:\n>\n> On Tue, Dec 15, 2020 at 6:07 PM Junio C Hamano wrote:\n> >\n> > \"Elijah Newren via GitGitGadget\" writes:\n> >\n> > > +/*\n> > > + * Originally from merge_recursive_internal(); somewhat adapted, though.\n> > > + */\n> > > +static void merge_ort_internal(struct merge_options *opt,\n> > > + struct commit_list *merge_bases,\n> > > + struct commit *h1,\n> > > + struct commit *h2,\n> > > + struct merge_result *result)\n> > > +{\n> > > + struct commit_list *iter;\n> > > + struct commit *merged_merge_bases;\n> > > + const char *ancestor_name;\n> > > + struct strbuf merge_base_abbrev = STRBUF_INIT;\n> > > +\n> > > + if (!merge_bases) {\n> > > + merge_bases = get_merge_bases(h1, h2);\n> > > + merge_bases = reverse_commit_list(merge_bases);\n> >\n> > Do we want to say why we reverse here, or is the reason so well\n> > known why in the original merge-recursive case?\n>\n> Oh, good point. After starting on merge-ort, I shifted back and forth\n> between it and cleaning up merge-recursive for a while...and it looks\n> like this is one of the things I forgot to copy over. The reason was\n> totally opaque to me until Johannes spelled it out over here:\n> https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n>\n> Note that the same reversing of merge bases is done in builtin/merge.c\n> and sequencer.c as well. It resulted in me adding the following note\n> to the declaration of merge_recursive() in merge-recursive.h:\n>\n> * NOTE: empirically, about a decade ago it was determined that with more\n> * than two merge bases, optimal behavior was found when the\n> * merge_bases were passed in the order of oldest commit to newest\n> * commit. Also, merge_bases will be consumed (emptied) so make a\n> * copy if you need it.\n>\n> but I never copied that comment over to merge_incore_recursive(). I\n> should do that, and perhaps reference that comment at this point in\n> the code.\n>\n> > > + }\n> > > +\n> > > + merged_merge_bases = pop_commit(&merge_bases);\n> > > + if (merged_merge_bases == NULL) {\n> > > + /* if there is no common ancestor, use an empty tree */\n> > > + struct tree *tree;\n> > > +\n> > > + tree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n> > > + merged_merge_bases = make_virtual_commit(opt->repo, tree,\n> > > + \"ancestor\");\n> > > + ancestor_name = \"empty tree\";\n> > > + } else if (opt->ancestor && !opt->priv->call_depth) {\n> > > + ancestor_name = opt->ancestor;\n> > > + } else if (merge_bases) {\n> > > + ancestor_name = \"merged common ancestors\";\n> > > + } else {\n> > > + strbuf_add_unique_abbrev(&merge_base_abbrev,\n> > > + &merged_merge_bases->object.oid,\n> > > + DEFAULT_ABBREV);\n> > > + ancestor_name = merge_base_abbrev.buf;\n> > > + }\n> >\n> > So, up to this point we learned:\n> >\n> > - merge bases either given by the caller, or computed from h1 and\n> > h2 when the caller just told us to figure it out ourselves.\n> >\n> > - if we have\n> >\n> > - 0 merge base between h1 and h2, in which case we would use an\n> > empty tree as an imaginary common\n> >\n> > - 1 merge base between h1 and h2, in which case the common\n> > ancestor of the resuting merge between h1 and h2 is that single\n> > merge base\n> >\n> > - 2 or more bases, in which case we'd use that would eventually\n> > come back when we merged recursively all bases.\n> >\n> > and the primary products of the above procedure are\n> >\n> > - ancestor_name (the string used when presenting conflicts while\n> > merging h1 and h2)\n> >\n> > - merged_merge_bases (one starting commit among the merge bases)\n> >\n> > And then the loop will iterate over the remaining merge bases,\n> > merging one popped from it in the current merged_merge_bases,\n> > until we run out. At that point when we leave the loop, we'd\n> > have merged_merge_bases that is a virtual commit to be used as\n> > a single merge base to use while merging trees of h1 and h2.\n> >\n> > > + for (iter = merge_bases; iter; iter = iter->next) {\n> > > + const char *saved_b1, *saved_b2;\n> > > + struct commit *prev = merged_merge_bases;\n> > > +\n> > > + opt->priv->call_depth++;\n> > > + /*\n> > > + * When the merge fails, the result contains files\n> > > + * with conflict markers. The cleanness flag is\n> > > + * ignored (unless indicating an error), it was never\n> > > + * actually used, as result of merge_trees has always\n> > > + * overwritten it: the committed \"conflicts\" were\n> > > + * already resolved.\n> > > + */\n> > > + saved_b1 = opt->branch1;\n> > > + saved_b2 = opt->branch2;\n> > > + opt->branch1 = \"Temporary merge branch 1\";\n> > > + opt->branch2 = \"Temporary merge branch 2\";\n> > > + merge_ort_internal(opt, NULL, prev, iter->item, result);\n> > > + if (result->clean < 0)\n> > > + return;\n> > > + opt->branch1 = saved_b1;\n> > > + opt->branch2 = saved_b2;\n> > > + opt->priv->call_depth--;\n> > > +\n> > > + merged_merge_bases = make_virtual_commit(opt->repo,\n> > > + result->tree,\n> > > + \"merged tree\");\n> > > + commit_list_insert(prev, &merged_merge_bases->parents);\n> > > + commit_list_insert(iter->item,\n> > > + &merged_merge_bases->parents->next);\n> >\n> > We need to record these parents because...? When merged_merge_bases\n> > we just created is used as one side of a merge in the next iteration,\n> > we'd need to compute the merge base between it and the one we'd pop\n> > out of merge_bases, and that is why.\n> >\n> > > + clear_or_reinit_internal_opts(opt->priv, 1);\n> > > + }\n> >\n> > OK. I think I understood this loop. It looks mostly straight-forward.\n> >\n> > > + opt->ancestor = ancestor_name;\n> >\n> > And the label to be used, that was computed before the above loop,\n> > is used here...\n> >\n> > > + merge_ort_nonrecursive_internal(opt,\n> > > + repo_get_commit_tree(opt->repo,\n> > > + merged_merge_bases),\n> > > + repo_get_commit_tree(opt->repo, h1),\n> > > + repo_get_commit_tree(opt->repo, h2),\n> > > + result);\n> >\n> > ... to finally compute the 3-way merge between h1 and h2.\n> >\n> > > + strbuf_release(&merge_base_abbrev);\n> >\n> > And the storage that may have been holding the .ancestor name is\n> > cleared, as we no longer need it.\n> >\n> > > + opt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n> > > +}\n> > > +\n> > > void merge_incore_nonrecursive(struct merge_options *opt,\n> > > struct tree *merge_base,\n> > > struct tree *side1,\n> > > @@ -1493,7 +1577,9 @@ void merge_incore_recursive(struct merge_options *opt,\n> > > struct commit *side2,\n> > > struct merge_result *result)\n> > > {\n> > > - (void)reverse_commit_list;\n> > > - (void)make_virtual_commit;\n> > > - die(\"Not yet implemented\");\n> > > + assert(opt->ancestor == NULL ||\n> > > + !strcmp(opt->ancestor, \"constructed merge base\"));\n> >\n> > Where does this string come from? The recursive backend does\n> > asssign a fixed string with that value to opt->ancestor, but we\n> > don't expect that string to come here, no?\n>\n> It's specifically the merge_recursive_generic() function from\n> merge-recursive.c that sets this, which was part of the\n> merge-recursive API. merge-ort does not (yet?) have an equivalent\n> function (anything calling merge_recursive_generic() just can't use\n> merge-ort right now -- a list that includes 'am', 'stash', and\n> 'merge-recursive'). For now, I am just letting those callers continue\n> to use merge-recursive.c. I never figured out if I wanted to make\n> that function part of merge-ort's API, whether I just wanted to add a\n> wrapper to merge-ort-wrappers.[ch] for it, or if I should rewrite the\n> callers to do something else.\n>\n> However, looking a little closer, the name for opt->ancestor is\n> slightly phony -- I think it only makes sense for \"am\", not for either\n> of \"stash\" or \"merge-recursive\". Perhaps I should instead count the\n> number of merge_bases, and assert that either opt->ancestor == NULL\n> (exclusive)OR num_merge_bases == 1. merge_recursive_generic() should\n\nNo, this isn't right. Most callers just grab all the merge bases and\noften there happens to be only one. In such a case, the caller\nshouldn't have to set opt->ancestor; the fallback of referencing the\ncommit id is perfectly good there. It's just that when there is\nexactly one merge base, a special caller like\nmerge_recursive_generic() might want to override the value for\nopt->ancestor.\n\nAnyway, I'll post a new patch soon.\n\n> also be made to stop setting opt->ancestor, and then callers like\n> \"am\", \"stash\", and \"merge-recursive\" should be responsible to provide\n> a reasonable ancestor name for merge.conflictStyle=diff3 to use when\n> it's clear they are providing the sole ancestor.\n>\n> Then at some point I can decide what to do with\n> merge_recursive_generic(). I'll probably just make it a wrapper at\n> some point; since that lets me kick the can down the road even\n> further. :-)\n>\n> > > + merge_start(opt, result);\n> > > + merge_ort_internal(opt, merge_bases, side1, side2, result);\n> > > }\n"},{"id":"412333","messageId":"fc26c1a11db76843b0a439d2c69567fcd7ad9ac2.1608097965.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v2.git.1608097965.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] merge-ort: make clear_internal_opts() aware of partial clearing","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T05:52:43Z","receivedAt":"2020-12-16T05:53:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to handle recursive merges, after merging merge-bases we need\nto clear away most of the data we had built up but some of it needs to\nbe kept -- in particular the \"output\" field. Rename the function to\nreflect its future change in use.\n\nFurther, since \"reinitialize\" means we'll be reusing the fields\nimmediately, take advantage of this to only partially clear maps,\nleaving the hashtable allocated and pre-sized. (This may be slightly\nout-of-order since the speedups aren't realized until there are far\nmore strmaps in use, but the patch submission process already went out\nof order because of various questions and requests for strmap. Anyway,\nsee commit 6ccdfc2a20 (\"strmap: enable faster clearing and reusing of\nstrmaps\", 2020-11-05), for performance details about the use of\nstrmap_partial_clear().)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 05ba92c91a6..10a97e944c4 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -253,10 +253,11 @@ static void free_strmap_strings(struct strmap *map)\n \t}\n }\n \n-static void clear_internal_opts(struct merge_options_internal *opti,\n-\t\t\t\tint reinitialize)\n+static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n+\t\t\t\t\t int reinitialize)\n {\n-\tassert(!reinitialize);\n+\tvoid (*strmap_func)(struct strmap *, int) =\n+\t\treinitialize ? strmap_partial_clear : strmap_clear;\n \n \t/*\n \t * We marked opti->paths with strdup_strings = 0, so that we\n@@ -266,14 +267,14 @@ static void clear_internal_opts(struct merge_options_internal *opti,\n \t * to deallocate them.\n \t */\n \tfree_strmap_strings(&opti->paths);\n-\tstrmap_clear(&opti->paths, 1);\n+\tstrmap_func(&opti->paths, 1);\n \n \t/*\n \t * All keys and values in opti->conflicted are a subset of those in\n \t * opti->paths. We don't want to deallocate anything twice, so we\n \t * don't free the keys and we pass 0 for free_values.\n \t */\n-\tstrmap_clear(&opti->conflicted, 0);\n+\tstrmap_func(&opti->conflicted, 0);\n \n \t/*\n \t * opti->paths_to_free is similar to opti->paths; we created it with\n@@ -1344,7 +1345,7 @@ void merge_finalize(struct merge_options *opt,\n \n \tassert(opt->priv == NULL);\n \n-\tclear_internal_opts(opti, 0);\n+\tclear_or_reinit_internal_opts(opti, 0);\n \tFREE_AND_NULL(opti);\n }\n \n-- \ngitgitgadget\n\n"},{"id":"412334","messageId":"pull.814.v2.git.1608097965.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.git.1608054807.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] merge-ort: implement recursive merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T05:52:41Z","receivedAt":"2020-12-16T05:53:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-2 (it does NOT depend on en/merge-ort-3\nand can thus be reviewed/merged independently of it).\n\nThis short series adds handling of recursive merges (merging of multiple\nmerge-bases to create a virtual merge base) to merge-ort. With this short\nseries the number of test failures under GIT_TEST_MERGE_ALGORITHM=ort drops\nby 801 (from 1448 to 647).\n\nChanges since v1 (based on review comments from Junio):\n\n * add documentation on why we reverse the commit_list of merge bases\n * modify the special override for allowing opt->ancestor to be set before\n merge_incore_recursive() and document its rationale\n\nElijah Newren (3):\n merge-ort: copy a few small helper functions from merge-recursive.c\n merge-ort: make clear_internal_opts() aware of partial clearing\n merge-ort: implement merge_incore_recursive()\n\n merge-ort.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++---\n merge-ort.h | 10 ++++\n 2 files changed, 152 insertions(+), 7 deletions(-)\n\n\nbase-commit: c5a6f65527aa3b6f5d7cf25437a88d8727ab0646\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-814%2Fnewren%2Fort-recursive-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-814/newren/ort-recursive-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/814\n\nRange-diff vs v1:\n\n 1: 0b455bd6fe7 = 1: 0b455bd6fe7 merge-ort: copy a few small helper functions from merge-recursive.c\n 2: fc26c1a11db = 2: fc26c1a11db merge-ort: make clear_internal_opts() aware of partial clearing\n 3: 82a773d8972 ! 3: d8f79450a40 merge-ort: implement merge_incore_recursive()\n @@ merge-ort.c: static void merge_ort_nonrecursive_internal(struct merge_options *o\n +\n +\tif (!merge_bases) {\n +\t\tmerge_bases = get_merge_bases(h1, h2);\n ++\t\t/* See merge-ort.h:merge_incore_recursive() declaration NOTE */\n +\t\tmerge_bases = reverse_commit_list(merge_bases);\n +\t}\n +\n @@ merge-ort.c: void merge_incore_recursive(struct merge_options *opt,\n -\t(void)reverse_commit_list;\n -\t(void)make_virtual_commit;\n -\tdie(\"Not yet implemented\");\n -+\tassert(opt->ancestor == NULL ||\n -+\t !strcmp(opt->ancestor, \"constructed merge base\"));\n ++\t/*\n ++\t * merge_incore_nonrecursive() exists for cases where we always\n ++\t * know there is a well-defined single merge base. However,\n ++\t * despite a similar structure, merge-recursive.c noted that some\n ++\t * callers preferred to call the recursive logic anyway and still\n ++\t * set a special name for opt->ancestor that would appear in\n ++\t * merge.conflictStyle=diff3 output.\n ++\t *\n ++\t * git-am was one such example (it wanted to set opt->ancestor to\n ++\t * \"constructed merge base\", since it created a fake merge base);\n ++\t * it called the recursive merge logic through a special\n ++\t * merge_recursive_generic() wrapper.\n ++\t *\n ++\t * Allow the same kind of special case here.\n ++\t */\n ++\tint num_merge_bases_is_1 = (merge_bases && !merge_bases->next);\n ++\tassert(opt->ancestor == NULL || num_merge_bases_is_1);\n +\n +\tmerge_start(opt, result);\n +\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n }\n +\n + ## merge-ort.h ##\n +@@ merge-ort.h: struct merge_result {\n + /*\n + * rename-detecting three-way merge with recursive ancestor consolidation.\n + * working tree and index are untouched.\n ++ *\n ++ * merge_bases will be consumed (emptied) so make a copy if you need it.\n ++ *\n ++ * NOTE: empirically, the recursive algorithm will perform better if you\n ++ * pass the merge_bases in the order of oldest commit to the\n ++ * newest[1][2].\n ++ *\n ++ * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n ++ * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n ++ * first\", 2006-08-09)\n + */\n + void merge_incore_recursive(struct merge_options *opt,\n + \t\t\t struct commit_list *merge_bases,\n\n-- \ngitgitgadget\n"},{"id":"412335","messageId":"d8f79450a40e5a91b401ccbbedc7326cfe8a33d6.1608097965.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v2.git.1608097965.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T05:52:44Z","receivedAt":"2020-12-16T05:53:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nImplement merge_incore_recursive(), mostly through the use of a new\nhelper function, merge_ort_internal(), which itself is based off\nmerge_recursive_internal() from merge-recursive.c.\n\nThis drops the number of failures in the testsuite when run under\nGIT_TEST_MERGE_ALGORITHM=ort from around 1500 to 647.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++--\n merge-ort.h | 10 +++++\n 2 files changed, 115 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 10a97e944c4..de9585b3179 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1476,6 +1476,91 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n \n+/*\n+ * Originally from merge_recursive_internal(); somewhat adapted, though.\n+ */\n+static void merge_ort_internal(struct merge_options *opt,\n+\t\t\t struct commit_list *merge_bases,\n+\t\t\t struct commit *h1,\n+\t\t\t struct commit *h2,\n+\t\t\t struct merge_result *result)\n+{\n+\tstruct commit_list *iter;\n+\tstruct commit *merged_merge_bases;\n+\tconst char *ancestor_name;\n+\tstruct strbuf merge_base_abbrev = STRBUF_INIT;\n+\n+\tif (!merge_bases) {\n+\t\tmerge_bases = get_merge_bases(h1, h2);\n+\t\t/* See merge-ort.h:merge_incore_recursive() declaration NOTE */\n+\t\tmerge_bases = reverse_commit_list(merge_bases);\n+\t}\n+\n+\tmerged_merge_bases = pop_commit(&merge_bases);\n+\tif (merged_merge_bases == NULL) {\n+\t\t/* if there is no common ancestor, use an empty tree */\n+\t\tstruct tree *tree;\n+\n+\t\ttree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n+\t\t\t\t\t\t\t \"ancestor\");\n+\t\tancestor_name = \"empty tree\";\n+\t} else if (opt->ancestor && !opt->priv->call_depth) {\n+\t\tancestor_name = opt->ancestor;\n+\t} else if (merge_bases) {\n+\t\tancestor_name = \"merged common ancestors\";\n+\t} else {\n+\t\tstrbuf_add_unique_abbrev(&merge_base_abbrev,\n+\t\t\t\t\t &merged_merge_bases->object.oid,\n+\t\t\t\t\t DEFAULT_ABBREV);\n+\t\tancestor_name = merge_base_abbrev.buf;\n+\t}\n+\n+\tfor (iter = merge_bases; iter; iter = iter->next) {\n+\t\tconst char *saved_b1, *saved_b2;\n+\t\tstruct commit *prev = merged_merge_bases;\n+\n+\t\topt->priv->call_depth++;\n+\t\t/*\n+\t\t * When the merge fails, the result contains files\n+\t\t * with conflict markers. The cleanness flag is\n+\t\t * ignored (unless indicating an error), it was never\n+\t\t * actually used, as result of merge_trees has always\n+\t\t * overwritten it: the committed \"conflicts\" were\n+\t\t * already resolved.\n+\t\t */\n+\t\tsaved_b1 = opt->branch1;\n+\t\tsaved_b2 = opt->branch2;\n+\t\topt->branch1 = \"Temporary merge branch 1\";\n+\t\topt->branch2 = \"Temporary merge branch 2\";\n+\t\tmerge_ort_internal(opt, NULL, prev, iter->item, result);\n+\t\tif (result->clean < 0)\n+\t\t\treturn;\n+\t\topt->branch1 = saved_b1;\n+\t\topt->branch2 = saved_b2;\n+\t\topt->priv->call_depth--;\n+\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo,\n+\t\t\t\t\t\t\t result->tree,\n+\t\t\t\t\t\t\t \"merged tree\");\n+\t\tcommit_list_insert(prev, &merged_merge_bases->parents);\n+\t\tcommit_list_insert(iter->item,\n+\t\t\t\t &merged_merge_bases->parents->next);\n+\n+\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n+\t}\n+\n+\topt->ancestor = ancestor_name;\n+\tmerge_ort_nonrecursive_internal(opt,\n+\t\t\t\t\trepo_get_commit_tree(opt->repo,\n+\t\t\t\t\t\t\t merged_merge_bases),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h1),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h2),\n+\t\t\t\t\tresult);\n+\tstrbuf_release(&merge_base_abbrev);\n+\topt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n+}\n+\n void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n@@ -1493,7 +1578,24 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n-\t(void)reverse_commit_list;\n-\t(void)make_virtual_commit;\n-\tdie(\"Not yet implemented\");\n+\t/*\n+\t * merge_incore_nonrecursive() exists for cases where we always\n+\t * know there is a well-defined single merge base. However,\n+\t * despite a similar structure, merge-recursive.c noted that some\n+\t * callers preferred to call the recursive logic anyway and still\n+\t * set a special name for opt->ancestor that would appear in\n+\t * merge.conflictStyle=diff3 output.\n+\t *\n+\t * git-am was one such example (it wanted to set opt->ancestor to\n+\t * \"constructed merge base\", since it created a fake merge base);\n+\t * it called the recursive merge logic through a special\n+\t * merge_recursive_generic() wrapper.\n+\t *\n+\t * Allow the same kind of special case here.\n+\t */\n+\tint num_merge_bases_is_1 = (merge_bases && !merge_bases->next);\n+\tassert(opt->ancestor == NULL || num_merge_bases_is_1);\n+\n+\tmerge_start(opt, result);\n+\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n }\ndiff --git a/merge-ort.h b/merge-ort.h\nindex 55ae7ee865d..d53a0a339f3 100644\n--- a/merge-ort.h\n+++ b/merge-ort.h\n@@ -34,6 +34,16 @@ struct merge_result {\n /*\n * rename-detecting three-way merge with recursive ancestor consolidation.\n * working tree and index are untouched.\n+ *\n+ * merge_bases will be consumed (emptied) so make a copy if you need it.\n+ *\n+ * NOTE: empirically, the recursive algorithm will perform better if you\n+ * pass the merge_bases in the order of oldest commit to the\n+ * newest[1][2].\n+ *\n+ * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n+ * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n+ * first\", 2006-08-09)\n */\n void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit_list *merge_bases,\n-- \ngitgitgadget\n"},{"id":"412336","messageId":"0b455bd6fe7dff72c1849eb8466b97b96b2b90a9.1608097965.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v2.git.1608097965.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T05:52:42Z","receivedAt":"2020-12-16T05:54:06Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn a subsequent commit, we will implement the traditional recursiveness\nthat gave merge-recursive its name, namely merging non-unique\nmerge-bases to come up with a single virtual merge base. Copy a few\nhelper functions from merge-recursive.c that we will use in the\nimplementation.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 32 ++++++++++++++++++++++++++++++++\n 1 file changed, 32 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 414e7b7eeac..05ba92c91a6 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,8 +17,10 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"alloc.h\"\n #include \"blob.h\"\n #include \"cache-tree.h\"\n+#include \"commit.h\"\n #include \"commit-reach.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n@@ -1348,6 +1350,34 @@ void merge_finalize(struct merge_options *opt,\n \n /*** Function Grouping: helper functions for merge_incore_*() ***/\n \n+static inline void set_commit_tree(struct commit *c, struct tree *t)\n+{\n+\tc->maybe_tree = t;\n+}\n+\n+static struct commit *make_virtual_commit(struct repository *repo,\n+\t\t\t\t\t struct tree *tree,\n+\t\t\t\t\t const char *comment)\n+{\n+\tstruct commit *commit = alloc_commit_node(repo);\n+\n+\tset_merge_remote_desc(commit, comment, (struct object *)commit);\n+\tset_commit_tree(commit, tree);\n+\tcommit->object.parsed = 1;\n+\treturn commit;\n+}\n+\n+static struct commit_list *reverse_commit_list(struct commit_list *list)\n+{\n+\tstruct commit_list *next = NULL, *current, *backup;\n+\tfor (current = list; current; current = backup) {\n+\t\tbackup = current->next;\n+\t\tcurrent->next = next;\n+\t\tnext = current;\n+\t}\n+\treturn next;\n+}\n+\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n \t/* Sanity checks on opt */\n@@ -1462,5 +1492,7 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n+\t(void)reverse_commit_list;\n+\t(void)make_virtual_commit;\n \tdie(\"Not yet implemented\");\n }\n-- \ngitgitgadget\n\n"},{"id":"412354","messageId":"4a4d9d29-ccba-8d39-a7cd-34b1ba785e22@gmail.com","threadId":"54831","inReplyTo":"0b455bd6fe7dff72c1849eb8466b97b96b2b90a9.1608054807.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-16T13:30:23Z","receivedAt":"2020-12-16T13:31:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/15/2020 12:53 PM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n> \n> In a subsequent commit, we will implement the traditional recursiveness\n> that gave merge-recursive its name, namely merging non-unique\n> merge-bases to come up with a single virtual merge base. Copy a few\n> helper functions from merge-recursive.c that we will use in the\n> implementation.\n\nI'm sure these are copies, but...\n\n> +static struct commit_list *reverse_commit_list(struct commit_list *list)\n> +{\n> +\tstruct commit_list *next = NULL, *current, *backup;\n> +\tfor (current = list; current; current = backup) {\n> +\t\tbackup = current->next;\n> +\t\tcurrent->next = next;\n> +\t\tnext = current;\n> +\t}\n\nThe naming of 'next' seems backwards to me, since it is really\nthe \"previous\" node. Using something like 'previous' makes it\nclear that you are reversing when you say\n\n\tcurrent->next = previous;\n\nThanks,\n-Stolee\n"},{"id":"412369","messageId":"nycvar.QRO.7.76.6.2012161710170.56@tvgsbejvaqbjf.bet","threadId":"54831","inReplyTo":"xmqqh7om5z50.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2020-12-16T16:12:19Z","receivedAt":"2020-12-16T16:14:04Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Tue, 15 Dec 2020, Junio C Hamano wrote:\n\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > From: Elijah Newren \n> >\n> > In a subsequent commit, we will implement the traditional recursiveness\n> > that gave merge-recursive its name, namely merging non-unique\n> > merge-bases to come up with a single virtual merge base. Copy a few\n> > helper functions from merge-recursive.c that we will use in the\n> > implementation.\n> >\n> > Signed-off-by: Elijah Newren \n> > ...\n> > @@ -1462,5 +1492,7 @@ void merge_incore_recursive(struct merge_options *opt,\n> > \t\t\t struct commit *side2,\n> > \t\t\t struct merge_result *result)\n> > {\n> > +\t(void)reverse_commit_list;\n> > +\t(void)make_virtual_commit;\n>\n> To keep these symbols referenced? Cute ;-)\n\nI saw this technique used extensively in cURL. Note that we ourselves\nintroduced the first such thing in 2fb330ca723 (packed_delete_refs():\nimplement method, 2017-09-08).\n\nHowever, we seem to have the `MAYBE_UNUSED` macro specifically for such\nuse cases (and use it in four instances as of time of writing). I wonder\nwhether we want to settle one one strategy instead of keeping both?\n\nCiao,\nDscho\n\n>\n> > \tdie(\"Not yet implemented\");\n> > }\n>\n"},{"id":"412370","messageId":"CABPp-BHf=G7xgVLLF+6hSazHB-=botZ3k2EHNXrZREeMhK787A@mail.gmail.com","threadId":"54831","inReplyTo":"nycvar.QRO.7.76.6.2012161710170.56@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-16T16:24:55Z","receivedAt":"2020-12-16T16:25:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 16, 2020 at 8:12 AM Johannes Schindelin\n wrote:\n>\n> Hi Junio,\n>\n> On Tue, 15 Dec 2020, Junio C Hamano wrote:\n>\n> > \"Elijah Newren via GitGitGadget\" writes:\n> >\n> > > From: Elijah Newren \n> > >\n> > > In a subsequent commit, we will implement the traditional recursiveness\n> > > that gave merge-recursive its name, namely merging non-unique\n> > > merge-bases to come up with a single virtual merge base. Copy a few\n> > > helper functions from merge-recursive.c that we will use in the\n> > > implementation.\n> > >\n> > > Signed-off-by: Elijah Newren \n> > > ...\n> > > @@ -1462,5 +1492,7 @@ void merge_incore_recursive(struct merge_options *opt,\n> > > struct commit *side2,\n> > > struct merge_result *result)\n> > > {\n> > > + (void)reverse_commit_list;\n> > > + (void)make_virtual_commit;\n> >\n> > To keep these symbols referenced? Cute ;-)\n>\n> I saw this technique used extensively in cURL. Note that we ourselves\n> introduced the first such thing in 2fb330ca723 (packed_delete_refs():\n> implement method, 2017-09-08).\n>\n> However, we seem to have the `MAYBE_UNUSED` macro specifically for such\n> use cases (and use it in four instances as of time of writing). I wonder\n> whether we want to settle one one strategy instead of keeping both?\n\nOoh, MAYBE_UNUSED, I like it. Much more self-documenting. I'm\nsending another round to address Derrick's comment, so I'll include\nthis change while at it.\n"},{"id":"412371","messageId":"dcf28565ad35729a0c5a755689ab47185bf56ccd.1608139034.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v3.git.1608139034.gitgitgadget@gmail.com","subject":"[PATCH v3 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T17:17:12Z","receivedAt":"2020-12-16T17:18:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn a subsequent commit, we will implement the traditional recursiveness\nthat gave merge-recursive its name, namely merging non-unique\nmerge-bases to come up with a single virtual merge base. Copy a few\nhelper functions from merge-recursive.c that we will use in the\nimplementation.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 32 ++++++++++++++++++++++++++++++++\n 1 file changed, 32 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 414e7b7eeac..b66f8a6f100 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,8 +17,10 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"alloc.h\"\n #include \"blob.h\"\n #include \"cache-tree.h\"\n+#include \"commit.h\"\n #include \"commit-reach.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n@@ -1348,6 +1350,36 @@ void merge_finalize(struct merge_options *opt,\n \n /*** Function Grouping: helper functions for merge_incore_*() ***/\n \n+static inline void set_commit_tree(struct commit *c, struct tree *t)\n+{\n+\tc->maybe_tree = t;\n+}\n+\n+MAYBE_UNUSED\n+static struct commit *make_virtual_commit(struct repository *repo,\n+\t\t\t\t\t struct tree *tree,\n+\t\t\t\t\t const char *comment)\n+{\n+\tstruct commit *commit = alloc_commit_node(repo);\n+\n+\tset_merge_remote_desc(commit, comment, (struct object *)commit);\n+\tset_commit_tree(commit, tree);\n+\tcommit->object.parsed = 1;\n+\treturn commit;\n+}\n+\n+MAYBE_UNUSED\n+static struct commit_list *reverse_commit_list(struct commit_list *list)\n+{\n+\tstruct commit_list *previous = NULL, *current, *backup;\n+\tfor (current = list; current; current = backup) {\n+\t\tbackup = current->next;\n+\t\tcurrent->next = previous;\n+\t\tprevious = current;\n+\t}\n+\treturn previous;\n+}\n+\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n \t/* Sanity checks on opt */\n-- \ngitgitgadget\n\n"},{"id":"412372","messageId":"bffc45c6570774dcf4a74fe20b0aef3780ea8cde.1608139034.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v3.git.1608139034.gitgitgadget@gmail.com","subject":"[PATCH v3 2/3] merge-ort: make clear_internal_opts() aware of partial clearing","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T17:17:13Z","receivedAt":"2020-12-16T17:18:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to handle recursive merges, after merging merge-bases we need\nto clear away most of the data we had built up but some of it needs to\nbe kept -- in particular the \"output\" field. Rename the function to\nreflect its future change in use.\n\nFurther, since \"reinitialize\" means we'll be reusing the fields\nimmediately, take advantage of this to only partially clear maps,\nleaving the hashtable allocated and pre-sized. (This may be slightly\nout-of-order since the speedups aren't realized until there are far\nmore strmaps in use, but the patch submission process already went out\nof order because of various questions and requests for strmap. Anyway,\nsee commit 6ccdfc2a20 (\"strmap: enable faster clearing and reusing of\nstrmaps\", 2020-11-05), for performance details about the use of\nstrmap_partial_clear().)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b66f8a6f100..7679c1d08e2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -253,10 +253,11 @@ static void free_strmap_strings(struct strmap *map)\n \t}\n }\n \n-static void clear_internal_opts(struct merge_options_internal *opti,\n-\t\t\t\tint reinitialize)\n+static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n+\t\t\t\t\t int reinitialize)\n {\n-\tassert(!reinitialize);\n+\tvoid (*strmap_func)(struct strmap *, int) =\n+\t\treinitialize ? strmap_partial_clear : strmap_clear;\n \n \t/*\n \t * We marked opti->paths with strdup_strings = 0, so that we\n@@ -266,14 +267,14 @@ static void clear_internal_opts(struct merge_options_internal *opti,\n \t * to deallocate them.\n \t */\n \tfree_strmap_strings(&opti->paths);\n-\tstrmap_clear(&opti->paths, 1);\n+\tstrmap_func(&opti->paths, 1);\n \n \t/*\n \t * All keys and values in opti->conflicted are a subset of those in\n \t * opti->paths. We don't want to deallocate anything twice, so we\n \t * don't free the keys and we pass 0 for free_values.\n \t */\n-\tstrmap_clear(&opti->conflicted, 0);\n+\tstrmap_func(&opti->conflicted, 0);\n \n \t/*\n \t * opti->paths_to_free is similar to opti->paths; we created it with\n@@ -1344,7 +1345,7 @@ void merge_finalize(struct merge_options *opt,\n \n \tassert(opt->priv == NULL);\n \n-\tclear_internal_opts(opti, 0);\n+\tclear_or_reinit_internal_opts(opti, 0);\n \tFREE_AND_NULL(opti);\n }\n \n-- \ngitgitgadget\n\n"},{"id":"412373","messageId":"pull.814.v3.git.1608139034.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v2.git.1608097965.gitgitgadget@gmail.com","subject":"[PATCH v3 0/3] merge-ort: implement recursive merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T17:17:11Z","receivedAt":"2020-12-16T17:18:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-2 (it does NOT depend on en/merge-ort-3\nand can thus be reviewed/merged independently of it).\n\nThis short series adds handling of recursive merges (merging of multiple\nmerge-bases to create a virtual merge base) to merge-ort. With this short\nseries the number of test failures under GIT_TEST_MERGE_ALGORITHM=ort drops\nby 801 (from 1448 to 647).\n\nChanges since v2:\n\n * rename local var from 'next' to 'previous' to make reversing logic\n clearer (as suggested by Stolee)\n * employ MAYBE_UNUSED modifier on new functions as better way to avoid\n unused-function errors (as suggested by Johannes)\n\nElijah Newren (3):\n merge-ort: copy a few small helper functions from merge-recursive.c\n merge-ort: make clear_internal_opts() aware of partial clearing\n merge-ort: implement merge_incore_recursive()\n\n merge-ort.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++---\n merge-ort.h | 10 ++++\n 2 files changed, 152 insertions(+), 7 deletions(-)\n\n\nbase-commit: c5a6f65527aa3b6f5d7cf25437a88d8727ab0646\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-814%2Fnewren%2Fort-recursive-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-814/newren/ort-recursive-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/814\n\nRange-diff vs v2:\n\n 1: 0b455bd6fe7 ! 1: dcf28565ad3 merge-ort: copy a few small helper functions from merge-recursive.c\n @@ merge-ort.c: void merge_finalize(struct merge_options *opt,\n +\tc->maybe_tree = t;\n +}\n +\n ++MAYBE_UNUSED\n +static struct commit *make_virtual_commit(struct repository *repo,\n +\t\t\t\t\t struct tree *tree,\n +\t\t\t\t\t const char *comment)\n @@ merge-ort.c: void merge_finalize(struct merge_options *opt,\n +\treturn commit;\n +}\n +\n ++MAYBE_UNUSED\n +static struct commit_list *reverse_commit_list(struct commit_list *list)\n +{\n -+\tstruct commit_list *next = NULL, *current, *backup;\n ++\tstruct commit_list *previous = NULL, *current, *backup;\n +\tfor (current = list; current; current = backup) {\n +\t\tbackup = current->next;\n -+\t\tcurrent->next = next;\n -+\t\tnext = current;\n ++\t\tcurrent->next = previous;\n ++\t\tprevious = current;\n +\t}\n -+\treturn next;\n ++\treturn previous;\n +}\n +\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n \t/* Sanity checks on opt */\n -@@ merge-ort.c: void merge_incore_recursive(struct merge_options *opt,\n - \t\t\t struct commit *side2,\n - \t\t\t struct merge_result *result)\n - {\n -+\t(void)reverse_commit_list;\n -+\t(void)make_virtual_commit;\n - \tdie(\"Not yet implemented\");\n - }\n 2: fc26c1a11db = 2: bffc45c6570 merge-ort: make clear_internal_opts() aware of partial clearing\n 3: d8f79450a40 ! 3: 59216a155ae merge-ort: implement merge_incore_recursive()\n @@ Commit message\n Signed-off-by: Elijah Newren \n \n ## merge-ort.c ##\n +@@ merge-ort.c: static inline void set_commit_tree(struct commit *c, struct tree *t)\n + \tc->maybe_tree = t;\n + }\n + \n +-MAYBE_UNUSED\n + static struct commit *make_virtual_commit(struct repository *repo,\n + \t\t\t\t\t struct tree *tree,\n + \t\t\t\t\t const char *comment)\n +@@ merge-ort.c: static struct commit *make_virtual_commit(struct repository *repo,\n + \treturn commit;\n + }\n + \n +-MAYBE_UNUSED\n + static struct commit_list *reverse_commit_list(struct commit_list *list)\n + {\n + \tstruct commit_list *previous = NULL, *current, *backup;\n @@ merge-ort.c: static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n @@ merge-ort.c: void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n --\t(void)reverse_commit_list;\n --\t(void)make_virtual_commit;\n -\tdie(\"Not yet implemented\");\n +\t/*\n +\t * merge_incore_nonrecursive() exists for cases where we always\n\n-- \ngitgitgadget\n"},{"id":"412374","messageId":"59216a155ae4f17b959b646e484dfe4a6038751d.1608139034.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v3.git.1608139034.gitgitgadget@gmail.com","subject":"[PATCH v3 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T17:17:14Z","receivedAt":"2020-12-16T17:18:13Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nImplement merge_incore_recursive(), mostly through the use of a new\nhelper function, merge_ort_internal(), which itself is based off\nmerge_recursive_internal() from merge-recursive.c.\n\nThis drops the number of failures in the testsuite when run under\nGIT_TEST_MERGE_ALGORITHM=ort from around 1500 to 647.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++--\n merge-ort.h | 10 +++++\n 2 files changed, 115 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 7679c1d08e2..f01307f2ee0 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1356,7 +1356,6 @@ static inline void set_commit_tree(struct commit *c, struct tree *t)\n \tc->maybe_tree = t;\n }\n \n-MAYBE_UNUSED\n static struct commit *make_virtual_commit(struct repository *repo,\n \t\t\t\t\t struct tree *tree,\n \t\t\t\t\t const char *comment)\n@@ -1369,7 +1368,6 @@ static struct commit *make_virtual_commit(struct repository *repo,\n \treturn commit;\n }\n \n-MAYBE_UNUSED\n static struct commit_list *reverse_commit_list(struct commit_list *list)\n {\n \tstruct commit_list *previous = NULL, *current, *backup;\n@@ -1478,6 +1476,91 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n \n+/*\n+ * Originally from merge_recursive_internal(); somewhat adapted, though.\n+ */\n+static void merge_ort_internal(struct merge_options *opt,\n+\t\t\t struct commit_list *merge_bases,\n+\t\t\t struct commit *h1,\n+\t\t\t struct commit *h2,\n+\t\t\t struct merge_result *result)\n+{\n+\tstruct commit_list *iter;\n+\tstruct commit *merged_merge_bases;\n+\tconst char *ancestor_name;\n+\tstruct strbuf merge_base_abbrev = STRBUF_INIT;\n+\n+\tif (!merge_bases) {\n+\t\tmerge_bases = get_merge_bases(h1, h2);\n+\t\t/* See merge-ort.h:merge_incore_recursive() declaration NOTE */\n+\t\tmerge_bases = reverse_commit_list(merge_bases);\n+\t}\n+\n+\tmerged_merge_bases = pop_commit(&merge_bases);\n+\tif (merged_merge_bases == NULL) {\n+\t\t/* if there is no common ancestor, use an empty tree */\n+\t\tstruct tree *tree;\n+\n+\t\ttree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n+\t\t\t\t\t\t\t \"ancestor\");\n+\t\tancestor_name = \"empty tree\";\n+\t} else if (opt->ancestor && !opt->priv->call_depth) {\n+\t\tancestor_name = opt->ancestor;\n+\t} else if (merge_bases) {\n+\t\tancestor_name = \"merged common ancestors\";\n+\t} else {\n+\t\tstrbuf_add_unique_abbrev(&merge_base_abbrev,\n+\t\t\t\t\t &merged_merge_bases->object.oid,\n+\t\t\t\t\t DEFAULT_ABBREV);\n+\t\tancestor_name = merge_base_abbrev.buf;\n+\t}\n+\n+\tfor (iter = merge_bases; iter; iter = iter->next) {\n+\t\tconst char *saved_b1, *saved_b2;\n+\t\tstruct commit *prev = merged_merge_bases;\n+\n+\t\topt->priv->call_depth++;\n+\t\t/*\n+\t\t * When the merge fails, the result contains files\n+\t\t * with conflict markers. The cleanness flag is\n+\t\t * ignored (unless indicating an error), it was never\n+\t\t * actually used, as result of merge_trees has always\n+\t\t * overwritten it: the committed \"conflicts\" were\n+\t\t * already resolved.\n+\t\t */\n+\t\tsaved_b1 = opt->branch1;\n+\t\tsaved_b2 = opt->branch2;\n+\t\topt->branch1 = \"Temporary merge branch 1\";\n+\t\topt->branch2 = \"Temporary merge branch 2\";\n+\t\tmerge_ort_internal(opt, NULL, prev, iter->item, result);\n+\t\tif (result->clean < 0)\n+\t\t\treturn;\n+\t\topt->branch1 = saved_b1;\n+\t\topt->branch2 = saved_b2;\n+\t\topt->priv->call_depth--;\n+\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo,\n+\t\t\t\t\t\t\t result->tree,\n+\t\t\t\t\t\t\t \"merged tree\");\n+\t\tcommit_list_insert(prev, &merged_merge_bases->parents);\n+\t\tcommit_list_insert(iter->item,\n+\t\t\t\t &merged_merge_bases->parents->next);\n+\n+\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n+\t}\n+\n+\topt->ancestor = ancestor_name;\n+\tmerge_ort_nonrecursive_internal(opt,\n+\t\t\t\t\trepo_get_commit_tree(opt->repo,\n+\t\t\t\t\t\t\t merged_merge_bases),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h1),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h2),\n+\t\t\t\t\tresult);\n+\tstrbuf_release(&merge_base_abbrev);\n+\topt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n+}\n+\n void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n@@ -1495,5 +1578,24 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n-\tdie(\"Not yet implemented\");\n+\t/*\n+\t * merge_incore_nonrecursive() exists for cases where we always\n+\t * know there is a well-defined single merge base. However,\n+\t * despite a similar structure, merge-recursive.c noted that some\n+\t * callers preferred to call the recursive logic anyway and still\n+\t * set a special name for opt->ancestor that would appear in\n+\t * merge.conflictStyle=diff3 output.\n+\t *\n+\t * git-am was one such example (it wanted to set opt->ancestor to\n+\t * \"constructed merge base\", since it created a fake merge base);\n+\t * it called the recursive merge logic through a special\n+\t * merge_recursive_generic() wrapper.\n+\t *\n+\t * Allow the same kind of special case here.\n+\t */\n+\tint num_merge_bases_is_1 = (merge_bases && !merge_bases->next);\n+\tassert(opt->ancestor == NULL || num_merge_bases_is_1);\n+\n+\tmerge_start(opt, result);\n+\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n }\ndiff --git a/merge-ort.h b/merge-ort.h\nindex 55ae7ee865d..d53a0a339f3 100644\n--- a/merge-ort.h\n+++ b/merge-ort.h\n@@ -34,6 +34,16 @@ struct merge_result {\n /*\n * rename-detecting three-way merge with recursive ancestor consolidation.\n * working tree and index are untouched.\n+ *\n+ * merge_bases will be consumed (emptied) so make a copy if you need it.\n+ *\n+ * NOTE: empirically, the recursive algorithm will perform better if you\n+ * pass the merge_bases in the order of oldest commit to the\n+ * newest[1][2].\n+ *\n+ * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n+ * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n+ * first\", 2006-08-09)\n */\n void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit_list *merge_bases,\n-- \ngitgitgadget\n"},{"id":"412377","messageId":"xmqqim914pfs.fsf@gitster.c.googlers.com","threadId":"54831","inReplyTo":"4a4d9d29-ccba-8d39-a7cd-34b1ba785e22@gmail.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-16T17:43:19Z","receivedAt":"2020-12-16T17:44:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 12/15/2020 12:53 PM, Elijah Newren via GitGitGadget wrote:\n>> From: Elijah Newren \n>> \n>> In a subsequent commit, we will implement the traditional recursiveness\n>> that gave merge-recursive its name, namely merging non-unique\n>> merge-bases to come up with a single virtual merge base. Copy a few\n>> helper functions from merge-recursive.c that we will use in the\n>> implementation.\n>\n> I'm sure these are copies, but...\n>\n>> +static struct commit_list *reverse_commit_list(struct commit_list *list)\n>> +{\n>> +\tstruct commit_list *next = NULL, *current, *backup;\n>> +\tfor (current = list; current; current = backup) {\n>> +\t\tbackup = current->next;\n>> +\t\tcurrent->next = next;\n>> +\t\tnext = current;\n>> +\t}\n>\n> The naming of 'next' seems backwards to me, since it is really\n> the \"previous\" node. Using something like 'previous' makes it\n> clear that you are reversing when you say\n>\n> \tcurrent->next = previous;\n\nHmph. I took \"next\" commit_list as \"list is the original one, and\nnext is the reversed list, the next generation of what we received\".\n\nCalling it \"previous\" feels even more backwards when you view among\nthree \"struct commit_list *\" pointers, one (the one that holds the\neventual return value) is primarily used to denote the resulting\nlist itself, and the other two are used to point individual elements\non the original list.\n\nI wonder if a slightly different codeflow may be easier to follow\n\n\tstruct commit_list *result = NULL;\n\twhile (list) {\n \tstruct commit_list *next = list->next;\n\t\tlist->next = result;\n\t\tresult = list;\n\t\tlist = next;\n\t}\n\treturn result;\n\nif we were to try improving this for readability? \n\nI dunno if it matters too much, though.\n\n"},{"id":"412379","messageId":"xmqqeejp4o8d.fsf@gitster.c.googlers.com","threadId":"54831","inReplyTo":"d8f79450a40e5a91b401ccbbedc7326cfe8a33d6.1608097965.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-16T18:09:22Z","receivedAt":"2020-12-16T18:10:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> +\t/*\n> +\t * merge_incore_nonrecursive() exists for cases where we always\n> +\t * know there is a well-defined single merge base. However,\n> +\t * despite a similar structure, merge-recursive.c noted that some\n> +\t * callers preferred to call the recursive logic anyway and still\n> +\t * set a special name for opt->ancestor that would appear in\n> +\t * merge.conflictStyle=diff3 output.\n\nSorry, I do not understand the comment, especially the \"anyway\"\npart. There is no such thing as nonrecursive variant of\nmerge-recursive, is it? If somebody wanted to perform a merge of\ntwo trees with a designated single common ancestor (\"am -3\" would\nwant to do so using a fabricated tree, \"cherry-pick\" would want to\ndo so using the parent commit of what gets picked), it would be\nnatural to call \"git merge-recursive O -- A B\" if it is a scripted\nPorcelain, or would call merge_recursive() with the single merge\nbase on the merge_bases commit_list parameter if it is written in C,\nI would think.\n\n> +\t * git-am was one such example (it wanted to set opt->ancestor to\n> +\t * \"constructed merge base\", since it created a fake merge base);\n> +\t * it called the recursive merge logic through a special\n> +\t * merge_recursive_generic() wrapper.\n> +\t *\n> +\t * Allow the same kind of special case here.\n> +\t */\n\nIn any case, the mention of \"constructed merge base\" may explain\nvery well why the assert in the previous iteration checked for the\nstring, but it does not seem relevant after the condition changed.\n\n> +\tint num_merge_bases_is_1 = (merge_bases && !merge_bases->next);\n> +\tassert(opt->ancestor == NULL || num_merge_bases_is_1);\n\nThe above comment may have explained why some callers that call the\nmachinery with a single merge base want to use its own diff3 label,\nbut the assert the comment applies to is stricter than that.\n\nIn other words, it is unclear why the caller is forbidden from\ngiving the diff3 label, when the recursive merge needs to synthesize\nthe virtual ancestor using all the given merge bases?\n\nThe answer could be a simple \"opt->ancestor field is managed by the\nrecursive machinery itself when it needs to create virtual ancestor,\nand must start as NULL, but when we do not create virtual ancestor,\nit is allowed to start with any value, as the machinery itself does\nnot assign any new value to the field\", but I cannot read if that is\nthe case from the comments in the patch.\n\n> +\n> +\tmerge_start(opt, result);\n> +\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n> }\n> diff --git a/merge-ort.h b/merge-ort.h\n> index 55ae7ee865d..d53a0a339f3 100644\n> --- a/merge-ort.h\n> +++ b/merge-ort.h\n> @@ -34,6 +34,16 @@ struct merge_result {\n> /*\n> * rename-detecting three-way merge with recursive ancestor consolidation.\n> * working tree and index are untouched.\n> + *\n> + * merge_bases will be consumed (emptied) so make a copy if you need it.\n> + *\n> + * NOTE: empirically, the recursive algorithm will perform better if you\n> + * pass the merge_bases in the order of oldest commit to the\n> + * newest[1][2].\n> + *\n> + * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n> + * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n> + * first\", 2006-08-09)\n> */\n\nI initially thought that this was a bit out-of-place for the comment\nthat explains why the merge bases list gets reversed in the code, but\nit is actually the right place---it guides the callers that hand a\nlist of merge_bases to the function.\n\n> void merge_incore_recursive(struct merge_options *opt,\n> \t\t\t struct commit_list *merge_bases,\n\nThanks.\n"},{"id":"412381","messageId":"CABPp-BFr=1iVY739cfh-1Hp82x-Mny-k4y0f3zZ_YuP3PxiGfQ@mail.gmail.com","threadId":"54831","inReplyTo":"xmqqeejp4o8d.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-16T18:37:41Z","receivedAt":"2020-12-16T18:38:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 16, 2020 at 10:09 AM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > + /*\n> > + * merge_incore_nonrecursive() exists for cases where we always\n> > + * know there is a well-defined single merge base. However,\n> > + * despite a similar structure, merge-recursive.c noted that some\n> > + * callers preferred to call the recursive logic anyway and still\n> > + * set a special name for opt->ancestor that would appear in\n> > + * merge.conflictStyle=diff3 output.\n>\n> Sorry, I do not understand the comment, especially the \"anyway\"\n> part. There is no such thing as nonrecursive variant of\n> merge-recursive, is it? If somebody wanted to perform a merge of\n\nThere is absolutely a nonrecursive variant; it's called merge_trees()\nin merge-recursive.[ch] and merge_incore_nonrecursive() in\nmerge-ort.[ch].\n\nNote that I called out the nonrecursive variant at the beginning of\nthe comment. Perhaps I should have said \"recursive variant\" rather\nthan \"recursive logic\"?\n\n> two trees with a designated single common ancestor (\"am -3\" would\n> want to do so using a fabricated tree, \"cherry-pick\" would want to\n> do so using the parent commit of what gets picked), it would be\n> natural to call \"git merge-recursive O -- A B\" if it is a scripted\n> Porcelain, or would call merge_recursive() with the single merge\n> base on the merge_bases commit_list parameter if it is written in C,\n> I would think.\n\ncherry-pick/sequencer uses merge_trees() or\nmerge_incore_nonrecursive(). In other words, the non-recursive API.\n\ngit-am uses merge_recursive_generic(), a weird wrapper that calls\nmerge_recursive() [whose analogue in merge-ort would be\nmerge_incore_recursive()]. It always passes in exactly one merge\nbase, though. And the label for the \"ancestor\" commit in diff3 output\nwould default to showing some fake commit ID, if it weren't for the\nability to override the ancestor label in that case.\n\n> > + * git-am was one such example (it wanted to set opt->ancestor to\n> > + * \"constructed merge base\", since it created a fake merge base);\n> > + * it called the recursive merge logic through a special\n> > + * merge_recursive_generic() wrapper.\n> > + *\n> > + * Allow the same kind of special case here.\n> > + */\n>\n> In any case, the mention of \"constructed merge base\" may explain\n> very well why the assert in the previous iteration checked for the\n> string, but it does not seem relevant after the condition changed.\n\nSure, the question in the last iteration was \"why check for this\nstring\", but there's a new question with this iteration: who would\npass a special opt->ancestor and with what kind of meaning. Providing\nan example thus provides an answer to that question and gives people\nan easy way to search for more information.\n\n> > + int num_merge_bases_is_1 = (merge_bases && !merge_bases->next);\n> > + assert(opt->ancestor == NULL || num_merge_bases_is_1);\n>\n> The above comment may have explained why some callers that call the\n> machinery with a single merge base want to use its own diff3 label,\n> but the assert the comment applies to is stricter than that.\n>\n> In other words, it is unclear why the caller is forbidden from\n> giving the diff3 label, when the recursive merge needs to synthesize\n> the virtual ancestor using all the given merge bases?\n>\n> The answer could be a simple \"opt->ancestor field is managed by the\n> recursive machinery itself when it needs to create virtual ancestor,\n> and must start as NULL, but when we do not create virtual ancestor,\n> it is allowed to start with any value, as the machinery itself does\n> not assign any new value to the field\", but I cannot read if that is\n> the case from the comments in the patch.\n\nYeah, you're making me lean towards thinking that\nmerge_recursive_generic() is just a broken API that I shouldn't port\nover (even as a wrapper), and that I further shouldn't support using\nthe merge_ort_recursive() API in a fashion wanted by that function.\n\nI'll just toss the single-merge-base check along with the laborious comment.\n\nTo clarify, though, your comment above is mostly correct but is off in\nthe case where there is no need to create a virtual ancestor.\nmerge_incore_recursive() does assign a label in that case (if one is\nnot already assigned) -- and that label is just a unique abbreviation\nof the relevant commit. That's a great label when the merge base is a\n\"real\" commit, less so when it's fake/constructed.\n\nBut we already have a merge_incore_nonrecursive() that allows (in\nfact, requires) setting the ancestor label, so we should probably just\nshift merge_recursive_generic() callers who have a special ancestor to\ngo through that API instead.\n\n> > +\n> > + merge_start(opt, result);\n> > + merge_ort_internal(opt, merge_bases, side1, side2, result);\n> > }\n> > diff --git a/merge-ort.h b/merge-ort.h\n> > index 55ae7ee865d..d53a0a339f3 100644\n> > --- a/merge-ort.h\n> > +++ b/merge-ort.h\n> > @@ -34,6 +34,16 @@ struct merge_result {\n> > /*\n> > * rename-detecting three-way merge with recursive ancestor consolidation.\n> > * working tree and index are untouched.\n> > + *\n> > + * merge_bases will be consumed (emptied) so make a copy if you need it.\n> > + *\n> > + * NOTE: empirically, the recursive algorithm will perform better if you\n> > + * pass the merge_bases in the order of oldest commit to the\n> > + * newest[1][2].\n> > + *\n> > + * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n> > + * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n> > + * first\", 2006-08-09)\n> > */\n>\n> I initially thought that this was a bit out-of-place for the comment\n> that explains why the merge bases list gets reversed in the code, but\n> it is actually the right place---it guides the callers that hand a\n> list of merge_bases to the function.\n>\n> > void merge_incore_recursive(struct merge_options *opt,\n> > struct commit_list *merge_bases,\n>\n> Thanks.\n"},{"id":"412419","messageId":"5fda57fa7bfd1_74ba20875@natae.notmuch","threadId":"54831","inReplyTo":"xmqqim914pfs.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2020-12-16T18:54:50Z","receivedAt":"2020-12-16T18:55:37Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Junio C Hamano wrote:\n> Derrick Stolee writes:\n> \n> > On 12/15/2020 12:53 PM, Elijah Newren via GitGitGadget wrote:\n> >> From: Elijah Newren \n> >> \n> >> In a subsequent commit, we will implement the traditional recursiveness\n> >> that gave merge-recursive its name, namely merging non-unique\n> >> merge-bases to come up with a single virtual merge base. Copy a few\n> >> helper functions from merge-recursive.c that we will use in the\n> >> implementation.\n> >\n> > I'm sure these are copies, but...\n> >\n> >> +static struct commit_list *reverse_commit_list(struct commit_list *list)\n> >> +{\n> >> +\tstruct commit_list *next = NULL, *current, *backup;\n> >> +\tfor (current = list; current; current = backup) {\n> >> +\t\tbackup = current->next;\n> >> +\t\tcurrent->next = next;\n> >> +\t\tnext = current;\n> >> +\t}\n> >\n> > The naming of 'next' seems backwards to me, since it is really\n> > the \"previous\" node. Using something like 'previous' makes it\n> > clear that you are reversing when you say\n> >\n> > \tcurrent->next = previous;\n> \n> Hmph. I took \"next\" commit_list as \"list is the original one, and\n> next is the reversed list, the next generation of what we received\".\n> \n> Calling it \"previous\" feels even more backwards when you view among\n> three \"struct commit_list *\" pointers, one (the one that holds the\n> eventual return value) is primarily used to denote the resulting\n> list itself, and the other two are used to point individual elements\n> on the original list.\n\nBoth feel awkward to me because to me previous/next are actually current\nin my mind, and we should return current, not previous/next. Plus\nthere's no need for current, we can use list, as your example.\n\nThis is what I came up with:\n\n struct commit_list *current = NULL;\n while (list) {\n struct commit_list *tmp = list->next;\n list->next = current;\n current = list;\n list = tmp;\n }\n return current;\n\nFor completeness I checked how Linux does it, and surprisingly\nllist_reverse_order() is very close to what I came up with:\n\n struct commit_list *new_list = NULL;\n while (list) {\n struct commit_list *tmp = list;\n list = list->next;\n tmp->next = new_list;\n new_list = tmp;\n }\n return new_list;\n\n(obviously translated)\n\nMaybe it's just me, but I find my version easier to read.\n\nCheers.\n\n-- \nFelipe Contreras\n"},{"id":"412423","messageId":"CABPp-BG+_4Dv_+HNgQxW8KNe1q04NwuhRpExeOuc=wLeunsj_w@mail.gmail.com","threadId":"54831","inReplyTo":"xmqqim914pfs.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-16T19:20:45Z","receivedAt":"2020-12-16T19:21:54Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 16, 2020 at 9:43 AM Junio C Hamano wrote:\n>\n> Derrick Stolee writes:\n>\n> > On 12/15/2020 12:53 PM, Elijah Newren via GitGitGadget wrote:\n> >> From: Elijah Newren \n> >>\n> >> In a subsequent commit, we will implement the traditional recursiveness\n> >> that gave merge-recursive its name, namely merging non-unique\n> >> merge-bases to come up with a single virtual merge base. Copy a few\n> >> helper functions from merge-recursive.c that we will use in the\n> >> implementation.\n> >\n> > I'm sure these are copies, but...\n> >\n> >> +static struct commit_list *reverse_commit_list(struct commit_list *list)\n> >> +{\n> >> + struct commit_list *next = NULL, *current, *backup;\n> >> + for (current = list; current; current = backup) {\n> >> + backup = current->next;\n> >> + current->next = next;\n> >> + next = current;\n> >> + }\n> >\n> > The naming of 'next' seems backwards to me, since it is really\n> > the \"previous\" node. Using something like 'previous' makes it\n> > clear that you are reversing when you say\n> >\n> > current->next = previous;\n>\n> Hmph. I took \"next\" commit_list as \"list is the original one, and\n> next is the reversed list, the next generation of what we received\".\n>\n> Calling it \"previous\" feels even more backwards when you view among\n> three \"struct commit_list *\" pointers, one (the one that holds the\n> eventual return value) is primarily used to denote the resulting\n> list itself, and the other two are used to point individual elements\n> on the original list.\n>\n> I wonder if a slightly different codeflow may be easier to follow\n>\n> struct commit_list *result = NULL;\n> while (list) {\n> struct commit_list *next = list->next;\n> list->next = result;\n> result = list;\n> list = next;\n> }\n> return result;\n>\n> if we were to try improving this for readability?\n\nLooks like Felipe also came up with the same version you did (modulo\nthe temporary variable name).\n\n> I dunno if it matters too much, though.\n\nYeah, reverse_commit_list() has been unchanged in merge-recursive.c\nsince its introduction in August of 2006. The function's purpose\nseems obvious from its name, so no one ever needs to look at or modify\nthe implementation. I'm certain I'll never touch it again. So, I\npersonally don't care what the particular implementation is, and I'm\nhappy to take whatever reviewers prefer here.\n\nSince we have three people weighing in with opinions though -- and on\na point that's irrelevant to me -- do you want to make the call here\nJunio?\n\nOtherwise I'll just leave it as-is and not update further.\n"},{"id":"412429","messageId":"dcf28565ad35729a0c5a755689ab47185bf56ccd.1608150919.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v4.git.1608150919.gitgitgadget@gmail.com","subject":"[PATCH v4 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T20:35:17Z","receivedAt":"2020-12-16T20:36:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn a subsequent commit, we will implement the traditional recursiveness\nthat gave merge-recursive its name, namely merging non-unique\nmerge-bases to come up with a single virtual merge base. Copy a few\nhelper functions from merge-recursive.c that we will use in the\nimplementation.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 32 ++++++++++++++++++++++++++++++++\n 1 file changed, 32 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 414e7b7eeac..b66f8a6f100 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,8 +17,10 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"alloc.h\"\n #include \"blob.h\"\n #include \"cache-tree.h\"\n+#include \"commit.h\"\n #include \"commit-reach.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n@@ -1348,6 +1350,36 @@ void merge_finalize(struct merge_options *opt,\n \n /*** Function Grouping: helper functions for merge_incore_*() ***/\n \n+static inline void set_commit_tree(struct commit *c, struct tree *t)\n+{\n+\tc->maybe_tree = t;\n+}\n+\n+MAYBE_UNUSED\n+static struct commit *make_virtual_commit(struct repository *repo,\n+\t\t\t\t\t struct tree *tree,\n+\t\t\t\t\t const char *comment)\n+{\n+\tstruct commit *commit = alloc_commit_node(repo);\n+\n+\tset_merge_remote_desc(commit, comment, (struct object *)commit);\n+\tset_commit_tree(commit, tree);\n+\tcommit->object.parsed = 1;\n+\treturn commit;\n+}\n+\n+MAYBE_UNUSED\n+static struct commit_list *reverse_commit_list(struct commit_list *list)\n+{\n+\tstruct commit_list *previous = NULL, *current, *backup;\n+\tfor (current = list; current; current = backup) {\n+\t\tbackup = current->next;\n+\t\tcurrent->next = previous;\n+\t\tprevious = current;\n+\t}\n+\treturn previous;\n+}\n+\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n \t/* Sanity checks on opt */\n-- \ngitgitgadget\n\n"},{"id":"412430","messageId":"pull.814.v4.git.1608150919.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v3.git.1608139034.gitgitgadget@gmail.com","subject":"[PATCH v4 0/3] merge-ort: implement recursive merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T20:35:16Z","receivedAt":"2020-12-16T20:36:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-2 (it does NOT depend on en/merge-ort-3\nand can thus be reviewed/merged independently of it).\n\nThis short series adds handling of recursive merges (merging of multiple\nmerge-bases to create a virtual merge base) to merge-ort. With this short\nseries the number of test failures under GIT_TEST_MERGE_ALGORITHM=ort drops\nby 801 (from 1448 to 647).\n\nChanges since v3:\n\n * remove the confusing portions of the merge_incore_recursive() API around\n opt->ancestor that were designed to accommodate merge_recursive_generic()\n or some function like it. If that stuff is really needed, we can add it\n later, but it may be better to simply adjust merge_recursive_generic()\n and/or its callers when we get to that point in the porting process.\n\nElijah Newren (3):\n merge-ort: copy a few small helper functions from merge-recursive.c\n merge-ort: make clear_internal_opts() aware of partial clearing\n merge-ort: implement merge_incore_recursive()\n\n merge-ort.c | 132 +++++++++++++++++++++++++++++++++++++++++++++++++---\n merge-ort.h | 10 ++++\n 2 files changed, 135 insertions(+), 7 deletions(-)\n\n\nbase-commit: c5a6f65527aa3b6f5d7cf25437a88d8727ab0646\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-814%2Fnewren%2Fort-recursive-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-814/newren/ort-recursive-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/814\n\nRange-diff vs v3:\n\n 1: dcf28565ad3 = 1: dcf28565ad3 merge-ort: copy a few small helper functions from merge-recursive.c\n 2: bffc45c6570 = 2: bffc45c6570 merge-ort: make clear_internal_opts() aware of partial clearing\n 3: 59216a155ae ! 3: f622d6905d0 merge-ort: implement merge_incore_recursive()\n @@ merge-ort.c: static void merge_ort_nonrecursive_internal(struct merge_options *o\n +\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n +\t\t\t\t\t\t\t \"ancestor\");\n +\t\tancestor_name = \"empty tree\";\n -+\t} else if (opt->ancestor && !opt->priv->call_depth) {\n -+\t\tancestor_name = opt->ancestor;\n +\t} else if (merge_bases) {\n +\t\tancestor_name = \"merged common ancestors\";\n +\t} else {\n @@ merge-ort.c: void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct merge_result *result)\n {\n -\tdie(\"Not yet implemented\");\n -+\t/*\n -+\t * merge_incore_nonrecursive() exists for cases where we always\n -+\t * know there is a well-defined single merge base. However,\n -+\t * despite a similar structure, merge-recursive.c noted that some\n -+\t * callers preferred to call the recursive logic anyway and still\n -+\t * set a special name for opt->ancestor that would appear in\n -+\t * merge.conflictStyle=diff3 output.\n -+\t *\n -+\t * git-am was one such example (it wanted to set opt->ancestor to\n -+\t * \"constructed merge base\", since it created a fake merge base);\n -+\t * it called the recursive merge logic through a special\n -+\t * merge_recursive_generic() wrapper.\n -+\t *\n -+\t * Allow the same kind of special case here.\n -+\t */\n -+\tint num_merge_bases_is_1 = (merge_bases && !merge_bases->next);\n -+\tassert(opt->ancestor == NULL || num_merge_bases_is_1);\n ++\t/* We set the ancestor label based on the merge_bases */\n ++\tassert(opt->ancestor == NULL);\n +\n +\tmerge_start(opt, result);\n +\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n\n-- \ngitgitgadget\n"},{"id":"412431","messageId":"bffc45c6570774dcf4a74fe20b0aef3780ea8cde.1608150919.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v4.git.1608150919.gitgitgadget@gmail.com","subject":"[PATCH v4 2/3] merge-ort: make clear_internal_opts() aware of partial clearing","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T20:35:18Z","receivedAt":"2020-12-16T20:36:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to handle recursive merges, after merging merge-bases we need\nto clear away most of the data we had built up but some of it needs to\nbe kept -- in particular the \"output\" field. Rename the function to\nreflect its future change in use.\n\nFurther, since \"reinitialize\" means we'll be reusing the fields\nimmediately, take advantage of this to only partially clear maps,\nleaving the hashtable allocated and pre-sized. (This may be slightly\nout-of-order since the speedups aren't realized until there are far\nmore strmaps in use, but the patch submission process already went out\nof order because of various questions and requests for strmap. Anyway,\nsee commit 6ccdfc2a20 (\"strmap: enable faster clearing and reusing of\nstrmaps\", 2020-11-05), for performance details about the use of\nstrmap_partial_clear().)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b66f8a6f100..7679c1d08e2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -253,10 +253,11 @@ static void free_strmap_strings(struct strmap *map)\n \t}\n }\n \n-static void clear_internal_opts(struct merge_options_internal *opti,\n-\t\t\t\tint reinitialize)\n+static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n+\t\t\t\t\t int reinitialize)\n {\n-\tassert(!reinitialize);\n+\tvoid (*strmap_func)(struct strmap *, int) =\n+\t\treinitialize ? strmap_partial_clear : strmap_clear;\n \n \t/*\n \t * We marked opti->paths with strdup_strings = 0, so that we\n@@ -266,14 +267,14 @@ static void clear_internal_opts(struct merge_options_internal *opti,\n \t * to deallocate them.\n \t */\n \tfree_strmap_strings(&opti->paths);\n-\tstrmap_clear(&opti->paths, 1);\n+\tstrmap_func(&opti->paths, 1);\n \n \t/*\n \t * All keys and values in opti->conflicted are a subset of those in\n \t * opti->paths. We don't want to deallocate anything twice, so we\n \t * don't free the keys and we pass 0 for free_values.\n \t */\n-\tstrmap_clear(&opti->conflicted, 0);\n+\tstrmap_func(&opti->conflicted, 0);\n \n \t/*\n \t * opti->paths_to_free is similar to opti->paths; we created it with\n@@ -1344,7 +1345,7 @@ void merge_finalize(struct merge_options *opt,\n \n \tassert(opt->priv == NULL);\n \n-\tclear_internal_opts(opti, 0);\n+\tclear_or_reinit_internal_opts(opti, 0);\n \tFREE_AND_NULL(opti);\n }\n \n-- \ngitgitgadget\n\n"},{"id":"412432","messageId":"f622d6905d010544c335baba2d3a5857c2f6fd05.1608150919.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v4.git.1608150919.gitgitgadget@gmail.com","subject":"[PATCH v4 3/3] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T20:35:19Z","receivedAt":"2020-12-16T20:36:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nImplement merge_incore_recursive(), mostly through the use of a new\nhelper function, merge_ort_internal(), which itself is based off\nmerge_recursive_internal() from merge-recursive.c.\n\nThis drops the number of failures in the testsuite when run under\nGIT_TEST_MERGE_ALGORITHM=ort from around 1500 to 647.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n merge-ort.h | 10 ++++++\n 2 files changed, 98 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 7679c1d08e2..d6c0cd36f4c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1356,7 +1356,6 @@ static inline void set_commit_tree(struct commit *c, struct tree *t)\n \tc->maybe_tree = t;\n }\n \n-MAYBE_UNUSED\n static struct commit *make_virtual_commit(struct repository *repo,\n \t\t\t\t\t struct tree *tree,\n \t\t\t\t\t const char *comment)\n@@ -1369,7 +1368,6 @@ static struct commit *make_virtual_commit(struct repository *repo,\n \treturn commit;\n }\n \n-MAYBE_UNUSED\n static struct commit_list *reverse_commit_list(struct commit_list *list)\n {\n \tstruct commit_list *previous = NULL, *current, *backup;\n@@ -1478,6 +1476,89 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n \n+/*\n+ * Originally from merge_recursive_internal(); somewhat adapted, though.\n+ */\n+static void merge_ort_internal(struct merge_options *opt,\n+\t\t\t struct commit_list *merge_bases,\n+\t\t\t struct commit *h1,\n+\t\t\t struct commit *h2,\n+\t\t\t struct merge_result *result)\n+{\n+\tstruct commit_list *iter;\n+\tstruct commit *merged_merge_bases;\n+\tconst char *ancestor_name;\n+\tstruct strbuf merge_base_abbrev = STRBUF_INIT;\n+\n+\tif (!merge_bases) {\n+\t\tmerge_bases = get_merge_bases(h1, h2);\n+\t\t/* See merge-ort.h:merge_incore_recursive() declaration NOTE */\n+\t\tmerge_bases = reverse_commit_list(merge_bases);\n+\t}\n+\n+\tmerged_merge_bases = pop_commit(&merge_bases);\n+\tif (merged_merge_bases == NULL) {\n+\t\t/* if there is no common ancestor, use an empty tree */\n+\t\tstruct tree *tree;\n+\n+\t\ttree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n+\t\t\t\t\t\t\t \"ancestor\");\n+\t\tancestor_name = \"empty tree\";\n+\t} else if (merge_bases) {\n+\t\tancestor_name = \"merged common ancestors\";\n+\t} else {\n+\t\tstrbuf_add_unique_abbrev(&merge_base_abbrev,\n+\t\t\t\t\t &merged_merge_bases->object.oid,\n+\t\t\t\t\t DEFAULT_ABBREV);\n+\t\tancestor_name = merge_base_abbrev.buf;\n+\t}\n+\n+\tfor (iter = merge_bases; iter; iter = iter->next) {\n+\t\tconst char *saved_b1, *saved_b2;\n+\t\tstruct commit *prev = merged_merge_bases;\n+\n+\t\topt->priv->call_depth++;\n+\t\t/*\n+\t\t * When the merge fails, the result contains files\n+\t\t * with conflict markers. The cleanness flag is\n+\t\t * ignored (unless indicating an error), it was never\n+\t\t * actually used, as result of merge_trees has always\n+\t\t * overwritten it: the committed \"conflicts\" were\n+\t\t * already resolved.\n+\t\t */\n+\t\tsaved_b1 = opt->branch1;\n+\t\tsaved_b2 = opt->branch2;\n+\t\topt->branch1 = \"Temporary merge branch 1\";\n+\t\topt->branch2 = \"Temporary merge branch 2\";\n+\t\tmerge_ort_internal(opt, NULL, prev, iter->item, result);\n+\t\tif (result->clean < 0)\n+\t\t\treturn;\n+\t\topt->branch1 = saved_b1;\n+\t\topt->branch2 = saved_b2;\n+\t\topt->priv->call_depth--;\n+\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo,\n+\t\t\t\t\t\t\t result->tree,\n+\t\t\t\t\t\t\t \"merged tree\");\n+\t\tcommit_list_insert(prev, &merged_merge_bases->parents);\n+\t\tcommit_list_insert(iter->item,\n+\t\t\t\t &merged_merge_bases->parents->next);\n+\n+\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n+\t}\n+\n+\topt->ancestor = ancestor_name;\n+\tmerge_ort_nonrecursive_internal(opt,\n+\t\t\t\t\trepo_get_commit_tree(opt->repo,\n+\t\t\t\t\t\t\t merged_merge_bases),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h1),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h2),\n+\t\t\t\t\tresult);\n+\tstrbuf_release(&merge_base_abbrev);\n+\topt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n+}\n+\n void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n@@ -1495,5 +1576,9 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n-\tdie(\"Not yet implemented\");\n+\t/* We set the ancestor label based on the merge_bases */\n+\tassert(opt->ancestor == NULL);\n+\n+\tmerge_start(opt, result);\n+\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n }\ndiff --git a/merge-ort.h b/merge-ort.h\nindex 55ae7ee865d..d53a0a339f3 100644\n--- a/merge-ort.h\n+++ b/merge-ort.h\n@@ -34,6 +34,16 @@ struct merge_result {\n /*\n * rename-detecting three-way merge with recursive ancestor consolidation.\n * working tree and index are untouched.\n+ *\n+ * merge_bases will be consumed (emptied) so make a copy if you need it.\n+ *\n+ * NOTE: empirically, the recursive algorithm will perform better if you\n+ * pass the merge_bases in the order of oldest commit to the\n+ * newest[1][2].\n+ *\n+ * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n+ * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n+ * first\", 2006-08-09)\n */\n void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit_list *merge_bases,\n-- \ngitgitgadget\n"},{"id":"412433","messageId":"xmqqlfdx32ln.fsf@gitster.c.googlers.com","threadId":"54831","inReplyTo":"CABPp-BG+_4Dv_+HNgQxW8KNe1q04NwuhRpExeOuc=wLeunsj_w@mail.gmail.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-16T20:41:56Z","receivedAt":"2020-12-16T20:42:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> I wonder if a slightly different codeflow may be easier to follow\n>>\n>> struct commit_list *result = NULL;\n>> while (list) {\n>> struct commit_list *next = list->next;\n>> list->next = result;\n>> result = list;\n>> list = next;\n>> }\n>> return result;\n>>\n>> if we were to try improving this for readability?\n>\n> Looks like Felipe also came up with the same version you did (modulo\n> the temporary variable name).\n\nFunny if it was sent as a response to the message that already had\nthe same answer...\n\n>> I dunno if it matters too much, though.\n>\n> Yeah, reverse_commit_list() has been unchanged in merge-recursive.c\n> since its introduction in August of 2006. The function's purpose\n> seems obvious from its name, so no one ever needs to look at or modify\n> the implementation. I'm certain I'll never touch it again. So, I\n> personally don't care what the particular implementation is, and I'm\n> happy to take whatever reviewers prefer here.\n>\n> Since we have three people weighing in with opinions though -- and on\n> a point that's irrelevant to me -- do you want to make the call here\n> Junio?\n\nIf I were pressed to give a suggestion, I have two ;-)\n\nI would prefer to see us first find out if all other callers of\nget_merge_bases() _care_ about a particular order of the resulting\nlist. If they do not care [*1*] and if it seems feasible to teach\nget_merge_bases() build its return value reversed already without\ntoo much extra effort, then the commit list reverser can\ndisappear and get_merge_bases() can be fixed to return its commit\nlist in older-to-newer order.\n\nIf the above does not happen, then I'd prefer to see a single commit\nlist reverser in commit.c and have it *shared* between the two merge\nbackends, instead of adding another one in merge-ort.c while leaving\nthe one in merge-recursive.c behind. And the single implementation\ncan be either \"copied from merge-recursive as that may be\nunintuitive or harder to follow but at least we know it is battle\ntested\", or the one we see above. If we were to take the latter, we\nreally need to avoid making stupid mistakes while attempting to\nreplace an existing awkward one with \"simplified\" version, though.\n\nSorry for listing even more work, but since you asked ... ;-)\n\n\n[Footnote]\n\n*1* if those who care actually would benefit if we used\nolder-to-newer order, it would be even better.\n"},{"id":"412436","messageId":"5fda7b2ee79df_8c35208e1@natae.notmuch","threadId":"54831","inReplyTo":"xmqqlfdx32ln.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2020-12-16T21:25:02Z","receivedAt":"2020-12-16T21:25:37Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Junio C Hamano wrote:\n> Elijah Newren writes:\n> \n> > I wonder if a slightly different codeflow may be easier to follow\n> >>\n> >> struct commit_list *result = NULL;\n> >> while (list) {\n> >> struct commit_list *next = list->next;\n> >> list->next = result;\n> >> result = list;\n> >> list = next;\n> >> }\n> >> return result;\n> >>\n> >> if we were to try improving this for readability?\n> >\n> > Looks like Felipe also came up with the same version you did (modulo\n> > the temporary variable name).\n> \n> Funny if it was sent as a response to the message that already had\n> the same answer...\n\nIt's two changes, actually: s/result/current/ and s/next/tmp/.\n\nBut yeah, it's interesting that I used Elijahs's version as a basis and\narrived at virtually the same thing.\n\nCheers.\n\n-- \nFelipe Contreras\n"},{"id":"412437","messageId":"CABPp-BE-EXbJxvJ-dy8SfK3-1rjsM0eKAq1G_vWMfC+A5UTHaQ@mail.gmail.com","threadId":"54831","inReplyTo":"xmqqlfdx32ln.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-16T21:34:40Z","receivedAt":"2020-12-16T21:35:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 16, 2020 at 12:42 PM Junio C Hamano wrote:\n>\n> Elijah Newren writes:\n>\n> > I wonder if a slightly different codeflow may be easier to follow\n> >>\n> >> struct commit_list *result = NULL;\n> >> while (list) {\n> >> struct commit_list *next = list->next;\n> >> list->next = result;\n> >> result = list;\n> >> list = next;\n> >> }\n> >> return result;\n> >>\n> >> if we were to try improving this for readability?\n> >\n> > Looks like Felipe also came up with the same version you did (modulo\n> > the temporary variable name).\n>\n> Funny if it was sent as a response to the message that already had\n> the same answer...\n\n\n>\n> >> I dunno if it matters too much, though.\n> >\n> > Yeah, reverse_commit_list() has been unchanged in merge-recursive.c\n> > since its introduction in August of 2006. The function's purpose\n> > seems obvious from its name, so no one ever needs to look at or modify\n> > the implementation. I'm certain I'll never touch it again. So, I\n> > personally don't care what the particular implementation is, and I'm\n> > happy to take whatever reviewers prefer here.\n> >\n> > Since we have three people weighing in with opinions though -- and on\n> > a point that's irrelevant to me -- do you want to make the call here\n> > Junio?\n>\n> If I were pressed to give a suggestion, I have two ;-)\n>\n> I would prefer to see us first find out if all other callers of\n> get_merge_bases() _care_ about a particular order of the resulting\n> list. If they do not care [*1*] and if it seems feasible to teach\n> get_merge_bases() build its return value reversed already without\n> too much extra effort, then the commit list reverser can\n> disappear and get_merge_bases() can be fixed to return its commit\n> list in older-to-newer order.\n\nThe ones in sequencer.c and builtin/merge.c care about the order, but\nthey manually reverse it (because they are going to call the merge\nmachinery). So, these two would benefit from it being reversed.\nHowever...\n\nnotes-merge.c and submodule.c both have subtle dependencies on the\norder (in ways that might be buggy). They could perhaps be taught to\ndepend on the reversed order, but I'm leery of touching something that\nlooks possibly buggy (one even has a TODO highlighting it) and\nbecoming responsible.\n\nget_octopus_merge_bases() depends on the order from get_merge_bases(),\nand builtin/merge-base.c depends on that function. So, the output\norder of a command depends on it, which might thus affect user\nscripts.\n\nbuiltin/pull.c also depends on the order returned by get_octopus_merge_bases().\n\nThat's enough dependencies that I'm inclined to just leave this side\nof things as they are.\n\n\n> If the above does not happen, then I'd prefer to see a single commit\n> list reverser in commit.c and have it *shared* between the two merge\n> backends, instead of adding another one in merge-ort.c while leaving\n> the one in merge-recursive.c behind. And the single implementation\n> can be either \"copied from merge-recursive as that may be\n> unintuitive or harder to follow but at least we know it is battle\n> tested\", or the one we see above. If we were to take the latter, we\n> really need to avoid making stupid mistakes while attempting to\n> replace an existing awkward one with \"simplified\" version, though.\n\ncommit.c seems like a natural location. I'll insert a patch at the\nbeginning of the series to move the function there, and just use\nJohannes' original version from 2006 as-is -- that'll make it easier\nto verify that my patch is simply moving things, anyway.\n\n> Sorry for listing even more work, but since you asked ... ;-)\n>\n>\n> [Footnote]\n>\n> *1* if those who care actually would benefit if we used\n> older-to-newer order, it would be even better.\n"},{"id":"412441","messageId":"pull.814.v5.git.1608157682.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v4.git.1608150919.gitgitgadget@gmail.com","subject":"[PATCH v5 0/4] merge-ort: implement recursive merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T22:27:58Z","receivedAt":"2020-12-16T22:28:46Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-2 (it does NOT depend on en/merge-ort-3\nand can thus be reviewed/merged independently of it).\n\nThis short series adds handling of recursive merges (merging of multiple\nmerge-bases to create a virtual merge base) to merge-ort. With this short\nseries the number of test failures under GIT_TEST_MERGE_ALGORITHM=ort drops\nby 801 (from 1448 to 647).\n\nChanges since v4:\n\n * add an earlier patch in the series that moves reverse_commit_list(),\n as-is, to commit.c. This also shrinks what is now the second patch.\n\nElijah Newren (4):\n commit: move reverse_commit_list() from merge-recursive\n merge-ort: copy a few small helper functions from merge-recursive.c\n merge-ort: make clear_internal_opts() aware of partial clearing\n merge-ort: implement merge_incore_recursive()\n\n commit.c | 11 +++++\n commit.h | 3 ++\n merge-ort.c | 121 +++++++++++++++++++++++++++++++++++++++++++---\n merge-ort.h | 10 ++++\n merge-recursive.c | 11 -----\n 5 files changed, 138 insertions(+), 18 deletions(-)\n\n\nbase-commit: c5a6f65527aa3b6f5d7cf25437a88d8727ab0646\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-814%2Fnewren%2Fort-recursive-v5\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-814/newren/ort-recursive-v5\nPull-Request: https://github.com/gitgitgadget/git/pull/814\n\nRange-diff vs v4:\n\n -: ----------- > 1: 9052faeabe6 commit: move reverse_commit_list() from merge-recursive\n 1: dcf28565ad3 ! 2: 949741932e5 merge-ort: copy a few small helper functions from merge-recursive.c\n @@ merge-ort.c: void merge_finalize(struct merge_options *opt,\n +\tcommit->object.parsed = 1;\n +\treturn commit;\n +}\n -+\n -+MAYBE_UNUSED\n -+static struct commit_list *reverse_commit_list(struct commit_list *list)\n -+{\n -+\tstruct commit_list *previous = NULL, *current, *backup;\n -+\tfor (current = list; current; current = backup) {\n -+\t\tbackup = current->next;\n -+\t\tcurrent->next = previous;\n -+\t\tprevious = current;\n -+\t}\n -+\treturn previous;\n -+}\n +\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n 2: bffc45c6570 = 3: 3852125c70b merge-ort: make clear_internal_opts() aware of partial clearing\n 3: f622d6905d0 ! 4: 63e30492ccb merge-ort: implement merge_incore_recursive()\n @@ merge-ort.c: static inline void set_commit_tree(struct commit *c, struct tree *t\n static struct commit *make_virtual_commit(struct repository *repo,\n \t\t\t\t\t struct tree *tree,\n \t\t\t\t\t const char *comment)\n -@@ merge-ort.c: static struct commit *make_virtual_commit(struct repository *repo,\n - \treturn commit;\n - }\n - \n --MAYBE_UNUSED\n - static struct commit_list *reverse_commit_list(struct commit_list *list)\n - {\n - \tstruct commit_list *previous = NULL, *current, *backup;\n @@ merge-ort.c: static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n\n-- \ngitgitgadget\n"},{"id":"412442","messageId":"9052faeabe62d9ba1b9bceae0c0f7b1809bd1b60.1608157683.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v5.git.1608157682.gitgitgadget@gmail.com","subject":"[PATCH v5 1/4] commit: move reverse_commit_list() from merge-recursive","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T22:27:59Z","receivedAt":"2020-12-16T22:28:47Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n commit.c | 11 +++++++++++\n commit.h | 3 +++\n merge-recursive.c | 11 -----------\n 3 files changed, 14 insertions(+), 11 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex f53429c0ac3..dc08a47b073 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -563,6 +563,17 @@ struct commit_list *copy_commit_list(struct commit_list *list)\n \treturn head;\n }\n \n+struct commit_list *reverse_commit_list(struct commit_list *list)\n+{\n+\tstruct commit_list *next = NULL, *current, *backup;\n+\tfor (current = list; current; current = backup) {\n+\t\tbackup = current->next;\n+\t\tcurrent->next = next;\n+\t\tnext = current;\n+\t}\n+\treturn next;\n+}\n+\n void free_commit_list(struct commit_list *list)\n {\n \twhile (list)\ndiff --git a/commit.h b/commit.h\nindex 5467786c7be..3e9139a0004 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -177,6 +177,9 @@ void commit_list_sort_by_date(struct commit_list **list);\n /* Shallow copy of the input list */\n struct commit_list *copy_commit_list(struct commit_list *list);\n \n+/* Modify list in-place to reverse it, returning new head; list will be tail */\n+struct commit_list *reverse_commit_list(struct commit_list *list);\n+\n void free_commit_list(struct commit_list *list);\n \n struct rev_info; /* in revision.h, it circularly uses enum cmit_fmt */\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex f736a0f6323..b052974f191 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -3517,17 +3517,6 @@ static int merge_trees_internal(struct merge_options *opt,\n \treturn clean;\n }\n \n-static struct commit_list *reverse_commit_list(struct commit_list *list)\n-{\n-\tstruct commit_list *next = NULL, *current, *backup;\n-\tfor (current = list; current; current = backup) {\n-\t\tbackup = current->next;\n-\t\tcurrent->next = next;\n-\t\tnext = current;\n-\t}\n-\treturn next;\n-}\n-\n /*\n * Merge the commits h1 and h2, returning a flag (int) indicating the\n * cleanness of the merge. Also, if opt->priv->call_depth, create a\n-- \ngitgitgadget\n\n"},{"id":"412443","messageId":"949741932e512ea10e7b2a1e6036eab1c4a02b4c.1608157683.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v5.git.1608157682.gitgitgadget@gmail.com","subject":"[PATCH v5 2/4] merge-ort: copy a few small helper functions from merge-recursive.c","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T22:28:00Z","receivedAt":"2020-12-16T22:28:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn a subsequent commit, we will implement the traditional recursiveness\nthat gave merge-recursive its name, namely merging non-unique\nmerge-bases to come up with a single virtual merge base. Copy a few\nhelper functions from merge-recursive.c that we will use in the\nimplementation.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 20 ++++++++++++++++++++\n 1 file changed, 20 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 414e7b7eeac..6eac0cef491 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,8 +17,10 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"alloc.h\"\n #include \"blob.h\"\n #include \"cache-tree.h\"\n+#include \"commit.h\"\n #include \"commit-reach.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n@@ -1348,6 +1350,24 @@ void merge_finalize(struct merge_options *opt,\n \n /*** Function Grouping: helper functions for merge_incore_*() ***/\n \n+static inline void set_commit_tree(struct commit *c, struct tree *t)\n+{\n+\tc->maybe_tree = t;\n+}\n+\n+MAYBE_UNUSED\n+static struct commit *make_virtual_commit(struct repository *repo,\n+\t\t\t\t\t struct tree *tree,\n+\t\t\t\t\t const char *comment)\n+{\n+\tstruct commit *commit = alloc_commit_node(repo);\n+\n+\tset_merge_remote_desc(commit, comment, (struct object *)commit);\n+\tset_commit_tree(commit, tree);\n+\tcommit->object.parsed = 1;\n+\treturn commit;\n+}\n+\n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n \t/* Sanity checks on opt */\n-- \ngitgitgadget\n\n"},{"id":"412444","messageId":"3852125c70b330fa8835b47c1dd6cd9b8f3ca041.1608157683.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v5.git.1608157682.gitgitgadget@gmail.com","subject":"[PATCH v5 3/4] merge-ort: make clear_internal_opts() aware of partial clearing","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T22:28:01Z","receivedAt":"2020-12-16T22:28:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to handle recursive merges, after merging merge-bases we need\nto clear away most of the data we had built up but some of it needs to\nbe kept -- in particular the \"output\" field. Rename the function to\nreflect its future change in use.\n\nFurther, since \"reinitialize\" means we'll be reusing the fields\nimmediately, take advantage of this to only partially clear maps,\nleaving the hashtable allocated and pre-sized. (This may be slightly\nout-of-order since the speedups aren't realized until there are far\nmore strmaps in use, but the patch submission process already went out\nof order because of various questions and requests for strmap. Anyway,\nsee commit 6ccdfc2a20 (\"strmap: enable faster clearing and reusing of\nstrmaps\", 2020-11-05), for performance details about the use of\nstrmap_partial_clear().)\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 6eac0cef491..bd237f3472e 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -253,10 +253,11 @@ static void free_strmap_strings(struct strmap *map)\n \t}\n }\n \n-static void clear_internal_opts(struct merge_options_internal *opti,\n-\t\t\t\tint reinitialize)\n+static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n+\t\t\t\t\t int reinitialize)\n {\n-\tassert(!reinitialize);\n+\tvoid (*strmap_func)(struct strmap *, int) =\n+\t\treinitialize ? strmap_partial_clear : strmap_clear;\n \n \t/*\n \t * We marked opti->paths with strdup_strings = 0, so that we\n@@ -266,14 +267,14 @@ static void clear_internal_opts(struct merge_options_internal *opti,\n \t * to deallocate them.\n \t */\n \tfree_strmap_strings(&opti->paths);\n-\tstrmap_clear(&opti->paths, 1);\n+\tstrmap_func(&opti->paths, 1);\n \n \t/*\n \t * All keys and values in opti->conflicted are a subset of those in\n \t * opti->paths. We don't want to deallocate anything twice, so we\n \t * don't free the keys and we pass 0 for free_values.\n \t */\n-\tstrmap_clear(&opti->conflicted, 0);\n+\tstrmap_func(&opti->conflicted, 0);\n \n \t/*\n \t * opti->paths_to_free is similar to opti->paths; we created it with\n@@ -1344,7 +1345,7 @@ void merge_finalize(struct merge_options *opt,\n \n \tassert(opt->priv == NULL);\n \n-\tclear_internal_opts(opti, 0);\n+\tclear_or_reinit_internal_opts(opti, 0);\n \tFREE_AND_NULL(opti);\n }\n \n-- \ngitgitgadget\n\n"},{"id":"412445","messageId":"63e30492ccbc6da3b46abc766c98b81ef14996dd.1608157683.git.gitgitgadget@gmail.com","threadId":"54831","inReplyTo":"pull.814.v5.git.1608157682.gitgitgadget@gmail.com","subject":"[PATCH v5 4/4] merge-ort: implement merge_incore_recursive()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-16T22:28:02Z","receivedAt":"2020-12-16T22:28:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nImplement merge_incore_recursive(), mostly through the use of a new\nhelper function, merge_ort_internal(), which itself is based off\nmerge_recursive_internal() from merge-recursive.c.\n\nThis drops the number of failures in the testsuite when run under\nGIT_TEST_MERGE_ALGORITHM=ort from around 1500 to 647.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n merge-ort.h | 10 ++++++\n 2 files changed, 98 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex bd237f3472e..31103d21407 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1356,7 +1356,6 @@ static inline void set_commit_tree(struct commit *c, struct tree *t)\n \tc->maybe_tree = t;\n }\n \n-MAYBE_UNUSED\n static struct commit *make_virtual_commit(struct repository *repo,\n \t\t\t\t\t struct tree *tree,\n \t\t\t\t\t const char *comment)\n@@ -1466,6 +1465,89 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t}\n }\n \n+/*\n+ * Originally from merge_recursive_internal(); somewhat adapted, though.\n+ */\n+static void merge_ort_internal(struct merge_options *opt,\n+\t\t\t struct commit_list *merge_bases,\n+\t\t\t struct commit *h1,\n+\t\t\t struct commit *h2,\n+\t\t\t struct merge_result *result)\n+{\n+\tstruct commit_list *iter;\n+\tstruct commit *merged_merge_bases;\n+\tconst char *ancestor_name;\n+\tstruct strbuf merge_base_abbrev = STRBUF_INIT;\n+\n+\tif (!merge_bases) {\n+\t\tmerge_bases = get_merge_bases(h1, h2);\n+\t\t/* See merge-ort.h:merge_incore_recursive() declaration NOTE */\n+\t\tmerge_bases = reverse_commit_list(merge_bases);\n+\t}\n+\n+\tmerged_merge_bases = pop_commit(&merge_bases);\n+\tif (merged_merge_bases == NULL) {\n+\t\t/* if there is no common ancestor, use an empty tree */\n+\t\tstruct tree *tree;\n+\n+\t\ttree = lookup_tree(opt->repo, opt->repo->hash_algo->empty_tree);\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo, tree,\n+\t\t\t\t\t\t\t \"ancestor\");\n+\t\tancestor_name = \"empty tree\";\n+\t} else if (merge_bases) {\n+\t\tancestor_name = \"merged common ancestors\";\n+\t} else {\n+\t\tstrbuf_add_unique_abbrev(&merge_base_abbrev,\n+\t\t\t\t\t &merged_merge_bases->object.oid,\n+\t\t\t\t\t DEFAULT_ABBREV);\n+\t\tancestor_name = merge_base_abbrev.buf;\n+\t}\n+\n+\tfor (iter = merge_bases; iter; iter = iter->next) {\n+\t\tconst char *saved_b1, *saved_b2;\n+\t\tstruct commit *prev = merged_merge_bases;\n+\n+\t\topt->priv->call_depth++;\n+\t\t/*\n+\t\t * When the merge fails, the result contains files\n+\t\t * with conflict markers. The cleanness flag is\n+\t\t * ignored (unless indicating an error), it was never\n+\t\t * actually used, as result of merge_trees has always\n+\t\t * overwritten it: the committed \"conflicts\" were\n+\t\t * already resolved.\n+\t\t */\n+\t\tsaved_b1 = opt->branch1;\n+\t\tsaved_b2 = opt->branch2;\n+\t\topt->branch1 = \"Temporary merge branch 1\";\n+\t\topt->branch2 = \"Temporary merge branch 2\";\n+\t\tmerge_ort_internal(opt, NULL, prev, iter->item, result);\n+\t\tif (result->clean < 0)\n+\t\t\treturn;\n+\t\topt->branch1 = saved_b1;\n+\t\topt->branch2 = saved_b2;\n+\t\topt->priv->call_depth--;\n+\n+\t\tmerged_merge_bases = make_virtual_commit(opt->repo,\n+\t\t\t\t\t\t\t result->tree,\n+\t\t\t\t\t\t\t \"merged tree\");\n+\t\tcommit_list_insert(prev, &merged_merge_bases->parents);\n+\t\tcommit_list_insert(iter->item,\n+\t\t\t\t &merged_merge_bases->parents->next);\n+\n+\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n+\t}\n+\n+\topt->ancestor = ancestor_name;\n+\tmerge_ort_nonrecursive_internal(opt,\n+\t\t\t\t\trepo_get_commit_tree(opt->repo,\n+\t\t\t\t\t\t\t merged_merge_bases),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h1),\n+\t\t\t\t\trepo_get_commit_tree(opt->repo, h2),\n+\t\t\t\t\tresult);\n+\tstrbuf_release(&merge_base_abbrev);\n+\topt->ancestor = NULL; /* avoid accidental re-use of opt->ancestor */\n+}\n+\n void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n@@ -1483,5 +1565,9 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n-\tdie(\"Not yet implemented\");\n+\t/* We set the ancestor label based on the merge_bases */\n+\tassert(opt->ancestor == NULL);\n+\n+\tmerge_start(opt, result);\n+\tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n }\ndiff --git a/merge-ort.h b/merge-ort.h\nindex 55ae7ee865d..d53a0a339f3 100644\n--- a/merge-ort.h\n+++ b/merge-ort.h\n@@ -34,6 +34,16 @@ struct merge_result {\n /*\n * rename-detecting three-way merge with recursive ancestor consolidation.\n * working tree and index are untouched.\n+ *\n+ * merge_bases will be consumed (emptied) so make a copy if you need it.\n+ *\n+ * NOTE: empirically, the recursive algorithm will perform better if you\n+ * pass the merge_bases in the order of oldest commit to the\n+ * newest[1][2].\n+ *\n+ * [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.1907252055500.21907@tvgsbejvaqbjf.bet/\n+ * [2] commit 8918b0c9c2 (\"merge-recur: try to merge older merge bases\n+ * first\", 2006-08-09)\n */\n void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit_list *merge_bases,\n-- \ngitgitgadget\n"},{"id":"412489","messageId":"ed765c96-2c19-d5b3-3712-bd6f92eb9b75@gmail.com","threadId":"54831","inReplyTo":"9052faeabe62d9ba1b9bceae0c0f7b1809bd1b60.1608157683.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v5 1/4] commit: move reverse_commit_list() from merge-recursive","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-17T14:03:49Z","receivedAt":"2020-12-17T14:04:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/16/2020 5:27 PM, Elijah Newren via GitGitGadget wrote:\n> +struct commit_list *reverse_commit_list(struct commit_list *list)\n> +{\n> +\tstruct commit_list *next = NULL, *current, *backup;\n> +\tfor (current = list; current; current = backup) {\n> +\t\tbackup = current->next;\n> +\t\tcurrent->next = next;\n> +\t\tnext = current;\n> +\t}\n> +\treturn next;\n> +}\n> +\n\nI followed the discussion about the variable names in\nthe earlier thread, and I certainly did not meant to\nstir a controversy. I think this approach of deduplicating\nbut keeping an exact copy is the best solution.\n\nThanks,\n-Stolee\n"}]}