Re: [PATCH] Additional merge-base tests

From: A Large Angry SCM <gitzilla@gmail.com>
Date: Jul 4, 2006, 06:41 UTC
Message-ID: <44AA0DAE.1060308@gmail.com>
In-Reply-To: <7v3bdhoraa.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano wrote:

Show 24 quoted lines

> A Large Angry SCM <gitzilla@gmail.com> writes:
> 
>> 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.