Re: Premerging topics (was: [RFD] annnotating a pair of commit objects?)

>
> The goal is to propose a structure for storing and pre-merging pairs of commits.
>
> Data-structure
> ==============
>
> We could use a note ref to store the pre-merge information. Each commit
> would be annotated with a blob containing the list of pre-merges (one
> sha1 per line with sha1 pointing to a merge commit). The commit on the
> other side of a merge would also be annotated.
>
> The choice of the refname could be done like we do with notes:
> - Have a default value
> - Have a default value configured in config
> - Use a specific value when merging/creating the pre-merges
>
> Here are my concerns:
>
> Pros
> ----
> 1. Notes allow dynamic annotation a commit
> 2. If we manage to fix 4, we can easily download all pre-merges from a
> remote host by fetching the ref (or clean by deleting the ref).
> 3. Conflicts on pre-merge notes could probably be resolved by concatenation.
>
> Cons
> ----
> 4. Checking connectivity means opening the blob and parsing it
> 5. Regular notes and pre-merge notes have to be handled separately
> because of 4.
>
> I'm hoping we can keep the pros and avoid the cons, but I'm kind of
> stuck here. Help would be really appreciated (or maybe this is a totally
> wrong direction, and I would also like to know ;)
>
> Merging (Using what we saved)
> =============================
> The goal is to merge branches J and B using existing pre-merges.
>
> E0. Create an empty stack S
> E1. Create set of commits 'J..B' and 'B..J' (that is probably already done)
> E2. For each commit C in smallest(J..B, B..J), execute E3
> E3. For each premerge P in notes-premerge(C), execute E4
> E4. If one of both parents of P belongs to biggest(J..B, B..J), stack P in S
> E5. Merge J and B using all pre-merges from S
>
> Let's consider that |J..B| is smaller than |B..J|.
> E0 is executed only once
> E1 is O(|J..B| + |B..J|)
> E2 is O(|J..B|)
> E3 is O(|J..B| x the average number of pre-merge per commits P_avg)
> E4 is executed for each parent (let's say it's two/constant, after all
> the topic is "pair" of commits), so still O(|J..B| x P_avg)
> E5 I don't know (how it can be done, and what would be the resulting
> time complexity)
>
> So the time cost for steps E0 to E4 is O(|J..B| + |B..J| x P_avg)
>
> Tools (Save the pre-merges)
> ===========================
>
> Of course we need several tools to maintain the list of premerges, and
> to easily compute them. For example, it would be nice to be able to do
> something like:
>
>     $ git pre-merge topicA topicB topicC
>
> to find, resolve and store all interactions between the topics. We could
> then easily derive to something that would allow to pre-merge a new
> topic with all topics already merged in master..pu (for example).
>
> Anyway, this task is left for latter.