2H-06 A Code Clone Detection Technique for Object-Oriented
Programming Languages and Its Empirical Evaluation
Toshihiro Kamiya†, Shinji Kusumoto†, and Katsuro Inoue†‡†Graduate School of Engineering Science, Osaka University‡Graduate School of Information Science, Nara Institute of Science and Technology{kamiya, kusumoto, inoue}@ics.es.osaka-u.ac.jp

1Introduction

A code clone is a code portion in source
files that is identical or similar to another.
Clones are introduced because of various
reasons such as reusing code by‘cut-and-paste’ or intentionally repeating acodeportion
forperformanceenhancement[2]. Clones make the source
files very hard to modify consistently. For
example, assume that a software system has
several clone subsystems created byduplication with slight modific ation. When afault is found in one subsystem, the engineer
has to carefully modify all other subsystems.
For a large and complex system, there aremany engineers who take care of eachsubsystem, and modification becomes very
difficult. Various clone detection tools havebeen
proposedand
implemented[1][2][5][6][7], and a number of algorithms
for finding clones have been used for them,such as line-by-line matching for an
abstracted source program [1], and similarity
detection for metrics values of function
bodies [7].
1.1 Definition of clone and relatedterms
A clone-relation is defined as anequivalence relation (i.e., reflexive, transitive,and symmetric relation) on code portions. Aclone-relation holds between two code
portions if (and only if) they are the same
sequences. For a given clone-relation, a pairof code portions is called clone-pair if theclone-relation holds between the portions.
An equivalence class of clone-relation iscalled clone-class. That is, a clone-class is a
maximal set of code-portions in which aclone-relation holds between any pair ofcode-portions.
For example, suppose a file has thefollowing 12 tokens:
axyzbxyzcxyd
Wegetthefollowing
threeclone-classes:
C1) a x y z b x y z c x y dC2) a x y z b x y z c x y dC3) a x y z b x y z c x y d
Note that sub-portions of code portions ineach clone-class also make clone-classes (e.g.
Each of C3 is a sub-portion of C1). In thispaper, however we are interested only inmaximal portions of clone-classes so only thelatter are discussed.
2

Proposedtechniqueclone-code

detection

Our approach presented in this paper
concerns the following issues in clonedetection.
•Identification of structures
Our pilot experiment has revealed thatcertain types of clones seem difficult to be
rewritten as a shared code even if they arefound as clones. Examples are a code portion
that begins at the middle of a function
definition and ends at the middle of anotherfunction definition, and a code portion that isa part of a table initialization code. For
effective clone analysis, our clone detection
technique automatically identifies andseparates each function definition and eachtable definition code. For comparison, in [1],table initialization values have to be removed
by hand, whereas in [7], only an entire
function definition can become a candidate
for clone.
•Regularization of identifiers
Recent programming languages such as
C++ and Java provide name space and/orgeneric type. As a result, identifiers often
appear with attributive identifiers of namespace and/or template arguments. In order totreat each complex name as an equivalent
simple name, the clone detecting process has
a subprocess to transform complex names
into simple form. If source files arerepresented as a string of tokens, structures insource files (such as sentences or function
definitions) are represented as substrings oftokens, and they can be comparedtoken-by-token
toidentifyclones.
Identifying structures and transforming
names require knowledge of syntax rules ofthe programming languages. Therefore, theimplementation of the clone detecting
technique depends on the input. The detail ofclone detecting process is described inSection 2.1.

Source files
Lexical Analysis
Token Sequence
Transformation

Transformed
Token Sequence

Detection

Mapping fromTransformed
Sequence into
Original

Clones on Transformed
Sequence

Formatting
Clone-pairs

Figure 1. Clone detecting process

2.1 Clone-detecting process
Clone detecting is a process in which theinput is source files and the output isclone-pairs. The entire process of ourtoken-based clone detecting technique isshown in Figure 1. The process consists offour steps:(1)Lexical analysis
Each line of source files is divided into
tokens corresponding to a lexical rule ofthe programming language. The tokens of
all source files are concatenated into asingle token sequence, so that finding
clones in multiple files is performed in thesame way as single file analysis. At thisstep, the white spaces between tokens are
removed from the token sequence, but thespaces are sent to the formatting step toreconstruct the original source files.
(2)Transformation

The token sequence is transformed bysubprocesses (2-1) and (2-2) described
below. At the same time, the mapping
information from the transformed token
sequence into the original token sequences
is stored for the later formatting step.
(2-1)Transformation by the transformation
rules
The token sequence is transformed, i.e.,
tokens are added, removed, or changed
based on the transformation rules. Table 1
shows the transformation rules for Javasource code(For C++ source code, anothertransformation rules are adapted).
(2-2)Parameter replacement
After step 2-1 each identifier related totypes, variables, and constants is replacedwith a special token (this replacement is a
preprocess of the ‘parameterized match’proposed in [1]). This replacement makes
code-portions in which variables arerenamed to be equivalent token sequences.
(3)Detection
From all the substrings on the transformed
token sequence, equivalent pairs aredetected as clone-pairs. Each clone-pair isrepresented as a quadruplet (cp, cl, op, ol),
where cp and op are, respectively, theposition of the first and second portion,and cl and ol are their respective lengths.
(4)Formatting
Each location of clone-pair is converted
into line numbers on the original sourcefiles.
Here, a clone-relation is specified with thetransformation
rulesandtheparameter-replacement described above.
Other clone-relations are derived with asubset of the transformation rules andneglection of the parameter-replacement. In

the experiments described in Section 3, aclone-relation with all the transformation
rules is compared to a clone-relation with asubset of the transformation rules.
2.2 The implementation techniques oftool CCFinder
Tool CCFinder was implemented in C++
and runs under Windows 95/NT 4.0 or later.
CCFinder extracts clone-pairs from C, C++
and Java source files. The tool receives thepaths of source files from the command-line(or text files in which the paths are listed),
and writes the locations of the extracted
clone-pairs to the standard output. The
straightforward clone-detecting algorithm forn tokens with matrix requires the timecomplexity of O(n2 ). A data structure called
Table 1. Transformation rules for Java

#RJ1

RJ2

RJ3

RJ4

Rule
( PackageName '.' )+ ClassName→ ClassName
Here, PackageName is a word thatbegins with a small letter andClassName is a capitalized word.
NDotOrNew NClassName '('→NDotOrNew CalleeID '.'NClassName '('Here, NDotOrNew is a token except'.' or 'new'. NClassName is an
uncapitalized word. CalleeID is atoken for an omitted callee.
'=' '{' InitalizationList, '}'→ '=' '{' UniqueID '}'']' '{' InitalizationList, '}'→ ']' '{' UniqueID '}'
Here, InitalizationList is a sequenceof Name, Number, String, Operators,',', '(', ')', '{', and '}'.
Insert UniqueID at each end of thetop-level definitions and declaration.

0100200300k LOC
5004000100200B300Ak LOC

400500Figure 2. Scatter plot of clones over 20 lines in JDK

suffix-tree is devised to detect clone-pairs
and it requires O(n) time complexity[4].
CCFinder employs a relaxed algorithm ofO(n log n) time using a suffix-tree, which isnotonly easily implemented but also
practically efficient.
As the other optimization for large source
files, CCFinder uses a filtering for tokens:
The clone-detection algorithm distinguishes"header" tokens. A header token is defined as
the token that can be the first token of codeportions of code-pairs. For example, ondetecting clone-pairs in C/C++ source files,tokens, “#”, “{”, and “(” are header tokens
by themselves. Also, the successors of “:”,“; ”, “)”, “}”, and ends-of-line of apreprocessor directive become header tokens.
This filtering reduced the number of tokens
inserted into suffix-tree by factor 3 in either

C/C++ or Java source file, in the experiments
described in Section 4.
3Experiment

The purpose of the experiment was toevaluate our token-based clone-detectingtechnique and the metrics. The target source
files have ‘industrial’ size and are widelyavailable. The person who performed theanalysis did not have preliminary knowledge
about the source files; consequently thefollowing results are obtained purely by theanalysis with the tool and metrics. In all thefollowing experiments, tool CCFinder wasexecuted on a PC with Pentium III 650MHz
and 1GB RAM.
3.1 4.1 Clones in a Java library, JDKJDK 1.2.2 is a commonly used Javalibrary and the source files are publicly

1400
1200
1000
8006004002000

Occurence

PR+1234PR+124

Length of clones (LOC)

100..

95908580757065605550

454035302520

PR+34
Exact MatchFigure 3. Occurences against length of clone-pairs in JDKavailable. Tool CCFinder has been applied toall source files of JDK excluding examples
and demo programs, which are about 500k
lines in total, in 1648 files. It takes about 3
minutes for execution on the PC. Figure 2
shows a scatter plot of the clone-pairs having
at least 20 lines of code (LOC). Both thevertical and horizontal axes represent lines ofsource files. The files are sorted inalphabetical order of the file paths, so files inthe same directory are also located near on
the axis. A clone-pair is shown as a diagonalline segment. Only lines below the main
diagonal are plotted as mentioned in Section
2.1. In Figure 2, each line segment looks likea dot because each clone-pair is small(several decades lines) in comparison to thescale of the axis. Most line segments arelocated near the main diagonal line, and thismeans that most of the clones occur within afile or among source files at the neardirectories.
Crowded clones marked A in the graphcorrespond to 29 files of javax/ swing/plaf/ multi/ *.java. These files arevery similar to each other and some of them
contain an identical class definition except
for their different parent classes. According

to the comments of the source files, a code
generator named AutoMulti creates thefiles. To modify these files, the developer
should obtain the tool (the tool is notincluded in JDK), edit, and apply it correctly.
If the developer does not use the tool, he/she
has to update all the files carefully by hand.
As the example shows, the modific ation ofclones needs extra work. In this case, theseclones are easily rewritten with a shared code
if the programming language would support
generic types.
The longest clone (349 lines) is foundwithin java/ util/ Arrays.java(marked B in Figure 2). Methods named“sort” have 18 variations for signatures(number and types of arguments), and theyuse identical algorithm/routine for sorting.
3.2 Evaluation of transformation rules
for JDK
In Section 2.1, we also proposed thetransformation rules for Java. To evaluate
effectiveness of the transformation rules, wehave applied CCFinder with some of theirtransformation rules disabled. Figure 3shows the histogram of detected clone-pairs
when some of rules are applied. PR+1234

means that the parameter-replacement and allrules (RJ1, RJ2, RJ3, and RJ4) are applied(i.e. original CCFinder). Exact Match meansthat no parameter-replacement or no
transformation is applied. This figure showsthat the longer the clone length is, the smaller
its occurrence becomes. A notic eable peakaround 80 LOC is a set of clone-pairs foundin files generated by AutoMulti, whichcannot be detected by Exact Match by thereason mentioned above. In this experiment,
the clone-pairs found by PR+1234 are much
fewer than with PR+124. This means thatrule RJ3 removes many table initializ ation
codes.
The case PR+1234 extracted 2111
clone-pairs and PR+34 extracted 2093
clone-pairs. There are several clone-pairs thatcan be detected by introducing RJ1 and RJ2.
In the case of Exact Match, only a small
number of clone-pairs are found. The “exact”
clone-pairs are obvious candidates to berewritten as a shared code. However, ourtransformation and parameter replacement
approach finds more subtle clone-pairs sothat the chances to rewrite and reorganize
overall structures of software systems
become higher.
4Conclusion

In this paper, we presented a clone detecting
technique with transformation rules and a
token-based comparison. The technique isimplemented and applied to a library of JDKin the experiment, and successfully extracted
code-clones.
References[1] B. S. Baker, “On finding Duplic ation andNear-Duplication in Large Software
System”, Proc. IEEE WCRE ’95., pp.

86-95 Jul. 1995
[2] I. D. Baxter et. al. “Clone Detection
Using Abstract Syntax Trees”, Proc.
ICSM ’98, pp. 368-377, Bethesda,Maryland, Nov. 1998.
[3] S. Ducasse et. al. “A Language
Independent Approach for Detecting
Duplicated Code”, Proc. IEEE ICSM ’99,
pp. 109-118. Oxford, England. Aug.
1999.
[4] D. Gusfield, Algorithms on Strings,
Trees, and Sequences, pp. 89-180.
Cambridge University Press 1997.
[5] J. H. Johnson, “Identifying Redundancy
in Source Code using Fingerprints”,
Proc. of IBM CAS CON ’93, pp. 171-183,
Toronto, Ontario. Oct. 1993.
[6] B. Laguë et. al “Assessing the Benefitsof Incorporating Function Clone
Detection in a Development Process”,
Proc. IEEE ICSM ’97, pp. 314-321, Bari,Italy. Oct. 1997.
[7] J. Mayland et. al. “Experiment on theAutomatic Detection of Function Clones
in a Software System Using Metrics”,
Proc. IEEE ICSM ’96, pp. 244-253,
Monterey, California, Nov. 1996.