Introduce get_merge_bases_many()

This introduces a new function get_merge_bases_many() which is a natural
extension of two commit merge base computation.  It is given one commit
(one) and a set of other commits (twos), and computes the merge base of
one and a merge across other commits.

This is mostly useful to figure out the common ancestor when iterating
over heads during an octopus merge.  When making an octopus between
commits A, B, C and D, we first merge tree of A and B, and then try to
merge C with it.  If we were making pairwise merge, we would be recording
the tree resulting from the merge between A and B as a commit, say M, and
then the next round we will be computing the merge base between M and C.

o---C...*
/       .
o---B...M
/       .
o---o---A

But during an octopus merge, we actually do not create a commit M.  In
order to figure out that the common ancestor to use for this merge,
instead of computing the merge base between C and M, we can call
merge_bases_many() with one set to C and twos containing A and B.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/commit.c b/commit.c
index 6052ca34c803e6af432309041c8e3201b71efca4..cafed26928cf6ef35fffdd41a8686c32e4fe5ca0 100644 (file)
--- a/commit.c
+++ b/commit.c
@@ -533,26 +533,34 @@ static struct commit *interesting(struct commit_list *list)
        return NULL;
 }
 
-static struct commit_list *merge_bases(struct commit *one, struct commit *two)
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
 {
        struct commit_list *list = NULL;
        struct commit_list *result = NULL;
+       int i;
 
-       if (one == two)
-               /* We do not mark this even with RESULT so we do not
-                * have to clean it up.
-                */
-               return commit_list_insert(one, &result);
+       for (i = 0; i < n; i++) {
+               if (one == twos[i])
+                       /*
+                        * We do not mark this even with RESULT so we do not
+                        * have to clean it up.
+                        */
+                       return commit_list_insert(one, &result);
+       }
 
        if (parse_commit(one))
                return NULL;
-       if (parse_commit(two))
-               return NULL;
+       for (i = 0; i < n; i++) {
+               if (parse_commit(twos[i]))
+                       return NULL;
+       }
 
        one->object.flags |= PARENT1;
-       two->object.flags |= PARENT2;
        insert_by_date(one, &list);
-       insert_by_date(two, &list);
+       for (i = 0; i < n; i++) {
+               twos[i]->object.flags |= PARENT2;
+               insert_by_date(twos[i], &list);
+       }
 
        while (interesting(list)) {
                struct commit *commit;
@@ -627,21 +635,26 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)
        return ret;
 }
 
-struct commit_list *get_merge_bases(struct commit *one,
-                                       struct commit *two, int cleanup)
+struct commit_list *get_merge_bases_many(struct commit *one,
+                                        int n,
+                                        struct commit **twos,
+                                        int cleanup)
 {
        struct commit_list *list;
        struct commit **rslt;
        struct commit_list *result;
        int cnt, i, j;
 
-       result = merge_bases(one, two);
-       if (one == two)
-               return result;
+       result = merge_bases_many(one, n, twos);
+       for (i = 0; i < n; i++) {
+               if (one == twos[i])
+                       return result;
+       }
        if (!result || !result->next) {
                if (cleanup) {
                        clear_commit_marks(one, all_flags);
-                       clear_commit_marks(two, all_flags);
+                       for (i = 0; i < n; i++)
+                               clear_commit_marks(twos[i], all_flags);
                }
                return result;
        }
@@ -659,12 +672,13 @@ struct commit_list *get_merge_bases(struct commit *one,
        free_commit_list(result);
 
        clear_commit_marks(one, all_flags);
-       clear_commit_marks(two, all_flags);
+       for (i = 0; i < n; i++)
+               clear_commit_marks(twos[i], all_flags);
        for (i = 0; i < cnt - 1; i++) {
                for (j = i+1; j < cnt; j++) {
                        if (!rslt[i] || !rslt[j])
                                continue;
-                       result = merge_bases(rslt[i], rslt[j]);
+                       result = merge_bases_many(rslt[i], 1, &rslt[j]);
                        clear_commit_marks(rslt[i], all_flags);
                        clear_commit_marks(rslt[j], all_flags);
                        for (list = result; list; list = list->next) {
@@ -686,6 +700,12 @@ struct commit_list *get_merge_bases(struct commit *one,
        return result;
 }
 
+struct commit_list *get_merge_bases(struct commit *one, struct commit *two,
+                                   int cleanup)
+{
+       return get_merge_bases_many(one, 1, &two, cleanup);
+}
+
 int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 {
        struct commit_list *bases, *b;