Re: More gitweb queries..

Disregard my last MB(A,A)===A thing. I really was not thinking, but in N-way merge I think rev-tree is your friend. Unlike merge-base which always does two heads at a time, rev-tree works N-way. You should be able to give many heads to it and have it help you figure out the ancestory relationship across them.

TG> But I still don't know how to handle the following scenario:

TG> /----- A TG> / TG> -GCA#1---GCA#2--- B TG> \---- C

TG> MERGES_HEAD = (A B C). I think the best way would be introduce a TG> temporary commit object otherwise C into AB merge would have merge_base TG> on the first GCA which is suboptimal and maybe wrong isn't it?

I think you can run the same algorithm for those pairwise ancestors and favor the less common ones. In the above drawing, you would first find out the three common pair-wise ancestors.

In your drawing,

    GCA(A,B) = GCA#1
    GCA(B,C) = GCA#2
    GCA(C,A) = GCA#1
    GCA(GCA#1,GCA#2) = GCA#1

Then you notice that GCA#2 is less common than GCA#1 (indeed GCA#1 is contained in GCA#2). So favoring the GCA#2, you do the merge pair that uses it as the merge base, namely B and C, first.

You scan the pairwise list again and find the pair that have not merged and uses the least common GCA as merge base and keep going. For the definition of less common, in many cases those GCA#n would not be related at all and cannot be compared by topology only, so you would probably need to come up with a heuristics to break such ties. Off the top of my head, you could compare commit timestamps (prefer younger), sum of commit chain length from GCA#n to its two head pairs (prefer shorter), sum of number of changed files from GCA#n to its two head pairs (prefer smaller).

TG> /----- A -------D---E TG> / / / TG> -GCA------GCA---- B / TG> \------- C

TG> Where D is a temporary COMMIT obeject to use the second GCA to merge C TG> with D and gets E.

Yes, if you ended up merging A and B first you would have something like that. I think you should not do that in the first place, and try to merge the "most recently diverged" pair first, like this:

         /----- A -----------Y
        /                   / 
     -GCA#1---GCA#2--- B --X
                 \---- C -/

If we are still talking about Octopus (Tripus in this case), you would not want to actually make a commit X. When you merge B and C, you consider that such a resulting tree resides at GCA#2 (merge base of B and C) for the purposes of further merge computation. Then you merge that resulting tree with A, using GCA#1.