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

From: Junio C Hamano <junkio@cox.net>
Date: Aug 12, 2005, 05:27 UTC
Message-ID: <7vwtmr912g.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <7vk6isc5x1.fsf_-_@assigned-by-dhcp.cox.net>

I wrote:

Show 20 quoted lines

> + *                  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.