arXiv:2003.05615v1 [cs.SE] 12 Mar 2020

Code Clone Matching:
A Practical and Effective Approach to Find Code Snippets
Katsuro Inoue

Yuya Miyamoto

Osaka University
Osaka, Japaninoue@ist.osaka-u.ac.jp

Osaka University
Osaka, Japan
yuy-mymt@ist.osaka-u.ac.jp

Daniel M. German

Takashi Ishio

University of Victoria
Victoria, Canada
dmg@uvic.ca

Nara Institute of Science and Technology
Ikoma-City, Japanishio@is.naist.jp

ABSTRACT
Finding the same or similar code snippets in source code is one offundamental activities in software maintenance. Text-based patternmatching tools such as grep is frequently used for such purpose, but
making proper queries for the expected result is not easy. Code clone
detectors could be used but their features and result are generally
excessive. In this paper, we propose Code Clone matching (CCmatching for short) that employs a combination of token-based
clone detection and meta-patterns enhanced with meta-tokens. The
user simply gives a query code snippet possibly with a few metatokens and then gets the resulting snippets, forming type 1, 2, or
3 code clone pairs between the query and result. By using a codesnippet with meta-tokens as the query, the resulting matches arewell controlled by the users. CC matching has been implemented
as a practical and efficient tool named ccgrep, with grep-like userinterface. The evaluation shows that ccgrep is a very effective tofind various kinds of code snippets.

CCS CONCEPTS• Software and its engineering → Software maintenance tools.

KEYWORDS
code snippet search, pattern matching, grep, code clone types

1

INTRODUCTION

Finding and locating code snippets in source code files are fundamental activities to understand and maintain software systems[9,35]. When we identify a bug in a code snippet, we would search
the same or similar snippets in the same or other systems to checkif they contain the same bug[16, 17, 30]. When we modify a codesnippet for feature change or enhancement, we would find thesame or similar snippets for preventing unintentional inconsistentbug[26, 44]. When we identify a code snippet with a bad coding
practice, we would search the same or similar snippets for possible
refactoring[34].
To find the same or similar code snippets effectively, various
kinds of software engineering tools or IDE’s have been proposed
and implemented[9, 42]; however, it has been reported that thecharacter-based pattern matching tool grep[11] is still widely used
to find code snippets, due to its simplicity, trustworthiness, speed,
and availability[21, 38]. Although grep is very convenient to findlines with specific keyword, it is not easy to make a proper query
for a code snippet that ignores comments and white spaces, andmight span multiple lines.
Code clone is a pair of code snippets those are identical or similar
each other[6]. A large body of scientific literature on clone detection
has been published and various kinds of code clone detection tools(detectors) have been developed[33, 36]. Most of these detectors aredesigned to detect all of the code clone pairs in the target source
files, and thus, the resulting code clone pairs become generally
huge[22] and they contain a lot of code clone pairs that might
not be of interest (including false positives). There are a few toolsthat find similar code snippet for a query code snippet, but theirperformance and usability are limited[15, 24, 32].
In this paper we propose a method, which we call Code Clone
matching (CC matching), to find clones of specific code snippets
by using a combination of clone detection and pattern matching.
Search queries can be simply code snippets, or code snippets enhanced with meta-patterns (with meta-tokens having leading $)that can provide flexibility to narrow or broaden the search query.
An example of a query that uses meta-patterns would be searchingfor for-loops in which the control variable of the for-loop is thevariable index and which contains a return statement inside thebody of this for-loop, represented likefor($index=$$){$$ return $$}As a consequence, CC matching is programming language aware,and able to properly tokenize the source code (ignoring whitespaceand comments). In clone-detection terms, CC matching retrieves,given a code snippet (that potentially includes some meta-patterns),
the clones (type 1, 2 and 3) of this snippet that also satisfy the metapatterns (e.g. that use a specific variable name in some specificlocations).
We will also present ccgrep, that is current implementation of CCmatching for C, C++, Java, and Python. ccgrep works as a handy
but reliable pattern matching tool with a grep-like and easy-tounderstand user interface. An evaluation of ccgrep shows that it
is capable of representing the queries for all of type 1, 2, and apart of type 3 clones. In addition, ccgrep accurately performs CC
matching, and the speed is slower than grep but faster than othersimilar code finders.
As far as we know, little has been studied on the pattern matchingbased on the notion of code clone. The contributions of this paper
are twofold:2.2• We propose CC matching, a new concept of matching codesnippets based on token-based code clone detection andenhanced pattern matching.
• We present a practical, efficient, and easy-to-use tool called
ccgrep that implements CC matching, with its evaluation.

Pattern Matching with grep

grep takes a query pattern in a form of a regular expression (oran extended regular expression), and reports the matched lines inthe target files. Developers specify a keyword, or a short idiom as
the query, and get the result output composed of the file paths andmatched lines. grep is generally fast and effective, but sometimes
a simple query pattern generates a large output which is hard toanalyze further. A complex query pattern might reduce the size ofthe output, but making a proper query is not an easy task even foran expert of the tool.
Also, grep is designed to work with any text file, and it is not
specifically designed to explore source code files. Unless a complex
query is written, it reports matches in comments (which users
might want to have ignored) and it is difficult to find matches
that spawn multiple lines. Furthermore, because grep is based on
finite state machines, it is not capable of dealing with matching
parenthesis, brackets or braces (e.g. one might want to match theentire block of code inside a for-loop, including other blocks insideit). There have been various proposals for extending grep to docode matching[1, 5, 8]; however, none of these have been successful
as grep.

2 BACKGROUND
2.1 Motivating Example
Some uses of the ternary operator (e.g., exp1 ? exp2 : exp3 meaning
the result of this entire expression is exp2 if exp1 is true, otherwise
the result is exp3—available in C, C++ and Java) are, arguably, considered bad practice[41]. For example, the use of a < b ? a : b isarguably harder to read than using min(a,b). Therefore, it might bedesirable to replace the ?: operator with a function or macro that
returns the minimum value. The following is an example found in
the file drivers/usb/misc/adutux.c in the Linux kernel (v5.2.0).
amount = bytes_to_read < data_in_secondary ?
bytes_to_read : data_in_secondary;This line of code should be replaced with a more readable expression(note that the macro min in Linux guarantees no side effects):
amount = min(bytes_to_read, data_in_secondary);
Finding all occurrences of such usage of the ternary operator
using grep is not easy. For example, simply executing "grep ’<’" forall 598 files (total 51,6394 lines in C) under /drivers/usb produces
16335 matching, including many unwilling patterns such as "if(a<b)", "for (i=0; i<x; ...)", or "#include <linux/...> ". We
could narrow the matches by concatenating grep like,

2.3

Code Clone Detection and Search

A code clone is broadly defined as a code snippet having the sameor similar code snippets in the target software collection[3, 20, 36],
and a code clone pair is classified into 4 types, type 1 (syntacticallythe same snippets except for comment or whitespace differences),
type 2 (type 1 with identifier or literal differences), type 3 (type 2
with addition, deletion, or change of statements within the clone),and type 4 (semantically equivalent snippets)[36].
Code clone detector is a promising method for finding codesnippets with unique characteristics. A user would want to simply
provide a snippet and then find all the clones of this specific snippet.
However, most of those clone detectors report all of code clone
pairs in the target files; these results are generally huge and mostly
irrelevant for finding specific code snippets. Further, most clone
detector tend to ignore small-size clones[28] and so they would misssmall code snippet for search as shown in the motivating example.
Some code clone detector, such as ccfinderX [19], have an option to find clones between a specified file and all other files; however, we still need to prepare a query file and also need to tune
various parameters to the specifics of the query (such as its length),which heavily affect the detection result[36].
There are several tools dealing with code search for code clone
pairs, such as CBCD[24], NCDSearch[15], and Siamese[32]. CBCD
is a PDG (Program Dependency Graph)-based code matching tool bygraph isomorphism testing. NCDSearch is a block-based code searchtool using normalized compression distance of two code snippets.
Siamese is token-based code retrieval tool with inverted index.
These tools would show good accuracy as code clone finder forcertain conditions, but they would still have issues on performanceor usability as daily-used practical software engineering tool.
Another issue is usability of the tools. Most of those tools are
stand-alone in the sense that they take their specific input format
and generate proprietary output. Integration with other tools needs

grep ’<’ -r . | grep ’?’ | grep ’:’
However, it still produces 149 matches. Perhaps more problematicis that the expressions could span multiple lines. While it is possible
to create a complex regular expression to find these expressions, itwould be time consuming and potentially error prone.
Another alternative would be to use a clone detector to detect
uses of the ?: operator. The clone detector NiCad[7] detects 646
block-level clone classes for the drivers/usb files by the default
setting, but no snippet with the ternary operator case is includedin the result because it is too small to be detectable.
Ideally we would like to be able to specify simple and easyto-create-and-understand query to find these types of snippets.
Therefore in this paper we propose CC matching, which is based on
the notion of code clone detection. Using CC matching, the queryis written simply as:a < b ? a : b
In a nutshell, this query specifies that a variable (represented by a)should be followed by < and then a second variable (representedby b), followed by a ?, followed by the same first variable found,followed by :, followed by the second variable. Also, whitespaceand comments should be ignored. This query would match x<y?x:y
but it would not match x<y?x:z.
Using this query, we used our implementation of CC matching(which we call ccgrep) to find the occurrences of this type Linux’s
drivers/usb. We identified 3 instances, and submitted patches toreplace them with min. Two of those patches have been acceptedalready into Linux.
2

3.3

to transform their input/output formats, so it becomes hard tocollaborate with others.

3 CC MATCHING
3.1 Design Policy
Our design policies of CC matching are as follows.
• CC matching is a process of finding code snippets in the target source code for a query snippet. The query and matchedresult can be seen as a code clone pair of either type1, 2, or
3. The query is a code snippet or a code snippet enhancedwith meta-patterns that can widen or narrow the potential
matches.
• The matching is made at a granularity of a sequence of
language-dependent tokens (white space and comments are
removed) and not as simply sequences of characters. .
• CC matching can also precisely control how tokens in thequery are matched. Using command line options, the query
pattern can match type 1, type 2 (P-match), type 2 (non-Pmatch) and a part of type 3 clone snippets effectively.

3.2Type 1 Matching

The most simple type of query in CC matching—named type 1
matching—is the case that m = n and qi = $ti for each identifier orliteral and qi = ti for other tokens. Type 1 matching is performed
to find the exact code snippet, discarding comments, white spaces,
or line breaks. This type of query does not use wildcard nor regularexpression tokens. These are examples of queries and targets:
q1: $a = $0; $b = $10;
t1: a = 0; b = 10;
q1 matches t1 as type 1 matching. Note that annotating all identifiers
and constants with $ would be sometimes bothersome; for thisreason our implementation has an option for automatic annotationof these tokens to find any type-1 clone of the query.
The next example is a case of "no match".
q2: $a = $0; $b = $10;
t2: a = 0; b = 20; (no match)
Literal 10 does not match 20, thus overall q2 does not match t2.

3.4

Formulating CC Matching

Type 2 Matching, P-Matching, and Pinning
Down

For the query token sequence q 1 , ..., qm and the target token sequence t 1 , ..., tn , if n = m and norm(qi ) = norm(ti ) for each i, thenq matches t as type 2 matching. Here norm is a normalization function to flat the distinction of identifiers (or literals), defined below.

The input of CC matching is the query q, the target T of sourcecode files in a programming language L, and matching option o.
The output is a matched code snippet t in T 1 . We refer to reserved
words, delimiters (operators, brackets, ; ...), identifiers, and literals
in L as regular tokens. Other tokens starting with meta symbol $are called meta-tokens. q is a sequence of regular tokens and themeta-tokes, and each matched result t is a sequence of the regulartokens. These token sequences do not contain comments, whitespaces, or line breaks. We always consider the matching on thetoken sequence level, not on the character level.
In Tab.1, we define a token-level matching for various kinds oftokens in CC matching, with simple examples. The basic ideas ofthese matches are as follows.

 #id if x is an identifier#li if x is an literal xotherwiseIn type 2 matching, an identifier in the query can match any identifier in the target, and also a literal in the query can match any
literal in the target.
q3: a = 0; b = 10;
t3: x = 10; y = 200;
q3 matches t3, because the sequences of the normalized tokens areboth [#id, =, #li, ; , #id, =, #li, ; ].
A special case of type 2 matching, with a constraint such thatfor any identifier or literal qi if qi = q j , then ti = t j , is called
Parameterized match or P-matching. This is sometimes referred toconsistent or aligned matching, meaning the same identifiers (orliterals) in the query are mapped into the same ones in the target.
P-matching is formally defined with a specialized normalization
function normp (), as follows.
norm(x) ≡• A language-defined token such as reserved words or delimiters matches the exact token.
• A user-defined token such as identifier or literal can match
same kind of token with a possibly different name or value.
To pin down them to a specific identifier name or literalvalue, $ is used before the token. For example, $count would
match only the token count.
• Wildcard tokens $., $#, and $$ are introduced for the matches
to any single token, any token sequence, or any token sequence discarding paired brackets, respectively.
• Popular regular expression operators for choice, repetition,and grouping are introduced to enhance the expressiveness.

 #idpos(x ) if x is an identifier#lipos(x ) if x is a literal xotherwiseHere, pos(x) is a function returning position i such that identifier(or literal) x is the i-th identifier (literal) newly appeared in thetoken sequence2 .
q4: a = 0; a = a + b;
t4: y = 0; y = y + c;
For q4, pos(a) = 1 and pos(b) = 2, and for t4, pos(y) = 1 and pos(c) =2. q4 matches t4 as P-matching, because the P-normalized sequences
normp (x) ≡Consider that query q is a token sequence q 1 , ..., qm (1 ≤ m),
and a target t is a token sequence t 1 , ..., tn (0 ≤ n). From q 1 to qm ,if each token in the query matches tokens in the target from t 1 totn as defined in Tab.1 without overlapping or orphan tokens, thenwe say q matches t by CC matching.
1 Note that in an actual implementation of CC matching, the location of all the matched

2 Note that any meta-token starting with $ in the query and their matched tokens incode snippets in T will be the output, but for simplicity of the explanation here, wetake one of the matched snippets itself t as the output.

the target are out of consideration of pos().
3

Table 1: Token-Level Matching
token(s) in querymatched token(s) in target

simple example of matchquery
target
while
while
(
(
mynameabc
1100$mynamemyname
$1
1
$.
if
$# +
while(f(a+reserved word†delimiter
identifier
literal$identifier$literal
$.
$# X
$$ X

exact reserved word
exact delimiter
any identifier‡
any literal‡
exact identifier
exact literalany single token
any shortest token sequence ending with X
any shortest token sequence ending with X, excluding X
inside well-balanced bracket {...}, [...], or (...)$$ +while(f(a+1))+
X $| Yeither X or Y
+ $| X $*repeated sequence of X zero or more times
( $*
(((
X $+
repeated sequence of X one or more times
( $+
((
X $?
X or none( $?
($( X1 X2 ... $)X1, X2, ... (group for further regular expression operations) $( a++ $| ++a $) a++†Type names are treated as identifiers.
‡Identifier and literal may match only the exact one by an option.
Tokens starting with $ are meta-tokens and others are regular tokens.
Wildcard meta-tokens $# and $$ match in reluctant way, and $*, $+, and $? match in possessive way[14].
X, Y, X1, X2, ... are any regular token or a group with $( ... $).
are both [#id 1 , =, #li 1 , ; , #id 1 , =, #id 1 , +, #id 2 , ; ]. The following caseis type 2 matching but not P-matching.

3.5

Wildcard Tokens and Type 3 Matching

There are three wildcard tokens, $. (any token, but only one), $#(any token sequence), and $$ (any token sequence with bracket
discarding). $. matches any single token in the target, and $# X
matches any shortest token sequence ending with X. $$ X is similar
to $# X but it does not end at X inside balanced brackets {...}, [...],and (...). In this case, the match continues until the first X outside
the balanced brackets; thus X’s inside the brackets are not seen.
For the query token sequence q 1 , ..., qm and the target token
sequence t 1 , ..., tn , if a wildcard token qi in the query matches sometarget tokens t j , ..., t j+k −1 , and other query tokens match properly
the target tokens (as defined in Tab.1), preserving the order of thequery and the matched target tokens without any overlapping ororphan tokens, we call it type 3 matching. Here, k ≥ 0, meaningthat the matched token sequence may be none(k = 0), a single
token(k = 1), or more(k ≥ 2). Here we present several examples of
wildcard tokens.

q5: a = 0; a = a + b;
t5: y = 0; y = z + c; (type 2 matching but not P-matching)
At t5, z cannot be matched by a because normp (a) = #id 1 is notequal to normp (z) = #id 2 . As a default of CC matching, P-matchingis assumed3 .
Sometime type 2 matching, even P-matching might match manytargets, and we would want to narrow them by pinning down an
identifier (or literal) to a specific one. To do this, we also use theannotation of $ at the beginning of the identifier (literal) in thequery, so that the identifier (literal) headed by $ is not normalized
and it matches only the exact token in the target.
q6: $cat = 1
t6-1: cat = 1 (match)
t6-2: dog = 1 (no match)

q8: $a = $. ;t8-1: a = b ;t8-2: a = 10 ;q6 matches t6-1, but it does not match t6-2 since identifier cat is
not normalized and is pin down to cat.
We can mix normalized identifiers (literals) and non-normalized
ones in the query as follows.

In this case, query q8 matches both t8-1 and t8-2, by the replacementof $. with b and 10, respectively.

q7: $cat = cat+1
t7: cat = dog+1

q9: $a $# ;t9-1: a = b+c ;t9-2: a++ ;q7 matches t7, because $cat in q7 and its corresponding target cat
in t7 are excluded from consideration of pos(), and so both cat in
q7 and dog in t7 are treated as the first appeared identifiers andboth are normalized to #id 1 .

Query q9 matches a and any tokens before ‘;’, and $# matched ‘=b+c’ in t9-1 and ‘++’ in t9-2.
q10: $a = $$ $b
t10-1: a = b

3 It can be changed by the tool’s option4t10-2: a = 10+c+bt10-3: a = f(b,10)+b
t10-1 is the case that the wildcard $$ matches none, t10-2 is ‘10+c+’,
and t10-3 is ‘f(b,10)+’ where the first b is inside the bracket (...)
and it is not matched by $b. The next is a more complex example.
q11: a= f(p); if($$){a=-a;}t11-1: b= g(q); if(c<=0){b=-b;}t11-2: b= g(q); if(h(c)==0){b=-b;}

Tokenizer
Generator

Tokenizer
Generator

Tokenizer
Generation(executed only
once for eachlanguage)

Map Table
Tokenizer
Token
Sequence

Tokenizer

TargetCCMatcher

OutputFormatter

OutputToken
Sequence

OptionccgrepFigure 1: Architecture of ccgrep- Setter method
q18: T1 f(T2 v1){this.v1=v2;}

Regular Expression Extensions- i f statement
q19: if ($$){$$}

To effectively represent queries for largely different variants, CC
matching employs regular expressions in its query with meta symbols |, *, +, ?, (, and ) preceded by $.

- f or statement using control variable
q20: for(T i=0; i<$$; i++){$$}

Selection: p1 $| p2 means a matching by either patterns p1 or
p2.
Iteration: p$*, p$+, and p$? are the repetition of p zero or moretimes, one or more times, and zero or one time, respectively.
Grouping: $( p $) defines the scope and precedence of meta
symbols in pattern. For example, $(p1 | p2 $)$+ means any
repeated pattern of p1 or p2.

These queries can be narrowed by restricting to specific identifiers or constants, by using $id, or $0 to match id or 0 exactly.

4

IMPLEMENTATION OF CC MATCHING

We have implemented our proposed CC matching approach forfinding code snippets in a tool named ccgrep4 . The target languagesof ccgrep at this moment are C, C++, Java, and Python3. We havechosen a grep-like input/output interface to facilitate its adoption.

For example, we can find nested if-else clauses as follows.
q12: $( if $$ else $) $+t12: if(i<10) {a=0;} else if(i<20) {a=5;} else
In this case, conditional expressions and then-clauses are matchedby $$, and if-else are sought until else is not followed by if.

3.7

Language
Definition

Query

In this query, the conditional expression of if statement can be
any token sequence followed by the closing bracket ). In t11-1, $$matches b<=0, and in t11-2 it matches h(b)==0 where the first closing bracket is balanced with the open bracket so that the matchingfor $$ continues after h(b) until another closing bracket appears.
With these wildcard tokens, we can specify possible changes of
the target token sequence, i.e., variants of the target code snippet.

3.6

ExtendedToken
Definition

4.1

Architecture of ccgrep

The architecture of the process of ccgrep is presented in Fig.1. Eachcomponent is described below.
Tokenizer Generators: Parser generator ANTLR5 is used togenerate two kinds of tokenizers. For the target tokenization,
only the language definition is used to recognize the regulartokens, but for the query tokenization, the definition of themeta symbol extension for the meta-tokens explained inSec.3.2 and that of regular tokens are used. This process has
been executed only once for each target language.
Tokenizers: Each tokenizer removes white spaces and comments from the input text, and decomposes the code into
tokens. The query tokenizer accepts the meta-tokens starting with $ and the regular tokens defined by the language,
but the target tokenizer accepts only the regular tokens. The
tokenizer for the target files are executed in parallel for eachfile, along with following CC Matcher.
CC Matcher: This performs a naive sequential pattern matching algorithm between two token sequences for the queryand the target[13]. For the case of the selection pattern in thequery, simply each case is tested one by one. For type 2 code

Finding Various Code Patterns

Combining the regular tokens and meta-tokens in the query, we
can find various kinds of code snippets in the target, from simple
to complex code patterns. The following are examples in Java.
- Method XY Z with no parameter
q13: $XYZ( )- Method XY Z with 0 or more parameters
q14: $XYZ($$)- Method print with variable bu f as the 1st parameter
q15: $print($buf, $$)- Any method definition
q16: T f($$){$$}
Note that type names are treated like identifiers andT matches
any type name.
- Getter method
q17: T f(){return this.v;}

4 https://github.com/yuy-m/CCGrep
5 https://www.antlr.org/

5





$ccgrep 'catch($IOException $$){$$ $toolError($$);}' -r .
./parse/TokenVocabParser.java: catch (IOException ioe) {./Tool.java:
catch (IOException ioe) {./Tool.java: catch (IOException ioe) {./Tool.java:
catch (IOException ioe) {./Tool.java: catch (IOException ioe) {./codegen/CodeGenerator.java: catch (IOException ioe) {./codegen/target/SwiftTarget.java:
catch (IOException ioe) {$

5

EVALUATION Goal of the evaluation is to show that our proposed approach, CC
matching and its implementation ccgrep, can find various kinds
The target is ANTLR V.4, ∼antlr4/tool/src/org/antlr/v4/.
of intended code snippets effectively and efficiently, compared to
Figure 2: An Example of ccgrep Output
other approaches. This goal could be decomposed into following
three research questions.
RQ1:Query Expressiveness Are various kinds of queries expressed by CC matching (and also its implementation ccgrep)?
Also, Are the queries written more easily than grep ?
RQ2:Accuracy of ccgrep Is ccgrep accurately find various
types of code clones already detected by other approaches?.
RQ3:Performance of ccgrep What it the execution time of
ccgrep? Is the token-based naive sequential pattern matching approach fast enough in practice, compared to othertools such as grep or code-clone search tool NCDSearch?

clone matching, we record normp () values for each identifier
and literal in Map Table so that we can check if correspondence of identifiers in the query and target is consistent or
not. Note that the table contents are flushed for each query.
The option controls the normalization level, input language,
output form, and many others discussed in the next section.
Output Formatter: This process constructs the output for the
successful matching result. Based on the input option, we canview the match result, like grep, in the form of the file nameassociated with the matched top line as the default, or as
many other styles such as full matched lines, only the numberof lines, or so on. Fig.2 is an example output of ccgrep wherecatch statement followed by identifier IOException anda specific call toolError(...) are sought in java files of
ANTLR Ver.4, and the top lines of the matched results with
their file paths are listed.

5.1

RQ1: Query Expressiveness andEffectivenessRQ1 explores how easily we can make the queries by our approach.
Here we discuss the way of creating queries of each matching type.
Since expressiveness of CC matching is equivalent of that of ccgrep
we only mention ccgrep here.

ccgrep is written in Java associated with the ANTLR output,
and it is easily installed and executed in various environments suchas Unix and Windows (a single JAR is provided that contains all
the required libraries needed to run it).

4.2

Output (Print-Out) Form: Various kinds of output forms canbe chosen. The default is a familiar form of grep, and thiscan be changed to different styles. The print out is usually
made to the character-based standard output, but it can bechanged to a JSON or XML format file.

5.1.1 Various Queries Classified with Matching Types. As shown inprevious sections, it is obvious that our approach can easily create
various query patterns for type 1 matching, type 2 matching with
P-match, and type 2 matching with non-P-match, by specifying acode snippet associated with appropriate options. In addition, we
can specify the name of an identifier or literal, if we place $ before
the name.
A type 3 code clone is one with a few statement addition, ordeletion, or change for a seed snippet. Thus the query for type3 matching could be made from the seed by adding meta-tokens
such as $., $$, or $*, deleting some regular tokens in the seed, or
modifying some regular tokens with $., $$, or other meta-tokens,
if we could specify how to modify the seed. We call such a type 3
matching specified type 3 matching, here.
On the other hand, we might want to make a broad query thatmatches all the code snippets of type 3 code clone for the seedwith similarity higher than a threshold. We call it unspecified type3 matching. Currently, CC matching (and ccgrep) does not have afeature for the unspecified type 3 matching. We will discuss further
on this issue in Sec.6.2.
Type 4 clones, which are semantically the same but syntacticallydifferent, are not considered here, because those cannot be foundby syntactical pattern matching approach like ours and we consider
that they are out of scope in this research.

Input/Output and Options of ccgrep

ccgrep has a character-based user interface, and it takes similar
options and standard input/output treatment to grep so that developers familiar with grep can easily use ccgrep. The options are as
follows.
Target Language: Currently, Java, C, C++, and Python3 are
the target languages we have implemented. The default target language is Java.
Target Files: The target files are specified by the commandline or they are sought recursively from the specified directory. By connecting ccgrep with pipe ’|’, the target becomesthe result of the previous command, and therefore we can
combine ccgrep with other shell commands or ccgrep repeatedly effectively.
Query Pattern: The default setting requires the query patternat the command line. This can be changed to a specified fileor the standard input.
Normalization (Blind) Level: We can choose the normalization level (blind level) of user defined identifiers and literals,
such as none for non normalization of type 1 clone detection,
P-matching for type 2 with consistent name change, non-Pmatching for all type 2 clone. The default is P-matching.

5.1.2 Comparison with grep. [Type 1 Matching]
For finding type 1 clones with ccgrep, we can place a code snippet
6Table 2: Various Queries for kmalloc in usb drivers
query
1
2
3
4
5
6†

kmalloc($$)$kmalloc($$)$kmalloc(sizeof($$),$$)$kmalloc(sizeof(struct x),$$)
struct x *p = $kmalloc(sizeof(struct x),$$)

Table 3: Checked Clones in BigCloneBench#found109,101
333
84
29
9

Clone Type Clone Pairs Found Not Found
Type 148116 48111
5*Type 2
4234
4232
2*
Total
52350 52343
7** indicates faulty clone pairs in BigCloneBench.

struct u132_endp *endp =kmalloc(sizeof(struct u132_endp), mem_flags);†With command option for non normalization (type 1 matching)

3

In this example, we start at query 1 with the type 2 matchingof kmallock() with any parameter list denoted by $$. This querymatches any function calls, thus it produces a large number of theresult(#found). In query 2, we pin down function name to kmalloc,
so that the result is reduced to a few hundred. We can further
narrow the matches by specifying the first parameter with sizeof
at query 3, and with any struct name x at query 4. At query 5, we
specify an assignment to a pointer variable with the same struct
name x, producing nine matches which are easily checked by hand.
We take one of these and give it as query at 6 as it is with nonnormalization option, resulting in three type 1 clones including thequery snippet itself.
As shown by this example, we can interactively and effectively
narrow or widen the matching with adding normal or meta-tokens
in queries.

as the query with non-normalization option (or adding $ to all identifiers and literals). Note that query strings below are surrounded
by a box to clearly separate from other descriptions.
int a = b; with non-normalization option

q21(ccgrep):

Instead, grep needs to care about white spaces between tokens.
q22(grep):\s*int\s+a\s*=\s*b\s*;

As seen here, q21 is simpler and more straightforward than q22.
Furthermore, additional complication should be needed for q22 if
we would want to eliminate comments possibly located between
tokens.
[Type 2 Matching]
Following are type 2 matching with any long variable declaration.
$long a;q23(ccgrep):q24(grep):

5.2

For evaluation of query-matching (or information retrieval) systems,
recall and precision values, computed by comparing the matchedresults with the oracles for the queries, are popularly employed[2].
Here in our approach, however, the query to CC matching has noambiguity and it reports the matching result rigorously as expected
and specified by the query with options. In such sense, the result
is always the same as the oracle, i.e., the recall and precision arealways one. Thus, instead of using recall and precision, here we
simply investigate if ccgrep works accurately in the sense thatcode clones already reported by other approaches could be foundby our approach.
For this purpose, first we have employed BigCloneBench[43]that is a huge collection of various kinds of code clones. We haveextracted all pairs classified as type 1 and type 2 code clones from
BigCloneBench, and for each clone pair (sp1, sp2), we have checked
if sp2 is successfully found in the result of ccgrep for sp1 as querywith appropriate options, and vice versa. Tab.3 shows the numbersof type 1 and 2 clones, accurately found and not.
As we can see in Tab.3, most type 1 and 2 clones are foundaccurately. There were several cases of not-found clones, and wehave investigated further those cases and recognized that thosecases are faults of the classification of BigCloneBench, some ofwhich should be classified into type 3, and some others are notclones. Thus, we can say that all of proper type 1 and 2 clones in
BigCloneBench were perfectly found by ccgrep.
For type 3 clones, since BigCloneBench contains a lot of faulty
type 3 data, we have instead used CBCD data[24], that contains
11 type 3 clone sets taken from the source code of Git, the Linuxkernel, and PostgreSQL. We have crafted type 3 queries from oneof code snippets in each clone set as the seed and have checkedlong\s+[a-zA-Z][a-zA-Z_0-9]*\s*;Both are equivalent but grep requires a much more complex representation for any possible identifier.
[Specified Type 3 Matching]$time($$) Find time with any parameterq25(ccgrep):q26(grep):time(

RQ2: Accuracy of ccgrep

Find string ‘time(’

In this case, we are searching type 3 clones of a function call time(),and ccgrep can easily specify it directly. However, in grep case,
if we simply give time, it matches many variable names and comments, so we add ’(’, a partial string of function call, which might
reduce such unwanted matches. We have applied these two queries
to linux’s tools6 . ccgrep matched 47 time() function calls. On
the other hand grep matched 382 lines that include strftime(),
get_time(), and many other function calls7 . Therefore, we would
say that our approach is straightforward to locate specific identifiers
or function calls, and that creating proper queries for grep is morecomprehensive and difficult, compared to our our CC matchingapproach with ccgrep.
5.1.3 Narrowing Matching Results. An advantage of ccgrep is interactive and repeated matching trials such that the users can try
various queries immediately after a result is not sufficient. As an
example, we show in Tab.2 a process of investigating a system callfunction kmalloc() in Linux usb driver sources /drivers/usb/*.
6 ~ linux/tools, rev. 4.20.0.
7 If we add -w option (word-based matching) to grep, the result is reduced to 7 matches

but it misses the cases immediately followed by a word such as time(NULL).

7

ccgrep query$( $map_write($map, $$, $$); $) $+$( $chip->state = FL_ERASING; $) $+Snippet 1

map_write(map, cfi->sector_erase_cmd,
chip->in_progress_block_addr);
chip->state = FL_ERASING;
chip->oldstate = FL_READY;Snippe 2

map_write(map, CMD(0xd0), adr);
map_write(map, CMD(0x70), adr);
chip->state = FL_ERASING;
chip->oldstate = FL_READY;Snippe 3Table 4: Target and Execution Result by ccgrep
Target

Antlr

Ant

Git

PgSQL

Linux

Lang.
#file
#line

Java
678
59,511Java
1,272
138,396

C
339
90,495

C
904
177,174

C
15,1233,756,212

qA




qB
qC
qD




#found0
2
8348
time(sec.)
1.12
1.32
1.11
1.43
9.46
#found
159
161
7
27
543
time(sec.)
1.15
1.33
1.10
1.47
10.15
#found
1,710
2,487
5,717
10,603
187,653
time(sec.)
1.20
1.38
1.13
1.55
12.01
#found1
13442
621
10,754time(sec.)
1.19
1.52
1.10
1.49
11.06
Antlr: Antlr4 v.4.7.2, Ant: Apache Ant v.1.10.5, Git: v.1.6.4.3,
PgSQL: PostgreSQL v.6.5.3, Linux: Linux kernel v.2.6.14rc2

map_write(map, CMD(LPDDR_RESUME),
map->pfow_base + PFOW_COMMAND_CODE);
map_write(map, CMD(LPDDR_START_EXECUTION),
map->pfow_base + PFOW_COMMAND_EXECUTE);
chip->state = FL_ERASING;
chip->oldstate = FL_READY;

for(a = 0; a < $$; a++) { $$ }qD: $|
a = 0; while(a < $$) { $$ a++; }Find for or while statement with a control variable.
 Tab.4 shows the size metrics of the target, the number of foundsnippets, and the execution time of each query on a workstation
Figure 3: An Example of Crafted Query and Type 3 Clones
with Intel Xeon E5-1603v4 (@2.8GHz × 4), 32GB RAM, and Winfor CBCD Data
dows 10 Pro for WS 64bit.
As we can see from Tab.4, the execution times are about 10 sec.
even for a few million lines of Linux kernel target. This might not
if those queries accurately match the other snippets in the same
be very fast, but we would think that they are acceptable speed asclone set. We have confirmed that all the crafted queries accurately
a daily-used development or maintenance tool.
match other snippets in each clone set. Fig.3 shows an example
The execution times for qA to qD are very stable for each target.
of a crafted query and its type 3 clone set. In this example, funcFor example, in the case of Linux, they are about 10 sec. even fortion map_write(...) is repeatedly invoked followed by repeatedthe small #found case (48 for qA) and the large #found case (187,653
assignments to variable chip’s elements.
for qC). Thus, we would say that the execution time is not heavily
As far as our investigation, all the matches are controlled by theaffected by the result size (#found) but mainly affected by the target
query, and are performed accurately as we have expected.
size (#line).
Targets Ant in Java and PgSQL in C have similar sizes around140-180K lines, and the execution times are also similar around
5.3 RQ3: Performance of ccgrep
1-1.5 sec. This would show that the execution time is not strongly
It is interesting to know that our approach, i.e., token-based andaffected by the target language.
naive sequential pattern matching, can be implemented fast enoughFor comparison to other tools, we have used a code snippet finder
for practical use. We have examined various queries for ccgrep
NCDSearch[15] and grep. NCDSearch finds similar code blocks inwith the target source files of Antlr and Ant in Java, and CBCD
the target file for the query code block, by checking the normalized
data (Git, PostgreSQL, and Linux Kernel)8 in C, and have measured
compressed distance of the query and target blocks, and it reports
the performance of ccgrep. Following are employed queries. All
sometimes false positive results. For NCDSearch, we have used
execution was made with default setting of ccgrep except for theqA as its query, and for grep we have used GNU grep[11] withlanguage option.
following qA’.
qA: a < b? a: b([a-zA-Z_][a-zA-Z_0-9]*)\s*<
Find ternary operation to give a smaller value.
qA’(grep): ([a-zA-Z_][a-zA-Z_0-9]*)\s*\?\s*
qB: T1 f(T2 a) { return $$; }\1\s*:\s*\2Find function definition immediately returning a value.
This qA’ is to find ternary expression using an extended regular
qC: f($$, $$, $$);
expression9 , and it is almost equivalent query to qA for ccgrep
Find three parameter function.
except that qA’ does not allow the new line between tokens. In order
to allow the new lines for grep, the query expression becomes toocomplex to present here.
8 For comparison to CBCD, we have used the same data set, but currently those projects

9 We have used options -w and --include=’*.[ch]’. Some version of grep might

are enhanced 2 to 4 times larger, and the results for applying to the current projects
grow almost linearly in both #found and time.

require -E option or egrep command for the extended regular expression.
8

Table 5: Comparison of ccgrep with NCDSearch and grep
Target

Antlr

Ant

Git

PgSQL

Issues of code clones have become popular and acknowledged
by not only by software engineering researchers but also industry
people[23], along with prevalence of various clone detectors such as
stand-alone tools, CCfinderX[19], NiCad[7], and SourcererCC[37],or IDE’s with clone detection features such as Eclipse[45], or Visual Studio[27]. However, those are basically large systems, andtheir proper installation and operation are not easy in general. We
would encourage the creators of these tools to create simpler interfaces that make it easy to find specific instances of clones of small
snippets, as ccgrep does.

Linux

qA
(ccgrep)#found0
2
8348
time(sec.)
1.12
1.32 1.11
1.43
9.46
time ratio
1.0
1.0
1.0
1.0
1.0
qA
#found3
21
22
80 21,047(NCDSearch) time(sec.)
5.55 12.00 8.41
16.54 366.39
time ratio
4.96
9.09 7.58
11.57
38.73
qA’
#found0
1
82
44(grep)
time(sec.)
0.24
0.30 0.12
0.24
2.62
time ratio
0.21
0.23 0.11
0.17
0.28
Time ratio means the ratio of the execution times of each tool to ccgrep.

6.2

Extending Matching for Unspecified Type 3
Matching

As discussed in former sections, CC matching allows type 3 queries
as the specified type 3 matching, where we have to predict andspecify the variable parts of the seed snippet of the clone pair,with some wildcard tokens. For the unspecified type 3 matching,i.e., if we do not know the variable parts clearly, but would wantto find just ’similar’ code snippets with a similarity metric value
higher than a threshold, the current CC matching approach might
be insufficient.
To solve this issue, we could extend CC matching to allow unspecified type 3 queries, by introducing, say, similarity-based matchingor error-allowable matching[29]. However, this introduction would
be far away from the current policy of CC matching such that thematches are rigorously controlled by the query with options and no
ambiguity in the result is allowed. In such sense, although we areinterested in this extension, it would be accomplished as anothermatching framework and a different tool.

Tab.5 shows the execution result of ccgrep, NCDSerach, andgrep. Since NCDSearch contains false positives, the number offound (#found) is larger than that of ccgrep that contains nofalse positives. Also, since qA’ could sometimes miss the snippets
with new lines, #found for grep is sometimes smaller than that of
ccgrep.
ccgrep is faster than NCDSearch for all targets, and grep isfaster than ccgrep. Since grep is known to be very fast10 , wewould think that the speed of ccgrep is acceptable as a practicallyusable software engineering tool. We will also discuss on further
improvement of the performance in Sec.6.3.

6 DISCUSSIONS
6.1 CC Matching Approach
We have proposed and formulated CC matching as a method offinding code snippets for the user’s interest. The approach is basedon the notion of finding code clones in the target, and the query is a
simple code snippet or its extension with meta symbols representing
specified or wildcard tokens, regular expressions, and so on.
We would think that our approach is a very good support forsoftware maintainers who need to look around huge source code,due to various reasons such as bug fixing, feature locating, refactoring and so on. Compared to grep CC matching (and ccgrep) generally can make rich queries more easily and compactly, inthe sense that white spaces, new lines, or comments are not considered, and matching identifier or literals can be controlled withmeta-tokens.
In fact, during our testing and evaluation of ccgrep we scanned
the source code of Linux for specific clones. We discovered that thepattern a<b?a:b had been removed over time, yet some instances
persisted. As described in the Motivating Example, we fixed 3 ofthem in the usb/drivers modules and submitted patches for them.
To this date, two of the three have been accepted and are alreadyintegrated into Linux.
There are many other approaches proposed to make rich queries
for code matching[1]; however, those are not easy to use for many
software engineers due to their own query forms. Our approachrelies on the notion of finding code clones, which is straightforwardand easy to understand and to use for many people. In addition,
we have adopted a grep-like interface for ccgrep, which would
greatly reduce the burden of using a new tool.

6.3

Performance of ccgrep

As shown in the evaluation, ccgrep is not as fast as grep but wethink that it is acceptable as a practical and useful tool for finding
code snippets. Currently, ccgrep employs a simple and naive sequential matching algorithm. The mismatch information is not used
for the following process, but the algorithms using the mismatch
information such as Knuth-Morris-Pratt algorithm or Boyer-Moore
algorithm[40] could be used for further performance improvement.
In addition, in the current implementation, a sequential trial process
for the selection of regular expressions is employed, but it could be
improved by introducing the parallel processes.

7 RELATED WORKS
7.1 Pattern Matching Tools
grep was originally developed as a simple pattern matching toolfor Unix, and has been enhanced with many regular-expression
features and other fast pattern matching algorithms for GNU grep.
Variants of grep, such as context grep cgrep, approximate grep
agrep, and many others had been proposed and implemented tomeet various requirements[1]. However, there is no one for clonebased matching like ours.
Semantic-based matching tool sgrep[5] relates to our work inthe sense of matching based on the program contexts, and thelogic-based query pattern capturing language is proposed in [39].
However, compared to these approaches, our approach is much

10 https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

9closer to the original program syntax and code snippet, than theirproprietary query patterns. We would think, the learning cost for
our approach is smaller than those for special and proprietary
matching patterns.
Formalization of abstracted pattern matching over various languages had been proposed by Dekel et al.[8]. They have defined an
abstract code pattern language CPL focusing on semantics rather
than syntax. Paul et al. had proposed a formal data model with analgebraic expression-based query language[31]. Those approaches
are aiming at generalization and formalization of query patterns,
and our approach, on the other hand, focuses on language-depend
easily-created query patterns with notion of code clone and metapattern.
awk is a pattern matching and text processing tool for generaltext handling[12]. Though it provides flexible pattern matchingwith regular expressions and powerful actions associated with thematches, no mechanism for matching based on the notion of code
clones is provided.

7.2

in Sec.5.3. In addition, the user cannot predict properly the similarity
to be matched by the approach, which produces false-positive andunexpected matching result.
Siamese has been developed for finding code clone pairs for aquery method or file using multiple representation of n-gram token
sequences with inverted index[32]. It reports the ranked result oftype 1, 2, and 3 clones, and it shows good accuracy and scalability.
However, although its query response time is small, it requires
fairly long indexing time (e.g., about 10 minutes indexing time for
10,000 method target). Thus its application and usage would be
different from ours.

8

Code Clone Detectors

There are numerous number of publications on code clone detection
methods and their tools[33, 36]. Token-based approach is a very popular process for clone detection, and one of early works was Dup[3],where important notions such as P-match and suffix tree matchingalgorithm were used. CCFinder extended this idea to strengthen
practical use by normalization and other transformation[20]. CPMiner used a frequent subsequent mining method to find similar
sequences[25].
Textual-based approach is another major method, pioneered by
Johnson[18], and it has been used by many others[10]. NiCad usedboth text and tree-based approach to detect near-miss clones[7].
SourcererCC employed block-based matching and heuristics forfiltering out redundant comparison to scale analysis[37].
Most of these approaches focus on finding all code clone pairs
in the target file collection. They report all code clones or similarcode snippets with similarity higher than certain threshold. Precisely controlling the matches with meta-symbols like CC Matching
cannot be accomplished by those approaches.

7.3

THREAT TO VALIDITY

We have started with the issue on the current pattern matching tools
and code clone tools. For highly experienced users of those tools,
our issue might not be applicable due to their deep knowledge andskill of the tools. We are interested in an approach widely applicableto many software engineers including not highly experienced ones
for those tools. Controlled experiment and/or feedback from various
users might help to understand the issue deeply.
Our evaluation in this paper was mainly focusing on finding codesnippets with well expected and specifiable patterns, as discussed
in Sec.6.2. Experiment with broader or vaguer queries including
unspecified type 3 matching might lower performance, but wewould think that handling such queries will be a different research
topics including a different tool implementation.
Expressiveness for the specified type 3 matching might be nonexhaustive. However, as long as we have investigated the CBCD
clone data, the queries for all type 3 clones were created without
any difficulty and we strongly think that we can easily extend themto many other type 3 clones.

9

CONCLUSIONS

We have presented and formulated a new approach to find code snippets in the target files with notion of code clone and meta-pattern,
as CC matching, associated with its implementation ccgrep. It isa practical and effective pattern matching method, and the tool isefficient and easy-to-use to many software engineers.
As a future direction, we are interested in further performance
improvement by using more efficient pattern matching algorithms
as discussed in Sec.6.3. Also, we are trying to spread use of ccgrep toindustry and academia. We believe that ccgrep is a very good tool
to explore similar bugs to prevent the late propagation[4], andsome companies have already shown their interest to their industry
applications.

Code Snippet Search Tools

There are several tools specialized for finding code snippet. CBCD
has been designed for finding related code snippets from a buggy
code snippet, by using matching of Program Dependence Graph(PDG)[24]. It can be used to find type 1, 2, and 3 clones; however,
the matching generally requires long pre-processing time to construct PDG, and so this approach would not fit to the handy clone
finding that we are interested in. For example, it is reported thatpre-processing time for a part of the Linux kernel with 170K LOC
required 32 minutes, which is far slower than our approach, eventhough it is claimed that the pre-processing is a one-time overhead
and repeatedly used for many queries.
NCDSearch has been designed to find similar code snippets inthe pile of source code files for the analysis of code reuse andevolution[15]. The query and the target snippets in block level arecompressed together to see the similarity. The approach would be
unique and interesting, but the speed is slower than ours as shown
10

REFERENCES[27] Microsoft. 2013.
Finding Duplicate Code by using Code Clone Detection.
https://docs.microsoft.com/en-us/previous-versions/visualstudio/
visual-studio-2012/hh205279(v=vs.110)[28] M. Mondai, C. K. Roy, and K. A. Schneider. 2018. Micro-clones in evolving software. In 2018 IEEE 25th International Conference on Software Analysis, Evolution
and Reengineering (SANER). 50–60. https://doi.org/10.1109/SANER.2018.8330196[29] Gonzalo Navarro. 2001. A Guided Tour to Approximate String Matching. ACM
Comput. Surv. 33, 1 (March 2001), 31–88. https://doi.org/10.1145/375360.375365[30] Tung Thanh Nguyen, Hoan Anh Nguyen, Nam H. Pham, Jafar Al-Kofahi, andTien N. Nguyen. 2010. Recurring Bug Fixes in Object-oriented Programs. In
Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering - Volume 1 (ICSE ’10). ACM, New York, NY, USA, 315–324. https://doi.org/10.1145/1806799.1806847[31] Paul and Prakash. 1994. Querying Source Code Using an Algebraic Query Language. In Proceedings 1994 International Conference on Software Maintenance.
127–136. https://doi.org/10.1109/ICSM.1994.336782[32] Chaiyong Ragkhitwetsagul and Jens Krinke. 2019. Siamese: Scalable and Incremental Code Clone Search via Multiple Code Representations. Empirical Software
Engineering 24, 4 (2019), 2236–2284. https://doi.org/10.1007/s10664-019-09697-7[33] Dhavleesh Rattan, Rajesh Bhatia, and Maninder Singh. 2013. Software Clone
Detection: A Systematic Review. Information and Software Technology 55, 7 (2013),
1165–1199.
[34] Jeff Gray Robert Tairas. 2012. Increasing clone maintenance support by unifying
clone detection and refactoring activities. Information and Software Technology
54, 12 (2012), 1297–1307.
[35] Tobias Roehm, Rebecca Tiarks, Rainer Koschke, and Walid Maalej. 2012. How
Do Professional Developers Comprehend Software?. In Proceedings of the 34th International Conference on Software Engineering (ICSE ’12). IEEE Press, Piscataway,
NJ, USA, 255–265. http://dl.acm.org/citation.cfm?id=2337223.2337254[36] Chanchal K. Roy, James R. Cordy, and Rainer Koschke. 2009. Comparison
and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach. Science of Computer Programming 74, 7 (2009), 470 – 495.
https://doi.org/10.1016/j.scico.2009.02.007[37] Hitesh Sajnani, Vaibhav Saini, Jeffrey Svajlenko, Chanchal K. Roy, and Cristina V.
Lopes. 2016. SourcererCC: Scaling Code Clone Detection to Big-code. In Proceedings of the 38th International Conference on Software Engineering (ICSE ’16). ACM,
New York, NY, USA, 1157–1168. https://doi.org/10.1145/2884781.2884877[38] Janice Singer and Timothy C. Lethbridge. 1997. Whatś so Great about ‘grep’?
Implications for Program Comprehension Tools. In Tech. Rep., National ResearchCouncil, Canada.
[39] Aishwarya Sivaraman, Tianyi Zhang, Guy Van den Broeck, and Miryung Kim.
2019. Active inductive logic programming for code search. In Proceedings of the
41st International Conference on Software Engineering. IEEE Press, 292–303.
[40] William Smyth. 2003. Computing Patterns in Strings. Addison-Wesley, New York.
[41] Q. D. Soetens and S. Demeyer. 2010. Studying the Effect of Refactorings: A
Complexity Metrics Perspective. In 2010 Seventh International Conference on
the Quality of Information and Communications Technology. 313–318. https://doi.org/10.1109/QUATIC.2010.58[42] M. Storey. 2005. Theories, Methods and Tools in Program Comprehension: Past,
Present and Future. In 13th International Workshop on Program Comprehension(IWPC’05). 181–191. https://doi.org/10.1109/WPC.2005.38[43] Jeffrey Svajlenko and Chanchal K Roy. 2015. Evaluating Clone Detection Tools
with bigclonebench. In 2015 IEEE International Conference on Software Maintenance and Evolution (ICSME). IEEE, 131–140.
[44] N. Tsantalis, D. Mazinanian, and G. P. Krishnan. 2015. Assessing the Refactorability of Software Clones. IEEE Transactions on Software Engineering 41, 11 (Nov
2015), 1055–1090. https://doi.org/10.1109/TSE.2015.2448531[45] Minhaz F. Zibran and Chanchal K. Roy. 2012. IDE-based Real-Time Focused
Search for Near-Miss Clones. In Proceedings of the ACM Symposium on Applied
Computing, SAC 2012, Riva, Trento, Italy, March 26-30, 2012. 1235–1242.

[1] Tony Abou-Assaleh and Wei Ai. 2004. Survey of Global Regular Expression Print(grep) Tools. In http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.3326.
[2] Ricardo Baeza-Yates and Berthier Ribeiro-Neto. 1999. Modern Information Retrieval. ACM Press, Addison-Wesley, New York.
[3] Brenda S. Baker. 1992. A Program for Identifying Duplicated Code. Proc. ofComputing Science and Statistics: 24th Symposium on the Interface 24 (1992), 49–
57.
[4] Liliane Barbour, Foutse Khomh, and Ying Zou. 2011. Late propagation in software
clones. In 2011 27th IEEE International Conference on Software Maintenance (ICSM).
273–282. https://doi.org/10.1109/ICSM.2011.6080794[5] R. I. Bull, A. Trevors, A. J. Malton, and M. W. Godfrey. 2002. Semantic grep:
Regular Expressions + Relational Abstraction. In Ninth Working Conference on
Reverse Engineering, 2002. Proceedings. 267–276. https://doi.org/10.1109/WCRE.
2002.1173084[6] S Carter, RJ Frank, and DSW Tansley. 1993. Clone Detection in Telecommunications Software Systems: A Neural Net Approach. In Proc. Int. Workshop on
Application of Neural Networks to Telecommunications. 273–287.
[7] J. R. Cordy and C. K. Roy. 2011. The NiCad Clone Detector. In 2011 IEEE 19thInternational Conference on Program Comprehension. 219–220. https://doi.org/10.
1109/ICPC.2011.26[8] U. Dekel, T. Cohen, and S. Porat. 2003. Towards a Standard Family of Languages
for Matching Patterns in Source Code. In Proceedings 2003 Symposium on Security
and Privacy. 10–19. https://doi.org/10.1109/SWSTE.2003.1245311[9] Bogdan Dit, Meghan Revelle, Malcom Gethers, and Denys Poshyvanyk. 2013.
Feature Location in Source Code: a Taxonomy and Survey. Journal of software:
Evolution and Process 25, 1 (2013), 53–95.
[10] Stéphane Ducasse, Matthias Rieger, and Serge Demeyer. 1999. A Language
Independent Approach for Detecting Duplicated Code. In Proceedings IEEE International Conference on Software Maintenance (ICSM’99). IEEE, 109–118.
[11] Free Software Foundation. 2018. GNU Grep 3.3 Manual. https://www.gnu.org/
software/grep/manual/grep.html[12] Gnu. 2015. The GNU Awk Userś Guide. https://www.gnu.org/software/gawk/
manual/gawk.html[13] Dan Gusfield. 1997. Algorithms on Strings, Trees and Sequences. Cambridge
University Press, New York, NY.
[14] Mehran Habibi. 2004. Java Regular Expressions: Taming the Java.util.regex Engine.
Apress. https://doi.org/10.1007/978-1-4302-0709-2[15] Takashi Ishio, Naoto Maeda, Kensuke Shibuya, and Katsuro Inoue. 2018. Cloned
Buggy Code Detection in Practice Using Normalized Compression Distance. In
2018 IEEE International Conference on Software Maintenance and Evolution, ICSME
2018, Madrid, Spain, September 23-29, 2018. 591–594.
[16] Jiyong Jang, Abeer Agrawal, and David Brumley. 2012. ReDeBug: Finding Unpatched Code Clones in Entire OS Distributions. In Proceedings of the 2012 IEEE
Symposium on Security and Privacy (SP ’12). IEEE Computer Society, Washington,
DC, USA, 48–62. https://doi.org/10.1109/SP.2012.13[17] Lingxiao Jiang, Zhendong Su, and Edwin Chiu. 2007. Context-based Detectionof Clone-related Bugs. In Proceedings of the the 6th Joint Meeting of the European
Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering (ESEC-FSE ’07). ACM, New York, NY, USA, 55–64.
https://doi.org/10.1145/1287624.1287634[18] J. Howard Johnson. 1993. Identifying Redundancy in Source Code Using Fingerprints. In Proceedings of the 1993 Conference of the Centre for Advanced Studies
on Collaborative Research: Software Engineering - Volume 1 (CASCON ’93). IBM
Press, 171–183. http://dl.acm.org/citation.cfm?id=962289.962305[19] Toshihiro Kamiya. 2010. CCFinderX Manual. http://www.ccfinder.net/[20] Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue. 2002. CCFinder: A
Multilinguistic Token-Based Code Clone Detection System for Large Scale Source
Code. IEEE Trans. Software Eng. 28 (2002), 654–670.
[21] Brian W. Kernighan and Bob Pike. 1999. The Practice of Programming. AddisonWesley, Boston.
[22] Miryung Kim, Vibha Sazawal, David Notkin, and Gail Murphy. 2005. An Empirical
Study of Code Clone Genealogies. ACM SIGSOFT Software Engineering Notes 30,
5 (2005), 187–196.
[23] Rainer Koschke, Ira D. Baxter, Michael Conradt, and James R. Cordy. 2012. Software Clone Management Towards Industrial Application (Dagstuhl Seminar
12071). Dagstuhl Reports 2, 2 (2012), 21–57.
[24] J. Li and M. D. Ernst. 2012. CBCD: Cloned Buggy Code Detector. In 2012 34th
International Conference on Software Engineering (ICSE). 310–320. https://doi.
org/10.1109/ICSE.2012.6227183[25] Zhenmin Li, Shan Lu, Suvda Myagmar, and Yuanyuan Zhou. 2006. CP-Miner:
Finding Copy-Paste and Related Bugs in Large-Scale Software Code. IEEE Transactions on software Engineering 32, 3 (2006), 176–192.
[26] D. Mazinanian, N. Tsantalis, R. Stein, and Z. Valenta. 2016. JDeodorant: Clone
Refactoring. In 2016 IEEE/ACM 38th International Conference on Software Engineering Companion (ICSE-C). 613–616.

11