コードクローン検出技術と その利用法 神谷年洋‡, 植田泰士†, 肥後芳樹†, 楠本真二†, 井上克郎† †大阪大学 大学院情報科学研究科 {y-ueda, y-higo, kusumoto, inoue}@ist.osaka-u.ac.jp ‡科学技術振興事業団 さきがけ研究21 kamiya@ist.osaka-u.ac.jp

ツールCCFinder / Gemini / CCShaper コードクローンとは コードクローン検出と開発プロセス コードクローン検出手法 ツールCCFinder / Gemini / CCShaper アルゴリズム 適用事例 2002/11/15

コードクローンとは ソースコード中に類似したコード片があるとき， それらをコードクローンという クローンクラス クローンペア クローンが生じる理由：コピー＆ペースト，定型処理，意図的な繰り返し，偶然，プログラミング言語に適切な機能がないため，など 2002/11/15

コードクローンが引き起こす問題 コードクローンはソフトウェア保守を困難にする コードクローンにフォールトが存在する場合，すべてのコードクローンについて修正を行わなければならない 機能追加も同様 大規模なソースコードからコードクローンを効率よく検出する方法が必要 2002/11/15

コードクローン検出と開発プロセス 修正前チェック リファクタリング 定型処理（イディオム）抽出 修正しようとする部分にコードクローンがあるかチェックする → すべて修正 リファクタリング コードクローンを検出する → まとめる 「メソッドの抽出」「メソッドの引き上げ」 定型処理（イディオム）抽出 よく使われるコード断片を抽出 → 部品化 2002/11/15

コードクローン検出のその他の応用 ソースコードの剽窃をチェックする バージョン間の変化を調べる 定量的な評価 よりよいdiffとして 2002/11/15

既存のコードクローン検出手法(1/2) Bakerの手法 Baxterらの手法 行単位でソースコードを比較してコードクローンを検出する C言語のソースファイルを入力，構文解析して，解析木(の部分木)を比較する [Baker1995] B. S. Baker: “On finding Duplication and Near-Duplication in Large Software System,” Proc. Second IEEE Working Conf. Reverse Eng., pp. 86-95, Tronto, Canada (Jul., 1995). [Baxter1998] I. D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier: “Clone Detection Using Abstract Syntax Trees,” Proc. of ICSM ’98, pp. 368-377, Bethesda, Maryland (Nov., 1998). 2002/11/15

既存のコードクローン検出手法(2/2) Merloらの手法 手続き（メソッドや関数）の特徴メトリクスを比較して，計測値が似ていればコードクローンであると判定する [Balazinska1999] M. Balazinska, E. Merlo, M. Dagenais, B. Lague, and K.A. Kontogiannis, "Measuring Clone Based Reengineering Opportunities", Proc. 6th IEEE Int'l Symposium on Software Metrics (METRICS '99), pp. 292-303, Boca Raton, Florida, Nov. 1999. 2002/11/15

CCFinder： コードクローン検出ツール ソースコードを字句解析してトークンの列に直してからコードクローン検出を行う （浅い）文法知識に基づいたソースコード変形 クラススコープや名前空間による複雑な名前の正規化を行う 初期化テーブルを取り除く モジュールの区切りを認識する 言語依存部分を取り替えることで，さまざまなプログラミング言語に対応 2002/11/15

コードクローン検出手順 (1)ソースコードを入力し，トークンの列にする (2)変形ルールにより，トークン列を変形する (3)パラメータ置換を行う (4)マッチングアルゴリズムによりコードクローンを検出する (5)コードクローンの位置(ファイル，行, カラム)を出力する 2002/11/15

例題ソースコード 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 2002/11/15

ステップ(1)：ソースコードを入力し，トークンの列にする 2002/11/15

ステップ(2)：変形ルールにより，トークン列を変形する 2002/11/15

ステップ(3)：パラメータ置換を行う 2002/11/15

マッチングアルゴリズムにより，コードクローンを検出 ステップ(4)： マッチングアルゴリズムにより，コードクローンを検出 2002/11/15

マッチングアルゴリズムにより，コードクローンを検出 ステップ(4)： マッチングアルゴリズムにより，コードクローンを検出 2002/11/15

ステップ(5)：コードクローンの位置を出力する 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 2002/11/15

変形ルールを用いない場合 4-6行目と 13-15行目， 8-10行目と 17-19行目 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) { 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. } 9. System.out.println("sum = " + sum); 10. } 11. static void goo(String [] a) throws RESyntaxException { 12. RE exp = new RE("[0-9,]+"); 13. int sum = 0; 14. for (int i = 0; i < a.length; ++i) { 15. if (exp.match(a[i])) 16. sum += parseNumber(exp.getParen(0)); 17. } 18. System.out.println("sum = " + sum); 19. } 変形ルールを用いなかった場合には，行3と行12，行7と行16が異なった行であると判定されるため，検出されるクローンはいずれも3行以下のクローンになります． 2002/11/15

Java向けの変形ルール RJ1：パッケージ名除去 ( PackageName ‘.’ )+ ClassName → ClassName RJ2:Callee挿入 NDotOrNew NClassName ‘(‘ → NDotOrNew CalleeIdentifier ‘.’ NClassName ‘(‘ RJ3:テーブル初期化除去 '=' '{' InitalizationList, '}' → '=' '{' UniqueIdentifier '}‘ ']' '{' InitalizationList, '}' → ']' '{' UniqueIdentifier '}’ RJ4:モジュールの分離 トップレベルの定義や宣言の終わりにUniqueIdentifier を挿入する RJ5:可視性キーワードの除去 protected, public，synchronizedなどのキーワードを取り除く RJ6:コンパウンド・ブロックの処理 if (…), else, while (…) の直後が単文なら{}を補う 2002/11/15

適用例#1 JDKのライブラリ JDK（Java Development Kit） 1.2.2（サンプルとデモプログラムを除く） 入力ファイルは164８個，約50万行 ツールの実行には，Pentium III 650MHzおよび1GBのRAMを持つPCで約3分を要した 2002/11/15

JDKのコードクローン散布図 両軸はソースファイルを辞書順に並べたもの 20行以上のコードクローンを図示 多くのコードクローンが密集している（A) 最長のコードクローン（B） B A 2002/11/15

コードクローンが密集している部分（A） src/javax/swing/plaf/multi/*.java（29個） クラス名を除いてまったく同じクラスの定義 コード生成ツールによって生成された 31| */ 32| public class MultiButtonUI extends ButtonUI { 33|   160| public static ComponentUI createUI(JComponent a) { 161| ComponentUI mui = new MultiButtonUI(); 162| return MultiLookAndFeel.createUIs(mui, 163| ((MultiButtonUI) mui).uis, 164| a); 165| } 2002/11/15

最長のコードクローン（B） 最長のコードクローン（349行） src/java/util/Arrays.javaの18の“sort”メソッド シグネチャ（引数の型と数）が異なる アルゴリズムは同一 2002/11/15

適用例#2 FreeBSD, Linux, NetBSDの比較 3つのOSの比較 FreeBSD 4.0 (C 220万行) Linux 2.4.0 (C 240万行) NetBSD 1.5 （C 260万行) FreeBSDとNetBSDは同じソースコードから，Linuxは異なるソースコード 実行には108分を要した 2002/11/15

FreeBSD, Linux, NetBSDのコードクローン散布図 2002/11/15

FreeBSDとLinuxのコードクローン ドライバ部分に多くのクローン「ファイル」が存在する 共通のソースから分岐したソースファイル 名前が付け替えられたソースファイル あるソースファイルを複数のファイルに分割している → 2002/11/15

大学の演習(1) Pascal風言語で書かれたコードをCASLに変換するコンパイラ Ｃ言語で開発 教科書,指導書を参考にして作成 課題１：構文チェッカ, 課題２：意味チェッカ, 課題3：コンパイラ，の順に作成 課題2と課題3では直前の課題で作成したプログラムを拡張 27人分のソースコード（P1～P27）を利用 次に，実験の概要について説明します。 データはある年度の情報科学演習Dにおいて作成されたプログラムを収集 しました。 この演習では，Pascal風言語で書かれたコードをCASLに変換するコンパイラをC言語で開発します。 教科書，指導書を参考にして作成していき，課題１では構文チェッカを，課題2では意味チェッカを課題3ではコンパイラの順に作成していきます。 課題２では課題1の課題3では課題2で作成されたプログラムを拡張していきます。 27人のソースコードをP１」からP27として入力データとします。 そしてDupSに適用し一致するコード片を検出した後，結果を分析します。 2002/11/15

大学の 演習(2) P1 P2 P3 P4 P5 P1 P2 P3 P4 P5 2002/11/15

大学の演習(4) 拡張時における利用割合による分析 関数単位の利用のされ方による分類 拡張時の利用度が高いP17（71%）と低いP5（39%）について調査 P17では課題2で作成したプログラムを関数単位でうまく利用している　　　　　 →　課題2における設計がしっかりしていたと評価できる P5では何らかの理由で大幅な作り変えが行われた　　　　　　　　　　　　　　　　　 →　原因を調査し対処方法を指導に盛り込む 課題2から課題3に拡張する時際の，利用度が高いP17と利用度の低いP5 について調べた結果です。 P17とP５について，その課題2のプログラムの関数について，そのまま利用された関数，修正されて利用された関数，全く再利用されていない関数にわけて集計し円グラフにしました。 P17では６４％の関数がそのまま課題3で使用されました。 これより，P17では課題2で作成したプログラムを関数単位でうまく利用していることが言え，課題2における設計がしっかりしていたと評価できます。 またP22では，６９％の関数が利用されず，何らかの理由で作り変えが行われたと思われ，原因を調査し対処方法を指導に盛り込む事が考えられます。 2002/11/15

ツールGemini / CCShaper インタラクティブな環境を提供(Gemini) 統計的な分析（Gemini) スキャッタープロット表示，ズーム，ソート 統計的な分析（Gemini) メトリクスグラフ Gappedクローン検出(Gemini) コピー＆ペースト＆修正されたコード断片 CCFinderの出力から意味的なまとまりを取り出す(CCShaper) 2002/11/15

Gemini: コードクローン分析環境 CCFinderの出力はテキストベース ソースコード分析を補助するツール 分析が大変 直感的，対話的な操作 統計分析機能 2002/11/15

Gappedクローン検出 コピー＆ペーストの後，追加や削除が行われる 追加や削除された部分＝ギャップ Gappedクローン検出機能により，そのような場合でもコードクローンとして検出することができる 2002/11/15

Gappedクローンの例 Geminiで検出されたGappedクローン 赤い文字の部分がギャップ 543| else { 544| t = NULL_STRING; 545| spaces.push_back(t); 546| errors.push_back(pos); 547| append_recover_to_last_space(); 548| state = MS_INIT; 549| } 550| 551| bool bFirstTrial = true; 552| bool bGotAvailToken = false; 553| while (! bGotAvailToken && pos < text.size()) { 554| if (get_word(&t, SpecialPrevChar)) { 340| else { 341| t = ""; 342| //pool_thru(&pool, &t); 343| spaces.push_back(t); 344| errors.push_back(pos); 345| append_recover_to_last_space(); 346| } 347| 348| bool bFirstTrial = true; 349| bool bGotAvailToken = false; 350| while (! bGotAvailToken && pos < text.size()) { 351| if (get_word(&t)) { Geminiで検出されたGappedクローン 赤い文字の部分がギャップ 2002/11/15

CCShaper： 「絞り込み」ツール CCFinderが検出するコードクローンはトークンの並び 必ずしも意味的な固まり(クラス，メソッド，etc…)にはなっていない リファクタリング（「メソッドの抽出」や「メソッドの引き上げ」）の対象としては不適当なコードクローンが多く含まれる 適切なフィルタリング 2002/11/15

メソッドの抽出 Void methodA(int i){ void methodA(int i){ methodZ(); System.out.println(“name:” + name); System.out.println(“amount:” + i); } Void methodB(int i){ methodY(); void methodA(int i){ methodZ(); methodC(i); } void methodB(int i){ methodY(); Void methodC(int i){ System.out.println(“name:” + name); System.out.println(“amount:” + i); methodC(i); methodC(i); 2002/11/15

メソッドの引き上げ クラスA クラスB クラスC 　メソッドA クラスA クラスB クラスC 　メソッドA 2002/11/15

CCFinderで検出されるコードクローン(例1) righttokennumber = c.getEndNumber() - c.getStartNumber() + 1; } string getLeftClone() const { char temp[STRLENGTH]; snprintf(temp,STRLENGTH, "%s\t%d,%d,%d\t%d,%d,%d\t",leftID.c_str(), leftstartline,leftstartcolumn,leftstartnumber, leftendline,leftendcolumn,leftendnumber); string clone(temp); return clone; string getRightClone() const return clone; } string getRightClone() const { char temp[STRLENGTH]; snprintf(temp,STRLENGTH, "%s\t%d,%d,%d\t%d,%d,%d\t",rightID.c_str(), rightstartline,rightstartcolumn,rightstartnumber, rightendline,rightendcolumn,rightendnumber); string clone(temp); int getLeftTokenNumber() const return lefttokennumber; の部分を検出してほしい 2002/11/15

CCFinderで検出されるコードクローン(例2) if(func->parameter!=NULL) return error("Error:Parameter Exist"); curVertex->kind=ST_call; lp=makeexptree(NULL,NULL,SIDENTIFIER,idtemp,SPROCEDURE); curVertex->tree=lp; curVertex->refer=search_tree_postorder(lp); curVertex->refer=uniq_RDlist(curVertex->refer); cutSt(); } break; case 66: #line 314 "subPascalParse.y" {struct FUNCTION *func; struct RD *para; lp=makeexptree(&lp,NULL,SRPAREN,NULL,SNULL); rp=makeexptree(NULL,&lp,SIDENTIFIER, idtemp,SPROCEDURE); curVertex->kind=ST_call; curVertex->tree=rp; curVertex->refer=search_tree_postorder(rp); curVertex->refer=uniq_RDlist(curVertex->refer); cutSt(); } break; case 67: #line 355 "subPascalParse.y" {yyval.exptree = yyvsp[0].exptree;} CCFinderは の部分を検出 しかし，このコードクローンはリファクタリングの対象にはならない 2002/11/15

CCShaperの アプローチ コードクローンの存在するソースコード(Java)を構文解析する 構文解析結果とCCFinderの出力から意味的なまとまり（ブロック構造）を抽出する コードクローン検出（CCFinder） 絞り込み(CCShaper) 表示（Gemini） 　　意味的にまとまりのあるコードクローン コードクローン 2002/11/15

適用実験その1(ANTLR)(1/5) ソースファイルは239個 総行数は約44000行 数値による結果比較 388574 984 1072 CCShaper無し CCShaperあり クローンペア数 388574 984 クローンクラス数 1072 148 解析時間：約2分 2002/11/15

適用実験その1(ANTLR)(2/5) スキャタープロット図による比較 CCShaper無し CCShaper有り a 2002/11/15

適用実験その1(ANTLR)(3/5) 選択範囲のコードクローン public final void mOPEN_ELEMENT_OPTION(boolean _createToken) throws RecognitionException, CharStreamException, TokenStreamException { 　　　int _ttype; 　　　Token _token=null; 　　　int _begin=text.length(); 　　　ttype = OPEN_ELEMENT_OPTION; 　　　int _saveIndex; 　　　match('<'); 　　　if ( _createToken && _token==null && _ttype!=Token.SKIP ) { 　　　　　　_token = makeToken(_ttype); 　　　　　　_token.setText(new String(text.getBuffer(), _begin, text.length()-_begin)); 　　　} 　　　_returnToken = _token; } 2002/11/15

適用実験その1(ANTLR)(4/5) 引数を2つ増やすことで１つのメソッドにまとめることができる 発見されたコードクローンの検証 異なっていたのは の部分のみ このコードクローンが20箇所に現れていた すべてのコードクローンは同じクラスのメソッドであった 引数を2つ増やすことで１つのメソッドにまとめることができる 2002/11/15

適用実験その1(ANTLR)(5/5) クラス図による比較 現状 ANTLRLexer クラス図による比較 現状 ANTLRLexer mOPEN_ELEMENT_OPTION(boolean _createToken) mCLOSE_ELEMENT_OPTION(boolean _createToken) mCOMMA(boolean _createToken) mQUESTION(boolean _createToken) mTREE_BEGIN(boolean _createToken) mLPAREN(boolean _createToken) mRPAREN(boolean _createToken) mCOLON(boolean _createToken) mSTAR(boolean _createToken) mPLUS(boolean _createToken) mASSIGN(boolean _createToken) mIMPLIES(boolean _createToken) mSEMI(boolean _createToken) mCARET(boolean _createToken) mBANG(boolean _createToken) mOR(boolean _createToken) mWILDCARD(boolean _createToken) mRANGE(boolean _createToken) mNOT_OP(boolean _createToken) mRCURLY(boolean _createToken) : Other methods （22個） 2002/11/15

適用実験その1(ANTLR)(5/5) クラス図による比較 リファクタリングした場合 ANTLRLexer クラス図による比較 リファクタリングした場合 ANTLRLexer mTOKEN(boolean _createToken,int i,char c) : Other methods（22個） 2002/11/15

まとめ コードクローン検出 ツールCCFinder / Gemini / CCShaper ソフトウェア保守 ソースコードを調べるための手段 より広範囲な意味での（Gapped）クローンを検出する 絞り込みによって，利用目的に応じたコードクローンを提示する 2002/11/15

END 2002/11/15