Subject: Re: [PATCH] Additional merge-base tests

From: A Large Angry SCM <[email-masked]>
Date: Mon, 03 Jul 2006 23:41:50 -0700

Junio C Hamano wrote:
> A Large Angry SCM <[email-masked]> 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.