日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

Attempts on Finding Cross-Language CodeClones based on Text and AST Information
DAI Feng, Shigeru CHIBA
Currently, there are no concrete deﬁnitions of what is a code clone. It could refer to a pair of code pieces thathave similar structures, or it could also refer to a pair of code pieces that implement similar functionality.
Such ambiguity is especially signiﬁcant under cross-language scenario, as diﬀerent programming languages
have diﬀerent syntax and grammar. However, most existing works do not recognize the ambiguity, andevaluate their approaches on inappropriate datasets, making their approaches for cross-language code clone
detection unreliable. In this paper, we develop several evaluation procedures and provide better datasetsfor robust evaluation of cross-language code clone detection task. To be speciﬁc, we focus on detecting
method-level code clones instead of entire code ﬁles. We also develop our model based on two similarity
measurements, and use non-dominated ranking system to select optimal code clone pairs. Our approach
can provide better performance under our new evaluation procedures.

crete deﬁnition of a code clone in academia so far.

1 Introduction[6] gives an explanation of four types of code clones.

Code clone detection is a valuable research topic,

But they are more like an induction instead of aas it can help to refactor and improve the main-deﬁnition. This leads to a disadvantage of current

tainability of large code bases. Duplicated code

literature tackling this problem.

fragments can be diﬃcult to maintain if there is an

However, when researchers try to expand the re-error in such code fragments. Nowadays, the num-search to cross-language scenario, the disadvantage

ber of programming languages is increasing, and abecomes more signiﬁcant. As diﬀerent program-system can be implemented in multiple program-ming languages have diﬀerent syntax and grammar,

ming languages. Under such scenario, repetitions

it is diﬃcult to say what is similar across two codeof source code functionality in diﬀerent program-pieces. Is a pair of code pieces sharing same struc-ming languages are unavoidable. Therefore, an ef-

ture a code clone? Or do they have to share same

fective cross-language code clone detection tool isfunctionality to be called a code clone? It can bedesirable.

seen that there is not a clear objective about what

When we say code clones, we are normally talking

to detect when it comes to detecting cross-language

about two fragments of source code, either in samecode clones. Unfortunately, most existing works dolanguage or diﬀerent languages, that are syntacti-

not recognize the problem, making their detection

cally or semantically similar to each other. How-models unreliable.

ever, there is no consensus about what is the con-There are two main reasons for the unreliability.
First, existing approaches, whether machine learn-

戴峰、千葉滋, 東京大学情報理工学系研究科, Graduate
School of Information Science and Technology, The
University of Tokyo.

ing based or non-machine learning based, base theirevaluation on competitive programming datasets,

such as Leetcode or AtCoder. This kind of datasets
usually contains solutions to many individual algorithm problems. The solutions are implemented
by diﬀerent programmers, and do not necessarily
share similar structures or even functionality. However, existing approaches treat such pairs of solutions as clones. This is inappropriate and unreliable. Second, most approaches calculate similarity
score based on single similarity measurement suchas text-similarity or AST-similarity. They either
treat source code as simple natural language text

図1

Java code of groupRecordsByUsers()

and symbols, or do not consider diﬀerent abstract
syntax grammar for diﬀerent languages. Further-in the ﬁeld.

more, they naively apply machine learning models
for the calculation.

2 Motivation

In this paper, we present two main contribu-

One of the most common scenarios that codetions for this topic. First, we come up with newclones happen is that programmers use multi-

evaluation procedures and develop new datasets

ple programming languages in a single applica-

to avoid the drawbacks of competitive program-tion project. For example, programmers may use

ming datasets. Current competitive programming

JavaScript for Web client and switch to Java fordataset uses entire code ﬁles, but we focus on

mobile client. We present a simple case which ismethod-level code pieces. Our datasets are more

often encountered in real development. In the de-appropriate for code clone detection evaluation.

velopment of a shopping record management sys-

Second, we design a new multi-modal model. We

tem, we want to add a feature to group shopping

consider both text-based similarity and AST-based

records by users’ id, and sort the groups by thesimilarity, and train each machine learning modeltime of most recent record in each group. More-

individually.

The models have clear objectives

over, in each group, all the records are sorted byabout what is similar across two code pieces. Af-

the time of each record. That is, we want a list

ter getting similarity scores, we use non-dominatedof groups as a result. All the records in the sameranking system to select optimal code clone pairs,

group are from the same user. Both the groups andso that each similarity measurement is equally con-the records in each group are sorted by time. Sincesidered. We believe our model works better under

this feature is not part of the initial design, we only

new evaluation procedures.

have an API that returns a list of unsorted records

The rest of the paper is organized as follow. In

from diﬀerent users in the form of an HTTP GET

section 2, we will introduce the motivation of our

endpoint. As the API is restricted, we need to im-

research. In section 3, we will introduce the overall

plement the feature from the front end side. We

structure of our model and each component of ourshow the implementation in JavaScript and Java inmodel. In section 4, we will introduce the evalua-Fig.2 and Fig.1. JavaScript code is for Web clientstion procedures and how we organize the datasets.

and Java code is for Android clients. In the code,

In section 5, we will show some existing literature

the logic is exactly the same even there are some

図2

JavaScript code ofgroupRecordsByUsers()

semantic diﬀerences. We ﬁrst sort all the records
by time in the list of records. Then we initialize alist of groups and assign each record to its corresponding group. Finally we sort the groups by eachgroup’s most recent record time. This is almost an
ideal example for a cross-language code clone. The

図3

Java code of a clone in existing dataset

structure is similar and the functionality is same.
In practice, there might be some slight changes inboth structure and functionality, but a valid clone
must consider both structural similarity and functionality. Currently, existing evaluation datasets
contain a lot of invalid pairs of code according tothis criteria.
In Fig.3 and Fig.4, we give an example of clone inexisting competitive programming dataset. We believe this pair of code is inappropriate to be called

図4

Python code of a clone in existing dataset

a clone for following reasons. First, they both contain multiple methods, and each of them implement

larity and AST path-based similarity. In this sec-

diﬀerent functionality. Second, they are diﬀerent

tion, we will introduce the structure of our model.

in structure judged by human expert.

We currently divide our model into two sub-parts,

Existing

dataset contains a lot of such pairs.

each of which is related to one similarity measurement. We use a non-dominated ranking system to

3 Model Detailchoose the code pair with the highest similarity

Existing models are not capable of ﬁnding clones

score. Since non-dominated ranking system sup-mentioned in Sec.2. This is because they have aports multiple objectives, our model can be ex-unclear deﬁnition of code clone and consider sin-tendable for more similarity measurements. The

gle similarity measurement. To solve this problem,

overview of our model is illustrated in Fig.5. Somewe propose our model with multiple similarity mea-

important parts are introduced as follow.

surements. To be speciﬁc, we use text-based simi-

3. 2 Generic AST design
Diﬀerent programming languages have diﬀerent
abstract syntax grammars. The node deﬁnition of
diﬀerent syntax trees is diﬀerent. This will leadto fewer anchor points, and cause lower eﬃciency
for training.

The solution we propose is to de-sign a generic abstract grammar for multiple languages. While designing, we make a trade-oﬀ be図5

Model structure overview

tween the level of adaption for diﬀerent languages,
and the simplicity of grammar size. The designing logic here is we preserve common node for bothlanguages, and preserve some key language-speciﬁc
nodes. The common nodes include control structures, operators, variables and class and function
deﬁnition. For some examples of key nodes, we in-

図6

How to get sub-tokens of source code

clude Switch, Do-While node for Java, and List
Comprehension node for Python. There are more

3. 1 Text-based similarity

such kind of language-speciﬁc key nodes for both

Text-based similarity is most frequently used. It

languages. Therefore, generic ASTs obtained frombasically works as what a lexical analyzer does.

two languages are not exactly same. To emphasize,

It treats source code as a sequence of sub-tokens.

we keep key language-speciﬁc nodes so that impor-

The sub-tokens are achieved by adopting byte-pairtant information would not be lost when transfer-encoding algorithm. The advantage of BPE algo-ring an AST to a generic AST.

rithms is that it can avoid rare tokens, and reduce
the size of vocabulary signiﬁcantly. We use Trans-

3. 3 AST path-based similarity

former as base model and train the model in an un-

AST-based similarity gives more consideration tosupervised way. The common tokens such as key-code structure. Given the AST of a code snippet,words and symbols can serve as anchor points in

instead of using depth-ﬁrst search or Breadth-ﬁrst

vector space. Therefore, the higher similarity thatsearch algorithm to represent a tree, we consider

ﬁnal representation of source code pieces share, theall pairwise paths between terminals, and represent

more they are similar in text manner. Fig.6 gives

them as sequences of terminal and non-terminal

an example to get sub-tokens of source code. Af-

nodes. This idea is originally proposed by an exist-

terwards, we use Transformer as base to train a

ing work called code2vec [1]. The idea is shownmasked language model of source code and get vec-in Fig.7. In an abstract syntax tree, leaves are

tor representation of code pieces. The similarity

identiﬁers in source code. Consider the three Javascore of two code pieces is calculated by cosine sim-

methods in Fig.8. These methods share a similar

ilarity equation.

syntactic structure: they all have a single parameter named target, iterate over a ﬁeld named elements, and have an if condition inside the loop
body. Therefore, if we extract such a path fromthe AST, this path can capture the main function-must consider both structural similarity and func-

ality of the method. The method iterates over ationality. Therefore, we work on method-level codeﬁeld called elements, and for each of its values itclone detection and organize our datasets based on

checks an if condition; if the condition is true, thethis criteria. We design two evaluation procedures

method returns something. From this example, we

for a complete and robust evaluation and we or-can see that AST paths are very representative toganize datasets for each evaluation procedure in-indicate the syntactic structure of a piece of source

dividually. Our evaluation procedures are bettercode.

in evaluating performance of cross-language code

In detail, we represent each of the path nodes

clone detectors.

and leaf values of a path context as real-valued vector representation, or known as embeddings. Then,

4. 1 Competitive programming evaluation

the leaf value vectors and node vectors of each con-Most current works are using competitive pro-text are concatenated to a single vector that repre-

gramming code for evaluation. They recognize so-sents that path-context. The base model here welutions to a same problem as clones. The drawback

use is bi-directional LSTM. Since there are mul-is that these solutions are implemented by diﬀerent

tiple paths in an AST, after getting path context

programmers, and do not necessarily contain sim-

representation, we uniformly sample K paths fromilar structures. Furthermore, diﬀerent implemen-

all the paths where K is a hyper parameter, andtations may vary a lot. Some implements are longcalculate the representation of K paths. Then weand include many functions, while others tend to beaverage K representations as the ﬁnal representa-

short and well-encapsulated in one single function.

tion of the code piece. Still, the higher similarity

Thus methods in the dataset may not implementthat code representation share, the more they are

similar functionality. Therefore, evaluations basedsimilar in AST manner.

on current competitive programming dataset are
not reliable.

3. 4 Non-dominated ranking

We make our own dataset based on current com-Non-dominated ranking is an algorithm that or-

petitive programming dataset manually. We only

ders results with multiple objectives without ag-

keep implementations that have similar lengths andgregation. In this algorithm, a result s is said tohave only one function. In this way we can at least

dominate another result t, if s is no worse than tmake sure that these source code implements samein any objective and is better than t in at least one

functionality. We also manually select the imple-

objective. Otherwise, there is a tie. In case of a tie,mentations that share similar structure, such as

we select the result that has the dominant objec-

common for loops and conditional statements.

tive closest to the optimal value, which is this case,

Using implementations to same problems as

the one more closer to the highest cosine similar-

ground truth, we can evaluate how our model

ity score 1. The detail of non-dominated ranking is

can perform when trying to recognize whether two

displayed in Fig.9.

pieces of source code are clones or not. The cleaning
procedures help to avoid the ambiguity mentioned

4 Evaluation Procedure
In this section, we will introduce our new evaluation procedures. As mentioned before, a valid clone

before.

図7

図8

Paths in AST

How paths are representative in source codetures in two programming languages, but the generated code is structurally similar and implements
same functionally.
We utilize such kind of tools to generate a translated version of original source code. Afterwards,
図9

Non dominated ranking

we mix the translated version with a pool of sourcecode pieces to let our model calculates the similar-

4. 2 Auto translation evaluation

ity score between original source code and all pieces

In this procedure, we use auto-translated sourcein the pool. We then select the piece with highest

code for evaluation.

Auto translation tools cantranslate source code from one programming lan-score to see if it is the translated version, which isground truth.

Current translation tools are

We only use auto-translated code for evaluating

mainly using pre-deﬁned rules. When encounter-the model and do not use such code for training.

ing some patterns in source language, tools gener-

This is important because this evaluation is use-

ate target source code following certain templates.

ful in that it selects the optimal candidate without

These tools cannot generate perfect target codeknowing any knowledge about the candidates. It’s

since there is no correspondence between all fea-

closer to real scenarios where we try to ﬁnd code

guage to another.

clones among a large pool of source code pieces.

5 Related Workguages.

Acknowledgements Senxi Li, Tetsuro Ya-

Code clone detection is a popular research topic,

mazaki and Soramichi Akiyama provide a lot ofespecially single language code clone detection. For

valuable suggestions in the discussion of this pa-

example, CCFinder in [3] and SourcererCC in [7]per. We greatly appreciate their help.

are token-based, and Deckard in [2] is AST-based.
Recently, machine learning has also been adopted

参 考 文 献in this topic, as shown in [9] and [8].

[1] Alon, U., Zilberstein, M., Levy, O., and Yahav,
E.: Code2Vec: Learning Distributed Representations of Code, Proc. ACM Program. Lang., Vol. 3,
No. POPL(2019), pp. 40:1–40:29.
[2] Jiang, L., Misherghi, G., Su, Z., and Glondu, S.:
Deckard: Scalable and accurate tree-based detection of code clones, 29th International Conference
on Software Engineering (ICSE’07), IEEE, 2007,
pp. 96–105.
[3] Kamiya, T., Kusumoto, S., and Inoue, K.:
CCFinder: a multilinguistic token-based code clone
detection system for large scale source code, IEEE
Transactions on Software Engineering, Vol. 28,
No. 7(2002), pp. 654–670.
[4] Mathew, G. and Stolee, K. T.: Cross-Language
Code Search Using Static and Dynamic Analyses,
Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2021, Association for Computing
Machinery, 2021, pp. 205–217.
[5] Perez, D. and Chiba, S.: Cross-language clone
detection by learning over abstract syntax trees,
2019 IEEE/ACM 16th International Conference on
Mining Software Repositories (MSR), IEEE, 2019,
pp. 518–528.
[6] Roy, C. K. and Cordy, J. R.: A survey on software clone detection research, Queen s School ofComputing TR, Vol. 541, No. 115(2007), pp. 64–68.
[7] Sajnani, H., Saini, V., Svajlenko, J., Roy, C. K.,
and Lopes, C. V.: Sourcerercc: Scaling code clone
detection to big-code, Proceedings of the 38th International Conference on Software Engineering, 2016,
pp. 1157–1168.
[8] Wei, H. and Li, M.: Supervised Deep Features
for Software Functional Clone Detection by Exploiting Lexical and Syntactical Information in Source
Code., IJCAI, 2017, pp. 3034–3040.
[9] White, M., Tufano, M., Vendome, C., and Poshyvanyk, D.: Deep learning code fragments for code
clone detection, 2016 31st IEEE/ACM International Conference on Automated Software Engineering (ASE), IEEE, 2016, pp. 87–98.

Compared with single language code clone detection, cross-language code clone detection is lesspopular, but there are still some existing works. For
example, [5] proposes to use tree-based skip-gramalgorithm and LSTM-based neural network to detect clones in competitive programming dataset.
One of the most recent works is [4], which utilizes static and dynamic analysis instead of machinelearning, and achieves the state-of-the-art performance. They also evaluate their approach on competitive programming dataset.

6 Conclusion and Future WorkIn this paper, we show that current works in theﬁeld of cross-language code clone detection do nothave a clear deﬁnition of code clones, and they evaluate their approaches on inappropriate datasets.
To solve, we propose new procedures and datasetsfor better evaluation of detection tools. Moreover,
we develop our own model and perform better under the circumstance of new evaluation procedures.
Currently, there are still some experiments undergoing, and results are not complete yet. We
plan to ﬁnish the comparison between our modeland state-of-the-art model to see ﬁnal results. In
future, we plan to have a deeper discussion about
what is code clone and how to measure similarity
between two pieces of source code in diﬀerent lan-