Semantics-based composition of class hierarchies

• US 7,137,104 B2
• Filed: 05/21/2002
• Issued: 11/14/2006
• Est. Priority Date: 05/21/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Snelting, Gregor, Tip, Frank
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): YIGDALL, MICHAEL J
• Application Number:
  US10/153,055
• Publication Number:
  US 20030221182A1
• Time in Patent Office: 1,638 Days
• Field of Search: 717/107, 717/108, 717/116, 717/165, 717/131, 717/143, 717/154, 717/124, 717/126
• US Class Current: 717/126
• CPC Class Codes: G06F 8/36 Software reuse
• CPC Class Codes: G06F 9/4492 Inheritance

Abstract

A system, method and computer readable medium for providing class hierarchy composition aims at constructing software systems by composing a set of class hierarchies into an executable system. Current composition algorithms cannot provide semantic guarantees. The present invention provides a composition algorithm, together with an interference criterion and its correctness proof, which guarantees that behavior of the original hierarchies is preserved for interference-free compositions. In case of interference, an impact analysis can determine the consequences of integration. The method is based on existing program analysis technology and is illustrated by various examples.

Claims

1. A method on an information processing device for reporting any behavioral differences after composing two or more class hierarchies ₁ and ₂ with associated applications A₁ and A₂ respectively, the method on the information processing device comprising:

creating a composed hierarchy ₃ by analyzing a hierarchy ₁ and a hierarchy ₂;

creating well-defined methods and/or fields in one or more classes of the hierarchy ₃ by analyzing the hierarchy ₁ and the hierarchy ₂ and user-supplied information;

associating a definition of a method M in a class D in a hierarchy with each executed call to a definition of a method M′

in a class C in the hierarchy where class D is a subtype of class C in a behavior in the hierarchy for each of an application A₁ and an application A₂, wherein the method M and the method M′

have an identical signature;

testing if two behaviors across the hierarchy ₁ and the hierarchy ₃ are different by comparing a behavior B₃ of the application A₁ in the composed hierarchy ₃ with a behavior B₁ of the application A₁ in the hierarchy ₁ and reporting any differences therebetween; and

testing if two behaviors across the hierarchy ₂ and the hierarchy ₃ are different by comparing a behavior B₄ of the application A₂ in the composed hierarchy ₃ with a behavior B₂ of the application A₂ in the hierarchy ₂ and reporting any differences therebetween.

2. The method of claim 1, further comprising:

determining a behavior B₁ of the application A₁ in the hierarchy ₁ by associating a method definition M₁′

in a class D₁ in the hierarchy ₁ with each executed call to a method M₁ in class C₁ in the hierarchy ₁, wherein the class D₁ is a subtype of the class C₁ in the hierarchy ₁ and wherein the method M₁ and the method M₁′

have an identical signature;

determining a behavior B₂ of the application A₂ in the hierarchy ₂ by associating a method definition M₂′

in a class D₂ in the hierarchy ₂ with each executed call to a method M₂ in class C₂ in the hierarchy ₂, wherein the class D₂ is a subtype of the C₂ in the hierarchy ₂ and wherein the method M₂ and the method M₂′

have an identical signature;

determining a behavior B₃ of the application A₁ in the hierarchy ₃ by associating a method definition M₃′

in a class D₃ in the hierarchy ₃ with each executed call to a method M₃ in class C₃ in the hierarchy ₃, wherein the class D₃ is a subtype of the C₃ in the hierarchy ₃, wherein the method M₃ and the method M₃′

have an identical signature; and

determining a behavior B₄ of the application A₂ in the hierarchy ₃ by associating a method definition M₄′

in a class D₄ in the hierarchy ₃ with each executed call to a method M₄ in class C₄ in the hierarchy ₃, wherein the class D₄ is a subtype of the C₄ in the hierarchy ₃, wherein the method M₄ and the method M₄′

have an identical signature.

3. The method of claim 1, further comprising:

determining, using program analysis, at least one of the following;

if the behavior of application A₁ when executed against the composed hierarchy ₃ differs from the behavior of application A₁ when executed against the hierarchy ₁; and

if the behavior of application A₂ when executed against the composed hierarchy ₃ differs from the behavior of application A₂ when executed against the hierarchy ₂.

4. The method of claim 1, wherein the creating of the well-defined methods and fields of the composed hierarchy ₃ includes using the user-supplied information to resolve conflicts between methods and/or fields that originate from the hierarchy ₁ and the hierarchy ₂.

5. The method of claim 1, further comprising:

reporting at least one of the composed hierarchy ₁ and the composed hierarchy ₂ is behavior-preserving in response to zero behavior differences having been reported.

6. The method of claim 1, wherein the creating of the well-defined classes in the composed hierarchy ₃ is a basic composition involving the hierarchy ₁ and the hierarchy ₂ and where the hierarchy ₁ and the hierarchy ₂ do not contain static interference.

7. The method of claim 1, wherein the creating of the well-defined classes in the composed hierarchy ₃ is an overriding composition involving the hierarchy ₁ and the hierarchy ₂ where the hierarchy ₁ and the hierarchy ₂ contains static interference.

8. The method of claim 1, wherein the creating of the well-defined classes in the composed hierarchy ₃ is an overriding composition involving the hierarchy ₁ and the hierarchy ₃ and where the determining, using program analysis, includes precedence of members as part of the user-supplied information and where the hierarchy ₁ and the hierarchy ₂ contains static interference.

9. The method of claim 8, wherein the determining, using program analysis, includes determining if the composition of the hierarchy ₁ and the hierarchy ₂ contains dynamic interference.

10. The method of claim 8, wherein the determining, using program analysis, includes using impact analysis to determine any parts of the application A₁ and/or any parts of the application A₂ whose behavior have changed.

11. The method of claim 9, wherein the determining, using program analysis, includes using impact analysis to determine any parts of the application A₁ and/or parts of the application A₂ whose behavior have changed.

12. A method on an information processing device of composing two or more input class hierarchies ₁ and ₂ with associated applications A₁ and A₂ respectively, the method on the information processing device comprising:

determining a union of any inheritance relations in two or more input class hierarchies ₁ and ₂;

determining one or more cycles in a transitive closure of the inheritance relations, and constructing a set of equivalence classes ε

corresponding to the cycles;

creating of a class in a composed hierarchy ₃ for each equivalence class in ε

;

associating a definition of a method M in a class D in a hierarchy with each executed call to a definition of a method M′

in a class C in the hierarchy where class D is a subtype of class C in a behavior in the hierarchy for each of an application A₁ and an application A₂, wherein the method M and the method M′

have an identical signature;

associating a name and a set of members with each class in the composed hierarchy ₃;

creating inheritance relations in the composed hierarchy ₃;

testing if two behaviors across the hierarchy ₁ and the hierarchy ₃ are different by comparing a behavior of the application A₁ in the composed hierarchy ₃ with a behavior of the application A₁ in the hierarchy ₁, and reporting any differences therebetween; and

testing if two behaviors across the hierarchy ₂ and the hierarchy ₃ are different by comparing a behavior of the application A₂ in the composed hierarchy ₃ with a behavior of the application A₂ in the hierarchy ₂, and reporting any differences therebetween.

13. The method of claim 12, further comprising:

determining a behavior B₁ of the application A₁ in the hierarchy ₁ by associating a method definition M₁′

in a class D₁ in the hierarchy ₁ with each executed call to a method M₁ in class C₁ in the hierarchy ₁, wherein the class D₁ is a subtype of the class C₁ in the hierarchy ₁ and wherein the method M₁ and the method M₁′

have an identical signature;

determining a behavior B₂ of the application A₂ in the hierarchy ₂ by associating a method definition M₂′

in a class D₂ in the hierarchy ₂ with each executed call to a method M₂ in class C₂ in the hierarchy ₂, wherein the class D₂ is a subtype of the C₂ in the hierarchy ₂ and wherein the method M₂ and the method M₂′

have an identical signature;

determining a behavior B₃ of the application A₁ in the hierarchy ₃ by associating a method definition M₃′

in a class D₃ in the hierarchy ₃ with each executed call to a method M₃ in class C₃ in the hierarchy ₃, wherein the class D₃ is a subtype of the C₃ in the hierarchy ₃, wherein the method M₃ and the method M₃′

have an identical signature; and

determining a behavior B₄ of the application A₂ in the hierarchy ₃ by associating a method definition M₄′

in a class D₄ in the hierarchy ₃ with each executed call to a method M₄ in a class C₄ in the hierarchy ₃, wherein the class D₄ is a subtype of the C₄ in the hierarchy ₃, wherein the method M₄ and the method M₄′

have an identical signature.

14. A physical computer readable medium including computer instructions for execution on an information processing device for composing two or more class hierarchies ₁ and ₂ with associated applications A₁ and A₂ respectively, the computer instructions comprising programming instructions for:

creating a composed hierarchy ₃ by analyzing a hierarchy ₁ and a hierarchy ₂;

creating well-defined methods and/or fields in one or more classes of the hierarchy ₃ by analyzing the hierarchy ₁ and the hierarchy ₂ and user-supplied information;

associating a definition of a method M in a class D in a hierarchy with each executed call to a definition of a method M′

in a class C in the hierarchy where class D is a subtype of class C in a behavior in the hierarchy for each of an application A₁ and an application A₂, wherein the method M and the method M′

have an identical signature;

testing if two behaviors across the hierarchy ₁ and the hierarchy ₃ are different by comparing a behavior B₃ of the application A₁ in the composed hierarchy ₃ with a behavior B₁ of the application A₁ in the hierarchy ₁ and reporting any differences therebetween; and

testing if two behaviors across the hierarchy ₂ and the hierarchy ₃ are different by comparing a behavior B₄ of the application A₂ in the composed hierarchy ₃ with a behavior B₂ of the application A₂ in the hierarchy ₂, and reporting any differences therebetween.

15. The computer readable medium of claim 14, further comprising the programming instructions of:

determining a behavior B₁ of the application A₁ in the hierarchy ₁ by associating a method definition M₁′

in a class D₁ in the hierarchy ₁ with each executed call to a method M₁ in class C₁ in the hierarchy ₁, wherein the class D₁ is a subtype of the class C₁ in the hierarchy ₁ and wherein the method M₁ and the method M₁′

have an identical signature;

determining a behavior B₂ of the application A₂ in the hierarchy ₁ by associating a method definition M₂′

in a class D₂ in the hierarchy ₂ with each executed call to a method M₂ in class C₂ in the hierarchy ₂, wherein the class D₂ is a subtype of the C₂ in the hierarchy ₂ and wherein the method M₂ and the method M₂′

have an identical signature;

determining a behavior B₃ of the application A₁ in the hierarchy ₃ by associating a method definition M₃′

in a class D₃ in the hierarchy ₃ with each executed call to a method M₃ in class C₃ in the hierarchy ₃, wherein the class D₃ is a subtype of the C₃ in the hierarchy ₃, wherein the method M₃ and the method M3′

have an identical signature; and

determining a behavior B₄ of the application A₂ in the hierarchy ₃ by associating a method definition M₄′

in a class D₄ in the hierarchy ₃ with each executed call to a method M₄ in class C₄ in the hierarchy ₃, wherein the class D₄ is a subtype of the C₄ in the hierarchy ₃, wherein the method M₄ and the method M₄′

have an identical signature.

16. The computer readable medium of claim 15, further comprising the programming instructions of:

determining, using program analysis, at least one of the following;

if the behavior of application A₁ when executed against the composed hierarchy ₃ differs from the behavior of application A₁ when executed against the hierarchy ₁; and

if the behavior of application A₂ when executed against the composed hierarchy ₃ differs from the behavior of application A₂ when executed against the hierarchy ₂.

17. The computer readable medium of claim 15, wherein the programming instruction of creating of the well-defined methods and fields of the composed hierarchy ₃ includes using the user-supplied information to resolve conflicts between methods and/or fields that originate from the hierarchy ₁ and the hierarchy ₂.

18. The computer readable medium of claim 15, further comprising the programming instruction of:

reporting at least one of the composed hierarchy ₁ and the composed hierarchy ₂ is behavior-preserving in response to zero behavior differences having been reported.

19. The computer readable medium of claim 15, wherein the programming instruction of creating of the well-defined classes in the composed hierarchy ₃ is a basic composition involving the hierarchy ₁ and the hierarchy ₂ and where the hierarchy ₁ and the hierarchy ₂ do not contain static interference.

20. The computer readable medium of claim 15, wherein the programming instruction of creating of the well-defined classes in the composed hierarchy ₃ is an overriding composition involving the hierarchy ₁ and the hierarchy ₂ and where the hierarchy ₁ and the hierarchy ₂ contains static interference.

21. The computer readable medium of claim 20, wherein the programming instruction of creating of the well-defined classes in the composed hierarchy ₃ is an overriding composition involving the hierarchy ₁ and the hierarchy ₃ and where the determining, using program analysis, includes precedence of members as part of the user-supplied information and where the hierarchy ₁ and the hierarchy ₂ contains static interference.

22. The computer readable medium of claim 21, wherein the programming instruction of determining, using program analysis, includes determining if the composition of the hierarchy ₁ and the hierarchy ₂ contains dynamic interference.

23. The computer readable medium of claim 21, wherein the programming instruction of determining, using program analysis, includes using impact analysis to determine any parts of the application A₁ and/or any parts of the application A₂ whose behavior have changed.

24. The computer readable medium of claim 22, wherein the programming instruction of using program analysis, includes using impact analysis to determine any parts of the application A₁ and/or parts of the application A₂ whose behavior have changed.

25. A physical computer readable medium including computer instructions for execution on an information processing device for composing two or more class hierarchies ₁ and ₂ with associated applications A₁ and A₂ respectively, the computer instructions comprising instructions for:

determining a union of any inheritance relations in two or more input class hierarchies ₁ and ₂;

determining one or more cycles in a transitive closure of the inheritance relations, and constructing a set of equivalence classes ε

corresponding to the cycles;

associating a name and a set of members with each class;

creating inheritance relations in the composed hierarchy ₃;

associating a definition of a method M in a class D in a hierarchy with each executed call to a definition of a method M′

in a class C in the hierarchy where class D is a subtype of class C in a behavior in the hierarchy for each of an application A₁ and an application A₂, wherein the method M and the method M′

have an identical signature;

creating of a class in a composed hierarchy ₃ for each equivalence class in ε

;

testing if two behaviors across the hierarchy ₁ and the hierarchy ₃ are different by comparing a behavior B₃ of the application A₁ in the composed hierarchy ₃ with a behavior B₁ of the application A₁ in the hierarchy ₁ and reporting any differences therebetween; and

testing if two behaviors across the hierarchy ₃ and the hierarchy ₃ are different by comparing a behavior b₄ of the application A₂ in the composed hierarchy ₃ with a behavior B₂ of the application A₂ in the hierarchy ₂, and reporting any differences therebetween.

26. The computer readable medium of claim 25, further comprising the programming instructions of:

determining a behavior B₁ of the application A₁ in the hierarchy ₁ by associating a method definition M₁′

in a class D₁ in the hierarchy ₁ with each executed call to a method M₁ in class C₁ in the hierarchy ₁, wherein the class D₁ is a subtype of the class C₁ in the hierarchy ₁ and wherein the method M₁ and the method M₁′

have an identical signature;

determining a behavior B₂ of the application A₂ in the hierarchy ₂ by associating a method definition M₂′

in a class D₂ in the hierarchy ₂ with each executed call to a method M₂ in class C₂ in the hierarchy ₂, wherein the class D₂ is a subtype of the C₂ in the hierarchy ₂ and wherein the method M₂ and the method M₂′

have an identical signature;

determining a behavior B₃ of the application A₁ in the hierarchy ₃ by associating a method definition M₃′

in a class D₃ in the hierarchy ₃ with each executed call to a method M₃ in class C₃ in the hierarchy ₃, wherein the class D₃ is a subtype of the C₃ in the hierarchy ₃, wherein the method M₃ and the method M₃′

have an identical signature; and

determining a behavior B₄ of the application A₂ in the hierarchy ₃ by associating a method definition M₄′

in a class D₄ in the hierarchy ₃ with each executed call to a method M₄ in class C₄ in the hierarchy ₃, wherein the class D₄ is a subtype of the C₄ in the hierarchy ₃, wherein the method M₄ and the method M₄′

have an identical signature.

27. A computer system for composing two or more class hierarchies ₁ and ₂ with associated applications A₁ and A₂ respectively, the computer system comprising:

a processor coupled to memory for executing a software program to perform;

means for creating a composed hierarchy ₃ by analyzing a hierarchy ₁ and a hierarchy ₂;

means for creating well-defined methods and/or fields created in one or more classes of the hierarchy ₃ by analyzing the hierarchy ₁ and the hierarchy ₂ and user-supplied information;

means for associating a definition of a method M in a class D in a hierarchy with each executed call to a definition of a method M′

in a class C in the hierarchy where class D is a subtype of class C in a behavior in the hierarchy for each of an application A₁ and an application A₂, wherein the method M and the method M′

have an identical signature;

means for testing if two behaviors across the hierarchy ₁ and the hierarchy ₃ are different by comparing a behavior B₃ of the application A₁ in the composed hierarchy ₃ with a behavior B₁ of the application A₁ in the hierarchy ₁ and reporting any differences therebetween; and

means for testing if two behaviors across the hierarchy ₂ and the hierarchy ₃ are different by comparing a behavior B₄ of the application A₂ in the composed hierarchy ₃ with a behavior B₂ of the application A₂ in the hierarchy ₂, and reporting any differences therebetween.

28. The computer system of claim 27, further comprising:

determining a behavior B₁ of the application A₁ in the hierarchy ₁ by associating a method definition M₁′

in a class D₁ in the hierarchy ₁ with each executed call to a method M₁ in class C₁ in the hierarchy ₁, wherein the class D₁ is a subtype of the class C₁ in the hierarchy ₁ and wherein the method M₁ and the method M₁′

have an identical signature;

determining a behavior B₂ of the application A₂ in the hierarchy ₂ by associating a method definition M₂′

in a class D₂ in the hierarchy ₂ with each executed call to a method M₂ in class C₂ in the hierarchy ₂, wherein the class D₂ is a subtype of the C₂ in the hierarchy ₂ and wherein method M₂ and the method M₂′

have an identical signature;

determining a behavior B₃ of the application A₁ in the hierarchy ₃ by associating a method definition M₃′

in a class D₃ in the hierarchy ₃ with each executed call to a method M₃ in class C₃ in the hierarchy ₃, wherein the class D₃ is a subtype of the C₃ in the hierarchy ₃, wherein the method M₃ and the method M₃′

have an identical signature; and

determining a behavior B₄ of the application A₂ in the hierarchy ₃ by associating a method definition M₄′

in a class D₄ in the hierarchy ₃ with each executed call to a method M₄ in class C₄ in the hierarchy ₃, wherein the class D₄ is a subtype of the C₄ in the hierarchy ₃, wherein the method M₄ and the method M₄′

have an identical signature.

29. The computer system of claim 28, further comprising:

means for determining, using program analysis, at least one of the following;

if the behavior of application A₁ when executed against the composed hierarchy ₃ differs from the behavior of application A₁ when executed against the hierarchy ₁; and

if the behavior of application A₂ when executed against the composed hierarchy ₃ differs from the behavior of application A₂ when executed against the hierarchy ₂.