Three To Two Merge

1. Background

The representation of three-way conflicts is not supported by many XML editors. On the other hand, XML editors do support two-way change tracking and this is well understood by users.

Therefore, representing 3-way merge conflicts in two-way change tracking would provide a significant and useful simplification for users. This article considers how this could be done without losing information although some fine detail is lost (though in some cases this makes it easier for a user to understand the result).

2. Introduction

The DeltaXML DITA Merge product is a symmetric algorithm. A common ancestor (M) is used which is older than the edits (P1, Q1, R, S) to provide the frame of reference for add and delete operations. This is n-way merge and is depicted by the red arrow in the diagram below.

However, a common merge use-case is merging two branches together. In this use-case we consider the branches and their common ancestor. In this case it is possible to represent the changes relative to the branch onto which the changes are being applied. When only three versions or inputs involved in a branch merge it is possible to define adds and deletes relative to the two branches (branches P and Q in the diagram). These are indicated by the blue and yellow arrows below.

Changes between the ancestor (M in the diagram above) and the two inputs being merged (P1 and Q1) are not considered as important as the differences between the two inputs themselves (P1 and Q1).

With this simplification we can represent a conflicting change as an addition-deletion pair. For example, if we are merging Q1 into the P branch (merge of M, P1, Q1 and indicated with the yellow arrow, in order to generate P2) then a conflict is represented as a deletion of the conflicting content in P1 and addition of the conflicting content in Q1. This has the characteristic that if all (conflicting) changes are rejected then we get the result of P1 unchanged where there is conflict, and if all (conflicting) changes are accepted then we get the result from Q1 where there is conflict. This is simpler to explain to users, and we only need two-way change tracking to represent this case.

3. Example of three to two merge process

Suppose there are two versions 'P1' and 'Q1' generated from one common ancestor, say, 'M'. There are two possibilities. Either we can merge 'P1' into 'Q1' or 'Q1' into 'P1'. If the first case is considered, then a conflict is represented as a addition of the conflicting content in P1 and deletion of the conflicting content in Q1 and vice-versa. In other words, if we reject all the changes then we are saying we do not approve of any changes made by Q1, so we would end up with P1. On the other hand, if we accept all the changes then we are saying we like all the changes in P1 but we agree that Q1 is right where there is any conflict or additional change made by Q1.

DeltaXML DITA Merge provides the functionality to generate three-to-two-way merge result by using ThreeWayDitaMerge.ThreeWayMergeResultType.TWO_WAY_RESULT.

3.1. Three-way merge result

Producing three way merge result is the first step of generating three-to-two merge result.

M input version
<section>
  <title>Both edits modify para differently</title>
  <p>This paragraph will be changed</p>
</section>
P1 input version
<section>
  <title>Both edits modify para differently</title>
  <p>This paragraph will be modified</p>
</section>
Q1 input version
<section>
  <title>Both edits modify para differently</title>
  <p>This paragraph will be updated</p>
</section>
Three way merge result
<section deltaxml:deltaV2="M!=P1!=Q1">
  <title deltaxml:deltaV2="M=P1=Q1">Both edits modify para differently</title>
  <p deltaxml:deltaV2="M!=P1!=Q1">This paragraph will be <deltaxml:textGroup
            deltaxml:deltaV2="M!=P1!=Q1" deltaxml:edit-type="modify">
    <deltaxml:text deltaxml:deltaV2="M">changed</deltaxml:text>
    <deltaxml:text deltaxml:deltaV2="P1">modified</deltaxml:text>
    <deltaxml:text deltaxml:deltaV2="Q1">updated</deltaxml:text>
  </deltaxml:textGroup></p>
</section>

3.2. Generating two-way merge

When representing the above there-way result using only a two way we need to consider which information is lost (we can only represent two of the three values) and how the remaining values are used. Lets assume that we are accepting all the changes from P1 and reject all the changes from Q1. So there will be addition of conflicts in P1 and deletion of conflicts in Q1. We will lose all the ancestor information in the process.

Result
<section deltaxml:deltaV2="P1!=Q1">
  <title deltaxml:deltaV2="P1=Q1">Both edits modify para differently</title>
          <p deltaxml:deltaV2="P1!=Q1">This paragraph will be <deltaxml:textGroup deltaxml:deltaV2="P1!=Q1">
        <deltaxml:text deltaxml:deltaV2="P1">modified</deltaxml:text>
        <deltaxml:text deltaxml:deltaV2="Q1">updated</deltaxml:text>
      </deltaxml:textGroup>
    </p>
</section>

3.3. Version renaming

In order to reuse existing deltaXML code where two way versions are called A and B corresponding to the parameters of the compare method the final prco eltas This step renames the versions as 'A' or 'B' according to the direction of merge ('P1 onto Q1' or 'Q1 onto P1'). Above two way merge result can be simplified further by saying added conflicts as 'A' and deleted conflicts as 'B'.

The root element attribute such as deltaxml:version-order will be removed during this process. The attribute such as deltaxml:content-type will be modified.

Simplified result for merge direction 'down'
<topic deltaxml:deltaV2="A!=B">
    <title deltaxml:deltaV2="A=B">Three to two test</title>
    <body deltaxml:deltaV2="A!=B">
        <section deltaxml:deltaV2="A!=B">
            <title deltaxml:deltaV2="A=B">Both edits modify para differently</title>
            <p deltaxml:deltaV2="A!=B">This paragraph will be <deltaxml:textGroup deltaxml:deltaV2="A!=B">
                <deltaxml:text deltaxml:deltaV2="A">modified</deltaxml:text>
                <deltaxml:text deltaxml:deltaV2="B">updated</deltaxml:text>
            </deltaxml:textGroup>
            </p>
        </section>
    </body>
</topic>

3.4. Applying track change filter

The above simplified result can be used to generate the track change output. This result will allow user to accept or reject changes easily.