In a modern multiple developer software engineering environment a software merge utility is used to bring the work of several developers together. It seems like a matter that needs little thought. Many of the merge utilities that come with modern SCM (Software Configuration Management) tools claim to be "automatic", further reinforcing the notion that the software merge issue need not be thought of in great depth - it being dealt with by the merge tool. The fact remains, however, that errors can be insidiously introduced into a software development/release process by the use of "automatic merge" utilities. Errors that could have been easily identified & quickly dealt with during merge operations will end up costing more time & money to isolate & fix later in the software development/release process. If the errors get as far as the end users before being detected, the costs can be devastating.
This paper discusses the software merge process in modern, multi-developer software engineering operations, how and when "automatic merge" utilities work and when and why they fail. The paper suggests ways to eliminate merge induced errors earlier in the software development/release process and thus decrease the delivered cost and time to market of quality software products.
Generally, when one person writes a program, there is no need to "merge" work later -- that one person keeps editing the same file iteratively.
However, larger software projects often employ multiple programmers. Sometimes these projects can be divided up in such a way that no single program or file is modified by more than one programmer. In such a case, merges still are unnecessary. But many systems have more complex interactions between modules. Often there are certain files that are shared by many programmers -- especially files that cover data structures or interfaces between two or more modules. When this happens, there is the possibility of both programmers making different changes to the file at roughly the same time. Since there is only one file, only the last set of changes will be kept, and earlier sets will be lost -- much to the chagrin of the programmer who wrote them and saved them.
To prevent this problem, programming organizations often introduce policies. One of the simplest such policies is called "check out/check in". This policy requires that no programmer can work on a file that is already being worked upon (i.e. checked out) by another programmer, until that other programmer finishes testing their work and saves the result (i.e. checks it in). At that point the second programmer checks out the revised version, ensuring that none of the previous work is lost. Such policies can be managed informally (i.e. "ask everyone before editing a file") or they can be enforced by tools. Typical tools for such work are RCS and SCCS.
As should be obvious, one draw back to the check out/check in approach is that it serializes work. One programmer may be stopped, waiting until another programmer checks in a key file. Programming thus goes not at the pace of the average programmer, but at the pace of the slowest programmer -- or worse at the pace of the sum of the lengthiest of several programming tasks.
In some professions this would not be a big concern. However, programming typically does not have a reputation for being delivered early. More typically it is delivered late, and the expected opportunity cost to delayed product releases are usually considered to be high. So many programming shops have looked at ways to parallelize their development.
In addition to this reason for parallelizing development, there are also many times where a company chooses to work on two releases simultaneously -- perhaps one for immediate bug fixes, and another for longer term enhancements. Or perhaps one to be hosted on Unix and another on Windows. Or perhaps there is a partnership with an OS vendor and serveral peripheral vendors. In such situations, check out/check in scenarios are considered inappropriate because of their serialization effect.
The typical approach to solving this problem is called branching. A common "ancestor" set of files is chosen and copies are made for each branch. Then individual programmers (or groups) can work on changes to their copies without interfering with the other programmers or groups.
This is great as long as the two branches never need to be resynchronized. However that is rarely the case. While the bug fix release may be ready first and released first, it would not be acceptable to follow it with a later release with the new functionality of the parallel branch -- but which reintroduced the old bugs.
To avoid this, a process called "merging" is employed. Each branch file is compared (also known as "differenced" or "diffed") against the original ancestor. From these differences it is possible to deduce what changes were made to create the new branch file from the ancestor. By applying the changes (also known as change sets) from each branch to a common ancestor, it is hoped that a new file will result that has both sets of changes.
In practice this works very well. In a large majority of the cases, the changes made by the programmers are so independent that no conflicts arise from this process. Of the remaining cases, most have conflicts that are so obvious that it is trivial to spot them even with "automated" programs. These cases require human intervention because of the conflicts and a programmer is then called in to examine both change sets and mediate between the two.
If this were the end of the story, there would be no reason for this paper, or for a product like MergeRight. But unfortunately there is more to the story. In addition to the set of "safe" merges, and the set of "obviously unsafe" merges there is an insidious case of "subtly unsafe" merges, a case where automated programs don't recognize that the very act of merging is introducing errors not present in either of the branch files.
This is admittedly rare. In days past, software was often like playing horseshoes: It was good enough to be close to the goal. Buggy software was considered unavoidable, and getting a program that works more often than not was considered a feat. In such situations, a problem of this rarity was often ignored.
Now, however, there are many environments where extremely high levels of software accuracy are required. These include medical software, telecommunications switching and much commercial software. Large expenses are incurred to QA software to ensure defects don't occur, or at least don't get out to the customers where support and warrantee costs can be expensive. Software Quality cultures now often emphasize error prevention and early detection, rather than merely gargantuan QA departments. MergeRight was designed for such organizations, as it helps spot these subtle merge problems before they occur and allows programmer to intervene earlier to prevent them from winding up in merged software where they might be harder to detect.
This paper explains how such subtle merge problems can happen in any parallel development using an automatic merge scenario.
When two files are 3-way merged, one of four cases are possible:
Case 1 is easy to recognize and is automated by both MergeRight and other file merges. Case 1 cannot inject undetected errors.
Case 4 REQUIRES operator intervention whether an "automatic" tool is used or not, as no merge tool can tell which set of these changes to use, or even if additional editing is required. Other merge tools will "automatically" merge the changes from both files and then leave the indicated overlap commands to be found and resolved in a later editing operation "manually". MergeRight makes these areas "jump out". Graphical editing capabilities integrated into MergeRight make it fast & easy to fix these problems as they are detected, when the software engineer's awareness of the problem and the possible correct solutions is optimum.
"Automatic" merges ignore a very real problem that can occur with Type 2 and Type 3 merges. Because the changes are non-overlapping, they are treated by other "automatic" merge tools as though there cannot be any problems introduced by just accepting the changes from each side. Initially it seems easy to confidently accept this logic. Unfortunately, this is not always true. It was precisely in recognition of this class of errors, made in confidence during "automatic merges", that MergeRight was created.
The problem of Type 2 and Type 3 merges occurs when code lines are moved from one place
in a file to another, or when lines appear multiple times (e.g. for {i=0,i++,I}
The good news is that this doesn't happen very often. But that's also the bad news, however, since it can take a lot of effort to catch these problems after they have been automatically generated.
The MergeRight strategy is to make it easy to check whether this type of problem has occurred within seconds of a requested file merge. If the requsted merge is benign and not one of the 5% dangerous merge types, a "select all recommendations" button provided by MergeRight does what an automated merge utility would have done. But in the cases where there is such a problem, the use of side-by-side windows, color schemes, and hidden common areas in MergeRight makes it far more likely that a software engineer will notice these kinds of syntax problems and thus prevent them BEFORE they are saved.
Assuming, as is typical, that of 100 file merges where at least one file has changed, 20 files will probably be overlapping, 75 non-overlapping can be safely automatically merged, and 5 non-overlapping files will be dangerously merged.
The 20 files will take some time to manually resolve. MergeRight has a built in editor with easy copy, cut, paste and navigation features designed for the kinds of problems that happen in resolving such conflicts. Some editors have special capabilities as well, so let's assume for the sake of argument that the integrated editing capabilies of MergeRight conveys no benefit over later editing in another editor.
That leaves the 80% that are non-overlapping. In the "automatic merge" case, these would appear to have been merged nearly instantaneously. And if we can live with the 5 files in error that will have resulted, then this will appear to be quicker. But if not, when we compare to the "automatic merge" situation, we see that using MergeRight and "select all recommendations" adds a few seconds to checking each file, adding at most a few minutes to checking the 75% files. And in those few minutes, the dangerous 5% are more likely to be easily found and fixed before they have a chance to become problems detected later in your software development/release process.
But we can't tell which are the 75% and which are the 5%. So now all 80% of the files have to be checked. How long does it take to check each file AFTER the merge has been invisibly done? Well that's much more difficult and time consuming than making sure in advance that the recommended merge will be safe. So, to be safe, more time is spent checking ALL of the non-overlapping files anyway, or more time is spent in QA hoping the errors will be found in test.
Truthfully, the likelihood of such dangerous merges varies from programming shop to programming shop. So does the cost of errors. In some commercial areas like telephone switches the cost of an undetected error introduced during a merge operation is very high. In some academic situations there may be no cost whatsoever.
In our experience,
the greater the likelihood of dangerous merges. In some multiple partner source exchanges these can be as high at 50%! In some single programmer shops working on small new programs, there may not be any such dangerous situations at all.
Returning to the initial point about "automatic merges" vs. "manual merges", and considering the points discussed above, it might be more accurate and meaningful to describe them as "manual (postmerge) checking" vs. "computer supported (premerge) checking". Which view we take as being the most cost effective depends a lot on our expected frequency of dangerous overlaps & the downsteam costs of undetected or accepted "automatic merge" induced errors.
An illustrative example of an error induced by an "automatic Merge" of non-overlapping changes:
(The following example is simplified in order to make the principles discussed above clear. A more realistic example, still quite simple, but more useful for actual testing with different merge tools is also available, by referring to the file links).
/* matching stuff 1*/
/* matching stuff 2*/
/* matching stuff 3*/
/* matching stuff 4*/
/* matching stuff 1*/
I := 1; /* from file 1 */
/* matching stuff 2*/
J := 10; /* from file 1 */
/* matching stuff 3*/
K := I*J;
/* matching stuff 4*/
/* K should equal 10 */
/* matching stuff 1*/
J := 1; /* from file 2 */
/* matching stuff 2*/
I := 10; /* from file 2 */
/* matching stuff 3*/
K := I*J;
/* matching stuff 4*/
/* K should equal 10 */
The result of "automatic merge" is that the user is told that there are no conflicts, and generates:
/* matching stuff 1*/
I:=1; /* from file 1 */
J := 1; /* from file 2 */
/* matching stuff 2*/
I := 10; /* from file 1 */
J := 10; /* from file 2 */
/* matching stuff 3*/
K := I*J;
/* matching stuff 4*/
/* K should equal 10 */
Note that in the result file, K should equal 10, but instead *will* equal 100, which is not an expected result in either File 1 or File 2. Clever diff algorithms MAY cause this to be flagged as an overlap, but all diff algorithms have a "match window" (typically a few lines). If the "matching stuff" exceeds that window, all diff and merge utilities will generate the above kinds of semantically incorrect (though syntactly correct) result files. Once that happens, compilers won't find this error for you either, since, even though I and J have both been reassigned, that's a semantic error to the compiler, not a syntactic one. Interested readers may want to test their merge programs themselves using the linked files provided.
Scott McGregor, a founder of Prescient Software, Inc. has over 20 years experience developing and managing software products. McGregor has developed commercial configuration software products for HP and Atherton Technology, and was Director of Software Engineering Services at Sybase. He lead the design team for the predecessor for MergeRight, Merge Ahead, which was showcased on front page of Sun World magazine at introduction. The Sun World reviewer also celebrated the product’s extreme ease of learning. McGregor was recognized by David Flack (Editor, Unix World) for pioneering work in prescient agent technology. The Practical Programmer column of Communications of the ACM also praised McGregor's SWIFT development methodology which shortened development time as much as 70%. McGregor is a widely published author of technical articles. He has also served as an Instructor for technology and management courses at University of California, Berkeley and UC, Santa Cruz including Design for Usability and Project Risk Management.
Author's email address: mcgregor@prescient.com
For More Information Contact:
CompanyLongName
CompanyAddress
Tel: CompanyPhone
CompanyAddress
Tel: CompanyPhone
FAX: CompanyFAX
Internet: CompanyEmail