Re: in_merge_bases() is too expensive for recent "pu" update

Thomas Rast [off-list ref] writes:

Junio C Hamano [off-list ref] writes:
...

quoted

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.

[...]

quoted

            o-------o
           /         \
          /       y---A
         /       /
     ---2---z---1---x---B
         \         /
          o-------o

[...]

quoted

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.