Method for performing conditionalized N-way merging of source code

• US 8,719,786 B2
• Filed: 03/30/2005
• Issued: 05/06/2014
• Est. Priority Date: 03/30/2005
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Waddington, Daniel G.
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): Wu, Junchun
• Application Number:
  US11/093,517
• Publication Number:
  US 20060225040A1
• Time in Patent Office: 3,324 Days
• Field of Search: 717/122
• US Class Current: 717/122
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management

Abstract

A method combines N versions of a C/C++ program into a single, semantically correct, unified program, while maintaining the semantics of each version within N. The problem of merge conflicts is avoided by conditionalizing changes that potentially conflict, according to a set of preprocessors definitions that uniquely define the version within N. Conditionalization is realized through C/C++ preprocessing directives (e.g., #if, #else, #elif).

Claims

1. A method for performing conditionalized N-way merging of source code associated with a program, comprising:

collecting differential information for each of N versions of source code, the source code having lines of text;

constructing a merge data structure using the differential information, the merge data structure comprising a plurality of common blocks and delta blocks, wherein each common block defines a respective sequence of textual lines of source code, each delta block defines an addition or deletion or change to a corresponding common block, each common block and delta block being associated with a respective set of exclusionary definitions indicative of any source code versions not including the respective block; and

merging the N versions into a single, semantically correct, unified version of source code associated with the program using the merge data structure, the single, semantically correct, unified version of source code associated with the program having preprocessing conditionals adapted to identify differences between the N versions.

2. The method of claim 1, wherein the differential information includes pairwise diffs between each version and the original source code program.

3. The method of claim 1, wherein the constructing the merge data structure comprises:

processing each difference in the differential information by selectively splitting common blocks, selectively adding deltas, and associating sets of versions to each common block and each delta.

4. The method of claim 1, wherein the merging the N versions into the single, semantically correct, unified program comprises:

writing out the textual lines in each common block and each associated delta along with preprocessing conditionals to reflect the sets of versions associated with each common block and each delta.

5. The method of claim 4, wherein one of the N versions is the original source code program.

6. The method of claim 1, wherein each common block comprises textual lines within a respective range of textual lines of an original version of the source code.

10. The method of claim 1, wherein said step of constructing said merge data structure comprises adapting the range of two or more common blocks in response to said differential information to provide thereby appropriate reference points for delta blocks.

11. The method of claim 1, wherein said merging the N versions comprises iteratively processing each of the plurality of common blocks according to the steps of:

(a) if the common block is included within each of the N versions, including the common block without conditions in the unified version of source code; and

(b) if the common block is included within some but not all of the N versions, including the common block with conditions in the unified version of source code.

12. The method of claim 11, wherein iteratively processing each of the plurality of common blocks further comprises:

(c) if the common block is not included within any of the N versions and is not associated with a delta block, not including the common block in the unified version of source code.

13. The method of claim 11, wherein iteratively processing each of the plurality of common blocks further comprises:

(d) if the common block is not included within any of the N versions and is associated with a delta block included within each of the N versions, including the delta block without conditions in the unified version of source code;

(e) if the common block is not included within any of the N versions and is associated with the delta block included within some but not all of the N versions, including the delta block with conditions in the unified version of source code.

14. The method of claim 11, wherein iteratively processing each of the plurality of common blocks further comprises:

(f) if the common block is included in some but not all of the N versions and is associated with a delta block included within each of the N versions, including the delta block without conditions in the unified version of source code,

(g) if the common block is included in some but not all of the N versions and is associated with a delta block included within some but not all of the N versions, including the delta block with conditions in the unified version of source code.

7. The method of claim one, wherein one or more of said common blocks comprise textual lines included in each of the N versions of the source code.

8. The method of claim one, wherein said step of constructing said merge data structure comprises splitting an initial common block representing the original version of the source code into said plurality of common blocks by splitting said initial common block into common blocks comprising textual lines included in each of the N versions of the source code and common blocks comprising textual lines included in only some of the N versions of the source code.

9. The method of claim 8, wherein said splitting of said initial common block is performed by associating respective ranges of textual portions of said initial common block to each of said plurality of common blocks.

15. A system for performing conditionalized N-way merging of source code, comprising:

memory for storing program components; and

a processor for executing the program components, the program components comprising;

a differential collection component for collecting differential information for each of N versions of source code, the source code having lines of text;

a constructor component for constructing a merge data structure using the differential information, the merge data structure comprising a plurality of common blocks and delta blocks, wherein each common block defines a respective sequence of textual lines of source code, each delta block defines an addition or deletion or change to a corresponding common block, each common block and delta block being associated with a respective set of exclusionary definitions indicative of any source code versions not including the respective block; and

a merge component for merging the N versions into a single, semantically correct, unified version of source code associated with the program using the merge data structure, the single, semantically correct, unified version of source code associated with the program having preprocessing conditionals adapted to identify differences between the N versions.

16. A non-transitory computer-readable storage medium having instructions stored thereon for performing a method for performing conditionalized N-way merging of source code, the method comprising:

collecting differential information for each of N versions of source code, the source code having lines of text;

constructing a merge data structure using the differential information, the merge data structure comprising a plurality of common blocks and delta blocks, wherein each common block defines a respective sequence of textual lines of source code, each delta block defines an addition or deletion or change to a corresponding common block, each common block and delta block being associated with a respective set of exclusionary definitions indicative of any source code versions not including the respective block; and

merging the N versions into a single, semantically correct, unified version of source code associated with the program using the merge data structure, the single, semantically correct, unified version of source code associated with the program having preprocessing conditionals adapted to identify differences between the N versions.

17. A system for performing conditionalized N-way merging of source code, the system comprising:

means for collecting differential information for each of N versions of an original source code program, the original source code program having lines of text;

means for constructing a merge data structure from the differential information; and

means for merging the N versions into a single, semantically correct, unified program using the merge data structure, the single, semantically correct, unified program having preprocessing conditionals to represent differences between the N versions.