diff options
| -rw-r--r-- | Documentation/git-merge-base.txt | 28 | ||||
| -rw-r--r-- | builtin/branch.c | 4 | ||||
| -rw-r--r-- | builtin/fetch.c | 2 | ||||
| -rw-r--r-- | builtin/merge-base.c | 22 | ||||
| -rw-r--r-- | builtin/receive-pack.c | 8 | ||||
| -rw-r--r-- | commit.c | 211 | ||||
| -rw-r--r-- | commit.h | 2 | ||||
| -rw-r--r-- | contrib/examples/builtin-fetch--tool.c | 2 | ||||
| -rw-r--r-- | fast-import.c | 2 | ||||
| -rw-r--r-- | http-push.c | 3 | ||||
| -rw-r--r-- | submodule.c | 12 |
11 files changed, 184 insertions, 112 deletions
diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt index b295bf8330..87842e33f8 100644 --- a/Documentation/git-merge-base.txt +++ b/Documentation/git-merge-base.txt @@ -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], diff --git a/builtin/branch.c b/builtin/branch.c index e61b0ece21..5cb6d78f2c 100644 --- a/builtin/branch.c +++ b/builtin/branch.c @@ -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."), diff --git a/builtin/fetch.c b/builtin/fetch.c index 3f2ad7727f..97a849a9dc 100644 --- a/builtin/fetch.c +++ b/builtin/fetch.c @@ -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)); diff --git a/builtin/merge-base.c b/builtin/merge-base.c index 2f223a6646..1bc7991048 100644 --- a/builtin/merge-base.c +++ b/builtin/merge-base.c @@ -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"); diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c index 2cb854feb4..9145f1a595 100644 --- a/builtin/receive-pack.c +++ b/builtin/receive-pack.c @@ -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"; @@ -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; } @@ -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, diff --git a/contrib/examples/builtin-fetch--tool.c b/contrib/examples/builtin-fetch--tool.c index 0d54aa7061..8bc8c7533a 100644 --- a/contrib/examples/builtin-fetch--tool.c +++ b/contrib/examples/builtin-fetch--tool.c @@ -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); diff --git a/fast-import.c b/fast-import.c index eed97c8fa9..c2a814ec66 100644 --- a/fast-import.c +++ b/fast-import.c @@ -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)", diff --git a/http-push.c b/http-push.c index a832ca77a3..8701c1215d 100644 --- a/http-push.c +++ b/http-push.c @@ -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) diff --git a/submodule.c b/submodule.c index 19dc6a6c0d..d133796c9c 100644 --- a/submodule.c +++ b/submodule.c @@ -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; } |