類似コード片を利用したリファクタリングの試み
肥後芳樹 ††

神谷年洋 ‡

楠本真二 †‡

大阪大学大学院情報科学研究科〒 560-8531 大阪府豊中市待兼山町 1-3

井上克郎 †

科学技術振興事業団 若手個人研究推進事業〒 332-0012 埼玉県川口市本町 4-1-8

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

On Program Refactoring Using Code Clone Information
Yoshiki Higo††Toshihiro Kamiya‡

Shinji Kusumoto†

Graduate School of Information Science andTechnology
Osaka University
1-3 Machikaneyama-cho, Toyonaka,
Osaka 560-8531, Japan‡

Katsuro Inoue†

PRESTO, Japan Science and Technology
Corporation
4-1-8 hon-machi, Kawaguchi,
Saitama 332-0012, Japan

Maintaining software systems is getting more complex and difficult task. Code clone is one of thefactors that make software maintenance more difficult. A code clone is a code portion in source files
that is identical or similar to another. If some faults are found in a code clone, it is necessary tocorrect the faults in its all code clones. We have developed a maintenance support 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 provided
by Gemini were not appropriate for refactoring. In this paper, we intend to extend the functionalityof Gemini to cope with the problems. Finally, we apply the extended Gemini to several software andevaluate the applicability of the new functions.

-1-

1

はじめに

これらの機能を用いることによってソフトウェアの保守作業を改善することができると期待できる．

ソフトウェアの大規模化・複雑化に伴い，高品

我々は Gemini を数十のソフトウェア会社に配質なソフトウェアを効率的に開発する手法が重要

布し，さまざまなプロジェクトに用いることによっとなっている．ソフトウェアプロセスの改善はそて評価した．その結果，ソフトウェア会社からのの手法の一つといえる．近年，保守工程はソフト

フィードバックよりいくつかの問題点が発見されウェア開発で最もコストを要する過程であると指た．最も多く指摘された問題は，Gemini をリファ

摘されている．また多くのソフトウェア会社が既

クタリング [7] に利用する際に発生する問題であっ存のシステムの保守に非常に多くの人的，時間的た．一般的に，コードクローンを除去することをコストをかけているとも報告されている [22]．ソ

目的として，コードクローンになっている部分を

フトウェアシステムの保守とは，そのシステムが一つのメソッドやクラスにまとめるリファクタリ

顧客に渡された後に，バグの修正や性能の改善のングが適用される．しかし Gemini によって検出さために，システムを修正することを意味する [19]．

れたコードクローンは，必ずしも一つのモジュー

コードクローンはソフトウェア保守を困難にしルとしてまとめるのに適していない．

ている一つの要因といわれている [7]．コードク

本論文では，この問題を解決するために Gemini

ローンとはソースコード中に存在する同一，またのコードクローン検出部に対して行なった拡張には類似したコード片のことである．コードクロー

ついて論ずる．そして最後に，提案した機能の有ンが生成される原因はさまざまな理由が考えられ用性を確認するために行なった適用実験の結果にるが，その最も大きな原因の一つとしてコピーア

ついて述べる．

ンドペーストによる修正，拡張作業があげられる．

2

コードクローン解析

2.1

コードクローンの定義 [10]コード片にバグが含まれていた場合，そのコード
片のコードクローンとなっている部分全てに対しあるトークン列中に存在する 2 つの部分トークて修正の是非を考慮する必要がある．特に大規模

ン列 α，β が等価であるとき，α と β は互いにク

ソフトウェアにおいては，これは非常に手間のかローンであるという．またペア（α，β ）をクローかる作業であるので，コードクローン検出の効率

ンペアと呼ぶ．α，β それぞれを真に包含する如何

化はソフトウェア保守工程の改善において有効である．これまでにコードクローン自動的にを発見なるトークン列も等価でないとき，α，β を極大クするためのさまざまな手法が提案されている．

ローンと呼ぶ．また，クローンの同値類をクローンクラスと呼ぶ．ソースコード中でのクローンをその手法の一つとして，我々はコードクローン

特にコードクローンという．

検出ツール CCFinder[12] と分析環境 Gemini[20]2.2を開発してきている．Gemini の一コンポーネント

コードクローン分析環境 Gemini

文献 [20] において我々はコードクローン分析環に CCFinder が用いられている．ユーザは Gemini

境 Gemini を開発した．図 1 はシステムのアーキテを用いることによりコードクローンの解析，ソークチャを示している．Gemini は内部の CCFinder

スコードの修正を容易に行なうことができる [21]．

Gemini は主に，クローン散布図とメトリクスグラ
フをユーザインターフェースとして提供する．ク

にソースコードを渡し，CCFinder の解析結果をローン散布図はソースコード中のコードクローン

ザに提供する機能を有する．

さまざまなユーザインターフェースを通してユー
本章では，簡単に Gemini と CCFinder の特徴の分布状態を俯瞰的に表示する．またメトリクス
グラフは各々のコードクローンについての定量的を説明する．

な情報を提供し，その値を用いることによって保2.2.1

守を阻害するコードクローンの選択をすることが可能である．選択されたコードクローンのソース

CCFinder はプログラムのソースコード中に存在するコードクローンを検出し，その位置をクロー

コードは容易に閲覧することができる．ユーザはンペアのリストとして出力する．検出されるコー-2-

CCFinderInterfaces

Code clone analysis environment, Gemini
Clone pair manager
Clone selection
information

Code clone detector
Source files

Clone scatter plot view

User

Source code manager
Code clone database

Source code view
Clone selection
information

Metrics manager
Metric graph views

図 1: Gemini 全体図
ドクローンの最小トークン数はユーザが前もって
図 2: クローン散布図表示例

設定することができる．

CCFinder のコードクローン検出手順（ソース
コードを読み込んで，クローンペア情報を出力する）は大きく 4 つの過程から成り立っている．
ステップ 1（字句解析）: ソースファイルを字句解析することによりトークン列に変換する．入力ファイルが複数の場合には，個々のファイルから得られたトークン列を連結し，単一のトークン列を生成する．
ステップ 2（変換処理）: 実用上意味を持たない
図 3: ソースコードビュー表示例

コードクローンを取り除くこと，及び，些細な
表現上の違いを吸収することを目的とした変換• ソースコードビュー．

ルールによりトークン列を変換する．例えば，この変換により変数名は同一のトークンに置換さクローン散布図はソースコードのどの部分にクれるので，変数名が付け替えられたコード片もローンペアが存在するのかを示す図である．一目

コードクローンであると判定することができる．

でソースコード中のコードクローンの分布状況がステップ 3（検出処理）: トークン列の中からわかるので，コードクローン解析の初期段階では指定された長さ以上一致している部分をクロー

非常に有効な解析手段となりうる．図上でユーザンペアとして全て検出する．

はマウスを用いて任意のクローンペアを選択する

ステップ 4（出力整形処理）: 検出されたクローことが可能であり，その例を図 2 に示す．クロー

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

ン散布図の詳細については後ほど論ずる．

情報を出力する．

またメトリクスグラフを用いることにより，ユー

CCFinder の詳細については文献 [12] を参照されたい．

ザはコードクローンを定量的な特性に基づいて選2.2.2

について複数のメトリクス値が示されているので，択することができる．それぞれのクローンクラス

Gemini

ユーザは長いコードクローンや，出現数の多いコー

Gemini は GUI ベースのコードクローン分析環
境であり，内部的にコードクローン検出部としてドクローンを選択できる．
ソースコードビューはクローン散布図やメトリ

CCFinder を用いている．Gemini はユーザに以下のユーザインターフェースを提供し，対話的な解

クスグラフと組み合わせて用いられる．ユーザはクローン散布図やメトリクスグラフで選択されたク

析を可能としている．

ローンのソースコードをソースコードビューを用• クローン散布図，いることにより閲覧することができる．図 3 では，• メトリクスグラフ，

図 2 において選択されたコードクローンのソース

-3-

1

A

2

B

3

C

4

E

c o d e fra g m e n t Y
5 6 7 8
F

B

C D

9

E

10

B

11
C

摘された．その一つはコードクローンを用いたリ

12

ファクタリングにおける問題であった．

D検出したコードクローンをリファクタリング [7]

1

A

3

C

ンを検出してもその部分を一つの関数，メソッドDなどにまとめることは難しい．我々はこれまでに

5C

多くの実験を行なってきたが，その実験で検出さDれた大部分のコードクローンは，特に意味的なま7

Eとまりを持たないものであった．図 5 に例を示す．

F

図 5 では，A と B の二つのコード片が示されてい9B

る．A と B それぞれの灰色の部分は，その部分が2に用いる場合の問題点として，単に最大長のクロー

B

4code fragment X

6
8

10

C

A と B の間の最大長のコードクローンであることを示している．コード片 A ではいくつかのデータがリスト構造の先頭から順に連続して格納されている．一方コード片 B では，リスト構造の後方から順に連続してデータが格納されている．これら

11 D

12 G

A ,B ,C , ... : c h a r a c te r , to k e n , lin e , s ta te m e n t o r f u n c tio n , ... e tc .
: c o d e c lo n e

二つのコード片間には共にリスト構造を扱ってい
図 4: クローン散布図モデルるという点において論理的に共通している．しかコードを表示している．

しながらこれらのコード片の for 文の前後には偶

2.2.3

然クローンとして含まれてしまった部分が存在しクローン散布図

図 4 はクローン散布図の例を示している．クローている．リファクタリングの視点からは，灰色のン散布図の縦軸と横軸にはソースコード中のトー部分全体よりも for 文のみをコードクローンとしクンが出現順に配置される．ここではクローン散て抽出する方が望ましい．
コードクローンをリファクタリングするための布図を説明するために以下の文字列を用いる．

研究はいくつか行なわれている．文献 [13] と文献
コード片 X: “ABCDCDEFBCDG”,[14] では，プログラム依存グラフを用いてコードクローンの凝集度を測定し，関数やメソッドの抽出に用いる方法が述べられている．しかしそれらの方法では，プログラム依存グラフの構築に非常にコストがかかることから大規模なソフトウェア
への適用が難しく，スケーラビリティの面から見て問題がある．一方 CCFinder では，検出過程において字句解析のみにとどめているため，その検コード片 Y: “ABCEFBCDEBCD”
ここでは，“A” や “B” などは文字や，トークン，行，文などのある一定の単位を表すとする．図 4の格子内の黒色の矩形はその縦軸の要素と横軸の要素が等しいことを意味している．このことから
クローンペアはクローン散布図においてある一定以上の長さを持った線分として出現することとな

出処理は非常に高速である．しかし，CCFinder にる．もし縦軸と横軸に配置される要素が同じファよって検出されるコードクローンは単に最大一致イルである場合は，主対角線上に黒色の矩形がプトークン数によるものであり，コードクローンのロットされる．またこの時はこの対角線に対して凝集度は考慮されていない．つまり CCFinder を

クローン散布図は線対称となる．

3

提案手法

3.1

これまでの問題点用いたコードクローン検出をリファクタリングに適用しようとした場合，ユーザは自ら CCFinderの検出結果から意味的なまとまりのある部分を抽

我々は，Gemini（と CCFinder）をさまざまな出する必要がある．

商用，及び非商用ソフトウェアに適用してきた．そこの問題を解決するため，我々はまず最大長のしてフィードバックとしていくつかの問題点が指コードクローンを検出し，さらにそのクローンに-4-   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 _ ` 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^]

図 6: Code Clone Shaper 概要

図 5: コードクローンのリファクタリング例
対して意味的なまとまりのある部分のみを抽出す

C++の三種類である．ここでは，実装したシェイ

るという二段階のアプローチを提案する．この提プドクローン検出プログラム（Code Clone Shaper

案手法では，例え対象が大規模なソフトウェアで以後 CCShaper と略す）について説明する．実装あっても実用的な時間でリファクタリングの容易したプログラムは図 6 にも示されているように大なコードクローンを検出することができる．

3.2

きく分けて四つのモジュールから構成されている．

アプローチ

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

• 制御部
• プログラム解析部
• 抽出部
• 出力部
制御部

STEP1: 対象のソフトウェアに対し CCFinderを実行し，コードクローンを検出する．
STEP2: 対象のソフトウェアを解析し，関数やfor 文，if 文などの意味的なまとまりをもったブロックの位置情報を抽出する．
STEP3: コードクローンの情報と，ブロックの位置情報を突き合わせ，意味的なまとまりのある部分のみを抽出する．

制御部は CCFinder の出力したコードクローン
情報を解析し，字句解析部や，ブロック抽出部，ブロック管理部を呼び出す役割を担っている．
プログラム解析部
プログラム解析部では対象のソースコードを字
句解析，構文解析して，プログラム中のブロックの位置情報を取得する．ここではブロックを中括

ここで，「意味的にまとまりのある」とは，直観

弧 (‘{’,‘}’) で囲まれた範囲と定義する．現段階で的には一つの関数などにまとめるのが容易にでは字句解析によって抽出された情報しか用いておきるような部分を指している．

3.3

らず，構文解析は今後の解析で用いる予定である．
抽出部

実装

ソースコードからシェイプドクローンを取り出す

プログラム解析部で抽出したブロックの位置情機能を Gemini に実装した（図 6 参照）．この部分

報と，CCFinder の出力結果であるコードクローのプログラムは約 4000 行であり C++によって実ン情報を突き合わせ，コードクローンである部分

装されている．現在のところ，対象言語は Java，C，から意味的にまとまりのある部分のみを抽出する．

-5-

表 1: ソースコードサイズ
ファイル数 行数
トークン数
508
141254221203Ant

図 8: Ant のクローン散布図（CCShaper 有）

Code Clone Shaper を適用する前、適用後のクローン散布図をそれぞれ図 7、図 8 に示す. また、適用前後のコードクローン数の比較を表 2 に示す.
CCShaper を用いない場合には、Ant 内には一様にコードクローンが散布しており，どのコードク
ローンを取り除くべきか、取り除くことができるかを判断するのに、非常に手間がかかってしまう

図 7: Ant のクローン散布図（CCShaper 無）
出力部
ブロック抽出部で取り出した意味的にまとまりのあるコードクローンを適切な順番で並び変え，

Gemini に与えるデータとして一貫性のあるものに
変換する．

4

適用実験

4.1

実験概要

と考えられる. 一方で、CCShaper を用いた場合には、リファクタリングが難しいコードクローンを取り除くことにより、クローンペアの 99 ％以上（1 万個以上）、クローンクラスの約 94 ％（803 個）を省くことができている.

前章で提案したシェイプドクローンの検出方法の有用性を確認するためにオープンソースの Java

実際に検出されたコードクローンのソースコー

ソフトウェアである Ant[1] に対して適用実験を行

ドを調べるために，最もクローンペアが密集してなった．Ant は Java 用のビルドツールである．ビ

いるラベル B で示す部分をソースコードビューでルド手順は XML で記述される．

閲覧する．9 はこの部分のコードクローンのソー提案手法の評価をするために，CCShaper を用

スコードを示している．このメソッド単位のコー

いた Gemini と用いていない Gemini を用いてそれ

ドクローンは 7 つのクラスに，各々一つずつ存在

ぞれ対象のソースファイルを解析した．そしてそのした．またこれら 7 つのクラスは全て同一のクラ後結果を比較した．この適用実験では，CCFinder

スを親クラスとして定義していた．これらのことが検出するコードクローンの最小一致トークン数からこのコードクローンは親クラスに引き上げるは 50 に設定した．

表 2: Ant から検出されたコードクローン数の比較

4.2

Ant

次に Ant に対しての実験結果を示す．Ant は 508

クローンペア数
クローンクラス数個のファイルから成り立っており，総行数は 14 万

1 千行であった．
-6-

CCShaper 有 CCShaper 無
12033
103
856
53

ing Abstract Syntax Trees, Proc. IEEE Int’l
Conf. on Software Maintenance (ICSM) ’98,
pages 368-377, Bethesda, Maryland, Nov.
1998.

          "!! #$  %!&'( ) *!,+- $.,$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[6] 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 109-118, Oxford, England, Aug. 1999.

図 9: ラベル B のコードクローンのソースコード
ことによって取り除くことができる．

5

まとめ[7] M. Fowler, Refactoring: improving the design of existing code, Addison Wesley, 1999.

本論文では，既存のコードクローン分析環境

Gemini を拡張してリファクタリングの候補となりうるコードクローンのみを抽出する機能（CodeClone Shaper）を提案した．そして提案手法をツールとして実装し，オープンソースのソフトウェアである Ant に適用した．Code Clone Shaper を適用することでコードクローンをフィルタリングすることに成功し，抽出されたコードクローンはいず
れもリファクタリングの容易なものであった．これらのことから本論文で提案したコードクローン抽出手法は非常に有用であると考えることができる．
また，今後はこのツールを実際のソフトウェア[8] D. Gusfield, Algorithms on Strings, Trees,
And Sequences, Cambridge University Press,
1997.
[9] J. Helfman, Dotplot Patterns: a Literal Look
at Pattern Languages, TAPOS, 2(1):311,1995.
[10] 井上克郎, 神谷年洋, 楠本真二, “コードクロー
ン検出法”, コンピュータソフトウェア, vol.18,
no.5, pp.47-54, 2001.

保守の場面で利用し，そのプロセス改善に役立て[11] J. H. Johnson, Identifying Redundancy inSource Code using Fingerprints, Proc. of
CASCON ’93, pages 171-183, Toronto, Ontario, 1993.

たいと考えている．

参考文献[1] Ant, http://jakarta.apache.org/ant/,
2002.

[12] T. Kamiya, S. Kusumoto, and K. Inoue,
CCFinder: A multi-linguistic token-based
code clone detection system for large scale
source code IEEE Transactions on Software
Engineering, (to appear).

[2] B. S. Baker, A Program for Identifying
Duplicated Code, Computing Science andStatistics, 24:49-57, 1992.
[3] B. S. Baker, On Finding Duplication and
Near-Duplication in Large Software Sys-[13] R. Komondoor and S. Horwitz, Using slic-

tems, IN Proc. IEEE Working Conf. on Reverse Engineering, pages 86-95, July 1995.

ing to identify duplication in source code, In
Proc. of the 8th International Symposium[4] B. S. Baker, Parameterized Duplication in
Strings: Algorithms and an Application to

on Static Analysis, Paris, France, July 1618, 2001.

Software Maintenance, SIAM Journal on
Computing, 26(5):1343-1362, 1997.

[14] Jens Krinke, Identifying Similar Code with
Program Dependence Graphs , In Proc. of
the 8th Working Conference on Reverse En-[5] I. D. Baxter, A. Yahin, L. Moura, M.
Sant’Anna, and L. Bier, Clone Detection Us-

gineering, 2001.
-7-

[15] 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 244253, Monterey, California, Nov. 1996.
[16] L. Prechelt, G. Malpohl, M. Philippsen,
Finding plagiarisms among a set of programswith JPlag, submitted to Journal of Universal Computer Science, Nov. 2001, taken fromhttp://wwwipd.ira.uka.de/~prechelt/Biblio/[17] M. Rieger, S. Ducasse, Visual Detection of
Duplicated Code, 1998.
[18] Duploc, http://www.iam.unibe.ch/~rieger/duploc/,
1999.
[19] Pigoski T. M, Maintenance, Encyclopediaof Software Engineering, 1, John Wiley &Sons, 1994.
[20] Y. Ueda, T. Kamiya, S. Kusumoto, K. Inoue, Gemini: Maintenance Support Environment Based on Code Clone Analysis, 8thInternational Symposium on Software Metrics, June 4-7, 2002.
[21] Y. Ueda, T. Kamiya, S. Kusumoto, K. Inoue, On Detection of Gapped Code Clones
using Gap Locations, Submitted to 9th
Asia-Pacific Software Engineering Conference, 2002.
[22] S. W. L. Yip and T. Lam, A software maintenance survey, Proc. of APSEC ’94, pages
70-79, 1994.
[23] E. J. Wegman and Q. Luo, High Dimensional Clustering Using Parallel Coordinates
and the Grand Tour, Proc. 28th Symp. Interface of Computing Science and Statistics,
1996.

-8-