Re: [PATCH] Additional merge-base tests

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;

Hi,

On Tue, 4 Jul 2006, Junio C Hamano wrote:

A Large Angry SCM [off-list ref] writes:

quoted

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.

We could introduce a time.maximumSkew variable, and just walk only 
that much further when traversing the commits.

So, if you do not trust your clients to have a proper ntp setup, just say 
"I trust my peers to be off at most 1 day". That would save lots vs 
traverse-everything.

Ciao,
Dscho

Johannes Schindelin [off-list ref] writes:

We could introduce a time.maximumSkew variable, and just walk only 
that much further when traversing the commits.

So, if you do not trust your clients to have a proper ntp setup, just say 
"I trust my peers to be off at most 1 day". That would save lots vs 
traverse-everything.

The problem ALASCM's example demonstrates does rely on clock
skews.  The timestamps used in the example looked like this:


   1   1
  /  \/  \
 4  -1   4
 |   |   |
 3  -2   3
 |   |   |
 2  -3   2
   \ |  /
     0

The crucial clock skew the case relies on is that the tip of the
middle branch (-1) is older than the common commit (0).  But the
topmost commits with timestamp 1 could be with timestamp 5 to
correct the clock skew and still make the example "fail".

   5   5
  /  \/  \
 4  -1   4
 |   |   |
 3  -2   3
 |   |   |
 2  -3   2
   \ |  /
     0

However, I am not sure how you are going to use that maximumSkew
variable.  The evil owner of the middle branch may have started
running a "git am" to commit 4-patch series just when the
machine's clock jumped back by 3 seconds, at the pace of 1 patch
a second.  Then he pushes '0' out on "master" branch, and the
three commits on top of that on "next" branch.

Two days later, two friends build left and right strands of
pearls based on the "master" branch of the evil owner of the
middle branch.  Maybe they do that one patch a day.  On the
fifth day, they both merge the "next" branch.

The point is that it does not require a very large clock skew to
trigger this.

Junio C Hamano wrote:

The problem ALASCM's example demonstrates does rely on clock
skews.  The timestamps used in the example looked like this:


   1   1
  /  \/  \
 4  -1   4
 |   |   |
 3  -2   3
 |   |   |
 2  -3   2
   \ |  /
     0

The crucial clock skew the case relies on is that the tip of the
middle branch (-1) is older than the common commit (0).  But the
topmost commits with timestamp 1 could be with timestamp 5 to
correct the clock skew and still make the example "fail".

   5   5
  /  \/  \
 4  -1   4
 |   |   |
 3  -2   3
 |   |   |
 2  -3   2
   \ |  /
     0

So would putting timestamp for merge be MAX(now, parents timestamps)
solve the problem?

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Hi,

On Tue, 4 Jul 2006, Jakub Narebski wrote:

Junio C Hamano wrote:

quoted

The problem ALASCM's example demonstrates does rely on clock
skews.  The timestamps used in the example looked like this:


   1   1
  /  \/  \
 4  -1   4
 |   |   |
 3  -2   3
 |   |   |
 2  -3   2
   \ |  /
     0

The crucial clock skew the case relies on is that the tip of the
middle branch (-1) is older than the common commit (0).  But the
topmost commits with timestamp 1 could be with timestamp 5 to
correct the clock skew and still make the example "fail".

   5   5
  /  \/  \
 4  -1   4
 |   |   |
 3  -2   3
 |   |   |
 2  -3   2
   \ |  /
     0

So would putting timestamp for merge be MAX(now, parents timestamps)
solve the problem?

If there is an evil committer, the parents could have bogus timestamps, 
too. But then, I would not pull from such an evil person...

Ciao,
Dscho

Hi,

On Tue, 4 Jul 2006, Junio C Hamano wrote:

However, I am not sure how you are going to use that maximumSkew
variable.

My idea was to continue traversing the merge base's ancestors, marking 
them UNINTERESTING, until hitting a commit which is maximumSkew older than 
the merge base (and not just stop at the merge base, as is the case right 
now, and neither continue traversing in eternity like suggested).

This would not help _evil_ cases (i.e. intentional), but most certainly 
your regular clock skew in a Microsoft network.

Ciao,
Dscho

Junio C Hamano wrote:

A Large Angry SCM [off-list ref] writes:

quoted

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.

The clean-up pass was devised to eliminate bases that are reachable from 
other bases. It just doesn't look hard enough.

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.

Yes, I was aware of graphs that would have that behavior.

The root of the problem is that the heuristic, that attempts to use 
timestamps to detect that a commit is _not_ reachable from a given 
commit, relies on the timestamps of commits with a reachability 
relationship to have a relationship that matches the graph.

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.

The history of the clean-up pass is that before it was added, 
git-merge-base was returning a base reachable from another base, and the 
base returned was, in some significant way, worse for merging. My 
construct demonstrates that the clean-up pass only deals with special case.

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.

Although a very important set of repositories to Git, the linux kernel 
repositories may no longer be representative of the diversity of Git 
use. Still, it would be interesting to know the outcome.

Johannes Schindelin wrote:

Hi,

On Tue, 4 Jul 2006, Junio C Hamano wrote:

quoted

A Large Angry SCM [off-list ref] writes:

quoted

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.

We could introduce a time.maximumSkew variable, and just walk only 
that much further when traversing the commits.

So, if you do not trust your clients to have a proper ntp setup, just say 
"I trust my peers to be off at most 1 day". That would save lots vs 
traverse-everything.

The fuzz would only serve to mask, even more, that the heuristic is 
broken. But, it would also allow the (broken) heuristic to be used _and_ 
let the user decide how much effort may be used to find the correct bases.

If this happens, it should be (yet another) user configurable; either, 
per repository, command line, or both.