This article was originally published in a journal published by
Elsevier, and the attached copy is provided by Elsevier for theauthor’s benefit and for the benefit of the author’s institution, for
non-commercial research and educational use including without
limitation use in instruction at your institution, sending it to specificcolleagues that you know, and providing a copy to your institution’s
administrator.
All other uses, reproduction and distribution, including without
limitation commercial reprints, selling or licensing copies or access,or posting on open internet sites, your personal or institution’s
website or repository, are prohibited. For exceptions, permission
may be sought for such use through Elsevier’s permissions site at:
http://www.elsevier.com/locate/permissionusematerial

Information and Software Technology 49 (2007) 985–998
www.elsevier.com/locate/infsof

pyMethod and implementation for investigating code clones
in a software systemco

Yoshiki Higo a,*, Toshihiro Kamiya b, Shinji Kusumoto a, Katsuro Inoue aaDepartment of Software Science, Graduate School of Information Science and Technology, Osaka University,
1-3 Machikaneyama-cho, Toyonaka, Osaka 560-8531, Japanb
National Institute of Advanced Industrial Science and Technology, Information Technology Research Institute,
Akihabara Dai Bldg. 1-18-13 Sotokanda, Chiyoda-ku, Tokyo, 101-0021, Japanal

Received 11 March 2006; received in revised form 10 October 2006; accepted 12 October 2006
Available online 22 November 2006

on

Abstractpe

rs

Maintaining software systems is becoming more diﬃcult as the size and complexity of software increase. One factor that complicatessoftware maintenance is the presence of code clones. A code clone is a code fragment that has identical or similar code fragments to it in
the source code. Code clones are introduced for various reasons such as reusing code by ‘copy and paste’. If modifying a code clone withmany similar code fragments, we must consider whether to modify each of them. Especially for large-scale software, such a process isvery complicated and expensive. In this paper, we propose methods of visualizing and featuring code clones to support their understanding in large-scale software. The methods have been implemented as a tool called Gemini, which has applied to an open source softwaresystem. Application results show the usefulness and capability of our system.
 2006 Elsevier B.V. All rights reserved.
Keywords: Software maintenance; Code clone; Software understanding; Software metrics

r's

1. Introduction

Au

th
o

Software maintenance is a continuous process of changing a software system after the system has been delivered tothe ﬁeld. As the size and complexity of software increase,maintenance tasks become more diﬃcult and burdensome.
For example, Yip and Lam reported that 66% of the cost of
the software life cycle is spent on maintenance phase [23].
A code clone is deﬁned as a code fragment that has identical or similar fragments to it in the source code. The presence of code clone is one factor that complicates software
maintenance. Fowler postulates in [9] that the most frequent cause of refactoring is the presence of code clones.
They are introduced in the source program for such reasons as reusing code by ‘copy-and-paste’. When modifying*

Corresponding author. Tel.: +816 6850 6571; fax: +816 6850 6574.
E-mail addresses: y-higo@ist.osaka-u.ac.jp (Y. Higo), t-kamiya@aist.go.jp (T. Kamiya), kusumoto@ist.osaka-u.ac.jp (S. Kusumoto),
inoue@ist.osaka-u.ac.jp (K. Inoue).
0950-5849/$ - see front matter  2006 Elsevier B.V. All rights reserved.
doi:10.1016/j.infsof.2006.10.005

a code clone with many other similar code fragments that
reside in the system, we must determine whether to modify
each of them. For large-scale software, in particular, such a
process is very complicated and costly. Therefore, a powerful code clone detection tool is essential to eﬀectively maintain software.
So far, much research has been done on the automatic
detection of code clones [3,4,6,8,13,14]. We have also developed a code clone detection tool, CCFinder [11], designed todetect code clones eﬀectively in a large-scale software system used in the industrial world, and it is still being
improved day by day. CCFinder has been applied to dozens
of software systems from which we have found many code
clones. Today CCFinder is used in more than 100 softwareorganizations all over the world, and we have received signiﬁcant feedback from them. Since CCFinder often identiﬁes an enormous amount of code clones, it is necessary
to provide some guidelines for selecting only the importantcode clones from the raw output of the tool.

2. Code Clone

r's

co

pe

A code clone, in general, means a code fragment that has
identical or similar code fragments to it in the source code.
However, there is no single or generic deﬁnition for a code
clone. So far, several methods of code clone detection havebeen proposed, and each has its own deﬁnition of code
clone. Some of these methods are described in Section 5.
In the remaining parts of this paper, we apply the code
clone detection feature of CCFinder as the deﬁnition ofcode clone.
2.2. CCFinder

Au

th
o

In CCFinder [11], a clone relation is deﬁned as an equivalence relation (reﬂexive, transitive, and symmetric relations) on fragments. A fragment, which is a part of asource ﬁle, can be represented using ID, Linestart, Columnstart, Lineend, and Columnend. For fragment f, ID(f ) is
the numeral ID of the source ﬁle where f resided. CCFinder
assigns a unique ID to all target source ﬁles. Linestart(f )(Lineend(f )) is the line number of the start (end) of f, andColumnstart(f) (Columnend(f )) is the column number of thestart (end) of f. In this deﬁnition, some fragments may partially overlap. A clone relation exists between two fragments if and only if the token sequences included in them
are identical1. For a given clone relation, a pair of fragments is called a clone pair if the clone relation holds
between them. An equivalence set of a clone relation iscalled a clone set. That is, a clone set is a maximal set of1

fragments where a clone relation exits between any pairof them.
Fig. 1 illustrates an example of a clone relation. As
shown here, ﬁve fragments have clone relations with otherfragments. Fragment f1 has a clone relation with fragment
f4, and fragments f2, f3, and f5 have clone relations witheach other. In this case,four clone pairs, (f1, f4), (f2, f3),
(f2, f5), (f3, f5), and two clone sets, {f1, f4}, {f2, f3, f5} exist.
CCFinder detects code clones from source programs andreveals the locations of clone pairs in source programs. The
minimum code clone length to be detected is set by users inadvance. The clone detection of CCFinder is a process inwhich source ﬁles are input and clone pairs are output.
The process consists of the following steps. (Fig. 2 shows
how the input source code is treated in each step):rs

2.1. Deﬁnition

Fig. 1. Clone pair and clone set.

al

In this paper, we propose visualization and characterization methods for code clones. By using these methods,
users can see how code clones are distributed in the system
at a glance or obtain the code clones that have the features
they are interested in. Also, based on our previous experience, we determined that there are many uninteresting code
clones in the results of code clone detection. An uninteresting code clone is a code clone deemed insigniﬁcant in thecontext of software maintenance. We propose a ﬁltering
method that skips such code clones and reduces investigation eﬀort. A ﬁltering method makes the visualization andcharacterization methods more eﬀective. A system named
Gemini has been implemented based on the proposed methods. Case study results demonstrate the usefulness andapplicability of Gemini.
In Section 2, we describe a code clone and subsequently
introduce CCFinder, the code clone detection tool. Section
3 describes the proposed methods and the tool, Gemini.
Section 4 illustrates the evaluation of Gemini. Section 5
introduces several other methods related to code clone
visualization and code clone detection. Finally, we conclude our discussion with future works in Section 6.

py

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

on

986

The sequences are the transformed ones as described below.

(1) Lexical analysis: Each line of every source ﬁle isdivided into tokens corresponding to the lexical
rules of the programming language. The tokens of
all source ﬁles are concatenated into a single token
sequence (Fig. 2(b)).
(2) Transformation: The token sequence is transformed,
for example, tokens are added, removed, or changed
based on the transformation rules that aim at theregularization of identiﬁers and the identiﬁcation of
structures (Fig. 2(c)).
(3) Match detection: From all the substrings on thetransformed token sequence, equivalent pairs aredetected as clone pairs (Fig. 2(d)).
(4) Formatting: Each location of detected clone pairs isconverted into line and column numbers on the original source ﬁles (Fig. 2(e)).

3. Visualization and characterization methods of code clone
for comprehension
3.1. Motivation
Since we have delivered CCFinder to more than 100 software organizations, its usefulness in actual software maintenance can be evaluated. We have received signiﬁcant
feedback from these organizations, including that CCFinder
extracts too many code clones. Hence it is necessary to provide guidelines to select important code clones from thetool’s output. Moreover, it is quite diﬃcult for users to

987

Au

th
o

r's

pe

rs

on

al

co

py

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

Fig. 2. Detection process of CCFinder.

investigate code clones only using the output of CCFinder.
Fig. 3 shows an example of the output. In the ﬁgure, eachline between #begin{clone} and #end{clone} identiﬁes a clone pair. For example, the fragment starting at line
73 to 86 in the source ﬁle (0.2) and the fragment starting atline 124 to 137 in the source ﬁle (1.2) contribute to a clone
pair. Depending on the size and nature of the target program, the amount of code clones detected by CCFindersometimes becomes quite huge. For example, in JDK 1.5,
there are approximately 2,500,000 clone pairs (12,000 clone

988

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

Here, we assume that at least two tokens are needed tobe identiﬁed as a code clone. With this assumption, the following three clone sets are detected from the source ﬁles.

pyS1 :{C(F1,1,2),C(F1,4,5),C(F2,4,5),C(F3,4,5)}
S2 :{C(F2,1,2),C(F2,2,3),C(F4,1,2)}S3 :{C(F3,1,3),C(F4,3,5)}co

3.2.1. Filtering out uninteresting code clones
Many uninteresting code clones are included in the
CCFinder detection results. In this paper, an ‘‘uninterestingcode clone’’ is a code clone whose existence information isuseless when using code clone information in softwaredevelopment or maintenance.
We have identiﬁed two types of uninteresting code
clones. The ﬁrst is a language-dependent code clone. Whena speciﬁc programming language is used, a programmer
has to repeatedly write some code fragments that cannot
be merged into code fragments due to language limitations.
A language-dependent code clone consists of such codefragments. The second is an application-dependent code
clone. Some application frameworks sometimes require idiomatic code fragments to the application code to interface
with the frameworks. For example, a code fragment of
database connection is a typical application-dependentcode clone. Application-dependent code clone is a code
clone that consists of such code fragments. Language-dependent code clones are detected from all software systems
written in the same programming language, but not application-dependent code clones, which diﬀer greatly amongsystems. Therefore, it is much more diﬃcult to ﬁlter out
application-dependent code clones than language-dependent ones. The presence of uninteresting code clones does
not negatively inﬂuence software development or maintenance. They are stereotyped code and are very stable.
As the ﬁrst step to ﬁlter out uninteresting code clones,
we propose a method to ﬁlter out language-dependent code
clones. For example, consecutive variable declarations,consecutive method invocations, and case entries of switch
statements, which become code clones due to the structureof the programming language, are typical language-dependent code clones.
Fig. 4 is an example of a language-dependent code
clone. The highlighted parts are a clone pair between ﬁlesA and B. Each code fragment of the clone pair is an implementation of consecutive method invocations. The variable
and method names in the code fragments are diﬀerent. As
described in Section 2.2, CCFinder transforms user-deﬁned
names into the same special token. This transform detects
the same logic code with diﬀerent names; for example, after
copy and paste some variable names are changed. Unfortunately, CCFinder also detects many language-dependentcode clones such as Fig. 4.
We focused on a repetition structure within a code clone
because a language-dependent code clone has repetitive
implementations of the same logics. We propose to ﬁlter

on

pe

rs

sets) whose fragment length is more than 30 tokens. It istrue that CCFinder enables users to obtain code clones
quickly from such large-scale software, but it is unrealistic
to check all of the detected code clones by hand to determine useful information. A simple browsing tool, whichdisplays the source code of clone pairs one by one, is not
helpful for large-scale software.

alFig. 3. Example of output from CCFinder.

3.2. Proposal techniques

Au

th
o

r's

From many our previous experiences with CCFinder, weobserved that CCFinder detects many uninteresting code
clones. As such, a ﬁltering method is proposed to counteract this problem. To realize an eﬀective code clone analysis
for large software products, we need some kind of bird’s
eye view of code clones to grasp the amount of code clones
in the system, especially in the initial phase of analysis.
Also, we provide an appropriate characterization of entities (code clones, target source ﬁles, and functionalities)
that enables users to select arbitrary entities based on theirfeatures.
In this section, we explain our methods with an example
to give a complete picture of them. Here, we assume that
we detect code clones from four source ﬁles (F1, F2, F3,
F4) located in two directories (D1, D2). Each source ﬁle consists of the following ﬁve tokens (the meaning of superscript * will be described in Section 3.2.1).
F1: a b c a b,
F2: c c* c* a b,
F3: d e f a b,
F4: c c* d e f

Also, we use label C(Fi,j,k) to represent a fragment.
Fragment C(Fi,j,k) starts at the jth token and ends at thekth token in source ﬁle Fi (j must be less than k).

i¼1

r's

0þ0þ0þ0 8¼ ¼ 1:0RNRðS 1 Þ ¼ 1 
2þ2þ2þ2 81þ2þ1 2RNRðS 2 Þ ¼ 1 ¼ ¼ 0:3_2þ2þ2 60þ0 6RNRðS 3 Þ ¼ 1 ¼ ¼ 1:0
3þ3 6

al

pe

rs

We deﬁned repeated code sequence as repetitions of its adjacent code sequence and non-repeated code sequence as theother parts. In the example, three tokens are considered
repeated code sequences, and the superscript * indicates thatits token is in a repeated code sequence.
In this case,onout such code clones with a metric called RNR(S) that
represents the ratio of non-repeated code sequence in clone
set S.
Here, we assume that clone set S includes n fragments,
f1,f2,   , fn. LOSwhole(fi) represents the Length Of whole
Sequence of fragment fi, and LOSrepeated(fi ) represents theLength Of repeated Sequence of fragment fi, then,nP
LOS repeated ðfi Þi¼1RNRðSÞ ¼ 1  P
n
LOS whole ðfi Þ

coFig. 4. Example of language-dependent code clone.

989

py

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

thoThis metric enables users to identify clone sets such as consecutive variable declarations or consecutive accessor declarations in Java or repeated printf, scanf, andswitch statements clones in C language. From our experience, clone sets whose RNR values are less than ‘0.5’ aredeemed uninteresting.

Au

3.2.2. Scatter Plot of code clone
We utilized and enhanced Scatter Plot [2,8,15] for abird’s eye view visualization method of code clones.
Fig. 5 shows the Scatter Plot of the example explained previously. Both the vertical and horizontal axes represent
tokens of source ﬁles that are sorted alphabetically by ﬁlepath, so the source ﬁles in the same directory are close toeach other. A clone pair is shown as a diagonal line segment, assuming that a cloned fragment has at least two
tokens. Each dot on diagonal line segments means the corresponding tokens on the horizontal and vertical axes are
identical. The dots are spread symmetrically with a diagonal line from the upper left corner to the bottom right.

Fig. 5. Example of Scatter Plot.

Using Scatter Plot, the distribution state of code clones
can be grasped at a glance. Also, our Scatter Plot shows ﬁltering results with metric RNR. Each blue dot represents anelement judged an uninteresting code clone. By using theﬁltering results, users can avoid spending too much timeon uninteresting code clones, which means code clone analysis can be done more eﬀectively by using Scatter Plot.
The directory (a package in the case of Java) separators
are drawn as a solid lines, to distinguish them from ﬁle separators shown as dotted lines. Users can recognize theboundaries of directories and understand which directories(packages) contain many code clones and which directories
shares many code clones with other directories.
3.2.3. Clone set metrics
Here, we elaborate how to quantitatively characterize
code clones and how to visualize them. We deﬁned the following metrics to characterize code clones.
• LEN(S): LEN(S) is the average length of sequences (sizeof fragments) in clone set S. In the example, the valuesof LEN(S1), LEN(S2), and LEN(S3) are 2, 2, and 3,
respectively. Using metric LEN, the fragment size ofclone set S3 is greater than the ones of clone sets S1and S2.

990

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998• POP(S): POP(S) is the number of S fragments. A highPOP(S) value means that S fragments appear in many
places in the system. In the example, the values ofPOP(S1), POP(S2), and POP(S3) are 4, 3, and 2, respectively. Using metric POP, the number of occurrences ofclone sets S1 is larger than S2 and S3.
• NIF(S): NIF(S) is the number of source ﬁles that include
any S fragments. A high NIF(S) value may indicate abadly designed software system, the absence of abstraction for S fragments, or spread code fragments of acrosscutting concern. In the example, the values of
NIF(S1), NIF(S2), and NIF(S3) are 3, 2, and 2, respectively. Using metric NIF, clone set S1 involves more
source ﬁles than S2 and S3.
• RNR(S): RNR(S) is described in Section 3.2.1. As
mentioned there, using metric RNR, we can see whether
each clone set is practical or uninteresting. From ourexperience, ‘0.5’ is deemed appropriate as a thresholdvalue of RNR. In the example, clone set S2 is judged
uninteresting.

on

al

co

py

• NOCth(F): NOCth(F) is the number of fragments of any
clone sets in source ﬁle F whose RNR values are equal toor greater than threshold th. In the example, the valuesof NOC0.5(F1) and NOC0.5(F3) are 2, and those of
NOC0.5(F2) and NOC0.5(F4) are 1. Here, by using metric
NOC, source ﬁles F1 and F3 have more duplicated fragments than source ﬁles F2 and F4.
• ROCth(F): ROCth(F) is the ratio of the duplication of F.
In the example, the values of NOC0.5(F1), NOC0.5(F2),NOC0.5(F3), and NOC0.5(F4) are 0.8, 0.4, 1.0 and 0.6,
respectively. Here, by using metric ROC, source ﬁle F3
is completely duplicated.
• NOFth(F): NOFth(F) is the number of source ﬁles thatshare any code clones with F. In the example, the valuesof NOF0.5(F1), NOF0.5(F2), NOF0.5(F3), and NOF0.5(F4)are 2, 2, 3, and 1 respectively. Here, by using metric
NOF, source ﬁle F3 shares code clones with all the othersource ﬁles.

3.3. Code clone visualization tool: Gemini

th
o

r's

pe

rs

Using these simple metrics, we can see which clone setsare discriminative in various aspects.
We propose a visualization/selection method using a
Metric Graph for characterized code clones. Here, we
explain Metric Graph using Fig. 6. In Metric Graph, each
metric has a parallel coordinate axis. Users can specify
the upper and lower limits of each metric. The hatchingpart shows the range bounded by their upper and lower
limits. A polygonal line is drawn per clone set. In this ﬁgure, three lines of clone sets S1, S2, and S3 are drawn. In
the left graph (Fig. 6(a)), all metric values of all clone sets
are in the hatching part. As such, all clone sets are in theselected state. In the right graph (Fig. 6(b)), the values ofLEN(S1) and LEN(S2) are smaller than the under limit of
LEN, which places S1 and S2 in an unselected state. Thismeans that we can get ‘‘long’’ code clones by changing
the lower limit of LEN. Thus Metric Graph enables users
to choose arbitrary clone sets based on metric values.

have thresholds of th or greater for calculation. Here, we
use ‘0.5’ as the threshold. These metrics are used for the ﬁltering of source ﬁles, which will be described below in Section 3.3.

3.2.4. File metrics
We also deﬁned the following metrics to characterize
source ﬁles. All metrics only use clone sets whose RNR
b

Au

a

Fig. 6. Filtering clone sets using the Metric Graph.

We implemented a code clone visualization tool named
Gemini based on the proposed visualization and characterization strategies. Gemini supports all programming languages that CCFinder can handle and provides thefollowing views as implementations of the code clone visualization mechanism and code clone/source ﬁle selection
mechanisms.
• Scatter Plot
• Metric Graph• File List

As described in Section 3.2.2, by using Scatter Plot,users can understand the distribution state of code clones
at a glance, which is very useful, especially in the early stageof analysis.
Metric Graph is designed to enable users to quantitatively
select clone sets. In Scatter Plot, the degree to which clone
sets are distinguished depends on their positions. For example, suppose clone set Sexample has 100 fragments. If all fragments of Sexample are in the same source ﬁle, they will be
distinguished because the positions of each line segment
are close to each other. But if they are in diﬀerent source
ﬁles, their line segments are scattered, and so they cannot
be distinguished. On the other hand, in Metric Graph,the ‘100 fragments’ feature is represented as metric
POP(Sexample), and users can select Sexample regardless of
their positions.
File List is used to select source ﬁles. File List exhibits all
source ﬁles of the system with quantitative information, theﬁle metrics described in Section 3.2.4 and two size metrics.

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

991

study, we set 0.5 as the threshold of metric RNR. If
RNR(S) is less than 0.5, more than half of the tokens inclone set S are in repeated token sequences. The detailsof the ﬁltering results are written in Section 4.2
4.2. Filtering with RNR

copy

We browsed through the source code of all code clones
judged uninteresting by using RNR. Table 1 shows thebreakdown of clone sets whose RNR are less than 0.5.
The number of such clone sets is 1073, and all of them
are the consecution of simple implementations. As
described in Section 2.2, CCFinder detects code clones after
translating all user-deﬁned names into the same special
token, and so each code fragment included in the sameclone set is an implementation of diﬀerent contents, as inFig. 4.
Many consecutive accessor declarations are coincidentally found as code clones; however, the user-deﬁned namesin them are diﬀerent. We identify them as code clones
because both the accessor and ﬁeld names are transformed
into the same token before detection.
Consecutive simple method declarations are coincidentally found as code clones just as in the case of consecutive
accessor declarations. Fig. 8(a) shows one such code clones
that implements simple instructions, but not accessors.
Consecutive method invocations are detected as code
clones. Fig. 8(b) shows one such code clone. It is pointless
to display it to users in code clone analysis because they can
do nothing about it.
Consecutive if and if-else statements are detected as code
clones. Fig. 8(c) shows one such code clone. These code
clones implement veriﬁcations of variable states. Since
these code clones are obviously harmless, it is pointless toshow them in code clone analysis.
Consecutive case entries are coincidentally found ascode clones, as in the case of consecutive accessor declarations. Fig. 8(d) shows one such code clone. The programmer usually implements simple instructions in caseentries. Moreover, CCFinder replaces all user-deﬁned
names into the same special token. Thus consecutive caseentries tend to be detected as code clones, but they areharmless.

4. Case study

th
o

r's

on

pe

rs

Users can sort all source ﬁles based on any metrics. Fig. 7
shows a snapshot of File List. In the ﬁgure, the two size
metrics, LOC(F ) and TOC(F ), represent the number oflines and tokens in source ﬁle F respectively. For metrics
NOC, ROC, and NOF, two values are shown. The values
outside parentheses are the metrics on threshold th, andthose in parentheses are the metrics on threshold 0, whichmeans that all code clones are counted. File List is very useful when users want to select source ﬁles based on quantitative information. We did not apply a quantitative ﬁleselection mechanism using Metric Graph for File List
because it is more useful to use not only quantitative metrics but also their paths or names. As described in Section
3.2.3, Metric Graph is suitable for selections based on
numeric values, but not for strings such as ﬁle paths ornames. This explains why we use File List not Metric Graph.
Also, File List has a function that sorts source ﬁles inascending or descending order of their metrics or in alphabetical order of their ﬁle names.

alFig. 7. Snapshot of the File List.

Au

4.1. Target and conﬁgurations

We chose Ant [1](version 1.6.0) as the target. Ant 1.6.0
includes 627 source ﬁles, and its size is approximately
180,000 LOC. In this case study, we set 30 tokens as theminimum token length of a code clone (intuitively, 30
tokens correspond to about 5 LOC). The value ‘30’ comesfrom our previous studies of CCFinder [11].
It took less than a minute to detect code clones with
CCFinder. As the results of code clone detection, we found2406 clone sets and 190,004 clone pairs. The results showthat it is unrealistic to check all detected code clones dueto the enormous amount, and it is also very important toselect discriminative code clones or source ﬁles. In thisTable 1
Breakdown of uninteresting code clones
Kinds of code clones

Number of clone sets

Consecutive accessor declarations
Consecutive simple method declarations
Consecutive method invocations
Consecutive if or if-else statements
Consecutive case entries
Consecutive variable declarations
Consecutive assign statements
Consecutive catch statements
Consecutive while statements

428
224
177
160
30
29
19
4
2

Total

1073

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

th
o

r's

pe

rs

on

al

co

py

992

Fig. 8. Examples of uninteresting code clones.

Au

Consecutive variable declarations and assign statements
are coincidentally found as code clones, as in the case ofconsecutive accessor declarations. Figs. 8(e) and (f) show
one such code clones. These coincidences reﬂect the detection algorithm of CCFinder, and they should not be detected as code clones.
Consecutive catch statements are detected as duplicatedfragments. Fig. 8(g) shows one such code clone. Their existence reﬂects the speciﬁcations of Java and should not be
detected as code clones.
Consecutive while statements are detected as duplicatedfragments. Fig. 8(h) shows one such code clone. In thiscase, the logics of each while statement are very simple,

and it is no problem to ﬁlter out them. But if their logics
are complex, they should not be ﬁltered out.
We were able to ﬁlter out 44% (1073 of 2403) of theclone sets by using RNR. All of the clone sets ﬁltered out
were either coincidental ones, inevitable duplications byJava speciﬁcations, or consecutive simple instructions.
4.3. Scatter Plot analysis
Fig. 9 shows snapshots of Ant’s Scatter Plot. In Fig. 9,
clone sets whose RNR are less than 0.5 are drawn in blue,
and the others are drawn in black. Each vertical or horizontal line is the border between ﬁles or directories. In

993

r's

pe

rs

on

al

co

py

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

Fig. 9. Snapshots of Scatter Plot.

Au

th
o

Fig. 9(a), all such lines are omitted because there are toomany. We can see the distribution state of code clones overthe system by using Scatter Plot at a glance. The distinct
parts in Scatter Plot are the parts where there are manycode clones in the system. Discovering whether the duplication of such parts in the system is the expected is one significant use of code clone information. We investigated whatkinds of implementations were conducted in the distinct
parts of the Scatter Plot. Fig. 9(a) is the entire Scatter Plot.
The following describes ‘‘A,’’ ‘‘B,’’ and ‘‘C,’’ the three different parts marked in Fig. 9(a).
Fig. 9(b) represents part ‘‘A’’ in Fig. 9(a). Here are thesource ﬁles under directory ant/ﬁlters/. These source ﬁles
implement classes that return a java.io.Reader object
under such various conditions as the following.
• ConcatFilter.java: Concatenate a ﬁle before and/or after
the ﬁle.

• HeadFilter.java: Read the ﬁrst n-lines of a stream.
• LineContains.java: Filter out all lines that don’t include
all the user-speciﬁed strings.
• PreﬁxLines.java: Attach a preﬁx to every line.
These source ﬁles share the following functionalities.
1. Reads a character from a speciﬁed stream. If it hasreached the end of stream, then some operations are
performed.
2. Creates a new Reader object and returns it.
The details of each functionality in these source ﬁleswere diﬀerent, but the processing ﬂows were duplicated.
Fig. 9(c) represents part ‘‘B’’ in Fig. 9(a). It shows thatsource ﬁle ant/taskdefs/optional/ide/VAJAntToolGUI.java
contains many code clones. This source ﬁle implements a
simple GUI for providing build information to Ant or994

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

pyFig. 10. Example of code clones in ‘‘B’’ (branching using source of
events).

coFig. 12. One fragment comprising a clone set whose POP is highest.

al

31 fragments, and all were in source ﬁle VAJAntTool.java
described in Section 4.3. Each fragment begins with theend of a method and ends with the beginning of its next
method. This means the center parts of each method diﬀer
from each other.

rsbrowsing build processes. Most of these code clones wereclassiﬁed into either of the following two types.

4.4.2. Clone sets whose LEN are high
The two source ﬁles WebLogicDeployment.java and
WebSphereDeployment.java, from directory ant/taskdefs/
optional/ejb/, shared the longest code clones. The fragment
size of the clone set was 282 tokens (77 lines). Both source
ﬁles implement tasks working with WebLogic [21] andWebShpere [22], which are well-known application servers.
Each source ﬁle has a method named isRebuildRequired,and both duplicated codes are in the methods. Some variable names diﬀer between the methods, but other properties (indents, blank lines, comments) are completely
identical, which indicates that those code clones were madeby ‘copy and paste’.

onFig. 11. Example of code clones in ‘‘B’’ (method’s creating GUI widgets).

pe• If statements that determine process ﬂow depending on
the source of events. Fig. 10 shows one of them.
• Method declarations that create GUI widgets. Fig. 11
shows one of them.

th
o

r's

These code clones are typical GUI processes.
Fig. 9(d) shows a closer view of part ‘‘C’’ in Fig. 9(a). It
corresponds to the source ﬁles under directory ant/taskdef/
optional/clearcase/. These source ﬁles implement several
tasks working with ClearCase [7], a famous version control
systems. Each command (for example, Checkin, Checkout,
Update. . .) of ClearCase is implemented as a class. Thesesource ﬁles were created by entire ﬁle copy, rather thancopy and paste of particular parts of the text.
4.4. Metric Graph analysis

Au

We investigated what kind of code clones is quantitatively discriminative by using Metric Graph. The following
types of code clones are investigated. Before performing
this analysis, we raised the lower limit of RNR to ﬁlter
out clone sets whose RNR are less than 0.5.
• Clone sets whose POP are high.
• Clone sets whose LEN are high.
• Clone sets whose NIF are high.

4.4.1. Clone sets whose POP are highFig. 12 is one of the fragments comprising the clone set
that has more fragments than any other. The clone set had

4.4.3. Clone sets whose NIF are high
The clone set that involved the most source ﬁles was
implementations of consecutive accessor declarations,which appeared in 19 ﬁles (22 places). The accessor’s names
diﬀered from each other, but CCFinder ignores diﬀerencesof user-deﬁned names2 when detecting code clones. Since
there are both setters and getters in the fragments of clone
sets, the fragments are not simple consecutive code. The
RNR value of the clone set was 85.
4.5. File List analysis
We investigated what kind of source ﬁles is discriminative by using File List. The following types of source ﬁleswere investigated. In this analysis, we targeted only clone
sets whose RNR are 0.5 or more.
• Files whose ROC are high.
• Files whose NOC are high.
• Files whose NOF are high.
2
Naturally, it is possible to make CCFinder recognize diﬀerences of userdeﬁned names.

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

995

source ﬁle had 378 code clones, which was overwhelmingly
more than any others.

Table 2
Duplicated ratios of ﬁlesPercentage

0–10%
11–20%
21–30%
31–40%
41–50%
51–60%
61–70%
71–80%
81–90%
91–100%

207
75
64
61
53
53
33
22
22
37

33%
12%
10%
10%
8%
8%
5%
4%
4%
6%

Total

627

100%

4.5.3. Files whose NOF are highThe source ﬁle with the highest NOF0.5 value was ant/
taskdefs/optional/jsp/JspC.java, and most of the code
clones in the source ﬁle were implementations of consecutive accessor declarations. These fragments are identicalto those described in Section 4.4.3. Not only this source ﬁlebut most such source ﬁles have many code clones of consecutive accessor declarations.

py# Files

4.6. Evaluation

4.5.1. Files whose ROC are highTable 2 represents the duplicated ratio distribution ofsource ﬁles. As seen in this table, Ant has many source ﬁleswith high duplicated ratios. Hence, we describe not only
the highest duplicated ratio source ﬁle, but also the top
10 ﬁles. In the following items, the numbers in parentheses
are the ROC0.5 values.

onal4.6.1. Filtering with RNR
We examined how the RNR ﬁltering worked well. We
browsed through the source code of all detected code
clones so as to calculate precision, recall and f-value ofthe ﬁltering. 869 of 2406 were practical clone sets and1537 were uninteresting ones. The deﬁnitions of the values
are the followings.
recallð%Þ ¼ 100


Au

th
o

r's

pe

rs

• FlatFileNameMapper.java (1.0): Returns the ﬁle nameincluded in a speciﬁed java.lang.String.
• IdentityMapper.java (1.0): This source ﬁle is a duplication of FlatFileNameMapper.java. Only the class nameis diﬀerent.
• DirSet.java (1.0): Treats a set of directories. This source
ﬁle is a complete duplication of FileSet.java.
• FileSet.java (1.0): Treats a set of source ﬁles. This
source ﬁle is a complete duplication of DirSet.java.
• CCMkbl.java (0.98): Implements a task working with
ClearCase. This source ﬁle is duplicated with several
source ﬁles implementing other ClearCase’s tasks.
• SOSCheckin.java (0.97): Implements a task working
with SourceOﬀSite [16]. This source ﬁle is duplicatedwith several source ﬁles implementing other SourceOﬀSite’s tasks.
• StringLineComments.java (0.97): This source ﬁle is oneof the ﬁle ﬁlters described in Section 4.3 part ‘‘A.’’ It
shares code clones with other ﬁlters.
• FieldRefCPInfo.java (0.96): Stores information of aﬁeld (for example, ﬁeld name, type, owner class, . . .).
This
sourceﬁleisaduplicationofInterfaceMethodRefCPInfo.java.
• InterfaceMethodRefCPInfo.java (0.96): Stores information of a method (for example, method name, signature,
owner class, . . .). This source ﬁle is a duplication of
FieldRefCPInfo.java.
• MSVSSCREATE.java (0.96): Implements a task working with Visual SourceSafe [19]. This source ﬁle is duplicated with several source ﬁles implementing other Visual
SourceSafe’s tasks.

4.5.2. Files whose NOC are highThe source ﬁle with the highest NOC0.5 value was VAJAntToolGUI.java described in Section 4.3 part ‘‘B’’. Thisco

Range of Duplicated Ratio(ROC0.5)# real uninteresting clone sets filtered out by RNR# clone sets filtered out by RNR

precisionð%Þ ¼ 100 f  value ¼# clone sets filtered out by RNR# all real uninteresting clone sets

2  recall  precision
recall þ precision

Fig. 13 illustrates transitions of recall, precision, and f-value when the RNR threshold is between 0 and 1.0. As mentioned above, in this case study, we used 0.5 as thethreshold. Under this condition, recall was 100(%), whichmeans that no practical clone set was accidentally ﬁlteredout at all. Also, precision was 65(%), which indicates thatabout one third real uninteresting clone sets were not ﬁltered out. Using 0.5 as the threshold raised precision from36(%) to 65(%). Therefore, we can conclude that most partof uninteresting clone clones were ﬁltered out with no false
positive by using 0.5 as the threshold.
It might be useful to set the threshold as to make f-value
the greatest. In this case study, f-value reached its greatest
when the threshold was 0.7. Under this condition, recall
was 95(%) and precision was 82(%). In other words, one
twentieth clone sets ﬁltered out were practical ones andfour ﬁfths of real uninteresting clone sets were ﬁlteredout. However, we consider that accidentally ﬁltering out
practical code clones should be avoided because ﬁlteredclone sets might play an important role in software development and maintenance. Hence, it deems to be better touse 0.5 as the threshold than 0.7.
4.6.2. Using Gemini in other contexts
In this section, we will discuss the external validity of thecase study. The discussion points are the followings.

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

Table 3Size of target software systems and results of executions
CCFinder# Files

LOC

Run time

627
6555

180,844
1,883,928

55 s
594 s

GeminiMem usage

Init time

Mem usage

30 MBytes
194 MBytes

4s
15 s

46 MBytes
137 MBytes

rs

Ant
JDK1.5Size

onTarget NamealFig. 13. Transition of recall, precision, and f-value.

co

py

996

pe

• Performance and scalability of Gemini.
• General versatility of the code clone analysis method
described in this case study.
• Required users’ skills to perform code clone analysis.

Au

th
o

r's

First discussion point is the performance and scalabilityof Gemini. We applied CCFinder and Gemini to a largescale software system, JDK 1.5 besides Ant for investigatingthese properties. We used a PC-based workstation3 to perform the tools. Table 3 illustrates the sizes of the target
software systems and the results of executions. Note that
total time of CCFinder’s running and Gemini’s initializationis only 10 min despites the huge size of JDK 1.5. Additionally, the memory usage of both CCFinder and Gemini isquite reasonable. Therefore, we can conclude that the performance and scalability of these tools are enough to be
used in real software development and maintenance. Users
can eﬃciently perform code clone analysis of a large-scale
software system with an ordinary PC.
Second, we will discuss the general versatility of the code
clone analysis method described in this case study. We havealready analyzed many other open source and industrial
software systems, and the analysis methods for them arealmost the same as the one described in this case study. This
analysis method can be applied to various software systems
independently of their sizes, development patterns, andtheir domains. From many experiences of code clone analyses, we have learnt that ‘30’ is an appropriate value of the3

CPU: PentiumIV 3.0 GHz, Memory Size: 2.0GBytes, OS:
WindowsXP.

minimum code clone size that CCFinder detects. But infrequently under this condition, especially in the case oflarge-scale software, too many code clones are detected,
and we cannot eﬃciently analyze code clones. In such cases,
users should change the minimum code clone size to ‘50’ or‘100’ and re-run CCFinder for eﬃcient analysis. Also, it
became clear that industrial software tends to include morecode clones than open source software. If users are going todetect and analyze code clones in a large-scale industrial
software system, they should use ‘100’ as the minimum code
clone size in the ﬁrst running of CCFinder.
Finally, we will discuss required users’ skills to perform
code clone analysis. In the code clone analysis with Gemini,
they have to browse through that the source code of code
clones and understand the implementations. Hence, theymust be familiar with the programming language of the target software. And if the target software was developed by 2
or more people, the higher skill of reading source code isrequired. But they do not need to know the detail information of the target software; actually we do not have deep
knowledge of Ant. If users had such information, they
could perform deeper analysis. If users want to do the samekind of analysis as the one described in this case study, they
do not need to have such information.

5. Related works and discussion
Kapser et al. implemented a visualization tool called
CLICS to comprehend cloning [12]. CLICS shows the structures in the source ﬁles and the system architecture with

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

on

al

co

py

with each other or fragments included in the same cloneset (in his paper, Hash is used instead of clone set). We
agree that hyperlink properties oﬀer convenient navigation
for users, but there is no functionality to see the state of thesystem’s code clones.
As described in Section 2.1, several code clone detection
methods have been proposed. A code clone detection tool
Dup [3] uses a sequence of lines to represent source codeand detects clones line-by-line. A language independent
clone detection tool duploc [8] reads source ﬁles, makes asequence of lines, removes white spaces and comments inlines, and detects matches by string-based Dynamic Pattern
Matching (DPM). Baxter et al. [6] proposed a technique toextract clone pairs of statements, declarations, or theirsequences from C source ﬁles. The tool parses source code
to build an abstract syntax tree and compares its subtrees
by characterization metrics. Komondoor et al. [13] proposed a method using program slicing in which a program
dependence graph is constructed by analyzing target sourcecode. Identical or similar parts are detected as code clones.
A clone-detecting method proposed by Mayrand et al. uses
a representation called Intermediate Representation Language (IRL) to characterize each function in the sourcecode [14]. A clone detection tool, Similar Method Classiﬁer(SMC) [4], uses a hybrid approach of characterization metrics and dynamic pattern matching (DPM).
Basit et al. suggested a method detecting structuralclones [5]. A structural clone is a pattern of cloned codefragments, and it indicates the presence of design-level similarities. They also implemented a tool detecting suchclones based on the ‘‘market basket analysis’’ techniqueof the Data Mining domain. Providing structural clone
information is a great support of program comprehension,
but how the information is expressed is a big challenge.
Walenstein et al. reported that the judgment of code
clones varies among experts [20]. In one of their experiments, three experts disagreed whether the fragments arereally code clone or not for more than 60% of automaticallydetected clones. Our metric system does not settle the controversy, but it helps users choose what kind of codesshould be regarded as code clones.

pe

rs

code clone information, which makes it possible for users
to easily get the information of code clones they are interested in. Also, CLICS is facilitated with a query support feature to display code clones that satisfy the conditions ofqueries. CLICS does not implements Scatter Plot due to
its limited scalability.
We believe that our enhanced Scatter Plot is scalable anduseful for understanding the state of the code clones of asoftware system. In our case study, Scatter Plot worked
smoothly on the source code of JDK 1.5, whose size was
1.8 million LOC, including 2,497,433 clone pairs in 12,522
clone sets, under LEN P 30 conditions. Our Scatter Plot
displays the results from which the uninteresting code clones
were already ﬁltered out, which diﬀerentiates it from previous works [2,8,15]. This enhancement reﬂects our previous
experiences, where we applied Scatter Plot to large softwaresystems and found an enormous amount of such code
clones. Kapser et al. share our opinion [12], and their tool,
CLICS has implemented ﬁltering features. Also, in Scatter
Plot, the directory (package) separators are shown diﬀerently from the ﬁle ones, which makes it possible for users to discover the boundaries of directories and then ﬁnds out thedirectories (packages) that contain many code clones anddirectories that share many code clones with other directories. Users can withness the state of the practical code clones
in the package hierarchy of a software system by using our
Scatter Plot since uninteresting code clones are ﬁltered out.
Kapser et al. also describe functionalities to support
navigation and understanding cloning in a software system[12]. The functionalities are as below.

997

r's

(1) Facilities to evaluate overall cloning activity.
(2) Mechanisms to guide users toward clones that will bemost eﬀectively used in their task.
(3) Methods for ﬁltering and reﬁning the analysis of theclones.

Au

thoHere, we consider these functionalities in the context ofour tool, Gemini. Since Scatter Plot provides a bird’s eye
view, it accomplishes the ﬁrst functionality. We believe that
Metric Graph and File List implement the second functionality because we can use them to easily get arbitrary clone
sets based on their quantitative features. The third functionality is realized through the ﬁltering metric RNR thatenables users to ﬁlter out uninteresting code clones. With
all the above characteristics, Gemini is deﬁnitely useful
and appropriate as a code clone visualization tool.
Rieger et al. suggested and implemented diagrams tovisualize code clone information [15]. Their diagrams are
based on the principle of Polymetric View and provide
abstracted code clone information on various granularities
for users. They also argue that in the large-scale software,
since too many code clones are detected, ﬁltering functionalities are essential.
Johnson suggested a navigation method using HTML[10]. The hyperlink functionality of HTML enables users
to jump freely between source ﬁles having clone relations

6. Conclusion
We proposed visualization and characterization methods of code clones in a software system and implemented
them as a tool, Gemini. Gemini provides valuable mechanisms that perform the following functions describe below.
• Filters out uninteresting code clones.
• Views the states of code clones over a system.
• Navigates code clones that have feature users are interested in.
As described in Section 4, our proposed methods
worked well and we could determine various cloning activities in Ant.

998

Y. Higo et al. / Information and Software Technology 49 (2007) 985–998

co

al

rs

We thank Yasushi Ueda of the Japan Aerospace Exploration Agency for his contributions to a previous paper
[17].

on

Acknowledgement[6] I. Baxter, A. Yahin, L. Moura, M. Anna, L. Bier, Clone detection
using abstract syntax trees, in: Proceedings of the International
Conference on Software Maintenance 98, March 1998, pp. 368–377.
[7] ClearCase. http://www-306.ibm.com/software/awdtools/clearcase/.
[8] S. Ducasse, M. Rieger, S. Demeyer, A language independent
approach for detecting duplicated code, in: Proceedings of theInternational Conference on Software Maintenance 99, August
1999, pp. 109–118.
[9] M. Fowlor, Refactoring: Improving the Design of Existing Code,
Addison Wesley, 1999.
[10] J.H. Johnson, Navigating the textual redundancy web in legacy
source, in: Proceedings of the 1996 Conference of Centre forAdvanced Studies on Collaborative Research, November 1996, pp.
7–16.
[11] T. Kamiya, S. Kusumoto, K. Inoue, Ccﬁnder: A multi-linguistic
token-based code clone detection system for large scale source
code, IEEE Transactions on Software Engineering 28 (7) (2002)
654–670.
[12] C. Kapser, M. Godfrey, Improved tool support for the investigation of duplication in software, in: Proceedings of the 21stInternational Conference on Software Maintenance, September
2005, pp. 305–314.
[13] R. Komondoor, S. Horwitz, Using slicing to identify duplication insource code, in: Proceedings of the 8th International Symposium on
Static Analysis, July 2001, pp. 40–56.
[14] J. Mayrand, C. Leblanc, E. Merlo, Experiment on the automatic
detection of function clones in a software system using metrics, in:Proceedings of the International Conference on Software Maintenance 96, November 1996, pp. 244–253.
[15] M. Rieger, S. Ducasse, M. Lanza, Insights into system-wide code
duplication, in: Proceedings of the 11th Working Conference on
Reverse Engineering, November 2004, pp. 100–109.
[16] SourceOﬀSize. http://www.sourcegear.com/sos/.
[17] Y. Ueda, T. Kamiya, S. Kusumoto, K. Inoue, Gemini: maintenancesupport environment based on code clone analysis, in: Proceedings of
the 8th International Symposium on Software Matrics, June 2002, pp.
67–76.
[18] Y. Ueda, T. Kamiya, S. Kusumoto, K. Inoue, On detection of gapped
code clones using gap locations, in: Proceedings of the 9th AsiaPaciﬁc Software Engineering Conference, December 2002, pp. 327–
336.
[19] VisualSourceSafe. http://msdn.microsoft.com/vstudio/previous/ssafe/.
[20] A. Walenstein, N. Jyoti, J. Li, Y. Yang, A. Lakhotia, Problems
creating task-relevant clone detection reference data, in: Proceedingsof the 10th Working Conference on Reverse Engineering, November
2003, pp. 285–294.
[21] WebLogic. http://www.beasys.com/products/weblogic/.
[22] WebSphere. http://www-306.ibm.com/software/websphere/.
[23] S.W.L. Yip, T. Lam, A software maintenance survey, in: Proceedingsof the 1st Asia-Paciﬁc Software Engineering Conference, December
1994, pp. 70–79.

py

Of course, further research issues remain. For example,
sometimes gaps occur between the original code fragments and the modiﬁed ones since developers areusually modifying copied and pasted code fragments.
Here, we call modiﬁed the code fragments, which include
some gaps, Gapped code clones [18]. By treating the gapped
code clones as well, our methods can become more
eﬀective.
As described in Section 3.2.1, the proposed ﬁltering
method only deals with language-dependent code clones.
We are going to improve the method to ﬁlter out application-dependent code clones. Features of application-dependent code clones are so strikingly diﬀerent among softwaresystems that such metric-based ﬁltering as RNR is probably
unpractical. We believe that pattern-based ﬁltering works
well. For example, users input code patterns that they are
not interested in. After that, Gemini ﬁlters out all code
clones whose contents correspond to the code patterns.
Using such a ﬁltering approach, we can ﬁlter out any kindof code clones dependent on the domain or the frameworkof a system.

pe

References

Au

th
o

r's

[1] Ant. http://ant.apache.org/.
[2] B.S. Baker, A program for identifying duplicated code, in: Proceedings of the 24th Symposium of Computing Science and Statistics,
March 1992, pp. 49–57.
[3] B.S. Baker, On ﬁnding duplication and near-duplication in large
software systems. in: Proceedings of the 2nd Working Conference on
Reverse Engineering, July 1995, pp. 86–95.
[4] M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe, K. Kontogiannis,
Advanced clone-analysis to support object-oriented system refactoring, in: Proceedings of the 7th IEEE International Working Conference on Reverse Engineering, November 2000, pp. 98–107.
[5] H.A. Basit, S. Jarzabek, Detecting higher-level similarity patterns
in programs, in: Proceedings of the ACM SIGSOFT Symposiumon the Foundations of Software Engineering, September 2005,
pp. 156–165.