Vol. 0

No. 0

1959

情報処理学会論文誌

コードクローン解析に基づくリファクタリングの試み
肥 後 芳 樹†楠 本

植 田 泰 士†
真 二†
井 上

神 谷
克 郎†

年

洋††

近年，ソフトウェアの大規模化・複雑化に伴い，保守作業に要するコストは増大している．ソフト
ウェアの保守を困難にしている要因の 1 つとしてコードクローンがあげられる．コードクローンとはソースコード中に存在する同一，または類似したコード片のことである．例えば，あるコード片にバグが含まれていた場合，そのコード片のコードクローン全てについて修正の是非を考慮する必要がある．コードクローンに関する処理を支援するために，我々はコードクローン分析環境 Gemini を開発してきた．Gemini をさまざまなプロジェクトに適用する中で，いくつかの問題点に直面した．ク
ローン検出の目的の 1 つとしてリファクタリングがあげられるが，Gemini によってユーザに示されるクローンはリファクタリングを適用できる単位となっていなかった．本論文ではこの問題を解決し，
Gemini を機能拡張した．また，オープンソースのソフトウェアに対して適用実験を行ない，本手法の有用性を確認する．

On software maintenance process improvement based on code clone analysis
Yoshiki Higo,† Yasushi Ueda,† Toshihiro Kamiya,††
Shinji Kusumoto† and Katsuro Inoue†
Maintaining software systems is getting more complex and difficult task. Code clone is oneof the factors that make software maintenance more difficult. A code clone is a code portionin source files that is identical or similar to another. If some faults are found in a code clone,
it is necessary to correct the faults in its all code clones. We have developed a maintenancesupport environment, Gemini, which provides the user with the useful functions to analyze
the code clones and modify them. However, through case studies, several problems were reported. That is, the clones extracted by Gemini were not necessarily appropriate to merge
into one module. In this paper, we intend to extend the functionality of Gemini to cope withthe problems. Finally, we apply the extended Gemini to several software and evaluate theapplicability of the new functions.

増大してきている．実際に，多くのソフトウェア会社

1. は じ め にが既存システムの保守に非常に多くの人的，時間的コ
ストをかけていると報告されている24) ．

近年，ソフトウェアの大規模化・複雑化に伴い，ソフトウェアの保守作業がますます困難なものになって

コードクローンはソフトウェア保守を困難にしている

きている．ソフトウェア保守では，フィールドバグの1 つの要因といわれている8) ．コードクローンとはソー

修正，環境変化に対する機能追加・変更， 将来トラブ

スコード中に存在する同一，または類似したコード片

ルにつながりそうな箇所に対する対応等の作業が実施のことである．コードクローンが生成される原因はさされる20) ．しかし，保守対象のソフトウェアがうまく

まざまな理由が考えられるが，その最も大きな原因の設計されていない，度重なる変更により構造がわかり

1 つとしてコピーアンドペーストによる修正，拡張作

にくくなってしまう，変更履歴のドキュメントが存在

業があげられる．コード片にバグが含まれていた場合，しない，等の問題により，ソフトウェア保守コストは

そのコード片のコードクローンとなっている部分全てに対して修正の是非を考慮する必要がある．このような作業は，特に大規模ソフトウェアでは非常に手間が† 大阪大学大学院情報科学研究科
Graduate School of Information and Science Technology, Osaka University†† 科学技術振興機構 さきがけ
PRESTO, Japan Science and Technology Agency

かかる．従ってコードクローン検出の効率化はソフト
ウェア保守工程の改善において有効である．これまでにコードクローンを自動的に発見するためのさまざま
1

2

1959

情報処理学会論文誌

な手法が提案されている3)4)5)6)7)12)13)14)15)16)18)19)

Interfaces

Code clone analysis environment, Gemini．

Clone pair manager

その手法の 1 つとして，我々はコードクローン検

Clone selection
information

出ツール CCFinder13) と分析環境 Gemini21) を開発
してきている．ユーザは Gemini を用いることによりCode clone detector
Source files

Clone scatter plot view

User

Source code manager
Code clone database

コードクローンの解析，ソースコードの修正を容易

Source code view
Clone selection
information

Metrics managerに行なうことができる23) ．Gemini は主に，クローン

Metric graph views

散布図とメトリクスグラフをユーザインターフェース

図 1 Gemini 全体図
Fig. 1 Overview of Gemini

として提供する．クローン散布図はソースコード中のコードクローンの分布状態を俯瞰的に表示する．またメトリクスグラフは各々のコードクローンについての
定量的な情報を提供し，その値を用いることによって保守を阻害するコードクローンの選択をすることが可能である．選択されたコードクローンのソースコード
は容易に閲覧できる．ユーザはこれらの機能を用いることによってソフトウェアの保守作業を改善することができると期待できる．
我々は Gemini を数十のソフトウェア会社に配布し，さまざまなプロジェクトに用いることによって評価した．その結果，ソフトウェア会社からのフィードバッ

図 2 クローン散布図表示例
Fig. 2 Scatter plot

クよりいくつかの問題点が発見された．最も多く指摘された問題は，Gemini をリファクタリング8) に利用する際に発生する問題であった．一般的に，コードク
ローンを除去することを目的として，コードクローンになっている部分を 1 つのメソッドやクラスにまとめるリファクタリングが適用される．しかし Gemini によって検出されたコードクローンは，必ずしも 1 つのモジュールとしてまとめるのに適していない．
本論文では，この問題を解決するために Gemini の
コードクローン検出部に対して行なった拡張について論ずる．そして最後に，提案した機能の有用性を確認するために行なった適用実験の結果について述べる．

図 3 ソースコードビュー表示例
Fig. 3 Source code view

2. コードクローン解析
2.1 コードクローンの定義9)

コードを渡し，CCFinder の解析結果をさまざまなユーあるトークン列中に存在する 2 つの部分トークン列

ザインターフェースを通してユーザに提供する機能をα，β が等価であるとき，α と β は互いにクローンであるという．またペア（α，β ）をクローンペアと呼ぶ．α，β それぞれを真に包含する如何なるトークン有する．
本章では，簡単に Gemini と CCFinder の特徴を説明する．

列も等価でないとき，α，β を極大クローンと呼ぶ．ま2.2.1 CCFinder

た，クローンの同値類をクローンクラスと呼ぶ．ソー

CCFinder はプログラムのソースコード中に存在す

スコード中でのクローンを特にコードクローンという．

るコードクローンを検出し，その位置をクローンペア

2.2 コードクローン分析環境 Gemini
文献21)において我々はコードクローン分析環境

Gemini を開発した．図 1 はシステムのアーキテクチャを示している．Gemini は内部の CCFinder にソースのリストとして出力する．検出されるコードクローンの最小トークン数はユーザが前もって設定することができる．

CCFinder のコードクローン検出手順（ソースコー

Vol. 0No. 03

コードクローン解析に基づくリファクタリングの試み

ドを読み込んで，クローンペア情報を出力する）は以
下の 4 つの STEP からなる．

STEP1（字句解析）: ソースファイルを字句解析することによりトークン列に変換する．入力ファイ
ルが複数の場合には，個々のファイルから得られたトークン列を連結し，単一のトークン列を生成
する．

STEP2（変換処理）: 実用上意味を持たないコード
クローンを取り除くこと，及び，些細な表現上の違いを吸収することを目的とした変換ルールによりトークン列を変換する．例えば，この変換により変数名は同一のトークンに置換されるので，変数名が付け替えられたコード片もコードクローンであると判定することができる．

STEP3（検出処理）: トークン列の中から指定された長さ以上一致している部分をクローンペアとして全て検出する．

STEP4（出力整形処理）: 検出されたクローンペアについて，元のソースコード上での位置情報を出力する．

CCFinder の詳細については文献13) で述べられている．

2.2.2 Gemini

図 4 クローン散布図モデル
Fig. 4 Scatter plot of code clones   J6K: A . #%$ & . 'L$& . ))4*+, -4. / 0 124354, #% 7 , 98 ( ,;<. 7 ,= * > -/ /  ( 7 . ?:3  ;<. 7 , * * &, -4. / #6 ;<. 7 ,= * , -. / 0 1424354, &, -4. / 0 1. # . &, -4. / 0 124354, #6BED ;<; &FM6 Gemini は GUI ベースのコードクローン分析環境であり，内部的にコードクローン検出部として CCFinderを用いている．Gemini は以下のユーザインターフェースを提供し，対話的な解析を可能としている．

• クローン散布図，• メトリクスグラフ，• ソースコードビュー．
クローン散布図はソースコードのどの部分にクローンペアが存在するのかを示す図である．一目でソース
コード中のコードクローンの分布状況がわかるので，
コードクローン解析の初期段階では非常に有効な解析手段となりうる．図上でユーザはマウスを用いて任意のクローンペアを選択することが可能である．例を図2 に示す．クローン散布図の詳細については後ほど論ずる．
またメトリクスグラフを用いることにより，ユーザ
はコードクローンを定量的な特性に基づいて選択でき
る．それぞれのクローンクラスについて複数のメトリクス値が示されていて，ユーザは長いコードクローン
や，出現数の多いコードクローンを選択できる．

_ ` a b cEd@eKfchgicfcKjjklm n o pmm myKo mJz nKp po|
yKo mm n o p q rsyKtu o md@z b m v nKo a p wKx mv k { `:xb v t `K_ b v k k f
m n o p d@b v k q rstu f
m n o p q r chdhcm fyyq rstu d~}< f

NPORQ@SUTVO<WXY OEZ\[             
 ! "#%$&"'%( &" ) ) *+, -. / 0 12435 , #6 7 , 98:( ,<;<. 7 , = * > -/ /  ( 7 . ?:3  ;<. 7 , * * &, -. / #6 ;<. 7 , = * , -. / 0 124354, &, -. / 0 1 "#@"A&, -. / 0 12435 , #CBED ;<; &F  CG@HEII <6!9E

NPORQ@SUTVO<WXY OEZ^]

図 5 コードクローンのリファクタリング例
Fig. 5 Example of merging two code fragments

ソースコードビューはクローン散布図やメトリクス
グラフと組み合わせて用いられる．ユーザはクローン
散布図やメトリクスグラフで選択されたクローンのソースコードをソースコードビューを用いることにより閲覧できる．図 3 では，図 2 において選択された
コードクローンのソースコードを表示している．

2.2.3 クローン散布図
図 4 はクローン散布図の例を示している．クローン
散布図の縦軸と横軸にはソースコード中のトークンが出現順に配置される．ここではクローン散布図を説明するために以下の文字列を用いる．
コード片 X: “ABCDCDEFBCDG”,

4

1959

情報処理学会論文誌

コード片 Y: “ABCEFBCDEBCD”
ここでは，“A” や “B” などは文字や，トークン，行，文などのある一定の単位を表すとする．図 4 の格子内の黒色の矩形はその縦軸の要素と横軸の要素が等しいことを意味している．このことからクローンペアはク
ローン散布図においてある一定以上の長さを持った線分として出現することになる．もし縦軸と横軸に配置
される要素が同じソースファイルである場合は，主対角線上に黒色の矩形がプロットされる．またこの時はこの対角線に対してクローン散布図は線対称となる．

3. 提 案 手 法
図 6 Code Clone Shaper 概要
Fig. 6 System of Code Clone Shaper

3.1 これまでの手法の問題点
我々は，Gemini（含む CCFinder）をさまざまな商用，及び非商用ソフトウェアに適用してきた．そしてフィードバックとしていくつかの問題点が指摘された．
検出したコードクローンをリファクタリング8) に用いる場合の問題点として，単に最大長のクローンを検出してもその部分を 1 つの関数，メソッドなどにまとめることは困難であることがあげられる．我々はこれまでに多くの実験を行なってきたが，その実験で検出された大部分のコードクローンは，プログラミング言語の意味にてらして構造的なまとまりを持たないものであった．図 5 に例を示す．図 5 では，A と B の 2 つのコード片が示されている．A と B それぞれの灰色の部分は，その部分が A と B の間の最大長のコードク
ローンであることを示している．コード片 A ではいく
つかのデータがリスト構造の先頭から順に連続して格納されている．一方コード片 B では，リスト構造の後方から順に連続してデータが格納されている．これら

2 つのコード片間には共にリスト構造を扱っているという点において論理的に共通している．しかしながらこれらのコード片の for 文の前後には偶然クローンとして含まれてしまった部分が存在している．リファク

検出処理は非常に高速である．しかし，CCFinder によって検出されるコードクローンは単に最大一致トークン数によるものであり，コードクローンの凝集度は考慮されていない．つまり CCFinder を用いたコード
クローン検出をリファクタリングに適用しようとした
場合，ユーザは自ら CCFinder の検出結果から構造的なまとまりのある部分を抽出する必要がある．
この問題を解決するため，我々はまず最大長のコー
ドクローンを検出し，次に，そのコードクローンに含まれる構造的なまとまりのある部分のみを抽出し，最後にユーザに指定された最小トークン以上のクローンを取り出すという三段階のアプローチを提案する．

3.2 アプローチ
CCFinder によって検出されたコードクローンから
1 つの関数やメソッドとしてまとめるのに適した部分のみを取り出したコードクローンをシェイプドクロー
ンと呼ぶ．ソフトウェアからシェイプドクローンを取り出す過程は以下の 3 つからなる．

(1)

タリングの視点からは，灰色の部分全体よりも for 文
のみをコードクローンとして抽出する方が望ましい．

対象のソフトウェアに対し CCFinder を実行し，コードクローンを検出する．

(2)

次に，対象のソフトウェアを解析し，構造的なコードクローンをリファクタリングするための研究

まとまりをもったブロックの位置情報を抽出すはいくつか行なわれている．文献14) と文献15) では，る．例えば，Java プログラムを対象とした場

プログラム依存グラフを用いてコードクローンの凝集

合は，構造的なまとまりをもったブロックとは度を測定し，関数やメソッドの抽出に用いる方法が述

具体的には以下で示すものである．

べられている．しかしそれらの方法では，プログラム依宣言: class { }，interface { }存グラフの構築に非常にコストがかかることから大規

メソッド: メソッド，コンストラクタ

模なソフトウェアへの適用が難しく，スケーラビリティ

文: if 文，for 文，while 文，do 文，switchの面から見て問題がある．一方 CCFinder では，検出過程において字句解析のみにとどめているため，その文，try 文，synchronized 文，static 文
ブロック: ‘{’ と ‘}’ で囲まれた範囲

Vol. 0

(3)

No. 0

コードクローン解析に基づくリファクタリングの試み

5

最後に，コードクローンの情報と，ブロックの位を解析し，プログラム解析部や，抽出部，管理部を呼置情報を突き合わせ，ユーザに指定された最小び出す役割を担っている．

トークン数以上のクローンをシェイプドクロー
ンとして取り出す．

CCFinder のコードクローン検出過程では，ソースコードに含まれるトークン数を n，検出された最も長いクローンのトークン数を t とした場合，O(nt) 時間で解析結果を得ることが可能である，詳しくは文献13)を参照していただきたい．CCFinder の検出したコー
ドクローンからシェイプドクローンを抽出する解析では，O(n) の処理時間で対象ソースコードを構文解析
しソースコード中の構造的なまとまりのある部分を抽出できる．また O(cs log c)（c は 1 つのファイル当たりに含まれるコードクローンの数，s は対象ソース
コードの数，c，s いずれも n に対して非常に小さい
値となる）の処理時間で CCFinder の検出したコード
クローン情報と，ソースコード中の構造的なまとまりのある部分から，シェイプドクローンを抽出できる．
他のアプローチ，例えばプログラム依存グラフを用いる手法と比較した場合，プログラム依存グラフ構築の時間コストが O(m2 )（m はソースコード中の文や式の数，m は n と比例関係にある）である11) ことを考慮すると，この提案手法では，対象が大規模なソフトウェアであっても実用的な時間でリファクタリングの容易なコードクローンを検出できると期待できる．

3.3 実

装

ソースコードからシェイプドクローンを取り出す機
能を Gemini に実装した（図 6 参照）．ユーザは Gem-ini の GUI の一部であるオプション設定ウィンドウからシェイプドクローン抽出の有無を設定し，抽出するプログラム解析部
プログラム解析部では対象のソースコードを字句解
析，構文解析して，プログラム中の構造的なまとまりをもつブロックの位置情報を取得する．本手法におけるブロックの位置情報はソースコードのファイルパス，
ファイル内でのブロックの開始行，開始列，終了行，終了列の 5 つの情報から成る．ソースコードのファイルパスは，ユーザから指定されたファイルに対して解析を行なっているので既に取得済みである．残りの 4つの値はソースコードを構文解析する過程で取得される．なお，このモジュールは JavaCC10) を用いて構築されている．
抽出部

プログラム解析部で抽出したブロックの位置情報と，

CCFinder の出力結果であるコードクローン情報を突
き合わせ，コードクローンである部分からプログラミ
ング言語の意味にてらして構造的にまとまりのある部分のみを抽出する．ブロックの位置情報と同様にコー
ドクローン情報もソースコードのファイルパス，開始
行，開始列，終了行，終了列の 5 つの情報から成る．
つまり，CCFinder の検出したコードクローン内に含まれる一番外側の構造的なまとまりをもったブロック
がシェイプドクローンとして抽出される．
出

力部

抽出部で取り出したシェイプドクローンを適切な順番で並び変え，Gemini に与えるデータとして一貫性のあるものに変換する．

3.4 リファクタリング方法
本節では，提案機能を使用したリファクタリング方法

シェイプドクローンの最小トークン数も指定することを説明する．リファクタリングの手順は以下の STEP1が可能である．このオプション機能を設定することで〜STEP3 から成る．

ユーザは構造的なまとまりをもつコードクローンをGemini を用いて分析できる．Gemini の詳しい使用
方法は，文献21) を参照していただきたい．
この機能は約 1 万 2 千行の Java プログラムで実装されている．現在のところ，対象言語は Java のみである．ここでは，実装したシェイプドクローン検出プ
ログラム（Code Clone Shaper 以後 CCShaper と略す）について説明する．実装したプログラムは図 6 に示されるように大きく分けて 4 つのモジュール，制御部，プログラム解析部，抽出部，出力部から構成され
ている．
制 御

部

制御部は CCFinder の出力したコードクローン情報

STEP1（クローン検出）: Gemini を用いて対象ソー
スコードからシェイプドクローンを検出する．

STEP2（クローン選択）: Gemini のクローン散布
図，メトリクスグラフを用いてリファクタリング
対象コードクローンを特定する．

STEP3（クローン除去）: STEP2 で選択したコー
ドクローンを除去する．

STEP1 については， Gemini の GUI の一部であるオプション設定ウィンドウからシェイプドクローン抽出機能の設定ができることは 3.3 節で述べた．

STEP2 では，検出したシェイプドクローンをクロー
ン散布図とメトリクスグラフを用いて分析し，リファ
クタリング対象となるコードクローンを決定する．

6

1959

情報処理学会論文誌
表 1 ソースコードサイズ
Table 1 Source code size

クローン散布図を用いた場合には，クローンが密集しているファイルのコードクローンを取り除くことが有効である．これまでに行なわれたケーススタディ17)
では，各ファイルにおいてそのファイルのクローンと

ファイル数

ANTLR
Ant

行数

239
508

トークン数

43548
141254140802221203

なっている行の割合，ファイル中の最大長クローンとそのファイルの改版数を定量的に比較し，一定以上し，各コード片をそのメソッドの呼出文に置き換えるの割合でクローンが含まれている場合や，非常に長ことが有効である．また，Fowler が提唱しているリ

いコードクローンが含まれていた場合，そのファイル

ファクタリングパターン8) の中にもクローンの除去にの改版数が多くなることが示されている．つまり，ク適用可能なパターンが存在する．例えば，複数のクラローン散布図を用いてクローンが密集しているファイスにメソッド単位のコードクローンが存在した場合をルのコードクローンをリファクタリング対象として選考える．もしそれらのクラスが共通の親クラスを継承

択し除去した場合，長期的なそのファイルの改版数はしているならば，クローンとなっている各メソッドにリファクタリングしない場合に比べ少なくなることが対して “Pull Up Method” パターンを適用すること予測され，保守コストの削減が期待できる．

で，クローンを除去できる．除去方法を決定した後は，一方，メトリクスグラフを用いた場合には各クロー

ユーザはテキストエディタなどを用いて，実際にソーンクラスの特性に基づいてリファクタリング対象コー

スコードに変更を加え，コードクローンを除去する．

ドクローンを選択することが可能である．メトリクス
グラフではクローンクラスを以下の 4 つのメトリクス
を用いて特徴づけている．

4. 適 用 実 験
4.1 実 験 概 要

RAD(C): クローンクラス C のディレクトリ階層に前章で提案したシェイプドクローンの検出方法の有おける分散度を示すメトリクスである．クローン

用性を確認するためにオープンソースの Java で記述

クラス C 中の全てのコード片がある 1 つのファされたソフトウェアである ANTLR2) と Ant1) に対

イル内に存在する場合は 0，1 つのディレクトリ

して適用実験を行なった．

内に存在する場合は 1 と，広い範囲で分散しているほどこのメトリクス値は大きくなる．

LEN(C): クローンクラス C に含まれるコード片の最大長を表す．

POP(C): クローンクラス C に含まれるコード片の数を表す．

ANTLR（ANother Tool for Language Recognition）は構文解析器を生成するためのツールである．
生成された構文解析器は Java もしくは C++で出力される．Ant は Java 用のビルドツールであり，ビルド手順は XML で記述される．
提案手法の評価をするために，CCShaper を用いた

DFL(C): クローンクラス C に含まれるコード片にGemini と用いていない Gemini を用いてそれぞれ対共通するロジックを実装するサブルーチンを作り，象のソースファイルを解析し，その結果を比較した．こ

各コード片をそのサブルーチンの呼び出しに置きの適用実験では，CCFinder が検出するコードクロー

換えた場合の減少が予測されるトークン数である．

ンの最小一致トークン数は 50，CCShaper が抽出す

例えば，将来的にバグが見つかった場合の修正コスト

るコードクローンの最小トークン数は 30 に設定した．

をなるべく押えたい場合は，POP 値の大きいクローン

またこの適用実験では，クローン散布図を用いてリクラスを除去することが有効である．また DFL 値のファクタリングを行なうコードクローンを決定した．

大きいクローンクラスを除去することは，ソースコー

文献17) では，コードクローンを一定以上含むファイドの行数を多く減少させることを意味するので，ソフ

ルが他のファイルに比べ改版数が多くなることを示し

トウェアの規模を小さくするという意味で有効である．

ている．クローン散布図でクローンが密集している部

STEP3 では，ユーザはまず STEP2 で選択したコー分はコードクローンを多く含むファイルであるため，

ドクローンのソースコードを Gemini のソースコード

このようなファイル中に存在するコードクローンをリ

ビューを用いて閲覧し，どのように除去するのかを決

ファクタリングすることにより，そのファイルの保守定しなければならない． 例えば，選択したクローン性を高めることができる．

クラスのコード片の全てもしくは大半が 1 つのクラス内に存在する場合は，そのクローンクラスのコード片に共通するロジックを新しいメソッドとして実装

4.2 ANTLRANTLR は 239 個のソースファイルから構成されており，総行数は 4 万 4 千行である．

Vol. 0No. 0

コードクローン解析に基づくリファクタリングの試み

7

除くべきか，取り除くことができるかを判断するのに，非常に手間がかかってしまうと考えられる. 一方で，

CCShaper を用いた場合には，リファクタリングが難しいコードクローンを取り除くことにより，クローン
ペアの 99 ％以上（33 万個以上），クローンクラスの約 85 ％（830 個）を省くことができている.
また，どのようなコードクローンが検出されているのかを調べるために，図 8 において最もクローンペア
が密集しているラベル A で示されている部分のソース
コードを調べ，図 9 に示す特徴的なクローンを発見した．このクローンクラスは 28 個のコード片から成り立っており，それぞれのコード片の長さは 82 トークンであった．またこのクローンクラスのコードクロー
ンは全てメソッド単位のクローンであり，コード片の差異は図 9 の灰色で示されている部分 2 箇所の定数
図 7 ANTLR のクローン散布図（CCShaper 無）Fig. 7 Result without Code Clone Shaper in ANTLR

名の違いのみであった．このクローンクラスの全てのコード片は全て同一のクラス内に存在しているメソッドであり，引数を 2 つ追加することによって容易に 1
つのメソッドにまとめることができる．

4.3 Ant
次に Ant に対しての実験結果を示す．Ant は 508個のファイルから成り立っており，総行数は 14 万 1千行であった．

CCShaper を適用する前，適用後のクローン散布図をそれぞれ図 10，図 11 に示す. また，適用前後のコー
ドクローン数の比較を表 3 に示す. CCShaper を用いない場合には，Ant 内には一様にコードクローンが散布しており，どのコードクローンを取り除くべきか，取り除くことができるかを判断するのに，非常に手間がかかってしまうと考えられる. 一方で，CCShaperを用いた場合には，リファクタリングが難しいコード
クローンを取り除くことにより，クローンペアの 99％以上（1 万個以上），クローンクラスの約 94 ％（803
図 8 ANTLR のクローン散布図（CCShaper 有）
Fig. 8 Result with Code Clone Shaper in ANTLR個）を省くことができている.
実際に検出されたコードクローンのソースコードを調べるために，最もクローンペアが密集しているラベ

表2

ANTLR から検出されたコードクローン数の比較
Table 2 Numbers of clones in ANTLR

クローンペア数
クローンクラス数

CCShaper 無し

CCShaper 有り

338574
1072

972
142

ル B で示す部分をソースコードビューで閲覧する．図12 はこの部分のコードクローンのソースコードを示している．このメソッド単位のコードクローンは 7 つのクラスに，各々1 つずつ存在した．またこれら 7 つのクラスは全て同一のクラスを親クラスとして定義して

CCShaper の適用前，適用後のクローン散布図をそいた．これらのことからこのコードクローンは親クラ

れぞれ図 7，図 8 に示す. また，適用前後のコードク

スに引き上げることによって取り除くことができる．

ローン数の比較を表 2 に示す. CCShaper を用いない
場合には，ANTLR 内に発見されるコードクローンは非常に多くなってしまい，どのコードクローンを取り

5. ま と め
本論文では，既存のコードクローン分析環境 Gemini

8

情報処理学会論文誌
        , 1   ! " % ( $ )*+,#  -  %  .  # %  / ( $  % $ # 0.  # % 
 % % % 3 # 4
 & #  % & # 5    4
 %  # -  5 % # . % 6  # - % ( " ' 4% % 3 #51, 1  , ! 4
 % * # ! # . 4

1959

 #   $ # % #  & # '/  & #  % $ # 1.  # %  02A

1 %  ( " 7 K 7 ' 4
 "   $ # % #  & # 919: % & # 55   919I % % 3 # ; 5  & # 6  <! J'2
 % & # 15 & #  & # "  % % 3 # ' 4
 % & # 6 * # % # . % " # )= % $  - " % # . % 6 - # % >   # $ " ' /   # -  / % # . % 6  # - % ( " ' @   # -  ' ' 4
A $ # %  $  & # 5 % & # 4

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

A1 %  ( " 7 87 ' 4
 "   $ # % #  & # 919: % & # 55   919 % % 3 # ; 5  & # 6  <! 0'2
 % & # 15 & #  & # "  % % 3 # ' 4
 % & # 6 * # % # . % " # )= % $  - " % # . % 6 - # % >   # $ " ' /   # -  /?# . % 6  # - % ( " ' @   # -  ' ' 4
A $ # %  $  & # 5 % & # 4

        +,B C,  DC1"   # ,  $ # % #  & # /  % /  ( $ '% ( $ )*+#  -  %  .  # %  / ( $  % $ # .  # %  /  & #  % $ # 1.  # %  02
 %  % % 3 # 4
 & # , % & # 5    4
 %   # -  5 % # . % 6  # - % ( " ' 4 % % 3 #5 4
 %  * #! #. 4

F
F

F
A

 %  ( "  ' 4
 "   $ # % #  & # 919: % & # 55   9 9E % % 3 # ; 5  & # 6  <! 0'2
 % & # 51 & #  & # "  % % 3 # ' 4
 % & # 6 * # % # . % " # )= % $  - " % # . % 6 - # % >   # $ " ' /   # -  / % # . % 6  # - % ( " ' @   # -  ' ' 4
A $ # %  $  & # 51 % & # 4

F
F
F
F
F
F
F
F
F
        1+G1+H,"   #  $ # % #  & # '% ( $ )*+,#  -  %  .  # %  / ( $  % $ # 0.  # %  /  & #  % $ # 1.  # %  02
 % % % 3 # 4
 & #  % & # 5    4  %   # -  5 % # . % 6  # - % ( " ' 4 % % 3 #5+ G1+H 4
 % * # ! # . 4

A1 %  ( " 7 A 7 ' 4
 "   $ # % #  & # 919: % & # 55   919I % % 3 # ; 5  & # 6  <! J'2
 % & # 15 & #  & # "  % % 3 # ' 4
 % & # 6 * # % # . % " # )= % $  - " % # . % 6 - # % >   # $ " ' /   # -  / % # . % 6  # - % ( " ' @   # -  ' ' 4
A $ # %  $  & # 5 % & # 4

図9

表3

ラベル A のコードクローンのソースコードとリファクタリング例
Fig. 9 Merged clone sample in ANTLR

Ant から検出されたコードクローン数の比較
Table 3 Numbers of clones in Ant

クローンペア数
クローンクラス数

えることができる．しかし，この提案手法ではコードCCShaper 有り

CCShaper 無し

12033
856

103
53

クローンをリファクタリングしやすい単位として抽出したものであり，抽出した各クローンがどのようにリファクタリングできるのかまでは考慮していない．今後は抽出したクローンをどのようにリファクタリング

を拡張してリファクタリングの候補となりうるコード

できるのかによって分類する手法の研究を行なうと共クローンのみを抽出する機能（Code Clone Shaper）に，このツールを実際のソフトウェア保守の場面で利を提案した．提案手法をツールとして実装し，オープ

用し，そのプロセス改善に役立てたいと考えている．

ンソースのソフトウェアである ANTLR，Ant に適謝辞 CCFinder，Gemini の評価について多くの用した．Code Clone Shaper を適用することでコー

フィードバックを頂いた．CCFinder メーリングリス

ドクローンをフィルタリングすることに成功し，抽出トの参加者に感謝します．

されたコードクローンはいずれもリファクタリングの容易なものであった．これらのことから本論文で提案したコードクローン抽出手法は非常に有用であると考Vol. 0No. 0

コードクローン解析に基づくリファクタリングの試み

9          "!! #$  %!&'( ) *!,+- $.,$0//1  '(
!&2  # -3 ! 45 3'62  74# 598": ;<+"=$>$? .A@B<C,?EDB<@+4F@48 '6GH   I )"*!,+ .,J"2 K J# L "  -# M N-MO'9'(!&2  # -3 ! 45 3'62  74# 598": ;<+"=$>$? .A@B<C,?EDB<@+NP@,B,'6G
H   I )"*!,+ .,J"2 K J# L "  -# MQD<M9'3'(!&2  # -3 ! 45 3'62  74# 598": ;<+"=$>$? .A@B<C,?EDB<@+-D,?&'6GH   E(
!&2  # -3 ! 45 3'62  74# 598": ;<+"=$>$? .A@B<C,?EDB<@+4F@48 '6G
HR R  S)  H

図 12 ラベル B のコードクローンのソースコード
Fig. 12 Entirely same clone in Ant

図 10 Ant のクローン散布図（CCShaper 無）Fig. 10 Result without Code Clone Shaper in Ant

図 11 Ant のクローン散布図（CCShaper 有）
Fig. 11 Result with Code Clone Shaper in Ant

参 考 文 献1) Ant,http://jakarta.apache.org/ant/,
2002.
2) ANTLR, http://www.antlr.org/, 2000.
3) B. S. Baker, A Program for Identifying Duplicated Code, Computing Science and Statistics,
24:49-57, 1992.
4) B. S. Baker, On Finding Duplication and
Near-Duplication in Large Software Systems,
IN Proc. IEEE Working Conf. on Reverse En-

gineering, pages 86-95, July 1995.
5) B. S. Baker, Parameterized Duplication in
Strings: Algorithms and an Application to Software Maintenance, SIAM Journal on Computing, 26(5):1343-1362, 1997.
6) I. D. Baxter, A. Yahin, L. Moura, M.
Sant’Anna, and L. Bier, Clone Detection Using
Abstract Syntax Trees, Proc. IEEE Int’l Conf.
on Software Maintenance (ICSM) ’98, pages
368-377, Bethesda, Maryland, Nov. 1998.
7) S. Ducasse, M. Rieger, and S. Demeyer, A
Language Independent Approach for Detecting
Duplicated Code, Proc. of IEEE Int’l Conf. on
Software Maintenance(ICSM) ’99, pages 109118, Oxford, England, Aug. 1999.
8) M. Fowler, Refactoring: improving the designof existing code, Addison Wesley, 1999.
9) 井上克郎, 神谷年洋, 楠本真二, “コードクロー
ン検出法”, コンピュータソフトウェア, vol.18,
no.5, pp.47-54, 2001.
10) JavaCC,
http://javacc.dev.java.net,
2003.
11) J. Ferrante, K.J. Ottenstein, J.D. Warren,
The Program Dependence Graph and Its Use in
Optimization ACM Transactions on Programming Languages and Systems, vol. 9, Issue. 3,
pp. 319-349, (1987-7).
12) J. H. Johnson, Identifying Redundancy inSource Code using Fingerprints, Proc. of CASCON ’93, pages 171-183, Toronto, Ontario,
1993.
13) T. Kamiya, S. Kusumoto, and K. Inoue,
CCFinder: A multi-linguistic token-based code
clone detection system for large scale sourcecode IEEE Transactions on Software Engineering, vol. 28, no. 7, pp. 654-670, (2002-7).
14) R. Komondoor and S. Horwitz, Using slicing
to identify duplication in source code, In Proc.
of the 8th International Symposium on Static
Analysis, Paris, France, July 16-18, 2001.
15) Jens Krinke, Identifying Similar Code with
Program Dependence Graphs , In Proc. of the

10

1959

情報処理学会論文誌

8th Working Conference on Reverse Engineering, 2001.
16) J. Mayland, C. Leblanc, and E. M. Merlo Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics, Proc. of IEEE Int’l Conf. on Software
Maintenance (ICSM) ’96, pages 244-253, Monterey, California, Nov. 1996.
17) 門田暁人, 佐藤慎一, 神谷年洋, 松本健一, “コー
ドクローンに基づくレガシーソフトウェアの品質の分析”, 情報処理学会論文誌, Vol.44, No.8,
pp.2178-2187, Aug. 2003.
18) L. Prechelt, G. Malpohl, M. Philippsen, Finding plagiarisms among a set of programs with
JPlag, submitted to Journal of Universal
Computer Science, Nov. 2001, taken fromhttp://wwwipd.ira.uka.de/~prechelt/Biblio/19) M. Rieger, S. Ducasse, Visual Detection of
Duplicated Code, 1998.
20) Pigoski T. M, Maintenance, Encyclopedia ofSoftware Engineering, 1, John Wiley & Sons,
1994.
21) Y. Ueda, T. Kamiya, S. Kusumoto, K. Inoue, Gemini: Maintenance Support Environment Based on Code Clone Analysis, 8th International Symposium on Software Metrics, June
4-7, 2002.
22) 植田泰士, 神谷年洋, 楠本真二, 井上克郎 “開発保守支援を目指したコードクローン分析環境”, 電
子情報通信学会論文誌 D-I, Vol.86-D-I, No.12,
pp.863-871, June. 2003.
23) Y. Ueda, T. Kamiya, S. Kusumoto, K. Inoue, On Detection of Gapped Code Clones using Gap Locations, Submitted to 9th AsiaPacific Software Engineering Conference, 2002.
24) S. W. L. Yip and T. Lam, A software maintenance survey, Proc. of APSEC ’94, pages 70-79,
1994.

植田 泰士（正会員）
平 13 阪大・基礎工・情報卒．平 15
同大大学院博士前期課程修了．現在，
宇宙開発事業団所属．在学中，コー
ドクローン分析の研究に従事．

神谷 年洋（正会員）
平 8 阪大・基礎工・情報中退．平13 同大大学院博士課程了．現在，科学技術振興機構 さきがけ研究者．博士 (工学)．オブジェクト指向関連技
術，ソフトウェア保守 (メトリクス，
コードクローン)，認知科学に関する研究に従事．IEEE各会員．
楠本 真二（正会員）
昭 63 阪大・基礎工・情報卒．平 3
同大学院博士課程中退．同年同大・
基礎工・情報・助手．平 8 同大講師．
平 11 同大助教授．平 14 阪大・情報・コンピュータサイエンス・助教
授．博士 (工学)．ソフトウェアの生産性や品質の定量的評価，プロジェクト管理に関する研究に従事．IEEE
各会員．
井上 克郎（正会員）
昭 54 阪大・基礎工・情報卒．昭 59
同大大学院博士課程了．同年同大・
基礎工・情報・助手．昭 59〜昭 61
ハワイ大マノア校・情報工学科・助教授．平 1 阪大・基礎工・情報・講師．平 3 同学科・助教授．平 7 同学科・教授．工学博(平成 ? 年 ? 月 ? 日受付)

士．平 14 阪大・情報・コンピュータサイエンス・教(平成 ? 年 ? 月 ? 日採録)

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

肥後 芳樹（正会員）
平 14 阪大・基礎工・情報中退．平 16
同大大学院博士前期課程修了，現在同大大学院博士後期課程 1 年．コー
ドクローン分析の研究に従事．