Re: Our merge bases sometimes suck

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 20, 2014, 06:53 UTC
Message-ID: <xmqqtx7gdqbt.fsf@gitster.dls.corp.google.com>
In-Reply-To: <53A06264.9080205@alum.mit.edu>

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

Show 9 quoted lines

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