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:

•	AccuRev analyzes two contributor versions of a file, along with a third version designated as the closest common ancestor of the two contributors.

•

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:

•	Using a third-party tool for merge, patch, and reverse patch operations

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.

•	Merging, patching, and reverting namespace changes

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.	Workspace version (appears in lower right pane of Merge tool)

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.

•	In this case, the new version is created in the workspace from which you launched the version tool. It's listed in the status bar at the bottom of the GUI window.

•	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.	Stream version (appears in lower left pane of Merge tool)

This is also called the "from" version.

•	In the most common merge scenario, this is the version in the workspace's backing stream.

•	If you're using one of the version tools, this is the version on which you invoked Merge From or Patch From.

•	In the Change Palette, this is the version in the "source stream".

3.	Closest common ancestor version (not displayed in Merge tool)

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:

•	Workspace File vs. Workspace Version

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.

•	How can I tell which is the closest common ancestor? How will the results of the merge appear in the Version Browser?

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:

•	If those 13 lines exist in the ancestor version, the Merge tool concludes that a change was made in contributor #1 (the lines were deleted) but no change was made in contributor #2 (the lines are still there).

•	If the 13 lines do not exist in the ancestor version, the Merge tool concludes that a change was made in contributor #2 (the lines were added) but no change was made in contributor #1 (nothing was added).

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:

•	Contributor #1:

#define E_COLOR498 "No color with that name was found."

•	Contributor #2:

#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:

•	The lower right pane contains the version in your workspace.

•	The lower left pane contains the stream (or "from") version -- the version, located in some other stream, that you selected when invoking Patch From.

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 in the patch, patching works in exactly the same way as merging. This means that it is possible (and perhaps automatic) that the "from" version's change will be included in the results of the Patch From.

•

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:

•	When reverting a transaction, AccuRev regards each version in that transaction as being the head version of a patch, and removes all the changes in that patch from the element.

•	When reverting a change package, AccuRev removes all the changes in each element's change package entry.

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.

•	The lower left pane contains the version currently in the stream.

•	The lower right pane contains the version that was in the stream just before the version being reverted was promoted there.

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: