Determining detailed structural correspondence for generalization tasks

ABSTRACT

Generalization tasks are important for continual improvement to the design of an evolving code base, eliminating redundancy where it has accumulated. An important step in generalization is identifying the detailed structural correspondence between two pieces of code being considered for generalization. Unfortunately, tool support for this step is insufficient, leaving the developer to resort to tedious and error-prone manual determination of correspondence. This paper presents an approach for automatically determining correspondences as an early step in a generalization task. The approach is implemented in a proof-of-concept plug-in to the Eclipse integrated development environment. Two small empirical evaluations of the tool have been conducted: a comparison between human attempts to determine detailed correspondences and those of the tool; and, a comparison of the use of the tool to the use of diff/CCFinder in performing generalization tasks.

REFERENCES

• 1: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, Efficient and precise dynamic impact analysis using execute-after sequences, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062534]
• 2: Hamid Abdul Basit , Stan Jarzabek, Detecting higher-level similarity patterns in programs, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 3: Ira D. Baxter , Andrew Yahin , Leonardo Moura , Marcelo Sant'Anna , Lorraine Bier, Clone Detection Using Abstract Syntax Trees, Proceedings of the International Conference on Software Maintenance, p.368, March 16-19, 1998
• 4: Jochen Burghardt, E-generalization using grammars, Artificial Intelligence, v.165 n.1, p.1-35, June 2005 [doi>10.1016/j.artint.2005.01.008]
• 5: Ekwa Duala-Ekoko , Martin P. Robillard, Tracking Code Clones in Evolving Software, Proceedings of the 29th international conference on Software Engineering, p.158-167, May 20-26, 2007 [doi>10.1109/ICSE.2007.90]
• 6: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically discovering likely program invariants to support program evolution, Proceedings of the 21st international conference on Software engineering, p.213-224, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302467]
• 7: M. Fowler. Refactoring: Improving the Design of Existing Code. Addison-Wesley, 2000.
• 8: Michael W. Godfrey , Lijie Zou, Using Origin Analysis to Detect Merging and Splitting of Source Code Entities, IEEE Transactions on Software Engineering, v.31 n.2, p.166-181, February 2005 [doi>10.1109/TSE.2005.28]
• 9: Reid Holmes , Robert J. Walker , Gail C. Murphy, Strathcona example recommendation tool, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 10: J. Huny and M. D. McIlroy. An algorithm for differential file comparison. Technical Report CSTR #41, Bell Telephone Laboratories, 1976.
• 11: Toshihiro Kamiya , Shinji Kusumoto , Katsuro Inoue, CCFinder: a multilinguistic token-based code clone detection system for large scale source code, IEEE Transactions on Software Engineering, v.28 n.7, p.654-670, July 2002 [doi>10.1109/TSE.2002.1019480]
• 12: Miryung Kim , David Notkin, Program element matching for multi-version program analyses, Proceedings of the 2006 international workshop on Mining software repositories, May 22-23, 2006, Shanghai, China [doi>10.1145/1137983.1137999]
• 13: Miryung Kim , David Notkin , Dan Grossman, Automatic Inference of Structural Changes for Matching across Program Versions, Proceedings of the 29th international conference on Software Engineering, p.333-343, May 20-26, 2007 [doi>10.1109/ICSE.2007.20]
• 14: Sunghun Kim , Kai Pan , E. James Whitehead, Jr., When Functions Change Their Names: Automatic Detection of Origin Relationships, Proceedings of the 12th Working Conference on Reverse Engineering, p.143-152, November 07-11, 2005 [doi>10.1109/WCRE.2005.33]
• 15: G. D. Plotkin. A note on inductive generalization. Machine Intelligence, 5:153--163, 1970.
• 16: L. Pottier. Généralisation de termes en théorie equationnelle, cas associatif-commutatif. Technical Report 1056, INRIA, 1989.
• 17: Tobias Sager , Abraham Bernstein , Martin Pinzger , Christoph Kiefer, Detecting similar Java classes using tree algorithms, Proceedings of the 2006 international workshop on Mining software repositories, May 22-23, 2006, Shanghai, China [doi>10.1145/1137983.1138000]
• 18: U. Schmid, U. Sinha, and F. Wysotzki. Program reuse and abstraction by anti-unification. In G. Stumme et al., editors, Professionelles Wissensmanagement-Erfahrungen und Visionen (German Workshop of Case-Based Reasoning), pages 183--185. Shaker, 2001.
• 19: Frank Tip , Adam Kiezun , Dirk Bäumer, Refactoring for generalization using type constraints, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 20: Christopher Walther , Thomas Kolbe, Proving theorems by reuse, Artificial Intelligence, v.116 n.1-2, p.17-66, Jan. 2000 [doi>10.1016/S0004-3702(99)00096-X]
• 21: Zhenchang Xing , Eleni Stroulia, Analyzing the Evolutionary History of the Logical Design of Object-Oriented Software, IEEE Transactions on Software Engineering, v.31 n.10, p.850-868, October 2005 [doi>10.1109/TSE.2005.106]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Object-oriented programming

General Terms:
Algorithms, Languages

Keywords:
anti-unification, correspondence, generalization, similarity, tool support