コードクローン問題に 対処する技術の動向 （コードクローン入門） 神谷 年洋 科学技術振興機構さきがけ Special Thanks to: 植田 泰士(Jaxa), 肥後 芳樹(大阪大学), 吉田 則裕(大阪大学) 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンとは ソースコード中に同一あるいは類似したコード断片があるとき、それらをコードクローンという 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンが引き起こす問題 コードクローンはソフトウェア保守を困難にする バグ修正や機能の変更が困難になる コードクローンにバグが含まれると、該当するすべてのコード断片について修正を検討する必要がある 大規模ソフトウェアでは、開発者がコードクローンをすべて覚えておく（発見する）ことはできない 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 発表の概略 コードクローンとは コードクローンが引き起こす問題 コードクローンが発生する原因 コードクローンへの対策 われわれのアプローチ コードクローン検出ツールCCFinder Gemini Aries 関連研究 コードクローン検出手法 ツリーのマッチング DP (Dynamic Programming) 特徴メトリクス Simultaneous Editing, Linked Editing Editing Process Patterns コードクローンへの対策マップ コードクローン検出手法マップ 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンが発生する原因 直接的な原因（開発者の作業） コピー＆ペースト 意図的な作りこみ 実行時性能を稼ぐためのループの展開 定型コード エラー処理 初期化 ツールで生成されたコード ただし、生成ツールとそのソースが管理できていれば問題にはならない （！生成ツールが対応できない処理） （！ソースが失われる、あるいは、提供されない） 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンが発生する原因（続き） 間接的な原因（開発プロセス） プログラミング言語に適切な機能がない スコープや動的なディスパッチなど 長期にわたって運用されているシステムでは深刻な問題 納期 コードや設計をレビューする（見直す）時間がない 共通機能の洗い出しの不足 「動いているコードには触るな」方針 ＝積極的にコードクローンを作る方針 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンへの対策マップ 部品化 コードクローンの検出 クローンコード 編集のサポート コードクローンの追跡 設計レビュー、 共通機能の 洗い出し コードクローンの 除去 制約 ソースコード 修正前のチェック 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンの検出 検出 与えられたソースコードから、文字列比較、木の比較、特徴メトリクスなどによって、同一部分を抽出する Dup, Duploc, CloneDR, Balazinska （！検出誤差） (参考) コードクローンの予防 モジュールと機能の対照表を作ってレビューする 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンの除去 自動的な除去 クローンをまとめるマクロを生成する ソースコードを修正する （！自動的に除去可能なコードクローンだけを扱うことになる） 除去作業のサポート 適用可能なリファクタリングパターンを提示する （！手作業でソースコードを編集する必要がある） 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) クローンコード編集のサポート Simultaneous Editing コードクローンになっているコード断片のひとつに対する修正を、他のコード断片に波及させる コードのバリエーションを管理するツール プログラミング言語独立の、任意のテキストを対象とした構成管理ツール(XVCL) 強力なマクロ 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンの追跡 テキストエディタのコピー＆ペースト操作を記録することで、コードクローンの発生を検出する 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 発表の概略 コードクローンとは コードクローンが引き起こす問題 コードクローンが発生する原因 コードクローンへの対策 われわれのアプローチ コードクローン検出ツールCCFinder Gemini Aries 関連研究 コードクローン検出手法 ツリーのマッチング DP (Dynamic Programming) 特徴メトリクス Simultaneous Editing, Linked Editing Editing Process Patterns コードクローンへの対策マップ コードクローン検出手法マップ 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) われわれのアプローチ コードクローンの検出  コードクローンの除去 コードクローン検出ツールCCFinder 分析ツールGemini リファクタリングサポートツールAries 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

コードクローン検出ツール CCFinder ソースコードを直接比較することによりクローンを検出するツール プログラミング言語の構文を認識して精密に、効率よく 変数名が書き換えられているクローンも検出 現在、C/C++, Java, COBOL用などがある 大規模なソースコードを対象とする 百万行規模のソースコードを実用時間で解析 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローン検出手順 以下の4つのステップを順に行う (1) ソースコードを入力してトークンの列を作る (2) プログラミング言語の文法の知識を利用した前処理をする (3) 一致部分列を特定する (4) 一致部分列のソースコード上の位置を出力する 単純化した例を使って説明・・・ 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 入力 AFG::AFG(JaObject* obj) { objname = “afg"; object = obj; } AFG::~AFG() { for(unsigned int i = 0; i < children.size(); i++) if(children[i] != NULL) delete children[i]; for(unsigned int i = 0; i < nodes.size(); i++) if(nodes[i] != NULL) delete nodes[i]; (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 入力（続き） トークンに 切り分ける (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 前処理 ユーザー定義名を$に置換 (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 一致部分列を特定 (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 一致部分列を特定（続き） (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 一致部分列を特定（続き） (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 出力 AFG::AFG(JaObject* obj) { objname = “afg"; object = obj; } AFG::~AFG() { for(unsigned int i = 0; i < children.size(); i++) if(children[i] != NULL) delete children[i]; for(unsigned int i = 0; i < nodes.size(); i++) if(nodes[i] != NULL) delete nodes[i]; (1)入力 (2)前処理 (3)一致部分列を特定 (4)出力 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 実際のツールでは… 前処理には、パターンマッチと変形ルールを用いて、 名前空間を除去 ユーザ定義名の置き換え テーブル初期化部分の除去 モジュールの区切りを認識 最適化 行列ではなく接辞尾木（suffix tree）を用いたアルゴリズム O(n+m) いろいろ枝狩り 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 3つのOSを比較した散布図 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

コードクローン分析へ CCFinderはコードクローンを検出できた でも、数百万行のソースコードから検出される何千、何万ものコードクローンを分析するのはやっぱり手間がかかる コードクローンの分析をサポート！ 実は、ここまでの散布図はgnuplotで描いてました 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローン分析ツール Gemini GUIを用いた対話的な分析 散布図上で拡大縮小、選択 選択部分のソースコードを表示 メトリクスを用いたコードクローンの絞り込み コードクローンの発生状況によるソースコードの整列 ギャップト・クローン（隣接したコードクローン）の検出機能 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

コードクローンの絞込みに用いられるメトリクス メトリクスはクローンセット（互いに類似するコードの断片の集合）に対して定義される 分散 RAD： そのクローンセットのコード断）を含むソースファイルの、ディレクトリ内での広がり  RADが大きいコードクローンは複数のサブシステムで共通に用いられるコード サイズ LEN： そのクローンセットに含まれるコード断片の長さ（トークン数） LNR： そのクローンセットに含まれるコード断片の、繰り返し部分以外の長さ（の最大値）  LNR/LENが小さいコードクローンは、繰り返しを含むコード POP： そのクローンセットに含まれるコード断片の数 DFL： そのクローンセットのコードをまとめたときに減少するコードの量の予測値 プログラミング言語に あまり依存しない 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) RADが大きいコードクローンの例 JDK 1.5.0.01 RAD=9 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

LNR/LENが大きいコードクローンの例 LNR(/LEN)大com.sun.org.apache.xerces.internal.impl.xpath.regex.RegularExpressionの２つのメソッド private int matchString(Context con, Op op, int offset, int dx, int opts)と private int matchCharacterIterator(Context con, Op op, int offset, int dx, int opts) 約４００行（１５００トークン） 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

LNR/LENが小さいコードクローンの例 com.sun.org.apache.xerces.internal.util.EncodingMapのスタティックイニシャライザ 約４３０行（LEN＝約2000, LNR < 10) 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) If (a > b) { b++; a=1;} コピー＆ペーストによる再利用 If (a > b) { b++; a=1; } Exact clone 名前の変更 If (i > j) { j++; i=0; } Renamed clone If (i > j) { i = i / 2; j++; i=0; } Gapped clone 挿入 If (i > j) { i=0; } 削除 If (i > j) { j = j + 1; i=0; } 修正 ギャップ ギャップ 開発者はコピー＆ペーストしたソースコードを修正する Next, we classify code clones into these three types, exact clone, renamed clone and gapped clone. For their explanations, I use this figure. Assume that this code fragment is an original and we reuse the code by copying-and-pasting. If the original is just copied-and-pasted like this case, it is a exact clone. This is same as the original except for the differences about blanks, new lines or comments. Additionally, If its identifiers are renamed, it is a renamed clone. And, a gapped clone is a code fragment that is partly similar to the original. It is created by operations such as insertion, delete or modification like these fragments. And we call these different code portions gaps. Also, we collectively call exact clone and renamed clone non-gapped clone. We have delivered CCFinder and Gemini Non-gapped clone 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

ギャップを想定して、短いコードクローンを検出すると・・ 短いコードクローンはたくさん検出される ３０トークン以上のコードクローン (1208ペア) １０トークン上のコードクローン(26984ペア) Now I explain why we want to detect such gapped clones. At first, almost of clones created by reusing the code with copying and pasting may become gapped clones because usually some modifications are needed to adapt the copied code to the pasting target portion. However, CCFinder can detect non-gapped clones. So, like in these two methods that are partly different to each other, a gapped clone is separately detected as several short non-gapped clones like these three. In that case, If each matched portion is too short, CCFinder does not identify it as a clone because the minimum length of clone to be detected must be set in CCFinder beforehand. If we set the minimum length to 20 tokens, these two clones are not identified because they are shorter than 20 tokens. On the other hand, if the minimum length is set to short one, too many clones would be detected because of the existence of coincidental simple statements such as substitution. These scatter plots are the result of comparison within a certain program. In the left, we plotted clones longer than 30 tokens. In the right, clones longer than 10 tokens. As you can see, too many clones are detected in the right. It is difficult to find gapped clones from such many clones. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

ギャップを含んだコードクローンを求めようとすると計算 可能な 組み合わせの数 3 15 105 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) ギャップト・クローンの検出手順 (1)（ギャップなしの）コードクローンの検出 (2)ギャップを検出 (3)ギャップをはさんでコードクローンを連結する 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

検出手順 ギャップなしのコードクローンの検出 A B C D E F G A B C E F B C D E B C D File Y File X 入力例 ソースファイルX: “ABCDCDEFBCDG” ソースファイルY: “ABCEFBCDEBCD” ギャップなしコードクローン コードクローンの検出 ギャップ検出 連結 ギャップ ギャップト・クローン ソースファイル Then, I explain shortly the gapped clone detection process using an example. with visualizing each of results. As a sample input, I use these two code sequences of file X and Y. These symbols like A, B, and C represent code portions in a certain unit such as tokens. In this example, we consider the comparison only between file X and Y. So, in this matrix, file X is arranged on the vertical axis and file Y is also arranged on the horizontal axis. In first step, non-gapped clones are detected from input source files using a presupposed non-gapped clone detection tool such as CCFinder. Then, we plot the detected non-gapped clones on this figure like this. In this plot, only non-gapped clones that are longer than 2 tokens are appeared, because in the actual source files almost of too short clones are coincidental ones. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 ギャップの検出 ギャップなしコードクローン コードクローンの検出 ギャップ検出 連結 ギャップ ギャップト・クローン ソースファイル Source files 指定した長さ以下のギャップ Gap Next in second step, gap locations are identified from non-gapped clones. Gap location is a kind of the combination of the two non-gapped clones. In the detection, we introduce the upper limit of the length of each gap for the practical use. For example, when we define which non-gapped clones should be combined with this one, we suppose this scope whose length is the upper limit in each direction. Then, only non-gapped clones whose head positions are included in this scope are combined. The gaps connected from other non-gapped clones are also identified in that way. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 検出手順 連結 A B C D E F G A B C E F B C D E B C D File Y File X A B C D E F G A B C E F B C D E B C D File Y File X ギャップなしコードクローン コードクローンの検出 ギャップ検出 連結 ギャップ ギャップト・クローン ソースファイル Next in third step, we draw gaps and non-gapped clones. If we plot the detected gap locations on this plot, It becomes like this. We call this scatter plot “gap-and-clone scatter plot” Additionally in this step, we remove non-gapped clones and gaps that don’t contribute to make long gapped clones by using the length of entanglements. In this example, there are these four entanglements. If we remove entanglements that are shorter than 10 tokens, 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

ギャップト・クローンを用いたバージョン比較 void sentence() { if ((tok_name == SIDENTIFIER)|| (tok_name == SREADLN) || (tok_name == SWRITELN) || (tok_name == SBEGIN)) basic_sen(); else if (tok_name == SIF) scan(); if (expression() != TBOOLEAN) error(4); if (tok_name != STHEN) syntax_error(); multi_sentence(); if (tok_name == SELSE) } else if (tok_name == SWHILE) if (tok_name != SDO) syntax_error(); sentence(); else syntax_error(); in Ex.2 int llt,llf,lp,lpf; llt=lt; llf=lf; lp=p; lpf=pf; if ((tok_name == SIDENTIFIER) || (tok_name == SREADLN) || (tok_name == SWRITELN) || fprintf(outfile,"\tPOP\tGR2\t;%d\n",tok_line); fprintf(outfile,"\tCPA\tGR2,TRUE\n",sub); fprintf(outfile,"\tJNZ\tLF%d\n\n",llf); lf++;lt++; fprintf(outfile,"\tJMP\tLT%d\n",llt); fprintf(outfile,"LF%d\n\n",llf); fprintf(outfile,"LT%d\n",llt); fprintf(outfile,"LOOP%d\n",lp); p++; fprintf(outfile,"\tJNZ\tLOOF%d\n\n",lpf); pf++; fprintf(outfile,"\tJMP\tLOOP%d\n",lp); fprintf(outfile,"LOOF%d\n\n",lpf); in Ex.3 A ギャップト・クローンを用いたバージョン比較 in Ex.3 in Ex.1 in Ex. 2 in Ex. 3 in Ex.3 in Ex. 2 in Ex. 1 40 tokens 45 tokens 27 tokens 50 tokens A The minimum size of non-gapped clones: 20 tokens B1 B2 B3 B4 大阪大学のプログラム開発演習で、ある学生が開発したプログラムのバージョンの比較 18 tokens 14 tokens 12 tokens B  The minimum size of non-gapped clones: 10 tokens The maximum size of gaps: 10 tokens The minimum size of entanglements: 20 tokens In this analysis, we compared three versions of only a function “sentence()” in exercise 1, 2 and 3 of a certain student. and examined the actual code portions that are appeared as gapped clones on the gap-and-clone scatter plot. In this figure,. his programs are arranged on both of the vertical and horizontal axes. And, only non-gapped clones that are longer than 20 tokens are appeared. When we refer to the source code corresponding to this non-gapped clone “A”, the non-gapped clone “A” means that just these first halves are clones in each function “sentence()” of exercise 2 and 3 . If user see only this scatter plot or source code, he may think last halves were changed entirely. However, if we refer to the gap-and-clone scatter plot with these thresholds, this gapped clone B is shown up. When we refer to the actual source code corresponding to this gapped clone, we can see last halves of this function were not so changed and these new statements are inserted in extending the programs from exercise 2 to 3, I’m sorry the font size is too small, but these gaps are code portions for outputting assembly language. This gapped clone is precisely what we have expected to observe. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) リファクタリングのサポートへ Geminiによって、コードクローンの分析をする環境はできたけれど 「検出されたコードクローンをどうすればよいのか分からない」 対策をアドバイスできないか ここのコードクローンに対して、適用可能なリファクタリングパターンを提示する 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

リファクタリングサポートツール Ariesのアプローチ 検出したクローンの集約にはリファクタリングパターンを用いる． メソッドの抽出： クローンをメソッドとして抽出 メソッドの引き上げ： クローンを親クラスへ引き上げる 検出したクローンが上記のどちらに適しているか，またはどちらにも適していないのかをメトリクスを用いて判定する． 次に集約方法の提示について説明したいと思います． クローンを集約しようと考えた場合以下の方法が考えられます． これらについては次に説明します． そして，検出したクローンがどちらに適しているのか，またはどちらにも適していないのかをメトリクスを用いて判定します． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) リファクタリングパターン メソッドの抽出 ある部分を新たなメソッドとして抽出するためには，周囲との結合度が低いことが望ましい(抽出部分の外側で定義された変数を用いていないことが望ましい） リファクタリング前 リファクタリング後 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); 抽出したメソッドの呼び出し メソッドの抽出 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

リファクタリングパターン メソッドの引き上げ リファクタリング前 リファクタリング後 コードクローンを含むクラスが同じクラスを継承していなければいけない Employee Employee メソッドの引き上げ getName() Salesman Engineer Salesman Engineer getName() getName() 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

リファクタリングパターンを判定するためのメトリクス（１/２） 以下の２つについて計測する 結合度の計測: クローンの外側で定義された変数の，クローンの内側での使用（代入，参照）数 クローンの分散度の計測: クローンが含まれるクラスがクラス階層においてどのような関係にあるか 解析結果はメトリクスとして数値化する つまり，「メソッドの抽出」と「メソッドの引き上げ」を容易に適用できるクローンを検出するために以下の２つのことがらについて調べます． １つ目が，クローンの外側で定義された変数を内側でいくつ用いているか，で，２つ目がクローンが含まれるクラスがクラス階層においてどのような関係にあるかです． そしてこれらの解析結果はメトリクスとして数値化します． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) メトリクスRVK(S),RVN(S) クローンセットS1にはコード片f1とf2が含まれている． コード片f1内では外部定義の変数a，bをそれぞれ１，２回使用している． コード片f2内では外部定義の変数c，dをそれぞれ３，４回使用している． RVK(S1) : (2 + 2)/2 = ２ RVN(S1) : ((1 + 2) + (3 + 4))/2 = ５ 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) メトリクスDCH(S) クローンセットS2内の全てのコード片が，ある１つのクラス内に存在する場合 DCH(S2) : 0 クローンセットS3内の全てのコード片があるクラスとその子クラス内に存在する場合 DCH(S3) : 1 クローンセットS4内のコード片が含まれるクラスが共通の親を持たない場合 DCH(S4) : -1 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) ツールAries 宣言単位 class宣言，interface宣言 メソッド単位 メソッド本体，コンストラクタ，スタティックイニシャライザ 文単位 do文，for文，if文，switch文，synchronized文，try文，while文 対象言語: Java クローン検出部には既存のコードクローン検出ツールCCFinderを利用 ツールの記述言語： Java 構文，意味解析を行うコンポーネントはオープンソースの構文解析器生成ツールJavaCCを用いて構築 動作環境：JDK1.4以上のVMが実行可能な環境 サイズ 解析部： 約15000行 GUI部： 約8000行 ユーザはGUIを操作することで，コードクローンの絞り込みを行うことができる そして，これらの提案手法を実装したリファクタリング支援ツールを試作しました． 現在のところ，対象言語はJavaのみとなっています． さきほど説明しましたように，クローン検出部にはCCFinderを用いています． ユーザはGUIを操作することで検出したコードクローンの絞込みを行うことができます． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) メトリクスグラフ クローンセットリスト これは，ツールのスナップショットです． この部分はメトリクスグラフと呼ばれるものです，ユーザはこのグラフにおいて各メトリクスの上限・下限を設定することで任意のクローンクラスを選択可能です． また，このパネルでは，ユーザは興味のあるクローンの単位を選択することが可能です． 例えば，メソッドの単位のクローンのみを選択といったことができます． また，このクローンクラスリストには，メトリクスグラフにおいて選択されたクローンクラスの一覧が表示されます． このクローンクラスリストでは，各メトリクス値に基づいてクローンクラスを昇順，降順にソート可能です． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) クローンユニット選択チェックボックス

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードフラグメントリスト クローンクラスリストにおいてクローンを選択すると，このようなウィンドウが立ち上がります． このウィンドウの上部には，このクローンクラスに含まれるコード片の一覧が表示されます． 各コード片について，そのコード片が含まれるファイルへのパス，ファイル内での位置，コード片のトークン数が表示されます． また，左下の部分はソースコードビューです． コードフラグメントリストにおいて選択されたコード片周辺のソースコードが表示されます． クローンになっている部分はハイライトがかかって表示されます． また，右下のリストには，クローンの外部で定義されていて，クローンの内部で使用している変数の一覧が表示されます． 各変数について，種類，変数名，使用回数が表示されます． 2005/03/10 ソースコードビュー 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 使用変数リスト

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 適用実験 概要 Ant (version 1.6.0) 入力 ソースファイル数：　627個 総行数：　約18万行 構造的なクローン検出には約３０秒 １５１個のクローンセットを検出 実験環境 FreeBSD 4.9 CPU Xeon2.8G×２ メモリ ４GB 本日は時間の関係上，Antに対しての適用実験のみについて述べたいと思います． Antとはmakeに代表されるビルドツールの１つであり，Javaで記述されております． ソースコードは627個，総行数は約18万行です． このクローン検出には約30秒かかりました． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 適用実験 Ant（メソッドの抽出） 「メソッドの抽出」を適用するためにクローンを絞り込んだ条件は次の３つ 文単位のクローンである クローンユニット選択チェックボックスで文単位のクローンにチェックを入れる 全てのコード片が１つのクラス内に存在する メトリクスグラフのDCHの上限を1より小さくする． クローンの外部で定義されたローカル変数を高々１つしか使用していない メトリクスグラフのRVKの上限を2より小さくする． １５１個のうちの３２個が該当した 「メソッドの抽出」を適用するために，検出したクローンを以下の条件で絞り込みました． まず，文単位のクローンである，2つ目がすべてのコード片が１つのクラス内に存在する，最後の条件が，クローンの外部で定義されたローカル変数を高々１つしか使用していないです． これらの条件で，151個のクローンを絞り込んだところ，32個のクローンが該当しました． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 適用実験 Ant（メソッドの抽出） ３２個の内訳は以下の通り if (iSaveMenuItem == null) { try {          iSaveMenuItem = new MenuItem();                 iSaveMenuItem.setLabel("Save BuildInfo To Repository"); } catch (Throwable iExc) {                 handleException(iExc);          }  } 変数への代入 // javacopts if (javacopts != null && !javacopts.equals("")) { genicTask.createArg().setValue("-javacopts");         genicTask.createArg().setLine(javacopts);  } ローカル変数 if (!isChecked()) { // make sure we don't have a circular reference here         Stack stk = new Stack();         stk.push(this);         dieOnCircularReference(stk, getProject());  } if (name == null) { if (other.name != null) { return false;         } } else if (!name.equals(other.name)) { return false; } 分類 数 抽出のみ ３個 外部定義の変数を引数として抽出 １８個 引数とした変数を返り値として返す ７個 その他 ４個 32個の内訳は以下の通りです． 単純にクローンになっている部分を抽出するのみで，リファクタリングできたものは３個でした． また，外部定義の変数を，新しく定義するメソッドの引数として抽出したのは，18個でした． さらに，引数とした変数を返り値として返す必要のあったものは7個でした． また，集約にその他の工夫が必要であるものは，４つでした． 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 発表の概略 コードクローンとは コードクローンが引き起こす問題 コードクローンが発生する原因 コードクローンへの対策 われわれのアプローチ コードクローン検出ツールCCFinder Gemini Aries 関連研究 コードクローン検出手法 ツリーのマッチング DP (Dynamic Programming) 特徴メトリクス Simultaneous Editing, Linked Editing Editing Process Patterns コードクローンへの対策マップ コードクローン検出手法マップ 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローン検出手法マップ 神谷 年洋, “コードクローンとは、コードクローンが引き起こす問題、その対策の現状”, 電子情報通信学会誌 Vol. 87, No. 9, pp. 791-797 (2004-9). 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローンの定義 （定義1）ソースコード中に同一あるいは類似したコード断片があるとき、それらをコードクローンという （！「同一あるいは類似」の意味は人に依存する） （定義2）開発者がソースコードをコピー＆ペーストしたとき、コピーとオリジナルはコードクローンである （！それ以外の理由によって発生した類似部分はコードクローンではない） （定義3）２つのソフトウェア部品が、ある基準によって同じであると判定されるとき、それらはコードクローンである （！人間の判断と、その基準がどれだけ一致するか） 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 関連研究 CloneDR コードクローン検出＋除去ツール CloneDR ASTの部分木の比較 ソースコードの自動的な修正 特徴 検出されるものはマージ可能なコードクローン 検出時間はO(n^2) n:ASTのノード数 I.D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier, “Clone Detection Using Abstract Syntax Trees,” Proc. IEEE International Conference on Software Maintenance (ICSM) ’98, pp. 368-377, Bethesda, Maryland, Nov. 1998. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

CloneDRのコードクローン検出アルゴリズム (1) ソースコードをパースして、ASTを作成 (2) ハッシュ値によるコードクローン検出 ASTの各ノードのハッシュ値を計算 ハッシュ値が同じノードはコードクローン (3) 含んでいるトークンの共通度によるコードクローン検出 それぞれのノードを根とする部分木に含まれるトークンの種類の類似度を計算 類似度がしきい値以上ならコードクローン void f() { x = 0; a = 1; b = 2; c = 3; w = 4; } void g() y = 2; i = 5; x = ; a 1 b 2 c 3 w 4 y i 5 ; = 0 1 a x ; = 1 2 a y 4/8 6/9 8/11 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) CloneDR(続き) 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 関連研究 Balazinska コードクローン検出ツール DP+特徴メトリクス 検出アルゴリズム (1)メソッドを特徴メトリクスによって比較し、類似しているメソッドをコードクローンの候補とする (2)候補となったメソッドをDPによってさらに比較し、類似しているものをコードクローンとする M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe, 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. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 特徴メトリクス コードのブロックや関数を対象として、以下のメトリクスを計測する 利用されているグローバル変数の数 呼ばれている関数の数 引数や戻り値の数 McCabeのサイクロマチック数 Balazinskaらの研究ではメトリクスの計測値が±１の範囲で一致するものをコードクローンとして検出している （！小さなコード断片については計測できない） （！ソースコードの小さな修正が、メトリクス値の大きな違いを生むことがある） 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

動的計画法（Dynamic Programming） Diffのアルゴリズム 与えられた２つの文字列のedit distanceを計算する ギャップト・クローンを検出することができる 計算時間はO(mn) (m, n : length of sequences) 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) Linked Editing (1)コードクローンを検出する (2)開発者が、コードクローンのコード断片の間に「リンク」を設定する (3)リンクが設定されたコード断片への編集は、他のコード断片へも反映される （４）ファイルを保存するときは、リンク情報も同時に保存する Michael Toomim, Andrew Begel, Susan L. Graham, “Managing Duplicated Code with Linked Editing”, Proc. IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC'04) pp. 173-180 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

Editing Process Patterns テキストエディタのコピー＆ペースト作業を記録する Support for Programmer Observation Support for C&P Programming Support for Program Understanding Support for Programming by Demonstration Miryung Kim, Vibha Sazawal, and David Notkin, “Supporting Uses of Editing Process Patterns”, Workshop on Behavior Based User Interface Customization,Intelligent User Interface, Jan 13-16, 2004 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) [1] S.F. Altschul, W. Gish, W. Miller, E. Myers, D. Lipman, “Basic Local Alignment Tool,” Journal of Molecular Biology, 215, pp. 403-410, (1990). [2] A. Aiken, “A System for Detecting Software Plagiarism (Moss Homepage)”, http://www.cs.berkeley.edu/~aiken/moss.html [Last visited 1st Feb. 2003]. [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,” Proc. IEEE Working Conf. on Reverse Engineering, pp. 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] M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe, 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. [7] M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe, and K.A. Kontogiannis, “Partial Redesign of Java Software Systems Based on Clone Analysis,” Proc. 6th IEEE Working Conference on Reverse Engineering (WCRE ’99), pp. 326-336, Atlanta, Georgia, Oct. 1999. [8] I.D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier, “Clone Detection Using Abstract Syntax Trees,” Proc. IEEE International Conference on Software Maintenance (ICSM) ’98, pp. 368-377, Bethesda, Maryland, Nov. 1998. [9] K.W., Church, and J.I. Helfman, “Dotplot: A Program for Exploring Self-Similarity in Millions of Lines of Text and Code,” Journal of Computational and Graphical Statistics, V2, N2, pp. 153-174 (1993). [10] James O. Coplien, Multi-Paradigm Design for C++, Pearson Education (2001). ジェームス・O・コプリン(著), 金沢 典子, 平鍋 健児, 羽生田 栄一(訳), マルチパラダイムデザイン, ピアソン・エデュケーション (2001). [11] Elizabeth Burd, John Bailey, “Evaluating Clone Detection Tools for Use during Preventative Maintenance,” Proc. 2nd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM) 2002, pp. 36-43. Montreal, Canada, Oct. 2002. [12] S. Ducasse, M. Rieger, and S. Demeyer, “A Language Independent Approach for Detecting Duplicated Code,” Proc. IEEE International Conference on Software Maintenance (ICSM) ’99, pp. 109-118. Oxford, England. Aug. 1999. [13] M. Fowler, Refactoring: improving the design of existing code, Addison Wesley, 1999. [14] FreeBSD. http://www.freebsd.org/. [15] D. Gusfield, Algorithms on Strings, Trees, and Sequences, pp. 89-180. Cambridge University Press, 1997. [16] T. Imai, Y. Kataoka, and T. Fukaya, “Evaluating Software Maintenance Cost Using Functional Redundancy Metrics,” Proc. 26th International Computer Software and Applications Conference (Compsac 2002), pp.299-306, 2002. [17] J.H. Johnson, “Identifying Redundancy in Source Code Using Fingerprints,” Proc. IBM Centre for Advanced Studies Conference (CAS CON) ‘93, pp. 171-183, Toronto, Ontario. Oct. 1993. [18] J.H. Johnson, “Substring Matching for Clone Detection and Change Tracking,” Proc. IEEE Int’l Conf. on Software Maintenance (ICSM) ’94, pp. 120-126. Victoria, British Columbia, Canada. Sep. 1994. 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) [19] J.H. Johnson, “Using Textual Redundancy to Understand Change,” Proc. IBM Centre for Advanced Studies Conference (CASCON) '95, pp. 34-40, Nov. 1999. [20] 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, vol. 28, no. 7, pp. 654-670, (2002-7). [21] 金久 實 (編), ヒューマンゲノム計画, 共立出版 (1997). [22] R. Komondoor and S. Horwitz, “Using Slicing to Identify Duplication in Source Code,” Proc. of the 8th International Symposium on Static Analysis(SAS), LNCS 2126, pp. 40-56, Springer (2001). [23] K.A. Kontogiannis, R. De Mori, E. Merlo, M. Galler, and M. Bernstein, “Pattern Matching Techniques for Clone Detection and Concept Detection,” Journal of Automated Software Engineering Kluwer Academic Publishers, vol. 3, pp. 770-108, 1996. [24] Jens Krinke, “Identifying Similar Code with Program Dependence Graphs,” Proc. of the 8th Working Conference on Reverse Engineering, 2001. [25] B. Laguë, E.M. Merlo, J. Mayrand, and J. Hudepohl, “Assessing the Benefits of Incorporating Function Clone Detection in a Development Process,” Proc. IEEE Int’l Conf. on Software Maintenance (ICSM) ’97, pp. 314-321, Bari, Italy. Oct. 1997. [26] Linux Online. http://www.linux.org/. [27] A. Marcus, and J.I., Maletic, “Identification of High-Level Concept Clones in Source Code,” Proc. Automated Software Engineering (ASE'01), San Diego, pp. 107-114, Nov. 2001, [28] J. Mayrand, C. Leblanc, and E. M. Merlo, “Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics,” Proc. IEEE Int’l Conference on Software Maintenance (ICSM) ’96, pp. 244-253, Monterey, California, Nov. 1996. [29] 門田 暁人, 佐藤 慎一, 神谷 年洋, 松本 健一, “コードクローンに基づくレガシーソフトウェアの品質の分析,” 情報処理学会論文誌, vol. 44, No. 8, pp. 2178-2188 (2003-8). [30] NetBSD Project. http://www.netbsd.org/. [31] 大駒 誠一, COBOL入門 改訂版, 培風館 (1986). [32] L. Prechelt, G. Malpohl, M. Philippsen, “JPlag: Finding Plagiarisms Among a Set of Programs,” Technical Report, University of Karlsruhe, Department of Informatics, 2000. [33] 田中 哲, “データマイニングを利用したプログラムの改善,” 日本ソフトウェア科学会 第7回プログラミングおよび応用のシステムに関するワークショップ(SPA 2004), pp. 1-8, (2004-3). [34] Will Tracz, Confessions of a Used Program Salesman --- Institutionalizing Software Reuse ---, Pearson Education (1995). W. トレイツ (著), 畑崎 隆雄, 林 雅弘, 鈴木 博之 (訳), ソフトウェア再利用の神話 --- ソフトウェア再利用の制度化に向けて ---, ピアソン・エデュケーション (2001). [35] 山本 哲男, 松下 誠, 神谷 年洋, 井上 克郎, “ソフトウェアシステムの類似度とその計測ツールSMMT,” 電子情報通信学会論文誌, vol. J85-D-I, no. 6, pp. 503-511. (2002-6). [36] 植田 泰士, 神谷 年洋, 楠本 真二, 井上 克郎, “開発保守支援を目指したコードクローン分析環境,” 電子情報通信学会論文誌 D-I, Vol. J86-D-I, No. 12, pp. 863-871 (2003-12). 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005) コードクローン検出手法応用マップ 部品化 Code Decayの評価 コードクローンの検出 コードクローンの 除去 剽窃検出 ソースコード 修正前のチェック 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)

（参考）コードクローンを用いたソースコード評価・比較 コードクローンによる評価 クローンをまとめることにより削減できるソースコードの割合[1] 機能が重複して実装されている割合、回数[6] クローンの分布 クローンが多く含まれるモジュール？ クローンクラス(同値類)の広がり フォールトとクローンの統計的な関係？ コードクローンによる比較 プロダクト間・バージョン間の類似度 2005/03/10 第7回プログラミングおよびプログラミング言語ワークショップ(PPL2005)