Master Thesis

Title

Study on Code Clone Detection and Modiﬁcation Support

Supervisor
Prof. Shinji KUSUMOTO

byTasuku Nakagawa

February 2, 2021

Departmant of Computer Science
Graduate School of Information Science and Technology
Osaka University

Master Thesis

Study on Code Clone Detection and Modiﬁcation Support
Tasuku Nakagawa

Abstract
A code clone (in short, clone) is a code fragment that is identical or similar to other code fragments in source code. The presence of clones has a negative impact on software maintenance. For
example, if a code fragment contains a bug, it is necessary to consider whether its clones should
be modiﬁed or not. Therefore, in software maintenance, clone detection techniques that automatically detect clones from the target software and clone modiﬁcation support for the developers
are important. We have conducted studies about clone detection and modiﬁcation support andproposed three techniques and systems. In this thesis, we report these studies.
First, we report a study about clone detection. Clones with a large number of edits, suchas inserting or deleting statements, are called large-variance clones. Large-variance clones havea negative impact on software maintenance as well as general clones. Hence, it is necessary todetect them as well as general clones. On the other hand, due to the recent large-scale softwaredevelopment, techniques that can detect clones from large inputs in a scalable manner are required.
However, there is no technique or tool that achieves both large-variance clone detection and highscalability. Consequently, we proposed a scalable large-variance clone detection technique andintroduced its implementation, called NIL. NIL is a token-based clone detector and uses an N-gram
representation of token sequences, an inverted index, and LCS to detect clones. Our experimental
results show that NIL has higher accuracy on large-variance clone detection than existing state-ofthe-art tools, and it is also good at scalability.
Second, we report a study about clone modiﬁcation support. Clone modiﬁcation support
for developers is important in software maintenance. An existing study proposed a system that
notiﬁes developers of clone change information to support eﬃcient clone modiﬁcation. However,
the existing system is premised on one execution a day and is not designed to be triggered byexternal factors except for time. Therefore, the system is diﬃcult to be executed triggered bydevelopment workﬂow. Consequently, we focused on a pull request (PR), a part of the development
workﬂow, and proposed CLIONE, a clone modiﬁcation system aimed to integrate into PR-based
development. CLIONE detects code fragments that need modiﬁcations by tracking clones whencreating PRs, and CLIONE also notiﬁes the developers of the code fragments as PR comments. We
evaluated CLIONE in ﬁve experiments and conﬁrmed that CLIONE was useful for supporting bothPR-based development and developers.
Finally, we report a study about clone modiﬁcation support, especially refactoring support.
An existing study proposed a technique to estimate the number of reducible lines of code (LoC)by merging clones to support clone refactoring. However, the existing technique has two issues;(1) it cannot correctly judge whether or not clones can be refactored, and (2) it cannot estimate
the number of reducible LoC about overlapping clones. Consequently, we proposed a technique tomeasure the number of reducible LoC by merging clones more correctly. The proposed techniqueautomatically repeats (1) detecting clones, (2) merging clones, and (3) compiling and testing thesource code so that the technique can measure reducible LoC on clones that can be actually mergedwith considering clone overlapping. Our experimental results showed the proposed technique wasable to measure the number of reducible LoC more correctly than the existing one.

Keywords
Code Clone
Software Maintenance
Clone Detection
Large-Variance Clone
Scalability
Clone Modiﬁcation Support
Pull Request Based Development
Refactoring
Reducible Lines of CodeContents
I

Introduction

1

1 Background2

2 Preliminaries
2.1 Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Causes of clone creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Clone detection techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Large-gap clone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Large-variance clone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Clone Notiﬁer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7 Pull request based development . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.8 Clone refactoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9 Clone overlapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10 Calculating reducible LoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
5
7
7
9
9
12
13
14
14
15

II

17

Scalable Large-Variance Clone Detection

1 Background18

2 Approach
2.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Clone detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Location phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Filtration phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Veriﬁcation phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20
20
21
22
23
23

3 Evaluation
3.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Large-variance clone detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Precision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Recall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 General clone detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Mutation Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 BigCloneEval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26
26
27
29
29
30
32
32
32
33

4 Threats to Validity

35i5 Related Works
5.1 Complicated Type-3 clone detection . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Scalable clone detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36
36
36

6 Conclusion

38

III Clone Modiﬁcation Support for Pull Request Based Development
39
1 Background40

2 Research Motivation42

3 Proposed System: CLIONE
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Improvements of clone tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Code fragment tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 File rename detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Clone change judgment by comparing token sequences . . . . . . . . . . . .

43
43
44
44
45
45

4 Evaluation
4.1 Experiment 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Experiment 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Experiment 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Experiment 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Experiment 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48
48
49
50
50
53

5 Threats to Validity

55

6 Related Works
6.1 PR-based development support system . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Clone modiﬁcation support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56
56
56

7 Conclusion

57

IV Measurement Reducible Lines of Code Based on Automated Merging Clones
58
1 Background59

2 Proposed Technique
2.1 Preprocessing source ﬁle changes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Clone merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61
62
62

ii

3 Implementation
3.1 Preprocessing source ﬁle changes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Generating a new Java class . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Initializing local variables . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Reformatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Clone merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Step 1: Detecting clone sets . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Step 2: Editing source ﬁles . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Step 3: Compiling and testing edited source ﬁles . . . . . . . . . . . . . . .
3.2.4 Step 4: Selecting edited source ﬁles . . . . . . . . . . . . . . . . . . . . . . .

63
63
63
63
63
63
63
65
66
67

4 Experiment68
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.1 Comparison with the existing technique . . . . . . . . . . . . . . . . . . . . 68
4.2.2 Investigation of diﬀerences in clone sets targeted to merge by each technique 71
5 Limitations
5.1 Limitations in executing the proposed technique . . . . . . . . . . . . . . . . . . .
5.1.1 Limitations in the execution environment . . . . . . . . . . . . . . . . . . .
5.1.2 Limitations in the execution time . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Limitations in the implementation . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 All extracted methods are declared in one class . . . . . . . . . . . . . . . .
5.2.2 Clones are detected block by block . . . . . . . . . . . . . . . . . . . . . . .
5.2.3 Code fragments that contain return statements are not detected as clones .
5.2.4 Arguments are passed by reference to the extracted method . . . . . . . . .

75
75
75
75
75
75
76
76
76

6 Conclusion

77

Acknowledgements

78

References

79

Appendix89

A Available ﬁles90

B Hunt-Szymanski Algorithm

91

C List of Publications

92

iii

List of Figures
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

26

Examples of clone types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Examples of Type-3 clones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of large-gap clones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of large-variance clones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Relation among clone types and target clone types for several tools . . . . . . . . .
Example of clone tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of extract method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Clone overlapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Overview of NIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of generating 3-grams . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Concept of partial inverted indexes . . . . . . . . . . . . . . . . . . . . . . . . . . .
Recall results for various numbers of inserted lines . . . . . . . . . . . . . . . . . .
Growth in the number of clone candidates with the increased number of code blocks
Two methods in JRuby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Overview of CLIONE. Blue lines means processes CLIONE performs. . . . . . . . .
Example of comment about a non-simultaneously modiﬁed clone sets . . . . . . . .
Improvement of clone tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Overview of proposed technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Diﬀerent reducible LoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Clone detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Editing source ﬁles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Venn diagram representing clone sets that are targeted to merge by the proposed
technique and/or the existing one . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of a clone that was actually refactorable, but the existing technique did ottarget to merge because the variables in the clones were ﬁeld variables . . . . . . .
Example of a clone that the existing technique did not target to merge because ofoverlapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of a clone that was actually not refactorable because of the type of the variable between the clones has no inheritance relationship, but hte existing techniquetargeted to merge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Example of a clone that was actually refactorable, but the proposed technique did
not target to merge because our implementation are insuﬃcient . . . . . . . . . . .

iv

5
6
10
11
12
13
14
15
20
21
22
31
34
42
43
46
47
61
64
65
66
71
72
73

74
74

List of Tables
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Settings for various clone detectors . . . . . . . . . . . . . . . . . . . . . . . . . . .
Recall and execution time results for each N value . . . . . . . . . . . . . . . . . .
Target systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Large-variance clone detection results . . . . . . . . . . . . . . . . . . . . . . . . .
Recall results for Mutation Framework . . . . . . . . . . . . . . . . . . . . . . . . .
Recall and precision results for BigCloneBench . . . . . . . . . . . . . . . . . . . .
Scalability results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Target OSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Results of experiment 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Response times of each PR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Breakdowns of improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
List of created PRs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Questionnaire target PRs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Experimental targets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Results of comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The number of CS 1 and CS 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

v

26
28
29
30
32
33
33
48
48
49
50
52
53
68
70
72

Part I

Introduction1

1

Background
Software development consists of the following ﬁve phases [1].
• Requirement phase• Design phase• Implementation phase• Testing phase• Maintenance phase

It has been said that the maintenance phase is the most expensive [2,3]. Maintenance of softwaresystems is deﬁned as modifying a software product after its delivery to correct faults, improve theperformance or other attributes, or adapt the software to a modiﬁed environment [4,5]. According
to literature [6], approximately 80% of the total cost is spent on software maintenance. To modify
software products, modifying the source code is unavoidable. Therefore, in order to support sourcecode modiﬁcation in software maintenance, many studies, such as automated program repair [7,8],
fault localization [9, 10], fault prediction [11, 12], refactoring [13, 14], and program slicing [15, 16],
have been conducted. In addition, the presence of code clones has been pointed out as one of thefactors that make software maintenance diﬃcult [17].
A code clone (in short, clone) is a code fragment identical or similar to other code fragments
in source code. Clones are generated for various reasons, such as copy-and-paste operations.
If a code fragment contains a bug and needs a modiﬁcation, we have to consider whether its
clones need the same modiﬁcation or not. Hence, software containing many clones is diﬃcult tomaintain [18]. Therefore, many studies about clones have been conducted to support software
maintenance. Among them, we considered that the following two research areas are particularly
important; clone detection and clone modiﬁcation support.
Clone detection
It is not realistic to manually compare a large number of code fragments in software to judge
whether they are clones or not. Therefore, many studies to automatically detect clones fromthe target software have been conducted [19–22]. Some clones are easy to detect, such as
simple copies, while others require special techniques for detection, such as code fragmentsthat are semantically similar but not syntactically similar. In addition, due to recent largescale software development, scalable clone detection techniques are required [23]. In software
maintenance, it is an important issue to propose techniques that can detect clones diﬃcult
to detect in a scalable manner.
Clone modiﬁcation support
Developers modify clones as needed, such as simultaneous clone modiﬁcation [24] or clone
refactoring [25]. Simultaneous clone modiﬁcation is modifying clones consistently at the sametime. Refactoring is improving the internal structure of software without changing its external
behavior [26]. Especially, clone refactoring is merging clones into a single module, such as amethod or a class. In software maintenance, it is an important issue to automatically detect2

clone changes and provide them for the developers to improve the developers’ eﬃciency ofthese tasks. Besides, refactoring changes source code that is working ﬁne, and there is apossibility that refactoring itself introduces a new bug into the source code [27]. Therefore,
developers need a reasonable indicator to refactor source code. In software maintenance, it
is also an important issue to provide the indicator for the developers.
For these issues, we have conducted three studies. In this thesis, we report the results.
First, in Part II, we report a study about scalable large-variance clone detection. A largevariance clone is a clone generated by inserting or deleting a large number of statements inscattered places in a copy-and-pasted code fragment. Most of the existing tools are aimed at
detection strongly similar clones and suﬀer in large-variance clone detection. On the other hand,the scalability of existing techniques that are specialized to detect large-variance clones is limited. Consequently, we proposed a scalable large-variance clone detection technique. The proposed
technique is token-based. Based on a feature of large-variance clones, the proposed technique detects large-variance clones by measuring the similarity from the LCS between token sequences of
two code fragments. Moreover, based on another feature of large-variance clones, the proposed
technique also achieves scalable clone detection by identifying clone candidates using N-gram representation of token sequences and an inverted index. We implemented the proposed technique as asoftware tool, NIL. We compared NIL with four state-of-the-art clone detectors, including existinglarge-variance clone detectors. The results show NIL has high accuracy on large-variance clone
detection, high scalability, and equivalent accuracy on general Type-1, Type-2, and Type-3 clone
detection.
Next, in Part III, we report a study about a clone modiﬁcation support system aimed to integrate into pull request (in short, PR) based development [28]. An existing study proposed asystem, Clone Notiﬁer, which supports developers to conduct simultaneous clone modiﬁcation andclone refactoring by regularly notifying them of clone change information of a target project [29].
However, Clone Notiﬁer is premised on one execution a day and is not designed to be triggered byexternal factors except for time [30, 31]. Therefore, the system is diﬃcult to be executed triggered
by development workﬂow, such as modifying source code or merging branches. Consequently, we
focused on a PR, a part of the development workﬂow, and proposed CLIONE, a clone modiﬁcation
support system aimed to integrate into PR-based development. When developers create a PR,
CLIONE notiﬁes code fragments that need modiﬁcations by tracking clones between the PR and
detecting clone changes. We evaluated the usefulness of CLIONE in ﬁve experiments. The experimental results show that CLIONE is useful to support PR-based development and developers.
Finally, in Part IV, we report a study about an indicator for refactoring [32]. An existing
study proposed to use the number of reducible lines of code (in short, LoC) by merging clones
as an indicator to refactor clones [33]. In addition, the existing study proposed a technique toestimate the number of the reducible LoC using JDeodorant [34], which judges whether clones canbe refactored or not, and a greedy algorithm that was proposed in an existing study [35]. However,since JDeodorant, which is used in the existing technique, does not actually merge clones, it cannot
correctly judge whether clones can be refactored or not. Moreover, the greedy algorithm cannot
measure the reducible LoC from overlapped clones. Therefore, we considered that the existing
technique cannot estimate the number of the reducible LoC correctly. Consequently, we proposeda technique to measure the number of the reducible LoC more correctly. The proposed technique3

automatically repeats (1) detecting clones, (2) merging clones, and (3) compiling and testing thesource code. We experimented to apply the proposed technique to several Java projects. We
also compared the number of reducible LoC the proposed techniques measure with the existing
technique’s ones. As a result, we conﬁrmed that the proposed technique was able to measure
reducible LoC more correctly than the existing technique.

4if (x > y) {int tmp = y;y = x;
x = tmp;}if (x > y)
{ // swap
int tmp = y;y = x;
x = tmp;}Type-1

if (a > b) {int temp = b;b = a;
a = temp;}

if (x > y) {print("swap");
int tmp = y;y = x;
x = tmp;}Type-2Type-3if (x > y) {x ^= y;y ^= x;x ^= y;}Type-4

Figure 1: Examples of clone types

2

Preliminaries

2.1

Deﬁnition

A code fragment is a consecutive segment of source code. It can be represented by the tuple(f ile name, start line, end line). A code block is a code fragment within braces. This study treatsa function, which is a code block, as a clone detection unit, as done in previous studies [23, 36, 37].
Clones are code fragments identical or similar to other code fragments in source code. A pairof similar code fragments is called a clone pair. Clones are classiﬁed based on the degree of thesimilarity between them as follows.
Type-1 is an exact copy without modiﬁcations (except for white space and comments).
Type-2 is a syntactically identical copy; only variable, types, or function identiﬁers were changed.
Type-3 is a copy with further modiﬁcations; statements were changed, added, or removed.
Type-4 is a code fragment with not syntactical similarity but semantic similarity.
Figure 1 shows examples of clone types. Moreover, Type-3 clones are classiﬁed based on the degreeof the similarity after pretty-printing and identiﬁer/literal normalization as follows.
Very Strongly Type-3 is a Type3 clone whose similarity is in range [90, 100).
Strongly Type-3 is a Type3 clone whose similarity is in range [70, 90).
Moderately Type-3 is a Type3 clone whose similarity is in range [50, 70).
Weakly Type-3 is a Type3 clone whose similarity is in range [0, 50).

5String sequence(int start, int stop) {StringBuilder b = new StringBuilder();
int i = start;
while (i <= stop) {if (i > start) b.append(',');
b.append(i);i++;}return b.toString();}

Very Strongly Type-3

Strongly Type-3

Moderately Type-3

Weakly Type-3

String sequence(int start, int stop) {StringBuilder b = new StringBuilder();for (int i = start; i<= stop; i++) {if (i > start) b.append(',');
b.append(i);}return b.toString();}
String sequence(int start, int stop) {StringBuilder b = new StringBuilder();String sep = ',';for (int i = start; i<= stop; i++) {if (i > start) b.append(sep);b.append(i);}return b.toString();}
String sequence(int start, int stop) {String sep = ',';
String result = Integer.toString(start);for (int i = start + 1; ; i++) {if (i > start) b.append(sep);
result = String.join(sep, result,Integer.toString(i));}
return result;}
String sequence(int b, int e, String s) {String result = Integer.toString(b);for (int n = b + 1; ; n++) {if (e < n) break;result = String.join(sep, result,Integer.toString(n));}
return result;}

Figure 2: Examples of Type-3 clones

6

Figure 2 shows examples of these Type-3 clones.
The minimum length of clones is the minimum number of lines that a code fragment must be
to be treated as a clone. It is often set to six lines or 50 tokens [19].
2.2

Causes of clone creation
Clones can be created or introduced in the following situations.

Copy-and-paste operations This is the most prevalent situation in which clones are created.
Reusing code by copy-and-paste operations is common in software development because it isquite easy and enables us to develop software faster.
Stylized processing Processing used frequently (e.g., calculations of income tax, insertions inqueues, and access to data structures) may cause code duplications.
Lack of suitable functions Developers may have to write similar processes with similar algorithms if they use programming languages that do not have abstract data types or local
variables.
Performance improvement Developers can intentionally introduce code duplication to improve
the performance of software systems if in-line expansion is not supported.
Automatically generated code Code generation tools automatically create code based on stylized code. As a result, if we use code generation tools to handle similar processes, the tools
may generate similar code fragments.
Handling multiple platforms Software systems that can handle multiple operating systems orCPUs tend to include many clones in each platform’s process handling.
Accident Diﬀerent developers may write similar code accidentally. However, it is rare the amountof similar code generated accidentally becomes high.
2.3

Clone detection techniques

Clones have a negative impact on software maintenance. Many clone detection techniques andtools have been proposed and developed. Clone detection techniques can be categorized into thefollowing categories.
Line-based techniques
Line-based techniques detect clones by comparing every line of code fragments as a string.
They regard multiple consecutive lines that exceed a speciﬁed threshold as clones. Line-based
techniques can detect clones quickly compared with other detection techniques because they
do not require any preprocessing of the source code. However, they cannot detect clones thathave diﬀerent coding styles.
The techniques of Johnson [38] and Ducasse [39] are well-known line-based techniques. Theirtechniques compare every line of code after removing white space, tabs, and line breaks.
Thus, they detect clones that have diﬀerent coding styles and are language-independent.
Simian is one of the most famous and commonly used line-based clone detectors [40]. Simian7

can handle about 20 programming languages (e.g., Java, C, and C++) and quickly detectclones.
Token-based techniques
First, token-based techniques transform source code into a token sequence. Then, they detect common sub-sequences of the tokens are clones. Compared to line-based techniques,
token-based techniques are robust for code formatting. The detection speed of token-based
techniques is inferior to that of line-based techniques. However, superior to the tree-basedor graph-based techniques discussed below.
Kamiya et al. developed a token-based clone detector, named CCFinder [41], that is wellknown and has been widely used by many developers. It replaces user-deﬁned identiﬁers(e.g., method or variable names) with speciﬁc tokens. By preprocessing, CCFinder can detect
Type-2 clones.
Li developed a token-based clone detector, named CP-Miner [42]. First, lexical and syntax
analyses are performed on the source code. User-deﬁned identiﬁers are replaced with speciﬁc
tokens, as in CCFinder. The major diﬀerence between CP-Miner and CCFinder is the detection
algorithms. In CP-Miner, hash values are calculated from every statement, and then a frequent pattern mining algorithm [43] is applied for detecting clones. In the frequent patternmining algorithm, the hash values do not have to be consecutive. Thus, CP-Miner can detect
Type-3 clones.
Tree-based techniques
In tree-based techniques, source code is transformed into a tree representation. Abstract
syntax tree (AST) is one of the well-known tree representations. Tree-based techniques regard common sub-trees as clones, and thus these techniques also robust for code formatting.
However, they have the disadvantages of requiring for detecting clones than do line-based
and token-based techniques.
Baxter developed a tree-based clone detector, named CloneDR [44], which calculates various
metrics based on ASTs and then detects clones by comparing metrics. Thus, CloneDR detects clones quickly in large software systems. CloneDR can also handle a lot of programming
languages.
Koschke’s technique [45] and Jiang’s technique [46] are also tree-based approaches. In
Koschke’s technique, ASTs compared with a suﬃx tree algorithm to reduce the detection
speed. Jiang’s detector, named DECKARD, uses a locality-sensitive hashing algorithm [47]to detect clones. With the algorithm, DECKARD can detect Type-3 clones.
Graph-based techniques
In graph-based techniques, source code is transformed into a graph representation. Program
dependence graph (PDG), one of the well-known graph representations, has data-dependenceedges and control-dependence edges for each source code element. Graph-based techniques
regard isomorphic sub-graph as clones. Because PDGs require a semantic analysis for theircreation, these approaches require much more cost than other detection techniques. However,these approaches can detect clones with some diﬀerences that have no impact on the program behavior. Komondoor proposed the initial graph-based technique [48]. Komondoor’s
technique uses program slicing [15] to ﬁnd isomorphic sub-graphs.
8

Krinke’s technique [49] and Higo’s technique [50] are also classiﬁed as graph-based techniques.
Both of these techniques are designed to reduce detection cost. Krinke’s technique sets thelimit of the search range for ﬁnding isomorphic sub-graphs. Higo proposed a technique that
aggregates nodes in PDGs under some conditions. Moreover, he introduced a new dependenceedge named execution dependence edge for PDGs. By introducing the execution dependenceedge, Higo’s technique successfully detected clones that other graph-based techniques could
not detect.
Text-based techniques
Text-based technique ﬁrstly normalizes the target source code and detects clones by comparing code fragments, such as methods or code blocks in the normalized source code.
NiCad [51] is a well-known text-based clone detection tool. First, it normalizes source codeusing TXL [52] and then detects clones by comparing code fragments based on Longest Common Subsequence algorithm. Moreover, text-based technique is used for detection clones
generated by inserting or deleting a large number of statements in a copy-and-pasted codefragment. CCAligner [36] and LVMapper [37] also use TXL and detect such clones based on
their own algorithms.
2.4

Large-gap clone

A large-gap clone is a clone generated by inserting or deleting a large number of statements
in one place in a copy-and-pasted code fragment. Figure 3 shows an example of large-gap clones.
In this example, a 10-line if-statement is inserted into Clone A (lines 4–13 of Clone B). Wang etal. [36] pointed out that existing clone detectors are incapable of large-gap clone detection because
most target to the detection of near-miss clones. Wang et al. deﬁned large-gap clone as follows.
Consider two code blocks c1 and c2 with LOC values of L1 and L2 , respectively, where L1 ≤ L2 .
Let λ = Li /Lj (i.e., λ is the ratio of the code lengths of two code blocks). If c1 and c2 are Type-3
clones and the corresponding λ ≤ 0.7, then these clones are large-gap clones. The clone pair shownin Figure 3 ﬁts the deﬁnition of large-gap clones because the ratio of the code lengths of Clone A
and Clone B is 12/22 ≃ 0.55 < 0.7.
Wang et al. proposed CCAligner [36], a large-gap clone detector. CCAligner detects clones usinga code window (a code fragment composed of k consecutive lines in a code block). First, CCAlignertransforms code blocks into code windows. Then, it identiﬁes clone candidates as pairs of code
blocks that share at least one code window with considering e edit distance. Finally, it veriﬁes
clone candidates based on their similarity, which is calculated as follows:sim(c1 , c2 ) =|Wc1 ∩ Wc2 |min(|Wc1 |, |Wc2 |)where c1 and c2 are two code blocks, and Wc1 and Wc2 are the corresponding sets of code windows,
respectively.
2.5

Large-variance clone

A large-variance clone is a clone generated by inserting or deleting a large number of statements
in various places in a copy-and-pasted code fragment. Figure 12 shows an example of large-variance9

1 protected int run(Commandline cmd) {
2
try {
3
Execute exe = new Execute(new LogStreamHandler(this,Project.MSG_INFO, Project.MSG_WARN);
4
exe.setAntRun(getProject());
5exe.setWorkingDirectory(getProject().getBaseDir());
6
exe.setCommandline(cmd.getCommandline);7
exe.setVMLauncher(false);
8
return exe.execute();9} catch (java.io.IOException e) {10throw new BuildException(e, getLocation());
11
}
12 }
(a) Clone A

1 protected int run(Commandline cmd) {
2
try {
3
Execute exe = new Execute(new LogStreamHandler(this,Project.MSG_INFO, Project.MSG_WARN);
4
if (serverPath != null) {5String[] env = exe.getEnvironment();6
if (env == null) {7
env = new String[0];8}9String[] newEnv = new String[env.length + 1];
10
System.arrayCopy(env, 0, newEnv, 0, env.length);11
newEnv[env.length] = "SSDIR=" + serverPath;12
exe.setEnvironment(newEnv);
13}
14
exe.setAntRun(getProject());
15
exe.setWorkingDirectory(getProject().getBaseDir());
16
exe.setCommandline(cmd.getCommandline);17
exe.setVMLauncher(false);
18
return exe.execute();19} catch (java.io.IOException e) {20
throw new BuildException(e, getLocation());
21
}
22 }
(b) Clone B

Figure 3: Example of large-gap clones

10

1 protected String getPrompt(InputRequest request) {2
String prompt = request.getPrompt();3
if (request instanceof MultipleChoiceInputRequest) {4
StringBuffer sb = new StringBuffer(prompt);
5
sb.append("(");
6
Enumeration e = ((MultipleChoiceInputRequest) request).getChoices().elements();
7boolean first = true;
8
while (e.hasMoreElements()) {9if (!first) {10
sb.append(",");
11}
12
sb.append(e.nextElement());
13
first = false;
14}
15
sb.append(")");
16
prompt = sb.toString();
17}
18
return prompt;
19 }(a) Clone A
1 protected String getPrompt(InputRequest request) {2
String prompt = request.getPrompt();3
String def = request.getDefaultValue();4
if (request instanceOf MultipleInputChoiceRequest) {5
StringBuilder sb = new StringBuilder(prompt).append("(");
6boolean first = true;7for (String next : ((MultipleInputChoiceRequest) request).getChoices()) {8
if (!first) {9
sb.append(",");
10}
11
if (next.equals(def)) {12
sb.append('|');
13}
14
sb.append(next);
15
if (next.equals(def)) {16
ab.append('|');
17}
18
first = false;
19}
20
sb.append(")");
21
return sb.toString();22}
23else if (def != null) {24
return prompt + "[" + def + "]";
25}
26
else {
27
return prompt;
28
}
29 }

(b) Clone B

Figure 4: Example of large-variance clones

11Large-gap clones

CCAligner

Large-variance clones

LVMapper&
NIL

Type-3 clones
All clones

Figure 5: Relation among clone types and target clone types for several tools

clones. In this example, statements have been inserted into and deleted from various places in Clone
A to create Clone B. Wu et al. [37] pointed out that CCAligner targets the detection of large-gap
clones, making it incapable of large-variance clone detection. Wu et al. deﬁned large-varianceclones as clones whose code length ratio is less than 0.7. This means that large-gap clones are a
special case of large-variance clones. They proposed LVMapper, a large-variance clone detector.
Figure 5 shows that the relation among clone types and the clone types targeted by CCAligner,
LVMapper, and NIL. CCAligner targets large-gap clones, whereas LVMapper and NIL target largevariance clones, which include large-gap clones.
LVMapper detects clones using code windows, just like CCAligner. Its clone detection has
three phases, namely the locating, ﬁltering and verifying phases. In the locating phase, LVMapper
identiﬁes pairs of code blocks that share at least one code window as clone candidates. Then, inthe ﬁltering phase, it calculates the proportions of common code windows for each clone candidate
and removes clone candidates whose proportions are lower than ﬁltering threshold θ. Finally, inthe verifying phase, it veriﬁes each clone candidate based on similarity measured using a common
subsequence of lines between each clone candidate’s code block pair.
2.6

Clone Notiﬁer

Tokui et al. developed a tool, Clone Notiﬁer, which supports developers to modify clones [29].
Clone Notiﬁer takes two versions of a project as inputs, and based on the changes of the sourcecode between the two versions, it classiﬁes all clone sets detected in each version under following
four categories.
Stable Clone set whose all clones have not been changed.
Changed Clone set whose some or all clones have been changed between the versions.
New Clone set whose all clones were added in the new version.
Deleted Clone set whose all clones were deleted in the old version.
12

Old version

New version…
10
11
12 void main() {13 int a = 0;
14 String c = "";
15 }
…

…
10
11 void main() {12 int a = 1;
13 String c = "";14 char e = '';15 }…

𝑜𝑠 = 12 − 1 = 11𝑜𝑒 = 15 − 2 = 13

𝑛𝑠 = 11
𝑛𝑒 = 15 − 2 = 13
Figure 6: Example of clone tracking

First, Clone Notiﬁer detects clones from each revision by using existing clone detectors [23,41,53].
Next, it tracks detected clones using location overlaping function, which an existing study [54]proposed.
Location overlapping function measures how much two code fragments cf 1 and cf 2 overlap
each other (0 ≤ LO(cf 1, cf 2) ≤ 1). Clone Notiﬁer uses the diﬀerence between the same ﬁle in eachversion, without the added and deleted lines. It computes the relative proportion of an overlapped
region between cf 1 and the calibrated cf 2.
min(ne , oe ) − max(ns , os )(1)ne − ns
where cf 1 in the old version spans from the line os to the line oe , and the calibrated location of
cf 2 in the new version spans from the line ns to the line ne . If the location overlapping between
the two clones is 0.3 or more, Clone Notiﬁer tracks from the clone at the old version to the clone
at the new version.
Figure 6 shows an example of clone tracking. In the ﬁgure, main method is tracked. In theold version, there are one and two deleted lines up to the start and end lines of main method,respectively. In the new version, there are zero and two added lines up to the start and end linesof main method, respectively. Therefore, based on os = 12 − 1 = 11, oe = 15 − 2 = 13, ns = 11,
and ne = 15 − 2 = 13, the result of location overlapping ﬁltering is 1, and the method tracking
succeeds.
Finally, Clone Notiﬁer classiﬁes clone sets under four categories (i.e., Stable, Changed, Added,
and Deleted ) from the results of clone tracking. Clone Notiﬁer is designed to be premised on regular
execution (e.g., once a day) [30].
LO(cf 1, cf 2) =2.7

Pull request based development

PR-based development is a development process using pull request (PR), which is one of thefeatures of GitHub. PR is a feature that notiﬁes developers of development information, such13

void printTaxi(amount) {String name = getTaxiName();void printTaxi(amount) {String name = getTaxiName();printFare(name, amount);}

print("name: " + name);print("amount: " + amount);}

void printBus(amount){
String name = getBusName();printFare(name, amount);}

void printBus(amount){
String name = getBusName();print("name: " + name);print("amount: " + amount);

void printFare(name, amount){
print("name: " + name);print("amount: " + amount);}}

Figure 7: Example of extract method

as source code changes before a branch is merged into another one. In PR-based development,
the developers make source code edits, such as adding features, refactoring, bug ﬁx on not themain branch but topic branches. Once the assigned work is done, the developer creates a PR
and notify other developers of the change information, and if the changes have no problems, thetopic branch is merged to the main branch. PR-based development is widely adopted by OSS
development [55–57].
2.8

Clone refactoring

Refactoring is known as a promising technique to improve the internal structure of source code
without changing its external behavior [26]. Duplicated code (clones) is one of the typical bad
smells (code to be refactored). There are a variety of ways to refactor (merge) clones [25, 58, 59].
Extract Method refactoring is a simple yet well-known technique to remove clones. The original
purpose of this refactoring pattern simpliﬁes a long and/or complicated method by extracting apart of it as a new method. However, by applying Extract Method refactoring to clones, they canbe removed. Figure 7 shows a simple example of Extract Method refactoring to two duplicatedcode fragments. Clones can be merged by extracting a clone set as a method. As a result, thenumber of potential bugs ans LoC can be reduced.
2.9

Clone overlapping

In this thesis, when two or more clones share one or more tokens, we say that “the clones areoverlapped with each other ”. Figure 8(a) shows an example of overlapped clones. In this ﬁgure,clone A includes clone B. In clone refactoring, it may not be possible to refactor both of twoclones overlapped with each other at the same time. Thus, when clones are overlapped like thisﬁgure, we need to do special care to estimate reducible LoC. For example, the existing techniquein literature [35] estimates reducible LoC in the case of removing clone A and in case of removing
clone B separately, and then remove only either A or B, whose reducible LoC is larger than theother. Literature [35] also proposes a more aggressive approach, which is shown in Figure 8(c).

14Clone A
Clone B

File A

File B

File C(a) Overlapped clones

Clone A
Clone B

File A

File B

File C(b) Merging either one

Clone A'
Clone B

File A

File B

File C

Clone C(c) Dividing clones

Figure 8: Clone overlapping

In this approach, the overlapped parts and the non-overlapped parts are separately considered forrefactoring.
2.10

Calculating reducible LoC

Herein, we introduce the deﬁnition of reducible LoC, which is proposed in the existing technique [35]. Herein, we assume that a clone set includes n code fragments, and each code fragment
consists of Csize LoC. In a refactoring of merging the clone set, each clone is replaced with a method
invocation, which is usually 1-line code. Consequently, reducible LoC Call can be represented withthe following formula.
Call = n ∗ Csize − n(2)In the case of Java, there is a 1-line code of method signature and open bracket “{” before amethod body, and there is another 1-line code of close bracket “}”. Thus, the LoC of a method
becomes LoC of the method body plus two. An extracted code fragment (a clone) becomes a15

body of the new method. Consequently, LoC of the extracted method can be represented with thefollowing formula.
M = Csize + 2(3)

By using the two formula 2 and 3, the LoC diﬀerence between the original code and refactoredcode can be represented with the following formula.
S = Call − M = (n − 1) ∗ Csize − n − 2(4)

In the existing technique [33], the above formula is used to estimate reducible LoC by removing
clones.

16Part II

Scalable Large-Variance Clone Detection17

1

BackgroundA code clone (in short, clone) is a code fragment that is identical or similar to other codefragments in source code. Clones are generated by copying, pasting, and modifying code fragments
for reuse [20, 60]. Clones are a major problem in software maintenance because they lead to bug
propagation. Therefore, clone detection techniques, which automatically detect clones in the target
codebase, are essential. Many clone detection techniques have been proposed [19, 21, 61], andapplied in applications [62], such as refactoring [25, 58, 63, 64], debugging [42, 65, 66], and mining
software repositories [67–69].
It is important for clone detection techniques to detect clones that have been heavily edited. A
clone generated by inserting or deleting a large number of statements in one place in a copy-andpasted code fragment is called a large-gap clone. Such clones are common in software development
and should thus be detected along with general clones. Wang et al. pointed out that it is diﬃcult
for existing clone detectors to detect large-gap clones; they proposed a technique for detecting
such clones and presented its implementation, called CCAligner [36]. Wu et al. pointed out that
CCAligner targets only clones in which statement insertion or deletion is made in a single placeand cannot detect clones in which modiﬁcations are scattered [37]. They called the latter type ofclone large-variance clones and proposed LVMapper, a clone detector for large-variance clones.
It is also important for clone detection techniques to be scalable. Highly scalable clone detectors are required for analyzing large-scale projects or source ﬁles in an inter-project repository.
Many scalable clone detectors have been proposed [23, 70, 71]. To achieve scalable clone detection,
SourcererCC [23] and CloneWorks [70] use heuristics to reduce the number of code block comparisonsneeded to detect clones, and SAGA [71] uses a GPU to parallelize its clone detection process.
However, clone detectors that can detect clones with a large number of edits fail for large
inputs [36] or require a long time to detect clones [37]. Scalable clone detectors target only identicalor strongly similar clones (near-miss clones). They are incapable of detecting large-variance clones,in which many statements have been inserted or deleted. Therefore, the scalable detection of largevariance clones is challenging.
In this part, we propose a scalable technique for detecting large-variance clones and describe
its implementation, called NIL1 , which uses an N-gram representation, an inverted index, and thelongest common subsequence (LCS). NIL is a token-based clone detector. One of the features oflarge-variance clones is that the order of many tokens is preserved (i.e., the common subsequence
between token sequences of large-variance clones is long). Hence, to detect large-variance clones,
NIL measures the similarity between the token sequences of two code fragments based on the
LCS. In addition, large-variance clones share many consecutive tokens. Hence, for scalable clone
detection, NIL uses an N-gram representation of token sequences and an inverted index to reduce
the number of code block comparisons needed to detect clones. First, NIL transforms code blocks
extracted from source ﬁles into token sequences and creates an inverted index from the N-gram
representation of the token sequences. Next, it identiﬁes the clone candidates for each code blockusing the code block and the inverted index. Finally, it veriﬁes the clone candidates by measuring
the similarity between the code block and the clone candidates.
We evaluate NIL’s (1) large-variance clone detection accuracy, (2) general Type-1, Type-2,
1 A clone detector using N-gram, Inverted index, and LCS.

18

and Type-3 clone detection accuracy, and (3) scalability. We compared NIL with existing stateof-the-art tools, namely LVMapper [37], CCAligner [36], SourcererCC [23], and NiCad [51]. The
experimental results show that NIL has a high precision of 87% in large-variance clone detection.
It also has a high recall of 100%, as determined in our evaluation of large-variance clone detection
using a mutation technique. In general clone detection, the accuracy of NIL is equivalent to thatof the existing tools. In addition, we conﬁrmed that NIL has high scalability; it can detect clones
faster than the existing tools for large inputs (codebases with 250 MLOC).
The main contributions of this part are as follows.
1. We proposed a scalable technique for detecting large-variance clones. The proposed technique
identiﬁes clone candidates eﬃciently by using an N-gram representation of token sequences
and an inverted index, and veriﬁes clone candidates precisely by measuring the similarity
between token sequences based on the LCS.
2. We implemented the proposed technique as a tool, called NIL. The executable ﬁle is available
at https://zenodo.org/record/4492665.
3. We evaluated the usefulness of NIL through three experiments. The results show that NIL has
high large-variance clone detection accuracy, high scalability, and equivalent general clone
detection accuracy compared to that of existing state-of-the-art tools. We have published
our experiment data to facilitate replication studies.

19Sourcecode

Extract&
Tokenize

Tokenized
code block

Generate
N-grams

CreateN-grams
N-grams
N-grams

Inverted
Index

Preprocessing

Select eachcode block
Tokenized
code block

Generate
N-grams

N-grams
Locate&FilterVerifyClone pair

Clone detection

Clone
candidate

Figure 9: Overview of NIL

2Approach

Figure 9 shows an overview of the proposed technique. The input is a set of source code ﬁles,and the output is the clone pairs in the source code. In the proposed technique, large-varianceclones are detected based on the similarity between token sequences based on the LCS, taking
advantage of the fact that the order of many tokens in a large-variance clone pair is preserved. In
addition, large-variance clones share many consecutive tokens. Hence, to achieve scalable largevariance clone detection, the proposed technique reduces the number of code block comparisons byusing an N-gram representation of token sequences and an inverted index. The proposed techniquetransforms code blocks in source code into token sequences in the Preprocessing phase and detects
clones by comparing the token sequences in the Clone detection phase. In this part, we implemented
the proposed technique as a tool, called NIL. NIL is written in the Kotlin language and currently
targets only Java source code. The following subsections describe the Preprocessing and Clone
detection phases.
2.1

Preprocessing

In the Preprocessing phase, NIL extracts code blocks from the target source code and transforms them into token sequences. NIL does not perform lexical analysis but simply divide eachcode block’s text based on symbols (e.g., “+”, “−”, or braces), white spaces, or newlines, as doneby SourcererCC. For example, when the code block shown in ﬁgure 4(a) is transformed into thetoken sequence, protected, String, getPrompt, InputRequest, request, .... With this transformation, lexical analyzers for other languages do not need to be implemented to extend NIL. The
token sequence transformation is fast because lexical analysis is not necessary. In addition, NIL
has a relatively low rate of false positives because it does not normalize identiﬁers, such as variable
and function names. However, it may not detect clones whose identiﬁers have been changed (i.e.,
Type-2 clones). We discuss the impact of the lack of identiﬁer normalization in Section 3.
Next, NIL generates N-grams from each token sequence. An N-gram is a chunk of consecutive
N tokens [72]. Figure 10 shows an example of generating 3-grams from the code block shown20

protected String getPrompt(InputRequest request) {Source code

Split
protected String getPrompt InputRequest request

Token sequence

Generate 3-grams
protected String getPrompt
protected String getPrompt InputRequest
protected

3-grams

getPrompt InputRequest request
Figure 10: Example of generating 3-grams

in ﬁgure 4(a). In this example, three 3-grams are generated from the ﬁve tokens of on the ﬁrst
line in the code block. Even though large-variance clones include many modiﬁcations (statement
insertions and deletions), many tokens other than the statements match consecutively (i.e., many
N-grams match). Therefore, using N-grams is eﬀective for scalable large-variance clone detection.
Then, NIL creates an inverted index from the generated N-grams. An inverted index is an
information retrieval technology that allows the fast retrieval of documents that contains a word
given as a query [73]. It is often used in clone detection techniques [74]. NIL uses a dictionary whose
keys are the hash values of N-grams, and values are the code blocks containing the corresponding
N-gram as an inverted index. All code blocks containing an N-gram can be quickly obtained bylooking up the hash value of the N-gram in the inverted index. Therefore, a pair of code blocks
that share an N-gram (i.e., the pair is possibly a large-variance clone pair) can be obtained quickly
using the inverted index.
However, an inverted index consumes a lot of memory. Hence, creating an inverted index fromall code blocks may lead to large memory consumption. To avoid this, we apply partial inverted
indexes [70]. Code blocks are divided into several groups and an inverted index is created foreach group (i.e., a partial inverted index), instead of creating a single inverted index for all code
blocks. Figure 11 shows the concept of partial inverted indexes. First, code blocks extracted fromsource code are divided into n groups (Step 1), where n is set to a value such that the memory
consumption of a partial inverted index is manageable. Next, an inverted index is created fromone group of code blocks (Step 2). Based on the partial inverted index created in Step 2 and allcode blocks, clone pairs between the code blocks in the group and all code blocks are detected in
Step 3 (the clone detection process is described in the following Section 2.2). Steps 2 and 3 areperformed for each group of code blocks.
2.2

Clone detection

After the Preprocessing phase, NIL performs Clone detection using the inverted index created in
the Preprocessing phase and all code blocks. Clone detection is divided into three phases, namely
21

Entire code blocks
code block

1. Divide into n groups
First group

Second group

code blockcode block

2. Create

4. Create

Inverted
Index

InvertedIndex

n-th group…

code block

2n. Create…

InvertedIndex

3. Clone detection
5. Clone detection
2n+1. Clone detection

Clone pairFigure 11: Concept of partial inverted indexes

location, ﬁltration, and veriﬁcation, as done by LVMapper [37]. First, NIL selects a code block fromall code blocks prepared in the Preprocessing phase as the target code block. Then, in the locationand ﬁltration phases, NIL identiﬁes the clone candidates of the target code block using an N-gramand the inverted index. Next, in the veriﬁcation phase, NIL veriﬁes that the target code blockand the clone candidates are clone pairs by calculating the LCS. These phases are performed foreach code block to detect all clone pairs in the target source code. Algorithm 1 shows the Clone
detection algorithm. The three phases of Clone detection are described in detail below.
2.2.1

Location phase

In the location phase, NIL collects the clone candidates of the target code block using theinverted index. Lines 3–11 in Algorithm 1 are the location phase.
First, NIL generates N-grams from the token sequence of the target code block. M−N+1 Ngrams are generated from a token sequence with length M . Next, a hash value is calculated foreach N-gram. This hash value is used as a query when looking up values in the inverted index.
Finally, NIL applies the hash values to the inverted index and collects code blocks that containthe N-gram whose hash value is the same as the given hash value. The obtained code blocks arereferred to as the clone candidates of the target code block.
22

2.2.2Filtration phase

In the ﬁltration phase, NIL removes code blocks that unlikely to be clones from the clone
candidates collected in the location phase. Lines 13–22 in Algorithm 1 are the ﬁltration phase. It
is necessary to reduce the number of clone candidates for scalable and fast clone detection because
NIL performs the LCS calculation, which is a time-consuming process, in the veriﬁcation phase.
NIL ﬁlters clone candidates based on a feature of large-variance clones.
As described in Section 2.1, the two code blocks of a large-variance clone pair share a certain
number of N-grams. Hence, if two code blocks share few N-grams, the pair is unlikely to be alarge-variance clone pair. Based on this feature, NIL calculates f iltration sim, deﬁned below,
between the target code block and each clone candidate.
f iltration sim(c1 , c2 ) =common ngrams(c1 , c2 )min(ngrams(c1 ), ngrams(c2 ))common ngrams(c1 , c2 ) = |ngrams(c1 ) ∩ ngrams(c2 )|where c1 and c2 are two code blocks with lengths |c1 | and |c2 |, respectively. ngrams(c1 ) andngrams(c2 ) are the numbers of N-grams generated from code blocks c1 and c2 , respectively. Because of the large number of statement insertions and deletions in large-variance clones, the twocode blocks may have signiﬁcantly diﬀerent token sequence lengths. We use min in the denominatorso that f iltration sim can be properly calculated even such cases. NIL removes clone candidates
whose f iltration sim is less than ﬁltration threshold θ.
2.2.3

Veriﬁcation phase

In the veriﬁcation phase, NIL checks whether the target code block and each clone candidate
are a true large-variance clone pair. Lines 24–32 in Algorithm 1 are the veriﬁcation phase. As
mentioned in Section 2.2.2, one of the features of large-variance clones is that the common subsequence between token sequences of large-variance clones is long even if there are a large numberof insertions and deletions. Therefore, NIL calculates the LCS between the target code block andeach clone candidate and measures the similarity of the pair based on the length of the LCS. The
similarity function verif ication sim(c1 , c2 ) is expressed as following
verif ication sim(c1 , c2 ) =lcs(c1 , c2 )min(|c1 |, |c2 |)where c1 and c2 are token sequences with lengths |c1 | and |c2 |, respectively, and lcs(c1 , c2 ) is thelength of the LCS between c1 and c2 .
We use min as the denominator of the similarity function to detect large-variance clones, as
done in the studies on CCAligner [36] and LVMapper [37] even if the lengths of the token sequences
diﬀer greatly.
Other clone detectors [37, 51] also use the LCS to measure similarity. However, they calculate
line-based LCS whereas NIL calculates token-based LCS. In general, the token sequence of a code
block is longer than its line sequence. The time complexity of a method for LCS calculation based23

on dynamic programming is O(|A| × |B|), indicating a very long computation time for a large
input size [75]. To reduce time complexity, NIL uses the Hunt-Szymanski algorithm [76]. With
this algorithm, NIL can calculate the LCS in O(r log |A| + |B| log |B|), where A and B are token
sequences (|A| ≤ |B|) and r is the number of pairs of common tokens between A and B.

24

Algorithm 1: Clone Detection
Input: C is a list of tokenized code blocks {c1 , c2 , . . . , cn }, Inverted Index I of C, N for size ofN-gram, θ for ﬁltering threshold, δ for verifying threshold
Output: All clone pairs CP
1: CP ← ϕ;
2: for all each ci in C do
3:// Location phase4:// CC represents clone candidates
5:
CC ← ϕ6:
for j = 1, 2, . . . , (ci .len − N + 1) do
7:// ci [j] is j-th token in ci ’s token sequence
8:
n gram = concat(ci [j], ci [j + 1], . . . , ci [j + N − 1]);9:
key = hash(n gram);
10:// get is a function that returns values to which a given key is mapped in a given
dictionary11:
CC = CC ∪ get(I, key);12:
end for
13:
14:
15:
16:

17:
18:
19:
20:
21:
22:
23:

// Filtration phase
for all each ccj in CC do/* common ngrams is a functionthat computes the number of common N-grams between two given code blocks */cn = common ngrams(ci , ccj );m = min(ci .len, ccj .len);f iltration sim = cn/(m − N + 1);
if f iltration sim < θ thenCC = CC \ {ccj };end ifend for24:// Veriﬁcation phase26:
for all each ccj in CC do
27:/* lcs is a function that computes the length of the LCS between token sequences of two
given code blocks */28:
lcs len = lcs(ci , ccj );29:
verif ication sim = lcs len/min(ci .len, ccj .len);30:
if verif ication sim ≥ δ then31:
CP = CP ∪ (ci , ccj );32:
end if
33:
end for34: end for
35: return CP ;
25:

25

3

Evaluation
We evaluated NIL in terms of• large-variance clone detection accuracy,• general clone detection accuracy, and• scalability.

In the following subsections, we ﬁrst optimize the N-gram size based on a balance between
recall and execution time. Next, we evaluate large-variance clone detection accuracy in terms
of precision and recall. Then, we evaluate general clone detection using two commonly usedbenchmarks. Finally, we evaluate scalability by measuring execution time for various input sizes.
Additionally, we compare the above results to those for four state-of-the-art tools [23, 36, 37, 51].
Table 1 shows these clone detectors and their settings. These settings were taken from the priorstudies [23, 36, 37]. Note that the threshold δ for veriﬁcation of LVMapper is variable and that δ
takes the following values depending on the number of the lines of clone l.



0.7
δ=

3.1

if 6 < l ≤ 10,

1 − 0.03 × l



0.4

if 10 < l ≤ 20,
if 20 < lSummaryFirst, we summarize the results of this evaluation. We found that NIL has a high precisionof 87% and a high recall of 100% in large-variance clone detection. These values are the highest
among the tested large-variance clone detectors [36, 37]. In general Type-1, Type-2, and Type3 clone detection, NIL’s accuracy is equivalent to that of the existing clone detectors, including
large-variance clone detectors, and its precision is higher than that of large-variance clone detectors.
Moreover, we conﬁrmed that NIL is the fastest at detecting clones in large codebases (1–250 MLOC)
among the tested clone detectors.
Table 1: Settings for various clone detectors
Tool

Settings

LVMapperMin length 6 lines, window size k = 3,
ﬁltering threshold θ = 0.1,
veriﬁcation threshold δ is dynamic.

CCAligner

Min length 6 lines, window size q = 6,
edit distance e = 1, min 60% similarity.

SourcererCC

Min length 6 lines, min 70% similarity.

NiCad

Min length 6 lines, max length 20,000 lines,
blind renaming, identiﬁer abstraction,
min 70% similarity.

26

3.2

Parameter setting

NIL requires three parameters, namely N for N-grams, ﬁltration threshold θ, and veriﬁcationthreshold δ. We set δ to 0.7, which is often used in clone detectors [23, 51]. We set θ to 0.1, as
done for LVMapper. N must be carefully selected because it has a large impact on performance(e.g., execution time and clone detection accuracy). If N is set to a too small value, the recallof clone detection will increase because more code blocks will share the same N-grams. However,
because more code blocks are identiﬁed as clone candidates in the location phase, the number ofcomparison targets in the ﬁltration and veriﬁcation phases increases, resulting in a longer execution
time. Therefore, to optimize the N , we executed NIL with N = 1–9 and measured the execution
time and clone detection recall for each N value. We used BigCloneEval [77] to measure recall.
BigCloneEval automatically measures the recall of clone detectors using BigCloneBench [78].
Table 2 shows the results for each N value. For N < 5, an increase in N signiﬁcantly reduces
the execution time without lowering recall by more than one point compared to when N = 1. For
N = 5 and 6, execution time decreases but recall also decreases. For N > 6, execution time does
not signiﬁcantly decrease. Therefore, considering the balance between execution time and recall,
N = 5 is the optimal value.

27

28
93.5
68.4
11.2
> 24h

Strongly Type-3

Moderately Type-3

Execution time

97.5

Type-2

Very Strongly Type-3

1N

2h 13m 52s

11.2

68.4

93.5

97.5

2

21m 42s

11.2

68.4

93.5

97.5

3

5m 56s

11.1

68.3

93.5

97.5

4

2m 58s

10.6

67.1

93.5

96.6

5

1m 13s

9.9

65.3

93.1

96.3

6

Table 2: Recall and execution time results for each N value

1m 4s

9.3

64.6

92.9

96.1

7

1m 2s

8.7

63.7

92.7

95.8

8

57s

7.8

62.0

92.5

93.3

9

3.3

Large-variance clone detection

We evaluated the large-variance clone detection accuracy of NIL in terms of precision and recall
and compared the results to those for existing large-variance and large-gap clone detectors, namely
CCAligner and LVMapper.
3.3.1

Precision

Precision is the ratio of correct clones detected to all clones detected. A clone detector withhigher precision provides more accurate results. In general, precision is measured via a manualvalidation of the clones detected by the target tool. In this part, we used Ant and Maven, whichwere used in the prior studies on CCAligner [36] and LVMapper [37] to measure precision. JDK1.2.2
and OpenNLP, also used in the above studies, were not used here because we were not able toﬁnd the source code for JDK1.2.2, which has been end-of-lifed and we considered OpenNLP to
be unsuitable for manual validation because it is a machine learning library whose source code
is diﬃcult to read (e.g., it includes repetitive array manipulation code). We used the following
procedure to measure the precision of each tool:
1. we input the target source code into each tool,
2. we randomly selected 100 large-variance clone pairs with more than 10 lines for each tooland target system, and3. we manually conﬁrmed whether the clone pairs were correct.
To remove bias in the manual validation, the detected large-variance clone pairs of a given tool
were validated without knowledge of the tool used for detection. Table 3 shows the number of ﬁlesand total LOC for Ant and Maven.
Table 4 shows the number of large-variance clone pairs detected by each tool and the precision
for each tool2 . The number of large-variance clones detected by NIL detected was almost sameas that of LVMapper and more than that of CCAligner. The manual validation results indicatethat NIL had a high average precision of 87% whereas LVMapper and CCAligner had low average
precision values of about 60% and 40%, respectively. We considered this diﬀerence in precision to
be due to LVMapper and CCAligner normalizing the identiﬁers in code blocks. After checking thelarge-variance clones detected by LVMapper and CCAligner, we found that code blocks with consecutive assignment statements, such as constructors, and consecutive if-statements were incorrectly
detected as large-variance clones. In contrast, NIL detected large-variance clones more precisely
because it does not perform identiﬁer normalization.
Table 3: Target systems
Name# Files

LoC

Ant 1.10.1

895

109,073

Maven 3.5.0

698

60,471

2 Manual validation descriptions are available at https://zenodo.org/record/4490845

29

In addition, NIL had a higher precision than that of LVMapper and detected a similar number oflarge-variance clone pairs, indicating that it can detect many large-variance clones that LVMapper
cannot. After checking large-variance clones that NIL detected but LVMapper did not, we found thatthe large-variance clone pairs share a small number of consecutive lines. LVMapper regards threeconsecutive lines in code blocks as code windows (see Section 2.4) and identiﬁes clone candidates
based on these code widows. Therefore, if a pair of code blocks shares a little or no code window,
LVMapper cannot detect the pair as a large-variance clone pair. In contrast, NIL can detect suchlarge-variance clones because it uses an N-gram representation of token sequences.
3.3.2

RecallRecall is the ratio of clones detected by a tool to the total number of true clones in the target
codebase. A clone detector with a higher recall can detect true clones more exhaustively. To
evaluate recall, all true clone pairs in the target codebase are required. However, it is not realistic
to manually check all code block pairs in a system to determine the total number of true clone
pairs.
Therefore, we generated large-variance clone pairs automatically using mutation techniques toevaluate recall. Mutation techniques are frequently used for clone detector recall evaluation [79].
The studies on CCAligner [36] and LVMapper [80] used them to evaluate large-variance clone detection recall. In this part, we reproduced large-variance clones by randomly inserting various
numbers of statements into original code blocks (i.e., the large-variance clones are mutants of theoriginal code blocks). We targeted JDK6 and Apache Commons3 because they were used in the
study on CCAligner [36]. We randomly selected 100 functions with 15–50 lines in these systems
as the original code blocks. A minimum length 15 lines is often used for recall evaluation using
mutation techniques [23, 79]. We used a maximum length of 50 lines because if the number oflines of the original code blocks is too large, even if a large number of statements are inserted into
the code blocks, the generated clones will not be large-variance clones. For example, if 20 lines ofstatements are inserted into an original code block, if the number of lines of a code block is 100,
the ratio of lines of the clone pair is 100/120 > 0.7, and thus the clone pair does not satisfy thelarge-variance clone deﬁnition. To reproduce large-variance clone pairs, 1–20 one-line statements
Table 4: Large-variance clone detection results
Tool
NIL

LVMapper

CCAligner

System# Large-variance clones

Precision (%)

Ant

354

86.0

Maven

398

88.0

Ant

355

64.0

Maven

389

60.0

Ant

184

43.0

Maven

284

40.0

3 A project that provides open-source reusable Java components

30

100

NIL

90
80

Recall (%)

70

LVMapper60
50

CCAligner

40
30
20
10
0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20# Inserted lines
Figure 12: Recall results for various numbers of inserted lines

were inserted into each code block at random locations. 20 clone pairs were generated per originalcode block, for a total of 2,000 clone pairs, including large-variance clone pairs4 .
Figure 12 shows the recall of NIL, LVMapper, and CCAligner for clone pairs generated by inserting
various numbers of statements. NIL detected all generated clone pairs. This is because even thoughmany statements are inserted into a code block, the order of many tokens between the largevariance clone pair is preserved, and thus the clone pair shares a certain number of N-grams andhas a long common subsequence. In summary, using N-gram-based clone candidate identiﬁcationand token-LCS-based clone validation is eﬀective in large-variance clone detection.
On the other hand, as shown in Figure 12, the recall of LVMapper and CCAligner decreased withincreasing number of inserted lines. LVMapper can also detect clones in which a large number ofstatements are inserted because it veriﬁes clones based on line-based LCS. However, our evaluation
results show that the recall of LVMapper decreased with increasing number of inserted lines. Thisis because LVMapper failed to identify many large-variance clones in its locating phase. LVMapper
identiﬁes a pair of code blocks that share some code windows (see Section 2.4) as a clone pair.
Therefore, with increasing number of inserted lines, the number of shared code windows decreases,
and thus LVMapper failed to identify a pair of code blocks as a large-variance clone pair. CCAligner
4 The generated large-variance clone pairs are available at https://zenodo.org/record/4491016

31uses e-mismatch code windows to identify clone candidates, and this aﬀects its recall. In addition,
CCAligner uses code windows in veriﬁcation and thus fails to detect large-variance clones.
3.4

General clone detection

We evaluated the general Type-1, Type-2, and Type-3 clone detection accuracy of NIL using
two benchmarks, namely Mutation Framework [79] and BigCloneEval [77]. In addition, we compared the results of NIL to those of existing state-of-the-art tools, namely CCAligner, LVMapper,
SourcererCC, and NiCad.
3.4.1

Mutation Framework

Mutation Framework automatically generates clone pairs based on mutation techniques. We
executed Mutation Framework with all the default settings and input the generated clones5 into
each clone detector. Table 5 shows the results of recall for each tool measured by Mutation
Framework. NIL detected all clone pairs generated by Mutation Framework.
3.4.2

BigCloneEval

BigCloneEval [77] automatically measures the recall of clone detectors using BigCloneBench [78].
We also measured precision, as done in the prior studies [23, 36, 37]. For each tool, we randomly
selected 400 of the detected clone pairs from BigCloneBench and validated them manually. The
clones were shuﬄed, and the validation was conducted without knowledge of the clone source.
Table 6 shows the results of recall6 and precision for each tool on BigCloneBench7 . As shown,
NIL has a high recall of 96% for Type-2 clone detection even though it does not normalize identiﬁers in the Preprocessing phase. NIL had the second highest recall of Moderately Type-3 clones,
which contain large-variance clones, behind only LVMapper. We considered that this is because
normalizing identiﬁers is necessary to detect most Moderately Type-3 clones.
The precision (see bottom of Table 6) of both LVMapper and CCAligner, which are large-varianceand large-gap clone detectors, was low. In contrast, that of NIL was very high (94%). Even
though SourcererCC and NiCad also had high precision, they had poor large-variance clone detection
performance. Therefore, compared to the existing tools, NIL has equivalent general clone detection
accuracy and higher precision than that of the existing large-variance clone detectors.
Table 5: Recall results for Mutation Framework
Tool

NIL

LVMapper

CCAligner

SourcererCC

NiCad

Type-1

100.0

100.0

100.0

100.0

100.0

Type-2

100.0

100.0

100.0

100.0

100.0

Type-3

100.0

99.9

99.9

100.0

100.0

5 The generated clone pairs are available at https://zenodo.org/record/4491052
6 Note that in our experiments, BigCloneEval reported diﬀerent recall of the existing clone detectors from the priorstudies. Type-1 recall of some clone detectors was 99.9% because BigCloneBench contains faulty clone pairs [81].
7 Manual validation descriptions are available at https://zenodo.org/record/4493069

32

3.5

Scalability

We evaluated the scalability of NIL using codebases with various sizes and compared the execution time of NIL to those of the existing tools. We used IJaDataset [82], a large inter-projectJava dataset, as done in the prior studies [23, 36, 37]. We created datasets with 1, 10, 100, and 250
MLOC8 . We used CLOC [83] to measure the LOC of the datasets. A computer with a quad-core
CPU and 12 GB of memory was used for the evaluation, as done in the prior studies [23, 36].
Table 7 shows the execution times for each tool for various input sizes. As shown, the execution
time of NIL is the shortest for all input sizes. Even though both LVMapper and SourcererCC detectedclones from the 250-MLOC codebases, their execution times are longer than three days, indicatingpoor scalability. In addition, CCAligner and NiCad was not able to complete detecting clones fromthe 100- and 10-MLOC codebases, respectively, indicating their limited scalability. Therefore, NIL
has the highest scalability.
Moreover, we examined how eﬀective the location and ﬁltration phases are for NIL’s scalability.
Figure 13 shows growth in the number of clone candidates with the increased number of code blocks.
Note that this ﬁgure is a logarithmic graph. “Naive” is comparing all pairs of code blocks for clone
detection9 . As shown in the ﬁgure, both the location and ﬁltration phases were able to drasticallyreduce the number of clone candidates. For example, when there were 10,000 code blocks, thenumber of clone candidates was able to be reduced from 49,995,000 in Naive to 1,449,634 in thelocation phase and 54,000 in the ﬁltration phase. Therefore, the two phases are very eﬀective forscalable clone detection.
Table 6: Recall and precision results for BigCloneBench
Tool

NIL

LVMapper

CCAligner

SourcererCC

NiCad

Type-1 Recall

99.9

99.9

99.8

93.8

99.9

Type-2 Recall

96.6

99.2

98.9

96.6

99.2

Very Strongly Type-3 Recall

93.5

98.1

97.4

68.2

98.4

Strongly Type-3 Recall

67.1

81.8

69.0

59.0

69.7

Moderately Type-3 Recall

10.6

19.1

10.0

4.8

0.5

Precision

94.0

58.5

33.7

99.2

80.2

Table 7: Scalability results
Tool

NIL

LVMapper

CCAligner

SourcererCC

NiCad

1M

10s

29s

52s

3m 1s

1m 48s10 M

1m 38s

13m 38s

26m 3s27m 37s—

100 M

1h 38m 29s

17h 23m 39s—

19h 38m 5s

—

250 M

7h 40m 7s

3d 13h 47m 39s—

5d 6h 55m 1s—

8 These datasets and an executable ﬁle of NIL are available at https://zenodo.org/record/4491208.
9 The curve can be represented using y = x(x − 1)/2 quadratic function where x is the number of code blocks ina project and y is the number of candidate comparisons carried out to detect all clone pairs.

33

10"

Naive

Located# Clone candidates

10#
10$

Filtered

10%
10&
10!
10
1

1

2,500

5,000

7,500

10,000# Code blocks
Figure 13: Growth in the number of clone candidates with the increased number of code blocks

34

4

Threats to Validity

To measure precision for each tool, we manually validated clones each tool detected, as donein the prior studies [23, 36, 37]. Because the clone detector names were not disclosed during themanual validation, there was no bias in the evaluation. However, because the criteria for whethera pair of code fragments is a clone pair can vary, manual validation by other researchers may yielddiﬀerent values. To ensure the validity of this study, the clones used in the manual validation are
made public so that a third party can conduct replication studies.
In this study, we used the widely used benchmarks, BigCloneEval [77] and Mutation Framework [79] to evaluate the recall of clone detectors. Diﬀerent results may be obtained using otherbenchmarks [19, 84, 85].
In this study, we targeted only the Java language. Diﬀerent results may be obtained for otherlanguages.
It is known that the accuracy and execution time of a clone detector is greatly inﬂuenced byits settings [86]. In this study, we optimized the N value for N-grams. However, the ﬁltrationthreshold θ and the veriﬁcation threshold δ were set based on values used by other clone detectors.
The results can be improved by optimizing these values for NIL.

35

5

Related Works
Many clone detection techniques have been proposed to achieve various goals.

5.1

Complicated Type-3 clone detection

In addition to large-variance clones, since complicated Type-3 clones are diﬃcult to detect,some techniques specialized for detecting them have been proposed.
Program dependence graph [87] (in short, PDG) is frequently used for complicated Type-3
clone detection. Krinke was the ﬁrst to use PDGs for clone detection [49]. His technique detectedisomorphic parts of PDGs as clones. He reported that PDG-based clone detection was good at recall
and precision. Higo et al. pointed out that Kirinke’s techniques suﬀered in the execution time anddetecting contiguous clones. To enhance PDG-based clone detection, they introduced two PDG
specializations and three heuristics into the PDG-based clone detection technique [50]. Zou et al.
pointed out that the PDG-based clone detection techniques have still been quite time-consuming
and missed many clones due to their exact graph matching using subgraph isomorphism. They
proposed CCGraph [88], using an approximate graph matching algorithm based on the reforming
Weisfeiler-Lehman graph kernel [89].
An intermediate representation (in short, IR) is also used for complicated Type-3 clone detection. Some syntactical diﬀerences (e.g., for-loop and while-loop) in source code are transformed
into the same or similar instructions in IRs of the source code. Selim et al. proposed a clone
detection technique using Java IRs generated by Soot [90, 91]. Their technique transforms Javasource code into their IRs and detects clones on the IRs using existing tools [40, 41], which were
not able to detect Type-3 clones. They reported that they detected Type-3 clones by executing
the tools on IRs of source code. Caldeira et al. also proposed a clone detection technique using
IRs [92]. They devised a C-like IR based on LLVM and ran NiCad [51] on it. Their experimental
results suggested that IRs were beneﬁcial for improving clone detection and IRs had a large impact
on complicated Type-3 clones.
Machine learning is also useful for complicated Type-3 clone detection. Saini et al. proposeda clone detector, Oreo, for Weakly Type-3 clones [93]. It combines machine learning, information
retrieval techniques, and software metrics to detect clones.
However, those three techniques based on PDG, IR, or machine learning do not always detectlarge-variance clones. For example, a prior study showed that Oreo has a higher precision but lower
recall in large-variance clone detection than those of LVMapper [37]. Moreover, these techniques
require a long execution time and are limited in scalability. PDG-based clone detection requires
a long time to construct PDGs and perform subgraph isomorphism. IR-based clone detection
requires a long time to transform source code into IRs. Machine learning-based clone detection isnecessary to complete training before clone detection.
5.2

Scalable clone detection

Kamiya et al. proposed CCFinder [41] and its successor, CCFinderX [94]. CCFinder transforms
the target source code into a token sequence, normalizes identiﬁers, such as variable names andliterals, and then uses a suﬃx tree algorithm to detect matching token sequences as clones. As

36shown in prior studies [23, 71], CCFinderX has high scalability and can detect clones even for a
100-MLOC codebase.
Ishihara et al. proposed a scalable method-level clone detection technique [95]. The techniquehashes each normalized method and detects methods whose hash values are the same as clones.
They reported that they detected clones in a large codebase (3.5 MLOC) in 3.5 hours.
Hummel et al. proposed ConQat [74, 96], an index-based clone detector. ConQat creates clone
indexes by hashing consecutive six lines of source code and detects the clone indexes whose hashvalues are the same as clones. ConQat is capable of distributed processing in clone detection, so it
can be applied for ultra-large codebase (2.9 GLOC) using cluster computing.
However, those scalable clone detectors cannot detect gapped clones due to their algorithms.
Though there are several tools for scalable near-miss clone detection [23,70,71,97], they still cannot
detect complicated Type-3 clones, including large-variance clones. In this part, we proposed NIL,
which achieves both large-variance clone detection and scalability.

37

6Conclusion

In this part, we proposed a clone detection technique for the scalable detection of large-varianceclones from a large codebase and described its implementation, called NIL. NIL uses N-grams, aninverted index, and the LCS to detect large-variance clones. Our experimental results show that
NIL has higher precision and recall in large-variance clone detection than those of existing largevariance and large-gap clone detectors. In addition, the general Type-1, Type-2, and Type-3 clone
detection accuracy of NIL is equivalent to that of existing state-of-the-art tools. Moreover, NIL candetect clones from large codebases more quickly than do existing clone detectors.
As future works, we consider doing research on software engineering applications such as code
recommendation and completion, refactoring, and bug propagation for large-variance clones using
NIL.

38

Part III

Clone Modiﬁcation Support for Pull
Request Based Development

39

1

Background

There are many studies on simultaneous modiﬁcation and refactoring support for clones [24,25]
because clones have been pointed out as one of the major problems in the maintenance process ofsoftware development. An existing study proposed a clone change notiﬁcation tool, Clone Notiﬁer,
to improve the eﬃciency of these tasks [29]. Clone Notiﬁer takes two versions of a target project
as inputs and notiﬁes developers of information about clones changed between the versions. Clone
Notiﬁer is designed for industry use [30] and is premised on one execution a day. On the other hand,
Clone Notiﬁer is diﬃcult to be executed triggered by development workﬂow, such as modifying
source code or merging branches, because it is not designed to be triggered by external factors
except for time. For this reason, we think there are the following issues when considering the useof Clone Notiﬁer in development, such as OSS development, in which modifying source code or
merging branches are frequently conducted [98].
• The ﬁrst issue is that even if code fragments need modiﬁcations due to clone changes, the codefragments will not be notiﬁed promptly. Because Clone Notiﬁer is executed once a day, once
Clone Notiﬁer has been executed, there is a day interval until the next execution. Suppose
Clone Notiﬁer users set its execution interval shorter (e.g., ﬁve minutes) to solve this issue.
In that case, the information of clones is notiﬁed to the users frequently even if the sourcecode is not modiﬁed. Hence, the notiﬁcation probably annoys the users. On the other hand,
if code fragments to be modiﬁed are notiﬁed to the developers in line with the development
workﬂow, such as source code modiﬁcations, the developers will be able to respond to thecode fragments promptly without feeling such annoying.
• The second issue is that a large number of notiﬁcations are possibly sent to developers at once.
If a large number of source code modiﬁcations are conducted, and as a result, many clones
may be changed improperly (i.e., many code fragments need modiﬁcations), the information
is notiﬁed all at once. In this case, the users will be forced to check a large amount of clonechange information, and they may overlook serious clone changes. If clone change notiﬁcationis triggered by development workﬂow, code fragments to be modiﬁed are notiﬁed in line witheach source code modiﬁcation so that the developers can avoid overlooking serious clonechanges.
• The third issue is that code fragments to be modiﬁed are merged into the main branchwhen developing with version control systems (in short, VCS). In such development, themain branch should be bug-free and always ready for release. Therefore, code fragments tobe modiﬁed that may contain bugs should be checked before the topic branch is merged.
However, Clone Notiﬁer, which is premised on regular execution, is diﬃcult to detect suchcode fragments before merging topic branches. If clone change notiﬁcation is triggered bydevelopment workﬂow, the possibility of bugs merged into the main branch can be reduced
because such code fragments are detected before merging topic branches.
Consequently, in this part, we propose a clone modiﬁcation support system named CLIONE10 ,which aims to integrate into pull request based development to solve these issues. CLIONE detects
10 https://github.com/T45K/CLIONE40

code fragments that need modiﬁcations by tracking clones when creating pull requests (in short,PR), and CLIONE also notiﬁes the code fragments to developers as PR comments. Moreover, we
made three improvements for more accurate clone change tracking than Clone Notiﬁer.
In order to evaluate CLIONE, we conducted ﬁve experiments. We conﬁrmed the followings fromthe experimental results.
1. There are 21.5% of PRs in which clones have been modiﬁed non-simultaneously (i.e., some ofclones were modiﬁed but the others were not), indicating that CLIONE is useful for PR-based
development.
2. The execution time of CLIONE was suﬃciently short compared to CI tools widely usedin PR-based development, indicating that the barrier to introduce CLIONE into PR-based
development is low.
3. Due to the clone tracking improvements, CLIONE was able to track clones correctly comparedto Clone Notiﬁer in 34.6% of PRs in which clones have been modiﬁed non-simultaneously.
4. We conducted proposals the way of clone modiﬁcations using CLIONE and questionnaire
survey to developers. From the results, CLIONE is also useful for developers.

41

- private IRubyObject any_pBlockless(ThreadContext context) {for (int i = 0; i < realLength; i++) {if (eltOk(i).isTrue()) return context.runtime.getTrue();}return context.runtime.getFalse();- }+ private IRubyObject any_pBlockless(ThreadContext context, IRubyObject[] args) {+IRubyObject pattern = args.length > 0 ? args[0] : null;+
if (pattern == null) {+for (int i = 0; i < realLength; i++) {+if (eltOk(i).isTrue()) return context.runtime.getTrue();+}+} else {+for (int i = 0; i < realLength; i++) {+if (pattern.callMethod(context, "===", eltOk(i)).isTrue())+
return context.runtime.getTrue();
+
}
+
}
+
+
return context.runtime.getFalse();+ }(a) any pBlockless method
private IRubyObject all_pBlockless(ThreadContext context) {for (int i = 0; i < realLength; i++) {if (!eltOk(i).isTrue()) return context.runtime.getFalse();}return context.runtime.getTrue();}(b) all pBlockless method

Figure 14: Two methods in JRuby

2

Research Motivation

Figure 14 shows two methods in JRuby. In PR#509611 , while any pBlockless method was
modiﬁed, all pBlockless method was not modiﬁed. This non-simultaneous modiﬁcation introduced
a bug that caused an error when calling a Ruby API, which internally calls all pBlockless method in
JRuby into the main branch. As a result, JRuby, which included this bug, was released at version
9.2.0.0. This bug was ﬁxed in PR#529812 .
If the developers used CLIONE, they could avoid introducing the bug caused by non-simultaneous
modiﬁcation of clones into the main branch. In development using VCS, the main branch should
be bug-free and always ready for release. Therefore, a clone modiﬁcation system aimed to integrate
into development workﬂow is needed to keep main branch bug-free.

11 https://github.com/jruby/jruby/pull/5096
12 https://github.com/jruby/jruby/pull/5298

42

GitHub

Developer

7. Notifying the results
2. Creating PRs

1. Registration

Project

3. git-clone

6. Comment

Clone sets

Code fragments
to be modified

4. Detecting clones
from head commit
Clone sets

CLIONE

4. Detecting clones
from base commit

5. Tracking clones
and classification

Figure 15: Overview of CLIONE. Blue lines means processes CLIONE performs.

3

Proposed System: CLIONEIn this part, we propose CLIONE, a clone modiﬁcation support system aimed to integrate intodevelopment workﬂow. CLIONE detects code fragments that need modiﬁcations by tracking clones
automatically at the time of creating PRs. CLIONE is a server-side application which uses GitHub
Apps [99] and receives HTTP requests which GitHub sends when developers create PRs. Thanks
to GitHub Apps, it is easy to install CLIONE on GitHub projects.
3.1

Overview

Figure 15 shows an overview of CLIONE. First, developers who want to use CLIONE register
their GitHub accounts and their repositories with CLIONE. After this registration, whenever thedeveloper creates a PR, GitHub sends an HTTP request to CLIONE, and CLIONE is executed.
CLIONE tracks clones between the head commit of the PR and the commit at the point where thePR branch was created (in short, base commit).
When the developer creates a PR, CLIONE downloads (git-clone) the project onto its local
environment. Next, CLIONE detects clones from the head and the base commits of the PR,
respectively, by using NiCad [51] or SourcererCC [23]. Why we select these clone detectors is eachof them can detect Type-3 clones precisely.
After clone detection on each commit, CLIONE tracks clones to detect clone changes between
the two commits. Clone tracking is used to determine if the clone has been modiﬁed between thetwo commits. As well as Clone Notiﬁer, in order to track clones between the two commits, CLIONE
calculates the overlapping location of clones, based on the location overlapping function of Kim

43

et al. [54]. Moreover, in order to suppress the execution time of CLIONE, CLIONE does not trackclones in source ﬁles that have not been modiﬁed between the two commits. The reason is thatsuch clones can be determined to be unchanged without tracking them.
After clone tracking, based on changes of clones, CLIONE detects code fragments that need
modiﬁcations. Speciﬁcally, CLIONE treats clone sets where some clones were modiﬁed but theothers were not modiﬁed and clone sets where some or all of clones were newly added as codefragments to be modiﬁed. Moreover, in CLIONE, we made three improvements for more accurate
clone tracking than Clone Notiﬁer. We explain the improvements in Section 3.2.
Finally, CLIONE makes a PR comment for each the code fragments to be modiﬁed to notify the
results to the developer. Figure 16 shows an example of PR comment about a non-simultaneously
modiﬁed clone set. In the top of the ﬁgure (a), the changed piece of the changed code fragment isshown in the diﬀ format, the whole of changed code fragment is shown in the middle (b), and thenon-changed code fragment is shown in the bottom (c). By getting notiﬁcations of the results as
PR comments, developers can receive feedback promptly.
3.2

Improvements of clone tracking

In CLIONE, we made three improvements to the clone change tracking technique used in Clone
Notiﬁer,
1. code fragment tracking,
2. ﬁle rename detection, and3. clone change judgment by comparing token sequences.
3.2.1

Code fragment tracking

First, CLIONE tracks not only clone instances but also code fragments. Clone Notiﬁer treats
only clone instances (code fragments that are detected as clones) as targets of tracking. Thus, if
code fragments that are detected as clones in the old version are not detected in the new version,
the code fragments are classiﬁed deleted clone instances by Clone Notiﬁer. On the other hand,in some cases, a code fragment is not detected as a clone because it has been modiﬁed. For
example, ﬁgure 17(a) shows two methods detected as clones in the base commit, but not detected
as clones in the head commit because one of them has been modiﬁed. In this case, Clone Notiﬁer
classiﬁes the clone set (i.e., the two methods) as Deleted because the methods are not detected
as clones in the head commit. However, this clone set should be classiﬁed as non-simultaneous
modiﬁcation because only main1 method was modiﬁed. As a result, developers may overlook thisnon-simultaneous modiﬁcation.
On the other hand, CLIONE tracks not only clone instances but also code fragments, such as
methods or code blocks. Even if clones are not detected in one of the commits, the changes of clones
can be detected by tracking code fragments themselves. Figure 17(b) shows an example of codefragment tracking. In this example, CLIONE tracks the methods themselves. As a result, CLIONE
can detect a non-simultaneously modiﬁed clone set (ﬁgure 17(c)) and classify it appropriately.

44

3.2.2File rename detection

Second, CLIONE detects ﬁle name changes. Clone Notiﬁer tracks clones in ﬁles with the same
name in the input two versions. On the other hand, in software development and maintenance,
ﬁle names are often changed. When a ﬁle is renamed between versions, Clone Notiﬁer determinesthat the ﬁle was deleted in the old version and added in the new version. Therefore, when a ﬁle isrenamed, Clone Notiﬁer incorrectly classiﬁes clones in the ﬁle as Deleted in the old version and as
Added in the new version, even if the contents of the ﬁle have not changed.
On the other hand, CLIONE uses Git’s rename detection function to track ﬁles based on thesimilarity of their contents, even when the ﬁle name has been changed. As a result, the codefragments in the ﬁle can be tracked, reducing the misclassiﬁcation of clones.
3.2.3

Clone change judgment by comparing token sequences

Third, CLIONE judges whether clones are changed or not by comparing their token sequences.
In Clone Notiﬁer, a clone is considered modiﬁed if there are lines in the clone that have been added
or deleted between two versions. On the other hand, even if changes made in clones do not aﬀect
the program behavior, such as formatting or comments, Clone Notiﬁer judges that the clones havebeen changed. In particular, when the source code format is changed, a large number of clones
may be judged as having changed because the changes will cover a wide area of the entire sourcecode. Therefore, judging whether clones have been changed based on the presence or absence ofadded or deleted lines may be burdensome for developers to check because a large amount of clonechange information will be notiﬁed even if the changes do not aﬀect the behavior of the program.
On the other hand, CLIONE converts the tracked code fragments into token sequences andcompares them to judge if the code fragments have been modiﬁed. Therefore, CLIONE can judge
whether clones have been modiﬁed while ignoring changes that do not aﬀect its behavior, such asformatting or comment changes. This allows us to avoid notifying developers of changes in clones
that they do not need to check.

45

a

b

c

Figure 16: Example of comment about a non-simultaneously modiﬁed clone sets46

1 void main1() {2 int a = 0;
3 String b = "";4 }5
6 void main2() {7 int c = 0;
8 String d = "";9 }1 void main1() {2
int a = 0;
3
int c = 1;
4
String b = "";5 }6
7 void main2() {8
int c = 0;9String d = "";10 }base commit

head commit(a) Clone instance tracking

1 void main1() {2 int a = 0;
3 String b = "";4 }5
6 void main2() {7 int c = 0;
8 String d = "";9 }1 void main1() {2
int a = 0;
3
int c = 1;
4
String b = "";5 }6
7 void main2() {8
int c = 0;9String d = "";10 }base commit

head commit(b) Code fragment tracking

1 void main1() {2 int a = 0;
3 String b = "";4 }5
6 void main2() {7 int c = 0;
8 String d = "";9 }1 void main1() {2
int a = 0;
3
int c = 1;
4
String b = "";5 }6
7 void main2() {8
int c = 0;9String d = "";10 }base commit

head commit(c) Accurate clone change tracking

Figure 17: Improvement of clone tracking
47

4

Evaluation
In this part, we conducted ﬁve experiments to evaluate CLIONE.

4.1

Experiment 1

In experiment 1, in order to evaluate the usefulness of introducing CLIONE into PR-based
development, we investigated the proportions of PRs in which clones have been modiﬁed nonsimultaneously, which CLIONE targets to notify. In this experiment, we manually executed CLIONE
on merged PRs of target projects and investigated whether clones had been modiﬁed simultaneously
or not for each PR.
In this experiment, we selected three OSS as our experimental targets. Table 14 shows thenames of the projects, the number of PRs merged by 20/7/2020, and the number of PRs in which
at least a Java ﬁle was changed (in short, target PRs). We selected those OSS because they areoften targeted in clone research [100–102] and developed in PR-based development on GitHub.
Table 9 shows the results of experiment 1. In this table, “improper PRs” means PRs in whichclones were modiﬁed non-simultaneously. All the projects have PRs in which clones were modiﬁed non-simultaneously, and their proportions are 11.9%–30.4%. Some of these non-simultaneous
modiﬁcations can cause bugs, as introduced in Section 2. Hence, developers need to check nonsimultaneously modiﬁed clones and determine whether they need modiﬁcations before merging
branches. If the developers use CLIONE, they are notiﬁed of non-simultaneously modiﬁed clones
for each PR created, so that they can easily deal with them. Therefore, CLIONE is useful to support
clone modiﬁcations in PR-based development.
Table 8: Target OSS
Name

# PRs

# Target PRs

JRuby13

2,248

292

JUnit4

848

236

Gson

317

69

Table 9: Results of experiment 1
Name# Target PR# improper PR

Proportion

JRuby

292

89

30.4%

JUnit4

236

28

11.9%

Gson

60

10

16.7%

Total

588

127

21.5%

13 JRuby is a multi-module project, and we targeted only core module of JRuby.

48

4.2

Experiment 2

In experiment 2, in order to evaluate whether CLIONE can be introduced into PR-based development, we measured response time from PR creation to CLIONE notiﬁcation14 . Additionally, we
compared the response time of CLIONE with the execution time of CI tools15 , which are widelyused in PR-based development [55]. If the response time of CLIONE is shorter than the execution
time of CI tools, the barrier to introducing CLIONE to PR-based development is low.
In this experiment, we manually reproduced the target PRs of JRuby, one of the OSS targetedin Experiment 1, and measure the response times of CLIONE. We targeted JRuby because JRubyis the only one that uses CI tools for the automated build. By all rights, we should reproduce allof the target PRs. However, we considered that manually reproducing them is hard task. Thus,
we targeted only the ﬁve latest PRs merged by 6/10/2020 and at least a Java ﬁle was changed.
Table 10 shows the results of experiment 3. As shown in the table, in all PRs, each responsetime of CLIONE is much shorter, less than half of the corresponding CI tool execution time. The
CI execution time varies so much depending on the PR because JRuby builds in two diﬀerent CI
tools depending on the PR changes. We also checked the breakdown of the CLIONE response timeand found that the PR#6424 took 50 seconds (67.4%) for git-clone, 25 seconds (29.0%) for clone
detection, and 1 second (1.6%) for others. The same trend was observed for the response time inother PRs. This indicates that CLIONE speciﬁc processes such as clone tracking and classiﬁcationaccount for a very small percentage of CLIONE’s response time. Also, since git-clone accounts
for the majority of CLIONE’s response time, we can improve the implementation of CLIONE. For
example, only the diﬀerences are downloaded to the CLIONE environment (git-pull) instead of
downloading the full target project every time a PR is created.
In addition, we conducted an experiment to estimate the upper limit of the response time of
CLIONE. As mentioned in Section 3.1, CLIONE does not track clones in ﬁles that have not been
modiﬁed. Therefore, the more ﬁles are modiﬁed in the PR, the more clones are tracked, and the
response time of CLIONE increases. Hence, CLIONE response time is expected to be the largest
when all the Java ﬁles in the project have been modiﬁed. In order to estimate the upper limit of
CLIONE response time, we created a PR with the change of adding blank lines at the end of all
Java ﬁles in JRuby16 , and measured the response time of CLIONE. A total of 1,459 Java ﬁles wereTable 10: Response times of each PR
PR number
6424
6412
6410
6407
6401

CLIONE response time

CI tool execution time

1m 26s
1m 28s
1m 23s
1m 18s
1m 17s4m 35s
14m 35s
12m53s
4m 20s
13m 26s

14 Our environment where CLIONE is executed is as follows; CPU: Intel Xeon E5-2620, Memory: 32GB, and OS:

Ubuntu 18.04.
15 Continuous Integration tools. They automatically build and test projects at the time of creating PRs or pushingcommits.
16 https://github.com/T45K/jruby_clione/pull/649

modiﬁed in this PR. The response time of CLIONE for this PR was 3 minutes and 37 seconds,
which is an increase from the response time in table 10 but shorter than the execution time of CI
tools.
In summary, CLIONE can notify code fragments in a short time, which is faster than theexecution time of CI tools, and CLIONE also can be easily introduced into PR-based development.
4.3

Experiment 3

In experiment 3, in order to evaluate our improvements of clone tracking, we compared theresults of CLIONE’s clone tracking and Clone Notiﬁer’s one. In this experiment, we manually
executed CLIONE and Clone Notiﬁer on the target PRs of three projects shown in table 14, checked
the clone tracking results of each tool, and counted PRs in which the clone tracking results are
diﬀerent.
As a result, we conﬁrmed that there were 44 PRs (34.6% of improper PRs) in total in which
CLIONE tracked clones more accurately than Clone Notiﬁer. On the other hand, there was no clone
where Clone Notiﬁer succeeded in tracking but CLIONE failed. Table 11 shows a breakdown of
the improvements that contributed to the diﬀerent clone track results. As shown in table 11, thenumber of PRs with diﬀerent clone tracking results by code fragment tracking is the highest. On
the other hand, the number of PRs with improved tracking results for ﬁle rename detection andclone change judgment by comparing token sequences is small. However, in the PRs with improved
tracking results, CLIONE was able to correctly classify a large number of clone changes while Clone
Notiﬁer misclassiﬁed a large number of clone changes due to ﬁle name changes and format changes.
In other words, although the number of improved PRs is small, these improvements can signiﬁcantly
reduce the burden on developers because the developers are not notiﬁed of the tracking results ofa large number of clones that are not considered necessary to be checked in that PR.
In summary, thanks to these three improvements, CLIONE can track clones more accurately
than Clone Notiﬁer and provide more useful clone change information.
4.4

Experiment 4

In experiment 4, in order to evaluate the usefulness of CLIONE for developers, we detected nonsimultaneously modiﬁed clones from past PRs of OSS using CLIONE, modiﬁed them, and proposed
them to the developers of OSS as PRs. When the proposed PR was merged, if the OSS developers
had used CLIONE, they would have dealt with the non-simultaneously modiﬁed clones when the
PR was created. Therefore, CLIONE is considered to be useful for the developers.
Table 11: Breakdowns of improvements
Improvement
Code fragment tracking# PRs with diﬀerent results
35

File rename detection

3

Clone change judgment by comparing token sequences

6

Total

44

50

In this experiment, we detected non-simultaneous modiﬁcations from OSS satisfying the following conditions to conﬁrm the usefulness of CLIONE for developers of diverse OSS.
• The OSS is developed in PR-based development on GitHub.
• The OSS is written in Java.
• The OSS has more than 5,000 stars on GitHub17 .
We selected OSS written in Java because we were familiar with Java so that we can easily modify
detected non-simultaneous modiﬁcations. Eventually, we created 15 PRs from 14 OSS.
Table 12 shows the list of 15 created PRs and their status as of 3/11/2020. Ten of them weremerged, one was closed, and four have been still opened. As for ten merged PRs, if the OSS
developers had used CLIONE, they could have dealt with the clones when creating the PRs. On
the other hand, one of them was closed. As for the closed PRs, the developers considered that theclones were not needed modiﬁcations while we considered that they should be modiﬁed.
In summary, though the developers need to decide whether or not to modify the code fragments,
CLIONE is useful for the developers because it can notify the developers of the code fragments tobe modiﬁed when the PR is created.

17 Star is a feature for GitHub users to save their favorite repositories.

repository has, the more popular the repository is.

51

It can be said that the more stars a

52

Name
JRuby
JUnit4
fastjson
RxJavaJenkinsGuava
Glide
libGDX
checkstyle
druid
JRuby
Druid
Zuul
JacocoJackson

URL
https://github.com/jruby/jruby/pull/6360
https://github.com/junit-team/junit4/pull/1671
https://github.com/alibaba/fastjson/pull/3444
https://github.com/reactivex/Rxjava/pull/7080
https://github.com/jenkinsci/jenkins/pull/4945
https://github.com/google/guava/pull/4036
https://github.com/bumptech/glide/pull/4353
https://github.com/libgdx/libgdx/pull/6201
https://github.com/checkstyle/checkstyle/pull/8872
https://github.com/alibaba/druid/pull/3956
https://github.com/jruby/jruby/pull/6361
https://github.com/apache/druid/pull/10414
https://github.com/Netflix/zuul/pull/900
https://github.com/jacoco/jacoco/pull/1099
https://github.com/fasterXML/jackson-core/pull/642

Table 12: List of created PRs
Modiﬁcation details
Change API
Boxing variables
Move code
Move method
Extract method
Remove dead code
Move code
Modify error message
Extract method
Change API
Remove dead code
Insert precondition
Remove dead code
Move code
Insert if statement

StatusMergedMergedMergedMergedMergedMergedMergedMergedMergedMergedClosed
Open
Open
Open
Open

4.5

Experiment 5

In experiment 5, in order to evaluate the usefulness of CLIONE for developers, we conducted aquestionnaire survey about notiﬁcation contents of CLIONE to developers. Concretely, we executed
CLIONE on past merged PRs of kGenProg [103], which is our OSS, selected ten of them as targets,and conducted a questionnaire survey on the content of notiﬁcation to four developers who createdthe PRs. Table 13 shows the list of the target PR numbers and the content of each PR. The
contents of the questionnaire are as follows.
1. Were you aware of the clones changed in this PR?
2. If you were aware of the clones, why did you not modify them (i.e., modify them simultaneously or merge them)?
3. If you have been notiﬁed of the clones from CLIONE when creating the PR, did you modify
them?
Hereafter, we introduce the responses to the questionnaire and discuss them.
In question(1), we got two responses (PR#633 and #663) that the developer was not aware of
the clone changes. Also, both responded to question (3) that they would modify the clones if they
were notiﬁed of them at the time of creating the PR. We checked the current implementation of
kGenProg, and both of the clones had been modiﬁed. Therefore, it can be said that if CLIONE
had been used, the developers would have been able to modify the code fragments to be modiﬁed
when creating the PRs.
On the other hand, we got eight responses that the developer was aware of the clone changes.
Hereafter, we classify these eight responses and discuss them in more detail. First, for the threecases (PR#154, #442, and #482), the answer to question (2) was “there is no need to merge
the clones.” We checked the clones, and all of them were about six lines. Hence, we consideredthat developers do not treat clones with a small number of lines as refactoring targets. Therefore,
Table 13: Questionnaire target PRs
PR number

How clones were changed

40

Newly added

76

Newly added

154

Newly added

442

Newly added

449

Newly added

482

Newly added

491

Newly added

496

Newly added633

Non-simultaneously modiﬁed

663

Newly added53

improving CLIONE to ﬁlter newly added clones by the number of their lines or tokens would prevent
sending such notiﬁcations that will not be useful to developers.
Second, for the two cases (PR#491 and #496), the answer to question (2) was “I thoughtmerging clones would make readability low.” The newly added clones in these PRs were clones
that performed similar processing but had diﬀerent parent classes, making it diﬃcult to pull up
the methods. Moreover, forcing to extract them into a single method could worsen the readability.
On the other hand, this may be due to the poor design of inheritance relations in the added codefragments, which makes it diﬃcult to merge clones. Actually, a refactoring that improves thedesign of the code fragments in these PRs has been conducted18 . Therefore, it can be consideredthat CLIONE can not only detect code fragments to be modiﬁed but also point out the poor designof the project.
Third, for the one case (PR#40), the answer to question (2) was “I did not dare merge the clones
for the sake of implementation speed.” This answer indicates that it depends on the developer todecide whether to merge clones or not. On the other hand, such ad hoc implementation is called
technical debt [104], which should be modiﬁed as soon as possible [105]. Creating Issue is one of
the ways of dealing with technical debt. Issue is a feature of GitHub, and we can manage tasks or
projects and ask the other developers for help using Issue. By managing tasks to modify technicaldebts as Issues, we can easily modify them later. Therefore, we consider that implementing Issue
creation function in CLIONE can support the management of such code fragments to be modiﬁed.
Fourth, for the one case (PR#76), the answer to question (2) was “It is diﬃcult to merge theclones because the types of the variables between the clones are diﬀerent.” The cause is that generalclone detectors normalize not only identiﬁer names but also type names. Therefore, if CLIONE
uses clone detectors that do not normalize type names, CLIONE can avoid detecting changes ofsuch clones that are not suitable for refactoring targets.
Finally, for the one case (PR#449), the answer to question (2) was “I wanted to merge theclones, but didn’t know how.” The clones had a common parent class, and only part of theprocess of them was diﬀerent. We checked them, and they have been merged in Template Method
Pattern [106]. In this regard, by implementing Issue creation function in CLIONE as describedearlier, developers can ask for help from other developers by creating Issue even if they ﬁnd itdiﬃcult to merge clones at the time of PR creation. In addition, he answered question (3) as“CLIONE should suggest me how to merge the clones.”
These results show that CLIONE can provide useful notiﬁcations to developers. Even if thedevelopers judge the information to be unhelpful at this point, with some improvements to CLIONE,
CLIONE can avoid providing unhelpful notiﬁcations or assist developers in other ways. Therefore,
CLIONE is useful for developers’ clone modiﬁcation support.

18 https://github.com/kusumotolab/kGenProg/pull/501

54

5

Threats to Validity

In this study, the experiments were conducted for a speciﬁc OSS. Therefore, diﬀerent results
may be obtained if diﬀerent projects are targeted. In addition, in Experiment 3, the clone tracking
results of CLIONE and Clone Notiﬁer were checked and compared manually. Therefore, the resultsof Experiment 3 may depend on our subjectivity.
CLIONE uses NiCad and SourcererCC to detect clones. If CLIONE uses other clone detectors,
the experimental results may diﬀer from this study.
Clone tracking and change classiﬁcation by CLIONE is independent of the programming language. Therefore, CLIONE can be applied to any project written in a programming language fromwhich the clone detector used by CLIONE can detect clones. However, in this study, only OSS
written in Java is used as the experimental target. Therefore, diﬀerent results may be obtained
when applying CLIONE to other languages.

55

6

Related Works

6.1

PR-based development support system

Some studies that integrate existing source code analysis techniques into PR-based development
to improve software development eﬃciency are conducted.
Alizadeh et al. proposed RefBot, a system that integrates automated refactoring into PR-based
development [107]. RefBot automatically refactors the target project every time a PR is created.
It also presents the results of the refactoring to the developer. The developer can interactively
select the following options for the refactoring done by RefBot. (1) Refactor the source code as-is.
(2) Reﬂect only the position, and the the developer does the refactoring itself. (3) Do not reﬂect
the refactoring.
Carvalho et al. proposed C-3PR, a system that integrates static analysis into PR-based development [108]. C-3PR executes existing static analysis tools on the target project for each PR
creation and automatically corrects the output warnings.
Alizadeh and Carvalho have experimented with their system in real-world development andconcluded that integrating automated refactoring and static analysis into PR-based development
is useful for developers, respectively. CLIONE is a system that integrates clone modiﬁcation support
into PR-type development, and we also concluded that CLIONE is useful for developers.
6.2

Clone modiﬁcation support

Since clones are considered one of the factors that aﬀect software maintenance, many studies
have been conducted to support clone modiﬁcations.
Nguyen et al. proposed JSync, a tool to support simultaneous modiﬁcation of clones [109]. JSync
is implemented as an Eclipse plug-in that targets Subversion repositories and automatically detects
non-simultaneous modiﬁcations of clones at commit time. It also calculates the diﬀerences in the
abstract syntax tree between the modiﬁed and unmodiﬁed clones and suggests to the developer
how to modify the clones.
Wit et al. proposed CLONEBOARD, a tool for managing clones by recording copy-and-paste
operations of code fragments [110]. CLONEBOARD is also implemented as an Eclipse plug-in.
When a copied-and-pasted code fragment is modiﬁed, the original code fragment is suggested tothe developer as the target of modiﬁcation.
The major diﬀerence between these tools and CLIONE is that CLIONE supports PR-based
development. Since PR-based development is widely adopted in today’s OSS development, weconsider supporting PR-based development highly important.
We also consider that these methods and CLIONE are not necessarily exclusive. For example,
we consider that more useful developer support can be provided by integrating JSync’s suggestionof clone modiﬁcation methods into CLIONE.

56

7

Conclusion

In this part, we proposed a clone modiﬁcation support system, CLIONE, for integration into
PR-based development. CLIONE detects code fragments that need to be modiﬁed due to clonechanges between the base commit and the head commit of a PR when the PR is created. We also
made three improvements to the clone tracking method used by Clone Notiﬁer in order to trackclones more accurately. Five experiments were conducted to evaluate CLIONE from three diﬀerent
perspectives. The experimental results showed that CLIONE is useful for PR-based development
and developer, and CLIONE can also track clones more accurately than Clone Notiﬁer.
As a future work, we plan to improve the implementation of CLIONE. Speciﬁcally, as describedin Section 4.5, we plan to implement a function to ﬁlter out clones that are not suitable forrefactoring, create Issue, and recommend how to modify code fragments detected by CLIONE.

57

Part IV

Measurement Reducible Lines of Code
Based on Automated Merging Clones

58

1

Background

Changes are occasionally (or even continuously) added to the source code after software systems
have been released. A bunch of changes to the source code deteriorates its quality (e.g., collapsing
its design, decreasing the readability), so that the maintenance cost gets more expensive [111–113].
The maintenance cost of the source code is often estimated from its size or complexity [113]. In
the case of large-scale software systems, an enormous amount of money is required. If users of asoftware system can estimate its number, they should be able to decide whether they continue to
use it or replace it with a new one [114].
A factor of deteriorating the quality of source code is the presence of clones. Clones get involvedin both software development and maintenance [115,116]. The presence of clones makes the sourcecode redundant so that inconsistencies in source code tend to happen unintentionally [54]. Thus,
from the perspective of maintainability of the source code, merging clones is important.
Merging clones is a well-known refactoring. Refactoring is deﬁned as a set of operations toimprove the internal structure of the source code without altering its external behavior [26]. Extract
Method refactoring, which is one of the most often performed refactorings, is a set of operations
to extract a code fragment in an existing method as a new method. If duplicated code fragments
are extracted as a new method, the duplication is removed from the source code. Removing clones
by refactoring makes it easier to keep consistencies in the source code because we do not have to
put the same changes on duplicated code in multiple places. However, there is a possibility thatrefactoring itself introduces a new bug in the source code [27]. Consequently, removing all clones
without any special reason is not realistic: a reasonable indicator is required whether or not given
clones should be refactored. The number of lines of code (LoC) reduced by refactoring clones areused for the indicator.
An existing study proposed a technique to estimate how many LoC can be reduced by refactoring clones [33] The existing technique judges whether clones can be refactored or not using
JDedorant [34], which Tsantalis et al. developed, and calculates reducible LoC based on the linesof refactorable clones. The technique utilizes the position information of clones (the path of the ﬁleincluding a given clone, start line and end line of the given clone). If multiple clones are overlappedwith each other, the technique selects only one of them using the greedy algorithm.
However, we think there are two issues in the existing technique.
• The ﬁrst issue is that the existing technique does not correctly judge whether or not a clone
can be refactored. In JDeodorant, several conditions are set and only the clones that match
all the conditions are judged to be refactorable. However, even if a clone matches all theconditions set by JDeodorant, there is a possibility that it cannot be refactored. It is also
considered that refactoring is possible even for clones that do not meet the criteria [33]. On
the other hand, it is not realistic to manually check the refactorability of all the large numberof clones detected, as this would require a lot of eﬀort.
• The second issue is that in the case that clones are overlapping, the existing technique only
considers merging one of the overlapped clones. However, even if two clones are overlapping,both of them may be able to be merged. Thus, an estimated reducible LoC may become acompletely diﬀerent number from the actual reducible LoC.

59

Therefore, in this part, we propose a new technique to calculate reducible LoC. The proposed
technique performs a loop of (1) detecting clones, (2) removing a set of clones, and (3) compilingand testing the edited source code as long as the LoC of the source code gets decreased by the
refactorings. Due to its nature, the proposed technique is completely free from the above twoissues. We implemented a software tool based on the proposed technique and applied it to several
open source software systems. The purpose of the application is comparing the proposed techniqueto the existing one. As a result, we conﬁrmed that the proposed technique was able to measure
reducible LoC more correctly than the existing technique.

60Preprocessing
source file changes
Input

Step1:
Detecting clone sets…
Original
source files

CS_1

Editedsource files

Clone Sets
CS_n

CS_2

Step2:
Editing source files

EditidSource files…
50 LoC
decreases

30 LoC
decreases

10 LoC
decreases

Step3:
Compiling and Testing…

Compilation andtest results

No
Terminate?

Step4:
SelectingYes
Output• source files whose all target clones are merged• reducible LoC

Figure 18: Overview of proposed technique2

Proposed Technique

We propose a new technique to calculate LoC that can be reduced by merging clones. The
technique repeats (1) detecting clones, (2) editing source ﬁles, (3) compiling, and (4) testing. This
technique enables users to obtain actual LoC that can be reduced by merging clones, not justestimating it. Moreover, this technique has an important feature: even if multiple clones areoverlapped, the technique tries to merge each of them while the existing study [33] only considers
one of the overlapped clones. The reasone why the proposed technique can deal with overlapped
clones is the technique performs clone detection and editing source ﬁles repeatedly. For example,
in the case of ﬁgure 8(a), in which clone A contains clone B, the technique ﬁrst merges clone A
and then detect clones again. Therefore, the technique can try to merge clone B, which have been
contained in clone A. Figure 18 shows an overview of the proposed technique. The input of thetechnique is a set of source ﬁles. The output is a set of source ﬁles in which clones have been
merged as much as possible and their reducible LoC. Please note that this technique does notmerge clones if merging them does not reduce LoC of the source ﬁles.
The technique is composed of two processes shown below. Both the processes are performed
fully automatically.
• Preprocessing source ﬁle changes

61• Clone merging
2.1

Preprocessing source ﬁle changes

First, a new class is generated. The new class is used as a utility class for placing merged clones.
More concretely, each merged clone is declared as a static method in the class. Besides, target
source ﬁles are edited to avoid compile error due to uninitialized local variables. Additionally, thesource ﬁles are reformatted to avoid inconsistencies of reducible LoC due to coding style. In total,
four changes are made in Preprocessing source ﬁle changes.
2.2

Clone merging

Clone merging is composed of four steps shown below. All of the steps are performed fully
automatically.
Step1: detecting clone sets
Step2: editing source ﬁles
Step3: compiling and testing edited source ﬁles
Step4: selecting edited source ﬁles
In Step1, clone sets in the target source ﬁles are detected. In Step2, source ﬁles are edited tomerge one of the clone sets that were detected in Step1. A method extracted to merge clones isplaced in the Java class described in Subsection 2.1. In Step3, the source ﬁles edited in Step2 arecompiled and tested to verify the external behavior. Hereafter, we call edited source ﬁles which
succeed in compiling and testing and whose LoC gets reduced selectable source ﬁles. Step2 andStep3 are performed on each of the clone sets detected in Step1. In Step4, the selectable source
ﬁles whose reduced LoC is the largest is selected. Then, Step1–Step4 are repeatedly performedon the selected source ﬁles. When either of the following termination conditions is satisﬁed, clone
merging terminates and outputs the reducible LoC.
• No clone sets are detected.
• No source ﬁles edited in Step2 are selectable.

62

3

Implementation
We implement our technique as a tool. The tool is written in Java and targets Java source ﬁles.

3.1

Preprocessing source ﬁle changes

3.1.1

Generating a new Java class

A class in which extracted methods are placed is newly generated. When the extracted methodin the new class is called from the original place, it is invoked with its fully qualiﬁed name.
3.1.2

Initializing local variables

On the Java language speciﬁcation, it is prohibited to reference uninitialized local variables.
Thus, when an uninitialized local variable is passed to the extracted method as an argument, acompile error occurs. Developers may initialize local variables and pass them to the method whendevelopers merge clones. In this part, all local variables which do not have final modiﬁer andare uninitialized at the time of their declaration are initialized. In the case that the local variable
is primitive type except for boolean type, it is initialized as 0. In the case of boolean type, it isinitialized as false. In the case of reference type, it is initialized with null.
3.1.3

Reformatting

In general, coding conventions are speciﬁed in each project. For example, some conventions
specify using many line breaks and other conventions specify a small number of line breaks. If
code fragments of convention violation exist, it is diﬃcult to calculate a reducible LoC properly.
Figure 19 shows examples in which diﬀerent reducible LoC are calculated due to the coding style.
Figure 19(a), Extract Method refactoring reduces 5 LoC, but Figure 19(b), Extract Method
refactoring reduces 4 LoC. Thus, it is necessary to unify coding style by using formatter. In an
ideal world, we should prepare the formatters which reproduce coding conventions of each of thetarget projects, but of course, it is impossible. Thus, we use the default Eclipse formatter [117].
3.2

Clone merging

3.2.1

Step 1: Detecting clone sets

Figure 20 shows an example of detecting clones. Clones are detected in block level. We regard
the following statements as blocks. Each following statement is deﬁned as a derived class of class
Statement in Eclipse JDT [118].
• Block• DoStatement• EnhancedForStatement• ForStatement• IfStatement

63

1
2
3
4
5
6

if (a > b){
int temp = a;a = b;
b = temp;
}

1
2
3
4
5
6
1

- if (a > b)
- {int temp = a;a = b;
b = temp;- }+ method(a, b);

1
2
3
4
5

if (a > b) {int temp = a;a = b;
b = temp;
}

1
2
3
4
5
1

- if (a > b) {int temp = a;a = b;
b = temp;- }+ method(a, b);(a) 5 LoC reduce(b) 4 LoC reduce

Figure 19: Diﬀerent reducible LoC• SwitchStatement• SynchronizedStatement• TryStatement• WhileStatement
Block-level clones are more coarse-grained than clones that are detected by token-based techniques. The number of block-level clones is less than the number of token-based clones [119].
However, block-level clones have a remarkable feature, which is that they are better candidatesof Extract Method refactoring because the code fragments are syntactic chunks [5]. The proposed
technique uses Eclipse JDT to parse source ﬁles and identify blocks. If a block includes a returnstatement, it is not detected as a clone because it is diﬃcult to extract it as a new method [120].
The proposed technique normalizes identiﬁed blocks according to the rules shown below because
the larger number of clones can be detected by applying the rules.
• Identiﬁers are normalized as “$” + “number”.
• The same identiﬁer is normalized as the same normalized name.
• All literals are normalized as “$”.
64

Blocks

Normalizing

Hashing Comparing
Clonesif (a > b) {int temp = a;a = b;
b = temp;}

if ($0 > $1) {int $2 = $0;$0 = $1;$1 = $2;
}

1234

1234

if (x > y) {int tmp = x;x = y;
y = tmp;}if ($0 > $1) {int $2 = $0;$0 = $1;$1 = $2;
}

1234

1234

...

if ($0 < $1) {int $2 = $1;$1 = $0;$0 = $2;
}

...

...

...

if (i < j) {int tmp = j;j = i;
i = tmp;
}

5678

5678

Figure 20: Clone detection• Qualiﬁed names are normalized as identiﬁers.
• Class name is not normalized.
• Method name is not normalized.
The same identiﬁer is normalized as the same normalized name to avoid false detection as muchas possible. The reason why class and method names are not normalized is to avoid detecting clones
whose diﬀerences are class or method names because it is diﬃcult to merge clones with diﬀerent
type names or calling methods.
After the normalization, a hash value is calculated from each block. The proposed techniqueuses SHA256 hashing algorithm [121]. Since SHA256 outputs 256-bit hash value, hash collisions
hardly occur.
Finally, the proposed technique compares the hash values of blocks to detect blocks of the samehash values as clones.
3.2.2

Step 2: Editing source ﬁlesUsing Extract Method refactoring on one of the clone sets detected in Step1, source ﬁles areautomatically edited. Figure 21 shows an example of automatically editing source ﬁles.
It is possible to reduce LoC because each of the clones is replaced to a method invocation by
extracting clones as a method. This extracted method is declared as a static method in the classmade in Preprocessing source ﬁles changes (see Section 3.1). The method is invoked with its fully
qualiﬁed name.
65Clone setsif (a > b) {int temp = a;a = b;
b = temp;}

Edited source code

Replacing method callpass by reference

if (x > y) {int temp = x;x = y;
y = temp;}

int[] a0 = {a}, a1 = {b};extracted(a0, a1);
a = a0[0]; b = a1[0];int[] a2 = {x}, a3 = {y};extracted(a2, a3);
x = a2[0]; y = a3[0];Extracted and declaredvoid extracted(int[] p0,int[] p1){
if (p0[0] > p1[0]) {int temp = p0[0];p0[0] = p1[0];p1[0] = temp;}}

Figure 21: Editing source ﬁles

In practice, we need to take care of changes of variables on Extract Method refactoring. For
example, when only one of the variables is changed in the code fragment, Extract Method refactoring
can be performed by returning the variable and assigning it in the caller place. However, in theJava language speciﬁcation, it is impossible to return two or more parameters simultaneously.
Extract Method refactoring on such clones is not realistic. Unfortunately, examining whether or
not each variable is changed in the target code fragment requires deep source code analysis. Thus,
In this part, we implemented our tool to pass arguments by reference to the extracted method tokeep the external behavior. Our tool uses an array type to pass arguments by reference. Before
invoking the extracted method, arrays whose types are the same of variables in the target codefragment are newly deﬁned and initialized with each of the values. These arrays are passed to themethod. In the method, the array element at index zero is referenced. After invoking the method,each array element at index zero is assigned back to each variable. These processes are devices of
implementation for automated refactoring, not for manual refactoring.
3.2.3

Step 3: Compiling and testing edited source ﬁles

In Step3, source ﬁles edited in Step2 are compiled and tested. At ﬁrst, compilation is performed.
After compilation gets success, test runs. If both compilation and test get success, edited source

66

ﬁles are recorded as selectable source ﬁles. If either compilation or test fails, edited source ﬁles are
not recorded.
3.2.4

Step 4: Selecting edited source ﬁlesAfter Step2 and Step3 are performed on each of the clone sets detected in Step1, Step4 is
performed. In Step4, the selectable source ﬁles whose reduced LoC is the largest is selected. Then,
Step1–Step4 are repeatedly performed on the selected source ﬁles.

67

4

Experiment4.1

Overview

In order to evaluate the proposed technique, we applied the proposed technique to open source
projects and compared the results obtained with the results of the existing technique. We also
investigated the diﬀerences between the clone sets merged by the proposed technique and theexisting technique. In this part, we selected the same ﬁve projects as the existing study [33],except for Columba and Xerces, which could not be compiled on our environment19 . Table 14
shows the names, versions, and total number of LoC of the target projects. In this experiment, weomitted the test code and tutorial code of the projects. The number of LoC was measured after
applying the formatter described in Section 3.1.3.
4.2
4.2.1

Experimental results
Comparison with the existing technique

Table 15 shows the number of merged clone sets, the number of reduced LoC, the execution
time as the results of executing the proposed technique, and the table also shows the numberof refactorable clone sets and the number of estimated reducible LoC as the results of executing
the existing technique. As shown from the table, in all projects, the number of clone sets actuallymerged by the proposed technique is smaller than the number of clone sets estimated as refactorable
by the existing technique. In addition, for all projects except jEdit, the number of reduced LoC
measured by the proposed technique is smaller than the number of reducible LoC estimated by
the existing technique. We considered that this is because JDeodorant judged many of the clone
sets that did not pass compilation or testing when merged to be refactorable, and as a result, theexisting technique estimated the number of LoC that can be reducible for those clone sets. Table 16
shows the number of clone sets that pass compilation and testing when merged (CS 1 in the table),for which the proposed technique measures the number of LoC to be reduced, and the table also
shows the number of clone sets that JDeodorant judges as refactorable (CS 2 in the table), forwhich the existing technique estimates the number of lines to be reduced, and their CS 2 in thetable), the number of clone sets that JDeodorant judged to be refactorable (CS 2 in the table). As
shown from the table, for each project, the number of clone sets that pass compilation and testing
when merged is less than the number of clone sets judged to be refactorable by JDeodorant. Hence,
Table 14: Experimental targets
Name

Version# Total LoC

Ant

1.10.7

231,634

jEdit

5.5.0

161,329

JFreeChart

1.5.0

210,823

JMeter.Core

5.2

82,360

JRuby.Core9.2.9.0

360,724

19 Ubuntu 18.04, OpenJDK 1.8.0 222, Ant 1.10.5, CPU: 8 cores 3.6GHz, Memory: 64GB

68

the number of reduced lines measured by the proposed technique may be lower than the number of
reducible lines estimated by the existing technique. However, since the proposed technique merges
only the clone sets that pass the compilation and testing when merged, the proposed technique
can measure the number of reduced LoC more accurately than the existing technique.

69

70

# Detected CS
583
421
810
103
747

Name

Ant

jEdit

JFreeChart

JMeter.Core

JRuby.Core

54

15

176

58

15

570

47

1491

548

456

1h 40m

10m

2h 54m34m

1h 15m

Proposed technique# Merged CS # Reduced LoC Execution time

Table 15: Results of comparison

210

34

250

91

155

1142

115

1963

494

1246

Existing technique# Refactorable CS # Reducible LoC

Only targeted by
the proposed technique30

Only targeted by
the existing technique28

Not targeted by either technique
300

63

Targeted byboth techniques

Figure 22: Venn diagram representing clone sets that are targeted to merge by the proposed
technique and/or the existing one

4.2.2

Investigation of diﬀerences in clone sets targeted to merge by each technique

The reason for the diﬀerence in the number of LoC reduced in the Section 4.2.1 is that the clone
sets targeted to merge are diﬀerent when calculating the number of reduced LoC. Therefore, weinvestigated the diﬀerence in the clone sets targeted to merge by each technique. We selected theclone sets detected from jEdit as the target. Figure 22 shows the diﬀerence in the number of clone
sets merged by the proposed technique and the number of clone sets estimated as refactorable by
the existing technique. As shown from the ﬁgure, the clone sets merged by the proposed techniqueand the clone sets estimated as refactorable by the existing technique have some clone sets incommon but also have some diﬀerent clone sets. As an example, we introduce total of four clone
sets that were targeted to merge by the proposed technique but not by the existing technique andthat were targeted to merge by the existing technique but not by the proposed technique, viceversa.
Figure 23 is a code fragment in org/gjt/sp/jedit/Buffer.java that is a clone of a codefragment in org/gjt/sp/jedit/View.java. The variables waitSocket used in this source codeare both of type Socket. In the proposed technique, this set of clones was successfully compiled
and tested after merging (i.e., it is actually refactorable). On the other hand, the existing techniquejudged that this clone set was not refactorable. JDeodorant, which is used in the existing technique,has several conditions to determine which clones can be refactored. One of the conditions is that“ﬁeld variables cannot be parameterized.” The variable websocket used in Figure 23 is a ﬁeld
variable, that condition was violated, and the existing technique was considered the clone set to71

1600 if (waitSocket != null) {1601 try {1602
waitSocket.getOutputStream().write('¥0');1603
waitSocket.getOutputStream().flush();1604
waitSocket.getInputStream().close();1605
waitSocket.getOutputStream().close();1606
waitSocket.close();1607 } catch {IOException e) {1608// Log.log(Log.ERROR,this,io);1609 }
1610 }
Figure 23: Example of a clone that was actually refactorable, but the existing technique did ottarget to merge because the variables in the clones were ﬁeld variables

be not refactorable. Thus, there were clone sets that the existing technique judged to be notrefactorable because it violated JDeodorant’s condition. However, they were actually refactorable,
and the proposed technique was able to merge them to measure reduced LoC.
Figure 24 shows a code fragment in org/gjt/sp/gui/ExtendedGridLayout.java, which is aclone (hereafter, clone A) of a code fragment in the same class. This clone set consisted of twocode fragments. On the other hand, the code fragments in lines 775–779, 781–785, and 787–792 of
Figure 24 are also clones (hereafter, clone B). This clone set consisted of six code fragments. In thisexample, clone A contains clone B. Using the formula (4) described in section 2.10, we can expect
a reduction of 16 lines when merging clone A and 17 lines when merging clone B. Therefore, theexisting technique that uses the greedy algorithm only targeted clone B and was not able to target
clone A. On the other hand, the proposed technique was able to both clone A and B, because it
ﬁrst merged clone B and then detects clone A after replacing the code fragment of clone B with amethod call. Thus, there were clone sets that were not targeted to merge by the existing technique
due to the greedy method but were merged by the proposed technique.
Figure 25 is a code fragment in org/gjt/sp/jedit/GUIUtilities.java, which is a clone of thecode fragment in org.gjt.sp.jeit.gui.ActionBar.java. Both classes had dispose methods,
but there was no inheritance relationship between the two classes. Therefore, the clone set was
Table 16: The number of CS 1 and CS 2
Name

# CS 1# CS 2# Intersection

Ant

225

292

105

jEdit

163

211

118

JFreeChart

377

539

275

JMeter.Core

48

68

40

JRuby.Core

60

396

40

72

773 for (int col = fromCol; col < toCol; col++) {774 int minimumColWidth = minimumColWidths[col];775 if ((Integer.MAX_VALUE - minimumColWidth) < ...) {776
currentMinimumColWidth = Integer.MAX_VALUE;777 } else {778
currentMinimumColWidth += minimumColWidth;
779 }780 int preferredColWidth = preferredColWidths[col];781 if ((Integer.MAX_VALUE - preferredColWidth) < ...) {782
currentPreferredColWidth = Integer.MAX_VALUE;
783 } else {784
currentPreferredColWidth += preferredColWidth;
785 }786 int maximumColWidth = maximumColWidths[col];787 if ((Integer.MAX_VALUE - maximumColWidth) < ...) {788
currentMaximumColWidth = Integer.MAX_VALUE;
789 } else {790
currentMaximumColWidth += maximumColWidth;
791 }
792 }
Figure 24: Example of a clone that the existing technique did not target to merge because ofoverlapping

not refactorable. However, the existing techniques judged that the clone sets were refactorable andtargeted them to merge. On the other hand, since the proposed technique failed to compile sourcecode after merging, the clone set was excluded from the targets to merge.
Figure 26 is a code fragment in org/gjt/sp/jedit/TextUtilities.java, which is a cloneof a code fragment in the same class. This clone set was judged to be not refactorable by the
proposed technique because it failed to compile source code after merging. However, the clone set
was judged to be refactorable by the existing technique. The variable buf is used in lines 965, 966,
969, and 972 of this code fragment. In one of the two code fragments in the clone set, the typeof buf variable is StringBuilder, while in the other, the type of buf variable is StringBuffer.
Both of these two types inherit from the AbstractStringBuilder class. Therefore, the clone set
can be refactored by declaring the parameter of an extracted method as AbstractStringBuffer
type. On the other hand, since the proposed technique is implemented to generate a method fromone of the code fragments in the clone set as described in 3.2.2, it is diﬃcult to declare the typesof the parameters in an abstract way. This is one of the future works in the implementation.
In summary, though the proposed technique needs some implementation improvements, compared to the existing technique, the proposed technique calculates the number of reduced LoC byusing only the clone sets that can be merged. In other words, the proposed technique can calculate
the number of reduced LoC more accurately than the existing technique.

73

1324 if (splash != null) {1325 splash.dispose();1326 splash = null;
1327 }
Figure 25: Example of a clone that was actually not refactorable because of the type of the variable
between the clones has no inheritance relationship, but hte existing technique targeted to merge

961 String word = st.nextToken();
962 if (lineLength == leadingWhitespaceWidth) {963 // do nothing964 } else if (lineLength + word.length() + 1 > ...) {965 buf.append('¥n');
966 buf.append(leadingWhitespace);
967 lineLength = leadingWhitespaceWidth;
968 } else {969 buf.append(' ');970 lineLength++;971 }972 buf.append(word);
973 lineLength += word.length();Figure 26: Example of a clone that was actually refactorable, but the proposed technique did nottarget to merge because our implementation are insuﬃcient74

5

Limitations

5.1

Limitations in executing the proposed techniqueIn this part, we showed that the proposed technique was able to calculate the number of reduced
LoC more accurately than the existing technique. However, when the conditions for calculating
the number of reducible LoC are limited, it is necessary to use the existing technique instead of
the proposed technique. For such situations, we discuss the execution environment and execution
time of both techniques.
5.1.1

Limitations in the execution environment

In order to execute the proposed technique, the target software must be compiled and tested.
Therefore, it is diﬃcult to execute the proposed technique if the environment for compiling andtesting the target software is limited and the number of computers that can provide the environment
is limited. In such a case, the existing technique should be used.
On the other hand, in order to execute the existing technique, the external tools CCFinderX [41]and JDeodorant [34] are required to run the existing technique. Therefore, if the uses do not havethe equipment to use these external tools, they should use the proposed technique.
5.1.2

Limitations in the execution time

In this part, we showed that the proposed technique was able to measure the number of reduced
LoC more accurately than the existing technique for software with hundreds of thousands of LoC
in a practical time. Therefore, we consider that the proposed technique should be used instead ofthe existing technique for software with hundreds of thousands of LoC.
On the other hand, the proposed technique should not be used to measure the number of
reducible LoC for large software that requires a long time to compile and test. This is because
the proposed technique repeatedly compiles and tests the software and thus may not be able tomeasure the number of reduced LoC in a practical time. The proposed technique can be used when
the target software uses incremental builds, which makes the second and subsequent compile andtest faster. However, in other cases, the use of the existing technique should be considered.
5.2

Limitations in the implementation

In this part, various limitations are given to the implementation of the proposed technique.
The limitations given are as follows.
5.2.1

All extracted methods are declared in one class

In our implementation, all methods extracted by refactoring are declared in a single class. This
reason this limitation was given that when merging clones that span multiple classes, we thought
it would be diﬃcult to automatically determine the class to declare the extracted methods. Whenthe developer performs refactoring, the extracted method will be declared in the appropriate classbased on the developer’s judgment.

75

5.2.2

Clones are detected block by block

In our implementation, the clones are detected in block-level. The reason this limitation wasgiven is that we considered that clones detected in block-level are easier to extract as a method.
When developers conduct the refactoring, not only blocks but also continuous statement lines aretargeted to refactor.
5.2.3

Code fragments that contain return statements are not detected as clones

In our implementation, code fragments that contain return statements are not detected as clones.
The reason this limitation was given is that we thought it would be diﬃcult to automatically
perform extract method on code fragments that contain return statements. This limitation does
not mean that developers will not refactor the clones that contain return statement.
5.2.4

Arguments are passed by reference to the extracted method

In the implementation of this part, arguments are passed by reference to the extracted methods.
This is because we thought it would be diﬃcult to automatically determine whether the variables
given as arguments are changed in the method. When developers conduct refactoring, they should
check whether the variables given as arguments are changed in the method and return the variable
that is changed in the method.

76

6Conclusion

In this part, we proposed a technique to measure the number of reduced LoC more accurately
based on the results of clone refactoring. The proposed technique repeatedly and automatically
performs clone detection, merging them, source code compilation, and testing on the target sourcecode. The experimental results show that the proposed technique can merge only clones thatcan be actually refactored and to calculate the number of reduced LoC more accurately than theexisting technique.
The following subsections are our future works.
Utilizing other refactoring patterns
At this moment, the proposed technique utilizes Extract Method pattern to remove clones.
However, there are various ways to remove clones: for example, Pull Up Method or Form Template
Method. Considering other refactoring patterns to remove clones, calculated reducible LoC will get
closer to the real value when developers appropriately remove clones.
Improving the implementation
As described in Section 4.2.2, we encountered compilation errors in the experiment. However,most of such compilation errors are avoidable if we devise an implementation. If we do so, we will
be able to get better reducible LoC.
Measuring the execution time on large software
In this part, we showed that the proposed technique was able to measure the number of reduced
LoC in a practical time for software with hundreds of thousands of LoC. On the other hand, we did
not measure the execution time for large-scale software that requires a long time for compilationand testing. It is important to conﬁrm whether or not the proposed technique can be applied tosuch software in the future.

77

Acknowledgements
This thesis has been completed with the help of many people.
First of all, I would like to appreciate my supervisor, Professor Shinji Kusumoto. I was very
fortunate to be able to do research under him. His support was very diverse, such as daily research
activities, attending conferences, and submitting papers. Moreover, he has been a sympathetic
supporter of mine and always cheered me up.
I would like to express the most gratitude to Associate Professor Yoshiki Higo. A large partof this thesis has been made possible with his three years of dedicated and meticulous guidance.
His advice was sometimes too stern to be painful for me, but it has steadily made me grow.
Thanks to his support, I have eventually been able to decide on a research topic and conducted
the experiments on my own.
I would like to express my deep appreciation for Assistant Professor Shinsuke Matsumoto. I
was greatly inspired by his philosophy, aesthetics, and presentation technique. Thanks to him, mywriting, diagram, and presentation skills have been greatly improved. I think these skills will be
useful after graduation.
I would like to express my thanks to Tomoko Kamiya, a clerical assistant. She took care of theclerical works so that I was able to focus on my research.
I would like to appreciate Professor Katsuro Inoue because the many studies he has done were
the driving force behind my own research. Moreover, he gave me much helpful advice in various
situations, such as Computer Science Seminar.
I would like to express my thanks to Ryo Arima, Akito Tanikado, Keigo Naito, Hiroyuki
Matsuo, and Miwa Sasaki, who graduated in 2019. They mentored me as a newcomer to Kusumotolaboratory. Without their help, my research would not have been as successful as it was.
My deep appreciation goes to Hiroto Tanaka, Masayuki Doi, Nozomi Nakajima, and Junnosuke
Matsumoto, who graduated in 2020. They have been a great help to me over the past two years.
Especially, Masayuki Doi supported my research activities, such as writing papers and Junnosuke
Matsumoto gave much technical advice to me. My foundation of research activities has consistedof the knowledge they gave. I would like to greater gratitude to them.
I would like to much appreciation for ﬁrst-year master’s students, Naoto Ichikawa, Ryoko Izuta,
Sho Ogino, Akira Fujimoto, and Aoi Maejima and fourth-year undergraduate students, Masashi
Iriyama, Kanta Kotou, Masayuki Taniguchi, Tomoaki Tsuru, and Hiroto Watanabe, for theirgrateful support. Thanks to their eﬀorts to improve the laboratory environment, I was able to
do my research comfortably. I was also able to gain valuable experience in teaching the younger
students.
I would like to express my special thanks to second-year master’s students, Hideaki Azuma,
Tetsushi Kuma, Yuya Tomida, and Kaisei Hanayama. I spent the longest time with them inKusumoto laboratory. Their presence has been a great encouragement to me in my long laboratory
life. Especially, Yuya Tomida was generous with his technical support for me. I am very fortunate
to have good friends.
Finally, I sincerely appreciate my parents for their 24-years support.

78

References[1] Richard N Burns and Alan R. Dennis. Selecting the appropriate application development
methodology. ACM SIGMIS Database: the DATABASE for Advances in Information Systems, 17(1):19–23, 1985.
[2] Rajiv D Banker, Srikant M Datar, Chris F Kemerer, and Dani Zweig. Software complexity
and maintenance costs. Communications of the ACM, 36(11):81–95, 1993.
[3] Alexander J Rostkowycz, Václav Rajlich, and Andrian Marcus. A case study on the longterm eﬀects of software redocumentation. In Proceedings of 20th IEEE International Conference on Software Maintenance, pages 92–101, 2004.
[4] Manishankar Mondal, Md Saidur Rahman, Ripon K Saha, Chanchal K Roy, Jens Krinke, andKevin A Schneider. An empirical study of the impacts of clones in software maintenance. In
Proceedings of 2011 IEEE 19th International Conference on Program Comprehension, pages
242–245, 2011.
[5] Yoshiki Higo, Yasushi Ueda, Toshihro Kamiya, Shinji Kusumoto, and Katsuro Inoue. On
Software Maintenance Process Improvement Based on Code Clone Analysis. In Proceedingsof International Conference on Product Focused Software Process Improvement, pages 185–
197, 2002.
[6] Ghazi Alkhatib. The maintenance problem of application software: An empirical analysis.
Journal of Software Maintenance: Research and Practice, 4(2):83–104, 1992.
[7] Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. Genprog: A
generic method for automatic software repair. Ieee transactions on software engineering,38(1):54–72, 2011.
[8] Matias Martinez and Martin Monperrus. Astor: Exploring the design space of generateand-validate program repair beyond genprog. Journal of Systems and Software, 151:65–80,
2019.
[9] W Eric Wong, Ruizhi Gao, Yihao Li, Rui Abreu, and Franz Wotawa. A survey on software
fault localization. IEEE Transactions on Software Engineering, 42(8):707–740, 2016.
[10] Rui Abreu, Peter Zoeteweij, and Arjan JC Van Gemund. On the accuracy of spectrum-based
fault localization. In Proceedings of Testing: Academic and industrial conference practice andresearch techniques-MUTATION, pages 89–98, 2007.
[11] Marco D’Ambros, Michele Lanza, and Romain Robbes. An extensive comparison of bug
prediction approaches. In Proceedings of 2010 7th IEEE Working Conference on Mining
Software Repositories, pages 31–41, 2010.
[12] Cagatay Catal and Banu Diri. A systematic review of software fault prediction studies.
Expert systems with applications, 36(4):7346–7354, 2009.
[13] Tom Mens and Tom Tourwé. A survey of software refactoring. IEEE Transactions on
software engineering, 30(2):126–139, 2004.
79

[14] Frank Simon, Frank Steinbruckner, and Claus Lewerentz. Metrics based refactoring. In
Proceedings 5th european conference on software maintenance and reengineering, pages 30–
38. IEEE, 2001.
[15] Mark Weiser. Program slicing. IEEE Transactions on software engineering, (4):352–357,
1984.
[16] Keith Brian Gallagher and James R Lyle. Using program slicing in software maintenance.
IEEE transactions on software engineering, 17(8):751–761, 1991.
[17] Elmar Juergens, Florian Deissenboeck, Benjamin Hummel, and Stefan Wagner. Do code
clones matter? In Proceedings of 2009 IEEE 31st International Conference on Software
Engineering, pages 485–495, 2009.
[18] Bruno Lague, Daniel Proulx, Jean Mayrand, Ettore M Merlo, and John Hudepohl. Assessing the beneﬁts of incorporating function clone detection in a development process. In
Proceedings International Conference on Software Maintenance, pages 314–321, 1997.
[19] Stefan Bellon, Rainer Koschke, Giulio Antoniol, Jens Krinke, and Ettore Merlo. Comparison and evaluation of clone detection tools. IEEE Transactions on software engineering,33(9):577–591, 2007.
[20] Chanchal Kumar Roy and James R Cordy. A survey on software clone detection research.
Queen’s School of Computing TR, 541(115):64–68, 2007.
[21] Andrew Walker, Tomas Cerny, and Eungee Song. Open-source tools and benchmarks forcode-clone detection: past, present, and future trends. ACM SIGAPP Applied Computing
Review, 19(4):28–39, 2020.
[22] Abdullah Sheneamer and Jugal Kumar Kalita. A Survey of Software Clone Detection Techniques. International Journal of Computer Applications, 2016.
[23] Hitesh Sajnani, Vaibhav Saini, Jeﬀrey Svajlenko, Chanchal K Roy, and Cristina V Lopes.
SourcererCC: Scaling code clone detection to big-code. In Proceedings of the 38th International Conference on Software Engineering, pages 1157–1168, 2016.
[24] Yoshiki Higo, Yasushi Ueda, Shinji Kusumoto, and Katsuro Inoue. Simultaneous Modiﬁcation Support based on Code Clone Analysis. In Proceedings of 14th Asia-Paciﬁc Software
Engineering Conference, pages 262–269, 2007.
[25] Yoshiki Higo, Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue. Refactoring support
based on code clone analysis. In Proceedings of International Conference on Product Focused
Software Process Improvement, pages 220–233, 2004.
[26] Martin Fowler. Refactoring: improving the design of existing code. Addison-Wesley Professional, 2018.
[27] Miryung Kim, Thomas Zimmermann, and Nachiappan Nagappan. A ﬁeld study of refactoring challenges and beneﬁts. In Proceedings of the ACM SIGSOFT 20th International
Symposium on the Foundations of Software Engineering, pages 1–11, 2012.
80

[28] Tasuku Nakagawa, Yoshiki Higo, and Shinji Kusumoto. CLIONE: Clone Modiﬁcation Support for Pull Request Based Development. In Proceedings of the 27th Asia-Paciﬁc Software
Engineering Conference, pages 455–459, 2020.
[29] Shogo Tokui, Norihiro Yoshida, Eunjong Choi, and Katsuro Inoue. Clone Notiﬁer: Developing and Improving the System to Notify Changes of Code Clones. In Proceedings of 2020
IEEE 27th International Conference on Software Analysis, Evolution and Reengineering,
pages 642–646, 2020.
[30] Yuki Yamanaka, Eunjong Choi, Norihiro Yoshida, Katsuro Inoue, and Tateki Sano. Applying
clone change notiﬁcation system into an industrial development process. In Proceedings of2013 21st International Conference on Program Comprehension, pages 199–206, 2013.
[31] Yuki Yamanaka, Eunjong Choi, Norihiro Yoshida, Katsuro Inoue, and Tateki Sano. Industrial Application of Clone Change Management System. In Proceedings of the 6th International Workshop on Software Clones, pages 67–71, 2012.
[32] Tasuku Nakagawa, Yoshiki Higo, Matsumoto Junnosuke, and Shinji Kusumoto. Measurement Reducible Lines of Code Based on Automated Merging Code Clones. IPSJ Journal,2021 (to appear).
[33] Takuya Ishizu, Norihiro Yoshida, Eunjong Choi, and Katsuro Inoue. Analyzing the Amountof Reducible Source Code Based on the Refactorability of Software Clones. IPSJ Journal,
60(4):1051–1062, 2019.
[34] Nikolaos Tsantalis, Davood Mazinanian, and Giri Panamoottil Krishnan. Assessing
the Refactorability of Software Clones. IEEE Transactions on Software Engineering,41(11):1055–1090, 2015.
[35] Norihiro Yoshida, Takuya Ishizu, Bufurod Edwards III, and Katsuro Inoue. How slim will
my system be? estimating refactored code size by merging clones. In Proceedings of the 26th
Conference on Program Comprehension, pages 352–360, 2018.
[36] Pengcheng Wang, Jeﬀrey Svajlenko, Yanzhao Wu, Yun Xu, and Chanchal K Roy. CCAligner:a token based large-gap clone detector. In Proceedings of the 40th International Conference
on Software Engineering, pages 1066–1077, 2018.
[37] Ming Wu, Pengcheng Wang, Kangqi Yin, Haoyu Cheng, Yun Xu, and Chanchal K Roy.
LVMapper: A Large-variance Clone Detector Using Sequencing Alignment Approach. IEEE
Access, 8:27986–27997, 2020.
[38] J Howard Johnson. Substring Matching for Clone Detection and Change Tracking. In
Proceedings of 1994 International Conference on Software Maintenance, pages 120–126, 1994.
[39] Stéphane Ducasse, Matthias Rieger, and Serge Demeyer. A language independent approachfor detecting duplicated code. In Proceedings of IEEE International Conference on Software
Maintenance, pages 109–118, 1999.
[40] Simian. https://www.harukizaemon.com/simian/.
81

[41] Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue. CCFinder: A Multilinguistic
Token-Based Code Clone Detection System for Large Scale Source Code. IEEE Transactions
on Software Engineering, 28(7):654–670, 2002.
[42] Zhenmin Li, Shan Lu, Suvda Myagmar, and Yuanyuan Zhou. CP-Miner: Finding copy-paste
and related bugs in large-scale software code. IEEE Transactions on software Engineering,32(3):176–192, 2006.
[43] Rakesh Agrawal and Ramakrishnan Srikant. Mining sequential patterns. In Proceedings ofthe 11th International Conference on Data Engineering, pages 3–14, 1995.
[44] Ira D Baxter, Andrew Yahin, Leonardo Moura, Marcelo Sant’Anna, and Lorraine Bier. Clone
detection using abstract syntax trees. In Proceedings of International Conference on Software
Maintenance, pages 368–377, 1998.
[45] Rainer Koschke, Raimar Falke, and Pierre Frenzel. Clone detection using abstract syntax
suﬃx trees. In Proceedings of 2006 13th Working Conference on Reverse Engineering, pages
253–262, 2006.
[46] Lingxiao Jiang, Ghassan Misherghi, Zhendong Su, and Stephane Glondu. DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones. In Proceedings of the 29th International Conference on Software Engineering, pages 96–105, 2007.
[47] Loı̈c Paulevé, Hervé Jégou, and Laurent Amsaleg. Locality sensitive hashing: A comparisonof hash function types and querying mechanisms. Pattern recognition letters, 31(11):1348–
1358, 2010.
[48] Raghavan Komondoor and Susan Horwitz. Using Slicing to Identify Duplication in Source
Code. In Proceedings of Static Analysis, pages 40–56, 2001.
[49] Jens Krinke. Identifying similar code with program dependence graphs. In Proceedings
Eighth Working Conference on Reverse Engineering, pages 301–309, 2001.
[50] Yoshiki Higo and Shinji Kusumoto. Code Clone Detection on Specialized PDGs with Heuristics. In Proceedings of 2011 15th European Conference on Software Maintenance and Reengineering, pages 75–84, 2011.
[51] James R Cordy and Chanchal K Roy. The NiCad Clone Detector. In Proceedings of 2011
IEEE 19th International Conference on Program Comprehension, pages 219–220, 2011.
[52] James R Cordy. The TXL source transformation language. Science of Computer Programming, 61(3):190–210, 2006.
[53] Kazuki Yokoi, Eunjong Choi, Norihiro Yoshida, and Katsuro Inoue. Investigating Vectorbased Detection of Code Clones Using BigCloneBench. In Proceedings of 2018 25th AsiaPaciﬁc Software Engineering Conference, pages 699–700, 2018.
[54] Miryung Kim, Vibha Sazawal, David Notkin, and Gail Murphy. An empirical study ofcode clone genealogies. In Proceedings of the 10th European software engineering conference
held jointly with 13th ACM SIGSOFT international symposium on Foundations of software
engineering, pages 187–196, 2005.
82

[55] Yue Yu, Huaimin Wang, Vladimir Filkov, Premkumar Devanbu, and Bogdan Vasilescu.
Wait for it: Determinants of pull request evaluation latency on github. In Proceedings of2015 IEEE/ACM 12th working conference on mining software repositories, pages 367–371,
2015.
[56] Oleksii Kononenko, Tresa Rose, Olga Baysal, Michael Godfrey, Dennis Theisen, and Bart
De Water. Studying pull request merges: a case study of shopify’s active merchant. In Proceedings of the 40th International Conference on Software Engineering: Software Engineeringin Practice, pages 124–133, 2018.
[57] Georgios Gousios, Martin Pinzger, and Arie van Deursen. An exploratory study of the pullbased software development model. In Proceedings of the 36th International Conference on
Software Engineering, pages 345–355, 2014.
[58] Nikolaos Tsantalis, Davood Mazinanian, and Shahriar Rostami. Clone refactoring withlambda expressions. In Proceedings of 2017 IEEE/ACM 39th International Conference on
Software Engineering, pages 60–70, 2017.
[59] Keisuke Hotta, Yoshiki Higo, and Shinji Kusumoto. Identifying, tailoring, and suggesting
form template method refactoring opportunities with program dependence graph. In Proceedings of 2012 16th European Conference on Software Maintenance and Reengineering,
pages 53–62, 2012.
[60] Rainer Koschke. Survey of research on software clones. In Dagstuhl Seminar Proceedings.
Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2007.
[61] Hou Min and Zhang Li Ping. Survey on software clone detection research. In Proceedingsof International Conference on Management Engineering, Software Engineering and Service
Sciences, page 9–16, 2019.
[62] Aakanshi Gupta and Bharti Suri. A Survey on Code Clone, Its Behavior and Applications. In
Proceedings of Networking Communication and Data Knowledge Engineering, pages 27–39,
2018.
[63] Manishankar Mondal, Chanchal K Roy, and Kevin A Schneider. A survey on clone refactoring
and tracking. Journal of Systems and Software, 159:110429, 2020.
[64] Salah Bouktif, Giuliano Antoniol, Ettore Merlo, and Markus Neteler. A Novel Approach to
Optimize Clone Refactoring Activity. In 1885-1892, editor, Proceedings of the 8th annual
conference of Genetic and Evolutionary computation, 2006.
[65] Lingxiao Jiang, Zhendong Su, and Edwin Chiu. Context-based detection of clone-relatedbugs. 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,
pages 55–64, 2007.
[66] Debarshi Chatterji, Jeﬀrey C Carver, Beverly Massengil, Jason Oslin, and Nicholas A Kraft.
Measuring the Eﬃcacy of Code Clone Information in a Bug Localization Task: An Empirical83

Study. In Proceedings of 2011 International Symposium on Empirical Software Engineeringand Measurement, pages 20–29, 2011.
[67] Miryung Kim, Vibha Sazawal, David Notkin, and Gail Murphy. An Empirical Study of CodeClone Genealogies. In Proceedings of the 10th European software engineering conference
held jointly with 13th ACM SIGSOFT international symposium on Foundations of software
engineering, pages 187–196, 2005.
[68] Takashi Ishio, Yusuke Sakaguchi, Kaoru Ito, and Katsuro Inoue. Source File Set Search
for Clone-and-Own Reuse Analysis. In Proceedings of 2017 IEEE/ACM 14th International
Conference on Mining Software Repositories, pages 257–268, 2017.
[69] Mathieu Nayrolles and Abdelwahab Hamou-Lhadj. CLEVER: Combining Code Metrics
with Clone Detection for Just-in-Time Fault Prevention and Resolution in Large Industrial
Projects. In Proceedings of the 15th International Conference on Mining Software Repositories, pages 153–164, 2018.
[70] Jeﬀrey Svajlenko and Chanchal K Roy. CloneWorks: A Fast and Flexible Large-Scale NearMiss Clone Detection Tool. In Proceedings of International Conference on Software Engineering Companion, pages 177–179, 2017.
[71] Guanhua Li, Yijian Wu, Chanchal K Roy, Jun Sun, Xin Peng, Nanjie Zhan, Bin Hu, andJingyi Ma. SAGA: Eﬃcient and Large-Scale Detection of Near-Miss Clones with GPU Acceleration. In Proceedings of 2020 IEEE 27th International Conference on Software Analysis,
Evolution and Reengineering, pages 272–283, 2020.
[72] Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoﬀrey Zweig. Syntactic
clustering of the web. Computer Networks and ISDN Systems, 29(8):1157–1166, 1997.
[73] Donald Ervin Knuth. The art of computer programming. Pearson Education, 1997.
[74] Benjamin Hummel, Elmar Juergens, Lars Heinemann, and Michael Conradt. Index-based
code clone detection: incremental, distributed, scalable. In Proceedings of 2010 IEEE International Conference on Software Maintenance, pages 1–9, 2010.
[75] Lasse Bergroth, Hakonen Harri, and Raita Timo. A survey of longest common subsequencealgorithms. In Proceedings of 7th International Symposium on String Processing and Information Retrieval, pages 39–48, 2000.
[76] James W. Hunt and Thomas G. Szymanski. A Fast Algorithm for Computing Longest
Common Subsequences. Communications of the ACM, 20(5):350––353, 1977.
[77] Jeﬀrey Svajlenko and Chanchal K Roy. BigCloneEval: A Clone Detection Tool Evaluation
Framework with BigCloneBench. In Proceedings of 2016 IEEE International Conference on
Software Maintenance and Evolution, pages 596–600, 2016.
[78] Jeﬀrey Svajlenko and Chanchal K Roy. Evaluating clone detection tools with BigCloneBench.
In Proceedings of 2015 IEEE International Conference on Software Maintenance and Evolution, pages 131–140, 2015.
84

[79] Jeﬀrey Svajlenko and Chanchal K Roy. The Mutation and Injection Framework: Evaluating
Clone Detection Tools with Mutation Analysis. IEEE Transactions on Software Engineering,
pages 1–1, 2019.
[80] Ming Wu, Pengcheng Wang, Kangqi Yin, Haoyu Cheng, Yun Xu, and Chanchal K. Roy.
LVMapper: A Large-variance Clone Detector Using Sequencing Alignment Approach, 2019.
[81] Katsuro Inoue, Yuya Miyamoto, Daniel M German, and Takashi Ishio. Code Clone Matching:
A Practical and Eﬀective Approach to Find Code Snippets. arXiv preprint arXiv:2003.05615,
2020.
[82] Ambient Software Evolution Group:
seclone.

IJaDataset 2.0.

http://secold.org/projects/[83] CLOC. http://cloc.sourceforge.net/.
[84] Farouq Al-Omari, Chanchal K Roy, and Tonghao Chen. SemanticCloneBench: A Semantic
Code Clone Benchmark using Crowd-Source Knowledge. In Proceedings of International
Workshop on Software Clones, pages 57–63, 2020.
[85] Yusuke Yuki, Yoshiki Higo, Keisuke Hotta, and Shinji Kusumoto. Generating clone references with less human subjectivity. In Proceedings of International Conference on Program
Comprehension, pages 1–4, 2016.
[86] Tiantian Wang, Mark Harman, Yue Jia, and Jens Krinke. Searching for Better Conﬁgurations: A Rigorous Approach to Clone Evaluation. In Proceedings of the 2013 9th Joint
Meeting on Foundations of Software Engineering, page 455–465, 2013.
[87] Jeanne Ferrante, Karl J Ottenstein, and Joe D Warren. The program dependence graphand its use in optimization. ACM Transactions on Programming Languages and Systems,
9(3):319–349, 1987.
[88] Yue Zou, Bihuan Ban, Yinxing Xue, and Yun Xu. Ccgraph: a pdg-based code clone detector
with approximate graph matching. In Proceedings of 2020 35th IEEE/ACM International
Conference on Automated Software Engineering, pages 931–942, 2020.
[89] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M
Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9),2011.
[90] Gehan MK Selim, King Chun Foo, and Ying Zou. Enhancing Source-Based Clone Detection
Using Intermediate Representation. In Proceedings of 2010 17th Working Conference on
Reverse Engineering, pages 227–236, 2010.
[91] Soot. http://soot-oss.github.io/soot/.
[92] Pedro M Caldeira, Kazunori Sakamoto, Hironori Washizaki, Yoshiaki Fukazawa, andTakahisa Shimada. Improving Syntactical Clone Detection Methods through the Use ofan Intermediate Representation. In Proceedings of 2020 IEEE 14th International Workshop
on Software Clones, pages 8–14, 2020.
85

[93] Vaibhav Saini, Farima Farmahinifarahani, Yadong Lu, Pierre Baldi, and Cristina V. Lopes.
Oreo: Detection of Clones in the Twilight Zone. In Proceedings of the 2018 26th ACM Joint
Meeting on European Software Engineering Conference and Symposium on the Foundationsof Software Engineering, pages 354—-365, 2018.
[94] CCFinderX. http://www.ccfinder.net/.
[95] Tomoya Ishihara, Keisuke Hotta, Yoshiki Higo, Hiroshi Igaki, and Shinji Kusumoto. InterProject Functional Clone Detection Toward Building Libraries - An Empirical Study on
13,000 Projects. In Proceedings of 2012 19th Working Conference on Reverse Engineering,
pages 387–391, 2012.
[96] Elmar Juergens, Florian Deissenboeck, and Benjamin Hummel. Clonedetective—a workbench for clone detection research. In Proceedings of 2009 IEEE 31st International Conference on Software Engineering, pages 603–606, 2009.
[97] Manziba Akanda Nishi and Kostadin Damevski. Scalable code clone detection and searchbased on adaptive preﬁx ﬁltering. Journal of Systems and Software, 137:130–142, 2018.
[98] Joseph Feller and Brian Fitzgerald. Understanding Open Source Software Development.
Addison-Wesley Longman Publishing Co., Inc., USA, 2002.
[99] GitHub Apps. https://developer.github.com/apps/.
[100] Tasuku Nakagawa, Yoshiki Higo, Junnosuke Matsumoto, and Shinji Kusumoto. How Compact Will My System Be? A Fully-Automated Way to Calculate LoC Reduced by Clone
Refactoring. In Proceedings of 2019 26th Asia-Paciﬁc Software Engineering Conference,
pages 284–291, 2019.
[101] Chaiyong Ragkhitwetsagul and Jens Krinke. Using compilation/decompilation to enhanceclone detection. In Proceedings of 2017 IEEE 11th International Workshop on Software
Clones, pages 1–7, 2017.
[102] Kyohei Uemura, Akira Mori, Eunjong Choi, and Hajimu Iida. Tracking Method-Level Clones
and a Case Study. In Proceedings of 2019 IEEE 13th International Workshop on Software
Clones, pages 27–33. IEEE, 2019.
[103] Yoshiki Higo, Shinsuke Matsumoto, Ryo Arima, Akito Tanikado, Keigo Naitou, Junnosuke
Matsumoto, Yuya Tomida, and Shinji Kusumoto. kGenProg: A High-performance, Highextensibility and High-portability APR System. In Proceedings of 2018 25th Asia-Paciﬁc
Software Engineering Conference, pages 697–698, 2018.
[104] Philippe Kruchten, Robert L Nord, and Ipek Ozkaya. Technical Debt: From Metaphor to
Theory and Practice. IEEE Software, 29(6):18–21, 2012.
[105] Francesca Arcelli Fontana, Vincenzo Ferme, and Stefano Spinelli. Investigating the impact
of code smells debt on quality code evaluation. In Proceedings of 2012 3rd International
Workshop on Managing Technical Debt, pages 15–22, 2012.

86

[106] Erich Gamma. Design patterns: elements of reusable object-oriented software. Pearson
Education India, 1995.
[107] Vahid Alizadeh, Mohamed Amine Ouali, Marouane Kessentini, and Meriem Chater. RefBot:
Intelligent Software Refactoring Bot. In Proceedings of 2019 34th IEEE/ACM International
Conference on Automated Software Engineering, pages 823–834, 2019.
[108] Antônio Carvalho, Welder Luz, Diego Marcı́lio, Rodrigo Bonifácio, Gustavo Pinto, andEdna Dias Canedo. C-3PR: A Bot for Fixing Static Analysis Violations via Pull Requests.
In Proceedings of 2020 IEEE 27th International Conference on Software Analysis, Evolution
and Reengineering, pages 161–171, 2020.
[109] Hoan Anh Nguyen, Tung Thanh Nguyen, Nam H Pham, Jafar Al-Kofahi, and Tien N Nguyen.
Clone Management for Evolving Software. IEEE Transactions on Software Engineering,38(5):1008–1026, 2011.
[110] Michiel De Wit, Andy Zaidman, and Arie Van Deursen. Managing code clones using dynamicchange tracking and resolution. In Proceedings of 2009 IEEE International Conference on
Software Maintenance, pages 169–178, 2009.
[111] Bennett P. Lientz and E. Burton Swanson. Software Maintenance Management. AddisonWesley Longman Publishing Co., Inc., 1980.
[112] Stephen G Eick, Todd L Graves, Alan F Karr, J Steve Marron, and Audris Mockus. Does
code decay? assessing the evidence from change management data. IEEE Transactions on
Software Engineering, 27(1):1–12, 2001.
[113] Thomas M. Pigoski. Practical Software Maintenance: Best Practices for Managing Your
Software Investment. Wiley Publishing, 1st edition, 1996.
[114] Harry M. Sneed. Planning the reengineering of legacy systems. IEEE software, 12(1):24–34,
1995.
[115] Anfernee Goon, Yuhao Wu, Makoto Matsushita, and Katsuro Inoue. Evolution of code clone
ratios throughout development history of open-source C and C++ programs. In Proceedingsof 2017 IEEE 11th International Workshop on Software Clones, pages 1–7, 2017.
[116] Rainer Koschke and Saman Bazrafshan. Software-clone rates in open-source programs written in C or C++. In Proceedings of 2016 IEEE 23rd International Conference on Software
Analysis, Evolution, and Reengineering, volume 3, pages 1–7, 2016.
[117] Eclipse. https://www.eclipse.org/.
[118] Eclipse Java development tools. https://www.eclipse.org/jdt/.
[119] Keisuke Hotta, Jiachen Yang, Yoshiki Higo, and Shinji Kusumoto. How Accurate Is Coarsegrained Clone Detection?: Comparison with Fine-grained Detectors. In Inproceedings of 8thInternational Workshop on Software Clones, pages 1–18, 2 2014.

87

[120] Raghavan Komondoor and Susan Horwitz. Eﬀective, automatic procedure extraction. In
Proceedings of 11th IEEE International Workshop on Program Comprehension, pages 33–42,
2003.
[121] National Institute of Standards and Technology. Secure Hash Standard. 2015.

88Appendix

89

A

Available ﬁlesAn executable ﬁle of NIL https://zenodo.org/record/4492665
Source code of NIL https://github.com/kusumotolab/NIL
Manual validation descriptions of large-variance clones https://zenodo.org/record/4490845.
Large-variance clones used in Section 3.3.2 https://zenodo.org/record/4491016.
Clones used in Section 3.4.1 https://zenodo.org/record/4491052.
Manual validation descriptions of general clones https://zenodo.org/record/4493069.
Codebases with various sizes https://zenodo.org/record/4491208.
Source code of CLIONE https://github.com/T45K/CLIONE

90

B

Hunt-Szymanski Algorithm

Algorithm 2: Hunt-Szymanski Algorithm
Input: element array A[1 : n], B[1 : n];
Output: Printing the LCS between A and B
1: // Identiﬁers
2: integer array T HREASH[0 : n];
3: list array M AT CHLIST [1 : n];
4: pointer array LIN K[1 : n];
5: pointer P T R;
6: // Step 1: build linked list
7: for i := 1 step 1 until n do
8:
set list array M AT CHLIST [i] := ⟨j1 , j2 , . . . , jp ⟩ such thatj1 > j2 > . . . > jp and A[i] = B[jq ] for 1 ≤ q ≤ p;
9: end for
10: // Step 2: initialize T HREASH array
11: T HREASH[0] := 0;
12: for i := 1 step 1 until n do
13:
T HREASH[i] := n + 1;
14: end for
15: LIN K[0] := null;
16: // Step 3: compute successive T HREASH values
17: for i := 1 step 1 until n do
18:
for all j on M AT CHLIST [i] do
19:
ﬁnd k such that T HREASH[k − 1] < j ≤ T HREASH[k];20:
if j < T HREASH[k] then21:
T HREAS[k] := j;
22:
LIN K[k] := newnode(i, k, LIN K[k − 1]);23:
end if24:
end for
25: end for
26: // Step 4: recover the LCS in reverse order
27: k := largestksuchthatT HREASH[k] ̸= n + 1;
28: P T R := LIN K[k];29: while P T R ̸= null do
30:
print (i, j) pair pointed to by P T R;
31:
advance P T R;
32: end while

91

C

List of Publications
1. Tasuku Nakagawa, Yoshiki Higo, Junnosuke Matsumoto, and Shinji Kusumoto. Measurement Reducible Lines of Code Based on Automated Merging Code Clones. IPSJ Journal,2021 (to appear).
2. TasukuNakagawa, Yoshiki Higo, and Shinji Kusumoto. CLIONE: Code Clone Modiﬁcation
Support System aimed to integrate into Pull Request Based Developement. IEICE Journal,2021 (conditional accepted).
3. Tasuku Nakagawa, Yoshiki Higo, Junnosuke Matsumoto, and Shinji Kusumoto. How Compact Will My System Be? A Fully-Automated Way to Calculate Loc Reduced by Clone
Refactoring. In Proceedings of the 26th Asia-Paciﬁc Software Engineering Conference, pages
284–291, 2019.
4. Tasuku Nakagawa, Yoshiki Higo, and Shinji Kusumoto. CLIONE: Clone Modiﬁcation Support for Pull Request Based Developement. In Proceedings of the 27th Asia-Paciﬁc Software
Engineering Conference, pages 455–459, 2020.

92