{"thread":{"id":"14699","subject":"[RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","startedAt":"2008-07-27T03:33:24Z","lastAt":"2008-07-28T06:18:51Z","messageCount":11,"participants":["Christian Couder","Junio C Hamano","Johannes Schindelin","Jakub Narebski","Miklos Vajna"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"85136","messageId":"20080727053324.b54fe48e.chriscool@tuxfamily.org","threadId":"14699","inReplyTo":null,"subject":"[RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2008-07-27T03:33:24Z","receivedAt":"2008-07-27T03:33:24Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Before this patch \"git merge-base\" accepted only 2 arguments, so\nonly merge bases between 2 references could be computed.\n\nThe purpose of this patch is to make \"git merge-base\" accept more\nthan 2 arguments, so that the merge bases between the first given\nreference and all the other references can be computed.\n\nThis is easily implemented because the \"get_merge_bases_many\"\nfunction in \"commit.c\" already implements the needed computation.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n Documentation/git-merge-base.txt |   27 +++++++++++++++-------\n builtin-merge-base.c             |   45 ++++++++++++++++++++++++++-----------\n commit.h                         |    2 +\n 3 files changed, 51 insertions(+), 23 deletions(-)\n\n\tHi,\n\n\tNo tests yet, but the following changes since the first version:\n\n\t- added documentation\n\t- don't use static variables anymore\n\n\tThanks for your comments,\n\tChristian.\n\ndiff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt\nindex 1a7ecbf..463c230 100644\n--- a/Documentation/git-merge-base.txt\n+++ b/Documentation/git-merge-base.txt\n@@ -8,26 +8,35 @@ git-merge-base - Find as good common ancestors as possible for a merge\n \n SYNOPSIS\n --------\n-'git merge-base' [--all] <commit> <commit>\n+'git merge-base' [--all] <commit> <commit>...\n \n DESCRIPTION\n -----------\n \n-'git-merge-base' finds as good a common ancestor as possible between\n-the two commits. That is, given two commits A and B, `git merge-base A\n-B` will output a commit which is reachable from both A and B through\n-the parent relationship.\n+'git-merge-base' finds as good common ancestors as possible between\n+the first commit and the other commits. The default behavior is to\n+output only one as good as possible common ancestor, called a merge\n+base.\n+\n+For example, given two commits A and B, `git merge-base A B` will\n+output a commit which is reachable from both A and B through the\n+parent relationship.\n+\n+Given three commits A, B and C, `git merge-base A B C` will output a\n+commit which is reachable through the parent relationship from both A\n+and B, or from both A and C.\n \n Given a selection of equally good common ancestors it should not be\n relied on to decide in any particular way.\n \n-The 'git-merge-base' algorithm is still in flux - use the source...\n-\n OPTIONS\n -------\n --all::\n-\tOutput all common ancestors for the two commits instead of\n-\tjust one.\n+\tOutput all merge bases for the commits instead of just one. No\n+\tmerge bases in the output should be an ancestor of another\n+\tmerge base in the output. Each common ancestor of the first\n+\tcommit and any of the other commits passed as arguments,\n+\tshould be an ancestor of one of the merge bases in the output.\n \n Author\n ------\ndiff --git a/builtin-merge-base.c b/builtin-merge-base.c\nindex 1cb2925..f2c9756 100644\n--- a/builtin-merge-base.c\n+++ b/builtin-merge-base.c\n@@ -2,9 +2,11 @@\n #include \"cache.h\"\n #include \"commit.h\"\n \n-static int show_merge_base(struct commit *rev1, struct commit *rev2, int show_all)\n+static int show_merge_base(struct commit *rev1, int prev2_nr,\n+\t\t\t   struct commit **prev2, int show_all)\n {\n-\tstruct commit_list *result = get_merge_bases(rev1, rev2, 0);\n+\tstruct commit_list *result = get_merge_bases_many(rev1, prev2_nr,\n+\t\t\t\t\t\t\t  prev2, 0);\n \n \tif (!result)\n \t\treturn 1;\n@@ -20,12 +22,20 @@ static int show_merge_base(struct commit *rev1, struct commit *rev2, int show_al\n }\n \n static const char merge_base_usage[] =\n-\"git merge-base [--all] <commit-id> <commit-id>\";\n+\"git merge-base [--all] <commit-id> <commit-id>...\";\n+\n+static struct commit *get_commit_reference(const char *arg)\n+{\n+\tunsigned char revkey[20];\n+\tif (get_sha1(arg, revkey))\n+\t\tdie(\"Not a valid object name %s\", arg);\n+\treturn lookup_commit_reference(revkey);\n+}\n \n int cmd_merge_base(int argc, const char **argv, const char *prefix)\n {\n-\tstruct commit *rev1, *rev2;\n-\tunsigned char rev1key[20], rev2key[20];\n+\tstruct commit *rev1, **prev2 = NULL;\n+\tsize_t prev2_nr = 0, prev2_alloc = 0;\n \tint show_all = 0;\n \n \tgit_config(git_default_config, NULL);\n@@ -38,15 +48,22 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)\n \t\t\tusage(merge_base_usage);\n \t\targc--; argv++;\n \t}\n-\tif (argc != 3)\n+\tif (argc < 3)\n \t\tusage(merge_base_usage);\n-\tif (get_sha1(argv[1], rev1key))\n-\t\tdie(\"Not a valid object name %s\", argv[1]);\n-\tif (get_sha1(argv[2], rev2key))\n-\t\tdie(\"Not a valid object name %s\", argv[2]);\n-\trev1 = lookup_commit_reference(rev1key);\n-\trev2 = lookup_commit_reference(rev2key);\n-\tif (!rev1 || !rev2)\n+\n+\trev1 = get_commit_reference(argv[1]);\n+\tif (!rev1)\n \t\treturn 1;\n-\treturn show_merge_base(rev1, rev2, show_all);\n+\targc--; argv++;\n+\n+\tdo {\n+\t\tstruct commit *rev2 = get_commit_reference(argv[1]);\n+\t\tif (!rev2)\n+\t\t\treturn 1;\n+\t\tALLOC_GROW(prev2, prev2_nr + 1, prev2_alloc);\n+\t\tprev2[prev2_nr++] = rev2;\n+\t\targc--; argv++;\n+\t} while (argc > 1);\n+\n+\treturn show_merge_base(rev1, prev2_nr, prev2, show_all);\n }\ndiff --git a/commit.h b/commit.h\nindex 77de962..4829a5c 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -121,6 +121,8 @@ int read_graft_file(const char *graft_file);\n struct commit_graft *lookup_commit_graft(const unsigned char *sha1);\n \n extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2, int cleanup);\n+extern struct commit_list *get_merge_bases_many(struct commit *one,\n+\t\tint n, struct commit **twos, int cleanup);\n extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);\n \n extern int register_shallow(const unsigned char *sha1);\n-- \n1.6.0.rc0.43.g00eb.dirty\n"},{"id":"85142","messageId":"7vabg43pcp.fsf@gitster.siamese.dyndns.org","threadId":"14699","inReplyTo":"20080727053324.b54fe48e.chriscool@tuxfamily.org","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-27T04:47:34Z","receivedAt":"2008-07-27T04:47:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n>  OPTIONS\n>  -------\n>  --all::\n> -\tOutput all common ancestors for the two commits instead of\n> -\tjust one.\n> +\tOutput all merge bases for the commits instead of just one. No\n> +\tmerge bases in the output should be an ancestor of another\n> +\tmerge base in the output. Each common ancestor of the first\n> +\tcommit and any of the other commits passed as arguments,\n> +\tshould be an ancestor of one of the merge bases in the output.\n\nThe point of merge_bases_many() is that it allows you to compute a merge\nbase between a commit and another commit that does not yet exist which is\na merge across all others.\n\n               o---o---o---o---C\n              /                 :\n             /   o---o---o---B..(M)\n            /   /                 :\n\t---o---*---o---o---o---A..(X)\n\nSuppose you have commits A, B and C, and you would want to come up with an\nOctopus merge X across these three commits.  Because our low-level merge\nmachinery works always on two trees with one common ancestor tree, we\nwould first create a tree that is a merge between B and C (which is marked\nas (M) in the picture), and then merge the tree of (M) and A using common\nancestor between (M) and A.\n\nIf we did not have merge_bases_many(), we would actually create (M) as a\nreal commit, and compute merge base between A and (M), which is marked as\n\"*\" in the picture.  The use of merge_bases_many() allows us to run the\nsame merge base computation without actually creating commit (M).  Instead\nof computing merge-base between A and (M), you can ask for the merge base\nbetween A (\"the first commit\") and B, C (\"the other commits\") to obtain\nthe same answer \"*\".\n\nBase between A and B is that \"*\", and you are correct to say that it is an\nancestor of the \"*\" that is output from the command; base between A and C\nis the parent of \"*\", and again you are correct to say it is ancestor of\nthe \"*\" that is output from the command.\n\nBut if we output any other commit between \"*\" and A from the command, it\nstill satisifies your condition.  \"The merge base between A and each of B,\nC,... should be an ancestor of what is output\".  In order to satisify your\ncondition, in the extreme case, we could even output A.  Both the merge\nbase between A and B, and the merge base between A and C, would be an\nancestor of A.\n\nSo your description may not be incorrect, but I think it completely misses\nthe point of what is being computed.\n\n>  Author\n>  ------\n> diff --git a/builtin-merge-base.c b/builtin-merge-base.c\n> index 1cb2925..f2c9756 100644\n> --- a/builtin-merge-base.c\n> +++ b/builtin-merge-base.c\n> @@ -2,9 +2,11 @@\n>  #include \"cache.h\"\n>  #include \"commit.h\"\n>  \n> -static int show_merge_base(struct commit *rev1, struct commit *rev2, int show_all)\n> +static int show_merge_base(struct commit *rev1, int prev2_nr,\n> +\t\t\t   struct commit **prev2, int show_all)\n>  {\n> -\tstruct commit_list *result = get_merge_bases(rev1, rev2, 0);\n> +\tstruct commit_list *result = get_merge_bases_many(rev1, prev2_nr,\n> +\t\t\t\t\t\t\t  prev2, 0);\n\nThis is just style, but if you must break lines somewhere, I'd prefer to\nhave prev2_nr and prev2 on the same line, like this:\n\n\tstruct commit_list *result = get_merge_bases_many(rev1,\n\t\t\t\t\t\t\t  prev2_nr, prev2, 0);\n\nbecause they logically belong to each other.  Further, I think this\n84-column single-line statement is perfectly fine as well in this case:\n\n\tstruct commit_list *result = get_merge_bases_many(rev1, prev2_nr, prev2, 0);\n\nI would probably do this myself in this case, though:\n\n\tstruct commit_list *result;\n\n\tresult  = get_merge_bases_many(rev1, prev2_nr, prev2, 0);\n"},{"id":"85171","messageId":"alpine.DEB.1.00.0807271631470.5526@eeepc-johanness","threadId":"14699","inReplyTo":"20080727053324.b54fe48e.chriscool@tuxfamily.org","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-27T14:38:05Z","receivedAt":"2008-07-27T14:38:05Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 27 Jul 2008, Christian Couder wrote:\n\n> diff --git a/builtin-merge-base.c b/builtin-merge-base.c\n> index 1cb2925..f2c9756 100644\n> --- a/builtin-merge-base.c\n> +++ b/builtin-merge-base.c\n> @@ -38,15 +48,22 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)\n>  \t\t\tusage(merge_base_usage);\n>  \t\targc--; argv++;\n>  \t}\n> -\tif (argc != 3)\n> +\tif (argc < 3)\n>  \t\tusage(merge_base_usage);\n> -\tif (get_sha1(argv[1], rev1key))\n> -\t\tdie(\"Not a valid object name %s\", argv[1]);\n> -\tif (get_sha1(argv[2], rev2key))\n> -\t\tdie(\"Not a valid object name %s\", argv[2]);\n> -\trev1 = lookup_commit_reference(rev1key);\n> -\trev2 = lookup_commit_reference(rev2key);\n> -\tif (!rev1 || !rev2)\n> +\n> +\trev1 = get_commit_reference(argv[1]);\n> +\tif (!rev1)\n>  \t\treturn 1;\n\nWhy do you special case rev1?  Is it so special?  Just handle it together \nwith all of the other arguments!\n\nIOW have one commit array, and do not call it \"prev\".\n\n> -\treturn show_merge_base(rev1, rev2, show_all);\n> +\targc--; argv++;\n> +\n> +\tdo {\n> +\t\tstruct commit *rev2 = get_commit_reference(argv[1]);\n> +\t\tif (!rev2)\n> +\t\t\treturn 1;\n> +\t\tALLOC_GROW(prev2, prev2_nr + 1, prev2_alloc);\n> +\t\tprev2[prev2_nr++] = rev2;\n> +\t\targc--; argv++;\n> +\t} while (argc > 1);\n\nNow, this is ugly.  You know beforehand the _exact_ number of arguments, \nand yet you dynamically grow the array?  Also, why do you use a do { } \nwhile(), when a for () would be much, much clearer?\n\nBTW I seem to recall that get_merge_bases_many() was _not_ the same as \nget_merge_octopus().  Could you please remind me what _many() does?\n\nCiao,\nDscho\n"},{"id":"85172","messageId":"m3vdyrtloo.fsf@localhost.localdomain","threadId":"14699","inReplyTo":"20080727053324.b54fe48e.chriscool@tuxfamily.org","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-07-27T15:02:21Z","receivedAt":"2008-07-27T15:02:21Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> Before this patch \"git merge-base\" accepted only 2 arguments, so\n> only merge bases between 2 references could be computed.\n\n> +'git-merge-base' finds as good common ancestors as possible between\n> +the first commit and the other commits. The default behavior is to\n> +output only one as good as possible common ancestor, called a merge\n> +base.\n> +\n> +For example, given two commits A and B, `git merge-base A B` will\n> +output a commit which is reachable from both A and B through the\n> +parent relationship.\n> +\n> +Given three commits A, B and C, `git merge-base A B C` will output a\n> +commit which is reachable through the parent relationship from both A\n> +and B, or from both A and C.\n\nI don't understand this complication.  Isn't merge base (merge bases)\nfor commits A, B and C simply least common ancestor (or ancestors)\nof commits A, B and C (with commits being included as their own\nancestors)?\n\nWhat are the results of \"git merge-base\" and \"git merge-base --all\"\nin the following situations?\n\nFor two commits:\n\n      .---.---*---.---.---A\n               \\\n                \\-.---B\n\n\n      .---m-----b---.---.---A\n           \\     \\ /\n            \\     X\n             \\   / \\\n              \\-a---.---.---B\n\n\nFor three commits:\n\n      .---.---1---2---.---.---A\n               \\   \\\n                \\   \\-.---B\n                 \\\n                  \\---.---.---C\n\n\n                    /-.---.---A\n                   /\n      .---.---1---2---.---.---B\n               \\\n                \\-.---.---.---C \n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"85174","messageId":"20080727152806.GA32057@genesis.frugalware.org","threadId":"14699","inReplyTo":"alpine.DEB.1.00.0807271631470.5526@eeepc-johanness","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Miklos Vajna","fromEmail":"vmiklos@frugalware.org","sentAt":"2008-07-27T15:28:06Z","receivedAt":"2008-07-27T15:28:06Z","isPatch":true,"sender":{"key":"vmiklos@frugalware.org","avatar":"https://gravatar.com/avatar/401c1cbbb3a5d13e650c691a2c71d6fd0b80df1a01bc74d9f1972675dd58f2bd?d=mp&s=160"},"body":"On Sun, Jul 27, 2008 at 04:38:05PM +0200, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> BTW I seem to recall that get_merge_bases_many() was _not_ the same as \n> get_merge_octopus().  Could you please remind me what _many() does?\n\nget_octopus_merge_bases() takes a commit_list, and tries to figure out\nthe common bases of those commits.\n\nget_merge_bases_many(), which is used by reduce_heads() takes a commit\nand a commit_list, and counts the bases of the heads against the commit\nspecified as the first parameter.\n\nI think get_merge_bases_many() could be even static, it is not really\ninteresting for anything else than reduce_heads() at the moment.\n"},{"id":"85184","messageId":"7vljzn2o51.fsf@gitster.siamese.dyndns.org","threadId":"14699","inReplyTo":"alpine.DEB.1.00.0807271631470.5526@eeepc-johanness","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-27T18:11:22Z","receivedAt":"2008-07-27T18:11:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> BTW I seem to recall that get_merge_bases_many() was _not_ the same as \n> get_merge_octopus().  Could you please remind me what _many() does?\n\nI explained what merge-bases-many gives in a separate message last night\nwith pictures.\n\nget_merge_octopus() is a more or less useless function.  It is there only\nbecause the protocol between \"merge\" and strategies requires that the\nformer have to pass _some_ bases to the latter.  In fact, the octopus\nstrategy implementation completely ignores the heads given by \"merge\";\na single set of merge base given from outside is not even useful when you\nbuild octopus by repeatedly running pairwise three-way merges.\n\nWith Christian's git-merge-base enhancement, the big comment at the end of\ngit-merge-octopus's main loop can go with a much improved \"next\" merge\nbase computation.\n"},{"id":"85201","messageId":"alpine.DEB.1.00.0807272241220.5526@eeepc-johanness","threadId":"14699","inReplyTo":"7vljzn2o51.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-27T20:44:02Z","receivedAt":"2008-07-27T20:44:02Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 27 Jul 2008, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > BTW I seem to recall that get_merge_bases_many() was _not_ the same as \n> > get_merge_octopus().  Could you please remind me what _many() does?\n> \n> I explained what merge-bases-many gives in a separate message last night \n> with pictures.\n\nI missed that, alright.\n\n> get_merge_octopus() is a more or less useless function.  It is there \n> only because the protocol between \"merge\" and strategies requires that \n> the former have to pass _some_ bases to the latter.\n\nDoes it?  I thought that e.g. merge-recursive accepts an empty set of \nmerge bases?  AFAIR that was the reason why gitk could be merged so well.\n\n> In fact, the octopus strategy implementation completely ignores the \n> heads given by \"merge\"; a single set of merge base given from outside is \n> not even useful when you build octopus by repeatedly running pairwise \n> three-way merges.\n> \n> With Christian's git-merge-base enhancement, the big comment at the end \n> of git-merge-octopus's main loop can go with a much improved \"next\" \n> merge base computation.\n\nOkay.\n\nCiao,\nDscho\n"},{"id":"85202","messageId":"7vk5f7yrz9.fsf_-_@gitster.siamese.dyndns.org","threadId":"14699","inReplyTo":"7vljzn2o51.fsf@gitster.siamese.dyndns.org","subject":"Re* [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-27T20:47:22Z","receivedAt":"2008-07-27T20:47:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>\n>> BTW I seem to recall that get_merge_bases_many() was _not_ the same as \n>> get_merge_octopus().  Could you please remind me what _many() does?\n>\n> I explained what merge-bases-many gives in a separate message last night\n> with pictures.\n>\n> get_merge_octopus() is a more or less useless function.  It is there only\n> because the protocol between \"merge\" and strategies requires that the\n> former have to pass _some_ bases to the latter.  In fact, the octopus\n> strategy implementation completely ignores the heads given by \"merge\";\n> a single set of merge base given from outside is not even useful when you\n> build octopus by repeatedly running pairwise three-way merges.\n\nThis part may benefit from a bit of clarification, so I'll borrow the\npicture from my other message.\n\n               o---o---o---o---C\n              /\n             /   o---o---o---B\n            /   /\n        ---1---2---o---o---o---A\n\nSuppose you have this topology, and you are trying to make an octopus\nacross A, B and C (you are at C and merging A and B into your branch).\nThe protoccol between \"git merge\" and merge strategies is for the former\nto pass common ancestor(s), '--' and then commits being merged.\n\nI think \"merge\", both in scripted version and Miklos's C version, gives\n\"1\" because that is the common across all the heads.  This choice of merge\nbase in itself is correct (that is why I said that git_merge_octopus() is\n\"more or less useless\", not \"totally pointless\").  If an implementation of\nstrategy that is capable of producing an octopus wanted to merge arbitrary\nnumber of trees using a single merge base in one-go, that is the merge\nbase it would want to use.\n\nHOWEVER.\n\nThe particular implementation of git-merge-octopus does not produce the\nfinal merge in one-go.  It iteratively produces pairwise merges.  So the\nfirst step might be to come up with a merge between B and C:\n\n               o---o---o---o---C\n              /                 :\n             /   o---o---o---B..(M)\n            /   /\n        ---1---2---o---o---o---A\n\nand for that, \"1\" is used as the merge base, not because it is the base\nacross A, B and C but because it is the base between B and C.  For this\nmerge, A does not matter.\n\nI drew M in parentheses and lines between B and C to it in dotted line\nbecause we actually do _not_ create a real commit --- the only thing we\nneed is a tree object, in order to proceed to the next step.\n\nThen the final merge result is obtained by merging tree of (M) and A using\ntheir common ancestor.  For that, we _could_ still use \"1\" as the merge\nbase.\n\nBut if you imagine a case where you started from A and M, you would _not_\npick \"1\" as the merge base; you would rather use \"2\" which is a better\nbase for this merge.\n\nThat is why git-merge-octopus ignores the merge base given by \"merge\" but\ncomputes its own.\n\n        Side note.  If your first step merge is between A and B, then you\n        would also use \"2\" as the merge base.\n\n                   o---o---o---o---C\n                  /\n                 /   o---o---o---B..(M)\n                /   /               : \n            ---1---2---o---o---o---A\n\nThe comment at the end of git-merge-octopus talks about \"merge reference\ncommit\", that we used to update it to common found in this round, and that\nthat updating was pointless.  After the first round of merge to produce\nthe tree for M (but without actually creating the commit object M itself),\nin order to figure out the merge base used to merge that with A in the\nsecond round, we used to use A and \"1\" (which was merge base between B and\nC).  That was pointless --- \"merge-base A 1\" is guaranteed to give a base\nthat is no better than either \"merge-base A B\" or \"merge-base A C\".  So\nthe current code keeps using the original head (iow, MRC=Ci, because n\nthis case we are starting from C and merging B and then A into it).\n\nThis trickerly was necessary only because we avoided creating the extra\nmerge commit object M.\n\n\tSide note.  An alternative implementation could have been to\n\tactually record it as a real merge commit M, and then let the\n\ttwo-commit merge-base compute the base between A and M when\n\tmerging A to the result of the previous round, but we avoided\n\tcreating M, at the expense of potentially using suboptimal base in\n\tthe later rounds.\n\nBut we do not have to be that pessimistic.  We can instead accumulate the\ncommits we have merged so far in MRC, and have merge_bases_many() compute\nthe merge base for the new head being merged and the heads we have\nprocessed so far, which can give a better base than what we currently do.\n\nThat is what Christian's patch enables us to do.\n\nIn other words, we can do something like this.\n\n git-merge-octopus.sh |   11 ++---------\n 1 files changed, 2 insertions(+), 9 deletions(-)\n\ndiff --git a/git-merge-octopus.sh b/git-merge-octopus.sh\nindex 645e114..1dadbb4 100755\n--- a/git-merge-octopus.sh\n+++ b/git-merge-octopus.sh\n@@ -61,7 +61,7 @@ do\n \t\texit 2\n \tesac\n \n-\tcommon=$(git merge-base --all $MRC $SHA1) ||\n+\tcommon=$(git merge-base --all $SHA1 $MRC) ||\n \t\tdie \"Unable to find common commit with $SHA1\"\n \n \tcase \"$LF$common$LF\" in\n@@ -100,14 +100,7 @@ do\n \t\tnext=$(git write-tree 2>/dev/null)\n \tfi\n \n-\t# We have merged the other branch successfully.  Ideally\n-\t# we could implement OR'ed heads in merge-base, and keep\n-\t# a list of commits we have merged so far in MRC to feed\n-\t# them to merge-base, but we approximate it by keep using\n-\t# the current MRC.  We used to update it to $common, which\n-\t# was incorrectly doing AND'ed merge-base here, which was\n-\t# unneeded.\n-\n+\tMRC=\"$MRC $SHA1\"\n \tMRT=$next\n done\n \n"},{"id":"85240","messageId":"200807280749.35278.chriscool@tuxfamily.org","threadId":"14699","inReplyTo":"alpine.DEB.1.00.0807271631470.5526@eeepc-johanness","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2008-07-28T05:49:35Z","receivedAt":"2008-07-28T05:49:35Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le dimanche 27 juillet 2008, Johannes Schindelin a écrit :\n> Hi,\n>\n> On Sun, 27 Jul 2008, Christian Couder wrote:\n> > diff --git a/builtin-merge-base.c b/builtin-merge-base.c\n> > index 1cb2925..f2c9756 100644\n> > --- a/builtin-merge-base.c\n> > +++ b/builtin-merge-base.c\n> > @@ -38,15 +48,22 @@ int cmd_merge_base(int argc, const char **argv,\n> > const char *prefix) usage(merge_base_usage);\n> >  \t\targc--; argv++;\n> >  \t}\n> > -\tif (argc != 3)\n> > +\tif (argc < 3)\n> >  \t\tusage(merge_base_usage);\n> > -\tif (get_sha1(argv[1], rev1key))\n> > -\t\tdie(\"Not a valid object name %s\", argv[1]);\n> > -\tif (get_sha1(argv[2], rev2key))\n> > -\t\tdie(\"Not a valid object name %s\", argv[2]);\n> > -\trev1 = lookup_commit_reference(rev1key);\n> > -\trev2 = lookup_commit_reference(rev2key);\n> > -\tif (!rev1 || !rev2)\n> > +\n> > +\trev1 = get_commit_reference(argv[1]);\n> > +\tif (!rev1)\n> >  \t\treturn 1;\n>\n> Why do you special case rev1?  Is it so special?  Just handle it together\n> with all of the other arguments!\n>\n> IOW have one commit array, and do not call it \"prev\".\n\nOk, I have done that in v3.\n\n> > -\treturn show_merge_base(rev1, rev2, show_all);\n> > +\targc--; argv++;\n> > +\n> > +\tdo {\n> > +\t\tstruct commit *rev2 = get_commit_reference(argv[1]);\n> > +\t\tif (!rev2)\n> > +\t\t\treturn 1;\n> > +\t\tALLOC_GROW(prev2, prev2_nr + 1, prev2_alloc);\n> > +\t\tprev2[prev2_nr++] = rev2;\n> > +\t\targc--; argv++;\n> > +\t} while (argc > 1);\n>\n> Now, this is ugly.  You know beforehand the _exact_ number of arguments,\n> and yet you dynamically grow the array?\n\nYou are right. I guess I dealt too much with complex parsing of arguments \nwhere you can have options everywhere, and perhaps I also felt somewhat \nguilty for not having used ALLOC_GROW before, or something.\n\n> Also, why do you use a do { } \n> while(), when a for () would be much, much clearer?\n\nWell, we already know that there are at least 2 commits to parse, so it \nfeels a little bit wastefull to check first again. Also the code to parse \nthe [--all|-a] option before use a while loop with \"argc--; argv++;\" at the \nend, so I think it is more coherent like that.\n\nThanks,\nChristian.\n\n> BTW I seem to recall that get_merge_bases_many() was _not_ the same as\n> get_merge_octopus().  Could you please remind me what _many() does?\n>\n> Ciao,\n> Dscho\n"},{"id":"85246","messageId":"200807280810.20922.chriscool@tuxfamily.org","threadId":"14699","inReplyTo":"7vabg43pcp.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2008-07-28T06:10:20Z","receivedAt":"2008-07-28T06:10:20Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le dimanche 27 juillet 2008, Junio C Hamano a écrit :\n>\n> The point of merge_bases_many() is that it allows you to compute a merge\n> base between a commit and another commit that does not yet exist which is\n> a merge across all others.\n>\n>                o---o---o---o---C\n>               /                 :\n>              /   o---o---o---B..(M)\n>             /   /                 :\n> \t---o---*---o---o---o---A..(X)\n>\n> Suppose you have commits A, B and C, and you would want to come up with\n> an Octopus merge X across these three commits.  Because our low-level\n> merge machinery works always on two trees with one common ancestor tree,\n> we would first create a tree that is a merge between B and C (which is\n> marked as (M) in the picture), and then merge the tree of (M) and A using\n> common ancestor between (M) and A.\n>\n> If we did not have merge_bases_many(), we would actually create (M) as a\n> real commit, and compute merge base between A and (M), which is marked as\n> \"*\" in the picture.  The use of merge_bases_many() allows us to run the\n> same merge base computation without actually creating commit (M). \n> Instead of computing merge-base between A and (M), you can ask for the\n> merge base between A (\"the first commit\") and B, C (\"the other commits\")\n> to obtain the same answer \"*\".\n\nYeah, but what is quite confusing I think is that a merge base seems to be \ndefined as \"an as good as possible _common_ ancestor\" but in this case, the \nresult of \"git merge-base A B C\" is not an ancestor of C (even with --all \noption). So perhaps we need a better definition.\n\n> Base between A and B is that \"*\", and you are correct to say that it is\n> an ancestor of the \"*\" that is output from the command; base between A\n> and C is the parent of \"*\", and again you are correct to say it is\n> ancestor of the \"*\" that is output from the command.\n>\n> But if we output any other commit between \"*\" and A from the command, it\n> still satisifies your condition.  \"The merge base between A and each of\n> B, C,... should be an ancestor of what is output\".  In order to satisify\n> your condition, in the extreme case, we could even output A.  Both the\n> merge base between A and B, and the merge base between A and C, would be\n> an ancestor of A.\n>\n> So your description may not be incorrect, but I think it completely\n> misses the point of what is being computed.\n>\n> >  Author\n> >  ------\n> > diff --git a/builtin-merge-base.c b/builtin-merge-base.c\n> > index 1cb2925..f2c9756 100644\n> > --- a/builtin-merge-base.c\n> > +++ b/builtin-merge-base.c\n> > @@ -2,9 +2,11 @@\n> >  #include \"cache.h\"\n> >  #include \"commit.h\"\n> >\n> > -static int show_merge_base(struct commit *rev1, struct commit *rev2,\n> > int show_all) +static int show_merge_base(struct commit *rev1, int\n> > prev2_nr, +\t\t\t   struct commit **prev2, int show_all)\n> >  {\n> > -\tstruct commit_list *result = get_merge_bases(rev1, rev2, 0);\n> > +\tstruct commit_list *result = get_merge_bases_many(rev1, prev2_nr,\n> > +\t\t\t\t\t\t\t  prev2, 0);\n>\n> This is just style, but if you must break lines somewhere, I'd prefer to\n> have prev2_nr and prev2 on the same line, like this:\n>\n> \tstruct commit_list *result = get_merge_bases_many(rev1,\n> \t\t\t\t\t\t\t  prev2_nr, prev2, 0);\n>\n> because they logically belong to each other.  Further, I think this\n> 84-column single-line statement is perfectly fine as well in this case:\n>\n> \tstruct commit_list *result = get_merge_bases_many(rev1, prev2_nr, prev2,\n> 0);\n>\n> I would probably do this myself in this case, though:\n>\n> \tstruct commit_list *result;\n>\n> \tresult  = get_merge_bases_many(rev1, prev2_nr, prev2, 0);\n\nI used that in v3.\n\nThanks,\nChristian.\n"},{"id":"85249","messageId":"7vej5ev8dw.fsf@gitster.siamese.dyndns.org","threadId":"14699","inReplyTo":"200807280810.20922.chriscool@tuxfamily.org","subject":"Re: [RFC/PATCH v2] merge-base: teach \"git merge-base\" to accept more than 2 arguments","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-28T06:18:51Z","receivedAt":"2008-07-28T06:18:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> Yeah, but what is quite confusing I think is that a merge base seems to be \n> defined as \"an as good as possible _common_ ancestor\" but in this case, the \n> result of \"git merge-base A B C\" is not an ancestor of C (even with --all \n> option). So perhaps we need a better definition.\n\nSee my other message.  \"git merge-base A B C\" is not the best common\nancestors across A B and C.  It is the best common ancestors between A and\na commit that is a merge between B and C.\n\nBy defining/explaining it that way, you can avoid the \"Huh, are you\ntalking about OR or AND\" question you would inevitably get when you say\n\"Common ancestor of A and B or A and C\".  Also in \"git merge-base A B C\",\nA is fundamentally different from any other commit; a commit being (or not\nbeing) common between A and B (or A and C) is what we care about a lot,\nbut a commit being (or not being) common between B and C does not matter\nin this computation.\n"}]}