7. Diff, Merge, Patch, and the Change Palette : The Merge, Patch, and Reverse Patch Algorithms

The Merge, Patch, and Reverse Patch Algorithms
The AccuRev GUI uses the same tool to perform interactive merge operations, interactive patch operations, and interactive reverse patch operations (Revert) on the contents of a text-file element. In all these operations:
The two contributor versions' contents are combined to produce a new version of the file, which is saved in the repository with a Keep command. Sometimes, the new version can be produced completely automatically; other times, you have to interactively resolve conflicts between the contributor versions.
The only differences among the several operations are in which versions are designated to be the contributors and the closest common ancestor. These differences are detailed below.
Notes:
By default, merge, patch, and reverse patch operations are performed by AccuRev's own Merge tool. If you configure a third-party text-file-merge tool, it will be used for all these operations. The algorithm used by the third-party tool is not necessarily the same as that used by AccuRev's Merge tool.
Any merge, patch, or reverse patch operation can involve namespace changes in addition to (or instead of) content changes. AccuRev compares the pathnames of the two contributor versions, and in some cases applies a pathname change with the Rename command. If both a Rename and a Keep are performed, the Rename transaction comes first.
See Resolving Namespace Conflicts for more details.
Merge: Incorporating Content Changes
In a Merge or Merge From operation, the analysis performed on the two contributor versions goes beyond a simple diff: AccuRev determines how each difference represents a change from the closest common ancestor version. (To emphasize the Merge tool's perspective, we use the term “change section” to describe a location where the contributors differ from each other. In the context of the Diff tool, we use the term “difference section”.)
Versions in a 3-Way Merge
The versions of an element that figure in AccuRev's 3-way merge algorithm are:
1.
This is also called the "to" version. The merge results will be saved as a new version in some workspace, replacing the version displayed in this pace. Which workspace is the new version created in?
In the most common merge scenario, you invoke Merge in a File Browser open on a particular workspace. The new version is created in that workspace.
You can invoke Merge From or Patch From in any of the version tools.
If you invoke Merge from the Change Palette, you are prompted to specify a workspace in which to perform the merge. The new version is created in that workspace.
2.
This is also called the "from" version.
3.
AccuRev takes into account previous merge operations, but not previous patch operations, in determining the closest common ancestor of the workspace version and the stream version.
Notes:
AccuRev always uses the file in the workspace tree as the first contributor. If you've just saved the file with Keep, the file in your workspace is identical to the most recent version in your workspace stream. But if you've edited the file without Keeping it, there's a difference.
In all cases, the version currently in the workspace stream is used in the determination of the closest common ancestor version.
In the Version Browser, you can identify the common ancestor by visual inspection. In the AccuRev CLI, use the command anc -c. The results of the merge will appear differently in the Version Browser if you are merging with a version from the backing stream than they will if you merge with a non-backing stream version. Consider the following examples:
The example above shows the most common case: merging the file with your modifications in your workspace (A) with a version with different changes in the backing stream (B). The closest common ancestor for A and B is C. This is considered a “rebase” merge, and the result appears as follows:
A new version is created (D) for the merged content. Note that in this case no red merge line is displayed. Instead, the merge is noted in the in the comments and in the tooltip which appears when you hover over the resulting version at D.
If you merge with a version that is not in the backing stream, the common ancestor is still easy to determine:
Again, the file with your modifications in your workspace is at (A). The version with different changes in a different stream is at (B). The closest common ancestor for A and B is C.
And again, the result of the merge is a new version shown at D. But note that for this more complex merge, AccuRev indicates the merge process with a red line. (In versions prior to 4.9.1, all merges -- including rebase merges-- were displayed with this red line.
Handling Change Sections
AccuRev processes each change section by comparing (1) the workspace version's content, (2) the stream version's content, the closest common ancestor's content:
Non-conflicting change: Only one contributor — either the 'from' version or the 'to' version — changed the content in the section; the other contributor didn't make a change. AccuRev automatically includes the change in the merged version.
Conflicting change: Both contributors changed the content in the section. AccuRev highlights the section in yellow; you must resolve the conflict by selecting one contributor's change to be included in the merged version.
Identical change: Both contributors changed the content in the section in exactly the same way. AccuRev doesn't flag this section at all; the agreed-upon change is automatically included in the merged version.
Example 1: non-conflicting change
Suppose a change section consists of 13 lines that occur in contributor #2 but not in contributor #1. To determine what kind of change this represents, the Merge tool looks at the corresponding location in the closest common ancestor version:
In both these cases, there was a change from the common ancestor in exactly one of the contributors. The Merge tool deems this a "non-conflicting change". It incorporates the change (be it an addition, a deletion, or a revision of existing text) into the merged version.
Example 2: conflicting change
Let's take another example. A one-line error message has a slightly different wording in the two contributors:
#define E_COLOR498 "No color with that name was found."
#define E_COLOR498 "Color name unknown."
The following line occurs at the corresponding location in the closest common ancestor version:
#define E_COLOR498 "Huh?"
In this situation, the Merge tool finds a change from the common ancestor in both contributors, not just one of them. This is a "conflicting change" (or more simply, a "conflict"). The Merge tool doesn't try to decide which contributor's change is better. It just makes it easy for you to make this decision when you perform the merge.
Example 3: identical change
It sometimes happens that both contributors have made the same change from the common ancestor version. For example, both contributors might have replaced this error message:
Huh?
with this one:
No such color
The Merge tool does not identify this as a difference section, because there's no difference between the two contributors. It silently incorporates the agreed-upon change into the merged version.
Patch: Incorporating Content Changes
In Patch From, the two contributor versions are the same as in a Merge:
But the patch algorithm does not use the actual closest common ancestor of these two contributors as the third version. Instead, it regards the stream version as being the head version of a patch, and uses the corresponding basis version as the closest common ancestor. (See Structure of a Patch.)
Using the basis version instead of the actual closest common ancestor effectively modifies the algorithm for handling change sections, enabling AccuRev to distinguish changes that are "in the patch" from changes made in other versions:
If a change in the "from" version is not in the patch, it is ignored -- the workspace version's change is automatically included in the results. (Why automatically? This case fits the definition of a non-conflicting change: "not in the patch" means that the text in the stream version is the same as the text in the basis version (playing the role of closest common ancestor). Since only one contributor, the workspace version, has a change that differs from the version designated as the closest common ancestor, that contributor's change is accepted automatically.)
Reverse Patch: Removing Content Changes
In a Revert, the changes in a specified set of versions are removed from a stream's current versions of those elements:
For more information on the structure of a patch and a change package entry, see Patch and Patch From.
For each element it processes, Revert uses the AccuRev Merge tool (or user-configured tool) to perform the operation that removes a set of changes from the current version. We use the term reverse patch to describe this process, but it's really just another instance of effectively modifying the merge algorithm by switching around the versions.
When the Merge tool is invoked by Revert:
The version you selected when invoking Revert is designated to be the closest common ancestor.
In this algorithm's switching around of the versions, the basis version of the change package entry being reverted (or the basis version corresponding to the promoted version being reverted) becomes the direct ancestor of the newly created version. The reverted element's Version Browser display shows this relationship:

Micro Focus