Re: in_merge_bases() is too expensive for recent "pu" update
Thomas Rast <trast@student.ethz.ch> writes:
Show 23 quoted lines
> 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.
Junio C Hamano <gitster@pobox.com>