Merge branch 'jc/merge-bases'
authorJunio C Hamano <gitster@pobox.com>
Tue, 11 Sep 2012 18:35:26 +0000 (11:35 -0700)
committerJunio C Hamano <gitster@pobox.com>
Tue, 11 Sep 2012 18:36:05 +0000 (11:36 -0700)
Optimise the "merge-base" computation a bit, and also update its
users that do not need the full merge-base information to call a
cheaper subset.

* jc/merge-bases:
reduce_heads(): reimplement on top of remove_redundant()
merge-base: "--is-ancestor A B"
get_merge_bases_many(): walk from many tips in parallel
in_merge_bases(): use paint_down_to_common()
merge_bases_many(): split out the logic to paint history
in_merge_bases(): omit unnecessary redundant common ancestor reduction
http-push: use in_merge_bases() for fast-forward check
receive-pack: use in_merge_bases() for fast-forward check
in_merge_bases(): support only one "other" commit

Documentation/git-merge-base.txt
builtin/branch.c
builtin/fetch.c
builtin/merge-base.c
builtin/receive-pack.c
commit.c
commit.h
contrib/examples/builtin-fetch--tool.c
fast-import.c
http-push.c
submodule.c
index b295bf83302de3fdac2833df756799a7aad6b404..87842e33f8aebc7d27fa732af1de15f0e4175c07 100644 (file)
@@ -11,6 +11,7 @@ SYNOPSIS
 [verse]
 'git merge-base' [-a|--all] <commit> <commit>...
 'git merge-base' [-a|--all] --octopus <commit>...
+'git merge-base' --is-ancestor <commit> <commit>
 'git merge-base' --independent <commit>...
 
 DESCRIPTION
@@ -50,6 +51,12 @@ from linkgit:git-show-branch[1] when used with the `--merge-base` option.
        from any other.  This mimics the behavior of 'git show-branch
        --independent'.
 
+--is-ancestor::
+       Check if the first <commit> is an ancestor of the second <commit>,
+       and exit with status 0 if true, or with status 1 if not.
+       Errors are signaled by a non-zero status that is not 1.
+
+
 OPTIONS
 -------
 -a::
@@ -110,6 +117,27 @@ both '1' and '2' are merge-bases of A and B.  Neither one is better than
 the other (both are 'best' merge bases).  When the `--all` option is not given,
 it is unspecified which best one is output.
 
+A common idiom to check "fast-forward-ness" between two commits A
+and B is (or at least used to be) to compute the merge base between
+A and B, and check if it is the same as A, in which case, A is an
+ancestor of B.  You will see this idiom used often in older scripts.
+
+       A=$(git rev-parse --verify A)
+       if test "$A" = "$(git merge-base A B)"
+       then
+               ... A is an ancestor of B ...
+       fi
+
+In modern git, you can say this in a more direct way:
+
+       if git merge-base --is-ancestor A B
+       then
+               ... A is an ancestor of B ...
+       fi
+
+instead.
+
+
 See also
 --------
 linkgit:git-rev-list[1],
index e61b0ece2199f0d2b637cd2ce879105280c38d21..5cb6d78f2c472cc6e579bf6618898f0e44e5ef03 100644 (file)
@@ -130,7 +130,7 @@ static int branch_merged(int kind, const char *name,
        if (!reference_rev)
                reference_rev = head_rev;
 
-       merged = in_merge_bases(rev, &reference_rev, 1);
+       merged = in_merge_bases(rev, reference_rev);
 
        /*
         * After the safety valve is fully redefined to "check with
@@ -140,7 +140,7 @@ static int branch_merged(int kind, const char *name,
         * a gentle reminder is in order.
         */
        if ((head_rev != reference_rev) &&
-           in_merge_bases(rev, &head_rev, 1) != merged) {
+           in_merge_bases(rev, head_rev) != merged) {
                if (merged)
                        warning(_("deleting branch '%s' that has been merged to\n"
                                "         '%s', but not yet merged to HEAD."),
index 3f2ad7727fbff9f12cb18c69d925e2717c2a768b..97a849a9dc082555fe1cbe6d0216d03563c75951 100644 (file)
@@ -323,7 +323,7 @@ static int update_local_ref(struct ref *ref,
                return r;
        }
 
-       if (in_merge_bases(current, &updated, 1)) {
+       if (in_merge_bases(current, updated)) {
                char quickref[83];
                int r;
                strcpy(quickref, find_unique_abbrev(current->object.sha1, DEFAULT_ABBREV));
index 2f223a66462c5e6014c8608cd3c50ef243e8668a..1bc79910481e6ee04b470620da5609c1c6fbcac4 100644 (file)
@@ -26,6 +26,7 @@ static const char * const merge_base_usage[] = {
        N_("git merge-base [-a|--all] <commit> <commit>..."),
        N_("git merge-base [-a|--all] --octopus <commit>..."),
        N_("git merge-base --independent <commit>..."),
+       N_("git merge-base --is-ancestor <commit> <commit>"),
        NULL
 };
 
@@ -70,6 +71,20 @@ static int handle_octopus(int count, const char **args, int reduce, int show_all
        return 0;
 }
 
+static int handle_is_ancestor(int argc, const char **argv)
+{
+       struct commit *one, *two;
+
+       if (argc != 2)
+               die("--is-ancestor takes exactly two commits");
+       one = get_commit_reference(argv[0]);
+       two = get_commit_reference(argv[1]);
+       if (in_merge_bases(one, two))
+               return 0;
+       else
+               return 1;
+}
+
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
        struct commit **rev;
@@ -77,11 +92,14 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
        int show_all = 0;
        int octopus = 0;
        int reduce = 0;
+       int is_ancestor = 0;
 
        struct option options[] = {
                OPT_BOOLEAN('a', "all", &show_all, N_("output all common ancestors")),
                OPT_BOOLEAN(0, "octopus", &octopus, N_("find ancestors for a single n-way merge")),
                OPT_BOOLEAN(0, "independent", &reduce, N_("list revs not reachable from others")),
+               OPT_BOOLEAN(0, "is-ancestor", &is_ancestor,
+                           N_("is the first one ancestor of the other?")),
                OPT_END()
        };
 
@@ -89,6 +107,10 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
        argc = parse_options(argc, argv, prefix, options, merge_base_usage, 0);
        if (!octopus && !reduce && argc < 2)
                usage_with_options(merge_base_usage, options);
+       if (is_ancestor && (show_all | octopus | reduce))
+               die("--is-ancestor cannot be used with other options");
+       if (is_ancestor)
+               return handle_is_ancestor(argc, argv);
        if (reduce && (show_all || octopus))
                die("--independent cannot be used with other options");
 
index 2cb854feb4b3a701201ef683c6644aaa852d50b5..9145f1a5950fcd363a5e65e817df5c61bd769c01 100644 (file)
@@ -480,7 +480,6 @@ static const char *update(struct command *cmd)
            !prefixcmp(name, "refs/heads/")) {
                struct object *old_object, *new_object;
                struct commit *old_commit, *new_commit;
-               struct commit_list *bases, *ent;
 
                old_object = parse_object(old_sha1);
                new_object = parse_object(new_sha1);
@@ -493,12 +492,7 @@ static const char *update(struct command *cmd)
                }
                old_commit = (struct commit *)old_object;
                new_commit = (struct commit *)new_object;
-               bases = get_merge_bases(old_commit, new_commit, 1);
-               for (ent = bases; ent; ent = ent->next)
-                       if (!hashcmp(old_sha1, ent->item->object.sha1))
-                               break;
-               free_commit_list(bases);
-               if (!ent) {
+               if (!in_merge_bases(old_commit, new_commit)) {
                        rp_error("denying non-fast-forward %s"
                                 " (you should pull first)", name);
                        return "non-fast-forward";
index 87268682f98f0cd0f18221b3647ad30dbcbc560e..0ea441d13b1430231f30d9524aed88b9719290b6 100644 (file)
--- a/commit.c
+++ b/commit.c
@@ -607,28 +607,12 @@ static struct commit *interesting(struct commit_list *list)
        return NULL;
 }
 
-static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
 {
        struct commit_list *list = NULL;
        struct commit_list *result = NULL;
        int i;
 
-       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;
-       for (i = 0; i < n; i++) {
-               if (parse_commit(twos[i]))
-                       return NULL;
-       }
-
        one->object.flags |= PARENT1;
        commit_list_insert_by_date(one, &list);
        for (i = 0; i < n; i++) {
@@ -669,9 +653,34 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
                }
        }
 
-       /* Clean up the result to remove stale ones */
        free_commit_list(list);
-       list = result; result = NULL;
+       return result;
+}
+
+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;
+
+       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;
+       for (i = 0; i < n; i++) {
+               if (parse_commit(twos[i]))
+                       return NULL;
+       }
+
+       list = paint_down_to_common(one, n, twos);
+
        while (list) {
                struct commit_list *next = list->next;
                if (!(list->item->object.flags & STALE))
@@ -709,6 +718,60 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)
        return ret;
 }
 
+static int remove_redundant(struct commit **array, int cnt)
+{
+       /*
+        * Some commit in the array may be an ancestor of
+        * another commit.  Move such commit to the end of
+        * the array, and return the number of commits that
+        * are independent from each other.
+        */
+       struct commit **work;
+       unsigned char *redundant;
+       int *filled_index;
+       int i, j, filled;
+
+       work = xcalloc(cnt, sizeof(*work));
+       redundant = xcalloc(cnt, 1);
+       filled_index = xmalloc(sizeof(*filled_index) * (cnt - 1));
+
+       for (i = 0; i < cnt; i++) {
+               struct commit_list *common;
+
+               if (redundant[i])
+                       continue;
+               for (j = filled = 0; j < cnt; j++) {
+                       if (i == j || redundant[j])
+                               continue;
+                       filled_index[filled] = j;
+                       work[filled++] = array[j];
+               }
+               common = paint_down_to_common(array[i], filled, work);
+               if (array[i]->object.flags & PARENT2)
+                       redundant[i] = 1;
+               for (j = 0; j < filled; j++)
+                       if (work[j]->object.flags & PARENT1)
+                               redundant[filled_index[j]] = 1;
+               clear_commit_marks(array[i], all_flags);
+               for (j = 0; j < filled; j++)
+                       clear_commit_marks(work[j], all_flags);
+               free_commit_list(common);
+       }
+
+       /* Now collect the result */
+       memcpy(work, array, sizeof(*array) * cnt);
+       for (i = filled = 0; i < cnt; i++)
+               if (!redundant[i])
+                       array[filled++] = work[i];
+       for (j = filled, i = 0; i < cnt; i++)
+               if (redundant[i])
+                       array[j++] = work[i];
+       free(work);
+       free(redundant);
+       free(filled_index);
+       return filled;
+}
+
 struct commit_list *get_merge_bases_many(struct commit *one,
                                         int n,
                                         struct commit **twos,
@@ -717,7 +780,7 @@ struct commit_list *get_merge_bases_many(struct commit *one,
        struct commit_list *list;
        struct commit **rslt;
        struct commit_list *result;
-       int cnt, i, j;
+       int cnt, i;
 
        result = merge_bases_many(one, n, twos);
        for (i = 0; i < n; i++) {
@@ -748,28 +811,11 @@ struct commit_list *get_merge_bases_many(struct commit *one,
        clear_commit_marks(one, 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_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) {
-                               if (rslt[i] == list->item)
-                                       rslt[i] = NULL;
-                               if (rslt[j] == list->item)
-                                       rslt[j] = NULL;
-                       }
-               }
-       }
 
-       /* Surviving ones in rslt[] are the independent results */
+       cnt = remove_redundant(rslt, cnt);
        result = NULL;
-       for (i = 0; i < cnt; i++) {
-               if (rslt[i])
-                       commit_list_insert_by_date(rslt[i], &result);
-       }
+       for (i = 0; i < cnt; i++)
+               commit_list_insert_by_date(rslt[i], &result);
        free(rslt);
        return result;
 }
@@ -780,6 +826,9 @@ struct commit_list *get_merge_bases(struct commit *one, struct commit *two,
        return get_merge_bases_many(one, 1, &two, cleanup);
 }
 
+/*
+ * Is "commit" a decendant of one of the elements on the "with_commit" list?
+ */
 int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
 {
        if (!with_commit)
@@ -789,28 +838,28 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
 
                other = with_commit->item;
                with_commit = with_commit->next;
-               if (in_merge_bases(other, &commit, 1))
+               if (in_merge_bases(other, commit))
                        return 1;
        }
        return 0;
 }
 
-int in_merge_bases(struct commit *commit, struct commit **reference, int num)
+/*
+ * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
+ */
+int in_merge_bases(struct commit *commit, struct commit *reference)
 {
-       struct commit_list *bases, *b;
+       struct commit_list *bases;
        int ret = 0;
 
-       if (num == 1)
-               bases = get_merge_bases(commit, *reference, 1);
-       else
-               die("not yet");
-       for (b = bases; b; b = b->next) {
-               if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {
-                       ret = 1;
-                       break;
-               }
-       }
+       if (parse_commit(commit) || parse_commit(reference))
+               return ret;
 
+       bases = paint_down_to_common(commit, 1, &reference);
+       if (commit->object.flags & PARENT2)
+               ret = 1;
+       clear_commit_marks(commit, all_flags);
+       clear_commit_marks(reference, all_flags);
        free_commit_list(bases);
        return ret;
 }
@@ -819,51 +868,31 @@ struct commit_list *reduce_heads(struct commit_list *heads)
 {
        struct commit_list *p;
        struct commit_list *result = NULL, **tail = &result;
-       struct commit **other;
-       size_t num_head, num_other;
+       struct commit **array;
+       int num_head, i;
 
        if (!heads)
                return NULL;
 
-       /* Avoid unnecessary reallocations */
-       for (p = heads, num_head = 0; p; p = p->next)
-               num_head++;
-       other = xcalloc(sizeof(*other), num_head);
-
-       /* For each commit, see if it can be reached by others */
-       for (p = heads; p; p = p->next) {
-               struct commit_list *q, *base;
-
-               /* Do we already have this in the result? */
-               for (q = result; q; q = q->next)
-                       if (p->item == q->item)
-                               break;
-               if (q)
+       /* Uniquify */
+       for (p = heads; p; p = p->next)
+               p->item->object.flags &= ~STALE;
+       for (p = heads, num_head = 0; p; p = p->next) {
+               if (p->item->object.flags & STALE)
                        continue;
-
-               num_other = 0;
-               for (q = heads; q; q = q->next) {
-                       if (p->item == q->item)
-                               continue;
-                       other[num_other++] = q->item;
+               p->item->object.flags |= STALE;
+               num_head++;
+       }
+       array = xcalloc(sizeof(*array), num_head);
+       for (p = heads, i = 0; p; p = p->next) {
+               if (p->item->object.flags & STALE) {
+                       array[i++] = p->item;
+                       p->item->object.flags &= ~STALE;
                }
-               if (num_other)
-                       base = get_merge_bases_many(p->item, num_other, other, 1);
-               else
-                       base = NULL;
-               /*
-                * If p->item does not have anything common with other
-                * commits, there won't be any merge base.  If it is
-                * reachable from some of the others, p->item will be
-                * the merge base.  If its history is connected with
-                * others, but p->item is not reachable by others, we
-                * will get something other than p->item back.
-                */
-               if (!base || (base->item != p->item))
-                       tail = &(commit_list_insert(p->item, tail)->next);
-               free_commit_list(base);
        }
-       free(other);
+       num_head = remove_redundant(array, num_head);
+       for (i = 0; i < num_head; i++)
+               tail = &commit_list_insert(array[i], tail)->next;
        return result;
 }
 
index d617fa3f28d9fecf0bbf8e87c373f8701c286227..6edce876739672b4fde2b6970e7ff55b8a921743 100644 (file)
--- a/commit.h
+++ b/commit.h
@@ -171,7 +171,7 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,
                int depth, int shallow_flag, int not_shallow_flag);
 
 int is_descendant_of(struct commit *, struct commit_list *);
-int in_merge_bases(struct commit *, struct commit **, int);
+int in_merge_bases(struct commit *, struct commit *);
 
 extern int interactive_add(int argc, const char **argv, const char *prefix, int patch);
 extern int run_add_interactive(const char *revision, const char *patch_mode,
index 0d54aa7061e780dd0000b8c2a48e266ad5b8ce53..8bc8c7533a8678e2a43d3ddd49bc9aa8d670897d 100644 (file)
@@ -96,7 +96,7 @@ static int update_local_ref(const char *name,
        strcpy(oldh, find_unique_abbrev(current->object.sha1, DEFAULT_ABBREV));
        strcpy(newh, find_unique_abbrev(sha1_new, DEFAULT_ABBREV));
 
-       if (in_merge_bases(current, &updated, 1)) {
+       if (in_merge_bases(current, updated)) {
                fprintf(stderr, "* %s: fast-forward to %s\n",
                        name, note);
                fprintf(stderr, "  old..new: %s..%s\n", oldh, newh);
index eed97c8fa9f3e1624f69443e28f76d995e589b34..c2a814ec660862937e495c0a7efb6375dc7718ac 100644 (file)
@@ -1691,7 +1691,7 @@ static int update_branch(struct branch *b)
                        return error("Branch %s is missing commits.", b->name);
                }
 
-               if (!in_merge_bases(old_cmit, &new_cmit, 1)) {
+               if (!in_merge_bases(old_cmit, new_cmit)) {
                        unlock_ref(lock);
                        warning("Not updating %s"
                                " (new tip %s does not contain %s)",
index a832ca77a31245e8ef9c71adcc0d7110fcda1e5c..8701c1215d21cd0413c1d69be91b309984cf6b1f 100644 (file)
@@ -1610,9 +1610,8 @@ static int verify_merge_base(unsigned char *head_sha1, struct ref *remote)
 {
        struct commit *head = lookup_commit_or_die(head_sha1, "HEAD");
        struct commit *branch = lookup_commit_or_die(remote->old_sha1, remote->name);
-       struct commit_list *merge_bases = get_merge_bases(head, branch, 1);
 
-       return (merge_bases && !merge_bases->next && merge_bases->item == branch);
+       return in_merge_bases(branch, head);
 }
 
 static int delete_remote_branch(const char *pattern, int force)
index 19dc6a6c0d5cf7d9a4c80c61e160290b4462665d..d133796c9ca6ef1018b23d7b0379d7ed71e846ee 100644 (file)
@@ -788,7 +788,7 @@ static int find_first_merges(struct object_array *result, const char *path,
                die("revision walk setup failed");
        while ((commit = get_revision(&revs)) != NULL) {
                struct object *o = &(commit->object);
-               if (in_merge_bases(b, &commit, 1))
+               if (in_merge_bases(b, commit))
                        add_object_array(o, NULL, &merges);
        }
        reset_revision_walk();
@@ -803,7 +803,7 @@ static int find_first_merges(struct object_array *result, const char *path,
                contains_another = 0;
                for (j = 0; j < merges.nr; j++) {
                        struct commit *m2 = (struct commit *) merges.objects[j].item;
-                       if (i != j && in_merge_bases(m2, &m1, 1)) {
+                       if (i != j && in_merge_bases(m2, m1)) {
                                contains_another = 1;
                                break;
                        }
@@ -865,18 +865,18 @@ int merge_submodule(unsigned char result[20], const char *path,
        }
 
        /* check whether both changes are forward */
-       if (!in_merge_bases(commit_base, &commit_a, 1) ||
-           !in_merge_bases(commit_base, &commit_b, 1)) {
+       if (!in_merge_bases(commit_base, commit_a) ||
+           !in_merge_bases(commit_base, commit_b)) {
                MERGE_WARNING(path, "commits don't follow merge-base");
                return 0;
        }
 
        /* Case #1: a is contained in b or vice versa */
-       if (in_merge_bases(commit_a, &commit_b, 1)) {
+       if (in_merge_bases(commit_a, commit_b)) {
                hashcpy(result, b);
                return 1;
        }
-       if (in_merge_bases(commit_b, &commit_a, 1)) {
+       if (in_merge_bases(commit_b, commit_a)) {
                hashcpy(result, a);
                return 1;
        }