A New Method to Detect Gapped Code Clones

Yasushi Ueda† , Toshihiro Kamiya†† , Shinji Kusumoto† , and Katsuro Inoue††

Graduate School of Information Science and Technology, Osaka University, Toyonaka-shi, 560-8531, Japan††

PRESTO, Japan Science and Technology Corporation, JAPAN
Abstract

It is generally said that code clone is a factor to make software maintenance diﬃcult. A code clone is theset of code portions in source ﬁles that are identical or similar to another. If we make some changes in sucha code portion, it might be necessary to apply the same changes in its clones. A code clone introduced by‘copy-and-paste reusing tends to have gaps because the developer often modiﬁes the code portion after
pasting. This paper proposes a new method to detect clones including gaps. In a case study, we conﬁrm
the eﬃciency of the method.
keywordSoftware maintenance, Code clone, Code visualization

論

文

不一致部分を含むコードクローンの抽出手法
植田 泰士†神谷年洋††

楠本 真二†

井上 克郎†A New Method to Detect Gapped Code Clones
Yasushi UEDA† , Toshihiro KAMIYA†† , Shinji KUSUMOTO† , and Katsuro INOUE†

あらまし ソフトウェアの保守性を阻害する一つの要因として，コードクローンが指摘されている．コードク
ローンとは，ソースコード中の同一，または類似した部分を指す．例えば，あるコード片に対して何らかの変更（機能追加，バグの修正等）を行う際は，そのコード片のコードクローン全てについて変更の是非を考慮する必要がある．大規模なソフトウェアの場合，それら全ての箇所を手作業で発見し，変更の是非を考慮することは非常に困難である．また，既存コードのコピーとペーストによる再利用によってコードクローンが生成される際には，部分的な変更が行われ，ペーストされたコード片はそのまま利用されることは少なく，コピー元との部分的な不一致が生じることが多い．本研究では，そのような不一致部分を含んだコードクローンを抽出する手法の提案を行う．また，本手法を，コードクローン分析環境 Gemini に実装し，大学におけるプログラミング演習で開発されたプログラムに適用するケーススタディにより，その有効性を確認した．
キーワード

ソフトウェア保守，コードクローン，コード視覚化

そこで，これまでに様々なコードクローン検出手法や

1. ま え が き

ツールが提案されている [1] [2] [3] [4] [5] [9] [10] [11]．

近年，ソフトウェアシステムの大規模化，複雑化に我々も文献 [8] において，新しいコードクローン検伴い，ソフトウェアの保守・デバッグ作業に要するコ出手法を提案している．提案手法に基づいて開発したストは増大しており，大企業では既存システムの保守

コードクローン検出ツール CCFinder は，大規模なソに多くのコストを費やすようになってきている．

フトウェアから実用的な時間でコードクローンを検出

保守作業を困難にする要因の一つとしてコードク

できるところに特長がある（注 1）．

ローンが指摘されている [6] [7]．コードクローンとは，

我々はこれまでに CCFinder を様々なソフトウェア

ソースコード中の同一，または類似した部分のことで開発組織で運用してきた．その結果，実利用を目指す

あり，「重複コード」とも呼ばれる．コードクローンが上での課題が幾つか顕在化した．その課題の一つが，ソフトウェア中に作り込まれる原因として，既存コー

不一致部分を含んだコードクローンを直接的に発見

ドのコピーとペーストによる再利用，頻繁に用いられできないことである．実際に，既存コードのコピーとる定型処理，パフォーマンス改善のための意図的な繰

ペーストによる再利用の際など，ペーストされたコー

り返し，コード生成ツールによって生成されたコード

ド片はそのまま利用されることは少なく，ペースト先などがある [4] [8]．コードクローンの存在が保守作業の文脈に合わせた部分的な修正や変更が行われる可能を困難にするのは，修正されるコード片のコードク性が高い．そのような場合，コピー元との不一致が生

ローンが存在すれば，その全てのコードクローンに対じるため，CCFinder を用いたクローン検出では，幾して修正の是非を検討しなければならないためである．

つかの相対的に短いクローンに分割され検出されてし† 大阪大学 大学院情報科学研究科，豊中市

Graduate School of Engineering Science, Osaka University,

まう．一般に，短いコードクローンはソフトウェア中に膨大に存在するため，不一致部分のために分割されToyonaka-shi, 560-8531 Japan†† 科学技術振興事業団 若手個人研究推進事業

PRESTO, Japan Science and Technology Corporation,
JAPAN

（注 1）
：例えば，100 万行規模のソースコードに対して，PC/AT 互換
機で，数分から数時間でコードクローンを検出できる

電子情報通信学会論文誌 X Vol. Jxx–X No. xx

pp. 1–??

xxxx 年 xx 月

1

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

C に対し部分的に類似しているコード片．つまり，構文的にも一致しない不一致コード (ギャップ (Gap)) を，C
If (a > b) { b++; a=1;}

部分的に含む．

resued by ‘copy-and-paste’‘copy-andpaste’
Reused

我々が検出対象にしているクローンの不一致部分
RenamedIf (a > b){// comment
b++;
a=1;
}

Exact clone

If (i > j){// comment
j++;
i=0;
}

(ギャップ (Gap)) とは，コピーとペーストによるプロ

Inserted

DeletedModified

If (i > j){i = i / 2;// comment
j++;
i=0;
}

If (i > j){// comment
i=0;}

If (i > j){// comment
j = j + 1;
i=0;}Parameterized clone

グラミングにおいて，ペーストされたコード片に含まれる，新規追加されたコード，削除されたコード，または構文が変更されたようなコードを意味する．図 1 に，Exact クローン，Parameterized クローン，Gapped
クローンの例を示す．

Gapped clone

2. 2 CCFinder の検出するコードクローン

Gap

CCFinder は単一または複数のソースファイル中か

図 1 コードクローンの分類
Fig. 1 Classification of code clones

ら，極大クローンのクローンペアを検出し，その位置情報を出力する．処理は以下の 4 ステップからなる．

た短いコードクローンを検出しようとすると，不必要

ステップ 1(字句解析): ソースファイルを字句解析(lexical analysis) によってトークン列に変換する．入な情報を多く検出してしまうことで分析者の手間が増

力ファイルが複数の場合には，それらのファイルの連

え，また検出のための計算コストも高くついてしまう．

結した単一のトークン列を生成する．

そこで，本論文では，不一致部分を含んだコードク

ステップ 2(変換処理): 実用上意味を持たないコー

ローンの抽出手法の提案を行う．本手法は，一致箇所

ドクローンを取り除くこと，および，些細な表記上のを検出した後，連結されるべき不一致箇所を特定し，違いを吸収することを目的とした変形ルールによって，さらに，マンマシンの共同作業を採り入れることで，トークン列を変換する．例えば，この変換によって変低い計算コストでそれらのコードクローンを抽出する．

数名は同一のトークンに置換されるので，変数名が付

また，本手法を，コードクローン分析環境 Gemini [12]

け替えられたコード片もコードクローンであると判定に実装し，大学におけるプログラミング演習で開発さすることができる．

れたプログラムに適用しその有用性を評価した．
以降，2. 節では，コードクローンの分類等について，

ステップ 3(検出処理): トークン列の中から，指定された長さ（最小一致トークン数）以上一致している

3. 節では，提案手法について述べる．4. 節では，適用実験の結果とその分析，考察について述べ，最後に 5.

ような部分クローン列を全て検出する．

節で，まとめと今後の課題を述べる．

クローンペアについて，元のソースコード上での位置

2. 準

備

2. 1 コードクローンの分類
一般に，ある与えられたコード片 C に対するコードクローンは，以下の 3 種類に分類される．

ステップ 4(出力整形処理): 検出されたそれぞれの情報を出力する．
以上の検出手順により，CCFinder は Exact クロー
ン，および Parameterized クローン (ステップ 2 の変換処理より) を検出する．以降，これらを併せて，Ng
クローン (Ng-clone (Non-gapped clone)) と呼ぶ．

Exact クローン (Exact clone):
C に対し，プログラムテキストとして完全に一致した

比較的小さな値に定めれば，偶然の一致等により非コード片．但し，文字列としての一致とは異なり，空常に多くのコードクローンが検出されてくる．逆に，

白，改行，コメントなどの違いは考慮しない．

大きくすると，分析粒度が粗くなる．既存コードのParameterized クローン (Parametarized clone):
C に対し，変数名，定数名，クラス名，メソッド名等

コピーとペースト，およびその修正によって発生したのユーザ定義名の違いを除き一致しているコード片．

ため検出されない場合がある．一方，ある一定の長さ

つまり言語依存の予約語等の構文的な一致を指す．

のギャップをコードクローンの中に含むことを許容す

Gapped クローン (Gapped clone):

ると，個々の一致箇所が連結され大きなコードクロー

2

一般に，ステップ 3 における最小一致トークン数を

コードクローンなどは，個々の一致箇所が小さくなる

論文／不一致部分を含むコードクローンの抽出手法ンとみなすことができ，検出の際，偶然の一致等によSource files

る単純に小さなコードクローンとは区別可能となる．

Algorithmic analysis

したがって，Gapped クローンを探すことにより，単Ng-clone detection

純に小さなコードクローンの情報を検出せず，かつ取

Ng-clones

りこぼしの少ない分析を行うことができる．
Gap identification

3. Gapped クローン抽出手法
Gaps

仮に Ng クローンの位置情報が存在した場合，本研

Corresponding between
gaps and Ng-clones

究でいう Gapped クローンの個々の発見問題は，NgVisualization

クローンの組み合わせ決定問題に帰着する．
Gap-and-clone scatter plot

しかし，複数の Ng クローンが互いに重なりあい密集した際には，あるひとつの Ng クローンからの次のNg クローンへの結合選択肢が多数存在し，全体としての Gapped クローン検出は，組合せ爆発を起こし，計算コストは膨大になる．経験上，そのように Ng ク

Source code investigation
using gaps and Ng-clones information
Tuned parameters

図 2 Gapped クローン抽出プロセス
Fig. 2 Extraction process of gapped clone

ローンが密集していることは多く，個々の Gapped ク
ローンを全て検出するということは，大規模ソフト
ウェアには向かない．

として，一方，実用的な応用としては，個々の Gapped ク

コード列 X: “ABCDCDEFBCDG”,

ローンの正確な一致箇所，不一致箇所まで知る必要性

コード列 Y: “ABCEFBCDEBCD”

はなく，密集範囲全体としてどの辺りが類似しているかが識別できれば十分なことも多い．例えばメソッドの 2 つ の コ ー ド 列 の 比 較 を 考 え る ．こ こ で ，“A”,“B”,“C”,... の記号は，文字，トークン，行，文，等の類似性を判断する場合などである．

関数などプログラムテキスト中の任意の要素を表すこ

そこで我々は Gapped クローンの検出に際し，個々とができる．つまり，本節における検出プロセスは，の Gapped クローンを自動的に検出するのではなく，

特定の Ng クローン検出アルゴリズムの検出粒度に束互いに素な Ng クローンの連結集合を検出することに縛されることはなく，各記号は，任意の Ng クローンよるマンマシン共同作業としてのアプローチをとる．

検出ツール毎の検出粒度に対応するものとする．また，

3. 1 抽 出 手 順

我々は複数ファイル間での比較，もしくは単一ファイ

図 2 に Gapped クローン抽出プロセスを示す．本プ

ル内での比較を想定している．以下の説明において，ロセスは次の 4 つのステップで構成されている．
ステップ 1: Ng クローン検出 (Ng-clone detection)，

コード列 X, Y が同じ場合も検出プロセスは同様である．

ステップ 2: ギャップ検出 (Gap identiﬁcation)，ステップ 1 (Ng クローン検出)

ステップ 3: 視覚化 (Visualization)，

入力ソースコードから Ng クローンを検出し，効率よステップ 4: ソースコード分析 (Source code inves-くギャップ検出を行うための準備として Ng クローン

tigation)．
ステップ 1 においては，入力されたソースコードから Ng クローンを検出する．次にステップ 2 で，ステッをソーティングする．
例における検出結果を，表 1 に示す．本表には，長さ 2 以上の Ng クローンが含まれている．

プ 1 で検出された Ng クローンの位置情報からギャッ

Ng クローンの最小一致長を定めなければ，これら

プの位置情報を生成する．そしてステップ 3 において，全てと，記号単一で一致する部分が検出されることにそれら Ng クローン位置情報とギャップ位置情報を視なる．しかし，この例において，たかだか長さ 12 の覚化する．最後にステップ 4 で分析者が，視覚化されコード列の中に長さ 2 以上の Ng クローンが 7 つも検た情報を利用して，Gapped クローンのソースコード

出されているように，代入文，変数宣言などの単純なを分析するという手順である．

構文により，比較的短いクローンの中には単なる偶然

以下，例を用いて検出プロセス手順を説明する．例の一致が多い．よって以降，最小一致長 (以降，閾値
3

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

1) が指定可能であることを前提とする．
この検出の際に決められる閾値 1 は Gapped クロー// for each NG-clone
for (i = 0; i < ngCloneTotalCount; i++){
NgClone ci = sortedNgCloneDB.get(i);ンの中に含まれる，それぞれ一致部分の最小長となる．

// search connection targets

つまり，最終的に分析を行いたい Gapped クローンのfor (j = i; j < ngCloneTotalCount; j++){
NgClone cj = sortedNgCloneDB.get(j);最小長よりも小さい値が指定されなければならない．

// if NG-clone ci and cj are near

また，ステップ 2 においてギャップを効率よく検出

dx = distance(ci.codeInX, cj.codeInX);するための前準備として，Ng クローンの検出結果に

dy = distance(ci.codeInY, cj.codeInY);
if (((0 <= dx) && (dx < threshold2)) &&対してソーティングを行う．Ng クローンの 2 つのコー((0 <= dy) && (dy < threshold2))){// create new gap information

ド片対それぞれ (以下，コード片 X,Y) は，単一ファGap newGap = new Gap(ci, cj);

イル内で閉じており，複数ファイルをまたぐことがな

gapDB.add(newGap);}

い (Gapped クローンとしても同様である) ので，まずelse{

ファイルの組み合わせで Ng クローン集合を分割する// optimization

ことができる．そして，分割されたそれぞれの集合のif (distance(c.codeInX, d.codeInY) >= threshold2)
break; // goto next i’s loop

中でソーティングを行う．ソーティングに用いられる}キーは，優先順位の高いものから，以下の通りとなる．
コード片 X のファイル内での出現位置，
コード片 Y のファイル内での出現位置．
ここでいうファイルは，例においてコード列 X，Y を指す．表 1 では，既にソーティングが完了している．
ステップ 2 (ギャップ検出)
ソーティング済みの Ng クローン情報を元に，ギャッ}}// Function "distance(x, y)" computes the// difference from end position of code portion x// to start position of code portion y.
// The result may be zero or minus when x and y// are overlapping or when y appears ahead of x.

図 3 ギャップ検出アルゴリズム
Fig. 3 Gap identification algorithm

プの位置情報を生成する．
図 3 にアルゴリズムの詳細を擬似コードとして示す．

の for ループでは，いったん Ng クローン ci からの各ギャップ毎に生成すべき情報は，ギャップのソース

距離が閾値 2 以上の Ng クローンが見つかれば，それコード上での位置情報，ギャップの両端に連結される

以降は閾値 2 以内の距離にある Ng クローンが見つか

2 つの Ng クローン情報であり，これらはステップ 3で利用される．表 2 は，表 1 の Ng クローンに対して生成されたギャップ位置を示している (g1, ..., g7)．
図 3 の中で現れている threshold2( 以降，閾値 2)
は Gapped クローン中に含まれることが許容されるそることは有り得ない．ここで注意すべきは，もし閾値

れぞれのギャップの上限長を表している．

側の for ループは定数時間で終了し，アルゴリズム全

また，図 3 の中の最適化では，Ng クローン情報がソート済みであるという事実を利用している．内側

2 が入力ソースコード長に対して十分小さく，全 Ng
クローンの密集度合いに偏りがなければ，ある Ng ク
ローンから閾値 2 以内の距離にある Ng クローンは，
高々定数個以内であると考えられる．したがって，内体の計算複雑さは，O(n)(n: Ng クローン数) である．
また，閾値 2 の値の決定方法については議論の必要があるが，本研究においては定数値として扱う．よっ表 1 Ng クローン検出結果 (長さ 2 以上)
Table 1 Detected Ng-clones that are longer than 2
Ng クローン
ID
c1
c2
c3
c4
c5
c6
c7

コード列
一致
X
Y
文字列
1- 3
1- 3
“ABC”
2- 4
6- 8
“BCD”
2 - 4 10 - 12
“BCD”
5 - 6 11 - 12
“CD”
5- 7
7- 9
“CDE”
7 - 11
4- 8“EFBCD”
9 - 11 10 - 12
“BCD”

(コード片の位置は記号の開始位置と終了位置を表す．例えば “6- 8” は，6 番目の記号から 8 番目の記号までを意味する．)

4

表 2 ギャップ位置
Table 2 Gap location
ギャップ ID
g1
g2
g3
g4
g5
g6
g7

コード列
X
Y
4
4-6
4
4 - 10
4- 6
4- 8 4 - 9
9 - 10
5- 8
9
8
-

長さ
3
7
3
6
2
4
1

論文／不一致部分を含むコードクローンの抽出手法

1

1

2

3

4

A

B C

E

Code sequence Y
5 6
7 8
F

B

C D

9

10

11 12

1

2

3

4

E

B

C

A

B C

E

D
1

A
B

3

C

4

D

5

C

6

D

7

E

8

F

9

B

c1
c2
g2

g1

c3
g5

g3

10 C

g6
g4

Code sequence X

Code sequence X

2

c4

c5
g7

c6

F

B

C D

9

10 11 12

E

B

C

D

A

2

B

3

C

4

D

5

C

6

D

7

E

8

F

9

B

c1
g1
g3
c5

g7
c6
c7

10 C

c7

11 D

11 D

12 G

12 G

: gc1
: gc2

A,B,C, ... : Character, token, line, statement or function, ... etc.
: Ng-clone
with disregard to minimum length of matched string: Identified gap: Non-identified gap ( threshold2 = 3 )

図 4 散布図 (フィルタリング前)
Fig. 4 Scatter plot without filtering

Code sequence Y
5 6 7 8図 5 散布図 (フィルタリング後)
Fig. 5 Scatter plot with filtering

プを取り除く本ステップは随意的なものであるが，散布図の視認て，閾値 2 は認識するギャップの最大長となっている．
本例においては，閾値 2 は 3 と定める．したがって性を改善することができる．
図 4 には，コード片 X，Y から検出され得る全 Ng

実際は，g2，g4，g6 は検出されてこない．

クローン，全ギャップが描かれている．しかし，先にステップ 3 (視覚化)ステップ 3-1 (散布図)

述べたように大規模ソフトウェアを対象とした場合，

Ng クローンとギャップを散布図に描画する．
この時点で，Ng クローンとギャップの位置情報を得ることができている．従って，図 4 のように Ng クロー

布図上には多くの短い Ng クローンやギャップが存在

ンとそれらのギャップをそれぞれ独立に散布図上に描プ長) を用いれば，Ng クローンとギャップの数を制御す

画すれば，擬似的に Gapped クローンの視覚化を行うることができる．しかし，これらの閾値では，Gapped

ことができる (以降，本散布図をGap-and-clone 散

クローンとしての長さを制御することはできない．例

布図，あるいは，混乱の恐れがない場合は単に散布図

えば，閾値 1 を 3 にすれば，c4 , g2，g5 を除いた全と呼ぶ)．

ての Ng クローンとギャップが現れる．逆にもう少し短い Ng クローンは非常に数多くの存在するので，散し，分析が煩雑になる．
閾値 1(Ng クローン最小一致長) と閾値 2(最大ギャッ

散布図の両座標軸は，各コード列を表しており，左大きな値，5 にすれば，Ng クローン c6 しか残らない．

上角が原点になっている．図 4 では，垂直軸がコード

そこで，Gapped クローンを散布図上でフィルタリ

片 X，水平軸がコード列 Y を表しており，各 Ng ク

ングするため，各 Ng クローンの連結集合の長さを新ローンは，両座標軸上で対応した 2 つの要素が一致

しいパラメータとして導入する．その長さとは，連結していることを表している黒い四角形を連結した線

集合中に含まれ得る Gapped クローンの上限長である．

分として表されている．また，各ギャップは，両端のNg クローンを結ぶ灰色の線分として表現されている．

表 3 Gapped クローン
Table 3 Gapped clone path list

つまり，黒い線分と灰色の線分を順に辿ったものが，Gapped クローンを表していることになる．表 3 に，そのパス (辿り方) とその対応コード列を示す．但し，g2，g4，g6 は認識されなかったので，それらを通る
辿り方は示さない．
ステップ 3-2 (フィルタリング)
Gapped クローンに関係のない Ng クローンとギャッ

ID
gc1
gc2
gc3

パス
c1 g1 c5 g7 c7
c1 g3 c6
c2 g5 c4

コード列 X
コード列 Y“ABC-CDE-BCD” “ABC---CDEBCD”“ABC---EFBCD”“ABCEFBCD”“BCDCD”“BCD--CD”(“-” はギャップを表している．つまり，それぞれの“-” の数がギャップの長さであり，そのギャップの両端の Ng クローンの距離となる．)
5

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

連結集合中に含まれ得る Gapped クローンの上限

スコード長に近づくにつれ，ステップ 2 の計算複雑さ

長の算出手順は，まずギャップ検出の際に生成した，は O(n2 )(n: Ng クローン数) に近づく．ただし，ソーギャップと Ng クローンの結合情報を 用いて Ng ク

スファイルの境界を越えて Ng クローンを連結するこローンを連結集合に分類する．そして，各連結集合とはないという経験則を用いることにより，実用上のs の中で，各コード片がコード列 X(Y) において最も先 頭 に近 いコ ード 片の 開 始位 置を s の開 始位 置

問題にはなっていない。

sStartX(sStartY) とし，同様に最も先頭から遠いものを s の終了位置 sEndX(sEndY) として求め，次式
sSize = max( sSizeX , sSizeY ),sSizeX = sEndX − sStartX,sSizeY = sEndY − sStartYで求まる sSize が連結集合中に含まれ得る Gapped
クローンの上限長となる．この長さの下限値を閾値 3とし，閾値 3 以上の長さを持つ連結集合のみを表示させることでフィルタリングを実現する．本例において，3. 2 実装本手法をコードクローン分析環境 Gemini [12] に実装した．Gemini は，CCFinder を内部的に利用し，検出されたコードクローンの位置を示す散布図，対応ソースコードを参照するビューなどその他様々なビューをユーザに対して提供する．本散布図を Gap-and-clone
散布図として実装することでユーザは，Ng クローン連
結集合を選択し対応したソースコードを参照できる．

4. 適 用 実 験閾値 3 を 8 とするならば，散布図は図 5 のようになる．

4. 1 概ステップ 4 (ソースコード分析)

本適用実験においては，大阪大学のプログラミン

要各パラメータの値を調整しながら，散布図を利用してグ演習で学 生が作成したソースコードを対象とし，ソースコードの分析を行う.

ンターフェイスを通じて，散布図上で特定の Gapped

Gapped クローンの検出手法の適用を行う．
本プログラミング演習課題は，，Pascal 風言語 (Pascal 言語 のサ ブ セット) で 記述 さ れた プ ログ ラ ムをCASL(アセンブリ言語) に変換するコンパイラを C 言クローンや Ng クローンを指定し対応するソースコー

語で作成することである．また，その作成課題は，次ドを参照する，あるいは，選択したソースコードだけの 3 つのステップ (副課題) で構成されている．

最後に，Gapped クローンが擬似的に現れている散布図を用いてユーザが実際に分析を行う．ユーザーイ

を散布図で表示したりできるものとする．

ステップ 1(課題 1): 構文解析器 (P arser) の作成.

ユーザーは，散布図やソースコードを参照すること

ステップ 2(課題 2): 意味解析器 (Checker) の作成.

により，以下のパラメータを調整したり，あるいは検ステップ 3(課題 3): コンパイラ (SP C) の作成．

出対象のソースコードを追加あるいは削除することで，また，Checker と SP C を作成するにあたり，各課分析を進める．

題の前課題のプログラムを再利用する（拡張して開閾値 1 Ng クローン検出における最小一致長，
閾値 2 ギャップ検出におけるギャップ上限長，発する）よう要求されている．つまり，Checker はP arser を再利用することで，SP C は Checker を再閾値 3 Ng クローン連結集合の下限長．

利用することで作成される．したがって，各課題のプ

これらのパラメータは計算コストと完全性のトレード

ログラム間の関係は，本手法で検出することを想定しオフである．またその閾値毎にその効果は異なる．例ているコピーとペーストおよびその修正によって書かえば，閾値 1 を小さくすると解析時間が増大する．数れたコードと同じと考えることができる．

多く修正が施されたような，それぞれの一致部分が短

4. 2 分析い Gapped クローンを検出しようと思えば，閾値 1 に本手法の有効性を確認するため，閾値 1(Ng クロー

小さな値を定めなければならない．しかし，メソッドンの最小一致長) や，閾値 3(Ng クローン連結集合のの抽出のようなリファクタリングなどが目的の場合は，下限長) を調整することで短い Ng クローンがある程

一般的にそのような Gapped クローンを 1 つモジュー度の大きさを持った Gapped クローンとしてどの程度
Gap-and-clone 散布図に現れてくるのかを確認する．
本適用実験では 69 人のプログラム (計 360KLOC)を対象にしたが，文献 [12] の課題間再利用率評価実験において，その評価が最も高かった学生 (S) を例にルにまとめるのは困難であると思われるので，さほど小さな値にする必要はないと考えられる．また，閾値

2 は大きくすると，1 つの Ng クローンから連結される
Ng クローンの数が増え，解析時間が増大する．ソー6

論文／不一致部分を含むコードクローンの抽出手法
Checker

SPC(Frequency)

ParserParser

1500

Checker

1000

500
SPC

0
0 10

図 6 Ng クローン散布図 (閾値 1 = 10 トークン)
Fig. 6 Ng-clone scatter plot (threshold1 = 10 tokens)
Checker

SPC

30

40

50
(tokens)

図 9 図 6，7 における Ng クローン出現頻度
Fig. 9 Number of Ng-clones in Figures 6 and 7

Parser(Frequency)

Parser

20

1500

1000
Checker

500

SPC

0
0 10

Shown up as gapped clones
that are longer than 30 tokens

20

30

40

50
(tokens)

図 10 図 8 における Ng クローン出現頻度
Fig. 10 Number of Ng-clones in Figure 8
図 7 Ng クローン散布図 (閾値 1 = 30 トークン)
Fig. 7 Ng-clone scatter plot (threshold1 = 30 tokens)
ParserChecker

SPC

コードクローンも含まれる．また，少し大きな Ng ク

Parser

ローンのみを調べるため，閾値 1 を 30 トークンにすると Ng クローン散布図は図 7 のようになる．この図

Checkerには，30 トークン以上の長めの Ng クローンしか現れていないので，容易に分析が行える．しかし，コピーとペーストとその修正によって生じたコードクローン

SPCなどは多く抜け落ちている可能性がある．
そ れ に 対 し ，Gap-and-clone 散 布 図 は ，個々の

図 8 Gap-and-clone 散布図 (閾値 3 = 30 トークン)
Fig. 8 Gap-and-clone scatter plot (threshold3 = 30
tokens)Gapped クローンを検出することに比べて計算コス
トが小さいまま，きめの細かい分析が容易に行える．
図 8 は，閾値 1 を 10 トークン，閾値 2 を 10 トーク
ン，閾値 3 を 30 トークンとした Gap-and-clone 散布

とって，その分析結果を示す．
図 6 に S の P arser(2267 トークン)，Checker(4394

図である．つまり，図 8 では，図 7 に現れたすべてのを表示する散布図を，Gap-and-clone 散布図と区別す

Ng クローン，および，10 トークン以上の Ng クロー
ンと 10 トークン未満のギャップで構成された 30 トー
クン以上の Gapped クローンが現れている．
Ng クローン散布図においての分析のきめの細かさるため，Ng クローン散布図 (Ng-clone scatter plot)と容易さとの間でのトレードオフと，Gap-and-cloneと呼ぶことにする．

散布図によるそれらのトレードアップを定量的に説明

図 6 の Ng クローン散布図では，10 トークン以上のNg クローンが全て描かれている (閾値 1=10 トークン)．図中に膨大に存在する黒い点は，非常に多くの短い Ng クローンが存在することを意味しており，これする．図 9，図 10 の棒グラフには，Ng クローン散布

らには，単一の変数宣言が一致しただけといった短い

まれる Ng クローンは殆どが 10 から 30 トークン未満トークン)，SP C(5738 トークン) の 3 プログラム間の比較結果の散布図を示す．ここで Ng クローンのみ

図上の Ng クローンの出現頻度と Gap-and-clone 散布
図上の Ng クローンの出現頻度が表されている．
図 9 の棒グラフは，図 6 の Ng クローン散布図に含7

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

であり，図 7 の Ng クローン散布図には，少ししか Ng[9] R. Komondoor, and S. Horwitz,

クローンが現れていないことを示している．逆に，図10 の棒グラフでは，約 2000 個近い 10 から 30 トー
クンの Ng クローンが 30 トークン以上の Gapped クInternational Symposium on Static Analysis, 2001.
[10]

他の学生についても確認することができた．

J. Krinke,“Identifying Similar Code with Pro-

gram Dependence Graphs”, Proceedings 8th Work-

ローンを構成するのに寄与していることが分かる．
これらのことは，特に学生 S に限ったことでなく，“Using slicing to

identify duplication in source code”, Proceedings 8th

ing Conference on Reverse Engineering, 2001, 562584.
[11]

J. Mayland, C. Leblanc, and E. Merlo,“Experi-ment on the Automatic Detection of Function Clones

5. まとめと今後の課題

in a Software System Using Metrics”,

Proceed-ings IEEE International Conference on Software

本研究では，ギャップの位置情報に基づいた Gapped
クローン抽出手法の提案を行った．また，本手法をコー

Maintenance-1996, 1996, 244-253.
[12]

植 田 泰 士, 神 谷 年 洋, 楠 本 真 二, 井 上 克 郎,

“開 発 保性の確認のため，大学におけるプログラミング演習で守 支援 を目指し たコード クロー ン分析環 境”, 大 阪大
学 ソフ トウェア 工 学講座技 術報告 SEL-June-3-2003,(http://sel.ist.osaka-u.ac.jp/~lab-db/betuzuri/

作成されたプログラムに適用した．適用実験においてarchive/423/423.pdf)， 2003.

ドクローン分析環境 Gemini へ実装し，本手法の有効は，本手法がコードクローン分析のきめの細かさと容（平成年月日受付，月日再受付）

易さとの間でのトレードオフを軽減することを確認で植田泰士

きた．今後の課題としては，大規模なソフトウェアや平 13 阪大・基礎工・情報卒．平 15 同大
大学院博士前期課程修了．現在，宇宙開発事業団所属．在学中，コードクローン分析

実際の保守作業への適用が挙げられる．
文
[1]

献

の研究に従事．

B.S. Baker, “A Program for Identifying DuplicatedCode”,

Computing Science and Statistics, 1992,

24:49-57.
[2]

B.S. Baker,

神谷“On Finding Duplication and Near-

Duplication in Large Software Systems”, Proceedings

平 8 阪大・基礎工・情報中退．平 13 同大

the 2nd Working Conference on Reverse Engineer-

大学院博士課程了．現在，科学技術振興事
業団 PRESTO 研究員．博士 (工学)．オブ
ジェクト指向関連技術，ソフトウェア保守

ing, 1995, 86-95.
[3]

M. Balazinska , E. Merlo, M. Dagenais, B. Lagüe, andK. Kontogiannis, “Measuring Clone Based Reengi-(メトリクス，コードクローン)，認知科学に関する研究に従事．情報処理学会，IEEE

neering Opportunities”, Proceedings 6th IEEE International Symposium on Software Metrics, 1999,
292-303.
[4]

I.D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and
L. Bier,S. Ducasse, M. Rieger, and S. Demeyer.

“A Lan-118.
M. Fowler,

Refactoring: improving the design ofexisting code, Addison-Wesley, 1999.

アの生産性や品質の定量的評価，プロジェ
クト管理に関する研究に従事．情報処理学会，IEEE，IFPUG
各会員．

井上

克郎

（正員）

T. Imai, Y. Kataoka, T. Fukaya, “Evaluating Soft-昭 54 阪大・基礎工・情報卒．昭 59 同

ware Maintenance Cost Using Functional Redun-

大大学院博士課程了．同年同大・基礎工・情報・助手．昭 59 〜昭 61 ハワイ大マノア
校・情報工学科・助教授．平 1 阪大・基礎

dancy Metrics”, Proceedings of 26th Annual International Computer Software and Applications Conference, 2002, 299-306.
T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder:
A multilinguistic token-based code clone detection
system for large scale source code”, IEEE Transactions on Software Engineering, 2002, 28(7):654-670.

8

（正員）

昭 63 阪大・基礎工・情報卒．平 3 同大

ference on Software Maintenance-1999, 1999, 109-

[8]

真二

学院博士課程中退．同年同大・基礎工・情報・助手．平 8 同大講師．平 11 同大助教
授．平 14 阪大・情報・コンピュータサイ
エンス・助教授．博士 (工学)．ソフトウェ

cated Code”, Proceedings IEEE International Con-

[7]

楠本

Trees”, Proceedings IEEE International Conference

guage Independent Approach for Detecting Dupli-

[6]

各会員．

“Clone Detection Using Abstract Syntax

on Software Maintenance-1998, 1998, 368-377.
[5]年洋工・情報・講師．平 3 同学科・助教授．平7 同学科・教授．工学博士．平 14 阪大・情報・コンピュータサイエンス・教授．ソフトウェア工学の研究に従事．情報処理学会，日本ソフトウェア科学会，IEEE，ACM各会員．