The Merge, Patch, and Reverse Patch Algorithms
The AccuRev GUI uses the same tool to perform interactive merge An operation that combines the contents of two versions (contributors) of the same element. To merge the contents of text files, AccuRev uses a '3-way merge' algorithm: it compares the two files line-by-line with a third file, the version that is the closest common ancestor of the other two. Merging of namespace changes also takes into account the closest common ancestor. operations, interactive patch A set of versions of a text-file element -- typically, containing the 'recent changes' made in one workspace. Also, the merge-like operation that incorporates those changes into another version of the same element. See merge, basis version, head version, change package, reverse patch. operations, and interactive reverse patch An operation that removes a selected set of changes from the current version of a text-file element. See patch, change package. operations (Revert command) on the contents of a text-file element. In all these operations:
AccuRev analyzes two contributor Either of two versions of an element, which are to be combined in a merge operation, producing a new version of the element. This can involve both content changes and namespace changes. versions of a file, along with a third version designated as the closest common ancestor (of two versions of an element) The most recent version that is an ancestor of two specified versions. Used in a merge operation to minimize the amount of work required to combine the contents of the two specified versions. See merge, version graph. 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 The situation in which both contributors to a merge operation differ from the closest common ancestor at the same text line (or set of lines). Also, the situation in which both contributors have pathnames that differ from the closest common ancestor, and from each other. 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 (click to view):
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 A change to the pathname of a file or directory element: either renaming the element in place or moving the element to a different location in the depot’s directory hierarchy. in addition to (or instead of) content changes A change to the contents of a file element, recorded in a new version created with the keep command. See namespace change.. 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.
Click here for more details.
In a Merge or Merge From command, the analysis performed on the two contributor versions goes beyond a simple diff An operation that compares the contents of two versions of a text-file element.: AccuRev determines how each difference represents a change from the closest common ancestor (of two versions of an element) The most recent version that is an ancestor of two specified versions. Used in a merge operation to minimize the amount of work required to combine the contents of the two specified versions. See merge, version graph. version.
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 the Merge command 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 AccuRev GUI tools that provide access to historical versions of elements. The Version Browser provides easy access to all versions of an element. The History Browser provides access to versions through the transactions in which they were created. The Stream Version Browser provides easy access to the version that currently appears in a given stream.. 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 (parent stream, basis stream) The stream that is just above a given workspace or stream in a depot's stream hierarchy. The given workspace/stream inherits versions from the backing stream..
If you're using one of the version tools AccuRev GUI tools that provide access to historical versions of elements. The Version Browser provides easy access to all versions of an element. The History Browser provides access to versions through the transactions in which they were created. The Stream Version Browser provides easy access to the version that currently appears in a given stream., 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 (click to view):
Workspace File vs. Workspace Version
AccuRev always uses the file in the workspace tree The ordinary directory tree, located in the user’s disk storage, in which the user performs development tasks and executes AccuRev commands. as the first contributor. If you've just saved the file with the Keep command, the file in your workspace is identical to the most recent version in your workspace stream The private stream that is built into a workspace. All new versions of elements are originally created in workspaces; AccuRev records these versions in workspace streams.. But if you've edited the file without Keep'ing it, there's a difference.
In all cases, the version currently in the workspace stream The private stream that is built into a workspace. All new versions of elements are originally created in workspaces; AccuRev records these versions in workspace streams. is used in the determination of the closest common ancestor (of two versions of an element) The most recent version that is an ancestor of two specified versions. Used in a merge operation to minimize the amount of work required to combine the contents of the two specified versions. See merge, version graph. version.
How can I tell which is the closest common ancestor?
In the Version Browser, you can tell by visual inspection. In the AccuRev CLI, use the command anc -c.
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.
Examples (click to view):
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.
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.
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.
In a Patch From command, the two contributor versions are the same as in a Merge command:
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 the Patch From command.
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 The version of an element that, along with a basis version, specifies that element's entry in a change package. Equivalently, the head-version/basis-version pair specifies a patch to that element. of a patch, and uses the corresponding basis version A particular ancestor of the version specified in a Patch, Revert, Diff, or Send to Issue command. The series of versions between the basis version and the specified version constitute the 'recent changes' to be patched into (or removed from) the target. Similarly, a change package entry consists of all the versions between a specified basis version and a specified head version. as the closest common ancestor. (More information: 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 command.
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. [note ]
In a Revert command, the changes in a specified set of versions are removed from a stream's current versions of those elements:
When reverting a transaction A record in the AccuRev repository database that indicates a particular change: promoting of a set of versions, changing the name of a stream, modification to an issue record, etc. Each transaction has an integer transaction number, which is unique within the depot., 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 A set of entries, each in the form of a basis-version/head-version pair, recorded on the Changes tab of an issue record. The change package records the changes to one or more elements, made to implement the feature or bugfix described in that issue record. Each entry in the change package describes changes to one element: the changes between the basis version and the head version. See patch., 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, click here.
For each element it processes, the Revert command 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 the Revert command 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 Promote'd version being reverted) becomes the direct ancestor See predecessor. of the newly created version. The reverted element's Version Browser display shows this relationship: