Vol. 0

情報処理学会論文誌

No. 0

1959

コードクローン間の依存関係に基づくリファクタリング支援
吉 田 則 裕†楠 本 真 二†肥 後 芳 樹†井 上 克 郎†神 谷 年 洋††

コードクローンとは，互いに一致または類似したコード片（ソースコードの断片）を持つコード片を意味し，ソフトウェア保守を困難にしている要因の 1 つとされている．例えば，あるコード片にバグが含まれていた場合，そのコード片のコードクローン全てに対して，修正の是非を検討する必要がある．コードクローンを取り除く方法として，リファクタリングの適用が考えられる．リファクタ
リングとは，ソフトウェアの外部的振舞いを変化させることなく，内部の構造を改善する作業のことである．しかし，クローンセット（互いに一致または類似したコード片の集合）に含まれるコード片と周辺のコード片間に依存関係が存在すると，リファクタリングが困難になる場合がある．本稿は，クローンセット間の依存関係を利用したリファクタリング支援手法を提案する．まず，異なるクロー
ンセットに含まれるコード片間の依存関係に着目し，そのような依存関係を持つコード片の集合を
チェーンドクローンセットと定義する．そして，メトリクスを用いてチェーンドクローンセットの特徴を判定し，適用可能なリファクタリングパターンを提示する．最後に，リファクタリング支援ツー
ルとして実装することで，いくつかのオープンソースソフトウェアに適用し，有効性の評価を行う．

On Refactoring Support Based on Code Clone Dependency Relations
N ORIHIRO YOSHIDA ,† YOSHIKI H IGO ,† T OSHIHIRO K AMIYA ,††S HINJI K USUMOTO † and K ATSURO I NOUE †Code clone is a set of code fragments identical or similar to each other. It is generally said that code clone
is one of the factors that make software maintenance more difﬁcult. If we modify one of them, it is necessary to determine whether or not we have to modify the others. Refactoring is a disciplined technique forrestructuring an existing body of code, altering its internal structure without changing its external behavior.
However, there are dependency relations between code fragments belonging to the different clone sets (aclone set is an equivalence class of code clones), and it is difﬁcult to apply refactoring to such code clones.
In this paper, we propose a refactoring support method by using dependency relations. At ﬁrst, we focus on
dependency relations between code fragments belonging to the different clone set, and we deﬁne “chainedclone set” as such code fragments. Then, we deﬁne the metrics for providing an appropriate refactoring
pattern to each “chained clone set”. Finally, we present the “chained clone set” refactoring support tool that
we have developed, together with some case studies.

コストが，特に大規模ソフトウェアの保守において問1. は じ め に題となる．

ソフトウェア保守を困難にする要因の 1 つとして，
1)∼5)

ソフトウェア保守性を改善する技術の 1 つとして，．コードクロー

リファクタリング6) がある．リファクタリングとは，

ンとは，ソースコード中に存在する互いに一致，またソフトウェアの外部的振る舞いを変化させることなは類似したコード片（ソースコードの断片）を意味す

く，内部の構造を改善する技術のことである．Fowler

る．例えば，あるコード片にバグが含まれていた場合，は，リファクタリングを検討すべき箇所にあらわれ

そのコード片のコードクローン全てに対して，修正のる特徴を Bad Smell と呼び，その代表例としてコー

是非を検討する必要がある．このような作業に要する

ドクローン（Duplicated Code）を挙げている．また，

コードクローンが指摘されている

コードクローンを単一のモジュールに集約する手法として，“Pull Up Method” や “Extract Method”，“Extract† 大阪大学 大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka
University†† 産業技術総合研究所
National Institute of Advanced Industrial Science and Technology

SuperClass” などのリファクタリングパターンを紹介している．
これまでに，我々はコードクローン検出ツール1

2

情報処理学会論文誌

1959

CCFinder7) およびリファクタリング支援環境 Aries8)

ぶ．また，クローンの同値類をクローンセットと呼ぶ．

を開発してきている．CCFinder は，ソースコードに

ソースコード中でのクローンを特にコードクローンと字句解析と正規化処理を行うことで得られたトーク

いう9) ．

ン列の同値性に基づいてコードクローン検出を行う．

2.2 コードクローン検出ツール: CCFinder

CCFinder の特徴は，表現上の差異があるコードクロー

CCFinder はプログラムのソースコード中に存在すンを検出できること，および百万行単位のソースコー

る極大クローンを検出し，その位置をクローンペアのドであっても実用時間で解析できることである．Aries

リストとして出力する．検出されるコードクローンのは，CCFinder の出力情報を基に，リファクタリングに最小トークン数はユーザが前もって設定できる．

適した単位（e.g. クラス，メソッド単位）でクローンセット（互いに一致または類似したコード片の集合）を検出し，更にメトリクスで特徴付けすることでリファクタリングパターンの提示を行う．

CCFinder のコードクローン検出手順は以下の 4 つの STEP からなる．

STEP1（字句解析）: ソースファイルを字句解析することによりトークン列に変換する．入力ファイ

これまでに，Aries を用いて様々なソースコードをルが複数の場合には，個々のファイルから得られ解析した結果，異なるクローンセットに含まれるコー

たトークン列を連結し，単一のトークン列を生成

ド片間に依存関係が存在する場合が確認されている．

する．

例えば，クローンセット Sa に 2 つのメソッド ma1 ，STEP2（変換処理）: 実用上意味を持たないコード

ma2 が含まれ, 同様にクローンセット Sb に 2 つのコー

クローンを取り除くこと，及び，些細な表現上のド片 mb1 ，mb2 が含まれるときに，メソッド ma1 が違いを吸収することを目的とした変換ルールによメソッド mb1 を呼び出し，メソッド ma2 がメソッド

りトークン列を変換する．例えば，この変換によ

mb2 を呼び出しているという場合である．

り変数名は同一のトークンに置換されるので，変Aries は，上述した呼出関係の解析は行っていない
ため，ユーザは自らクローンセット Sa と Sb 間の呼出数名が付け替えられたコード片もコードクローンであると判定することができる．

関係を把握する必要がある．もし，ユーザが Sa に対

STEP3（検出処理）: トークン列の中から指定されして ma1 と mb1 ，ma2 と mb2 の呼出関係を考慮せずた長さ以上一致している部分をクローンペアとしに集約を試みると，呼出関係が保存されない可能性がて全て検出する．

ある．有効なリファクタリング支援を行うためには，

STEP4（出力整形処理）: 検出されたクローンペアに

クローンセット Sa と Sb は，まとめてユーザに提示

ついて，ソースコード上での位置情報を出力する．

するべきであると考えられる．

2.3 リファクタリング支援環境: Aries

本稿では，クローンセット間の依存関係を利用したリファクタリング支援環境 Aries は，CCFinder の出

リファクタリング支援手法を提案する．まず，異なるク

力情報を基に，リファクタリングに適した単位（e.g.

ローンセットに含まれるコード片間の依存関係に着目

クラス，メソッド単位）でクローンセットを検出し，し，そのような依存関係を持つコード片の集合をチェー

更にメトリクスで特徴付けすることでリファクタリン

ンドクローンセットと定義する．そして，チェーンドグパターンの提示を行う．

クローンセットの特徴に応じて，適用可能なリファク

リファクタリングに適した単位とは，ソースコード

タリングパターンを提示するためのメトリクスを定義

上の構造的なまとまりのことである．クローンセット

する．最後に，提案手法をリファクタリング支援ツーに含まれるコード片が構造的なまとまりを持っている

ルとして実装し，2 つのオープンソースソフトウェア

なら，容易に集約することが出来る．現在，Aries はに適用することで有効性の評価を行う．

Java 言語を対象として実装されているため，用いる構

2. コードクローン
2.1 コードクローンの定義

造的なまとまりは以下の 12 種類である．
宣言: class { }, interface { }メソッド:メソッド本体, コンストラクタ,

文:

if, for, while, do, switch,

スタティックイニシャライザ

あるトークン列中に存在する 2 つの部分トークン
列 α，β が等価であるとき，α と β は互いにクローンであるという．またペア（α，β ）をクローンペアと呼ぶ．α，β それぞれを真に包含する如何なるトー
クン列も等価でないとき，α，β を極大クローンと呼try, synchronized
クローンセットの特徴付けに用いるメトリクスの 1
つとして，分散度メトリクス DCH(S)8) について説明

Vol. 0

コードクローン間の依存関係に基づくリファクタリング支援

No. 0

クラスへの集約を検討するべきであることがわかる．

 P Aa1   Ba2(a) DCH(S1 ) = 0



b

 C  c(b) DCH(S2 ) = 1

!" D d3 E  e(c) DCH(S3 ) = ∞図 1 DCH メトリクスの算出例
Fig. 1 Example of DCH metric calculation

3. 提 案 手 法
3.1 本研究の動機
リファクタリングを行う際は，“保守性を悪化させるコード（Bad Smell）の特定” と “外部的振る舞いを変更させず保守性を向上させる修正作業” を行う必要がある．
既に述べたように，保守性を悪化させるコードとしてコードクローンが指摘されている．門田らは，コー
ドクローンを含むモジュールの方が保守コストが大きくなる事例を紹介している10) ．彼らが紹介した事例では，より行数の多いコードクローンを含むモジュール
ほど，保守コストが大きくなっていた．
検出したコードクローンを容易にリファクタリング

する．クローンセット S はコード片 f1 , f2 , · · · , fn

するためには，次の 2 つの条件を満たしていることがを含んでいるとする．クラス Ci はコード片 fi を含ん望ましい．

でいるクラスとする．もしクラス C1 , C2 , · · · , Cn が(条件 1) クローンセットに含まれるコード片が構造共通の親クラスを持つ場合は，その共通の親クラスの中で，クラス階層的に最も下位（最も深い階層）に位置するクラスを Cp で表すとする．また D(Ck , Ch )的なまとまりを持っている．

(条件 2) クローンセットに含まれるコード片と周辺のコード間に結合が少ない．

はクラス Ck と Ch のクラス階層における距離を表す(条件 1) については，2.3 節で述べている．(条件 2)とする．この時，の例として，メソッド呼出を含む場合（図 2(a)）や，フィールド変数を使用（参照，代入）している場合（図DCH(S) = max {D(C1 , Cp ), · · · , D(Cn , Cp )}2(b)）が挙げられる．図 2(a) では，メソッド a1 と b1がコードクローンとなっており，点線矢印で表すようと表される．直観的には，DCH(S) メトリクスはクにメソッド a1 が a2 を呼び出し，メソッド b1 が b2 をローンセット S に含まれる各コード片間のクラス階層

呼び出している．図 2(b) では，メソッド a1 とメソッ内における最大の距離を示す．図 1(a)〜(c) は，それぞ

ド a2 はフィールド変数 va を参照しており，メソッド

れクローンセットに含まれる 2 つのコード片に対して，

b1 とメソッド b2 はフィールド変数 vb を参照してい

DCH(S) メトリクスを算出した例である．DCH(S)る．このような周辺のコードと結合度が高いコードクの値は，全てのコード片が 1 つのクラス内に存在すローンを集約することは困難である．なぜなら，集約る場合は 0 (図 1(a))，あるクラスとその直接の子クラ作業を行う際に，メソッド間の呼出関係やメソッドとス内に存在する場合は 1 となる (図 1(b))．例外的に，

フィールド変数の関係に不整合が起きないよう考慮す

コードクローンが存在するクラスが共通の親クラスをる必要があるからである．

持たない場合は ∞ とする (図 1(c))．このメトリクス

ここまでに述べたように，コード量が大きいコード

は，クラスライブラリ等の修正不可能なクラスを除外

クローンにかかる保守コストや，周辺のコードと結合したクラスを対象として計算される．

が多いコードクローンに対するリファクタリングの難DCH(S) メトリクスにより，クローンセット S のしさが問題になりやすい．我々はコードクローン分析

コード片を集約したモジュールを置くことが出来るを行う中で，そのようなコードクローンのパターンをクラス（集約先）を特定することが出来る．例えば，見つけた．それは，異なるクローンセット間に依存関

DCH(S) メトリクスの値が 1 の場合は，そのクロー係が存在する場合である（図 3(a)）． 図 3(a) は，クランセットが存在するクラスの親クラスに集約できるこ

ス A，B 間にまたがる 3 つのクローンセットを表してとがわかる．また，DCH(S) メトリクスの値が ∞ のいる．これら 3 つのクローンセットは，他のクローン

場合は，分析対象内に集約先位置になるクラスが存在

セットとの間にメソッド呼出関係やフィールド変数のしないため，クラスの作成，もしくは継承関係のない

参照関係が存在する．図 3(a) のクラス A，B のよう情報処理学会論文誌

4

1959

 #"
 
!

0 12 10

       

      +* -,+. / * , -/. -,    "!#%$'&   "!(#$)   '+   +
"$ "! #&%(    

      
 )     )+* -,+. /(a) メソッド呼び出し, -/. -,

0 12 10
  "!$#&%'+* -,. /, -/. -,(a) リファクタリング前, -/. -,)+*-,.*&)

0 12 10
 
#$&% %
 "!
#$&% %
' "()+*-,.*&)(b) フィールド変数の使用

図 2 周辺のコードと結合している例
Fig. 2 Examples of codes are coupled each other0 12 10 

(b) リファクタリング後（3つ同時）"
9;:=<>:9
9;:=<>:79%'& ( *),+.-0/
9;:=<>:9
9;:=<>:9 #$120345 5 4675 8


に，類似したクラスには，“Extract SuperClass” パター
ンの適用を検討すべきと指摘されている6) ．クラス A，

B に “Extract SuperClass” パターンの適用した結果が
図 3(b) である．
図 3(a) から図 3(b) へのリファクタリングを支援す  !

る方法として，図 3(a) 中に含まれる 3 つのクローン  !

    
     
 

セットを同時に提示することが考えられる．
その理由の 1 つ目は，1 つのクローンセットを対象(c) リファクタリング後（1 つのみ）としたリファクタリングは，呼出関係が原因で困難な

図 3 異なるクローンセット間に依存関係が存在する例
Fig. 3 Example of clone sets that have dependency relations

場合があるからである．例えば，図 3(a) のクローン
セットの 1 つ（メソッド a1 とメソッド b1 ）に対して集約を試みると，親クラスに新たに作成したメソッド

わせを “チェーンドクローンセット” と呼び，“チェーs1 から子クラスのメソッド a2 と b2 を呼び出すこと

ンドクローンセット” に対するリファクタリング支援が出来なくなる（図 3(c)）．この問題を解決するため手法を提案する．

には，子クラスのメソッドに対応する抽象メソッドを

3.2 チェーンドクローン

親クラスに追加する必要がある．3 つのクローンセッ

チェーンドクローンを定義するための準備として，トを同時にリファクタリングする際にはこのような工メソッドチェーンを定義する．メソッドの集合が与え夫は必要ない．

られたとき，それらメソッド間の依存関係を表す有向2 つ目の理由は，図 3(a) のようなクローンセットの組み合わせを手作業で見つけ出すことは難しいからでグラフが連結グラフになるなら，そのメソッドの集合
をメソッドチェーンと定義する．

ある．なぜなら，大規模ソフトウェアは大量のクロー

ここで扱う依存関係は，以下の 2 種類である．

ンセット含んでいることが多いため，それらの全てに(1) メソッドの呼出関係

対して呼出関係の有無を確認することは困難だから(2) 同一フィールド変数の共有（参照または代入）である．また，呼出関係の理解支援にはコールグラフ

図 4(a) は呼出関係を含むメソッドチェーンの例であ(Call Graph) がよく用いられるが，頂点数（メソッドる．この例では，メソッド a が b を，メソッド b が c数）が膨大になりやすい大規模ソフトウェアへの適用を呼び出している．また，図 4(b) は，図 4(a) のメソッは現実的でない．

ドチェーンの依存関係をラベル付き有向グラフで表し

本稿では，図 3(a) のようなクローンセットの組み合たものである．有向辺に付属しているラベル “call” は，

Vol. 0

コードクローン間の依存関係に基づくリファクタリング支援

No. 0



aab(a) 呼出関係

 



b

a



xrefer (3)

  

 

b

assign (2)

call

call
c

refer (1)

call

call

5



yassign (4)cc(a) フィールド変数の使用(b) 呼出関係を表す
グラフa

図 4 呼出関係と呼出関係を表すグラフ
Fig. 4 Method chain whose dependency relations are method
invocations

RX(1)

依存関係の種類がメソッドの呼出関係であることを表Ry (3)Ay (4)

c

している．例えば，メソッド a が b を呼び出している
とき，有向辺 (a, b) を引き，ラベル “call” を付ける．

AX (2)b(b) フィールド変数の共有関係を表すグラフ

なお，1 つのメソッドが同一のメソッドを 2 回呼び出
している場合は，それらメソッド間に呼出関係を表す
有向辺を 2 本追加する．
図 5(a) はフィールド変数を使用しているメソッド
チェーンの例である．図 5(a) の有向辺に付属している
ラベル “refer” はフィールド変数の参照を表しており，“assign” はフィールド変数への代入を表している．図5(a) のメソッド a と b は，フィールド変数 x を共有しており，メソッド a，c はフィールド変数 y を共有している．また，図 5(b) は，図 5(a) のメソッドチェー

図5フィールド変数の使用と共有関係を表すグラフ（括弧内の数
字は対応する関係を表す）
Fig. 5 Chained method whose dependency relations are sharing
variables     a



A

A

11

 a a21 a a   a

12

22

1

2

図 6 ケース 1
Fig. 6 Case 1ンに含まれるメソッド間の共有関係をラベル付き有向グラフで表したものである．有向辺に付属しているラベル “Rx (ref er)” はフィールド変数 x への参照による共有関係，ラベル “Ay (assign)” は，フィールド変られるリファクタリングについて説明するため，適用

数 y への代入による共有関係を表している．例えば，可能なリファクタリングパターンが異なる 4 つのケー

メソッド a が変数 x を参照し，かつメソッド b が変スを紹介する．

数 x を使用（参照または代入）しているとき，有向辺

ケース 1 は，チェーンドクローンセットが 1 つのク(a, b) を引き，ラベル “Rx ” を付ける．また，メソッド

ラスに包含されている場合である．ケース 1 では，そc が変数 y に代入し，かつメソッド a が変数 y を使用の 1 つのクラス内にクローンセットを集約可能である．

しているとき，有向辺 (c, a) を引き，ラベル “Ay ” を

図 6 は，ケース 1 のチェーンドクローンセットに対す付ける．

るリファクタリングの例である．互いにクローンであ次に，メソッドチェーンを用いてチェーンドクロー

るメソッド a11 とメソッド a12 を集約しメソッド a1

ンを定義する．2 つのメソッドチェーンが互いにチェーとし，同様に互いにクローンであるメソッド a21 とメ

ンドクローンとなるのは，各メソッドチェーンが持つ

ソッド a22 を集約しメソッド a2 としている．

依存関係のグラフが同形であり，対応する頂点（メソッド）が同一クローンセットに含まれ，対応する辺（依存関係）のラベルは等しいときである．また，互いにチェーンドクローンであるメソッドチェーンの同値類
を，チェーンドクローンセットと呼ぶ．

3.3 チェーンドクローンセットに対するリファクタ
リング
ここでは，チェーンドクローンセットに対して考えケース 2 は，チェーンドクローンセットが以下の 2つの条件を満たす場合である．

• チェーンドクローンセットに含まれるメソッドは，
全て兄弟クラスに属する．

• 各メソッドチェーンは，それぞれ 1 つのクラスに包含されている．
ケース 2 は，“Pull Up Method” パターンを適用することで，リファクタリングできる．つまり，兄弟クラス

情報処理学会論文誌

6



S

 

 
A
         
a2

  b


(b)



 

B

 b

S2



C

   c  Sab1

  ab2

B  b

 

A

 



B

1

 

S1

D

  d

1

2

1

2



2

 
A
         a    a
S ab

1


(a) 


  A     aB  b

a1



1959

 

A

 S  cd2



B

 

C



D

図 8 ケース 4
Fig. 8 Case 4  b23

図 7 ケース 2 とケース 3
Fig. 7 Case 2 and Case 3• 各メソッドチェーンは，複数のクラスにまたがって存在する．つまり依存関係が複数のクラス間にまたがっている．

にまたがって存在するクローンセットを，親クラスにケース 4 は，チェーンドクローンセット単位でリファ集約することでリファクタリングできる．図 7(a) は，

クタリングできない場合である．だが，チェーンドク

ケース 2 に対するリファクタリングの例である．このローンセットを複数のクローンセットとして扱い，そ例では，兄弟クラスであるクラス A，B にまたがってれぞれの親クラスに集約することでリファクタリング

存在する 2 つのクローンセットを，親クラス S に作できるため，クローンセット単位でのリファクタリン

成したメソッドに集約している．具体的には，クラス

グを検討すべきである．図 8 は，ケース 4 にクロー

A のメソッド a1 とクラス B のメソッド b1 を集約し，ンセット単位でのリファクタリングを適用した例であ親クラス S のメソッド ab1 とし，同様にクラス A のる．この例では，兄弟クラスであるクラス A，B にまメソッド a2 とクラス B のメソッド b2 を集約し，親たがって存在する 2 つのクローンセットを，それぞれ

クラス S のメソッド ab2 としている．

の親クラスに作成したメソッドに集約している．具体

ケース 3 は，チェーンドクローンセットが以下の 2つの条件を満たす場合である．

的には，クラス A のメソッド a とクラス B のメソッ
ド b を集約し，親クラス S1 のメソッド ab とし，同様• チェーンドクローンセットに含まれるメソッドをにクラス C のメソッド c とクラス D のメソッド d を持つクラスは，いずれも共通の親クラスを持た集約し，親クラス S2 のメソッド cd としている．

ない．

• 各メソッドチェーンは，それぞれ 1 つのクラスに包含されている．

3.4 チェーンドクローンセットの分類
前節の 4 つのケースのように，チェーンドクローン
セットを分類する．前節の 4 つのケースには，それぞケース 3 は，“Extract SuperClass” パターンを適用すれ適合するための条件があった．それらは，次の 2 つることで，リファクタリングできる．つまり，チェーである．

ンドクローンセットに含まれるメソッドを持つクラス

C1 チェーンドクローンセットに含まれるメソッドがに対して，共通の親クラスを作成し，クラス間をまたがって存在するクローンセットを，新たに作成した親クラスに集約することでリファクタリングできる．図所属するクラス間の関係についての条件

C2 メソッドチェーンに含まれるメソッドが所属するクラス間の関係についての条件

7(b) は，ケース 3 に対するリファクタリングの例であ

ここでのクラス間の関係とは，クラス階層上の関係

る．この例では，まず共通の親クラスを持たない 2 つのことである．クラス間の関係は，次に 3 つに分類でのクラス A, B に，共通の親クラス S を作成している．

きる．

その後，ケース 2 と同様に兄弟クラスとなったクラス

R1 全ての同一クラス

A，B にまたがって存在する 2 つのクローンセットを，

R2 共通の祖先クラスを持つ

親クラス S に作成したメソッドに集約している．

R3 共通の祖先クラスを持たないクラス

ケース 4 は，チェーンドクローンセットが以下の条件を満たす場合である．

条件の種類とクラス間の関係を組み合わせることにより，チェーンドクローンセットを表 1 のように分類

Vol. 0

コードクローン間の依存関係に基づくリファクタリング支援

No. 0



できる．
次の 4 つの分類については，以下に示すリファクタ AX YWZP[ V *\ Z'[G]^U_ T

リングを行うことできると考えられる．
分類 1 前節のケース 1 である．図 6 の例のように，

M1

チェーンドクローンセットを包含しているクラスに，全てのクローンセットを集約することができる．
分類 2 前節のケース 2 である．図 7(a) の例のように，“Pull Up Method” パターンを適用できる．
分類 3 前節のケース 3 である．図 7(b) の例のように，“Extract SuperClass” パターンを適用できる．
分類 4 前節のケース 4 である．図 8 からわかるように，チェーンドクローンセット単位でのリファク
タリングを行うことが出来ないが，クローンセッ



7
S

M2

S1

SKTUV a

S2

SWTUV a

1

2



B

C

SWTUV b

M3

1

SWTUV c

SKTUV b

SKTUV c

2

1

2


  


%'& (*),+-.0/21 1 1  1  /1  1  1 2   2/87 !"#$1
  #3$ 45 3$6 5 9:<;>= 5?A@B:<;G= ?H1IB :*;>= ?J B
DC8:<!;GEF=  ?J/ 1 B :<;G=  ?J/ B :<;>= K?HM/ 7L B:<;>=<: ?A@NB
OCP!E2
KRQ
図 9 提案するメトリクスの算出例
Fig. 9 Example of proposed metrics calculation

ト単位でのリファクタリングを検討すべきである．

3.5 チェーンドクローンセットの分類を目的とした
メトリクス

M1 , M2 , · · · , Mn が含まれるとする．更に，メソッド
チェーン Mi には，複数のメソッドが含まれるとする．

ここでは，チェーンドクローンセットの分類を行う
ためのメトリクスを 2 つ提案する．1 つは C1 を評価

このとき，DCHD(T ) メトリクスの定義は以下のようになる．

するメトリクス，もう 1 つは C2 を評価するメトリク
スである．これらメトリクスは，メソッド間のクラス

DCHD(T ) = max{DCH(M1 ), · · · , DCH(Mn )}階層上における関係を表す．この関係は，2.3 節で述べた DCH(S) メトリクス（クローンセット S に含まれ

図 9 は，提案する 2 つのメトリクスの算出例である各コード片間のクラス階層内における最大の距離）

る．ここでは，分類 2 のチェーンドクローンセット

によって表すことができる．

を例として用いる．このチェーンドクローンセットに

まず，DCH(S) メトリクスを用いて，C1 を表す

は，クラス A，B ，C にまたがって 2 つのクローン

DCHS(T) メトリクスを定義する．チェーンドクロー

セット S1 ，S2 が存在する．各クローンセットについンセット T を n 個のクローンセット S1 , S2 , · · · , Sn にてそれぞれ DCH(S1 )，DCH(S2 ) を求めると，クラ分割する (すなわち，S1 ∪S2 ∪· · ·∪Sn = T, Si ∩Sj = ∅,ス A，B ，C は共通の直接の親クラス S を持ってい1 ≤ i ≤ n, 1 ≤ j ≤ n, i 6= j)．更に，クローンセッ

るため両者とも 1 になる．DCHS(T ) の値は，これト Si には，複数のメソッドが含まれるとする．このらの最大値の 1 である．また，このチェーンドクロー

とき，DCHS(T ) メトリクスの定義は以下のようにンセットには，3 つのメソッドチェーン M1 , M2 , M3なる．

が含まれている．各メソッドチェーンについてはそれ
ぞれ DCH(M1 )，DCH(M2 )，DCH(M3 ) を求める

DCHS(T ) = max{DCH(S1 ), · · · , DCH(Sn )}と，各メソッドチェーンはそれぞれ 1 つのクラスに包含されているため全て 0 になる．よって，DCHD(T )同様に DCH(S) メトリクスを用いて，C2 を表す DCHD(T) メトリクスを定義する．チェーンド
クローンセット T 中には，n 個のメソッドチェーン
表 1 チェーンドクローンセットの分類
Table 1 Categorization of chained clone sets

PP
PP C2
PP
C1
R1
R2
R3

R1

R2

R3

の値は，これらの最大値の 0 である．

3.6 実

装

提案手法を Aries のコンポーネントの 1 つとして実装した．具体的には，Aries に対して，以下の 3 つの機能を追加した．

(F1) チェーンドクローンセットの検出機能(F2) 提案したメトリクスの算出機能

分類 1
分類 2
分類 3

分類 4

(F3) チェーンドクローンセットおよびメトリクス値の表示機能(F1) は，まず CCFinder および Aries を用いて各ク

情報処理学会論文誌

8

ローンセットが含むコード片を検出する．次に，それ1959

ローンセット数で除算した値とした．

らコード片を対象に，メソッド呼出関係と変数の共有

設定した評価基準に基づいて，クローンセットの検関係を表すグラフを構築する．その後，構築したプロ

出結果（表 2）と分類 1，2，3 に属したチェーンドク

グラム依存グラフに含まれる部分グラフから同形グ

ローンセットの検出結果（表 3(a)）を比較する．

ラフを検出することにより，チェーンドクローンセッ

まず，ANTLR では分類 2 に属したチェーンドクロー

トを検出する．(F2) は，Aries の DCH(S) メトリク

ンセットのメソッド数やメソッド行数が極めて大きかっスを計算する機能を拡張した．(F3) を実現するためた．分類 2 のメソッド数はクローンセットの 8.3 (19/2.3)に，チェーンドクローンセットを閲覧するビューを追倍，メソッド行数は 5.0 (54.0/10.8) 倍であった．一方，

加した．

分類 1，3 に属したチェーンドクローンセットのメソッド
数は両者ともクローンセットの 1.7 (4.0/2.3) 倍，メソッ

4. ケーススタディ
4.1 概

ド行数はそれぞれ 2.6 (27.7/10.8) 倍，3.2 (35.0/10.8) 倍要であった．分類 2 に属するチェーンドクローンセット

提案手法の有効性を確かめるため，ケーススタディを行った．具体的には，以下の 2 つを確認した．

• クローンセット単位の検出と比較して，検出できたチェーンドクローンセットの規模が大きいかの多くは，図 10 のような，Java，C#，C++に対応した出力を行う箇所から検出された．これら言語に対応した出力処理は類似しており，大量のコードクローンを含んでいた．

• クローンセット単位でのリファクタリングと比較

次に，JBoss の結果を見てみると，分類 1，2，3 にして，容易にリファクタリングできているか属したチェーンドクローンセットのメソッド数はそれ

なお，この章におけるチェーンドクローンセットは，

ぞれクローンセットの 1.8 倍〜2.8 倍，メソッド行数

極大チェーンドクローンセット を指す．
☆

適用対象は，次の 2 つのオープンソースソフトウェがそれぞれ 2.4 倍〜3.2 倍であった．これらの結果か
ら，チェーンドクローンセットの規模がクローンセッ
トに比べて大きいことがわかる．続いて，分類 1，2，

アである．

• ANTLR 2.7.4 ( 4.7 万行，285 クラス）

3 に属したチェーンドクローンセットの検出結果（表• JBoss 3.2.612) ( 64 万行， 3364 クラス）

3(a)）と，分類 4 に属したチェーンドクローンセット

11)

ANTLR は，3 つのプログラミング言語（Java，C#，の検出結果（表 3(b)）を比較する．3.4 節で述べたよC++）に対応したコンパイラ・コンパイラである．JBoss

うに，表 3(a) で示した分類 1，2，3 は，チェーンド

は，J2EE アプリケーションサーバである．

クローンセット単位でのリファクタリング可能である

4.2 チェーンドクローンセットの検出が，表 3(b) で示した分類 4 はチェーンドクローンセッ

前述の 2 つのソフトウェアに対し，提案手法に基づ

ト単位でのリファクタリングが出来ない．分類 1，2，

くチェーンドクローンセットの検出，および従来手法

3 と比較して分類 4 に属するチェーンドクローンセッに基づくクローンセットの検出を行った．提案手法で

表 2 クローンセットの検出結果
Table 2 Detection result of clone sets

はメソッド単位のコードクローンのみを扱うため，従来手法に基づく検出でもメソッド単位のクローンセッ
トのみを対象とした．また，CCFinder が検出するコー
ドクローンの最小トークン数は 30 に設定した．

検出数
ANTLR
JBoss
152
377

検出結果の比較を行うために，2 つの評価基準とし(a) 分類 1，2，3

ソッド数は，検出単位毎（クローンセット毎やチェー
総クローンセット数や各分類に属する全てのチェーン
ドクローンセット数で除算した値とした．メソッド行
数は，検出単位毎に最長メソッドの行数を求め，総ク

分類

検出数
ANTLR
JBoss

1
2
3

3
6
1

与えられたチェーンドクローンセットを真に包含する如何なるチェーンドクローンセットも存在しないとき，そのチェーンドク
ローンセットを極大チェーンドクローンセットと呼ぶ．

メソッド数
ANTLR
JBoss
4.0
5.8
19
4.5
4.0
6.8

16
17
13

メソッド行数
ANTLR
JBoss
27.7
16.2
54.0
17.1
35.0
21.5

(b) 分類 4

ローンセット数や各分類に属する全てのチェーンドク
☆

メソッド行数
ANTLR
JBoss
10.8
6.63

表 3 チェーンドクローンセットの検出結果
Table 3 Detection result of chained clone setて，メソッド数と，メソッド行数を用いる．ここで，メンドクローンセット毎）に含まれるメソッド数を求め，

メソッド数
ANTLR
JBoss
2.3
2.4

検出数
ANTLR
JBoss

メソッド数
ANTLR
JBoss

0

-

4

19

メソッド行数
ANTLR
JBoss
54.5

Vol. 0

コードクローン間の依存関係に基づくリファクタリング支援

No. 0

トは少ないことがわかる．特に，ANTLR からは検出されなかった．一方，JBoss では 4 種類のチェーンド
クローンセットが検出された．これらのメソッド数,
メソッド行数は，分類 1〜3 に比べて数倍の大きさに9;:F<G>@HAICKJ

なっている．

4.3 チェーンドクローンセットに対するリファクタ
リングの例

9;:F<G>@HAICMLANTLR から検出された全てのチェーンドクローン
セットと JBoss から検出された 8 つのチェーンドク
ローンセットを対象として，提案手法に基づくリファ
クタリングを行った．ここでは，それらの中から 2 つの例を紹介する．
まず，図 10 ，図 12 で示すチェーンドクローンセッ

9 :=<?>;@BADCE   
 ! "#  $ % &'# (0  11

0 1 1

0 1 1   
/*)$ # -'+# -,. /(
0 1 1   
./ *)$ #  '+8#  ,.(0 1 1

 324 
5! "#  $ #  '#  % &6( 2. 
! "#  $ # -'#  % &6( 324 
5! "#  $ #  '#  % &6(   !"#$ &%('$$) *+!, -.) /類 2 であるから，“Pull Up Method” パターンを適用し: ; ;

た．その結果，図 11 のようになった．ANTLR パッ &!"$ 0"213*+) .4 ) 5/: ; ;

ケージ中の examples ディレクトリ以下にある全てのテストケース（計 86 ファイル，文法ファイル）を用い

 768  %9'+$$) *) &.) &, -2/て回帰テストを行い，外部的振る舞い（出力結果）がた．その結果，図 13 のようになった．JBoss パッケー

, " 7-  
 ! "#  $ % &' # (図 10 ANTLR から検出されたチェーンドクローンセットの例
Fig. 10 Example of a chained clone set in ANTLR

グパターンを適用できることを確認した．図 10 は分変化していないことを確認した．また，図 12 は分類

"" 7  
 ! "#  $  % &' # /( 
*)$ #  '+# -,. /(
0 1 1トに対し，提案手法により提示されたリファクタリン

3 であるから，“Extract SuperClass” パターンを適用し9 7      

図 11 図 10 のチェーンドクローンセットをリファクタリングした例
Fig. 11 Example of refactoring of a chained clone set of Fig. 10

ジの testsuite ディレクトリ以下にある全テストケース（計 65 ファイル，JUnit フレームワーク13) を使用）を用いて回帰テストを行い，外部的振る舞いが変化していないことを確認した．
更に，従来手法に基づいて，チェーンドクローンセッ
トを構成するクローンセットに対し集約を試みると，工夫が必要となる場合があることを確認した．具体的には，図 10，図 12 からそれぞれクローンセットを 1
つ選び，従来手法により提示されたリファクタリング

*

+ % ,-.$ &,/01"2 &#($ &
6708:9;=<0>1 
6708:9;=<0>

2 !" #$"% &
6708:9
% %;=<0>3
'( " #$)

*

5  % /01"2&#(($ &
33  
4 "" #$!% &
% %
'(" #$

図 12 JBoss から検出されたチェーンドクローンセットの例
Fig. 12 Example of a chained clone set in JBoss

パターンの適用をした．まず，図 10 のクローンセッ
ト 1 に対し集約を試みると，提示されたリファクタリ(1) 対象ソフトウェア ケーススタディでは，Java 言

ングパターンの適用に加えて，クローンセット 2 のメ語で開発された 2 つのオープンソースソフトウェ

ソッドに対応する抽象メソッドを CodeGenerator クラアを対象として有効性の確認を行った．オブジェ

スに追加する必要があった．なお，クローンセット 2

クト指向型言語であれば，Java 言語以外で開発さに対して集約を試みた場合も同様であることが確認でれたソフトウェアであっても適用可能であると考きた．また，図 12 のクローンセット 2 を新たに作成えられる．なぜなら，Java 言語以外のオブジェク

した親クラスに集約を試みると，提示されたリファク

ト指向型言語で開発されたソフトウェアであってタリングパターンの適用に加えて，クローンセット 2

も，リファクタリングや依存関係解析を適用可能のメソッドに対応する抽象メソッドを親クラスに追加だからである．今後，Java 言語以外で開発されたする必要があった．

ソフトウェアや商用ソフトウェアなど，様々な種

4.4 考

察

ここでは，今回のケーススタディに基づいて，提案
手法の妥当性・制限等について考察を行う．

類のソフトウェアを対象に有効性の評価を行う必要がある．

(2) 被支援者の知識，経験 今回のケーススタディに10

情報処理学会論文誌

 .


1959

                                .
#       ! "#$%     # ## "!&$%     # "!&$% #  #   "!&$% #    "   ";=<?>A@=BDCFE #  ! "!&$%  ! )/  #0 1% $% ('     )*      +('    )/  # # +;=<?>A@=BDCFE #  ! "!&$%  ! )/  #0 1% $% ('     )*      ,- +('    )/  # # ,/ +    )*      23  ;=<G>H@=BDCIE !  # "#$%  ! )/  #0 1: $% ('     )*  #   ,4  5$% ,--, 673   " 8 9/+ ('    )/  #   ,4 #5$% ,-,6&3   " 8 9*+
図 14

0
0

分類 4 のチェーンドクローンセットの例
Fig. 14 Example of Category 4$ # */,-1 $"& $   


!! "!# $# #(4) 分類 4 のチェーンドクローンセットへの支援
JBoss から分類 2 のチェーンドクローンセットを内包する分類 4 のチェーンドクローンセットが検出された（図 14）．提案手法は，これに対しク

% ! "&' # ()& $(*+,-

し，有効性の評価を行う必要がある．

ローンセット単位でのリファクタリングを提示す.  # */,!-

図 13 図 12 のチェーンドクローンセットをリファクタリングした例
Fig. 13 Example of refactoring of a chained clone set of Fig. 12

るが，内包された分類 2 のチェーンドクローンセッ
トに “Pull Up Method” リファクタリングパターンを適用可能である．このような場合は，内包されたチェーンドクローンセットに対してリファクタ

おけるリファクタリング作業は，全て著者が行っリングパターンの提示を行うべきであると考えらた．そのため，手法の詳細を知らない人やリファれる．

クタリング経験が少ない人に対しても，有効な支援が行えるかどうか評価する必要がある．例えば，5. 関 連 研 究

一般の開発者に本稿のツールを使用してもらい，

CCFinder や Balazinska2) らの手法を用いることによ

リファクタリングにかかった時間を計測すること

り，クローンセットの検出を行うことはできる．本稿

で効率を評価するということが考えられる．

の手法では，チェーンドクローンセット単位でのリファ(3) 対象とするコード片や依存関係の種類 提案手法

クタリングを提示することにより，大規模なリファク

は，メソッドより小さい単位のコード片からな

タリングを実現することが出来た．また，CCFinder がるクローンセットは対象としていない．また，メ

検出するクローンセットには容易にリファクタリング

ソッドの呼出関係および変数の共用による依存関

できないものが含まれており，Balazinska らの手法も係のみを扱っているため，その他のデータ依存関同様と考えられる．本稿では，それら容易にリファク

係や制御依存関係を対象としていない．今後，対タリングできないクローンセットを組み合わせること象とするコード片や依存関係を増やすことで検出で容易にリファクタリングできる場合があることを示

可能なチェーンドクローンセットの規模を大きくし，それらクローンセットに対するリファクタリング

Vol. 0

コードクローン間の依存関係に基づくリファクタリング支援

No. 0

手法を提案した．

Komondoor4) らの手法は，プログラムスライシング技術を用いて，ソースコードからプログラム依存グラフを構築し，そのグラフ上で同形である箇所をコードクローンとして検出している．よって，本稿で用いている CCFinder が検出できないコードクローン（一部の文の出現順序が異なっている reodered clone 等）を検出することができる．しかし，プログラム依存グラフの構築にかかる計算コストは非常に大きいため，大規模ソフトウェアへの適用は現実的でない．本稿の手法は，CCFinder が検出したコードクローンに対して，
メソッド呼出関係と変数の利用関係のみを解析しているため，ケーススタディで示した規模のソフトウェ
アに適用可能である．実際に，ANTLR を対象としたチェーンドクローンセットの検出を約 1 分 4 秒で行う
ことができた☆ ．

6. ま と め
本稿では，クローンセットに含まれるメソッド間の依存関係に着目し，チェーンドクローンセットを定義した．そして，チェーンドクローンセットに対しリファ
クタリングパターンを提示するためのメトリクスを提案した．最後に，提案手法をリファクタリング支援
ツールとして実装し，2 つのオープンソースソフトウェ
アに適用することで，有効性の評価を行った．有効性の評価として，チェーンドクローンセットの規模がク
ローンセットと比べて大きいこと，およびチェーンド
クローンセットのリファクタリングがクローンセット
単位のリファクタリングと比べて容易であることを確認した．
今後の課題としては，様々なソフトウェアを対象とした有効性の評価，チェーンドクローンセットの中に異なる分類のチェーンドクローンセットが包含されて112) Balazinska, M., Merlo, E., Dagenais, M., Lague,
B. and Kontogiannis, K.: Advanced clone-analysis
to support object-oriented system refactoring, Proc.
Working Conference on Reverse Engineering(WCRE2000), pp.98–107 (2000).
3) Baxter, I., Yahin, A., Moura, L., Anna, M. and Bier,
L.: Clone Detection Using Abstract Syntax Trees,
Proc. International Conference on Software Maintenance(ICSM98), pp.368–377 (1998).
4) Komondoor, R. and Horwitz, S.: Using Slicing to
Identify Duplication in Source Code, Proc. International Static Analysis Symposium(SAS2001), pp.40–
56 (2001).
5) Krinke, J.: Identifying Similar Code with Program Dependence Graphs, Proc. Working Conference on Reverse Engineering (WCRE2001), pp.301–
309 (2001).
6) Fowler, M.: Refactoring: improving the design ofexisting code, Addison Wesley (1999).
7) Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder:
A multi-linguistic token-based code clone detection
system for large scale source code, IEEE Transactions on Software Engineering, Vol. 28, No. 7, pp.
654–670 (2002).
8) Higo, Y., Kamiya, T., Kusumoto, S. and Inoue, K.:
ARIES: Refactoring Support Environment Based on
Code Clone Analysis, Proc. IASTED International
Conference on Software Engineering and Applications(SEA2004), pp.222–229 (2004).
9) 井上克郎，神谷年洋，楠本真二：コードクローン
検出法，コンピュータソフトウェア，Vol.18, No.5,
pp.47–54 (2001).
10) 門田暁人，佐藤慎一，神谷年洋，松本健一：コー
ドクローンに基づくレガシーソフトウェアの品質の分析，情報処理学会論文誌， Vol.44, No.8, pp.
2178–2188 (2003).
11) ANTLR: http://www.antlr.org.
12) JBoss: http://www.jboss.org.
13) JUnit: http://www.junit.org.

いる場合への対処，対象とする依存関係やコード片の(平成 xx 年 x 月 x 日受付)

拡大が挙げられる．

(平成 xx 年 x 月 x 日採録)

謝辞 本研究は一部，文部科学省リーディングプロ
ジェクト「eSociety 基盤ソフトウェアの総合開発」，日

吉田 則裕（学生会員）

本学術振興会の科研費（課題番号：17200001）の支援

平 16 九工大・情報工・知能情報を受けている．

卒．平 18 阪大大学院博士前期課程

参 考 文 献1) Baker, B. S.: A Program for Identifying Duplicated Code, Proc. Computing Science and Statistics,
Vol.6, pp.49–57 (1992).
☆

実行環境: CPU Xeon 2.80GHz，メモリ 2.5GB，OS FreeBSD 6.1RELEASE修了．現在同大大学院博士後期課程

1 年．コードクローン分析の研究に従事．人工知能学会会員．

情報処理学会論文誌

12

1959

肥後 芳樹（正会員）

楠本 真二（正会員）

平 14 阪大・基礎工・情報中退．平昭 63 阪大・基礎工・情報卒．平 3

18 同大大学院博士後期課程修了．現

同大学院博士課程中退．同年同大・

在日本学術振興会特別研究員．コー

基礎工・情報・助手．平 8 同講師．平

ドクローン分析・リファクタリング

11 同助教授．平 14 阪大・情報・コ支援の研究に従事．

ンピュータサイエンス・助教授．平17 同教授．博士 (工学)．ソフトウェアの生産性や品質の定量的評価，プロジェクト管理に関する研究に従事．電子情報通信学会，IEEE，JFPUG, PM 各会員．

神谷 年洋

井上 克郎（正会員）

平 8 阪大・基礎工・情報中退．平昭 54 阪大・基礎工・情報卒．昭13 同大大学院博士課程了．同年科学59 同大大学院博士課程了． 同年同技術振興事業団研究者．平 17 産業

大・基礎工・情報・助手．昭 59〜昭技術総合研究所研究員．博士 (工学)．

61 ハワイ大マノア校・情報工学科・

オブジェクト指向関連技術，ソフト助教授．平 1 阪大・基礎工・情報・ウェア保守 (メトリクス，コードクローン)，認知科学

講師．平 3 同学科・助教授．平 7 同学科・教授． 工学に関する研究に従事．電子情報通信学会，電気学会，

博士．平 14 阪大・情報・コンピュータサイエンス・教IEEE，各会員．

授．ソフトウェア工 学の研究に従事．電子情報通信学会，日本ソフトウェア科学会，IEEE，ACM 各会員．