In version control, merging (also called integration) is a fundamental operation that reconciles multiple changes made to a version-controlled collection of files. Most often, it is necessary when a file is modified on two independent branches and subsequently merged. The result is a single collection of files that contains both sets of changes.
In some cases, the merge can be performed automatically, because there is sufficient history information to reconstruct the changes, and the changes do not conflict. In other cases, a person must decide exactly what the resulting files should contain. Many revision control software tools include merge capabilities.
Types of merges
There are two types of merges: unstructured and structured.
Unstructured merge
Unstructured merge operates on raw text, typically using lines of text as atomic
units. This is what Unix tools (diff/patch) and CVS tools (SVN, Git) use. This is limited, as a line of text does not represent the structure of source code.
Structured merge
Structured merge tools, or AST merge, turn the source code into a
fully resolved AST. This allows for a fine-grained merge that avoid spurious conflicts.
Workflow
Automatic merging is what version control software does when it reconciles changes that have happened simultaneously (in a logical sense). Also, other pieces of software deploy automatic merging if they allow for editing the same content simultaneously. For instance, Wikipedia allows two people to edit the same article at the same time; when the latter contributor saves, their changes are merged into the article instead of overwriting the previous set of changes. Manual merging is what people have to resort to (possibly assisted by merging tools) when they have to reconcile files that differ. For instance, if two systems have slightly differing versions of a configuration file and a user wants to have the good stuff in both, this can usually be achieved by merging the configuration files by hand, picking the wanted changes from both sources (this is also called two-way merging). Manual merging is also required when automatic merging runs into a change conflict; for instance, very few automatic merge tools can merge two changes to the same line of code (say, one that changes a function name, and another that adds a comment). In these cases, revision control systems resort to the user to specify the intended merge result.
Merge algorithms
There are many different approaches to automatic merging, with subtle differences. The more notable merge algorithms include three-way merge, recursive three-way merge, fuzzy patch application, weave merge, and patch commutation.
Three-way merge
A three-way merge is performed after an automated difference analysis between a file "A" and a file "B" while also considering the origin, or common ancestor, of both files "C". It is a rough merging method, but widely applicable since it only requires one common ancestor to reconstruct the changes that are to be merged. Three way merge can be done on raw text (sequence of lines) or on structured trees.
The three-way merge looks for sections which are the same in only two of the three files. In this case, there are two versions of the section, and the version which is in the common ancestor "C" is discarded, while the version that differs is preserved in the output. If "A" and "B" agree, that is what appears in the output. A section that is the same in "A" and "C" outputs the changed version in "B", and likewise a section that is the same in "B" and "C" outputs the version in "A".
Sections that are different in all three files are marked as a conflict situation and left for the user to resolve.
Three-way merging is implemented by the ubiquitous diff3 program, and was the central innovation that allowed the switch from file-locking based revision control systems to merge-based revision control systems. It is extensively used by the Concurrent Versions System (CVS).
Recursive three-way merge
Three-way merge based revision control tools are widespread, but the technique fundamentally depends on finding a common ancestor of the versions to be merged.
There are awkward cases, particularly the "criss-cross merge", where a unique last common ancestor of the modified versions does not exist.