summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--merge-base.c87
-rw-r--r--show-branch.c68
-rw-r--r--t/t1200-tutorial.sh4
-rwxr-xr-xt/t6010-merge-base.sh59
4 files changed, 202 insertions, 16 deletions
diff --git a/merge-base.c b/merge-base.c
index 286bf0e..751c3c2 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -80,14 +80,95 @@ 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;
+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;
struct commit_list *result = NULL;
+ struct commit_list *tmp = NULL;
if (rev1 == rev2) {
printf("%s\n", sha1_to_hex(rev1->object.sha1));
@@ -104,9 +185,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 +212,9 @@ static int merge_base(struct commit *rev1, struct commit *rev2)
if (!result)
return 1;
+ if (result->next && list)
+ mark_reachable_commits(result, list);
+
while (result) {
struct commit *commit = result->item;
result = result->next;
diff --git a/show-branch.c b/show-branch.c
index 7012000..631336c 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);
@@ -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;
}
diff --git a/t/t1200-tutorial.sh b/t/t1200-tutorial.sh
index 35db799..d7562e9 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
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
new file mode 100755
index 0000000..c3a9680
--- /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