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

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