The need to integrate several versions of a program into a common one arises frequently, but it is a tedious and time consuming task to integrate programs by hand. Anyone who has had to reconcile divergent lines of development will recognize the problem and identify with the need for automatic assistance. This paper concerns the design of a tool for automatically integrating program versions. The main contribution of the paper is an algorithm, called Integrate, that takes as input three programs A, B, and Base, where A and B are two variants of Base. Whenever the changes made to Base to create A and B do not "interfere" (in a sense defined in the paper), Integrate produces a program M that integrates A and B.

The method is based on the assumption that any change in the behavior, rather than the text, of Base's variants is significant and must be preserved in M. Although it is undecidable to determine whether a program modification actually leads to such a difference, it is possible to determine a safe approximation by comparing each of the variants with Base. To determine this information, we employ a program representation that is similar, but not identical, to the program dependence graphs that have been used previously in vectorizing compilers.

To the best of our knowledge, the code-integration problem has not been previously formalized. It should be noted, however, that the integration problem examined here is a greatly simplified one; in particular, we assume that expressions contain only scalar variables and constants, and that the only statements used in programs are assignment statements, conditional statements, and while-loops.

CR Categories and Subject Descriptors: D.2.2 [Software Engineering]: Tools and Techniques -- programmer workbench; D.2.3 [Software Engineering]: Coding -- program editors; D.2.6 [Software Engineering]: Programming Environments; D.2.7 [Software Engineering]: Distribution and Maintenance -- enhancement, restructuring, version control; D.2.9 [Software Engineering]: Management -- programming teams, software configuration management; D.3.4 [Programming Languages]: Processors

General Terms: Algorithms, Design

Additional Key Words and Phrases: program integration, non-interfering versions, propagating enhancements, program dependence graph, program slicing, data-flow analysis, control dependency, data dependency

(Click here to access the paper: PostScript, PDF.)