Finding Code-Clone Snippets in Large
Source-Code Collection by ccgrep
Katsuro Inoue1, Yuya Miyamoto1,Daniel M. German2, and Takashi Ishio3
1: Osaka University
2: University of Victoria
3: Nara Institute of Science and Technology
1
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Ternary Operator in Linux USB Driver Filelinux/drivers/usb/gadget/function/u_ether.c...
1003
1004
1005
1006
1007
1008
1009
1010

{
int ret;rtnl_lock();
ret = snprintf(name, len, "%s¥n",
netdev_name(net));rtnl_unlock();
return ret < len ? ret : len;}...

Returns the minimum of two.
Should be changed tomin(ret, len)

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

2

Using grep

ret < len ? ret : len;$ grep '<' -r .
./misc/chaoskey.c: * Copyright © 2015 Keith Packard <keithp@keithp.com>./misc/chaoskey.c:#include <linux/module.h>./misc/chaoskey.c:#include <linux/slab.h>...

16,335 matches in linux/drivers/usb/*$ grep '<' -r . | grep '?'| grep ':'./host/oxu210hp.h:#define QTD_STS_PING(1 << 0) /* issue PING? */./misc/usbtest.c:? (INTERRUPT_RATE << 3)./misc/usbtest.c:
return (retval < 0) ? retval : -EDOM;...

149 matches in linux/drivers/usb/*
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

3

Using Clone Detector

ret < len ? ret : len;

Installing CCFinderX
Works on Java 5 ~ 8, but not 11 or later

Requires Python 2.6, not 2.7 or 3.X
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

4Simple Tool
$ tool –r .
ret < len ? ret : len;

Copy and Paste Snippet./misc/adutux.c:
int amount =bytes_to_read < data_in_secondary ?
bytes_to_read :data_in_secondary;./storage/realtek_cr.c:residue=residue < buf_len ? residue:buf_len;./gadget/function/u_ether.c:
Query Seed Snippet
return ret < len ? ret : len;
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

5Motivation• Find similar code snippets• Similar bug finding, code refactoring, ...

• grep is too primitive• Code clone detector generally– Requires complex installation and environment setting– Generates excessive output• Simple tool to find similar code snippets

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

6

ccgrep (Code Clone grep)• Use notion of code clone for matching• Query and matched snippet forms a code clone pair oftype 1, 2, or 3
TargetSourceccgrepQuery
SnippetMatchedSnippets

Code Clone Pair(type 1, 2, or 3)
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

7Type Classification of Code Clone Pairs
Two code snippets with differences of• Type 1: spaces, line breaks, or comments• Type 2: replacement of identifiers or literals (+ type 1)• Type 3: some statement additions, deletions, or changes(+ type 2)• Type 4: syntax but semantics are equivalent

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

8Type 2 Clone Match• Basis and default of ccgrep• Allows differences of identifiers or literals• P-(parameterized)match (consistent mapping)

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

9Type 1 Matching• Same snippets with different spaces, line-breaks, comments• Give an option (-b none) or fix identifier/literal in the query with meta
symbol $Seed:

int a= 0 ;Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

10Type 3 Matching• Allows statement additions, deletions, or changes• Employ meta tokens $. and $$$.

Any single token$$ Any token sequence

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

11Matching Various Code Snippets

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

12Formal Definition of Matching(Appendix Table 3)

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

13Architecture of ccgrep
MetaToken
Definition

Language
Definition

Tokenizer
Generator

Tokenizer
Generator

Tokenizer
Generation(executed onlyonce for eachlanguage)Java, C, C++, Python

Implemented by Antlr and Java
single JAR file on Windows or Unix
Map Table

Query

Tokenizer
TokenSequence

TargetOption

Tokenizer

CCMatcher

OutputFormatter

OutputTokenSequence

ccgrepSoftware Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

14

Evaluation of ccgrep• RQ1: Query ExpressivenessAre various kinds of code clones expressed by thequeries?
• RQ2: Accuracy
Does it accurately find clones already detected by otherapproaches?
• RQ3 : Performance
What is the execution time?
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

15

RQ1: Query Expressiveness
Query for• Type 1 clone: seed snippet plus an option or $id or $literal• Type 2 clone: seed snippet (P-match as default)(Non P-match à by option)• Type 3 clone: seed snippet with meta tokens ($., $$, or $#) at
addition, deletion, or change points
All queries for type 1, 2, and 3 clones are effectively expressed

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

16

RQ2: Accuracy• Type 1 and 2: 53K clones in BigCloneBench– Made one snippet of each clone pair as query
Successfully found another snippet in each case

• Finding 11 type 3 clones for CBCD data[16]– Crafted the query from one snippet in each clone pair to match
another snippet
Successfully found another snippet in each case[16] Li, J., Ernst, M.D.: Cbcd: Cloned buggy code detector. In: 2012 34th International Conference on Software Engineering (ICSE). pp. 310{320 (June 2012).
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University17

RQ3: PerformanceQuires

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

18

Result of RQ3
Sufficiently fast andacceptable as asearch tool even forlarge targets

grep
generally 3~9 times
faster, but it misses
multiple-line resultsIntel Xeon E5-1603v4(@2.8GHz 4), 32GB RAM, and Windows 10 Pro for WS 64bit
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

19

Related works• grep-like tools– agrep, cgrep, sgrep, ... extend grep’s feature– coccigrep is data-structure based matching
No idea of clone-based matching• Pattern matching tools– CBCD (PDG based matching to find buggy code)– NCDSearch (similarity by compression distance)– Siamese (index of methods or files)
No precise control of the matching

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

20

Conclusion• Proposed clone-based pattern matching tool ccgrep– Effectively finds type 1, 2, and 3 clone snippets• ccgrep is OSS on GitHub
https://github.com/yuy-m/CCGrep

Future direction• Improve the matching algorithm• Add a small GUI to edit query from the seed snippet

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

21

Thank you!
Question?

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University22•-b,--blind <LEVEL> set blind level.
• none(Type 1) / consistent(p-match)(by default) / full(Type 2).
•-e <PATTERN> use PATTERN for matching.
•--exclude <FILE_PATTERN> skip files matching FILE_PATTERN.
•-f,--file <FILES> obtain query from file.
• CANNOT give query as code string at once.
•--fix <ID> specify identifier to match exactly the same one.
•-h,--help show help.
•ignore-extension search all files ignoring file extensions.
•--include <FILE_PATTERN> search ONLY files that match FILE_PATTERN.
•--json print clones and execution information with JSON format.
•-l,--language <LANG> set target language.
• c / c++ / java(by default) / python3.
• With -f option, the language can be inferred from the file extension.
•-m,--max-count <NUM> stop after NUM clones.
•--no-messages suppress error messages.
•--no-overlap search without overlap.
23•-p,--print <OPTION> set printing option c/l/n/f/e like -p fn.
• If c is given, print the count of clones file by file.
• If C is given, print ONLY the count of all clones.
• If l is given, print ONLY file name per matched files.
• If h is given, NOT print file names.
• If n is given, print line numbers.
• If N is given, print pairs of start and end line number.
• If f is given, print whole code of clones.
• If r is given, print whole code of clones in one line.
• If o is given, print only the matched parts of a clone code.
• If e is given, comment out the file name and line numbers.
•--parallel search each file in parallel.
•-r,--recursive traverse directories recursively.
•-s,--stdin-query obtain query from standard input. CANNOT give query as code string at once.
•-x,--file-match force QUERY to match only whole file.
•--xml print clones with XML format.
24