{"thread":{"id":"35580","subject":"[PATCH 1/2] merge-base: fix duplicates and not best ancestors in output","startedAt":"2013-12-28T10:22:26Z","lastAt":"2013-12-31T11:15:56Z","messageCount":4,"participants":["Василий Макаров","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"232474","messageId":"CABEtfDFu=Fc0SXbyFctEyiMCJwqxP25K9mdVhAB0X_vKHxvW_A@mail.gmail.com","threadId":"35580","inReplyTo":null,"subject":"[PATCH 1/2] merge-base: fix duplicates and not best ancestors in output","fromName":"Василий Макаров","fromEmail":"einmalfel@gmail.com","sentAt":"2013-12-28T10:22:26Z","receivedAt":"2013-12-28T10:22:26Z","isPatch":true,"sender":{"key":"einmalfel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2640813?v=4"},"body":"Hi there!\nFirst of all: I'm new to mailing-lists, sorry if I'm doing it wrong.\n\nI've found a bug in git merge-base, causing it to show not best common\nancestors and duplicates under some circumstances (example is given in\nattached test case).\nProblem cause is algorithm used in get_octopus_merge_bases(), it\niteratively concatenates merge bases, and don't care if there are\nduplicates or decsendants/ancestors in result.\nWhat I suggest as a solution is to simply reduce bases list after\nget_octopus_merge_bases().\n\nHere is the fix:\n\n---\n builtin/merge-base.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex e88eb93..d6ad330 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -44,19 +44,19 @@ static struct commit *get_commit_reference(const char\n*arg)\n return r;\n }\n\n-static int handle_octopus(int count, const char **args, int reduce, int\nshow_all)\n+static int handle_octopus(int count, const char **args, int reduce_only,\nint show_all)\n {\n struct commit_list *revs = NULL;\n struct commit_list *result;\n int i;\n\n- if (reduce)\n+ if (reduce_only)\n show_all = 1;\n\n for (i = count - 1; i >= 0; i--)\n commit_list_insert(get_commit_reference(args[i]), &revs);\n\n- result = reduce ? reduce_heads(revs) : get_octopus_merge_bases(revs);\n+ result = reduce_heads(reduce_only ? revs : get_octopus_merge_bases(revs));\n\n if (!result)\n return 1;\n-- \n1.8.3.1\n"},{"id":"232517","messageId":"xmqqppoerwnm.fsf@gitster.dls.corp.google.com","threadId":"35580","inReplyTo":"CABEtfDFu=Fc0SXbyFctEyiMCJwqxP25K9mdVhAB0X_vKHxvW_A@mail.gmail.com","subject":"Re: [PATCH 1/2] merge-base: fix duplicates and not best ancestors in output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-12-30T19:01:01Z","receivedAt":"2013-12-30T19:01:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Василий Макаров writes:\n\n> Hi there!\n> First of all: I'm new to mailing-lists, sorry if I'm doing it wrong.\n>\n> I've found a bug in git merge-base, causing it to show not best common\n> ancestors and duplicates under some circumstances (example is given in\n> attached test case).\n\nAttached???\n\n> Problem cause is algorithm used in get_octopus_merge_bases(), it\n> iteratively concatenates merge bases, and don't care if there are\n> duplicates or decsendants/ancestors in result.\n> What I suggest as a solution is to simply reduce bases list after\n> get_octopus_merge_bases().\n\nI do not offhand remember if it was deliberate that we do not dedup\nthe result from the underlying get_octopus_merge_bases() (the most\nlikely reason for not deduping is because the caller is expected to\ndo that if it wants to).\n\nWhether it is an improvement to force deduping here or it is an\nregression to do so, I think we should split that helper function\nhandle_octopus(). It does two totally unrelated things (one is only\nto list independent heads without showing merge bases, the other is\nto show one or more merge bases across all the heads given).\nPerhaps if we split the \"independent\" codepath introduced by\na1e0ad78 (merge-base --independent to print reduced parent list in a\nmerge, 2010-08-17) into its own helper function, like this, it would\nmake it clear what is going on.\n\nThanks.\n\n builtin/merge-base.c | 31 +++++++++++++++++++++++++------\n 1 file changed, 25 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex e88eb93..a00e8f5 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -44,19 +44,36 @@ static struct commit *get_commit_reference(const char *arg)\n \treturn r;\n }\n \n-static int handle_octopus(int count, const char **args, int reduce, int show_all)\n+static int handle_independent(int count, const char **args)\n {\n \tstruct commit_list *revs = NULL;\n \tstruct commit_list *result;\n \tint i;\n \n-\tif (reduce)\n-\t\tshow_all = 1;\n+\tfor (i = count - 1; i >= 0; i--)\n+\t\tcommit_list_insert(get_commit_reference(args[i]), &revs);\n+\n+\tresult = reduce_heads(revs);\n+\tif (!result)\n+\t\treturn 1;\n+\n+\twhile (result) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(result->item->object.sha1));\n+\t\tresult = result->next;\n+\t}\n+\treturn 0;\n+}\n+\n+static int handle_octopus(int count, const char **args, int show_all)\n+{\n+\tstruct commit_list *revs = NULL;\n+\tstruct commit_list *result;\n+\tint i;\n \n \tfor (i = count - 1; i >= 0; i--)\n \t\tcommit_list_insert(get_commit_reference(args[i]), &revs);\n \n-\tresult = reduce ? reduce_heads(revs) : get_octopus_merge_bases(revs);\n+\tresult = get_octopus_merge_bases(revs);\n \n \tif (!result)\n \t\treturn 1;\n@@ -114,8 +131,10 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)\n \tif (reduce && (show_all || octopus))\n \t\tdie(\"--independent cannot be used with other options\");\n \n-\tif (octopus || reduce)\n-\t\treturn handle_octopus(argc, argv, reduce, show_all);\n+\tif (octopus)\n+\t\treturn handle_octopus(argc, argv, show_all);\n+\telse if (reduce)\n+\t\treturn handle_independent(argc, argv);\n \n \trev = xmalloc(argc * sizeof(*rev));\n \twhile (argc-- > 0)\n"},{"id":"232524","messageId":"xmqqy532qf23.fsf@gitster.dls.corp.google.com","threadId":"35580","inReplyTo":"xmqqppoerwnm.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 1/2] merge-base: fix duplicates and not best ancestors in output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-12-30T20:06:28Z","receivedAt":"2013-12-30T20:06:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I do not offhand remember if it was deliberate that we do not dedup\n> the result from the underlying get_octopus_merge_bases() (the most\n> likely reason for not deduping is because the caller is expected to\n> do that if it wants to).\n>\n> Whether it is an improvement to force deduping here or it is an\n> regression to do so, I think we should split that helper function\n> handle_octopus(). It does two totally unrelated things (one is only\n> to list independent heads without showing merge bases, the other is\n> to show one or more merge bases across all the heads given).\n> Perhaps if we split the \"independent\" codepath introduced by\n> a1e0ad78 (merge-base --independent to print reduced parent list in a\n> merge, 2010-08-17) into its own helper function, like this, it would\n> make it clear what is going on.\n\nAnd assuming that deduping is the right thing to do here, here is a\nfollow-up on top of the spliting patch.\n\n-- >8 --\nSubject: [PATCH] merge-base --octopus: reduce the result from get_octopus_merge_bases()\n\nScripts that use \"merge-base --octopus\" could do the reducing\nthemselves, but most of them are expected to want to get the reduced\nresults without having to do any work themselves.\n\nTests are taken from a message by Василий Макаров\n\n\nSigned-off-by: Junio C Hamano \n---\n\n We might want to vet the existing callers of the underlying\n get_octopus_merge_bases() and find out if _all_ of them are doing\n anything extra (like deduping) because the machinery can return\n duplicate results. And if that is the case, then we may want to\n move the dedupling down the callchain instead of having it here.\n\n builtin/merge-base.c | 2 +-\n t/t6010-merge-base.sh | 39 +++++++++++++++++++++++++++++++++++++++\n 2 files changed, 40 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/merge-base.c b/builtin/merge-base.c\nindex daa96c7..87f4dbc 100644\n--- a/builtin/merge-base.c\n+++ b/builtin/merge-base.c\n@@ -73,7 +73,7 @@ static int handle_octopus(int count, const char **args, int show_all)\n \tfor (i = count - 1; i >= 0; i--)\n \t\tcommit_list_insert(get_commit_reference(args[i]), &revs);\n \n-\tresult = get_octopus_merge_bases(revs);\n+\tresult = reduce_heads(get_octopus_merge_bases(revs));\n \n \tif (!result)\n \t\treturn 1;\ndiff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\nindex f80bba8..abb5728 100755\n--- a/t/t6010-merge-base.sh\n+++ b/t/t6010-merge-base.sh\n@@ -230,4 +230,43 @@ test_expect_success 'criss-cross merge-base for octopus-step' '\n \ttest_cmp expected.sorted actual.sorted\n '\n \n+test_expect_success 'merge-base --octopus --all for complex tree' '\n+\t# Best common ancestor for JE, JAA and JDD is JC\n+\t# JE\n+\t# / |\n+\t# / |\n+\t# / |\n+\t# JAA / |\n+\t# |\\ / |\n+\t# | \\ | JDD |\n+\t# | \\ |/ | |\n+\t# | JC JD |\n+\t# | | /| |\n+\t# | |/ | |\n+\t# JA | | |\n+\t# |\\ /| | |\n+\t# X JB | X X\n+\t# \\ \\ | / /\n+\t# \\__\\|/___/\n+\t# J\n+\ttest_commit J &&\n+\ttest_commit JB &&\n+\tgit reset --hard J &&\n+\ttest_commit JC &&\n+\tgit reset --hard J &&\n+\ttest_commit JTEMP1 &&\n+\ttest_merge JA JB &&\n+\ttest_merge JAA JC &&\n+\tgit reset --hard J &&\n+\ttest_commit JTEMP2 &&\n+\ttest_merge JD JB &&\n+\ttest_merge JDD JC &&\n+\tgit reset --hard J &&\n+\ttest_commit JTEMP3 &&\n+\ttest_merge JE JC &&\n+\tgit rev-parse JC >expected &&\n+\tgit merge-base --all --octopus JAA JDD JE >actual &&\n+\ttest_cmp expected actual\n+'\n+\n test_done\n-- \n1.8.5.2-311-g6427a96\n"},{"id":"232541","messageId":"CABEtfDEVfmrTrsAUqY75NfBPYJpWA-YVouYJDktn5ovkjg_Vtw@mail.gmail.com","threadId":"35580","inReplyTo":"xmqqy532qf23.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 1/2] merge-base: fix duplicates and not best ancestors in output","fromName":"Василий Макаров","fromEmail":"einmalfel@gmail.com","sentAt":"2013-12-31T11:15:56Z","receivedAt":"2013-12-31T11:15:56Z","isPatch":true,"sender":{"key":"einmalfel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2640813?v=4"},"body":"Hello, Junio!\n\n>> Hi there!\n>> First of all: I'm new to mailing-lists, sorry if I'm doing it wrong.\n>>\n>> I've found a bug in git merge-base, causing it to show not best common\n>> ancestors and duplicates under some circumstances (example is given in\n>> attached test case).\n>\n>Attached???\n\nSorry about this. I expected my first message to be sent back to me by\ngit@vger.kernel.org. As I understand I should have replied to this\nmessage with second patch (test). But I did not received first message\nback, so I just sent second one to git@vger.kernel.org. What am I\ndoing wrong?\n\n> I think we should split that helper function\n> handle_octopus(). It does two totally unrelated things\n\nAgree! I have not done this in original patch because I wanted it to\nbe a minimal change.\n\n> And assuming that deduping is the right thing to do here, here is a\n> follow-up on top of the spliting patch.\n>\n> Scripts that use \"merge-base --octopus\" could do the reducing\n> themselves, but most of them are expected to want to get the reduced\n> results without having to do any work themselves.\n\nNot sure what scripts you are talking about. Man git merge-base says:\n\"--octopus\n Compute the best common ancestors of all supplied commits\"\nWithout deduping this option doesn't always work, so it is a right\nthing to do here.\n\nI've also tested changes you've sent, they are OK.\n\nHappy new year!\n\n2013/12/31 Junio C Hamano :\n> Junio C Hamano writes:\n>\n>> I do not offhand remember if it was deliberate that we do not dedup\n>> the result from the underlying get_octopus_merge_bases() (the most\n>> likely reason for not deduping is because the caller is expected to\n>> do that if it wants to).\n>>\n>> Whether it is an improvement to force deduping here or it is an\n>> regression to do so, I think we should split that helper function\n>> handle_octopus(). It does two totally unrelated things (one is only\n>> to list independent heads without showing merge bases, the other is\n>> to show one or more merge bases across all the heads given).\n>> Perhaps if we split the \"independent\" codepath introduced by\n>> a1e0ad78 (merge-base --independent to print reduced parent list in a\n>> merge, 2010-08-17) into its own helper function, like this, it would\n>> make it clear what is going on.\n>\n> And assuming that deduping is the right thing to do here, here is a\n> follow-up on top of the spliting patch.\n>\n> -- >8 --\n> Subject: [PATCH] merge-base --octopus: reduce the result from get_octopus_merge_bases()\n>\n> Scripts that use \"merge-base --octopus\" could do the reducing\n> themselves, but most of them are expected to want to get the reduced\n> results without having to do any work themselves.\n>\n> Tests are taken from a message by Василий Макаров\n> \n>\n> Signed-off-by: Junio C Hamano \n> ---\n>\n> We might want to vet the existing callers of the underlying\n> get_octopus_merge_bases() and find out if _all_ of them are doing\n> anything extra (like deduping) because the machinery can return\n> duplicate results. And if that is the case, then we may want to\n> move the dedupling down the callchain instead of having it here.\n>\n> builtin/merge-base.c | 2 +-\n> t/t6010-merge-base.sh | 39 +++++++++++++++++++++++++++++++++++++++\n> 2 files changed, 40 insertions(+), 1 deletion(-)\n>\n> diff --git a/builtin/merge-base.c b/builtin/merge-base.c\n> index daa96c7..87f4dbc 100644\n> --- a/builtin/merge-base.c\n> +++ b/builtin/merge-base.c\n> @@ -73,7 +73,7 @@ static int handle_octopus(int count, const char **args, int show_all)\n> for (i = count - 1; i >= 0; i--)\n> commit_list_insert(get_commit_reference(args[i]), &revs);\n>\n> - result = get_octopus_merge_bases(revs);\n> + result = reduce_heads(get_octopus_merge_bases(revs));\n>\n> if (!result)\n> return 1;\n> diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\n> index f80bba8..abb5728 100755\n> --- a/t/t6010-merge-base.sh\n> +++ b/t/t6010-merge-base.sh\n> @@ -230,4 +230,43 @@ test_expect_success 'criss-cross merge-base for octopus-step' '\n> test_cmp expected.sorted actual.sorted\n> '\n>\n> +test_expect_success 'merge-base --octopus --all for complex tree' '\n> + # Best common ancestor for JE, JAA and JDD is JC\n> + # JE\n> + # / |\n> + # / |\n> + # / |\n> + # JAA / |\n> + # |\\ / |\n> + # | \\ | JDD |\n> + # | \\ |/ | |\n> + # | JC JD |\n> + # | | /| |\n> + # | |/ | |\n> + # JA | | |\n> + # |\\ /| | |\n> + # X JB | X X\n> + # \\ \\ | / /\n> + # \\__\\|/___/\n> + # J\n> + test_commit J &&\n> + test_commit JB &&\n> + git reset --hard J &&\n> + test_commit JC &&\n> + git reset --hard J &&\n> + test_commit JTEMP1 &&\n> + test_merge JA JB &&\n> + test_merge JAA JC &&\n> + git reset --hard J &&\n> + test_commit JTEMP2 &&\n> + test_merge JD JB &&\n> + test_merge JDD JC &&\n> + git reset --hard J &&\n> + test_commit JTEMP3 &&\n> + test_merge JE JC &&\n> + git rev-parse JC >expected &&\n> + git merge-base --all --octopus JAA JDD JE >actual &&\n> + test_cmp expected actual\n> +'\n> +\n> test_done\n> --\n> 1.8.5.2-311-g6427a96\n>\n"}]}