Re: [PATCH] Additional merge-base tests
A Large Angry SCM <gitzilla@gmail.com> writes:
Show 10 quoted lines
>> 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.
Show changes to 2 files +73 −0
t/t6010-merge-base.sh, merge-base.c
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;
A Large Angry SCM
