From: Junio C Hamano <gitster@pobox.com>
Date: Fri, 24 Aug 2012 15:52:03 GMT
Subject: Re: in_merge_bases() is too expensive for recent "pu" update
Message-ID: <7v1uiw2spo.fsf@alter.siamese.dyndns.org>
In-Reply-To: <87393cbp6b.fsf@thomas.inf.ethz.ch>

Thomas Rast <trast@student.ethz.ch> writes:

> Junio C Hamano <gitster@pobox.com> writes:
> ...
>> Start from A and B.  Follow from B to find 'x' and paint it in blue,
>> follow from A to find 'y' and paint it in amber.  Follow from 'x' to
>> '1', paint it in blue.  Follow from 'y' to '1', paint it in amber
>> but notice that it already is painted in blue.
> [...]
>>             o-------o
>>            /         \
>>           /       y---A
>>          /       /
>>      ---2---z---1---x---B
>>          \         /
>>           o-------o
> [...]
>> So we need to notice that '1' and '2' have ancestry relation in
>> order to reject '2' as "common but not merge-base".  One way of
>> doing so is not to stop at '1' and keep digging (and eventually we
>> find that '2' is what we could reach from '1' that already is a
>> merge base), but then we will be susceptible to the same kind of
>> clock skew issue as the revision traverser.
>
> I think that is *the* way to do it.

But we do not live in *that* world.  At least not yet.

> I conjecture that every history walking problem can be solved in time
> linear in the number of commits once we properly use the generation
> numbers ;-)

I would conjecture that too, but we do not live in that world yet.