情報処理学会研究報告
IPSJ SIG Technical Report

複数プログラミング言語で記述されたソフトウェアからのコードクローン検出中村 勇太1,a)崔 恩瀞2

吉田 則裕3

春名 修介1

井上 克郎1

概要：複数のプログラミング言語 (以降，言語) で記述されたソフトウェアでは，異なる言語を組合わせて
1 つの機能を実装するため，各言語で記述されたソースコードは互いに呼出し関係を持つ．異なる言語で記述されたソフトウェアから検出されたコードクローンは呼出し関係を持つことが多く，呼出し関係で結合された，より大きなコード片に対して新しくコードクローンを定義することができる．このコードク
ローンは呼出し関係の前後で実装している機能は同じだと考えられるため，互いに一致もしくは類似した機能を実装していると考えられる．このようなコードクローンを開発者に提示することにより，ライブラ
リ作成支援やリファクタリングなどが機能単位で行え，コードクローンの保守作業がより効率的になると期待できる．しかし，既存のコードクローン検出手法では呼出し関係を考慮していないため，複数のコー
ドクローン検出結果を見比べて呼出し関係を把握するという作業が必要である．そこで本研究では，このコードクローンを InterLanguage Clone (ILC) として定義し，その自動検出手法について提案する．さらに，実際のオープンソースの複数言語ソフトウェアに対してケーススタディを実施し，検出される ILC が同一もしくは類似した機能を実装しているかどうか調査した．その結果，そのようなケースがいくつか存
在することを確認できた．
キーワード：コードクローン検出，ソフトウェア保守，複数言語ソフトウェア

Detection of Software Clones Written in
Multiple Programming Languages
Yuta Nakamura1,a)Eunjong Choi2

Norihiro Yoshida3

1. はじめにSyusuke Haruna1

Katsuro Inoue1

ブラリを作成する際は，頻繁に再利用されているコード片を把握する必要があり，その把握にコードクローンが有用

コードクローンとは，ソースコード中に存在する互いにである．また，コードクローンはソフトウェア保守に悪影

一致もしくは類似した部分を持つコード片のことであり，響を及ぼすという指摘もされている [3], [4], [5]．コードク

主にソースコードのコピーアンドペーストによって生成さローンを含むソフトウェアの保守性を改善するためには，れる [1], [2]．

ソースコード中のコードクローンを 1 つのモジュールに

ソースコード中のコードクローンには様々な活用方法が集約するリファクタリングを検討しなければならない [6]．

ある．例えば，既存のソースコードから再利用可能なライ

コードクローンはソフトウェア開発や保守の支援に活用されるため，開発者はソースコード中から見つける必要があ

1

2

3

a)

大阪大学
Osaka University
奈良先端科学技術大学院大学
Nara Institute of Science and Technology
名古屋大学
Nagoya University
n-yuuta@ist.osaka-u.ac.jp

c 2016 Information Processing Society of Japan⃝る．しかし，開発者が開発のたびに目視でコードクローンを見つけることは開発における時間的な制約を考えると現実的ではない．したがって，コードクローンを自動で検出し，開発者に提示する支援が必要となる．

1

情報処理学会研究報告
IPSJ SIG Technical Report

これまで，様々なコードクローン自動検出手法の提案や

䝁䞊䝗∦Ă

その適用実験が行われてきた [4], [7], [8]．しかし，これらの研究は，主に単一のプログラミング言語 (以降，言語) で記述されたソフトウェアを対象にしているため，複数の言

,dD>
ĐĂůů

䝁䞊䝗∦ď

:ĂǀĂ^ĐƌŝƉƚ
ĐĂůů

語を組合わせてより高度なソフトウェアが開発されてきている現状にあってない [9]．さらに，複数の言語で記述されたソフトウェア (以降，複数言語ソフトウェア) にも正しく適用できない恐れがある．

䝁䞊䝗∦Đ
図 1

:ĂǀĂ^ĐƌŝƉƚ

呼出し関係グラフ (CRG)．

Fig. 1 Call Relation Graph.

複数言語ソフトウェアの場合，異なる言語を組合わせて

1 つの機能を実装する．例えば，ウェブアプリケーションを持つコード片であり，主にソースコードのコピーアンドである機能を実装する際は，クライアント側の実装とサーペーストによって生成される [1], [2]．一般に，互いにコー

バ側の実装で異なる言語を用いる．そのため，各言語で記

ドクローンであるコード片のペアをクローンペア，そして述されたソースコードは互いに呼出し関係を持つ．その結

コードクローンの同値類をクローンセットと呼ぶ．

果，各言語で記述されたソースコードから検出されたコー
ドクローン同士が呼出し関係を持つことがある．

複数言語ソフトウェアは複数の言語の特性を組合わせて機能を実装する．その際，異なる言語で記述されたソース

例えば，コード片 (Ci , Ci′ ) と (Cj , Cj ′ ) がコードクロー

コード間に呼出し関係が生じる．このような複数言語ソフンであり，Ci → Cj や Ci′ → Cj ′ というように呼出し関係

トウェアからコードクローンを検出した場合，検出されたを持ち，さらに呼出し元と呼出し先が異なる言語で記述さ

コードクローンが互いに呼出し関係を持つことが多いあ

れた場合，この呼出し関係で結合された，より大きなコーる．本研究では，この呼出し関係で結合された，より大きド片に対して新しくコードクローンを定義することができなコード片に対して定義される新しいコードクローンをる．つまり，(Ci → Cj ) と (Ci′ → Cj ′ ) が新しいコードク

Interlanguage Clone (ILC) と定義する．以降，ILC の詳し

ローンとなる．呼出し関係の前後で実装している機能は同

い定義について説明する．

じだと考えられるため，この新しいコードクローン同士は

ILC を定義するにあたり，まず呼出し関係グラフを定義

互いに一致もしくは類似した機能を実装していると考えらする．コード片の集合が与えられたときに，コード片間のれる．したがって，一致もしくは類似した機能を実装して呼出し関係に基づいて有向グラフを構築することができいるコードクローンを開発者に提示することで，ライブラる．図 1 は呼出し関係グラフ (CRG) の例を表している．

リ作成支援やリファクタリングといったコードクローンのこのグラフのノードはコード片を，ノード間に引かれる

活用がより効率的になると期待できる．

エッジはコード片間の呼出し関係を表している．また，各

しかし，既存のコードクローン検出手法は複数言語ソフ

ノードに付けられた名前はそのコード片を記述している言

トウェアを想定してない上，呼出し関係を考慮していない語を表す．図 1 では，HTML で記述されたコード片 a がため，既存のコードクローン検出手法で複数言語ソフト

JavaScript で記述されたコード片 b を呼出し，さらにそのウェアからコードクローンを検出する場合，複数のコード

コード片 b が同じく JavaScript で記述されたコード片 c を

クローン検出結果を見比べて呼出し関係を把握する必要が呼出している．このような有向グラフを呼出し関係グラフ

あり，作業効率が下がってしまう．

(CRG) と定義する．

そこで本研究では，このコードクローンを InterLanguage

呼出し関係グラフに基づいて，ILC を次のように定義す

Clone (ILC) として定義し，その自動検出手法について提る．与えられた 2 つのコード片集合 1 と 2 に対して，呼出案する．さらに，実際のオープンソースの複数言語ソフト

し関係グラフ CRG1 と CRG2 を構築する．これら 2 つのウェアに対してケーススタディを実施し，検出される ILC

グラフ CRG1 と CRG2 が以下の条件を満たすとき，与えが一致もしくは類似した機能を実装しているかどうか調査られたコード片集合 1 と 2 は互いに ILC となる．

した．

( 1 ) グラフが複数の言語で記述された以降，2 章では本研究で提案する ILC の定義について

コード片で構築されている．

述べ，3 章ではその検出手法を説明する．そして 4 章では( 2 ) グラフが同型である．

ケーススタディとその結果について述べ，5 章では関連研( 3 ) グラフの対応する各ノード同士がコードクローンの究を紹介する．最後に 6 章で本研究のまとめと今後の課題について述べる．

2. Interanguage Clone
コードクローンとは，互いに一致もしくは類似した部分

c 2016 Information Processing Society of Japan
⃝関係にある．
図 2 は 2 つのコード片集合から構築される呼出し関係グラフの例を表している．この図において，2 つのコード片集合から構築された呼出し関係グラフ CRG1 と CRG2 は同じ型をしており，対応するノード同士がコードクローン2

情報処理学会研究報告
IPSJ SIG Technical Report䝁䞊䝗∦㞟ྜϭ• 対応する各ノードがコードクローンの関係にある．

Z'ϭ
,dD>

以上 3 つの条件を満たす部分グラフのペアを見つけることĐĂůů:ĂǀĂ^ĐƌŝƉƚ
ĐĂůů:ĂǀĂ^ĐƌŝƉƚ

に等しい．その手順は以下の通りである．
手順 1：
手順 2：

䝁䞊䝗∦㞟ྜϮ

選択したコードクローンそれぞれに対して，呼出し先/呼出し元のコードクローンを取得する．
手順 3：

Z'Ϯ
,dD>

同じクローンセット内に存在する任意のコード

クローンを 2 つ選択する．

呼び出し先/呼出し元のコードクローンが共に同じクローンセットに含まれていれば，同型部分グラ
フ候補として追加する．

ĐĂůů:ĂǀĂ^ĐƌŝƉƚ
ĐĂůů:ĂǀĂ^ĐƌŝƉƚ

手順 4：

呼び出し先/呼出し元が存在しない場合，同じク

ローンセットに含まれていない場合，既に同型部分グ
ラフ候補に追加済みの場合は探索を終了する．
この処理を再帰的に行うことで，対応するノードがコー
ドクローンの関係にあるような同型部分グラフのペアを得

図 2

2 つのコード片集合から構築される呼出し関係グラフ．同色のることができる．その中で，複数の言語が用いられていれノード同士は互いにコードクローンの関係にあることを表す．

ば，その同型部分グラフのペアを ILC ペアとして検出す

Fig. 2 Call Relation Graphs Constructed from Two Code Fragment Sets. Two Nodes which Have the Same Color
Mean that They are Code Clone.

る．手順 4 における，追加済みかどうかの条件は呼出し関係が循環している場合に探索が無限ループに陥ってしまう
事態を防ぐために設けた．

の関係にある．さらに，グラフは HTML と JavaScript で記述されたコード片で構築されている．したがってこの場
合，2 つのコード片集合は互いに ILC となる．

4. ケーススタディ
4.1 概要さらに，通常のコードクローンにおけるクローンペアと本研究では複数言語ソフトウェアを対象として，ILC のクローンセットを ILC の場合でも同様に定義することがで

定義とその自動検出手法を提案した．その目的は，1 章できる．つまり，互いに ILC の関係にあるコード片集合のペ述べたように，複数の言語で記述されたソースコード間でアが ILC ペア，そして ILC の同値類が ILC セットとなる．

呼出し関係を持たせることにより機能を実装している複数

3. Interlanguage Clone 検出手法

言語ソフトウェアから，同一もしくは類似した機能を実装しているコードクローンを検出することである．

この章では，2 章で定義した ILC の自動検出手法についそこで，実際のオープンソースソフトウェアを用いたて説明する．検出手法は 3 つのステップで構成されている

ケーススタディを実施し，ILC を検出することでこの目的(図 3)．

を実現できているかどうかを確認した．ケーススタディで

ステップ 1：

入力ソースコードに対して既存のコードクは以下の 2 点について調査を行った．

ローン検出ツールを適用し，各言語毎にコードクロー( 1 ) ILC はどの程度存在するのか．

ンを検出する( 2 ) I 各 LC セット内の全 ILC は同一もしくは類似機能をステップ 2：検出されたコードクローンに対して静的解析を行い，コードクローン間の呼出し関係情報を抽出する．入力ソースコード全体ではなく，検出された

実装しているか．
以降，ケーススタディの対象と調査方法，そしてその結果や考察について述べる．

コードクローンを対象として静的解析を行うのは，解析に掛かる時間を削減するためである．

4.2 対象検出されたコードクローンをノード，抽出

ILC は複数言語ソフトウェア全般に対して定義することした呼出し関係情報をエッジとする呼出し関係グラフができる．しかし今回のケーススタディでは，特定のドメステップ 3：を構築し，定義に基づいて ILC を検出する．
以降，ステップ 3 についてその詳細を述べる．

表 1

ステップ 3 の ILC 検出は，構築された呼出し関係グラフ

Table 1 Statistics of Target Web Applications.

全体の中から，

対象ウェブアプリケーション (WA) の規模．

総行数 (HTML)

総行数 (JavaScript)• 複数の言語を用いている．

Webogram

6,146

224,140• 同型である．

DuckieTV

3,404

67,485c 2016 Information Processing Society of Japan
⃝

WA 名

3

情報処理学会研究報告
IPSJ SIG Technical Reportධຊ䝋䞊䝇䝁䞊䝗

䝇䝔䝑䝥ϭ䠖
䝁䞊䝗䜽䝻䞊䞁᳨ฟ図 3ྛ䝥䝻䜾䝷䝭䞁䜾ゝㄒ䛻ᑐᛂ䛧䛯䝁䞊䝗䜽䝻䞊䞁䝇䝔䝑䝥ϯ䠖
/>᳨ฟ䝇䝔䝑䝥Ϯ䠖
࿧ฟ䛧㛵ಀゎᯒ࿧ฟ䛧㛵ಀ᝟ሗ

/>

ILC 検出手法の概要．

Fig. 3 Overiew of Proposed ILC Detection Approach.

イン，及び言語に焦点を当てた．これは，ドメインや言語検出するステップでは，既存のコードクローン検出であを絞ることによりコードクローン検出や呼出し関係解析のる NiCad[4] を用いた．NiCad は行単位でソースコードを精度を上げるためである．

比較し，その類似度が指定した閾値以上であるときにコー

今回のケーススタディでは，ドメインについてはウェ

ドクローンであると判定する．NiCad は，文法情報と，関ブアプリケーションを，そして言語については HTML と数やブロックといった検出粒度を与えることで，任意の言

JavaScript を選択した．ウェブアプリケーションは，リ語から任意の粒度でコードクローンを検出することができ

リース期間の短さやパフォーマンス低下回避などが要因でる．専用の検出ツールが存在しない HTML と JavaScript

コードクローンを多く含むことが分かっている．[10], [11]．

からコードクローンを検出するにあたり，文法情報を与え

ILC の検出には通常のコードクローンが必要となるため，るだけで検出が行える拡張性の高さが理由で NiCad を選

コードクローンが多いウェブアプリケーションからは十分択した．

な数の ILC が検出されると考えた．また，過去の研究でNiCad に与えるパラメータは，検出粒度，類似度の閾値，GitHub*1 上のリポジトリを調査した結果，複数の言語を用

そして検出されるコードクローン行数の閾値がある．今回

いて開発が行われていた 66,825 リポジトリの内，22.9%ののケーススタディでは，HTML に対するコードクローン

リポジトリで HTML と JavaScript を組合わせて開発を検出の場合，検出粒度を開始タグから終了タグまでの一括行っていたことが分かった [12]．これは，他の利用言語のり，類似度の閾値を 0.3，最小行数を 10 行とした．また，組み合わせの中でも最多であった．よって，対象となるソ

JavaScript に対するコードクローン検出の場合，検出粒度

フトウェアを探しやすいと考えて，HTML と JavaScript

を関数，類似度の閾値を 0.3，最小行数を 5 行とした．さを利用言語に選んだ．

らに，文法構造が同じでもユーザ定義名に違いがあるコー

さらに，十分な規模のウェブアプリケーションを選択す

ド片をコードクローンとして検出するために，どちらの場るための条件として，(1) コミット数が 1000 以上，(2) 人気

合もユーザ定義名をすべて同一トークンに変換している．

度を表すスターが 100 個以上付けられたウェブアプリケー

呼出し関係を解析するステップでは，HTML 内に存在ションのみに絞った．そしてその中から，無作為にウェブする関数呼び出しを HTML→JavaScript の呼出し関係，

アプリケーションを選択し，今回の対象とした．

JavaScript 内の関数呼び出しを JavaScript→JavaScript の

表 1 に，今回のケーススタディで用いた 2 つのウェブ

呼出し関係として抽出した．

アプリケーション (Webogram*2 ，DuckieTV*3 ) に関する

こうして検出されるコードクローンと，それらの間の呼データを示した．表中の値はそれぞれ，HTML ファイル

出し関係情報を用いて ILC を検出し，検出された ILC セッの総行数と JavaScript ファイルの総行数を表している．

トの数を確認する．

Webogram はチャットアプリである Telegram をウェブア

各 ILC セット内の全 ILC は同一もしくは類似機能をプリケーション化したものである．また，DuckieTV は，実装しているか．

カレンダー上でドラマなどのテレビ番組の更新情報を管理するためのウェブアプリケーションである．

検出された各 ILC セット内の全 ILC が実装している機能を調べ，それらが同一もしくは類似した機能かどうかを判断する．すべての ILC が同一もしくは類似した機能を実

4.3 調査方法

装している場合に限り，その ILC セットは同一もしくは類ILC はどの程度存在するのか．

似した機能を実装したコードクローンが集まっていると判3 章で説明した検出手法にしたがって，2 つのウェブア

断する．

プリケーションから ILC を検出する．コードクローンを4.4 結果*1*2*3

https://github.com/
https://github.com/zhukov/webogram
https://github.com/SchizoDuckie/DuckieTV

c 2016 Information Processing Society of Japan⃝ILC はどの程度存在するのか．
2 つのウェブアプリケーションから検出された ILC セット

4

情報処理学会研究報告
IPSJ SIG Technical Report
表2

検出された ILC セットの数及び，HTML と JavaScript から検出されたクローンセットの数

Table 2 Number of Detected ILC Sets and Original(HTML&JavaScript) Clone Sets.
WA 名

ILC セット数

HTML クローンセット数

JavaScript クローンセット数

Webogram

4

97

44

DuckieTV

3

11

65

表 3

各 ILC セット内の ILC が同一もしくは類似機能を実装しているかどうかの判断結果．

Table 3 The Result of Judging Whether All the ILCs of Each ILC Set Implement theSame or Similar Functionalities or not.
WA 名

ILC セット番号

ILC 数

1

2

N

2

2

Y

3

2

N

4

3

Y

1

2

Y

2

2

Y

3

2

Y

Webogram

DuckieTVの数について表 2 にまとめた．Webogram に関して，元々同一もしくは類似機能を実装しているか (Y/N)

4.5 考察は HTML 単体で 97 個のクローンセットが，JavaScript 単

表 3 より，ILC セットを構成している ILC がすべて類体で 44 個のクローンセットが検出されていた．これに対似機能を実装しているケースが検出されている．したがっして ILC 検出を行ったところ，4 個の ILC セットが検出て，開発者に ILC 検出結果を提示することで，類似機能がされた．また，DuckieTV の場合は，HTML 単体で 11 個

まとまっていることを活かしたコードクローン利用を行うのクローンセットが，JavaScript 単体では 65 個のクローことができると考えられる．例えばライブラリ作成を行う

ンセットが検出されていた．これに対して ILC 検出を行う

場合にコードクローンの情報を用いる場合は，全く異なると，3 個の ILC セットが検出された．

機能を実装しているコードクローンを提示される場合に比各 ILC セット内の全 ILC は同一もしくは類似機能をべて効率よくライブラリ候補を探すことができる．

実装しているか．

表 2 から分かるように，元々検出されていたコードク検出された各 ILC セット内の全 ILC が同一もしくは類

ローンの大部分が ILC セットとして検出されなくなってい似機能を実装しているかどうか判断した結果を表 3 に示しる．これは，呼出し関係を持たないコードクローンは ILC

た．Webogram については，検出された 4 個の ILC セッとして検出されなくなってしまうからである．このことか

トの内，2 個の ILC セット内の全 ILC が類似機能を実装

ら，ILC 検出結果を見るだけでは本来利用価値のあった重していた．DuckieTV は，3 個の ILC セットすべてにおい

要なコードクローンまでも無視してしまう恐れがあることて，ILC セット内の全 ILC が類似機能を実装していた．

が分かる．そこで，開発者にはまず ILC 検出結果を見て

図 4 に，Webogram から検出された ILC セット内の全もらい，開発時間に余裕があればその後，既存のコードク

ILC が，類似機能を実装していたケースにおける実際のローン検出ツールによる結果を見て細部にまで目を向けて

ソースコードの例を，図 5 に，同じく Webogram から，異もらうという 2 段階の利用方法が考えられる．ウェブアプなる機能を実装していたケースにおけるソースコードの例

リケーションのように，リリース期間が短く，時間的制約を載せた．

が厳しい開発環境においては，既存のコードクローン検出

図 4 はどちらも，チャットアプリ内に存在する様々な切り替えボタン (トグル) を押したときの処理を実装していると ILC 検出を組合わせるこの利用方法が有用であると考えられる．

ため，類似機能を実装していると判断した．一方，図 5 の

今回のケーススタディでは，ILC セット内の全 ILC が類

例では，上のコード片がタイトルの編集という処理を，下似機能を実装していないケースがみられた (表 3)．その例のコード片がチャット内のチャンネルに参加する際の処理を見てみると (図 5)，どちらも言語の構文的構造は類似しを表している．これらは異なる機能を実装していると判断ているものの，使われている識別子が異なっていることがした．

分かる．したがって，検出される ILC セット内の全 ILCが同一もしくは類似した機能を実装しているようにするた
めには，こうした識別子に着目して手法を改善する必要がc 2016 Information Processing Society of Japan⃝5

情報処理学会研究報告
IPSJ SIG Technical Report㻨㼍㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼟㼑㼏㼠㼕㼛㼚㼋㼠㼛㼓㼓㼘㼑㼋㼣㼞㼍㼜 㼠㼓㼋㼏㼔㼑㼏㼗㼎㼛㼤㻎㻌㼚㼓㻙㼏㼘㼕㼏㼗㻩㻎㼠㼛㼓㼓㼘㼑㻰㼑㼟㼗㼠㼛㼜㻔㻕䇾㼚㼓㻙㼏㼘㼍㼟㼟㻩㻎㼚㼛㼠㼕㼒㼥㻚㼐㼑㼟㼗㼠㼛㼜 㻫㻌㻓㼠㼓㼋㼏㼔㼑㼏㼗㼎㼛㼤㼋㼛㼚㻓㻌㻦㻌㻓㻓㻎㻪㻨㼟㼜㼍㼚㻌㼏㼘㼍㼟㼟㻩㻎㼕㼏㼛㼚㻌㼕㼏㼛㼚㻙㼏㼔㼑㼏㼗㼎㼛㼤㻙㼛㼡㼠㼑㼞㻎㻪㻨㼕 㼏㼘㼍㼟㼟㻩㻎㼕㼏㼛㼚㻙㼏㼔㼑㼏㼗㼎㼛㼤㻙㼕㼚㼚㼑㼞㻎㻪
㻨㻛㼕㻪
ĐĂůů
㻨㻛㼟㼜㼍㼚㻪
㻨㼟㼜㼍㼚㻌㼏㼘㼍㼟㼟㻩㻎㼠㼓㼋㼏㼔㼑㼏㼗㼎㼛㼤㼋㼘㼍㼎㼑㼘㻎㻌㼙㼥㻙㼕㻝㻤㼚㻩㻎㼟㼑㼠㼠㼕㼚㼓㼟㼋㼙㼛㼐㼍㼘㼋㼚㼛㼠㼕㼒㼕㼏㼍㼠㼕㼛㼚㼟㻎㻪㻨㻛㼟㼜㼍㼚㻪
㻨㻛㼍㻪㻨㼍㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼟㼑㼏㼠㼕㼛㼚㼋㼠㼛㼓㼓㼘㼑㼋㼣㼞㼍㼜 㼠㼓㼋㼏㼔㼑㼏㼗㼎㼛㼤㻎㻌㼚㼓㻙㼏㼘㼕㼏㼗㻩㻎㼠㼛㼓㼓㼘㼑㻼㼞㼑㼢㼕㼑㼣㻔㻕䇾㼚㼓㻙㼏㼘㼍㼟㼟㻩㻎㼚㼛㼠㼕㼒㼥㻚㼜㼞㼑㼢㼕㼑㼣 㻫㻌㻓㼠㼓㼋㼏㼔㼑㼏㼗㼎㼛㼤㼋㼛㼚㻓㻌㻦㻌㻓㻓㻎㻪㻨㼟㼜㼍㼚㻌㼏㼘㼍㼟㼟㻩㻎㼕㼏㼛㼚㻌㼕㼏㼛㼚㻙㼏㼔㼑㼏㼗㼎㼛㼤㻙㼛㼡㼠㼑㼞㻎㻪㻨㼕 㼏㼘㼍㼟㼟㻩㻎㼕㼏㼛㼚㻙㼏㼔㼑㼏㼗㼎㼛㼤㻙㼕㼚㼚㼑㼞㻎㻪㻨㻛㼕㻪㻨㻛㼟㼜㼍㼚㻪
ĐĂůů㻨㼟㼜㼍㼚㻌㼏㼘㼍㼟㼟㻩㻎㼠㼓㼋㼏㼔㼑㼏㼗㼎㼛㼤㼋㼘㼍㼎㼑㼘䇾㼙㼥㻙㼕㻝㻤㼚㻩㻎㼟㼑㼠㼠㼕㼚㼓㼟㼋㼙㼛㼐㼍㼘㼋㼙㼑㼟㼟㼍㼓㼑㼋㼜㼞㼑㼢㼕㼑㼣㻎㻪㻨㻛㼟㼜㼍㼚㻪
㻨㻛㼍㻪㻐㼟㼏㼛㼜㼑㻚㼠㼛㼓㼓㼘㼑㻰㼑㼟㼗㼠㼛㼜 㻩㻌㼒㼡㼚㼏㼠㼕㼛㼚㻌㻔㻕㼧㻐㼟㼏㼛㼜㼑㻚㼚㼛㼠㼕㼒㼥㻚㼐㼑㼟㼗㼠㼛㼜 㻩㻌㻍㻌㻐㼟㼏㼛㼜㼑㻚㼚㼛㼠㼕㼒㼥㻚㼐㼑㼟㼗㼠㼛㼜㻧㼕㼒㻌㻔㻐㼟㼏㼛㼜㼑㻚㼚㼛㼠㼕㼒㼥㻚㼐㼑㼟㼗㼠㼛㼜㻕㻌㼧㻿㼠㼛㼞㼍㼓㼑㻚㼞㼑㼙㼛㼢㼑 㻔㻓㼚㼛㼠㼕㼒㼥㼋㼚㼛㼐㼑㼟㼗㼠㼛㼜㻓㻕㻧㼩㼑㼘㼟㼑㻌㼧
㻿㼠㼛㼞㼍㼓㼑㻚㼟㼑㼠 㻔㼧㼚㼛㼠㼕㼒㼥㼋㼚㼛㼐㼑㼟㼗㼠㼛㼜 㻦㻌㼠㼞㼡㼑㼩㻕㻧㼩㻐㼞㼛㼛㼠㻿㼏㼛㼜㼑㻚㻐㼎㼞㼛㼍㼐㼏㼍㼟㼠㻌㻔㻓㼟㼑㼠㼠㼕㼚㼓㼟㼋㼏㼔㼍㼚㼓㼑㼐㻓㻕㻧㼩㻐㼟㼏㼛㼜㼑㻚㼠㼛㼓㼓㼘㼑㻼㼞㼑㼢㼕㼑㼣 㻩㻌㼒㼡㼚㼏㼠㼕㼛㼚㻌㻔㻕㼧㻐㼟㼏㼛㼜㼑㻚㼚㼛㼠㼕㼒㼥㻚㼜㼞㼑㼢㼕㼑㼣 㻩㻌㻍㻌㻐㼟㼏㼛㼜㼑㻚㼚㼛㼠㼕㼒㼥㻚㼜㼞㼑㼢㼕㼑㼣㻧㼕㼒㻌㻔㻐㼟㼏㼛㼜㼑㻚㼚㼛㼠㼕㼒㼥㻚㼜㼞㼑㼢㼕㼑㼣㻕㻌㼧㻿㼠㼛㼞㼍㼓㼑㻚㼞㼑㼙㼛㼢㼑 㻔㻓㼚㼛㼠㼕㼒㼥㼋㼚㼛㼜㼞㼑㼢㼕㼑㼣㻓㻕㻧㼩㼑㼘㼟㼑㻌㼧
㻿㼠㼛㼞㼍㼓㼑㻚㼟㼑㼠 㻔㼧㼚㼛㼠㼕㼒㼥㼋㼚㼛㼜㼞㼑㼢㼕㼑㼣 㻦㻌㼠㼞㼡㼑㼩㻕㻧㼩㻐㼞㼛㼛㼠㻿㼏㼛㼜㼑㻚㻐㼎㼞㼛㼍㼐㼏㼍㼟㼠㻌㻔㻓㼟㼑㼠㼠㼕㼚㼓㼟㼋㼏㼔㼍㼚㼓㼑㼐㻓㻕㻧㼩

図 4 類似機能を実装している例．赤字は呼出し関係部分．

Fig. 4 Example of ILCs which Implement Similar Functionalities.

㻨㼐㼕㼢㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼍㼏㼠㼕㼛㼚㼟㼋㼣㼞㼍㼜 㼏㼘㼑㼍㼞㼒㼕㼤㻎㻪㻨㼍㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼍㼏㼠㼕㼛㼚 㼙㼐㼋㼙㼛㼐㼍㼘㼋㼍㼏㼠㼕㼛㼚㼋㼏㼘㼛㼟㼑䇾㼚㼓㻙㼏㼘㼕㼏㼗㻩㻎㻐㼏㼘㼛㼟㼑㻔㻕䇾㼙㼥㻙㼕㻝㻤㼚㻩㻎㼙㼛㼐㼍㼘㼋㼏㼘㼛㼟㼑㻎㻪㻨㻛㼍㻪㻨㼍㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼍㼏㼠㼕㼛㼚䇾㼚㼓㻙㼕㼒㻩㻎㼔㼍㼟㻾㼕㼓㼔㼠㼟㻔㻓㼑㼐㼕㼠㼋㼠㼕㼠㼘㼑㻓㻕䇾ĐĂůů㼚㼓㻙㼏㼘㼕㼏㼗㻩㻎㼑㼐㼕㼠㼀㼕㼠㼘㼑㻔㻕㻎㻌㼙㼥㻙㼕㻝㻤㼚㻩㻎㼙㼛㼐㼍㼘㼋㼑㼐㼕㼠㻎㻪㻨㻛㼍㻪㻨㻛㼐㼕㼢㻪

㻨㼐㼕㼢㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼟㼑㼏㼠㼕㼛㼚㼋㼘㼕㼚㼗㼋㼣㼞㼍㼜䇾㼚㼓㻙㼟㼣㼕㼠㼏㼔㻩㻎㼏㼔㼍㼠㻲㼡㼘㼘㻚㼏㼔㼍㼠㻚㼜㻲㼘㼍㼓㼟㻚㼘㼑㼒㼠㻎㻪㻨㼍㻌㼚㼓㻙㼟㼣㼕㼠㼏㼔㻙㼣㼔㼑㼚㻩㻎㼠㼞㼡㼑䇾㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼟㼑㼏㼠㼕㼛㼚㼋㼘㼕㼚㼗䇾㼚㼓㻙㼏㼘㼕㼏㼗㻩㻎㼖㼛㼕㼚㻯㼔㼍㼚㼚㼑㼘㻔㻕䇾ĐĂůů㼙㼥㻙㼕㻝㻤㼚㻩㻎㼏㼔㼍㼚㼚㼑㼘㼋㼙㼛㼐㼍㼘㼋㼖㼛㼕㼚㻎㻪㻨㻛㼍㻪㻨㼍㻌㼚㼓㻙㼟㼣㼕㼠㼏㼔㻙㼐㼑㼒㼍㼡㼘㼠㻌㼏㼘㼍㼟㼟㻩㻎㼙㼐㼋㼙㼛㼐㼍㼘㼋㼟㼑㼏㼠㼕㼛㼚㼋㼘㼕㼚㼗䇾㼚㼓㻙㼏㼘㼕㼏㼗㻩㻎㼕㼚㼢㼕㼠㼑㼀㼛㻯㼔㼍㼚㼚㼑㼘㻔㻕䇾㼙㼥㻙㼕㻝㻤㼚㻩㻎㼏㼔㼍㼚㼚㼑㼘㼋㼙㼛㼐㼍㼘㼋㼍㼐㼐㼋㼙㼑㼙㼎㼑㼞㻎㻪㻨㻛㼍㻪㻨㻛㼐㼕㼢㻪

図 5

㼒㼡㼚㼏㼠㼕㼛㼚㻌㼑㼐㼕㼠㼀㼕㼠㼘㼑 㻔㻕㼧㼞㼑㼠㼡㼞㼚㻌㻹㼠㼜㻭㼜㼕㻹㼍㼚㼍㼓㼑㼞㻚㼕㼚㼢㼛㼗㼑㻭㼜㼕 㻔㻓㼏㼔㼍㼚㼚㼑㼘㼟㻚㼑㼐㼕㼠㼀㼕㼠㼘㼑㻓㻘㼧㼏㼔㼍㼚㼚㼑㼘㻌㻦㻌㻭㼜㼜㻯㼔㼍㼠㼟㻹㼍㼚㼍㼓㼑㼞㻚㼓㼑㼠㻯㼔㼍㼚㼚㼑㼘㻵㼚㼜㼡㼠 㻔㻐㼟㼏㼛㼜㼑㻚㼏㼔㼍㼠㻵㻰㻕㻘㼠㼕㼠㼘㼑㻌㻦㻌㻐㼟㼏㼛㼜㼑㻚㼏㼔㼍㼚㼚㼑㼘㻚㼠㼕㼠㼘㼑㼩㻕㻚㼠㼔㼑㼚㻌㻔㼒㼡㼚㼏㼠㼕㼛㼚㻌㻔㼡㼜㼐㼍㼠㼑㼟㻕㼧㻭㼜㼕㼁㼜㼐㼍㼠㼑㼟㻹㼍㼚㼍㼓㼑㼞㻚㼜㼞㼛㼏㼑㼟㼟㼁㼜㼐㼍㼠㼑㻹㼑㼟㼟㼍㼓㼑 㻔㼡㼜㼐㼍㼠㼑㼟㻕㻧㼩㻕㻧㼩㼒㼡㼚㼏㼠㼕㼛㼚㻌㼖㼛㼕㼚㻯㼔㼍㼚㼚㼑㼘 㻔㻕㼧㻹㼠㼜㻭㼜㼕㻹㼍㼚㼍㼓㼑㼞㻚㼕㼚㼢㼛㼗㼑㻭㼜㼕 㻔㻓㼏㼔㼍㼚㼚㼑㼘㼟㻚㼖㼛㼕㼚㻯㼔㼍㼚㼚㼑㼘㻓㻘㼧㼏㼔㼍㼚㼚㼑㼘㻌㻦㻌㻭㼜㼜㻯㼔㼍㼠㼟㻹㼍㼚㼍㼓㼑㼞㻚㼓㼑㼠㻯㼔㼍㼚㼚㼑㼘㻵㼚㼜㼡㼠 㻔㻙 㼜㼑㼑㼞㻵㻰㻕㼩㻕㻚㼠㼔㼑㼚㻔㼒㼡㼚㼏㼠㼕㼛㼚㻌㻔㼞㼑㼟㼡㼘㼠㻕㼧㻭㼜㼕㼁㼜㼐㼍㼠㼑㼟㻹㼍㼚㼍㼓㼑㼞㻚㼜㼞㼛㼏㼑㼟㼟㼁㼜㼐㼍㼠㼑㻹㼑㼟㼟㼍㼓㼑 㻔㼞㼑㼟㼡㼘㼠㻕㻧㼩㻕㻧㼩

異なる機能を実装している例．赤字は呼出し関係部分．

Fig. 5 Example of ILCs which Implement Diﬀerent Functionalities.

c 2016 Information Processing Society of Japan⃝6

情報処理学会研究報告
IPSJ SIG Technical Reportある．例えば，関数呼出し文に使われている識別子が大き的な web アプリケーションを対象にしたスライシング手

く異なる場合には ILC として検出しないという方法が考え

法 WebSlice を提案し，5 つのシステムを対象にした実証

られる．

実験を行った [16]．その結果，プログラミング言語を横5. 関連研究

断するデータフローやスライスを多数確認できた．最後に，Muhammad らは動的ウェブページから island gram-

単一のプログラミング言語で記述されたソフトウェア

mar[17] を用いて PHP ソースコードを抽出した後，NiCad

からコードクローンを検出する様々なツールが提案されを用いてコードクローンを検出し，ウェブアプリケーショてきた．Kamiya らはトークンベースのコードクローン検ンにおける PHP コードクローンを調査した [18]．

出ツール CCFinder を開発した [7]．CCFinder は，字句解

上述の通り，複数言語ソフトウェアを対象としたコード析を行うことによってソースコードをトークン列に変換

クローンの検出やその調査は行われてきたが，いずれもし，変数名や関数名などのユーザ定義名を同一トークンにコードクローン間の呼出し関係に着目していない．複数言変換する．その後，閾値以上の長さの共通トークン列を探

語ソフトウェアから検出されたコードクローン間に存在す

索することによって，コードクローンを検出する．Jiang

る呼出し関係に着目して新たなコードクローン (ILC) を検らはソースコードの構文構造を木構造で表した抽象構文

出したのは本研究が初めてである．

木を用いてコードクローンを検出するツール DECKARDを開発した [8]．DECKARD は構文解析を行うことによっ6. まとめと今後の課題てソースコードを抽象構文木に変換し，類似した部分木

複数言語ソフトウェアでは，異なる言語で記述されたを探索することによってコードクローンを検出する．Roy

ソースコード間に呼出し関係が存在する．そのため，異ならは Text ベースのコードクローンツール NiCad を開発しる言語で記述されたソースコードに含まれるコードクロー

た [4]．NiCad は TXL’s agile parsing[13] を用いてソースン同士も呼出し関係を持つ．このとき，呼出し関係で結合

コードを正規化した後に，最長共通部分列アルゴリズムをされたコードクローンの組をより大きな 1 つのコード片と用いてコードクローンを検出する．

みると，このコード片に対して新しくコードクローンが定複数のプログラミング言語で記述されたソフトウェアからコードクローンを検出する手法も提案されてきた．Kraft

義できる．本研究ではこれを ILC と定義し，さらに自動検出手法を提案した．

らは C#と Visual Basic.NET 言語間でのコードクローン

複数言語ソフトウェアの 1 つであるウェブアプリケーを検出する手法を提案した [3]．彼らの手法はソースコー

ションに対してケーススタディを実施した結果，2 つの対

ドを CodeDOM(Code Document Object Model) グラフに

象ウェブアプリケーションから計 7 個の ILC セットを検変換し，トークン列を抽出した後に，レーベンシュタイン

出した．さらに，各 ILC セット内の全 ILC が同一もしく

距離 [14] に基づいてコードクローンを検出する．Cheng らは類似した機能を実装しているケースが 5 個確認できた．

は git のログから C#と Java プログラミング言語間でのこのことから，ILC 検出を行うことで類似機能を実装した

diﬀ クローンを検出するツール CLCMiner を開発した [15]．

コードクローンが 1 つにまとまることに繋がると結論を出

CLCMiner は git のログを解析し，diﬀ の列やそれぞれ diﬀ

した．この状態で開発者に結果を提示することで，例えばの属性（コミット日付，コミットＩＤなど）を抽出する．

類似機能をまとめてライブラリを作成したり，機能単位で抽出された diﬀ はトークン列に正規化され，同じファイル

コードクローンの集約を効率よく行うことが可能になると名の diﬀ の類似度に基づいてコードクローンを検出する．

考えられる．

ウェブアプリケーションを対象にコードクローンを検出

今後の課題としては，検出に識別子の情報を組み込むこし，調査した研究がある．Rajapakse らは CCFinder を用とで，ILC セット内の全 ILC が類似機能を実装しているよいて 17 のウェブアプリケーションを対象にコードクローン

うな検出結果を出すことが挙げられる．また，ソフトウェを検出し調査した [10]．その結果，ウェブアプリケーショ

ア開発や保守の観点から，既存のコードクローンよりもンに含まれるソースコードのうち 17-63%がコードクロー

ILC を開発者に提示することで本当により効率的に作業がンとなっていることが分かった．また，彼らは CCFinder

行えるかどうかを検証していきたい．

を用いてウェブアプリケーションのサーバページを対象に
コードクローン検出し，実証研究を行った [11]．その結果，ほとんどのサーバページのコードクローンは集約可能であ

謝辞 本研究は JSPS 科研費 JP25220003，JP26730036，

JP15H06344，JP16K16034 の助成を受けたものです．

り，コードクローンの集約によるソースコードサイズの減少などの利点がある反面，パフォーマンス低下などの欠点

参考文献がありトレードオフの関係にあることが分かった．

[1]

Nguyen らは複数のプログラミング言語で記述された動c 2016 Information Processing Society of Japan⃝

Baxter, I. D., Yahin, A., Moura, L., Sant’Anna, M. andBier, L.: Clone Detection Using Abstract Syntax Trees,7

情報処理学会研究報告
IPSJ SIG Technical Report

[2]

[3]
[4]

[5]

[6]
[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Proc. of ICSM 1998, pp. 368–377 (1998).
肥後芳樹，楠本真二，井上克郎：コードクローン検出とその関連技術 (ソフトウェア工学)，電子情報通信学会論文誌. D, 情報・システム， Vol. 91, No. 6, pp. 1465–1481(2008).
Kraft, N., Bonds, B. and Smith, R.: Cross-Language
Clone Detection, Proc. of SEKE 2008, pp. 54–59 (2008).
Chanchal, K. R. and James, R. C.: NICAD: Accurate
Detection of Near-Miss Intentional Clones Using Flexible Pretty-Printing and Code Normalization, Proc. of
ICPC 2008, pp. 172–181 (2008).
吉田則裕，肥後芳樹，神谷年洋，楠本真二，井上克郎：
コードクローン間の依存関係に基づくリファクタリング支援，情報処理学会論文誌，Vol. 48, No. 3, pp. 1431–1442(2007).
Fowler, M.: Refactoring: Improving the Design of Existing Code, Addison Wesley (1999).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: A
Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code., IEEE Trans. SoftwareEng., Vol. 28, No. 7, pp. 654–670 (2002).
Jiang, L., Misherghi, G., Su, Z. and Glondu, S.:
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, Proc. of ICSE 2007, pp. 96–105(2007).
Baishakhi, R., Daryl, P., Vladimir, F. and Premkumar,
D.: A Large Scale Study of Programming Languages andCode Quality in Github, Proc. of FSE 2014, pp. 155–165(2014).
Rajapakse, D. C. and Jarzabek, S.: An Investigation ofCloning in Web Applications, Proc. of ICWE 2005, pp.
252–262 (2005).
Rajapakse, D. C. and Jarzabek, S.: Using Server Pages
to Unify Clones in Web Applications: A Trade-Oﬀ Analysis, Proc. of ICSE 2007, pp. 116–126 (2007).
Nakamura, Y., Choi, E., Yoshida, N., Haruna, S. andInoue, K.: Towards Detection and Analysis of Interlanguage Clones for Multilingual Web Applications, Proc.
of IWSC 2016, pp. 17–18 (2016).
Dean, T. R., Cordy, J. R., Malton, A. J. and Schneider, K. A.: Agile Parsing in TXL, Automated Software
Engg., Vol. 10, No. 4, pp. 311–336 (2003).
Levenshtein, V. I.: Binary codes capable of correcting
deletions, insertions and reversals, Soviet Physics Doklady, Vol. 10, pp. 707–710 (1966).
Cheng, X., Peng, Z., Jiang, L., Zhong, H., Yu, H. andZhao, J.: Mining Revision Histories to Detect Crosslanguage Clones Without Intermediates, Proc. of ASE
2016, pp. 696–701 (2016).
Nguyen, H. V., Kästner, C. and Nguyen, T. N.: Crosslanguage Program Slicing for Dynamic Web Applications, Proc. of ESEC/FSE 2015, pp. 369–380 (2015).
Synytskyy, N., Cordy, J. R. and Dean, T. R.: Robust
Multilingual Parsing Using Island Grammars, Proc. of
CASCON 2003, pp. 266–278 (2003).
Muhammad, T., Zibran, M. F., Yamamoto, Y. and Roy,C. K.: Near-miss Clone Patterns in Web Applications:
An Empirical Study with Industrial Systems, Proc. of
CCECE 2013, pp. 1–6 (2013).

c 2016 Information Processing Society of Japan⃝

8