ギャップを含むコードクローンの フィルタリング手法の提案 井上研究室 博士前期過程2年 宮崎 宏海 2018/11/21

研究概要 既存の手法で検出したギャップを含むコードクローンを調査 基準を定めてギャップを含むコードクローンを分類 見る必要のない不要なものをフィルタリング 　　コードクローン分析の効率化を図る

発表の流れ 背景 既存手法による実験 提案手法 実験 まとめと今後の課題

発表の流れ 背景 既存手法による実験 提案手法 実験 まとめと今後の課題

コードクローンとは ソースコード中のコード片で同一または類似するコード片を持つもの クローンペア：互いにクローンとなっているコード片の対 主な出現要因：コピー＆ペースト 弊害：保守コストの増加 クローンペア：互いにクローンとなっているコード片の対 クローンセット：互いにクローンとなっているコード片の集合 クローンペア クローンセット （C1,C3） （C1,C4） （C3,C4） ｛C1,C3,C4｝ （C2,C5） ｛C2,C5｝ C4 C1 C2 C5 C3

コードクローンのタイプ 識別子名の変更 Exactクローン 空白などのコーディングスタイルを除いて 完全に一致するコードクローン if(a = =b){ a = a + 1; b = b*3;} コピー&ペーストによる 再利用 if(a = =b){ a = a + 1; b = b*3;} 識別子名の変更 文の挿入 文の削除 文の変更 Exactクローン 空白などのコーディングスタイルを除いて 完全に一致するコードクローン if(i = =j){ i = i + 1; j = j*3;} if(a == b){ b = b – 2; a = a + 1; b = b*3;} if(a = =b){ b = b*3;} if(a == b){ a ++; b = b*3;} Parameterizedクローン ユーザ定義名や一部の予約語が異なるコードクローン Gappedクローン 文単位でギャップを含むコードクローン

Gappedクローンの検出について Gappedクローンを検出できる手法は少ない AGMアルゴリズムを用いた検出手法の問題点 *藤野 陽平，TechnicalReport “グラフマイニングアルゴリズムを用いたギャップを含むクローン抽出手法の提案” *肥後 芳樹, 植田 泰士, 楠本 真二, 井上 克郎 “AGMアルゴリズムを用いたギャップを含むコードクローン情報の生成”

AGMアルゴリズムを用いた検出の流れ 1 2 3 4 1 3 4 1 1 2 3 3 4 4 1 3 1 4 3 4 1 3 4 AGMアルゴリズムの適用 （2回以上出現するグラフパターンを検出． ただし，検出されるグラフは分岐と閉路を 含まない）

Gappedクローンの検出について Gappedクローンを検出できる手法は少ない AGMアルゴリズムを用いた検出手法の問題点 *藤野 陽平，TechnicalReport “グラフマイニングアルゴリズムを用いたギャップを含むクローン抽出手法の提案” *肥後 芳樹, 植田 泰士, 楠本 真二, 井上 克郎 “AGMアルゴリズムを用いたギャップを含むコードクローン情報の生成”

発表の流れ 背景 既存手法による実験 提案手法 実験 まとめと今後の課題

調査内容 コードクローン検出ツール 検出したGappedクローンの中で不要なものの数を調べる 対象 CCFinder* Ant 1.7.1 JHotDraw 7.0.9 JDK 1.5.0 コードクローン検出ツール CCFinder* *Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue, "CCFinder: A Multi-Linguistic Token-based Code Clone Detection System for Large Scale Source Code," IEEE Trans. Software Engineering, vol. 28, no. 7, pp. 654-670

不要なGappedクローンの基準 構成するコード片が複数の関数にまたがっている 関数は記述の順序によって処理に影響がない 同型のGappedクローンのインスタンスがオーバーラップしている コピー&ペーストで生成された可能性が低い Gappedクローンが繰り返し構造を持っている ソフトウェア開発や保守の観点から調査の対象にする必要がない 上記の条件を満たすGappedクローンはコードクローン分析を行う上で不要 いずれの条件も満たさないGappedクローンを有用とする

複数の関数にまたがっているGappedクローン public final synchronized Iterator iterator() { if (isReference()) { return ((BaseResourceCollectionContainer) getCheckedRef()).iterator(); } dieOnCircularReference(); return new FailFast(this, cacheCollection().iterator()); /** * Fulfill the ResourceCollection contract. * @return number of elements as int. */ public synchronized int size() { getCheckedRef()).size(); return cacheCollection().size(); /** * Fulfill the ResourceCollection contract. * @return number of elements as int. */ public synchronized int size() { if (isReference()) { return ((BaseResourceCollectionContainer) getCheckedRef()).size(); } dieOnCircularReference(); return cacheCollection().size(); public final synchronized Iterator iterator() { getCheckedRef()).iterator(); return new FailFast(this, cacheCollection().iterator()); A B A 関数の順番を 変更 B A B 関数の順番で 生成されるグラフが違う B A 13

不要なGappedクローンの基準 構成するコード片が複数の関数にまたがっている 関数は記述の順序によって処理に影響がない 同型のGappedクローンのインスタンスがオーバーラップしている コピー&ペーストで生成された可能性が低い Gappedクローンが繰り返し構造を持っている ソフトウェア開発や保守の観点から調査の対象にする必要がない 上記の条件を満たすGappedクローンはコードクローン分析を行う上で不要 いずれの条件も満たさないGappedクローンを有用とする

インスタンスがオーバーラップするGappedクローン } else if (family.equals(FAMILY_OS2)) { isFamily = OS_NAME.indexOf(FAMILY_OS2) > -1; } else if (family.equals(FAMILY_NETWARE)) { isFamily = OS_NAME.indexOf(FAMILY_NETWARE) > -1; } else if (family.equals(FAMILY_DOS)) { isFamily = PATH_SEP.equals(";") && !isFamily(FAMILY_NETWARE); } else if (family.equals(FAMILY_MAC)) { isFamily = OS_NAME.indexOf(FAMILY_MAC) > -1; } else if (family.equals(FAMILY_TANDEM)) { isFamily = OS_NAME.indexOf("nonstop_kernel") > -1; } else if (family.equals(FAMILY_UNIX)) { isFamily = PATH_SEP.equals(":") && !isFamily(FAMILY_VMS) && (!isFamily(FAMILY_MAC) || OS_NAME.endsWith("x")); } else if (family.equals(FAMILY_ZOS)) { isFamily = OS_NAME.indexOf(FAMILY_ZOS) > -1 || OS_NAME.indexOf("os/390") > -1; } else if (family.equals(FAMILY_OS400)) { isFamily = OS_NAME.indexOf(FAMILY_OS400) > -1; } else if (family.equals(FAMILY_VMS)) { isFamily = OS_NAME.indexOf(FAMILY_VMS) > -1; } else { throw new BuildException( 1 G Gappedクローン G1の不一致部分 2 G Gappedクローン G2の不一致部分 G1とG2はクローンペア コピーアンドペーストで生成された可能性は低い

不要なGappedクローンの基準 構成するコード片が複数の関数にまたがっている 関数は記述の順序によって処理に影響がない 同型のGappedクローンのインスタンスがオーバーラップしている コピー&ペーストで生成された可能性が低い Gappedクローンが繰り返し構造を持っている ソフトウェア開発や保守の観点から調査の対象にする必要がない 上記の条件を満たすGappedクローンはコードクローン分析を行う上で不要 いずれの条件も満たさないGappedクローンを有用とする

繰り返し構造を持つGappedクローン g.drawLine(8,1, 1,8); // left edge of roof g.drawLine(8,1, 15,8); // right edge of roof g.drawLine(11,2, 11,3); // left edge of chimney g.drawLine(12,2, 12,4); // right edge of chimney g.drawLine(3,7, 3,15); // left edge of house g.drawLine(13,7, 13,15); // right edge of house g.drawLine(4,15, 12,15); // bottom edge of house // Draw door frame // same color as edge of house g.drawLine( 6,9, 6,14); // left g.drawLine(10,9, 10,14); // right g.drawLine( 7,9, 9, 9); // top // Draw roof body g.setColor(MetalLookAndFeel.getControlDarkShadow()); g.fillRect(8,2, 1,1); //top toward bottom g.fillRect(7,3, 3,1); g.fillRect(6,4, 5,1); g.fillRect(5,5, 7,1); g.fillRect(4,6, 9,2); // Draw doornob // same color as roof body g.drawLine(9,12, 9,12); 不一致部分

不要なGappedクローンの基準 不要なGappedクローンの基準 構成するコード片が複数の関数にまたがっている 関数は記述の順序によって処理に影響がない 同型のGappedクローンのインスタンスがオーバーラップしている コピー&ペーストで生成された可能性が低い Gappedクローンが繰り返し構造を持っている ソフトウェア開発や保守の観点から調査の対象にする必要がない 上記の条件を満たすGappedクローンはコードクローン分析を行う上で不要 いずれの条件も満たさないGappedクローンを有用とする

実験データ ソフトウェア 664 369 （55.6%） 455 （68.5%） 393 （59.2%） 54 （8.1%） 599 281 合計 複数関数 オーバーラップ 繰り返し構造 有用 Ant 664 369 （55.6%） 455 （68.5%） 393 （59.2%） 54 （8.1%） JHotDraw 599 281 （46.9%） 427 （71.3%） 400 （66.8%） 61 （10.2%） JDK 15,433 8.204 （52.5%） 11,444 （74.2%） 11,764 （76.2%） 929 （6.0%） 検出されたGappedクローンのクローンセット数 複数の基準に当てはまるものも存在する

発表の流れ 背景 既存手法による実験 提案手法 実験 まとめと今後の課題

使用するノードやノード間のエッジを少なくすることで 提案手法 グラフ構築時に各基準に当てはまるGappedクローンをフィルタリング 複数関数にまたがるGappedクローンのフィルタリング 異なる関数に含まれるコード片に対応するノード間にエッジを引かない インスタンスがオーバーラップするGappedクローンのフィルタリング 同一のIDを持つコード片に対応するノード間にエッジを引かない 繰り返し構造を持つGappedクローンのフィルタリング 繰り返し構造を持つコード片をノードとして用いない 使用するノードやノード間のエッジを少なくすることで グラフの構築を効率的に行う

フィルタリング（複数関数） 1 2 3 4 フィルタリング する 1 4 3 2 関数A 関数B 1 2 3 4 フィルタリング しない

フィルタリング（オーバーラップ） 1 2 フィルタリング する 1 2 1 2 1 フィルタリング しない

発表の流れ 背景 既存手法による実験 提案手法 実験 まとめと今後の課題

適用実験 目的 対象 コードクローン検出に使用するツール 実験環境 フィルタリング手法の有効性を確認 Ant 1.7.1 JHotDraw 7.0.9 JDK 1.5.0 コードクローン検出に使用するツール CCFinder 実験環境 CPU：Pentium4 3.20 GHｚ メモリ：2GB OS：Windows Vista

実験の評価 フィルタリング手法の有効性の評価 フィルタリングする場合としない場合を比較 フィルタリング後のGappedクローンを調査

フィルタリングの有無の比較 Gappedクローン数 検出時間（s） ソフトウェア フィルタリング無 フィルタリング有 Ant 650 78 20 53 JHotDraw 598 90 5 33 JDK 15,433 1,020 11,221 887

フィルタリング後に取得したGappedクローン for (int i = 0; i < dirs.length; i++) { File d = new File(dirs[i]); if (!d.exists()) { if (!d.mkdirs()) { log("Unable to create directory " + d.getAbsolutePath(), Project.MSG_ERR); } else { createCount++; } if (createCount > 0) { log("Copied " + dirCopyMap.size() + " empty director“ + (dirCopyMap.size() == 1 ? "y" : "ies") + " to " + createCount + (createCount == 1 ? "y" : "ies") + " under “ + destDir.getAbsolutePath()); ・・・ } File d = new File(toDirNames[i]); if (!d.exists()) { if (!d.mkdirs()) { log("Unable to create directory " + d.getAbsolutePath(), Project.MSG_ERR); } else { createCount++; File fromDir = new File(fromDirName); if (!selfMove && okToDelete(fromDir)) { deleteDir(fromDir); if (createCount > 0) { log("Moved " + dirCopyMap.size() + " empty director" + (dirCopyMap.size() == 1 ? "y" : "ies") + " to " + createCount + (createCount == 1 ? "y" : "ies") + " under " + destDir.getAbsolutePath()); ・・・ ファイルの コピー処理 不一致部分 ログ出力 Copy.java Move.java

考察 Gappedクローンの数を大幅に削減 大規模なソフトウェアに対して検出時間を大幅に削減 →提案手法は有効である 今後の課題 フィルタリング後のGappedクローンの中にコード片間が等しいものが含まれていた コード片間が等しい場合，Gappedクローンとしてではなく1つのコードクローンとして検出されるべき

発表の流れ 背景 既存手法による実験 提案手法 実験 まとめと今後の課題 まとめます

まとめと今後の課題 AGMアルゴリズムにより取得したGappedクローンを基準を定めて有用か判断し，フィルタリングを行った グラフの構築手法を新たに設定 複数のオープンソースソフトウェアに適用 フィルタリングの有効性を確認 今後の課題 コード片間が等しいGappedクローンのフィルタリング その他のコードクローン検出手法へAGMアルゴリズムの適用

各ソフトウェアのサイズ ソフトウェア バージョン 記述言語 ファイル数 総行数 Ant 1.7.1 Java 787 200,401 JHotDraw 7.0.9 471 90,241 JDK 1.5.0 6,551 1,887,008