Method-Level Code Clone Detection on Transformed Abstract Syntax Trees using Sequence Matching Algorithms

Current research shows that a large fraction of source code in many large-scale applications contains code clones [4]. The existence of code clones can introduce many instabilities within a software application, such as unnecessary duplicates. These instabilities can over-complicate routine maintenance tasks, since a change in one method may lead to changes across many methods. In addition, unnecessary duplicates can potentially induce the spread of bugs and prevent changes from being propagated [6]. Therefore, in order to prevent and treat these instabilities, we must figure out where potential clones occur. A properly annotated abstract syntax tree supplies a great deal of information about the structure of an application’s source code. These trees can be easily transformed into a sequence of substrings. Borrowing a few ideas from biological sequence alignment, similarities between transformed subtrees can be identified. Once identified, an application architect or maintainer can accept (or reject) the similar blocks of code as a (non-)clone. Given the use of subtree transformation, I will present three code clone algorithms in this paper. The research presented serves as a starting point for code clone detection using transformed subtrees and sequence similarity. Thus, my results will justify intuition and open a few doors to future work in the area of code clone detection.