Incremental Clone Detection

Abstract

Finding, understanding and managing software clones - passages of duplicated source code - is of large interest in research and practice. There is an abundance of techniques to detect clones. However, all these techniques are limited to a single revision of a program. When the code changes, the analysis must be run again from scratch even though only small parts may have changed. In this paper, we present an incremental clone detection algorithm, which detects clones based on the results of the previous revision's analysis. Moreover, it creates a mapping between clones of one revision to the next, supplying information about the addition and deletion of clones. Our empirical results demonstrate that the incremental technique requires considerably less time than a non-incremental approach if the changes do not exceed a certain fraction of the source code. An incremental analysis is useful for on-the-fly detection and evolutionary clone analysis. On-the-fly detection may be integrated in an IDE and allows to re-run clone detection immediately when a programmer saves his changes or even while he/she is typing. In evolutionary clone analysis, many revisions of a system need to be analyzed in order to understand how clones evolve.