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

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

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?

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

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/