A state-of-the-art survey on software merging
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: A fast algorithm for computing longest common subsequences

paper_content:

Previously published algorithms for finding the longest common subsequence of two sequences of length n have had a best-case running time of O(n 2 ). An algorithm for this problem is presented which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match. Thus in the worst case the algorithm has a running time of O(n 2 log n). However, for those applications where most positions of one sequence match relatively few positions in the other sequence, a running time of O(n log n) can be expected.
---
paper_title: Computer-Aided Software Engineering in a distributed workstation environment

paper_content:

Computer-Aided Software Engineering environments are becoming essential for complex software projects, just as CAD systems have become essential for complex hardware projects. DSEE, the DOMAIN Software Engineering Environment, is a distributed, production quality, software development environment that runs on Apollo workstations. DSEE provides source code control, configuration management, release control, advice management, task management, and user-defined dependency tracking with automatic notification. ::: DSEE incorporates some of the best ideas from existing systems. This paper describes DSEE, contrasts it other systems, and discusses some of the technical issues involved in the construction of a highly-reliable, safe, efficient, and distributed development environment.
---
paper_title: Computer supported cooperative software engineering with Beyond-Sniff

paper_content:

Teamwork is a prerequisite for the development of large complex software systems. In conventional software engineering coordination of teamwork is achieved by exchanging formal documents and by providing support for keeping these documents consistent even while several developers are evolving them. In order to support teamwork more effectively it is important to move the focus beyond coordination towards cooperation. The goal of the Beyond-Sniff project is to provide cooperation support in three ways. First, by providing a terminological and conceptional foundation for the field of cooperative software engineering. Second, by developing tools for computer supported cooperative software engineering. Third, by developing a platform for control and data integration, a technical prerequisite for computer supported cooperative software engineering. >
---
paper_title: How to Merge Program Texts

paper_content:

Abstract Software usually exists in multiple versions. All these versions must evolve in parallel. We propose a program-merging system that helps programmers to manage the evolution of all versions, which is much needed in software development and maintenance environments. The system can either combine two programs or it can combine changes to a base program. The system consists of three stages: a syntax-based comparator, a synchronous printer and a merging editor. Based on the differences between the two programs identified by the syntax-based comparator, the synchronous printer combines the texts of two programs. Because there may be conflicts between the two programs, a merging editor provides the user with commands to resolve the conflicts. Another distinct feature of the merging system is the generator approach to producing syntactic program comparators for new programming languages.
---
paper_title: Program integration for languages with procedure calls

paper_content:

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
---
paper_title: Integrating non-intering versions of programs

paper_content:

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. The main contribution of this 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 .
---
paper_title: Program Restructuring as an Aid to Software Maintenance

paper_content:

Maintenance tends to degrade the structure of software, ultimately making maintenance more costly. At times, then, it is worthwhile to manipulate the structure of a system to make changes easier. However, it is shown that manual restructuring is an error-prone and expensive activity. By separating structural manipulations from other maintenance activities, the semantics of a system can be held constant by a tool, assuring that no errors are introduced by restructuring. To allow the maintenance team to focus on the aspects of restructuring and maintenance requiring human judgment, a transformation-based tool can be provided--based on a model that exploits preserving data flow-dependence and control flow-dependence--to automate the repetitive, error-prone, and computationally demanding aspects of restructuring. A set of automatable transformations is introduced; their impact on structure is described, and their usefulness is demonstrated in examples. A model to aid building meaning-preserving restructuring transformations is described, and its realization in a functioning prototype tool for restructuring Scheme programs is discussed.
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: Program integration for languages with procedure calls

paper_content:

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
---
paper_title: Integrating non-intering versions of programs

paper_content:

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. The main contribution of this 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 .
---
paper_title: Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory

paper_content:

From the Publisher: ::: "First book-length exposition of the denotational (or `mathematical' or `functional') approach to the formal semantics of programming languages (in contrast to `operational' and `axiomatic' approaches). Treats various kinds of languages, beginning with the pure-lambda-calculus and progressing through languages with states, commands, jumps, and assignments. This somewhat discursive account is a valuable compilation of results not otherwise available in a single source." ::: ::: -- American Mathematical Monthly
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: Object-Oriented Software Engineering Conquering Complex and Changing Systems

paper_content:

From the Publisher: ::: This book is based on object-oriented techniques applied to software engineering. Employing the latest technologies such as UML, Patterns, and Java, Bernd Bruegge and Allen H. Dutoit offer a cohesive, class-tested presentation of object-oriented software engineering in a step-by-step format based on ten years of teaching and real-world software engineering experience. This text teaches practical experience in developing complex software appropriate for software engineering project courses, as well as industry R & D practitioners. The reader benefits from timely exposure to state-of-the-art tools and methods. ::: ::: Unlike other texts based on the teaching premise of multiple classes or developing multiple systems, this book focuses on techniques and applications in a reasonably complex environment, such as multi-team development projects including 20 to 60 participants. The book is based on concrete examples from real applications such as accident management, emissions modeling, facility management, and centralized traffic control. ::: ::: Provides an integrated communication infrastructure for distributed development ::: Shows the state of the art in Software Engineering: UML, Java, Design Patterns, Distributed Development, and Multiproject Management ::: Illustrates how the reader learns to develop in a distributed team with hands-on experience on real system development problems ::: Offers a CD-ROM containing the materials used in courses taught by the authors-problem statements, requirement analysis documents, system design documents, test manuals, prototypes, and all the artifacts produced during the development of a facility management system ::: Presents Companion Website (www.prenhall.com/bruegge) with supplemental material such as problem statements, requirement analysis documents, system design documents, test manuals, and solutions to exercises
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: The string-to-string correction problem with block moves

paper_content:

The string-to-string correction problem is to find a minimal sequence of edit operations for changing a given string into another given string. Extant algorithms compute a longest common subsequence (LCS) of the two strings and then regard the characters not included in the LCS as the differences. However, an LCS does not necessarily include all possible matches, and therefore does not produce the shortest edit sequence. An algorithm that produces the shortest edit sequence transforming one string into another is presented. The algorithm is optimal in the sense that it generates a minimal covering set of common substrings of one string with respect to another. Two improvements of the basic algorithm are developed. The first improvement performs well on strings with few replicated symbols. The second improvement runs in time and space linear to the size of the input. Efficient algorithms for regenerating a string from an edit sequence are also presented.
---
paper_title: A fast algorithm for computing longest common subsequences

paper_content:

Previously published algorithms for finding the longest common subsequence of two sequences of length n have had a best-case running time of O(n 2 ). An algorithm for this problem is presented which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match. Thus in the worst case the algorithm has a running time of O(n 2 log n). However, for those applications where most positions of one sequence match relatively few positions in the other sequence, a running time of O(n log n) can be expected.
---
paper_title: The source code control system

paper_content:

The Source Code Control System (SCCS) is a software tool designed to help programming projects control changes to source code. It provides facilities for storing, updating, and retrieving all versions of modules, for controlling updating privileges for identifying load modules by version number, and for recording who made each software change, when and where it was made, and why. This paper discusses the SCCS approach to source code control, shows how it is used and explains how it is implemented.
---
paper_title: The source code control system

paper_content:

The Source Code Control System (SCCS) is a software tool designed to help programming projects control changes to source code. It provides facilities for storing, updating, and retrieving all versions of modules, for controlling updating privileges for identifying load modules by version number, and for recording who made each software change, when and where it was made, and why. This paper discusses the SCCS approach to source code control, shows how it is used and explains how it is implemented.
---
paper_title: The source code control system

paper_content:

The Source Code Control System (SCCS) is a software tool designed to help programming projects control changes to source code. It provides facilities for storing, updating, and retrieving all versions of modules, for controlling updating privileges for identifying load modules by version number, and for recording who made each software change, when and where it was made, and why. This paper discusses the SCCS approach to source code control, shows how it is used and explains how it is implemented.
---
paper_title: Program integration for languages with procedure calls

paper_content:

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
---
paper_title: Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory

paper_content:

From the Publisher: ::: "First book-length exposition of the denotational (or `mathematical' or `functional') approach to the formal semantics of programming languages (in contrast to `operational' and `axiomatic' approaches). Treats various kinds of languages, beginning with the pure-lambda-calculus and progressing through languages with states, commands, jumps, and assignments. This somewhat discursive account is a valuable compilation of results not otherwise available in a single source." ::: ::: -- American Mathematical Monthly
---
paper_title: Program integration for languages with procedure calls

paper_content:

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
---
paper_title: Integrating non-intering versions of programs

paper_content:

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. The main contribution of this 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 .
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: How to Merge Program Texts

paper_content:

Abstract Software usually exists in multiple versions. All these versions must evolve in parallel. We propose a program-merging system that helps programmers to manage the evolution of all versions, which is much needed in software development and maintenance environments. The system can either combine two programs or it can combine changes to a base program. The system consists of three stages: a syntax-based comparator, a synchronous printer and a merging editor. Based on the differences between the two programs identified by the syntax-based comparator, the synchronous printer combines the texts of two programs. Because there may be conflicts between the two programs, a merging editor provides the user with commands to resolve the conflicts. Another distinct feature of the merging system is the generator approach to producing syntactic program comparators for new programming languages.
---
paper_title: How to Merge Program Texts

paper_content:

Abstract Software usually exists in multiple versions. All these versions must evolve in parallel. We propose a program-merging system that helps programmers to manage the evolution of all versions, which is much needed in software development and maintenance environments. The system can either combine two programs or it can combine changes to a base program. The system consists of three stages: a syntax-based comparator, a synchronous printer and a merging editor. Based on the differences between the two programs identified by the syntax-based comparator, the synchronous printer combines the texts of two programs. Because there may be conflicts between the two programs, a merging editor provides the user with commands to resolve the conflicts. Another distinct feature of the merging system is the generator approach to producing syntactic program comparators for new programming languages.
---
paper_title: The string-to-string correction problem with block moves

paper_content:

The string-to-string correction problem is to find a minimal sequence of edit operations for changing a given string into another given string. Extant algorithms compute a longest common subsequence (LCS) of the two strings and then regard the characters not included in the LCS as the differences. However, an LCS does not necessarily include all possible matches, and therefore does not produce the shortest edit sequence. An algorithm that produces the shortest edit sequence transforming one string into another is presented. The algorithm is optimal in the sense that it generates a minimal covering set of common substrings of one string with respect to another. Two improvements of the basic algorithm are developed. The first improvement performs well on strings with few replicated symbols. The second improvement runs in time and space linear to the size of the input. Efficient algorithms for regenerating a string from an edit sequence are also presented.
---
paper_title: Program integration for languages with procedure calls

paper_content:

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
---
paper_title: Integrating non-intering versions of programs

paper_content:

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. The main contribution of this 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 .
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---
paper_title: Program integration for languages with procedure calls

paper_content:

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.
---
paper_title: Integrating non-intering versions of programs

paper_content:

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. The main contribution of this 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 .
---
paper_title: A formal foundation for object-oriented software evolution

paper_content:

My PhD thesis claims that the principles behind object-oriented software evolution are independent of a particular domain or phase in the software lifecycle. To validate this claim, a formalism based on graphs and graph rewriting was developed and applied to a particular aspect of software evolution, namely the problem of software upgrading and software merging. When the same piece of software is modified in parallel by different software developers, unexpected inconsistencies can arise. Formal support can be provided to detect and resolve these inconsistencies in a general way.
---

Title: A State-of-the-Art Survey on Software Merging

Section 1: Introduction
Description 1: Introduce the necessity and challenges of software merging, particularly in the context of large-scale software development and configuration management.

Section 2: Overview of Merge Techniques
Description 2: Provide a comprehensive overview of various merge techniques reported in the literature and categorize them along different dimensions.

Section 3: Merge Conflicts
Description 3: Discuss different types of inconsistencies that can arise during a merge, including syntactic, structural, and semantic conflicts, and look into their detection and resolution methods.

Section 4: Delta Algorithms
Description 4: Examine delta algorithms used for calculating differences between software versions and discuss how they are related to various merge techniques.

Section 5: Design Criteria
Description 5: Explore the different design criteria influencing the development of a merge tool, such as formality, accuracy, domain independence, granularity, scalability, efficiency, and customizability.

Section 6: Conclusion and Research Directions
Description 6: Conclude the survey, summarizing the main findings and suggesting directions for future research in the field of software merging.