The Merge, Patch, and Reverse Patch Algorithms

Merge: Incorporating Content Changes

Versions in a 3-Way Merge

Handling Change Sections

Patch: Incorporating Content Changes

Reverse Patch: Removing Content Changes

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:

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

Merge: Incorporating Content Changes

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 To emphasize the Merge tool's perspective, we use the term change section In a merge operation, a location where the two contributors being merged differ from each other. (In a diff operation, these are called difference sections.) The Merge tool highlights and counts the change sections. It also tracks the conflicting changes (conflicts) — the subset of change sections in which both contributors differ from the closest common ancestor. Conflicts must be resolved by human intervention. to describe a location where the contributors differ from each other. In the context of the Diff tool, we use the term difference section In a text-file-comparison operation, a location where the two files (or two versions of the same file) differ from each other. The Diff tool highlights and counts the difference sections. See "change section".. 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.

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?

2. Stream version (appears in lower left pane of Merge tool)

This is also called the "from" version.

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

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:

Examples (click to view):

Patch: Incorporating Content Changes

In a Patch From command, the two contributor versions are the same as in a Merge 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:

Reverse Patch: Removing Content Changes

In a Revert command, 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, 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:

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: