クラス階層構造を利用したコードクローン集約支援
手法の改良
佐野由希子†
楠本肥後 芳樹†（正員）

真二†（正員）

Improving Code Clone Merging Method Based on ClassHierarchy
Yukiko SANO† , Nonmember, Yoshiki HIGO† ,and Shinji KUSUMOTO† , Members†

大阪大学大学院情報科学研究科，吹田市

図 1 コードクローンの分布状況と対応する DCH の値
Fig. 1 Code clone distributions and the corresponding DCH values.

Graduate School of Information Science and Technology,
Osaka University, 1–5 Yamadaoka, Suita-shi, 565–0871 Japan

ために行った実験について述べる．

2. 従 来 手 法
2. 1 メトリックス DCH
あらまし ソースコード中に存在する同一，または類似したコード片をコードクローンという．我々は，メトリックス DCH は文献 [2] にて下記のように定義されている．

クラス階層構造を利用したコードクローン集約支援手法を提案してきたが，集約可能と正しく判定できない場合があった．本論文ではこの問題を改善した．
キーワード

コードクローン，集約

1. ま え が き
ソフトウェア保守を困難にしている一つの要因としてコードクローンが指摘されている [1]．コードクローンとはソースコード中に存在する同一，または類似したコード片のことである．例えば，あるコード片にバグが含まれていた場合，そのコード片のコードクローンすべてについて同様の修正の是非を検討しなければならない．
我々はこれまでに，コードクローンを一つのモジュールに集約する支援を行う手法を提案している [2]．その手法の中で，メトリックス DCH を定義している．

DCH は，クラス階層内においてコードクローンがどの程度広く分布しているのかを表現するメトリックスである．一般的に，コードクローンはクラス階層において広く分布しているよりも，近くに存在している方が集約しやすい．しかし，DCH はクローンセット（注 1）

クローンセット S はコード片 f1 , f2 , · · · , fn を含んでいるとする．Ci はコード片 fi を含んでいるクラスとする．もしクラス C1 , C2 , · · · , Cn が共通 の 親 ク ラ ス を も つ 場 合 は ，そ の 共 通 の 親 ク ラス の 中 で ，ク ラ ス 階 層 的 に 最 も 下 に 位 置 す る ク
ラ ス を Cp で 表 す と す る ．ま た D(Ck , Ch ) は ク
ラス Ck と Ch のクラス階層における距離（ノード を ク ラ ス ，エッジ を 継 承 関 係 と し た グ ラ フ 表
現におけるホップ数）を表すとする．このとき，DCH(S) = max{D(C1 , Cp ), · · · , D(Cn , Cp )} と表される．直観的には，メトリックス DCH(S) はクローンセット S に含まれる各コード片間のクラス階層内における最大の距離を示す．例えば，S 中のすべてのコード片が一つのクラス内に存在する場合は DCH(S) の値は 0（図 1 (a)），あるクラスとその直接の子クラス内に存在する場合は DCH(S) の値は 1 となる（図 1 (b)）．例外的に，コードクローンが存在するクラスが共通の親クラスをもたない場
合は DCH(S) の値は ∞ とする（注 2）（図 1 (c)）．

単位で計測されるため，クローンセット内の一部のDCH の値を用いることにより，そのコードクローコードクローンのみが離れて存在する場合と，すべてンがどのクラスに集約可能であるかを判定できる．例のコードクローンがクラス階層の様々な位置に分布している場合の区別がつかない．後者は集約を行うことが難しいが，前者については離れた位置に存在しているコードクローン以外は容易に集約することができる．
そこで本論文では，このメトリックス DCH の計測単位の細分化と，その細分化を実現するツールの試作を行った．以降，細分化の手法，及びそれを評価する
電子情報通信学会論文誌

えば，DCH = 0 ならコードクローンの存在するクラス内に，DCH ≥ 1 なら共通の親クラス内に集約を行うことができる．ただし，DCH = ∞ の場合は，集（注 1）：クローンセットとは，互いにコードクローンとなっているコード片の集合である．
（注 2）：文献 [2] 中ではこの場合の DCH(S) の値は −1 となっているが，距離を示すという概念上，本論文では直観的に分かりやすいであろう ∞ を採用した．

c （社）電子情報通信学会 2010
D Vol. J93–D No. 1 pp. 59–63 59電子情報通信学会論文誌 2010/1 Vol. J93–D No. 1

図 2 クローンセット S の例
Fig. 2 Example of clone set S.

約を行うことが難しい．
また，文献 [2] と同様に，メトリックス DCH は，

Fig. 3図 3 提案手法のアルゴリズム
Algorithm of the proposed technique.

JDK のクラスライブラリ等の修正不可能なクラスは除外して計算される．これにより，実際には修正不可能なクラスに対して集約を行おうとする場合にはDCH = ∞ となり，そのような集約はできないことが分かる．

ト，のように DCH の値ごとに作成する．
このようなサブセットの情報を文献 [2] で得られる各メトリックス値の情報と併用することによって，よ2. 2 問 題 点り多くの集約可能なコードクローンを検出し，より柔従来の DCH はクローンセット単位で計測されてい軟に集約の候補を提示することができる．よって，従た．この方法では，クローンセット内の一部のコード来手法では DCH = ∞ で集約不可能と示されていた片のために DCH の値が大きくなってしまう場合があ

クローンセットに対しても，集約可能なサブセットをる．クローンセット S に含まれているコードクローン提示することができる．

を f1 ，f2 ，· · ·，f7 とし，これらが図 2 のように分布3. 2 アルゴリズムしている場合を考える．この場合，クラス C2 はクラ提案するアルゴリズムの入力はクローンセットであス C4 の親クラス，クラス C1 はクラス C2 とクラスり，出力は DCH の値に基づいて分割されたサブセッ

C3 の親クラスである．f6 と f7 の存在するクラス C5トの集合である．このアルゴリズムは，DCH = 0 のは，他のどのクラスとも共通する親クラスをもっていサブセットを生成する STEP1 と，DCH ≥ 1 のサブない．もしクローンセット S 内に f6 と f7 がなければセットを生成する STEP2 からなる．2〜10 行では，DCH(S) = 2 となるが，f6 と f7 のために値が ∞ にSTEP1 を行っている．まず，入力されたクローンセッなってしまう．

トは，コードクローンを含むクラスごとにサブセット

しかし，それは集約を行う上において好ましくない．

として分割される．そして，二つ以上のコードクロー

同一クラス内に存在するクローンのみを集約したい，ンをもつサブセットは，DCH = 0 のサブセットとしより多くのコード片を集約したい等の，細かな要求にて G に追加される．

こたえにくいためである．

11〜26 行は STEP2 を行っている．STEP2 では，3. 提 案 手 法

STEP1 で生成されたサブセットを一つ指定し，その3. 1 概サブセットのコードクローンを含むクラスを基点にし要

従来手法の問題点を解決するため，本論文では，クて，下記の処理を行いながら親クラスを順にたどる．

ローンセットをサブセットに分割し，そのサブセット（ 1 ） 現在注目しているクラスと，基点となるクラごとに DCH を計測する手法を提案する．サブセット

スとの距離（図 3 のアルゴリズムでは，変数 h であはすべての組合せで作成するのではなく，DCH の値る）を計測する（13 行目，24 行目）．

が 0 となるサブセット，DCH の値が 1 となるサブセッ（ 2 ） 現在注目しているクラスから h 階層内に位置

60

レター
表1 実験結果
Table 1 Experimental result.

ソフトウェア(a)Apache Ant(v1.6.0)(b)Areca backup(v5.5.6)(c)Eclipse Checkstyle Plug-in(v4.4.0)(d)JasperReports-Java Reporting(v2.0.4)(e)jEdit(v4.2)(f)JFreeChart(v1.0.9)(g)Jimm-Mobile Messaging(v0.5.1)(h)Robocode(v1.5.2)(i)XUI RIA Framework(v1.0.4)(j)ZK-Simply Ajax and Mobile(v3.0.2)
合計

ソフトウェアの規模
ファイル数
行数
650
189,915323
55,179206
43,349948
211,619394
140,665538
194,470
56
27,166
209
48,717439
76,770961
132,597
4,724 1,120,447

集約可能と判定されたコードクローンの数
Pull Up Method
Extract Method
従来手法 提案手法 差分 従来手法 提案手法 差分
656836872
437
48
1130
44
14990
20
244292
309
17143
205
62
385
153
155
2262
307
45
176
275
99
00028
280
17
17060
60
034
340
4347
447
47066
72
6766
847
81787
982 195

するクラスに含まれるコードクローンを，指定したサれらに対して，コードクローン集約パターン “Pullブセットに併合する（15〜19 行目）．

Up Method” と “Extract Method” の二つを適用し（ 3 ） 同様のコードクローン集合をもつサブセットた．これらを用いて集約を行うための詳細な条件につが G に登録されていない場合は，生成されたサブセッ

いては，文献 [2] を参照されたい．なお，この実験でトを DCH = h のサブセットとして G に登録するは，30 字句（行数に換算して約 5，6 行）以上のコー（20〜22 行目）．

ドクローンを対象とした．

この処理を STEP1 で生成されたすべてのサブセット

対象ソフトウェアのクローンセット数を l，クラス階層の階層数を m，クローンセット内のコードクローに対して行う．

3. 3 従来手法との比較

ンを含むクラス数を n とすると，アルゴリズムの計算

この提案手法を用いることにより，従来の手法では時間は O(lmn2 ) である．しかし，10 万行規模のソフDCH(S) = ∞ となってしまっていた図 2 のクローン

トウェアでもクローンセット数は数百個程度，階層数セット S の DCH が，以下のように計測される．

は数層程度，クラス数は数個から 10 数個程度である

DCH = 0 のサブセット：{f3 ,f4 },{f6 ,f7 }ため，ツールの実行時間はさほど長くない．コードク

DCH = 1 のサブセット：{f1 ,f2 ,f3 ,f4 }, {f2 ,f5 }ローン検出から DCH の計測まで，数分以内で処理がDCH = 2 のサブセット：{f1 ,f2 ,f3 ,f4 ,f5 }終了した．

この結果を用いることにより，例えば，DCH = 2

4. 1 実 験 結 果のサブセット {f1 ,f2 ,f3 ,f4 ,f5 } をクラス C1 に集約し，従来手法と提案手法を実験対象ソフトウェアに適更に，DCH = 0 のサブセット {f6 ,f7 } をクラス C5用し，“Pull Up Method” と “Extract Method”，のに集約することができる．このように集約を行った場

条件に一致するコードクローン数を計測した結果を，合，七つあったコードクローンを二つに減らすことが

表 1 の「集約可能と判定されたコードクローンの数」できる．に示す．差分には提案手法で計測したコード片数から4. 実験コードクローン集約支援環境 Aries [2] の出力する従来手法で計測したコード片数を引いた値を示している．

コードクローン情報を入力とし，改良手法を用いて計

表 1 より，提案手法を用いた場合，従来手法を用測された DCH を出力とするツールを実装し，提案手いた場合よりも “Pull Up Method” では 81 個，“Ex-法の有効性を調べるための実験を行った（注 3）．

tract Method” では 195 個多くのコード片が検出され実験では，従来手法を用いた場合と提案手法を用ている．

いた場合において，集約可能と判定されるコードクローンの数の差を計測した．表 1 に表しているオー
プンソースソフトウェア 10 種を実験の対象とし，そ（注 3）：実験を行った環境は CPU が Pentium4 2.66 GHz，主記憶容量が2.00 GByte，OS が Windows XP/Professional SP2 である．

61

電子情報通信学会論文誌 2010/1 Vol. J93–D No. 1
表 2 提案手法で集約可能となったコード片数に対応するクローンセット数
Table 2 Number of clone sets corresponding numberof code fragments which can be aggregatedby the proposed technique.
ソフトウェア

集約可能となったコード片数
2 3
4 5 6 7 8 9 10 11

合計

れば，それらを集約することによって，将来的な保守コストを大きく減らすことができる．頻繁に修正される場所を予測するための手法としては，過去の修正履歴を調査するといった方法が考えられる．過去に頻繁に修正が行われている場所については，その後も修正の繰り返される可能性が高いと推測される．本手法は，(a)21000000003(b)21301000007

そのような予測手法とともに使うと効果が高くなるだ(c)20000000002ろう．

(d)613010203016(e)10010000002

本手法を用いて新たに見つかった集約可能なコード(f)14314002201137

クローンを調査した結果，同じディレクトリ内に存在(g)00000000000しているものが多いことが判明した．同じディレクト(h)00000000000

リ内のファイルは似た機能を実装していることが多い(i)

00100000001(j)10100000002ので，これらのコードクローンは意味的に似たもので合計28622122404170ある可能性が高い．例えば，四つのコードクローンがant\taskdefs\optional\ejb\BorlandGenerateClient.java
ant\taskdefs\optional\XMLValidateTask.java

4. 2 考察

多くの場合において (13/20)，提案手法を用いた方

ant\taskdefs\Property.java
ant\util\ClasspathUtils.java

が，多くのコードクローンを集約可能と判定した．ソの四つのファイルに分布するクローンセットは，従フトウェアの規模と差分とを比較すると，行数の多い

来手法では DCH = ∞ となったが，提案手法ではものは差分も多い傾向がある．10 万行以上の規模のソ

taskdefs ディレクトリ内のファイルに分布する三つのフトウェアについては，従来手法と提案手法とでコーコードクローンは，DCH = 1 で集約可能と判定され

ド片 6 個分以上の差が出ている．規模が 10 万行未満

た．四つのファイルのうち，ClasspathUtils.java ファのソフトウェアは，かなりの差が出るものもあれば，イルは ant のクラスパスに関する機能を提供している全く差が出ないものもあった．また，ファイル数と差が，それ以外の taskdefs ディレクトリ内の三つのファ分には関連性は見られなかった．

イルは，どれも ant のタスクの動作を定義している．

表 1 には集約可能なコード片の総数を示している

このようなコードクローンは集約してよいと思われる．

が，各クローンセットについて詳細に調べたところ，対象ソフトウェアによって，その差分の量は大きく

表 2 のようになった．なお，表 2 中のアルファベッ変わるものの，従来手法を用いるよりも提案手法を用トは表 1 のソフトウェアのアルファベットと対応しいた方が多くの集約可能なコード片を検出できた．更ている．つまり，(a) の Apache Ant には二つのコーに，新たに検出された集約可能なコードクローンは，ド片が集約可能となったクローンセットが二つ，三つ集約を行ってよいものであることも分かった．また，のコード片が集約可能となったクローンセットが一つ

対象ソフトウェアの規模が大きいほど，差分が大きくあったというように見る．表 2 より，提案手法を用いなる傾向があるので，規模の大きいソフトウェアに本て多くのコード片が新たに集約可能となったクローン手法を用いれば，集約可能なコード片を多く検出するセットはあまりなかった．新たに 5 個以上のコード片のに役立つと考えられる．ただし，本手法は集約可能が集約可能となったクローンセットが 14 個だったのなコード片を検出することを目的としており，実際にに対し，新たに 2 個しか集約可能にならなかったもの

集約すべきかどうかは開発者や保守管理者が見て判断が 28 個であった．

する必要がある．

集約できるコード片の数が少ない場合，一つひとつ5. む す び

コード片の内容を見て集約すべきか判断するのでは，

本論文では，メトリックス DCH の計測単位の細分集約により減らせる保守コストよりも集約に必要とな化を行った．また，従来の計測方法に比べ，提案したるコストの方が高いかもしれない．しかし，その後も計測方法が集約可能なコードクローンを多く検出でき頻繁に修正の繰り返される可能性が高いコード片であることを実験で確認した．

62

レタ

謝辞

ー

本研究は，文部科学省科学研究費補助金基盤（課題番号：17200001），基盤研究（C）（課研究（A）
題番号：20500033）及び若手研究（スタートアップ）（課題番号：19800022）の助成を得た．
文[1]献M. Fowler, Refactoring: Improving the design of ex-[2]

晶夫，平澤 章，梅澤真史（訳），リファクタリング プロ
グラミングの体質改善テクニック，ピアソン・エデュケーション，2000.）．
肥後芳樹，神谷年洋，楠本真二，井上克郎，“コードクローンを対象としたリファクタリング支援環境，” 信学論（D-I），vol.J88-D-I, no.2, pp.186–195, Feb. 2005.
（平成 21 年 3 月 5 日受付，7 月 27 日再受付）

isting code, Addison Wesley, 1999 （児玉公信，友野63