Re: Our merge bases sometimes suck

[Junio C Hamano <gitster@pobox.com>]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> It just looks asymmetric, but actually it is symmetric, which was kindof
> surprising when I realized it....
>
> Since "|branch ∧ master|" is the same for all candidates, minimizing N
> is the same as maximizing |candidate|, which is the same as
>
>     git rev-list --count --no-merges $candidate
>
> This is clearly symmetric in master vs. base.

Hmph, but that obviously will become very expensive to compute as
project grows.

When we (potentially) have multiple merge-bases, after finding all
the candidates by traversing from the two commits to be merged, we
already make another set of traversals, starting from the candidates
and painting the ancestors down to their common ancestors.  This is
done to discover if each candidate is reachable from any other
candidate (in which case the reachable one is not a merge-base).

The resulting graph of this traversal is currently used only to cull
non-merge-bases out of the candidates, but I wonder if you can
*count* the nodes in it in each color and use that number (which is
essentially the number of commits that can be reached only from one
candidate and not from other candidates) to derive a score for each
candidate, and use it to assess the goodness of merge-bases, just
like the number you are counting in the above full traversal.