Re: Two-phase merge

[Julian Foad <ju...@btopenworld.com>]

On 29 April, Stefan Fuhrmann wrote:
> Julian Foad wrote:
>> Stefan Fuhrmann wrote:
>>> [...] The proposal I make here is not
>>> an alternative to e.g. "Symmetric Merge" but rather a
>>> refined merge strategy that would also benefit the current
>>> merge.
[...]
>>> In end, we will always merge individual file or property
>>> changes but we plan the merge on tree-level. For many
>>> file nodes, this will unnecessary intermediate states
>>> where the merge got fragmented due to a change to
>>> some *other* file.
>> 
>> Yes.  That is likely to be a significant cause of extra conflict in cases
>> where the user has sub-tree mergeinfo or has done some cherry-pick merges
>> and is now doing a "merge everything else" merge.
> 
> It also happens in the "back and forth" case:


If this problem does arise in basic back-and-forth merging then I would agree it's much more important than I thought, 
but I don't get it.  If "it" 
refers to fragmenting the merge, then no, each merge in a back-and-forth case doesn't get fragmented.

> if the changes in the source are interspersed
> with merges from the target, i.e. the merges
> from A to B will be excluded from the changes
> to be merged from B to A.

Do you mean like this?

            A2      A3      A4
  A o-------o-------o-------o

   /         \             /

  o           \           /

   \           \         /

  B o---o-------o-------o

        B2      B3      B4   


The merge we're considering is the one shown from B4 to A4.  Changes B2 and B4 are changes in the source, interspersed with B3 which is a merge from the target, that is the result of a merge from A to B.

A2 will be chosen as the base for a 3-way merge, and the two arms of this merge will be (A2:B4) as the source side and (A2:A4) as the target side.  The source side, (A2:B4), is equivalent to the combination of B2 and B4.  It can be a bit tricky to understand why it is equivalent; if so, see <>.  The point is that changes B2 and B4 don't get split up and merged one after the other in this scenario.



>>>  This increases the probability of
>>>  merge conflicts and their likelihood to show up again
>>>  after each conflict resolution.
>> (That is: after each phase of the N revision-range phases that the merge 
>> got broken into.)
>> 
>>>  Moreover, it masks cases
>>>  where Symmetric Merge might select an optimized
>>>  merge plan (see wiki for various examples).
>>  I understand, but I don't know of any examples on the Wiki yet.
> 
> E.g. in a merge from A to B, we can simply take the merge
> result of the last B to A merge if there were no later changes
> on either side and the B -> A merge did not cherry-pick
> (with respect to the node in question).

>>>  I propose to use the following two-phase merge workflow:
>>> 
>>>  (1) Planning phase
>>>  - read / evaluate the merge info and change history
>>>     to find the list of revisions to merge
>>>  - break that down for each node changed on the source side
>>>  - optionally handle renaming etc.
>>>  - mark tree conflicts (not sure when to signal them to the
>>>     user and when to resolve them; high-level fragmentation
>>>     might become necessary)
>>> 
>>>  (2) Execution phase
>>>  - merge changes on a per-node basis, i.e. all changes of
>>>     that node get merged before the next node
>>>  - fragmentation may still be necessary for *that file*
>>>  - given the "merge plan" for a node, alternative merge
>>>     strategies may be chosen
>> 
>> OK, the significant change here is not so much the two-phase (although that 
>> has merit in itself) but rather turning the processing order inside-out from 
>> (conceptually)
>> 
>>     REV_RANGES = [contiguous-revision-ranges needed for TREE]
>>     for REV_RANGE in REV_RANGES:
>>       3-way merge REV_RANGE into the whole TREE
>> 
>> to (conceptually)
>> 
>>     for each NODE in the TREE:
>>       MERGES = [find the best sequence of 3-way merges to merge all needed 
>> changes into NODE]
>>       for MERGE in MERGES:
>>         3-way-merge MERGE into NODE
> 
> Correctly. With the tiny addition that all rename
> and tree conflict handling is done in the planning
> phase. That makes it repeatable and potentially
> reduces the number of conflicts (at most one per
> node instead of one per node and merge step).

I get how it reduces conflicts.  What do you mean by 'repeatable'?

> The second phase is also reduced to purely text-
> based processing because all the "structure"
> issues have already been resolved. But that might
> be more of a mental aid instead of a true reduction
> in complexity (we still might need to handle missing
> targets on disk etc.).


>> This is a good idea in itself.  It certainly brings advantages as
>> mentioned above.  I'm not sure what, if any, disadvantages it might have.
> 
> Memory consumption could be proportional to
> the number of changes and renames or such.
> Should not be a real-world problem as long as
> you don't merge more than a few 100k changes.
> 
> A more severe issue might be latency because
> the planning phase needs to gather / evaluate
> data from large sections of history. But that one
> can be improved ;)

Right.

>> I don't know that the scenarios this helps with are our main concern at
>> this point.  It would be good to keep this approach in mind when writing
>> or  designing any new merge code.  In terms of development effort I think
>> it's  more valuable to concentrate first on the advantages to to-and-fro
>> merging (most  commonly without subtree merges and without cherry-picks)
>> that the  'symmetric merge' brings.
> 
> I think it can become helpful as soon as we track renames because
> we need to remap on a per-node basis.

To track a renamed node, we need to be able to recognize and act on the information that each node in a merge will be found at three paths that may all be different: its path in the merge-base (aka source-left) tree, its path in the source (aka source-right) tree, and its path in the target tree.  Is that what you mean by "remap on a per-node basis"?  I think that's something we will need to do anyway, but I don't see that it makes much difference whether we do this once at the planning stage (for a two-phase merge), or do it separately for each sub-merge (for the split-into-revision-ranges method).

- Julian