From ed9a540b2b351ea305e26bb0d9028f21c976b67c Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 10 Nov 2005 17:21:54 -0800 Subject: merge-base: fully contaminate the well. The discussion on the list demonstrated a pathological case where an ancestor of a merge-base can be left interesting. This commit introduces a postprocessing phase to fix it. Signed-off-by: Junio C Hamano --- merge-base.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 77 insertions(+), 1 deletion(-) diff --git a/merge-base.c b/merge-base.c index 286bf0e8d1..43a6818369 100644 --- a/merge-base.c +++ b/merge-base.c @@ -80,6 +80,45 @@ static struct commit *interesting(struct commit_list *list) * Now, list does not have any interesting commit. So we find the newest * commit from the result list that is not marked uninteresting. Which is * commit B. + * + * + * Another pathological example how this thing can fail to mark an ancestor + * of a merge base as UNINTERESTING without the postprocessing phase. + * + * 2 + * H + * 1 / \ + * G A \ + * |\ / \ + * | B \ + * | \ \ + * \ C F + * \ \ / + * \ D / + * \ | / + * \| / + * E + * + * list A B C D E F G H + * G1 H2 - - - - - - 1 2 + * H2 E1 B1 - 1 - - 1 - 1 2 + * F2 E1 B1 A2 2 1 - - 1 2 1 2 + * E3 B1 A2 2 1 - - 3 2 1 2 + * B1 A2 2 1 - - 3 2 1 2 + * C1 A2 2 1 1 - 3 2 1 2 + * D1 A2 2 1 1 1 3 2 1 2 + * A2 2 1 1 1 3 2 1 2 + * B3 2 3 1 1 3 2 1 2 + * C7 2 3 7 1 3 2 1 2 + * + * At this point, unfortunately, everybody in the list is + * uninteresting, so we fail to complete the following two + * steps to fully marking uninteresting commits. + * + * D7 2 3 7 7 3 2 1 2 + * E7 2 3 7 7 7 2 1 2 + * + * and we end up showing E as an interesting merge base. */ static int show_all = 0; @@ -88,6 +127,7 @@ static int merge_base(struct commit *rev1, struct commit *rev2) { struct commit_list *list = NULL; struct commit_list *result = NULL; + struct commit_list *tmp = NULL; if (rev1 == rev2) { printf("%s\n", sha1_to_hex(rev1->object.sha1)); @@ -104,9 +144,10 @@ static int merge_base(struct commit *rev1, struct commit *rev2) while (interesting(list)) { struct commit *commit = list->item; - struct commit_list *tmp = list, *parents; + struct commit_list *parents; int flags = commit->object.flags & 7; + tmp = list; list = list->next; free(tmp); if (flags == 3) { @@ -130,6 +171,41 @@ static int merge_base(struct commit *rev1, struct commit *rev2) if (!result) return 1; + /* + * Postprocess to fully contaminate the well. + */ + for (tmp = result; tmp; tmp = tmp->next) { + struct commit *c = tmp->item; + /* Reinject uninteresting ones to list, + * so we can scan their parents. + */ + if (c->object.flags & UNINTERESTING) + commit_list_insert(c, &list); + } + while (list) { + struct commit *c = list->item; + struct commit_list *parents; + + tmp = list; + list = list->next; + free(tmp); + + /* Anything taken out of the list is uninteresting, so + * mark all its parents uninteresting. We do not + * parse new ones (we already parsed all the relevant + * ones). + */ + parents = c->parents; + while (parents) { + struct commit *p = parents->item; + parents = parents->next; + if (!(p->object.flags & UNINTERESTING)) { + p->object.flags |= UNINTERESTING; + commit_list_insert(p, &list); + } + } + } + while (result) { struct commit *commit = result->item; result = result->next; -- cgit v1.2.1 From 9e5f4a5539fe0e6ed31f26f34f1832a729facf4b Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 10 Nov 2005 22:41:44 -0800 Subject: merge-base: avoid unnecessary postprocessing. When we have only one merge-base candidates in the result list, there is no point going back to mark the reachable commits again. And that is the most common case, so try not to waste time on it. Suggested by Linus. Signed-off-by: Junio C Hamano --- merge-base.c | 77 +++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 43 insertions(+), 34 deletions(-) diff --git a/merge-base.c b/merge-base.c index 43a6818369..751c3c281b 100644 --- a/merge-base.c +++ b/merge-base.c @@ -123,6 +123,47 @@ static struct commit *interesting(struct commit_list *list) static int show_all = 0; +static void mark_reachable_commits(struct commit_list *result, + struct commit_list *list) +{ + struct commit_list *tmp; + + /* + * Postprocess to fully contaminate the well. + */ + for (tmp = result; tmp; tmp = tmp->next) { + struct commit *c = tmp->item; + /* Reinject uninteresting ones to list, + * so we can scan their parents. + */ + if (c->object.flags & UNINTERESTING) + commit_list_insert(c, &list); + } + while (list) { + struct commit *c = list->item; + struct commit_list *parents; + + tmp = list; + list = list->next; + free(tmp); + + /* Anything taken out of the list is uninteresting, so + * mark all its parents uninteresting. We do not + * parse new ones (we already parsed all the relevant + * ones). + */ + parents = c->parents; + while (parents) { + struct commit *p = parents->item; + parents = parents->next; + if (!(p->object.flags & UNINTERESTING)) { + p->object.flags |= UNINTERESTING; + commit_list_insert(p, &list); + } + } + } +} + static int merge_base(struct commit *rev1, struct commit *rev2) { struct commit_list *list = NULL; @@ -171,40 +212,8 @@ static int merge_base(struct commit *rev1, struct commit *rev2) if (!result) return 1; - /* - * Postprocess to fully contaminate the well. - */ - for (tmp = result; tmp; tmp = tmp->next) { - struct commit *c = tmp->item; - /* Reinject uninteresting ones to list, - * so we can scan their parents. - */ - if (c->object.flags & UNINTERESTING) - commit_list_insert(c, &list); - } - while (list) { - struct commit *c = list->item; - struct commit_list *parents; - - tmp = list; - list = list->next; - free(tmp); - - /* Anything taken out of the list is uninteresting, so - * mark all its parents uninteresting. We do not - * parse new ones (we already parsed all the relevant - * ones). - */ - parents = c->parents; - while (parents) { - struct commit *p = parents->item; - parents = parents->next; - if (!(p->object.flags & UNINTERESTING)) { - p->object.flags |= UNINTERESTING; - commit_list_insert(p, &list); - } - } - } + if (result->next && list) + mark_reachable_commits(result, list); while (result) { struct commit *commit = result->item; -- cgit v1.2.1 From 53de71f88b0d5a55892c19b412688548f5797f0b Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 11 Nov 2005 01:00:52 -0800 Subject: Add test case for merge-base. Although it was shown that the "full contamination" was not really full during the list discussion, the series improves things without incurring extra parsing cost, and here is a test to check that. Signed-off-by: Junio C Hamano --- t/t6010-merge-base.sh | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100755 t/t6010-merge-base.sh diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh new file mode 100755 index 0000000000..c3a9680e2e --- /dev/null +++ b/t/t6010-merge-base.sh @@ -0,0 +1,59 @@ +#!/bin/sh +# +# Copyright (c) 2005 Junio C Hamano +# + +test_description='Merge base computation. +' + +. ./test-lib.sh + +T=$(git-write-tree) + +M=1130000000 +Z=+0000 + +export GIT_COMMITTER_EMAIL=git@comm.iter.xz +export GIT_COMMITTER_NAME='C O Mmiter' +export GIT_AUTHOR_NAME='A U Thor' +export GIT_AUTHOR_EMAIL=git@au.thor.xz + +doit() { + OFFSET=$1; shift + NAME=$1; shift + PARENTS= + for P + do + PARENTS="${PARENTS}-p $P " + done + GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z" + GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE + export GIT_COMMITTER_DATE GIT_AUTHOR_DATE + commit=$(echo $NAME | git-commit-tree $T $PARENTS) + echo $commit >.git/refs/tags/$NAME + echo $commit +} + +# Setup... +E=$(doit 5 E) +D=$(doit 4 D $E) +F=$(doit 6 F $E) +C=$(doit 3 C $D) +B=$(doit 2 B $C) +A=$(doit 1 A $B) +G=$(doit 7 G $B $E) +H=$(doit 8 H $A $F) + +test_expect_success 'compute merge-base (single)' \ + 'MB=$(git-merge-base G H) && + expr "$(git-name-rev "$MB")" : "[0-9a-f]* B"' + +test_expect_success 'compute merge-base (all)' \ + 'MB=$(git-merge-base --all G H) && + expr "$(git-name-rev "$MB")" : "[0-9a-f]* B"' + +test_expect_success 'compute merge-base with show-branch' \ + 'MB=$(git-show-branch --merge-base G H) && + expr "$(git-name-rev "$MB")" : "[0-9a-f]* B"' + +test_done -- cgit v1.2.1 From 9ce7028531fd7ce1ca8d75a5c4f9a941ef79c9d4 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Wed, 9 Nov 2005 23:36:15 -0800 Subject: git-show-branch: tighten merge-base computation. This makes the merge-base computation resistant to the pathological case discussed on the list earlier, by doing the same logic as git-merge-base. As a side effect, it breaks the command's primary function to list non-merge commit sequences, which needs to be fixed separately. Signed-off-by: Junio C Hamano --- show-branch.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/show-branch.c b/show-branch.c index 70120005be..714e7f8ca3 100644 --- a/show-branch.c +++ b/show-branch.c @@ -181,11 +181,11 @@ static void join_revs(struct commit_list **list_p, while (*list_p) { struct commit_list *parents; + int still_interesting = !!interesting(*list_p); struct commit *commit = pop_one_commit(list_p); int flags = commit->object.flags & all_mask; - int still_interesting = !!interesting(*list_p); - if (!still_interesting && extra < 0) + if (!still_interesting && extra <= 0) break; mark_seen(commit, seen_p); -- cgit v1.2.1 From 6b209d473378cc25708ab9839d0edd493afc1e8f Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 10 Nov 2005 15:47:58 -0800 Subject: Fully detect uninteresting commits. With the change in the previous round, we are guaranteed to come up with the list of all relevant merge bases, but sometimes we do not fully mark unintersting ones due to a horizon effect. Add a phase to postprocess, so that we mark all ancestor of "interesting" commit. This also changes the default ordering of shown commits back to chronological order, and adds --topo-order flag to show them in topological order. Signed-off-by: Junio C Hamano --- show-branch.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 53 insertions(+), 11 deletions(-) diff --git a/show-branch.c b/show-branch.c index 714e7f8ca3..631336cd9d 100644 --- a/show-branch.c +++ b/show-branch.c @@ -199,18 +199,58 @@ static void join_revs(struct commit_list **list_p, parents = parents->next; if ((this_flag & flags) == flags) continue; - parse_commit(p); + if (!p->object.parsed) + parse_commit(p); if (mark_seen(p, seen_p) && !still_interesting) extra--; p->object.flags |= flags; insert_by_date(p, list_p); } } + + /* + * Postprocess to complete well-poisoning. + * + * At this point we have all the commits we have seen in + * seen_p list (which happens to be sorted chronologically but + * it does not really matter). Mark anything that can be + * reached from uninteresting commits not interesting. + */ + for (;;) { + int changed = 0; + struct commit_list *s; + for (s = *seen_p; s; s = s->next) { + struct commit *c = s->item; + struct commit_list *parents; + + if (((c->object.flags & all_revs) != all_revs) && + !(c->object.flags & UNINTERESTING)) + continue; + + /* The current commit is either a merge base or + * already uninteresting one. Mark its parents + * as uninteresting commits _only_ if they are + * already parsed. No reason to find new ones + * here. + */ + parents = c->parents; + while (parents) { + struct commit *p = parents->item; + parents = parents->next; + if (!(p->object.flags & UNINTERESTING)) { + p->object.flags |= UNINTERESTING; + changed = 1; + } + } + } + if (!changed) + break; + } } static void show_one_commit(struct commit *commit, int no_name) { - char pretty[128], *cp; + char pretty[256], *cp; struct commit_name *name = commit->object.util; if (commit->object.parsed) pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0, @@ -360,7 +400,7 @@ int main(int ac, char **av) unsigned int rev_mask[MAX_REVS]; int num_rev, i, extra = 0; int all_heads = 0, all_tags = 0; - int all_mask, all_revs, shown_merge_point; + int all_mask, all_revs; char head_path[128]; const char *head_path_p; int head_path_len; @@ -369,6 +409,8 @@ int main(int ac, char **av) int independent = 0; int no_name = 0; int sha1_name = 0; + int shown_merge_point = 0; + int topo_order = 0; setup_git_directory(); @@ -394,6 +436,8 @@ int main(int ac, char **av) merge_base = 1; else if (!strcmp(arg, "--independent")) independent = 1; + else if (!strcmp(arg, "--topo-order")) + topo_order = 1; else usage(show_branch_usage); ac--; av++; @@ -496,7 +540,8 @@ int main(int ac, char **av) exit(0); /* Sort topologically */ - sort_in_topological_order(&seen); + if (topo_order) + sort_in_topological_order(&seen); /* Give names to commits */ if (!sha1_name && !no_name) @@ -504,15 +549,12 @@ int main(int ac, char **av) all_mask = ((1u << (REV_SHIFT + num_rev)) - 1); all_revs = all_mask & ~((1u << REV_SHIFT) - 1); - shown_merge_point = 0; while (seen) { struct commit *commit = pop_one_commit(&seen); int this_flag = commit->object.flags; - int is_merge_point = (this_flag & all_revs) == all_revs; - if (is_merge_point) - shown_merge_point = 1; + shown_merge_point |= ((this_flag & all_revs) == all_revs); if (1 < num_rev) { for (i = 0; i < num_rev; i++) @@ -521,9 +563,9 @@ int main(int ac, char **av) putchar(' '); } show_one_commit(commit, no_name); - if (shown_merge_point && is_merge_point) - if (--extra < 0) - break; + + if (shown_merge_point && --extra < 0) + break; } return 0; } -- cgit v1.2.1 From 4bc51db0feb4a93a285d6333f206cad77c83ed57 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 10 Nov 2005 18:27:44 -0800 Subject: t1200: use --topo-order to keep the show-branch output stable. Because a batch-oriented script creates many commits within a second on a fast machine, show-branch output of the test results are unstable without topo-order. Signed-off-by: Junio C Hamano --- t/t1200-tutorial.sh | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/t/t1200-tutorial.sh b/t/t1200-tutorial.sh index 35db799edf..d7562e9748 100644 --- a/t/t1200-tutorial.sh +++ b/t/t1200-tutorial.sh @@ -122,7 +122,7 @@ cat > show-branch.expect << EOF ++ [mybranch] Some work. EOF -git show-branch master mybranch > show-branch.output +git show-branch --topo-order master mybranch > show-branch.output test_expect_success 'git show-branch' 'cmp show-branch.expect show-branch.output' git checkout mybranch @@ -145,7 +145,7 @@ cat > show-branch2.expect << EOF ++ [master] Merged "mybranch" changes. EOF -git show-branch master mybranch > show-branch2.output +git show-branch --topo-order master mybranch > show-branch2.output test_expect_success 'git show-branch' 'cmp show-branch2.expect show-branch2.output' # TODO: test git fetch -- cgit v1.2.1