Towards pattern-based design recovery

ABSTRACT

A method and a corresponding tool is described which assist design recovery and program understanding by recognising instances of design patterns semi-automatically. The approach taken is specifically designed to overcome the existing scalability problems caused by many design and implementation variants of design pattern instances. Our approach is based on a new recognition algorithm which works incrementally rather than trying to analyse a possibly large software system in one pass without any human intervention. The new algorithm exploits domain and context knowledge given by a reverse engineer and by a special underlying data structure, namely a special form of an annotated abstract syntax graph. A comparative and quantitative evaluation of applying the approach to the Java AWT and JGL libraries is also given.

REFERENCES

• 1: {AGG} Technical University of Berlin. AGG, the Attributed Graph Grammar system. Online at http://www.tfs.cs.tu-berlin/agg.
• 2: {AWT} SUN Microsystems. AWT, the SUN Java Abstract Window Toolkit. Online at http://java.sun.com/products/jdk/awt.
• 3: Aniello Cimitile , Anna Rita Fasolino , Paolo Maresca, Reuse Reengineering and Validation via Concept Assignment, Proceedings of the Conference on Software Maintenance, p.216-225, September 01, 1993
• 4: Robert Eckstein , Marc Loy , Dave Wood, Java Swing, O'Reilly & Associates, Inc., Sebastopol, CA, 1998
• 5: Thorsten Fischer , Jörg Niere , Lars Torunski , Albert Zündorf, Story Diagrams: A New Graph Rewrite Language Based on the Unified Modeling Language and Java, Selected papers from the 6th International Workshop on Theory and Application of Graph Transformations, p.296-309, November 16-20, 1998
• 6: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 7: Mehdi T. Harandi , Jim Q. Ning, Knowledge-Based Program Analysis, IEEE Software, v.7 n.1, p.74-81, January 1990 [doi>10.1109/52.43052]
• 8: {JCC} SUN Microsystems. JavaCC, the SUN Java Compiler Compiler. Online at http://www.suntest.com/JavaCC.
• 9: {JGL} ObjectSpace, Inc. JGL, the ObjectSpace (Voyager) Java Generic Library. Online at http://www.objectspace.com/products/voyager/libraries.asp.
• 10: {KNNZ99} H.J. Köhler, U. Nickel, J. Niere, and A. Zündorf. Using UML as a visual programming language. Technical Report tr-ri-99-205, University of Paderborn, Paderborn, Germany, August 1999.
• 11: Hans J. Köhler , Ulrich Nickel , Jörg Niere , Albert Zündorf, Integrating UML diagrams for production control systems, Proceedings of the 22nd international conference on Software engineering, p.241-251, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337207]
• 12: Christian Kramer , Lutz Prechelt, Design Recovery by Automated Search for Structural Design Patterns in Object-Oriented Software, Proceedings of the 3rd Working Conference on Reverse Engineering (WCRE '96), p.208, November 08-10, 1996
• 13: Rudolf K. Keller , Reinhard Schauer , Sébastien Robitaille , Patrick Pagé, Pattern-based reverse-engineering of design components, Proceedings of the 21st international conference on Software engineering, p.226-235, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302622]
• 14: Kurt Mehlhorn, Graph algorithms and NP-completeness, Springer-Verlag New York, Inc., New York, NY, 1984
• 15: {MOTU93} H.A. Müller, M.A. Orgun, S.R. Tilley, and J.S. Uhl. A Reverse Engineering Approach To Subsystem Structure Identification. Journal of Software Maintenance, 5(4):181-204, John Wiley and Sons, Inc., December 1993.
• 16: S. Paul , A. Prakash, A Framework for Source Code Search Using Program Patterns, IEEE Transactions on Software Engineering, v.20 n.6, p.463-475, June 1994 [doi>10.1109/32.295894]
• 17: Alex Quilici, A memory-based approach to recognizing programming plans, Communications of the ACM, v.37 n.5, p.84-93, May 1994 [doi>10.1145/175290.175301]
• 18: Ansgar Radermacher, Support for Design Patterns Through Graph Transformation Tools, Proceedings of the International Workshop on Applications of Graph Transformations with Industrial Relevance, p.111-126, September 01-03, 1999
• 19: {SS00} P. Selonen and T. Systä. Scenario-Based Syntesis of Annotated Class Diagrams in UML. In Proc. of the Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), Minneapolis, Minnesota USA. IEEE Computer Society Press, October 2000.
• 20: Jochen Seemann , Jürgen Wolff von Gudenberg, Pattern-based design recovery of Java software, ACM SIGSOFT Software Engineering Notes, v.23 n.6, p.10-16, Nov. 1998
• 21: Andy Schürr , Andreas J. Winter , Albert Zündorf, Graph Grammar Engineering with PROGRES, Proceedings of the 5th European Software Engineering Conference, p.219-234, September 25-28, 1995
• 22: Paolo Tonella , Giulio Antoniol, Object Oriented Design Pattern Inference, Proceedings of the IEEE International Conference on Software Maintenance, p.230, August 30-September 03, 1999
• 23: Linda M. Wills, Using Attributed Flow Graph Parsing to Recognize Clichés in Programs, Selected papers from the 5th International Workshop on Graph Gramars and Their Application to Computer Science, p.170-184, November 13-18, 1994
• 24: {Zün96} A. Zündorf. Graph Pattern Matching in PROGRES. In Proc. of the 5th International Workshop on Graph-Grammars and their Application to Computer Science, LNCS 1073. Springer Verlag, 1996.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Patterns (e.g., client/server, pipeline, blackboard)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

General Terms:
Algorithms, Design, Performance