Abstract
A new method is presented for analyzing and reengineering class hierarchies. In our approach, a class hierarchy is processed along with a set of applications that use it, and a fine-grained analysis of the access and subtype relationships between objects, variables, and class members is performed. The result of this analysis is again a class hierarchy, which is guaranteed to be behaviorally equivalent to the original hierarchy, but in which each object only contains the members that are required. Our method is semantically well-founded in concept analysis: the new class hierarchy is a minimal and maximally factorized concept lattice that reflects the access and subtype relationships between variables, objects and class members. The method is primarily intended as a tool for finding imperfections in the design of class hierarchies, and can be used as the basis for tools that largely automate the process of reengineering such hierachies. The method can also be used as a space-optimizing source-to-source transformation that removes redundant fields from objects. A prototype implementation for Java has been constructed, and used to conduct several case studies. Our results demonstrate that the method can provide valuable insights into the usage of a class hierarchy in a specific context, and lead to useful restructuring proposals.
- Accredited Standards Committee X3. 1997. Working paper for draft proposed international standard for information systems|programming language C++. Doc. No. X3J16/97-0108.Google Scholar
- Agesen, O. and Ungar, D. 1994. Sifting out the gold: Delivering compact applications from an exploratory object-oriented programming environment. In Proceedings of the Ninth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOP-SLA'94). Portland, OR, 355-370. ACM SIGPLAN Notices 29(10). Google Scholar
- Andersen, L. O. 1994. Program analysis and specialization for the c programming language. Ph.D. thesis, DIKU, University of Copenhagen. DIKU report 94/19.Google Scholar
- Astudillo, H. 1997. Maximizing object reuse with a biological metaphor. Theory and practice of object systems 3, 4, 235-251. Google Scholar
- Bacon, D. F. and Sweeney, P. F. 1996. Fast static analysis of C++ virtual function calls. In Proceedings of the Eleventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'96). San Jose, CA, 324-341. ACM SIGPLAN Notices 31(10). Google Scholar
- Ball, T. 1999. The concept of dynamic analysis. In Proceedings of the Seventh European Software Engineering Conference Held Jointly with the Seventh ACM SIGSOFT Symposium on the Foundations of Software Engineering. Toulouse, France, 216-234. Google Scholar
- Bent, L., Atkinson, D., and Griswold, W. G. 2000. A comparative study of two whole-program slicers for C. Tech. Rep. CS2000-643, UCSD. May. Google Scholar
- Birkhoff, G. 1940. Lattice Theory. American Mathematical Society.Google Scholar
- Bogemann, A. and Streckenbach, M. 1999. KABA: Reengineering class hierarchies using concept lattices. M.S. thesis, Technische Universitat Braunschweig, Germany.Google Scholar
- Casais, E. 1998. Reengineering of object-oriented legacy systems. Journal of object-oriented programming, 45-52.Google Scholar
- Choi, J., Grove, D., Hind, M., and Sarkar, V. 1999. E cient and precise modeling of exceptions for the analysis of java programs. In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE '99). ACM, Toulouse, France, 21-31. Google Scholar
- Choi, J.-D., Burke, M., and Carini, P. 1993. E cient ow-sensitive interprocedural computation of pointer-induced aliases and side e ects. In Conference Record of the Twentieth ACM Symposium on Principles of Programming Languages. ACM, 232-245. Google Scholar
- Das, M. 2000. Uni cation-based pointer analysis with directional assignments. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'00). Vancouver, Canada, 35-46. Appeared as ACM SIGPLAN Notices 35(5). Google Scholar
- Davey, B. and Priestley, H. 1990. Introduction to lattices and order. Cambridge University Press.Google Scholar
- Ganter, B. and Wille, R. 1999. Formal Concept Analysis - Mathematical Foundations. Springer Verlag. Google Scholar
- Godin, R. and Mili, H. 1993. Building and maintaining analysis-level class hierarchies using galois lattices. In Proceedings of the Eighth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'93). Washington, DC, 394-410. ACM SIGPLAN Notices 28(10). Google Scholar
- Godin, R., Mili, H., Mineau, G. W., Missaoui, R., Arfi, A., and Chau, T.-T. 1998. Design of class hierarchies based on concept (galois) lattices. Theory and Practice of Object Systems 4, 2, 117-134. Google Scholar
- Hind, M. and Pioli, A. 2000. Which pointer analysis should I use? In Proceedings of the International Symposium on Software testing and Analysis. Portland. to appear. Google Scholar
- Krone, M. and Snelting, G. 1994. On the inference of con guration structures from source code. In Proceedings of the 1994 International Conference on Software Engineering (ICSE'94). Sorrento, Italy, 49-57. Google Scholar
- Lindig, C. 1998. Analyse von Softwarevarianten. Tech. Rep. 98-02, TU Braunschweig, FB Infor-matik.Google Scholar
- Lindig, C. 1999. Algorithmen zur begri sanalyse und ihre anwendung in softwarebibliotheken. Ph.D. thesis, Technische Universitat Braunschweig. in German.Google Scholar
- Lindig, C. and Snelting, G. 1997. Assessing modular structure of legacy code based on mathematical concept analysis. In Proceedings of the 1997 International Conference on Software Engineering (ICSE'97). Boston, MA, 349-359. Google Scholar
- Moore, I. 1996. Automatic inheritance hierarchy restructuring and method refactoring. In Proceedings of the Eleventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'96). San Jose, CA, 235-250. ACM SIGPLAN Notices 31(10). Google Scholar
- Opdyke, W. and Johnson, R. 1993. Creating abstract superclasses by refactoring. In ACM 1993 Computer Science Conference. Google Scholar
- Opdyke, W. F. 1992. Refactoring object-oriented frameworks. Ph.D. thesis, University Of Illinois at Urbana-Champaign. Google Scholar
- Pande, H. D. and Ryder, B. G. 1996. Data- ow-based virtual function resolution. In Proceedings of the Third International Symposium on Static Analysis (SAS'96). 238-254. Springer-Verlag LNCS 1145. Google Scholar
- Pugh, W. and Wonnacot, D. 1998. Constraint-based array dependence analysis. ACM Transactions on Programming Languages and Systems 20, 3 (May), 635-678. Google Scholar
- Rossie, J. G. and Friedman, D. P. 1995. An algebraic semantics of subobjects. In Proceedings of the Tenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'95). Austin, TX, 187-199. ACM SIGPLAN Notices 30(10). Google Scholar
- Rountev, A. and Ryder, B. G. 2000. Practical points-to analysis for programs built with libraries. Tech. Rep. dcs-tr-410, Rutgers University. February.Google Scholar
- Shapiro, M. and Horwitz, S. 1997. Fast and accurate ow-insensitive points-to analysis. In Conference Record of the Twenty-Fourth ACM Symposium on Principles of Programming Languages. Paris, France, 1-14. Google Scholar
- Siff, M. and Reps, T. 1997. Identifying modules via concept analysis. In Proc. International Conference on Software Maintenance. Bari, Italy, 170-179. Google Scholar
- Snelting, G. 1996. Reengineering of con gurations based on mathematical concept analysis. ACM Transactions on Software Engineering and Methodology 5, 2 (April), 146-189. Google Scholar
- Snelting, G. 1998. Concept analysis - a new framework for program understanding. In Proc. ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE). Montreal, Canada, 1-10. ACM SIGPLAN Notices 33(7). Google Scholar
- Snelting, G. and Tip, F. 1998. Reengineering class hierarchies using concept analysis. In Proc. ACM SIGSOFT Symposium on the Foundations of Software Engineering. Orlando, FL, 99-110. Google Scholar
- Steensgaard, B. 1996. Points-to analysis in almost linear time. In Proceedings of the Twenty-Third ACM Symposium on Principles of Programming Languages. St. Petersburg, FL, 32-41. Google Scholar
- Streckenbach, M. and Snelting, G. 2000. Points-to analysis for object-oriented languages. Tech. rep., Universitat Passau, Fakultat fur Informatik. To appear.Google Scholar
- Sweeney, P. F. and Tip, F. 1998. A study of dead data members in C++ applications. In Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation. Montreal, Canada, 324-332. ACM SIGPLAN Notices 33(6). Google Scholar
- Sweeney, P. F. and Tip, F. 2000. Extracting library-based object-oriented applications. In Proceedings of the Eighth International Symposium on the Foundations of Software Engineering (FSE'2000). San Diego, CA. To appear. Google Scholar
- Tip, F., Choi, J.-D., Field, J., and Ramalingam, G. 1996. Slicing class hierarchies in C++. In Proceedings of the Eleventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'96). San Jose, CA, 179-197. ACM SIGPLAN Notices 31(10). Google Scholar
- Tip, F., Laffra, C., Sweeney, P. F., and Streeter, D. 1999. Practical experience with an application extractor for Java. In Proceedings of the Fourteenth Annual Conference on Object-Oriented Programming, Languages, and Applications (OOPSLA'99). Vol. 34. 292-305. Google Scholar
- Tip, F. and Sweeney, P. 1997. Class hierarchy specialization. In Proceedings of the Twelfth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'97). Atlanta, GA, 271-285. ACM SIGPLAN Notices 32(10). Google Scholar
- Tip, F. and Sweeney, P. F. 2000. Class hierarchy specialization. Acta Informatica. to appear. Google Scholar
- Wille, R. 1982. Restructuring lattice theory: an approach based on hierarchies of concepts. Ordered Sets, 445-470.Google Scholar
Index Terms
- Understanding class hierarchies using concept analysis
Recommendations
Reengineering class hierarchies using concept analysis
The design of a class hierarchy may be imperfect. For example, a class C may contain a member m not accessed in any C-instance, an indication that m could be eliminated, or moved into a derived class. Furthermore, different subsets of C's members may be ...
Reengineering class hierarchies using concept analysis
SIGSOFT '98/FSE-6: Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineeringThe design of a class hierarchy may be imperfect. For example, a class C may contain a member m not accessed in any C-instance, an indication that m could be eliminated, or moved into a derived class. Furthermore, different subsets of C's members may be ...
Concept Analysis for Class Cohesion
CSMR '09: Proceedings of the 2009 European Conference on Software Maintenance and ReengineeringA concept lattice based approach for analysis of class cohesion is presented. The approach facilitates rapid identification of less cohesive classes. It also helps identify less cohesive methods, attributes and classes in one go. Further, the approach ...
Comments