Method and apparatus for slicing class hierarchies

• US 6,179,491 B1
• Filed: 02/05/1997
• Issued: 01/30/2001
• Est. Priority Date: 02/05/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Field, John H., Ramalingam, Ganesan, Tip, Frank, Choi, Jong-Deok
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Sattizahn, Brian
• Application Number:
  US08/794,986
• Time in Patent Office: 1,455 Days
• Field of Search: 395/704, 395/709, 395/702, 395/703
• US Class Current: 717/116
• CPC Class Codes: G06F 9/4492 Inheritance

Abstract

Given a class hierarchy (a collection of classes and inheritance relations among them) and a program P that uses the hierarchy, a slice of the class hierarchy is computed with respect to the program by eliminating from the hierarchy those data members, member functions, classes, and inheritance relations that are unnecessary for ensuring that the semantics of P is maintained.

Claims

1. In a system wherein a computer program has a class hierarchy comprising a plurality of components including classes of objects, a method for generating a run-time representation of said computer program, the method comprising the steps of:

i) identifying a first class of objects and a second class of objects, wherein said first class inherits from said second class, said second class being known as a base class and said first class being known as a derived class, and wherein components of said class hierarchy include an inheritance relation that identifies said second class as a base class with respect to said first class and that identifies said first class as a derived class with respect to said second class, wherein each object within said first class of objects includes an object of said second class as a subobject, and wherein for any object O of said first class of objects, said subobject of O belonging to the said second class of objects is not accessed during any execution of said computer program;

ii) generating said run-time representation of said computer program that includes said first class of objects yet omits said inheritance relation between said first class and said second class; and

wherein said step i) includes the step of examining components of said class hierarchy.

2. The method of claim 1, wherein omitting said inheritance relation between said first class and said second class results in omission from every object belonging to said first class a corresponding subobject belonging to said second class.

3. The method of claim 1, wherein said first class of objects of said computer program inherits from multiple classes of objects.

4. The method of claim 1, wherein said first class of objects of said computer program virtually inherits from said second class of objects.

5. In a system wherein a computer program has a class hierarchy comprising a plurality of components including classes of objects, a method for generating information characterizing said computer program, the method comprising the steps of:

i) identifying a first class of objects and a second class of objects, wherein said first class inherits from said second class, said second class being known as a base class and said first class being known as a derived class, and wherein components of said class hierarchy include an inheritance relation that identifies said second class as a base class with respect to said first class and that identifies said first class as a derived class with respect to said second class, wherein each object within said first class of objects includes an object of said second class as a subobject, and wherein for any object O of said first class of objects, said subobject of O belonging to the said second class of objects is not accessed during any execution of said computer program;

ii) notifying a user that objects of the said first class may be created and accessed during execution, but that said subobject representing said second class is never accessed during any execution of said computer program;

wherein said step i) includes the step of examining components of said class hierarchy.

6. The method of claim 5, wherein said first class of objects of said computer program inherits from multiple classes of objects.

7. The method of claim 5, wherein said first class of objects of said computer program virtually inherits from said second class of objects.

8. In a system wherein a computer program has a class hierarchy comprising a plurality of components including classes of objects and members of said classes, a method for generating a run-time representation of said computer program, the method comprising the steps of:

i) identifying at least one member m of said members of said computer program, wherein said member m is not accessed during any execution of said computer program; and

ii) generating a run-time representation of said computer program that omits said member m;

wherein step i) includes the step of examining components of said class hierarchy;

wherein step ii) includes the steps of;

iii) identifying a set of all members MT of said class hierarchy of said computer program;

iv) identifying a set of members M of said class hierarchy of said computer program, wherein each member within said set M may be accessed during some execution of said computer program; and

v) identifying all members of said computer program that are not accessed during any execution of said computer program as those members belonging to the set MT yet omitted from the set M;

further comprising the step of;

vi) identifying a first class of objects and a second class of objects, wherein said first class inherits from said second class, said second class being known as a base class and said first class being known as a derived class, and wherein components of said class hierarchy include an inheritance relation that identifies said second class as a base class with respect to said first class and that identifies said first class as a derived class with respect to said second class, wherein each object within said first class of objects includes an object of said second class as a subobject, and wherein for any object O of said first class of objects, said subobject of O belonging to the said second class of objects is not accessed during any execution of said computer program;

wherein said step ii) generates said run-time representation of said computer program that includes said first class of objects yet omits said inheritance relation between said first class and said second class; and

wherein said step vi) includes the step of examining components of said class hierarchy.

9. The method of claim 8, further comprising the steps of:

identifying in said computer program at least one member lookup operation wherein a member m1 is accessed from an expression e; and

identifying components of said class hierarchy that are necessary to preserve execution behavior of said member lookup operation.

10. The method of claim 9, further comprising the steps of:

identifying a first set of subobjects that e may denote during execution of said member lookup operation; and

for each subobject n within said first set of subobjects,

identifying a second set of subobjects contained within said subobject n that contains a visible definition of said member m1,

identifying a dominant subobject n′

in said second set of subobjects,

identifying a least derived class C for said dominant subobject n′

, and

adding member m1 belonging to said least derived class C to said set of members M; and

if member m1 belonging to said least derived class C is a virtual method,

identifying a most derived class D for said subobject n,

identifying a full subobject corresponding to said most derived class D,

identifying a third set of subobjects contained within said full subobject that contain a visible definition of said member m1,

identifying a dominant subobject n1′

in said third set of subobjects,

identifying a least derived class C1 for said dominant subobject n1′

, and

adding member m1 belonging to said least derived class C1 to said set of members M.

11. The method of claim 8, wherein omitting said inheritance relation between said first class and said second class results in omission from every object belonging to said first class a corresponding subobject belonging to said second class.

12. The method of claim 8, wherein said first class of objects of said computer program inherits from multiple classes of objects.

13. The method of claim 8, wherein said first class of objects of said computer program virtually inherits from said second class of objects.

14. A program storage device readable by a machine, tangibly embodying a computer program executable by said machine to perform a method for generating a run-time representation of said computer program, wherein said computer program has a class hierarchy comprising a plurality of components including classes of objects, said method comprising the steps of:

i) identifying a first class of objects and a second class of objects, wherein said first class inherits from said second class, said second class being known as a base class and said first class being known as a derived class, and wherein components of said class hierarchy include an inheritance relation that identifies said second class as a base class with respect to said first class and that identifies said first class as a derived class with respect to said second class, wherein each object within said first class of objects includes an object of said second class as a subobject, and wherein for any object O of said first class of objects, said subobject of O belonging to the said second class of objects is not accessed during any execution of said computer program;

ii) generating said run-time representation of said computer program that includes said first class of objects yet omits said inheritance relation between said first class and said second class; and

wherein said step i) includes the step of examining components of said class hierarchy.

15. The program storage device of claim 14, wherein omitting said inheritance relation between said first class and said second class results in omission from every object belonging to said first class a corresponding subobject belonging to said second class.

16. The program storage device of claim 14, wherein said first class of objects of said computer program inherits from multiple classes of objects.

17. The program storage device of claim 14, wherein said first class of objects of said computer program virtually inherits from said second class of objects.

18. A program storage device readable by a machine, tangibly embodying a program executable by said machine to perform a method for generating information characterizing a computer program having a class hierarchy comprising a plurality of components including classes of objects, the method comprising the steps of:

i) identifying a first class of objects and a second class of objects, wherein said first class inherits from said second class, said second class being known as a base class and said first class being known as a derived class, and wherein components of said class hierarchy include an inheritance relation that identifies said second class as a base class with respect to said first class and that identifies said first class as a derived class with respect to said second class, wherein each object within said first class of objects includes an object of said second class as a subobject, and wherein for any object O of said first class of objects, said subobject of O belonging to the said second class of objects is not accessed during any execution of said computer program;

ii) notifying a user that objects of the said first class may be created and accessed during execution, but that said subobject representing said second class is never accessed during any execution of said computer program;

wherein said step i) includes the step of examining components of said class hierarchy.

19. The program storage device of claim 18, wherein said first class of objects of said computer program inherits from multiple classes of objects.

20. The program storage device of claim 18, wherein said first class of objects of said computer program virtually inherits from said second class of objects.

21. A program storage device readable by a machine, tangibly embodying a computer program executable by said machine to perform a method for generating a run-time representation of said computer program, wherein said computer program has a class hierarchy comprising a plurality of components including classes of objects and members of said classes, said method comprising the steps of:

i) identifying at least one member m of said members of said computer program, wherein said member m is not accessed during any execution of said computer program; and

ii) generating a run-time representation of said computer program that omits said member m;

wherein step i) includes the step of examining components of said class hierarchy;

wherein step ii) includes the steps of;

iii) identifying a set of all members MT of said class hierarchy of said computer program;

iv) identifying a set of members M of said class hierarchy of said computer program, wherein each member within said set M may be accessed during some execution of said computer program; and

v) identifying all members of said computer program that are not accessed during any execution of said computer program as those members belonging to the set MT yet omitted from the set M;

further comprising the step of;

vi) identifying a first class of objects and a second class of objects, wherein said first class inherits from said second class, said second class being known as a base class and said first class being known as a derived class, and wherein components of said class hierarchy include an inheritance relation that identifies said second class as a base class with respect to said first class and that identifies said first class as a derived class with respect to said second class, wherein each object within said first class of objects includes an object of said second class as a subobject, and wherein for any object O of said first class of objects, said subobject of O belonging to the said second class of objects is not accessed during any execution of said computer program;

wherein said step ii) generates said run-time representation of said computer program that includes said first class of objects yet omits said inheritance relation between said first class and said second class; and

wherein said step vi) includes the step of examining components of said class hierarchy.

22. The program storage device of claim 21, further comprising the steps of:

identifying in said computer program at least one member lookup operation wherein a member m1 is accessed from an expression e; and

identifying components of said class hierarchy that are necessary to preserve execution behavior of said member lookup operation.

23. The program storage device of claim 22, further comprising the steps of:

identifying a first set of subobjects that e may denote during execution of said member lookup operation; and

for each subobject n within said first set of subobjects,

identifying a second set of subobjects contained within said subobject n that contains a visible definition of said member m1,

identifying a dominant subobject n′

in said second set of subobjects,

identifying a least derived class C for said dominant subobject n′

, and

adding member m1 belonging to said least derived class C to said set of members M; and

if member m1 belonging to said least derived class C is a virtual method,

identifying a most derived class D for said subobject n,

identifying a full subobject corresponding to said most derived class D,

identifying a third set of subobjects contained within said full subobject that contain a visible definition of said member m1,

identifying a dominant subobject n1′

in said third set of subobjects,

identifying a least derived class C1 for said dominant subobject n1′

, and

adding member m1 belonging to said least derived class C1 to said set of members M.

24. The program storage device of claim 21, wherein omitting said inheritance relation between said first class and said second class results in omission from every object belonging to said first class a corresponding subobject belonging to said second class.

25. The program storage device of claim 21, wherein said first class of objects of said computer program inherits from multiple classes of objects.

26. The program storage device of claim 21, wherein said first class of objects of said computer program virtually inherits from said second class of objects.