Semantics-based composition of class hierarchies

[0001] 1. Field of the Invention

[0002] This invention generally relates to the field of object-oriented programming and class hierarchies and more specifically to constructing software systems by composing the code associated with a set of class hierarchies into an executable system.

[0003] 2. Description of Related Art

[0004] Class hierarchy composition aims at constructing software systems by composing the code associated with a set of class hierarchies into an executable system, or by weaving separately written aspects into a class hierarchy. See generally William Harrison and Harold Ossher, “Subject-Oriented Programming (A Critique Of Pure Objects)” In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 411–428, 1993 and Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and William G. Griswold. An overview of AspectJ, In Proc. 15th European Conf. on Object-Oriented Programming (ECOOP'01), Budapest, Hungary, June 2001. Advocates of composition argue that, by putting the functionality associated with each system feature in a separate hierarchy, a better separation of concerns is achieved, resulting in code that is easier to understand, maintain, and change.

[0005] Although considerable amounts of work have been devoted to developing specification formalisms for software composition, and on the methodological aspects of compositional software development, current techniques and tools for hierarchy composition operate on a purely syntactical basis and cannot provide any semantic guarantees about the behavior of the composed hierarchy. It is thus our aim to develop a semantically well-founded notion of composition that enables reasoning about the behavior of composed class hierarchies. Accordingly a need exists to overcome the shortcomings of the prior art systems and to provide a semantically well-founded notion of composition that enables reasoning about the behavior of composed class hierarchies.

[0006] Research on aspect-oriented software development has been gaining in popularity recently see for example Communications of the ACM. 44(10), October 2001, “Special Issue On Aspect-Oriented Programming.” In essence, the goal of this field is to obtain more extensible and reusable designs by distributing unrelated functionality over disjoint hierarchies or aspects. To achieve this, a mechanism for composing these functionalities into executable code is needed. In our setting, this is accomplished by composing hierarchies. Aspect-oriented languages such as AspectJ (see Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and William G. Griswold, “An overview of AspectJ”, In Proc. 15th European Conf. on Object-Oriented Programming (ECOOP'01), Budapest, Hungary, June 2001) have language constructs that allow one to specify the conditions under which a piece of advice is “woven in” at a joint point. Until recently, there has been very little work on the semanticfoundations of composition

[0007] The work most closely related to ours is the Aspect Sandbox (ASB) project by Wand et al. (see Mitchell Wand, Gregor Kiczales, and Christopher Dutchyn, “A Semantics For Advice And Dynamic Join Points In Aspect-Oriented Programming”, October 2001), who incorporate several key aspect-oriented language constructs such as join points, pointcut designators, and advice into a simple language with procedures, classes, and objects. Wand et al. formalize the semantics of this language using a denotational semantices. Wand et al. do not provide any guarantees about the noninterference of aspects, nor do they determine the semantic impact of “weaving in” an aspect.

[0008] Ernst presented a class hierarchy composition system, where the composition operator is built into the syntax of the programming language gbeta. Explicitly specified compositions may trigger propagation of implicit compositions, for example an explicit combination of methods or classes may trigger implicit composition of other (e.g. auxiliary) methods or classes. Ernst showed that his composition system and propagation mechanism preserve static type correctness, but nothing is said about preservation of dynamic client behavior.

[0009] Our approach is similar in spirit to the work by Binkley et al. (see David Binkley, Susan Horwitz, and Thomas Reps “Program Integration For Languages With Procedure Calls”, ACM Transactions on Software Engineering and Methodology, pages 3–35, January 1995.) on the integration of C programs that are variations of a common base, by analyzing and merging their program dependence graphs. Similar to our work, Binkley et al. use an interference test, which is a sufficient criterion for noninterference. The main differences between Binkley et al. and our work is that Binkley et al. operates at the statement level, whereas our techniques operate on calling relationships between methods. Binkley et al. do not consider object-oriented language features.

[0010] Composition of object-oriented programs has been studied by other authors in the context of component-based systems. See Oscar Nierstrasz and Dennis Tsichritzis (ed.). “Object-Oriented Software Composition”, Prentice Hall, 1995. One approach is concerned with the dynamic interaction of concurrent objects, and the goal is to create new behavior as a composition of given behavior. Our approach aims to preserve old behavior while combining given behavior. Another line of research has investigated the composition of systems from components, where the components are treated as black boxes and come with some interface specification, usually in the form of a type system.

[0011] Briefly, in accordance with the present invention, disclosed is 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.

[0012] In one embodiment, a method is directed to composing two or more class hierarchies ₁ and ₂ with associated applications A₁ and A₂ respectively, resulting in at least one composed class hierarchy ₃, and reporting a behavior of application A₁ and application A₂ when executing against ₃, the method comprising:

• • [0013] creating a well-defined class in a composed hierarchy ₃ by analyzing a hierarchy ₁ and a hierarchy ₂;
  • [0014] creating the well-defined methods and/or fields in the classes of the hierarchy ₃ by analyzing the hierarchy ₁ and the hierarchy ₂ and user-supplied information;
  • [0015] determining at least one of the following:
    • [0016] if the behavior A₁ when executed against a composed hierarchy ₃ differs from the behavior of A₁ when executed against ₁ using program analysis; and
    • [0017] if the behavior A₂ when executed against a composed hierarchy ₃ differs from the behavior of A₂ when executed against ₂ using program analysis.

[0028] It should be understood that these embodiments are only examples of the many advantageous uses of the innovative teachings herein. In general, statements made in the specification of the present application do not necessarily limit any of the various claimed inventions. Moreover, some statements may apply to some inventive features but not to others. In general, unless otherwise indicated, singular elements may be in the plural and vice versa with no loss of generality. In the drawing like numerals refer to like parts through several views.

[0029] This patent is based in part on a paper entitled “Semantic-Based Composition of Class Hierarchies” with identical named authors, which will be presented on Jun. 10–14, 2002, at the ECOOP (European Conference On Object-Oriented Programming) in Málaga, Spain which is hereinto incorporated by reference in its entirety.

1 Introduction

[0030] Class hierarchy composition aims at constructing software systems by composing the code associated with a set of class hierarchies into an executable system, or by weaving separately written aspects into a class hierarchy. The present invention provides the following approach:

• • [0031] The present invention define notions of static interference and dynamic interference that capture how features in one hierarchy may impact the behavior of code in another. The former notion captures behavioral impact at composition-time, whereas the latter is concerned with run-time changes in program behavior.
  • [0032] The present invention considers two kinds of compositions. Basic compositions involve hierarchies that do not statically interfere. Overriding compositions rely on a mechanism by which a user can explicitly resolve static interference.
  • [0033] In cases where interference is found, an impact analysis (similar Barbara G. Ryder and Frank Tip, change impact analysis for object-oriented programs. In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), pages 46–53, Snowbird, Utah, June 2001) is performed that determines a set of methods in the composed hierarchy for which preservation of behavior cannot be guaranteed.

[0034] Hence, the present invention permits a developer to quickly determine if a proposed composition may result in behavioral changes, and-if so-report precisely which parts of the program may be affected. It should be understood that these techniques can be incorporate t in a system such as Hyper/J in the form of a tool that performs various sanity checks on compositions.

[0035] Turning now to FIG. 1 shows three hierarchies that model a number of aspects of university life. ₁ defines classes Course, Person, Student, and Professor, and provides functionality for enrolling students in courses, for associating professors with courses, and for professors to approve the graduation of students (method Professor.approveGraduation ( )). This latter operation requires the approval of the courses taken by a student, modeled using a method approveCourses( ). The details of approveCourses ( ), but one can easily imagine adding functionality for keeping track of a student's course load and grades which would be checked by the professor to base his decision on. Class Driver1 contains a small test driver that exercises the functionality of hierarchy ₁.

[0036] Hierarchy ₂ is concerned with employment and advisory relationships. A student can designate a professor as his/her advisor (method Student.setAdvisor( )), and a professor can hire a student as a teaching assistant using method Professor.hireAssistant( ). Class Driver2 exercises the functionality in this hierarchy.

[0037] Hierarchy ₃ shows a slightly more elaborate model, where a distinction is made between (undergraduate) Students and PhDStudents. This impacts the approval of graduations, because PhDStudents are also required to produce a thesis of sufficient quality (modeled by method Professor. approvePhDThesis ( )). The details of this method are omitted but are understood by those of average skill in the art.

[0038] Let us now consider the composition of ₁ and ₂. These hierarchies are not disjoint, since they contain the same classes. However, since there are no “syntactic collisions” between members in ₁ and ₂ (i.e., ₁ and ₂ do not contain methods with the same name and signatures (i.e., arguments of methods), but with different bodies), one can simply construct a hierarchy that contains the union of the classes in ₁ and ₂, where each class in the combined hierarchy contains the union of the methods/fields that occur in the corresponding class(es) in ₁ and ₂. The resulting hierarchy is shown in FIG. 2.

[0039] What can be said about the behavior of ₁⊕₂? In this case, our interference check guarantees that the behavior of the client applications of these hierarchies (modeled by Driver1.main ( ) and Driver2.main ( )) are unaffected by the composition. For this specific composition, we can even provide the stronger guarantee that the behavior of any client of ₁ and ₂ is preserved. As shown below, this is not always the case.

[0040] Now consider composing ₁ and ₃, which contain different methods Professor.approveGraduation ( ), an example of static interference. Method approveGraduation ( ) in ₃ is “more general” than approveGraduation ( ) in ₁. In constructing ₁⊕H3 (see FIG. 3), we have assumed that the user specified that the definition of approveGraduation ( ) in ₃ should be preferred over that in ₁. In this case, our techniques report dynamic interference, i.e., preservation of behavior for clients of the original hierarchies cannot be guaranteed. Impact analysis reports that Driver3.main ( ) is not affected by the composition, but that the behavior of Driver1.main ( ) may have changed.

Composition of Hierarchies

[0041] One of the first issues that arise when composing two class hierarchies is the question in which classes and methods in the input hierarchies correspond. The Hyper/J composition system (see Peri Tarr, Harold Ossher, William Harrison, and Stanley M. Sutton, Jr. “N Degrees Of Separation: Multi-Dimensional Separation Of Concerns”, In Proceedings of the 1999 International Conference on Software Engineering, pages 107–119, May 1999) relies on a specification language to express these correspondences. For example, one can specify “merge-by-name” compositions in which two classes in different input hierarchies are matched if they have the same name, and one can explicitly specify pairs of matching classes (with different names) using an “equate” construct. In order to simplify the presentation in this present invention, we will assume that classes are matched “by name” only. Compositions that are not name-based can be modeled using an additional preprocessing step in which classes and methods are renamed appropriately. In particular, manually established relations between entities in the two hierarchies are assumed to be modeled by appropriate renaming.

Class Hierarchies

[0042] Definition 1 defines the notion of a class hierarchy. To keep our definitions simple, we assume that fields and abstract methods have undefined bodies (body (m)=⊥), and that fields and abstract methods cannot have the same name.

[0043] Definition 1 (class hierarchy). A class hierarchy is a set of classes together with an inheritance relation: =(C, ≦). For a class C∈C we also write C∈. A class C∈ has a name and contains a set of members (according to this definition, members (C) does not contain inherited members that are declared in superclasses of C):C=(n, M), where name(C)=n, members(C)=M. A member m ∈ members(C) is characterized by its name, its signature and its body: m=(f, σ, B) where σ∈C*×C, where f is the name of the function, σ is the signatures of the function, and B is the body of the function. We will use namesig(m) to denote the combination <f, σ> that together uniquely identify a member within a class, and body(m) to denote the body B of member m.

Classes and Inheritance Relations in the Composed Hierarchy

[0044] Semantically sound composition requires that the original inheritance relations can be order-embedded into the composed hierarchy. That is, a relationship A instanceof B that holds in an input hierarchy should also hold in the composed hierarchy. In general, one cannot simply compute the union of the inheritance relations in the input hierarchies because the resulting hierarchy may contain cycles. We therefore use a well-known factorization technique that produces an acyclic hierarchy such as those taught by 4. B. A. Davey and H. A. Priestley. Entitled Introduction to Lattices and Order. Cambridge University Press 1990. This construction has the advantage that hierarchies can be composed even if there are cycles in the union of the original inheritance relations, which might sometimes be useful in practice.

[0045] Given two input hierarchies ₁ and ₂, their composition is denoted ₁⊕₂. The construction of ₁⊕₂ is given in Definition 2. This involves: creating a set of pairs of the form <class, hierarchy> (step 1), determining the “union” of the inheritance relations in the input hierarchies (assuming that classes are matched by name) (step 2), determining cycles in the transitive closure of these inheritance relations, and constructing a set of equivalence classes ε corresponding to these cycles (steps 3–5), creation of a class in the composed hierarchy for each equivalence class in ε (step 6), associating a name and a set of members (step 7) with each class, and creation of the inheritance relations in the composed hierarchy (step 8). The term “class” as in “equivalence class” is different form “class” as in “class hierarchy”; we use this “overloading” in order to be compatible with both mathematical and computer science conventions.

[0046] Definition 2 (hierarchy composition). Let ₁=(C₁,≦₁) and ₂=(C₂,≦₂) be two class hierarchies. Then, ₁⊕₂=(C,≦), which is defined as follows:

• • [0047] 1. S={<C₁, ₁>|C₁∈C₁}∪{<C2, 2>|C₂∈C₂},
  • [0048] 2. <C₁, ₁>≦′<C₂, ₁>′C₁≦C₂, <C₁, ₂>≦′<C₂, ₂>C₁≦₂C₂, <C₁, i>≦′<C₂, j>namesig(C₁)=namesig(C₂), (i, j∈{1, 2})
  • [0049] 3. xρyx≦′*yΛy≦′*x,
  • [0050] 4. ≦=≦′*/ρ,
  • [0051] 5. ε={[x]_ρ|x∈S},
  • [0052] 6. C={class([x]_ρ)|[x]_ρ∈ε},
  • [0053] 7. class([x]_ρ)=<namesig([x]_ρ), members ([x]_ρ)>, and
  • [0054] 8. class([x]_ρ)≦class([y]_ρ)[x]_ρ≦[y]_ρ

[0055] The name function determines the name of the composed class from the names of the classes in equivalence class [C]_ρ and will not be formally defined here (some examples will be given below). Note that the members of a composed class do not include inherited members from the original classes, but only members defined locally in the original classes. Different members operators will be presented for different kinds of compositions in Definitions 4 and 6 below.

[0056] Note that ≦′ is not necessarily transitive, hence the use of the closure operator. As usual, [x]_ρ consists of all classes ρ-equivalent to x, and [x]_ρ≦[y]_ρx≦′y; we assume that ≦ is the smallest partial order satisfying the conditions from the definition. We will use ε to denote the set of all equivalence classes [<C, >]_ρ, for any <(C, >∈S. Moreover, we define a partial order on εby: <C, >≦′<C′, ′)>[<C, >]_ρ≦[C′, ′]_ρ. Intuitively, one can imagine this order as the directed acyclic graph of all strongly connected components of the union of the two input hierarchies.

[0057] In the hierarchy of FIG. 4(a), the transitive closure of ≦₁ and ≦₂ does not contain any cycles. Hence, we have: E={{<A, ₁>, <A, ₂,>}, {<B, ₁>}, {<C, ₁>, <C, ₂>}, {<D, ₁>}, {<E, ₁>}, {<F, ₂,>}, {<G, ₂>}}. Consequently, the following inheritance relations are constructed: B<A, F<A, C<F, G<F, D<C, E<C. Here, class names in the composed hierarchy are generated from the names of the classes in the corresponding equivalence sets (e.g., class A corresponds to {<A, ₁>, <A, ₂>}). Note that immediate subclass/superclass relations need not be preserved F is now between A and C.

[0058] For the slightly more interesting example of FIG. 4(b), we have: ε={{<A, ₁>, <A, ₂>, <C, ₁>, <C, ₂>, <F, ₂>}, {<B, ₁>}, {<D, ₁>}, {<E, ₁>}, {<G, ₂>}}. The composed hierarchy contains a class for each of these equivalence classes (for the purposes of this example, we assume that the name function constructs a class name by concatenating the names of elements in the equivalence class). There is an inheritance relation X<Y if the equivalence class corresponding to X contains a class x, and the equivalence class corresponding to Y contains a class y such that x inherits from y in one or both of the input hierarchies. For example, class B inherits from ACF because <B, ₁< is part of equivalence class {<B, ₁>}, <A, ₁> is part of equivalence class {<A, ₁>, <A, ₂>, <C, ₁>, <C, ₂>, <F, ₂>}, and class B inherits from class A in ₁. Again, immediate subclass/superclass relations need not be preserved: some immediate relations (e.g., F<C) have been collapsed.

[0059] In case classes have been merged, new class names have been introduced as well (e.g. ACF in the above example). Thus any client code must be transferred accordingly: any occurrence of the old class name x must be replaced by name([x]_ρ). In the example, any occurrence of class names A, C, or F in client code must be replaced by ACF.

[0060] A final issue to note is that the composed inheritance relation may contain multiple inheritance. This may cause problems in languages such as Java that do not support general multiple inheritance. We consider this issue to be outside the scope of this present invention, and plan to pursue an approach in which multiple inheritance is automatically transformed into delegation.

Basic Composition

[0061] In defining the set of members in the composed hierarchy, the question arises of what to do when two or more classes in an equivalence class [x]_ρ define the same member. We will refer to such cases as static interference. The easiest approach of dealing with this issue is to simply disallow composition if static interference occurs. We will refer to this scenario as basic composition. As we shall see shortly, the absence of static interference does not guarantee preservation of behavior.

[0062] Definition 3 defines basic static interference. Note that it does allow situations where an equivalence class [x]_ρ contains two elements <C₁, ₁> and <C₁, ₂> such that C₁ and C₂ each contain a member m, provided that (i) body(m)=⊥holds for at least one of these m's, or (ii) that the two m's have the same body.

[0063] Definition 3 (basic static interference). ε contains basic static interference if there is an equivalence class [x]_ρ∈E such that for some <C₁, >, <C₂, ′>∈[x]_ρ, C₁≠C₂, m₁∈members (C₁), m₂∈members (C₂), namesig(m₁)=namesig (m₂) we have that: body(m₁)≠⊥, body(m₂)≠⊥, and body(m₁)≠body(m₂).

[0064] Definition 4 defines the set of members in the composed hierarchy. Note that, in cases where the classes in an equivalence class contain multiple methods with the same name and signature, the unique method with a non-⊥ body is selected.

[0065] Definition 4 (members). Let E be free of basic static interference, and let [x]_ρ∈ε be an equivalence class. Define:

• • [0066] members ([x]_ρ)={m|<C, >∈[x]_ρ, m∈members (C), (<C′, ′>∈[x]_ρ, C′≠C, m′∈members (C′), namesig(m)=namesig(m′)body(m′)=⊥,}

[0067] The transitive closure of the inheritance relations in ₁ and ₂ of FIG. 1 does not contain any cycles. Hence, the construction of Definition 2 produces a hierarchy with classes Course, Person, Student, Professor, Driver1, and Driver2, with inheritance relations Student<Person and Professor<Person. The equivalence classes constructed are: S₁={<Course, ₁>}, S₂={<Person, ₁>}, S₃={<Student, ₁>, <Student, ₂>}, S₄={<Professor, ₁>, <(Professor, ₂>}, S₅={<Driver1, ₁>}, and S₆={<Driver2, ₂>}. Definition 3 states that there is basic static interference if an equivalence class S contains multiple methods with the same name but different bodies. Singleton equivalence classes such as S₁, S₂, S₅, and S₆ cannot give rise to interference because a class can contain only one method with a given name and signature. S₃ and S₄ do not give rise to interference either because Student and Professor in ₁ and ₂ do not contain conflicting methods. Hence, there is no basic static interference. FIG. 2 shows the composed hierarchy.

[0068] Consider composing the class hierarchies ₁ and ₃ of FIG. 1. The set equivalence classes ε constructed according to Definition 2 contains, among others, the element S={<Professor, ₁>, <Professor, ₃>}. ε exhibits basic static interference because both elements of S contain a member Professor.approveGraduation(Student) and the bodies of these methods are different. Hence, basic composition cannot be applied to ₁ and ₃.

Overriding Composition

[0069] As shown in FIG. 3, basic static interference is not necessarily an unwanted phenomenon. Often, a method from ₂ is an “improved” or “generalized” version of a method in ₁. To address such cases, we augment basic composition with a mechanism that allows one to express conditions such as “member B.m in ′ has precedence over member A.m in ”. This is captured by a precedence relation << containing elements <, m₁><<<′, m₂> indicating that method m₂ of hierarchy ′ has precedence over method m₁ of hierarchy . Note that it may be the case that ,=′. It is assumed that ‘<<’ is a partial order.

[0070] The static interference notion of Definition 3 only requires minor modifications to allow situations where an equivalence class contains two classes C₁ and C₂ originating from hierarchies ₁ and ₂, respectively, such that <₁, m₁> and <₂, m₂> are <<-ordered. Definition 5 shows the resulting definition.

[0071] Definition 5 (overriding static interference). ε contains overriding static interference w.r.t. ‘<<’ if there is an equivalence class [x]_ρ∈ε such that for some <C₁, >, <C₂, >∈[x]_ρ, C₁≠C₂, m₁∈members (C₁), m₂∈members (C₂), and namesig (m₁)=namesig(m₂) we have that: body (m₁)≠⊥, body (m₂)≠⊥, body(m₁)≠body(m₂), (, m₁><,′, m₂>, and <′, m₂><, m₁>.

[0072] Definition 6 shows the members function for overriding compositions. In the sequel, we will often say “⊕,₂ is free of overriding syntactic interference” if it is obvious which ordering ‘<<’ is used.

[0073] Definition 6 (members). Let ε be free of overriding static interference w.r.t ‘<<’, and let [x]_ρ∈ε be an equivalence class. Define:

• • [0074] members ([x]_ρ)={m₁|<C₁, ₁>∈[x]_ρ, m₁∈members (C₁), (<C₂, ₂>∈[x]₉₂ , C₂≠C₁, m₁∈members (C₂), namesig (m₁)=namesig(m₂))body(m₂)=⊥<₁, m₁><<<₂, m₂>}

[0075] Consider an overriding composition of hierarchies ₁ and ₃ of FIG. 1 using <Professor.approveGraduation (Student), ₁><<<Professor.approveGraduation (Student), ₃>. Then, the set of equivalence classes ε constructed by Definition 2 is: S₁={<Course, ₁>}, S₂={<Person, ₁>}, S₃={<Student, ₁>}, S₄={(Professor, ₁>, <Professor, ₃}, S₅={<Driver1, ₁>}, S₆={<PhDStudent, ₃>}, and S₇={<Driver3, ₃>}. Since singleton sets never give rise to interference, we only need to verify that S₄ does not cause overriding static interference. This is the case because the only method that occurs in both Professor classes is approveGraduation( ), and these methods are <<-ordered. The composed hierarchy can now be constructed using Definition 6, and was shown earlier in FIG. 3.

Type Correctness

[0076] A class hierarchy is type correct if: (1) any member access e.m( . . . ) refers to a declared member definition, and (2) for any assignment x=y, the type of x is a superclass of the type of y. As a first step towards providing semantic guarantees about the composed class hierarchy, we demonstrate that the composed hierarchy is type correct. Due to space limitations, we only demonstrate these properties for basic compositions. The arguments for overriding compositions are similar.

[0077] Definition 7 (type correctness). Let be a hierarchy.

• • [0078] 1. The static type of an object or object reference in a hierarchy is denoted TypeOf(, o), where o is a declare type variable. For convenience, we use TypeOf(_1,2, o)=C as an abbreviation for TypeOf(₁, o)=C TypeOf(₂, o)=C.
  • [0079] 2. For a class C∈ and m∈members(C), we define StaticLookup(, C, m)=m′, where m′∈members (C) for some class C′ such that C≦C′, namesig(m)=namesig(m), and there is no class C″ such that C≦C″≦C′, m″∈members (C″), namesig(m)=namesig(m″). We will use Static Lookup(_1,2, C, m)=m′ as a shorthand for StaticLookup(₁, C,m)=m′ StaticLookup(₂,C,m)=m′
  • [0080] 3. A hierarchy is type correct if for all assignments x=y∈ we have that TypeOf(, x)≧TypeOf(, y), and for all member accesses o.m( . . . )∈ we have that: StaticLookup(, TypeOf (, o), m)≠⊥.

[0081] Note that if TypeOf(_1,2, o)=C, then by construction TypeOf(₁⊕₂, o) =class([C]_ρ). As an example, consider FIG. 4, and assume that v is a variable such that TypeOf(₁, v)=A. Then, in FIG. 4(a) we have that TypeOf (₁⊕₂, v)=A and in FIG. 4(b) that TypeOf(₁⊕₂, v)=ACF. The latter case demonstrates that sometimes new class names are introduced, and member declarations must be changed accordingly. In particular, whenever name([C]_ρ)≠name(C), all declarations containing class name C must be updated to reflect the new class name name([C]_ρ). This will only happen if classes have been merged due to cycles in the transitive inheritance relations of the input hierarchies.

[0082] The following two lemmas show that assignments and member lookups in the composed hierarchy remain type correct. Note that this includes assignments due to parameter-passing in method calls, and implicit assignments to this-pointers.

[0083] Lemma 1 (assignment correctness). Let x=y be an assignment in _1,2. Then, this assignment is still type correct in ₁⊕₂.

[0084] Proof. Without loss of generality, let x=y ε ₁. Then, TypeOf (₁, x)≧₁TypeOf(₁, y). By construction, TypeOf(₁⊕₂, x)=class([TypeOf (₁, x)]_ρ)≧class([TypeOf (₁, y)]_ρ)=TypeOf(₁⊕₂, y).

[0085] Lemma 2 (member access correctness). If ₁ and ₂ are type correct and with-out basic static interference, then StaticLookup(_1,2, TypeOf(_1,2, o), m), ≠⊥ StaticLookup(₁⊕₂, TypeOf(₁⊕₂, o), m)≠⊥

[0086] Proof. Without loss of generality, let C=TypeOf(₁, o), and let D be the class which contains m′=StaticLookup(₁, TypeOf(₁, o), m) . Then, we have C≦₁D, m∈members(D) and by construction m∈members(class([D]_ρ)) as there is no static interference. Furthermore, class([C]_ρ)≦class([D]_ρ) and TypeOf(₁⊕₂, o)=class([C]_ρ). m could also occur in a subclass of class([D]_ρ) in ₁⊕₂, but for class D′ which contains m″=StaticLookup(₁⊕₂, TypeOf(₁⊕₂, o), m), we have in any case that D′≦class ([D]_ρ), hence StaticLookup(₁⊕₂, TypeOf (₁⊕₂, o), m)≠⊥.

[0087] Corollary 1. For hierarchies ₁ and ₂ without static interference, ₁⊕₂is type correct.

Dynamic Interference

[0088] Even basic composition (which makes the strongest assumptions about static noninterference) does not guarantee preservation of client behavior. This can be seen in the basic composition of FIG. 5, which does not exhibit static interference.

[0089] However, H₁⊕H₂ contains an overriding definition of foo( ) in class B, hence the call to foo( ) in C. main( ) binds to B.foo( ) instead of A.foo( ) as it did in ₁. Hence, behavior of ₁'s client C.main( ) is not preserved.

[0090] FIG. 6 shows an overriding composition (constructed using <₁, A.foo( )><<<₂, A. foo( )>) that is free of overriding static interference. However, in the composed hierarchy, variable x is bound to a B-object instead of an A-object. Thus, the call x.bar( ) suddenly resolves to B.bar( ) instead of A.bar( ) as in ₁.

Dynamic Interference

[0091] The term dynamic interference is used to refer to run-time behavioral changes such as the ones in the above examples. Some additional definitions are required to make this notion precise. To this end, we will use an operational semantics, where the effect of statement execution is described as a state transformation.

[0092] Definition 8 (state, state transformation).

• • [0093] 1. A program state maps variables to values: σ∈Σ=Var→Value.
  • [0094] 2. The effect of executing a statement S is a state transformation: σσ¹

[0095] Details of Var and Value are left unspecified, as they are not important for our purposes. (See Java subsets, Atshushi Igarashi, Benjamin Pierce, and Philip Wadler, “Featherweight Java: A minimal core calculus for Java” and GJ, In Proc. SIGPLAN/Conference an Object-Oriented Program-min, Systems, Languages and Applications (OOPSLA'99), pages 132–146, ACM, November 1999 and 12. Tobias Nipkow and David von Oheimb. “Java light is type safe—definitely”, In Proc. SIG-PLAN/SIGACT Symposium on Principles of Program Languages (POPL'98), pages 161–170. ACM, January 1998). Var includes local variables, parameters, and this-pointers in method invocation stack frames—note that the domain of Var may change as execution proceeds. Value comprises primitive values (e.g., integers) and objects in the heap. In order to model reference-typed fields, we assume that Var also contains an element for each field f of an object o, where o is an object in Value whose type contains a field f (either directly or through inheritance).

[0096] Now let us assume that we have a hierarchy together with some client code K which is type correct with respect to . We define:

[0097] Definition 9 (execution sequence).

• [0098] 1. An execution sequence of a hierarchy is the (finite or infinite) sequence of statements E(, K, I, σ₀)=S₁, S₂, S₃, . . . which results from executing the client code K of with input I in initial state σ₀. The corresponding sequence of program states is Σ(, K, I, σ₀)=σ₀→σ₁→σ₂→σ₃. . . .
• [0099] 2. The statement subsequence of S₁, S₂ . . . consisting only of member accesses (data member accesses or method calls) is denoted M (, K, I, σ₀)=S₁, S₂, . . . where Sv_i=S_j∈E(, K, I, σ₀). The corresponding sequence of invoked target methods is denoted T(, K, I, σ₀)=tv₁, tv₂, . . . where each tv₁ is the method that is actually invoked at run-time.

[0100] Definition 10 states that two hierarchies and ′ are behaviorally equivalent if the same sequence of statements is executed using the two hierarchies, for all given clients of with appropriate inputs and initial states. Definition 11 states that a composed hierarchy ₁⊕₂ exhibits dynamic interference if ₁ and ₁⊕₂ are not behaviorally equivalent (for some client of ₁ with associated input and initial state), or if ₂ and ₁⊕₂ are not behaviorally equivalent (for some client of ₂ with associated input and initial state).

[0101] Definition 10 (behavioral equivalence). Two hierarchies , ′ are behaviorally equivalent if for all clients K of with appropriate inputs and initial states I, σ₀ we have that E(, K, I, σ₀)=E(′, K, I, σ ).

[0102] Definition 11 (dynamic interference). ₁⊕₂ contains dynamic interference, if (for some ₁-client K with associated I, σ₀) ₁ and ₁⊕₂ are not behaviorally equivalent, or if (for some ₂-client K with associated I, σ₀) ₂ and ₁⊕₂ are not behaviorally equivalent.

[0103] Remark. From an observational point of view, E(₁, K, I, σ₀)=E(₁, ₂, K, I, σ₀) is not a necessary condition for behavioral equivalence, because a modified sequence of statements might still produce the same visible effects. However, we are not interested in cases where the observable behavior of a client of a composed hierarchy is accidentally identical to its original behavior.

Checking for Dynamic Interference

[0104] We would like to verify whether or not a certain composition exhibits dynamic interference. In general, determining whether or not two arbitrary programs will execute the same statement sequences for all possible inputs is undecidable of course. However, for the compositions studied in this present invention, the situation is not hopeless. Our approach will be to develop a noninterference criterion that implies E(₁, K, I, σ₀)=E(₁⊕₂, K, I, σ₀) that is based on static analysis information. This approach is also used in our earlier work on semantics-preserving class hierarchy transformations see generally G. Snelting and F. Tip. “Understanding Class Hierarchies Using Concept Analysis” ACM Trans. on Programming Languages and Systems, pages 540–582, May 2000 and Gregor Snelting and Frank Tip “Reengineering class hierarchies using concept analysis” In Proc. ACM SIGSOFT Symposium on the Foundations of Software Engineering, pages 99–110, Orlando, Fla., November 1998. Being a sufficient, but not a necessary condition, our criterion may occasionally generate false alarms. However, we believe that the impact analysis of Section 4 will provide the user with sufficient information to determine whether reported interferences can occur in practice.

[0105] Definition 12 defines a function srcHierarchy that defines the class hierarchy that a program construct originated from. The srcHierarchy of an object is defined as the srcHierarchy of the statement that created it. Definition 13 uses srcHierarchy to define the projection of a state onto a hierarchy.

[0106] Definition 12 (srcHierarchy). For =(C, ≦), C=<c, M>∈, m∈M and a statement s in body (m), we write srcHierarchy(C)=srcHierarchy(m)=srcHierarchy(s)=. Moreover, let s≡new C( . . . ) be an object creation site, and let object o∈Value be an instance of C created by s at run-time. Then, srcHierarchy (o)=srcHierarchy (s). Further, for any x∈Var, we define srcHierarchy(x)=srcHierarchy(s), where s is the static program part responsible for the creation of x at run-time.

[0107] Definition 13 (state projection). The projection of a program state σ onto a hierarchy is defined as σ|={xv|xv∈σ, srcHierarchy(x)=}. Moreover, we extend the projection operator to apply to a sequence of program states as follows:

[0108] Σ(₁⊕₂, K, I, σ₀)|₁=σ₀|₁→σ₁|₁→σ₂|₁→ . . . , where Σ(_{1 2}, K, I, σ₀)=σ₀→σ₁→σ₂→

[0109] The noninterference criterion relies on information produced by a points-to analysis. A points-to analysis computes for each reference-typed variable the set of objects that it may point to. Definitions 14 and 15 define appropriate notions ObjectRefs of object references and Objects of objects.

[0110] Definition 14 (object reference). Let be a hierarchy. Then, ObjectRefs ()Var is the set of all object references in . This includes class-typed local variables, method parameters, fields, static variables, and this pointers of methods.

[0111] Definition 15 (object). Let be a hierarchy. Then, Objects() is the set of all object creation sites in , that is, all statements S≡new C( . . . ); occurring in some method body. Moreover, for o∈Objects(), o≡new C( . . . ), we define TypeOf (, o)=C.

[0112] Object creation sites in Objects() should not be confused with run-time objects in Value. Finally, Definition 16 formalizes the notion of points-to sets. We do not make any assumptions about the specific algorithm used to compute these points-to sets. Any method suitable for object-orientated languages will do such as Donglin Liang, Maikel Pennings, and Mary Jean Harrold Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for java. In Proc. ACM SIG-PLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01, pages 73–79, Snowbird, Utah, 2001 and Atanas Rountev, Ana Milanova, and Barbara G. Ryder. Points-to analysis for java using annotated constraints. In Proc. ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'01), Tampa, Fla., 2001.

[0113] Definition 16 (points-to sets). Let be a hierarchy, and let p∈ObjectRefs (). Then PointsTo(, p) Objects () is the set of all objects (represented by creation sites) that object reference p might point to at run-time.

[0114] The noninterference criterion (Definition 17) states that the method invoked by a virtual method call p.m( . . . ) (as determined by applying StaticLookup on the receiver object) in ₁⊕₂ is the same as it was in ₁. Note that the condition does not say anything about ₂ objects. While the points-to sets in the composed hierarchy may also contain ₂ objects, these objects are never created by clients of ₁, and therefore need not be considered.

[0115] Definition 17 (noninterference criterion).

[0116] A composition ₁⊕₂ meets the noninterference criterion if for all p∈ObjectRefs (₁), for all method calls p.m( . . . ) in ₁, and for all o∈PointsTo(_{1 2}, p) ∩ Objects (₁) we have that StaticLookup(₁, T, m)=StaticLookup(₁⊕₂, T′, m) where T=TypeOf (₁, o), and T′=TypeOf(₁⊕₂, o).

[0117] The use of points-to information deserves a few more comments. First, one might wonder about the consequences of using imprecise points-to information (i.e., overly large points-to sets). In this case, the “for all o” in the noninterference criterion runs over a larger scope than necessary, making the criterion stronger than necessary, and spurious interference may be reported. However, the criterion is safe in the sense that it will never erroneously report non-interference.

[0118] Note also that the criterion is much more precise than the static checks from Section 2. To see this, consider again the examples of FIGS. 5 and 6. One could argue that the simple interferences in these examples are not really dynamic. In fact, one could report static interference in the examples of FIGS. 5 and 6 by modifying members(C) to also include members in superclasses of C (as opposed to only the members defined locally in C). So why use the more complex criterion of Definition 17? The reason is that, for large programs, the suggested modified static interference check will report interference even if the class exhibiting the changed behavior is never used in the program. In Definition 17, the scope of the key condition
StaticLookup(₁⊕₂, T, m)=StaticLookup(₁, T′, m)
is limited by the size of the points-to set associated with the receiver of the method call. This effectively restricts the condition to method calls that are actually reachable, and to many fewer spurious interferences being reported.

[0119] Most points-to analysis algorithms compute information that is valid for a specific client K This has the advantage that the points-to sets are more precise, reducing the number of false alarms. However, in this case the noninterference criterion only holds for the client K. To compute results that are safe for any client, one could employ algorithms such as Atanas Rountev, Barbara G. Ryder, and William Landi, “Data-flow analysis of program fragments” In Proceedings of Symposium on the Foundations of Software Engineering (FSE 1999), pages 235–252, Toulouse, France, 1999 that are capable of analyzing incomplete programs.

[0120] Concerning the complexity of the interference test, it is dominated by the computation of points-to information, as the test itself just performs two static lookups per member access, which is linear in the program size. Various points-to algorithms of various precisions are known, ranging from Steengaard's almost linear algorithm (which scales millions of LOC) to Andersen's cubic algorithm which has recently been scaled to a million-line C-program by using a new approach for dynamically computing transitive closures. The performance of this algorithm on object-oriented applications are still unknown, as far as we know.

Justification

[0121] We will now demonstrate that the noninterference criterion of Definition 17 ensures that the behavior of client K of ₁ is preserved. The analogous argument for ₂ is completely symmetrical.

[0122] Lemma 3 states that it is sufficient to demonstrate that the sequence of call targets in ₁ does not change after composition.

[0123] Lemma 3. For all K, I and σ₀, we have that: T(₁, K, I, σ₀)=T(₁⊕₂, K, I, σ₀)E(₁, K, I, σ₀)=E(₁⊕₂, K, I, σ₀) and therefore: T(₁, K, I, _σ0)=T (₁⊕₂, K, I, σ₀)Σ(₁, K, I, σ₀)=Σ(₁⊕₂, K, I, σ₀)|₁

[0124] Proof. The proof is by induction on the length n of sequence E(₁, K, I, σ₀). For n=0, the statement is trivial, as both hierarchies start in state σ₀. Now consider statement Sn in E(₁, K, I, σ₀). By induction, the previously executed statements S₁, S_{2, . .} . S_n-1 are the same in both E(₁, K, I, σ₀) and E(₁⊕₂, K, I, σ₀), and lead to corresponding states σ_n-1 and σ_n-1|₁, respectively.

[0125] Now, S_nis a statement at some position π in some method m₁ of ₁. By assumption, the sequence of executed method bodies is the same in ₁⊕₂. Since there is no static interference, we may conclude that we are at the same position π in some method m₂ in ₁⊕₂, for which body(m₁)=body(m₂). Hence, S_n is also the next statement to be executed in E(₁⊕₂, K, I, σ₀).

[0126] Now there are two cases. 1) S_n is a method call p.m( . . . ). Then, by assumption, this call resolves to the same target tv_| which is executed in the same state σ_n-1. Thus, after execution of the method body, both hierarchies are in the same state σ_n at the same position π′ in the same method bodies m₁ and m₂.) S_n is not a method call. Then, it must be the same in m₁ and m₂ due to the absence of static interference. Hence, after execution, the same state σ_n is reached.

[0127] Theorem 1 (correctness of criterion). Let ₁⊕₂ be a composition that meets the noninterference criterion of Definition 17. Then, we have that: E(₁, K, I, σ₀)=E(₁⊕₂, K, I, σ₀) and Σ(₁, K, I, σ₀)=Σ(₁⊕₂, K, I, σ₀)|₁, for all K, I, σ₀.

[0128] Proof. Again the proof is by induction on n. For n=0 the statement is trivial, as both hierarchies start in state σ₀. Now consider statement S_n in E(₁, K, I, σ₀). By induction, the previously executed statements S₁, S₂, . . . S_n-1 are the same in both E(₁, K, I, σ₀) and E(₁⊕₂, K, I, σ₀) and lead to corresponding states σ_n-1 and σ_n-1|₁, respectively. As in the previous lemma, we may conclude that S_n is the same in both execution sequences. (This time the necessary fact that the previous call targets have been the same is not by assumption, but by induction: if S₁, S₂, . . . are the same in both E(₁, K, I, σ₀) and E(₁⊕₂, K, I, σ₀), so are S₁, S₂, . . . and tv₁, tv₂, . . . ).

[0129] Now there are two cases. If S_n is not a method call or data member access, we may conclude that the corresponding states σ_n and σ_n|₁ are produced in Σ(₁, K, I, σ₀) and Σ(₁⊕₂, K, I, σ₀)|₁, respectively. In case S_n=p.m(x), we know σ_n-1(p)∈PointsTo(₁⊕₂, p) (remember that σ_n-1 was reached in both ₁ and _1⊕2). Furthermore, σ_n-1(p)∈Objects (₁), as σ_n-1|₁∈Σ(₁, K, I, σ₀), and ₁ does not contain ₂ objects.

[0130] We know StaticLooku (₁, TypeOf(₁,o), m)≠⊥ and by the type correctness lemma thus StaticLookup(₁⊕₂, TypeOf(₁⊕₂, o), m)≠⊥. By the static noninterference criterion, both static lookups must compute the same result, namely method definition (resp. data member) m. After execution of m's body (resp. access to m's value in state σ_n-1), we may as in the above lemma conclude that execution of both hierarchies is in the same state σ_n.

[0131] For the example of FIG. 5, we have PointsTo(₁, o)=PointsTo(₁⊕₂, o)={B1}. For the method call o.foo( ), we obtain StaticLookup (₁, TypeOf(₁,B₁), foo( ))=StaticLookup (₁, B, foo( ))=A.foo( ), but StaticLookup(₁⊕₂,TypeOf(₁⊕₂, B1), foo( ))=StaticLookup(₁⊕₂, B, foo( ))=B.foo( ). Hence, dynamic interference is reported.

[0132] In Example 7 and in subsequent examples, we use the labels shown in boxes in FIG. 1 to identify object creation sites.

[0133] For client Driver1.main( ) in FIG. 2, we obtain PointsTo(₁⊕₂, c1) ∩Objects(₁)={C1}, PointsTo(₁⊕₂, p1) ∩Objects( ₁)={P1}. Hence, StaticLookup(₁, TypeOf(₁, C1), enroll( ))=Course.enroll( )=StaticLookup(₁⊕₂, TypeOf(₁⊕₂, C1), enroll( )). Moreover, we have that StaticLookup(₁, TypeOf(₁, C1), assign( ))=Course.assign( )=StaticLookup(₁⊕₂, TypeOf(₁⊕₂, C1), assign( )), and that StaticLookup( ₁,TypeOf(₁, P1), approveGraduationo)=Professor.approveGraduation( )=StaticLookup(₁⊕₂,TypeOf(₁⊕₂, P1), Professor.approveGraduation( )). Similar arguments can be made for all other method calls in FIG. 2. Hence, the behavior of Driver1.main( ) in ₁ is preserved in ₁⊕₂. In fact, the basic composition in FIG. 2 preserves the behavior of any possible client. Potential clients may introduce arbitrary allocation sites and arbitrary points-to relationships. A conservative approximation must therefore assume that for any member access p.m( . . . )∈₁, PointsTo(₁⊕₂, p) ∩ Objects(₁) contains all allocation sites S∈Objects(₁) where TypeOf(₁⊕₂, S)≦TypeOf(₁⊕₂, P). Nevertheless, StaticLookup(₁, TypeOf(₁, S), m)=StaticLookup(₁⊕₂, TypeOf(₁⊕₂, S), m), because in the example the methods from ₁ and ₂ are either disjoint or identical.

Overriding Compositions

[0134] The noninterference criterion was designed for basic compositions. It can be applied to overriding compositions as well, but will report failure as soon as a method call p.m( . . . ) resolves to methods that have different bodies in ₁ and ₁⊕₂. Nevertheless, interference checks may still succeed if the overridden methods are not reachable from client code. Constructing an interference check for overriding compositions that ignores conflicts that users are aware of (via the <<-ordering) is a topic for future research.

[0135] Let us apply the criterion to FIG. 6. We have PointsTo(₁, a)=PointsTo(₁⊕₂, a)={B1}, but due to the overriding, StaticLookup(₁, TypeOf(₁, B₁), foo)=A.foo( )₁≠A.foo( )₂=StaticLookup (₁⊕₂, TypeOf(₁⊕₂, B₁), foo( )). Here, we use subscripts ₁ and ₂ to indicate the hierarchies that the different methods A.foo( ) originate from. Hence, the behavior of call a.foo( ) is not preserved. For call x.bar( ), we obtain PointsTo(₁⊕₂, x)={B2}, hence PointsTo(₁⊕₂, x) ∩ Objects(₁)=Ø Thus the criterion is trivially satisfied for x.bar( ).

[0136] Remark: In Example 8, one might wonder why the criterion is satisfied for x.bar( ) despite the fact that the behavior of this call obviously changed: We have that B.bar( ) is called in ₁⊕₂ whereas A.bar( ) was called in ₁. This secondary behavioral change is caused by another change in behavior (in this case, the changed behavior of call a.foo( ), which causes x to be bound to an object of type B). While the noninterference criterion does not necessarily detect secondary behavioral changes, it does find all primary changes, which suffices to guarantee behavioral equivalence. We plan to use impact analysis to obtain a more precise understanding of where behavioral changes occur, as will be discussed in Section 4.

Impact Analysis

[0137] When the purpose of composition is to add functionality that is not completely orthogonal to the system's existing functionality, changes in behavior are often unavoidable. The interference check of Section 3 determines whether the behavior of a specific client K is affected. In principle, one could manually apply the interference check to successively smaller clients to determine the impact of the composition. However, such a non-automated process would be tedious and labor-intensive, and problematic in cases where it is not possible to partition the code in K In order to provide a less labor-intensive approach, we plan to adapt the change impact analysis of Barbara, G. Ryder and Frank Tip. Change impact analysis for object-oriented programs. In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), pages 46–53, Snowbird, Utah. June 2001 in order to automatically determine the set of program constructs affected by a composition. The remainder of this section presents some preliminary ideas on how this can be accomplished.

Change Impact Analysis

[0138] We begin with a brief review of the change impact analysis. In this work, it is assumed that a program is covered by a set of regression test drivers T=t₁, . . . , t_n. Each test driver is assumed to consist of a separate main routine from which methods in the application are called. Prior to the editing session, a call graph G_i is built for each t₁. Any of several existing call graph construction algorithms can be used. We plan to employ an algorithm that has been demonstrated to scale to large applications see generally Frank Tip and Jens Palsberg, “Scalable Propagation-Based Call Graph Construction Algorithms”, In Proc. ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'00), pages 281–293, Minneapolis, Minn., 2000. SIGPLAN Notices 35(10).

[0139] After the user has ended the editing session, the edits are decomposed into a set A of atomic changes. A consists of (i) a set AC of (empty) classes that have been added, (ii) a set DC of classes that have been deleted, (iii) a set AM of methods that have been added, (iv) a set DM of methods that have been deleted, (v) a set CM of methods whose body contains one or more changed statements, (vi) a set AF of fields that have been added,(vii) a set DF of fields that have been deleted, and (viii) a set LC of elements of the form <T, C.m( )>, indicating that the dispatch behavior for a call to C.m( ) on an object type T has changed. In general, a simple user edit can imply several atomic changes. For example, addition of a method may involve the addition of an empty method (in AM), a change in dispatch behavior (in LC) of existing call sites in cases where the added method overrides an existing method, and a change of a method body (in CM).

[0140] By analyzing the call graphs G_i and the set of atomic changes A, a subset of affected tests T′T is determined. FIG. 7 shows how correlating the nodes and edges in the call graphs for the test drivers with the CM, DM, and LC changes leads to the identification of a set of affected tests t_i. Here, Nodes(P, t_i) and Edges(P, t_i) denote the set of nodes resp. edges in the call graph for test driver t_i. Informally, the formula shown in the figure states that a test driver t_i is potentially affected if a node in the call graph for t_i corresponds to a deleted or changed method (line1), or if one of the edges in the call graph for t_i corresponds to a dispatch relation that has been changed (lines2 3).

[0141] Any test driver that is not in T′ is guaranteed to have the same behavior as before. If a test driver t_i occurs in T, the user can run this test to determine if the new behavior of the test meets his expectations. If this is not the case, an additional analysis (also based on call graphs) determines a subset of atomic changes A′A that contribute to t_i's altered behavior. The user can apply successively larger subsets of A′ to identify the change that “broke” test driver t_i. Alternatively, divide-and-conquer strategies can be applied to quickly narrow down the search space such as Andreas Zeller “Yesterday my program worked. Today, it does not. Why?” In Proc. of the 7th European Software Engineering Conf./7th ACM SIGSOFT Symp. on the Foundations of Software Engineering (ESEC/FSE'99), pages 253–267, Toulouse, France, 1999.

Impact Analysis for Composition

[0142] We adapt the analysis to determine the impact of a composition ₁⊕₂ on a set of test drivers T=t₁, ,t_k associated with hierarchy H_i by interpreting a composition as a set of changes w.r.t _i such as Barbara G. Ryder and Frank Tip. Change impact analysis for object-oriented programs such as In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), pages 46–53, Snowbird, Utah. June 2001. To do so, we need to establish a relationship between classes/members in ₁⊕₂, and the classes/members in ₁ and ₂ that these classes/members originate from. This is expressed by Definition 18 below.

[0143] Definition 18 (origin). Let ₁=(C_1,≦1) and ₂=(C₂,≦₂) be two class hierarchies, let =₁⊕₂=(C, ≦), and let ε be the set of equivalence classes constructed by Definition 2. Furthermore, let C be a class in C, and let m∈members (C).

[0144] Define:

• • [0145] origin(C)={<C′, >|S∈ε, name(S)=name(C), <C′, >∈S}
  • [0146] origin(m)={<C′, m′, >|<C′, >∈origin(C), m′∈members (C′), namesig(m)=namesig(m′), body (m)=body(m′)

[0147] Definition 18 defines the origin of a class C in C as the set of (class,hierarchy) pairs in its equivalence class, and the origin of a method m in C is the set of methods in each such class with the same name and body as m. Note that these definitions work with both of the members definitions given earlier.

[0148] For hierarchy =₁⊕₃ of FIG. 3 we have origin(Professor)={<Professor, ₁>, <Professor, ₃>} and origin(Professor.approveGraduation)={<Professor, approveGraduation, ₃>}.

[0149] It is now straightforward to construct the sets of atomic changes w.r.t. one of the original hierarchies. For example, for the composition =₁⊕₃, where =<C,≦>, ₁=<C₁,≦₁>, and ₃=<C₄,≦₄>, the sets AC and CM w.r.t. ₁ may be computed as:

• • [0150] AC={C′|<C′, ′>∈origin(C), C∈C, ′≠₁}
  • [0151] CM={m′|<C′, ₁>∈origin(C), C∈C, m′∈members (C), origin(m′)=Ø in members (C′)s.t. namesig(m)=namesig(m′) and body(m)=body(m)}

[0152] The other sets of atomic changes are computed similarly. We can now apply the analysis to determine the impact of the composition.

[0153] Consider the overriding composition of FIG. 3, for which we previously found that behavior could not be preserved (see Example 8). We will now apply impact analysis to obtain a more precise understanding of where the inferences occur. Interpreting the ₁⊕₃, as a set of changes w.r.t. ₁, we find that Driver1.main( ) is affected, because CM contains method Professor.approveGraduation( ), which occurs in the call graph for Driver1.main( ). Moreover, interpreting ₁⊕₃ as a set of changes w.r.t. ₃, we find that Driver3.main( ) is not affected, because the call graph for Driver3.main( ) does not contain any added, changed, or deleted methods, or any edges corresponding to a changed dispatch behavior.

[0154] Thus far, we have computed the impact of a composition on a set of test drivers. In order to obtain more fine-grained information, one could construct a separate call graph for each method m in hierarchy ₁ (using appropriate conservative assumptions about the run-time types of parameters and accessed fields), and proceed as before. Then, impact could be reported as the set of methods whose behavior might have changed. For example, if separate call graphs are constructed for all methods of ₁ in the overriding composition ⊕₃ of FIG. 3, we can report that only the behavior of methods Driver1.main( ) and Professor.approveGraduation( ) is impacted by the composition because these are the only methods that transitively call methods whose behavior may have changed. Space limitations prevent us from providing more details.

Related work

[0155] We already discussed how our impact analysis is a derivative of the change impact analysis (see Barbara G. Ryder and Frank Tip. Change impact analysis for object-oriented programs. In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), pages 46–53, Snowbird, Utah., June 2001). Offutt and Li (see Michelle L. Lee, “Change Impact Analysis Of Object-Oriented Software”, PhD thesis, George Mason University, 1998 and Michelle L. Lee and A. Jefferson Offutt, “Algorithmic Analysis Of The Impact Of Changes To Object-Oriented Software”, in IEEE International Conference on Software Maintenance, pages 171–184, Monterey, Calif., November 1996) also presented a change impact analysis for object oriented programs, which only relies on structural relationships between classes and members (e.g., containment), and is therefore much less precise than approaches such as Barbara G. Ryder and Frank Tip, “Change Impact Analysis For Object-Oriented Programs”, in Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), pages 46–53, Snowbird, Utah., June 2001 that rely on static analysis.

Exemplary Implementations

[0156] The present invention can be realized in hardware, software, or a combination of hardware and software. A system according to a preferred embodiment of the present invention can be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system—or other apparatus adapted for carrying out the methods described herein—is suited. A typical combination of hardware and software could be a general-purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein.

[0157] An embodiment of the present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out these methods. Computer program means or computer program in the present context mean any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following a) conversion to another language, code or, notation; and b) reproduction in a different material form.

[0158] A computer system may include, inter alia, one or more computers and at least a computer readable medium, allowing a computer system, to read data, instructions, messages or message packets, and other computer readable information from the computer readable medium. The computer readable medium may include non-volatile memory, such as ROM, Flash memory, Disk drive memory, CD-ROM, and other permanent storage. Additionally, a computer readable medium may include, for example, volatile storage such as RAM, buffers, cache memory, and network circuits. Furthermore, the computer readable medium may comprise computer readable information in a transitory state medium such as a network link and/or a network interface, including a wired network or a wireless network, that allow a computer system to read such computer readable information.

[0159] FIG. 8 is a block diagram depicting the hardware hierarchy of a computer system useful for implementing an embodiment of the present invention. The computer system includes one or more processors, such as processor 804. The processor 804 is connected to a communication infrastructure 802 (e.g., a communications bus, cross-over bar, or network). Various software embodiments are described in terms of this exemplary computer system. After reading this description, it will become apparent to a person of ordinary skill in the relevant art(s) how to implement the invention using other computer systems and/or computer architectures.

[0160] The computer system can include a display interface 808 that forwards graphics, text, and other data from the communication infrastructure 802 (or from a frame buffer not shown) for display on the display unit 810. The computer system also includes a main memory 806, preferably random access memory (RAM), and may also include a secondary memory 812. The secondary memory 812 may include, for example, a hard disk drive 814 and/or a removable storage drive 816, representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive 816 reads from and/or writes to a removable storage unit 818 in a manner well known to those having ordinary skill in the art. Removable storage unit 818, represents a floppy disk, magnetic tape, optical disk, etc. which is read by and written to by removable storage drive 816. As will be appreciated, the removable storage unit 818 includes a computer usable storage medium having stored therein computer software and/or data.

[0161] In alternative embodiments, the secondary memory 812 may include other similar means for allowing computer programs or other instructions to be loaded into the computer system. Such means may include, for example, a removable storage unit 822 and an interface 820. Examples of such may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units 822 and interfaces 820 which allow software and data to be transferred from the removable storage unit 822 to the computer system.

[0162] The computer system may also include a communications interface 824. Communications interface 824 allows software and data to be transferred between the computer system and external devices. Examples of communications interface 824 may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, etc. Software and data transferred via communications interface 824 are in the form of signals which may be, for example, electronic, electromagnetic, optical, or other signals capable of being received by communications interface 824. These signals are provided to communications interface 824 via a communications path (i.e., channel) 826. This channel 826 carries signals and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link, and/or other communications channels.

[0163] In this document, the terms “computer program medium,” “computer usable medium,” and “computer readable medium” are used to generally refer to media such as main memory 806 and secondary memory 812, removable storage drive 816, a hard disk installed in hard disk drive 814, and signals. These computer program products are means for providing software to the computer system. The computer readable medium allows the computer system to read data, instructions, messages or message packets, and other computer readable information from the computer readable medium. The computer readable medium, for example, may include non-volatile memory, such as Floppy, ROM, Flash memory, Disk drive memory, CD-ROM, and other permanent storage. It is useful, for example, for transporting information, such as data and computer instructions, between computer systems. Furthermore, the computer readable medium may comprise computer readable information in a transitory state medium such as a network link and/or a network interface, including a wired network or a wireless network, that allow a computer to read such computer readable information.

[0164] Computer programs (also called computer control logic) are stored in main memory 806 and/or secondary memory 812. Computer programs may also be received via communications interface 824. Such computer programs, when executed, enable the computer system to perform the features of the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor 804 to perform the features of the computer system. Accordingly, such computer programs represent controllers of the computer system.

[0165] FIG. 9 is a block diagram illustrating the software hierarchy for the computer or other information processing device 800 of FIG. 8 according to the present invention. The hardware 800 is the information processing system of FIG. 8. BIOS (Basic Input Output System) 902 is a set of low level of computer hardware instructions, usually stored in main memory 806, for communications between an operating system 906, device driver(s) 9046 and hardware 800. Device drivers 906 are hardware specific code used to communicate between and operating system 906 and hardware peripherals such as a mouse, CD ROM drive or printer. Applications 908 are software application written in C/C++, Java, assembler or equivalent. Operating system 906 is the master program that loads after BIOS 902 initializes, that controls and runs the hardware 800. Examples of operating systems include DOS, Windows 3.1/95/98/NT, Unix, Macintosh, OS/2 and equivalent.

[0166] The present invention can be implemented as an application 808 such as a tool kit as part of a compiler such as IBM VisualAge™ line of products or IBM WebSphere™ those available from Borland or Microsoft and programming environments Eclipse or other open source platforms (www.eclipse.org). In another embodiment, the present invention is implemented as part of a compiler and messages are presented to a user during the reporting of behavior differences during the class compositions.

[0167] It is important to note, that any behavioral difference of methods and/or fields as compared application A₁ as executing against composed hierarchy ₃ with application A₁ as executing against the composed hierarchy₁.(and similarly with A₂) can be formed into a report. In one embodiment this report is editable with interactive tools such as browsers and editors and portions of the program text that have behavior differences are marked or highlighted for user review.

[0168] It should be understood by those skilled in the art that the present invention provided a basis to provide better semantic support for composition-based software development. The present invention provides the basis for other work that includes:

• • [0169] Handling the peculiarities of particular programming languages such as Java (exception handling) where the present invention abstracts away from peculiarities of specific programming languages.
  • [0170] “Merging” compositions, in which two interfering methods m₁ and m₂ are “merged” in some user-specified way (e.g., by constructing a new method that first executes the body of m₁ and then that of m₂).
  • [0171] More interference tests can that can provide behavioral guarantees even in the presence of dynamic interference, by taking into account those conflicts that users have explicitly resolved.
  • [0172] We have outlined how the impact analysis can be used to obtain a more detailed view of where behavioral interferences occur. We consider this to be a topic that needs much further thought.
  • [0173] In practice, class hierarchy compositions are often performed with the intention of changing program behavior. We consider methods for distinguishing behavioral changes expected by the user from unanticipated behavioral changes to be an important research topic. Such methods could be used to filter the information produced by the impact analysis.

[0174] Although specific embodiments of the invention have been disclosed, those having ordinary skill in the art will understand that changes can be made to the specific embodiments without departing from the spirit and scope of the invention. The scope of the invention is not to be restricted, therefore, to the specific embodiments. Furthermore, it is intended that the appended claims cover any and all such applications, modifications, and embodiments within the scope of the present invention.