RFC v2merge-base: teach "git merge-base" to accept more than 2 arguments

Before this patch "git merge-base" accepted only 2 arguments, so only merge bases between 2 references could be computed.

The purpose of this patch is to make "git merge-base" accept more than 2 arguments, so that the merge bases between the first given reference and all the other references can be computed.

This is easily implemented because the "get_merge_bases_many" function in "commit.c" already implements the needed computation.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 Documentation/git-merge-base.txt |   27 +++++++++++++++-------
 builtin-merge-base.c             |   45 ++++++++++++++++++++++++++-----------
 commit.h                         |    2 +
 3 files changed, 51 insertions(+), 23 deletions(-)

	Hi,

	No tests yet, but the following changes since the first version:

	- added documentation
	- don't use static variables anymore

	Thanks for your comments,
	Christian.

Christian Couder <chriscool@tuxfamily.org> writes:

The point of merge_bases_many() is that it allows you to compute a merge base between a commit and another commit that does not yet exist which is a merge across all others.

               o---o---o---o---C
              /                 :
             /   o---o---o---B..(M)
            /   /                 :
	---o---*---o---o---o---A..(X)

Suppose you have commits A, B and C, and you would want to come up with an Octopus merge X across these three commits. Because our low-level merge machinery works always on two trees with one common ancestor tree, we would first create a tree that is a merge between B and C (which is marked as (M) in the picture), and then merge the tree of (M) and A using common ancestor between (M) and A.

If we did not have merge_bases_many(), we would actually create (M) as a real commit, and compute merge base between A and (M), which is marked as "*" in the picture. The use of merge_bases_many() allows us to run the same merge base computation without actually creating commit (M). Instead of computing merge-base between A and (M), you can ask for the merge base between A ("the first commit") and B, C ("the other commits") to obtain the same answer "*".

Base between A and B is that "*", and you are correct to say that it is an ancestor of the "*" that is output from the command; base between A and C is the parent of "*", and again you are correct to say it is ancestor of the "*" that is output from the command.

But if we output any other commit between "*" and A from the command, it still satisifies your condition. "The merge base between A and each of B, C,... should be an ancestor of what is output". In order to satisify your condition, in the extreme case, we could even output A. Both the merge base between A and B, and the merge base between A and C, would be an ancestor of A.

So your description may not be incorrect, but I think it completely misses the point of what is being computed.

This is just style, but if you must break lines somewhere, I'd prefer to have prev2_nr and prev2 on the same line, like this:

	struct commit_list *result = get_merge_bases_many(rev1,
							  prev2_nr, prev2, 0);

because they logically belong to each other. Further, I think this 84-column single-line statement is perfectly fine as well in this case:

	struct commit_list *result = get_merge_bases_many(rev1, prev2_nr, prev2, 0);

I would probably do this myself in this case, though:

	struct commit_list *result;

	result  = get_merge_bases_many(rev1, prev2_nr, prev2, 0);

Le dimanche 27 juillet 2008, Junio C Hamano a écrit :

Yeah, but what is quite confusing I think is that a merge base seems to be defined as "an as good as possible _common_ ancestor" but in this case, the result of "git merge-base A B C" is not an ancestor of C (even with --all option). So perhaps we need a better definition.

I used that in v3.

Thanks, Christian.

Christian Couder <chriscool@tuxfamily.org> writes:

See my other message. "git merge-base A B C" is not the best common ancestors across A B and C. It is the best common ancestors between A and a commit that is a merge between B and C.

By defining/explaining it that way, you can avoid the "Huh, are you talking about OR or AND" question you would inevitably get when you say "Common ancestor of A and B or A and C". Also in "git merge-base A B C", A is fundamentally different from any other commit; a commit being (or not being) common between A and B (or A and C) is what we care about a lot, but a commit being (or not being) common between B and C does not matter in this computation.

Hi,

On Sun, 27 Jul 2008, Christian Couder wrote:

Why do you special case rev1? Is it so special? Just handle it together with all of the other arguments!

IOW have one commit array, and do not call it "prev".

Now, this is ugly. You know beforehand the _exact_ number of arguments, and yet you dynamically grow the array? Also, why do you use a do { } while(), when a for () would be much, much clearer?

BTW I seem to recall that get_merge_bases_many() was _not_ the same as get_merge_octopus(). Could you please remind me what _many() does?

Ciao, Dscho

On Sun, Jul 27, 2008 at 04:38:05PM +0200, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

get_octopus_merge_bases() takes a commit_list, and tries to figure out the common bases of those commits.

get_merge_bases_many(), which is used by reduce_heads() takes a commit and a commit_list, and counts the bases of the heads against the commit specified as the first parameter.

I think get_merge_bases_many() could be even static, it is not really interesting for anything else than reduce_heads() at the moment.

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

I explained what merge-bases-many gives in a separate message last night with pictures.

get_merge_octopus() is a more or less useless function. It is there only because the protocol between "merge" and strategies requires that the former have to pass _some_ bases to the latter. In fact, the octopus strategy implementation completely ignores the heads given by "merge"; a single set of merge base given from outside is not even useful when you build octopus by repeatedly running pairwise three-way merges.

With Christian's git-merge-base enhancement, the big comment at the end of git-merge-octopus's main loop can go with a much improved "next" merge base computation.

Hi,

On Sun, 27 Jul 2008, Junio C Hamano wrote:

I missed that, alright.

Does it? I thought that e.g. merge-recursive accepts an empty set of merge bases? AFAIR that was the reason why gitk could be merged so well.

Okay.

Ciao, Dscho

Junio C Hamano <gitster@pobox.com> writes:

This part may benefit from a bit of clarification, so I'll borrow the picture from my other message.

               o---o---o---o---C
              /
             /   o---o---o---B
            /   /
        ---1---2---o---o---o---A

Suppose you have this topology, and you are trying to make an octopus across A, B and C (you are at C and merging A and B into your branch). The protoccol between "git merge" and merge strategies is for the former to pass common ancestor(s), '--' and then commits being merged.

I think "merge", both in scripted version and Miklos's C version, gives "1" because that is the common across all the heads. This choice of merge base in itself is correct (that is why I said that git_merge_octopus() is "more or less useless", not "totally pointless"). If an implementation of strategy that is capable of producing an octopus wanted to merge arbitrary number of trees using a single merge base in one-go, that is the merge base it would want to use.

HOWEVER.

The particular implementation of git-merge-octopus does not produce the final merge in one-go. It iteratively produces pairwise merges. So the first step might be to come up with a merge between B and C:

               o---o---o---o---C
              /                 :
             /   o---o---o---B..(M)
            /   /
        ---1---2---o---o---o---A

and for that, "1" is used as the merge base, not because it is the base across A, B and C but because it is the base between B and C. For this merge, A does not matter.

I drew M in parentheses and lines between B and C to it in dotted line because we actually do _not_ create a real commit --- the only thing we need is a tree object, in order to proceed to the next step.

Then the final merge result is obtained by merging tree of (M) and A using their common ancestor. For that, we _could_ still use "1" as the merge base.

But if you imagine a case where you started from A and M, you would _not_ pick "1" as the merge base; you would rather use "2" which is a better base for this merge.

That is why git-merge-octopus ignores the merge base given by "merge" but computes its own.

        Side note.  If your first step merge is between A and B, then you
        would also use "2" as the merge base.

                   o---o---o---o---C
                  /
                 /   o---o---o---B..(M)
                /   /               : 
            ---1---2---o---o---o---A

The comment at the end of git-merge-octopus talks about "merge reference commit", that we used to update it to common found in this round, and that that updating was pointless. After the first round of merge to produce the tree for M (but without actually creating the commit object M itself), in order to figure out the merge base used to merge that with A in the second round, we used to use A and "1" (which was merge base between B and C). That was pointless --- "merge-base A 1" is guaranteed to give a base that is no better than either "merge-base A B" or "merge-base A C". So the current code keeps using the original head (iow, MRC=Ci, because n this case we are starting from C and merging B and then A into it).

This trickerly was necessary only because we avoided creating the extra merge commit object M.

	Side note.  An alternative implementation could have been to
	actually record it as a real merge commit M, and then let the
	two-commit merge-base compute the base between A and M when
	merging A to the result of the previous round, but we avoided
	creating M, at the expense of potentially using suboptimal base in
	the later rounds.

But we do not have to be that pessimistic. We can instead accumulate the commits we have merged so far in MRC, and have merge_bases_many() compute the merge base for the new head being merged and the heads we have processed so far, which can give a better base than what we currently do.

That is what Christian's patch enables us to do.

In other words, we can do something like this.

 git-merge-octopus.sh |   11 ++---------
 1 files changed, 2 insertions(+), 9 deletions(-)

Le dimanche 27 juillet 2008, Johannes Schindelin a écrit :

Ok, I have done that in v3.

You are right. I guess I dealt too much with complex parsing of arguments where you can have options everywhere, and perhaps I also felt somewhat guilty for not having used ALLOC_GROW before, or something.

Well, we already know that there are at least 2 commits to parse, so it feels a little bit wastefull to check first again. Also the code to parse the [--all|-a] option before use a while loop with "argc--; argv++;" at the end, so I think it is more coherent like that.

Thanks, Christian.

Christian Couder <chriscool@tuxfamily.org> writes:

I don't understand this complication. Isn't merge base (merge bases) for commits A, B and C simply least common ancestor (or ancestors) of commits A, B and C (with commits being included as their own ancestors)?

What are the results of "git merge-base" and "git merge-base --all" in the following situations?

For two commits:

      .---.---*---.---.---A
               \
                \-.---B

      .---m-----b---.---.---A
           \     \ /
            \     X
             \   / \
              \-a---.---.---B

For three commits:

      .---.---1---2---.---.---A
               \   \
                \   \-.---B
                 \
                  \---.---.---C

                    /-.---.---A
                   /
      .---.---1---2---.---.---B
               \
                \-.---.---.---C