Re: [PATCH] Additional merge-base tests
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:42:32
Subsystem:
the rest · Maintainer:
Linus Torvalds
Possibly related (same subject, not in this thread)
- 2016-06-15 · [PATCH] Additional merge-base tests · A Large Angry SCM <hidden>
- 2016-06-15 · Re: [PATCH] Additional merge-base tests · Junio C Hamano <hidden>
- 2016-06-15 · Re: [PATCH] Additional merge-base tests · A Large Angry SCM <hidden>
- 2016-06-15 · Re: [PATCH] Additional merge-base tests · Junio C Hamano <hidden>
- 2016-06-15 · Re: [PATCH] Additional merge-base tests · Junio C Hamano <hidden>
A Large Angry SCM [off-list ref] writes:
quoted
This is a good demonstration that merge-base may not give you minimal set for pathological cases. If you want to be through you could traverse everything to make sure we do not say 'S' is relevant, but that is quite expensive, so I think there will always be artifacts of horizon effect like this no matter how you try to catch it (didn't I keep saying that already?).The problem is in mark_reachable_commits(); it is either superfluous or it needs to parse_commit() those commits that haven't been parsed yet that it needs to traverse.
Yes, you could traverse everything. But that is not practical. We have known that the clean-up pass has this horizon effect, and it is a compromise. If you apply this testing patch on top of yours, you will see that parsing more commits at that point makes the clean-up pass go all the way down to the root commit. We may alternatively not use the clean-up pass at all, but I suspect that might give us many false positives. I don't remember the details but I think we added it while fixing merge-base in the real life situation. It may be interesting to run tests on real merges (I believe the kernel repository has a handful merges that have more than one merge bases) to see how effective the current clean-up pass is. It may turn out to be ineffective in practice, in which case we could kill it off.
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index 9a815bd..4c6ed5c 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh@@ -89,4 +89,33 @@ test_expect_success 'compute merge-base 'MB=$(git-merge-base --all PL PR) && expr "$(git-name-rev "$MB")" : "[0-9a-f]* tags/C2"' +# Setup third set +# +# S-U0-U1-U2-U3-U4 +# \ X +# D0-D1-D2-D3-D4 + +U0=$(doit 1 U0 $S) +D0=$(doit 1 D0 $S) +U1=$(doit 2 U1 $U0) +D1=$(doit 2 D1 $D0) +U2=$(doit 3 U2 $U1) +D2=$(doit 3 D2 $D1) +U3=$(doit 4 U3 $U2) +D3=$(doit 4 D3 $D2) +U4=$(doit 5 U4 $U3 $D3) +D4=$(doit 5 D4 $D3 $U3) + +test_expect_success 'compute merge-base' ' + + git merge-base --all U4 D4 >out 2>err + if grep tags/S err + then + echo "went all the way down to S -- very unhappy" + false + else + echo "stopped before going too far" + fi +' + test_done
diff --git a/merge-base.c b/merge-base.c
index 4856ca0..daab296 100644
--- a/merge-base.c
+++ b/merge-base.c@@ -6,8 +6,35 @@ #define PARENT1 1 #define PARENT2 2 #define UNINTERESTING 4 +static void debug_list(struct commit_list *l, const char *msg) +{ + fprintf(stderr, "%s\n", msg); + while (l) { + char buf[1024]; + int parsed; + struct commit *commit = l->item; + l = l->next; + parsed = commit->object.parsed; + + if (parsed) { + pretty_print_commit(CMIT_FMT_ONELINE, commit, + ~0UL, buf, sizeof(buf), 7, + NULL, NULL); + } + else { + sprintf(buf, "git-name-rev %s 1>&2", + sha1_to_hex(commit->object.sha1)); + system(buf); + strcpy(buf, sha1_to_hex(commit->object.sha1)); + } + fprintf(stderr, "%d %d %s\n", commit->object.flags, + parsed, buf); + } +} + static struct commit *interesting(struct commit_list *list) { + debug_list(list, "in interesting()"); while (list) { struct commit *commit = list->item; list = list->next;
@@ -134,6 +161,9 @@ static void mark_reachable_commits(struc /* * Postprocess to fully contaminate the well. */ + debug_list(list, "list at top of mark-reachable"); + debug_list(result, "result at top of mark-reachable"); + for (tmp = result; tmp; tmp = tmp->next) { struct commit *c = tmp->item; /* Reinject uninteresting ones to list,
@@ -142,10 +172,12 @@ static void mark_reachable_commits(struc if (c->object.flags & UNINTERESTING) commit_list_insert(c, &list); } + while (list) { struct commit *c = list->item; struct commit_list *parents; + debug_list(list, "list in mark-reachable postprocessing"); tmp = list; list = list->next; free(tmp);
@@ -155,6 +187,15 @@ static void mark_reachable_commits(struc * parse new ones (we already parsed all the relevant * ones). */ + + /* Parsing object here which is a disaster; + * let's demonstrate it. + */ +#if 1 + if (!c->object.parsed) + parse_commit(c); +#endif + parents = c->parents; while (parents) { struct commit *p = parents->item;
@@ -164,6 +205,7 @@ static void mark_reachable_commits(struc commit_list_insert(p, &list); } } + debug_list(result, "result in mark-reachable postprocessing"); } }
@@ -196,6 +238,7 @@ static int merge_base(struct commit *rev free(tmp); if (flags == 3) { insert_by_date(commit, &result); + debug_list(result, "a new result"); /* Mark parents of a found merge uninteresting */ flags |= UNINTERESTING;
@@ -218,6 +261,7 @@ static int merge_base(struct commit *rev if (result->next && list) mark_reachable_commits(result, list); + debug_list(result, "final result"); while (result) { struct commit *commit = result->item; result = result->next;