Re: [PATCH] Additional merge-base tests

Junio C Hamano wrote:

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

quoted

This demonstrates a problem with git-merge-base.
 
+# Setup for second test set
+#
+#   PL  PR
+#  /  \/  \
+# L2  C2  R2
+# |   |   |
+# L1  C1  R1
+# |   |   |
+# L0  C0  R0
+#   \ |  /
+#     S

Cute.

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?).

Not _that_ pathological in practice, given that you can't really depend 
on the timestamps in a distributed SCM.

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.

However, I do not think it is really a "problem".  At least what
"merge-base --all" did not miss any, that should be OK.

The degree of the problem is, admittedly, situational.

I think the practical way to proceed is to say that the test
condition should really check that we do not _omit_ C2 in the
merge-base --all output.

I do not believe that the (current) code will miss any bases but it can 
certainly return bases that are reachable from other bases.