Re: Our merge bases sometimes suck

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Jun 20, 2014, 08:53 UTC
Message-ID: <53A3F67A.80501@alum.mit.edu>
In-Reply-To: <xmqqtx7gdqbt.fsf@gitster.dls.corp.google.com>

On 06/20/2014 08:53 AM, Junio C Hamano wrote:

Show 14 quoted lines

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

This formulation is theoretically interesting because it shows the symmetry of the criterion, but that doesn't mean it is the most practical to use. Given that multiple formulations are equivalent, any of them can be used.

Show 14 quoted lines

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

It sounds promising. Let's see if I correctly understand the algorithm that you described:

"common_ancestors" = intersection of all candidates' histories "painting_from($candidate)" = $candidate - common_ancestors discard $candidate if $candidate is in painting_from($other_candidate) (i.e., it is not a merge base)

If that is correct, then the candidate with the most commits in painting_from($candidate) should be the best merge base, because common_ancestors is a subset of the candidate's history, so

    |painting_from($candidate)| = |$candidate| - |common_ancestors|

Since |common_ancestors| is the same for all candidates, minimizing
|painting_from($candidate)| is the same as minimizing |$candidate|.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/