Re: [RFD] annnotating a pair of commit objects?

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Jan 3, 2013, 09:59 UTC
Message-ID: <50E5568A.5060909@alum.mit.edu>
In-Reply-To: <7vr4m2ycij.fsf@alter.siamese.dyndns.org>

On 01/03/2013 08:03 AM, Junio C Hamano wrote:

Show 22 quoted lines

> I'd like a datastore that maps a pair of commit object names to
> another object name, such that:
> 
>  * When looking at two commits A and B, efficiently query all data
>    associated with a pair of commits <X,Y> where X is contained in
>    the range A..B and not in B..A, and Y is contained in the range
>    B..A and not in A..B.
> 
>  * When <X,Y> is registered in the datastore, and X is rewritten to
>    X' and/or Y is rewritten to Y', the mapping is updated so that it
>    can be queried with <X',Y'> as a new key, similar to the way a
>    notes tree that maps object X can be updated to map object X'
>    when such a rewrite happens.
> 
> The intended use case is to "go beyond rerere".  Given a history of
> this shape:
> 
>     o---o---o---I      mainline
>    / 
>   O---o---X---o---A    topic A
>    \
>     o---Y---o---o---B  topic B

If we ignore rewriting for a moment, the information that you want to record is essentially the merge M of X and Y, no? Namely, X and Y conflict logically with each other (though perhaps not textually) and you, the human, want to record how to reconcile them:

     o---o---o---I      mainline
    /
   O---o---X---o---A    topic A
    \       \
     \       M
      \     /
       o---Y---o---o---B  topic B

However, you don't necessarily want to go to the trouble to make a branch to point at M, nor to do the bookkeeping manually that would be required to take the information stored in M into account when merging A and B later.

Suppose we had M; how could we make use of it in future merges?

Show 7 quoted lines

> [...] and can create a merge J without semantic adjustment.
> 
>     o---o---o---I---J      mainline
>    /               /  
>   O---o---X---o---A        topic A
>    \
>     o---Y---o---o---B      topic B

That would become

     o---o---o---I---J      mainline
    /               /
   O---o---X---o---A        topic A
    \       \
     \       M
      \     /
       o---Y---o---o---B  topic B

Show 8 quoted lines

> When I later merge topic B to the integration branch, however, [...]
> to notice that we need to be careful when creating the merge K:
> 
>     o---o---o---I---J---K  mainline
>    /               /   /
>   O---o---X---o---A   /    topic A
>    \                 /
>     o---Y---o---o---B      topic B

When doing this merge, I think your goal is equivalent to discovering that M includes part of the merge of J and B, and adding M as an (implicit or explicit) third parent to the merge:

     o---o---o---I---J-------K  mainline
    /               /    .  /
   O---o---X---o---A    .  /    topic A
    \       \          .  /
     \       M.........  /
      \     /           /
       o---Y---o---o---B        topic B

How could M be stored? Assuming that these type of premerge merges are sparse, then Jeff's analysis seems good. Concretely, one could simply store pointers to M from both X and Y; e.g.,

* Add a note to X with the information "when merging this commit with Y,
use premerge M"

* Add a note to Y with the information "when merging this commit with X,
use premerge M"

Then, when merging, create the set J..B, scan all of the commits on B..J for these "premerge" notes (O(|B..J|)), and for each one, look in the set J..B to see if it is present. The effort should scale like

    O( |J..B| + |B..J| * lg(|J..B|) )

where, of course J and B could be exchanged for either aesthetic or performance reasons. (One would also need a mechanism for preventing M from being garbage-collected.)

Incidentally, this is just the sort of thing I have been thinking about using to implement a kind of "incremental merge"; I've started writing up my thoughts on my blog [1,2,3] (including how to make pretty pictures of merge conflicts).

Michael

[1] http://softwareswirl.blogspot.de/2012/12/the-conflict-frontier-of-nightmare-merge.html [2] http://softwareswirl.blogspot.de/2012/12/mapping-merge-conflict-frontier.html [3] http://softwareswirl.blogspot.de/2012/12/real-world-conflict-diagrams.html

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