Re: [PATCH] merge-base.c: pathological case fix.

[Junio C Hamano <junkio@cox.net>]

I wrote:

> + *                  F
> + *                 / \
> + *            E   A   D
> + *             \ /   /  
> + *              B   /
> + *               \ /
> + *                C
> + *
> + * First we push E and F to list to be processed.  E gets bit 1
> + * and F gets bit 2.  The list becomes:
> + * ...
> + * Next, we pop B and something very interesting happens.  It has flags==3
> + * so it is also placed on the result list, and its parents are marked
> + * uninteresting, retroactively, and placed back on the list:
> + *
> + *    list=C(7), result=C(7) B(3)
> + * 
> + * Now, list does not have any interesting commit.  So we find the newest
> + * commit from the result list that is not marked uninteresting.  Which is
> + * commit B.

I suspect we could have "list" where all commits on it is
uninteresting, while "result" has an interesting commit that
turns out to be reachable from one of the uninteresting commits
that is still on "list", and we miss it because we give up as
soon as "list" contains nothing but uninteresting ones.

I have not come up with such a pathological example, but if that
is indeed the case, we would still end up terminating the
well-contamination too early.  I have a suspicion that no matter
how we cut it we would have this horizon effect anyway, and if
we want to really do the perfect job then we cannot avoid
traversing to the root.

Since merge-base is aiming to be a heuristic that works well
enough in practice, I think we should declare victory now and
not aim for perfection, which is an enemy of the good.