Detecting similar Java classes using tree algorithms

ABSTRACT

Similarity analysis of source code is helpful during development to provide, for instance, better support for code reuse. Consider a development environment that analyzes code while typing and that suggests similar code examples or existing implementations from a source code repository. Mining software repositories by means of similarity measures enables and enforces reusing existing code and reduces the developing effort needed by creating a shared knowledge base of code fragments. In information retrieval similarity measures are often used to find documents similar to a given query document. This paper extends this idea to source code repositories. It introduces our approach to detect similar Java classes in software projects using tree similarity algorithms. We show how our approach allows to find similar Java classes based on an evaluation of three tree-based similarity measures in the context of five user-defined test cases as well as a preliminary software evolution analysis of a medium-sized Java project. Initial results of our technique indicate that it (1) is indeed useful to identify similar Java classes, (2)successfully identifies the ex ante and ex post versions of refactored classes, and (3) provides some interesting insights into within-version and between-version dependencies of classes within a Java project.

REFERENCES

• 1: 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
• 2: Refactoring: improving the design of existing code, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: 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
• 4: Reid Holmes , Gail C. Murphy, Using structural context to recommend source code examples, Proceedings of the 27th international conference on Software engineering, p.117-125, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062491]
• 5: Kostas Kontogiannis, Program representation and behavioural matching for localizing similar code fragments, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
• 6: Amir Michail , David Notkin, Assessing software libraries by browsing similar classes, functions and relationships, Proceedings of the 21st international conference on Software engineering, p.463-472, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302678]
• 7: G. Mishne and M. de Rijke. Source Code Retrieval using Conceptual Similarity. 2004.
• 8: Ginger Myles , Christian Collberg, K-gram based software birthmarks, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066753]
• 9: Iulian Neamtiu , Jeffrey S. Foster , Michael Hicks, Understanding source code evolution using abstract syntax tree matching, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 10: Object Technology International, Inc. Eclipse Platform Technical Overview. 2003.
• 11: Martin P. Robillard, Automatic generation of suggestions for program investigation, 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
• 12: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 13: S. Tichelaar. FAMIX Java Language Plug-in 1.0.1999.
• 14: S. Tichelaar, P. Steyaert, and S. Demeyer. FAMIX 2.0: The FAMOOS Information Exchange Model. 1999.
• 15: G. Valiente. Simple and Efficient Tree Pattern Matching. Technical Report LSI-00-72-R, Technical University of Catalonia, Dec.2000.
• 16: Gabriel Valiente, Algorithms on Trees and Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 17: Jason T. L. Wang , Huiyuan Shan , Dennis Shasha , William H. Piel, TreeRank: a similarity measure for nearest neighbor searching in phylogenetic database, Proceedings of the 15th international conference on Scientific and statistical database management, p.171-182, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214978]
• 18: Kaizhong Zhang , Rick Statman , Dennis Shasha, On the editing distance between unordered labeled trees, Information Processing Letters, v.42 n.3, p.133-139, May 25, 1992 [doi>10.1016/0020-0190(92)90136-J ]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
change analysis, software evolution, software repositories, tree similarity measures