アイテムセットマイニングを利用した コードクローン分析作業の効率向上

Presentation on theme: "アイテムセットマイニングを利用した コードクローン分析作業の効率向上"— Presentation transcript:

1 アイテムセットマイニングを利用した コードクローン分析作業の効率向上
大阪大学大学院情報科学研究科 M2 　宮崎　宏海

2 概要 コードクローン分析技術をより効率的に行える手法を提案
コードクローンの散布図では，個々のコードクローンに対して調査をする際はどこから見ていけば良いか分からない

3 コードクローンとは ソースコード中に出現する同一または類似するコード片 コードクローンの弊害 主な出現要因
コピー＆ペースト 定型的な処理（ファイルオープン，データベース処理など） コードクローンの弊害 コードクローン部分に修正を加える場合，全てのコード片に対して修正を検討する必要がある コピーアンドペースト コードクローン

4 コードクローンに関するこれまでの研究 コードクローンに対する支援ツール CCFinder[1] コードクローン検出ツール
トークン単位でコードクローンを検出 多種のプログラミング言語(C, C++. Java, etc..)に対応 解析結果はテキスト形式で出力 [1] T. Kamiya, S. Kusumoto, K. Inoue : “CCFinder : A multi-linguistic token-based code clone detection system for large scale source code” , IEEE Transactions on Software Engineering, 28(7), pp , July 2002. [2] Y. Ueda, T. Kamiya, S. Kusumoto and K. Inoue, “Gemini: Maintenance Support Environment Based on Code Clone Analysis”, Proc. Of the 8th IEEE International Symposium on Software Metrics, 67-76, 2002.

5 クローンペアとクローンセット クローンペア：互いにクローンとなっているコード片の対 クローンセット：互いにクローンとなっているコード片の集合
類似したコード片 クローンペア クローンセット （C1,C3） ｛C1,C3,C4｝ （C1,C4） ｛C2,C5｝ （C3,C4） （C2,C5） C1 C3 C2 C4 C5 類似したコード片

6 散布図 定義 対象とするソースコードの集合に含まれるコードクローンの散布状況を表す
左上を始点として水平方向・垂直方向にソースコードのトークンを出現順に配置 水平方向・垂直方向のトークンが一定数以上連続して一致する箇所に点をつける a b c a b c c c a b a b c a b c c c 長さが2以上で線分を引いていることを言う！ 図はあるファイルについての例 a b a, b, c, ... : トークン : トークンが一致した箇所

7 散布図の利点と問題点 利点 問題点 システムのどこにコードクローンが含まれているかを瞬時に把握できる
個々のコードクローンを調査する場合に，どのコードクローンから調査すればいいか分かり辛い コードクローンが固まっている部分に分析すべきものがあるとは限らない

8 研究の目的とアプローチ 目的 アプローチ 個々のコードクローンを分析する際に，散布図上にどのコードクローンから調査するべきかを表示する
コードクローンの出現パターンを抽出する 同じクローンセットに属するコードクローンは類似した機能を持つ 複数のコードクローンを共有するファイルは類似度が高いと考えられる 類似度が高いファイルを見つけるのはなぜか？ －処理内容(機能)が類似したファイルは，処理の流れにも類似したところがあるのでは ないかと考えており，その情報を用いれば，コードクローンでない箇所に修正を加えた 場合に同時に見るべきファイルと出来るかもしれない．また，同様にコードクローンで ある箇所に修正を加えた場合に，コードクローンでない箇所に与える影響にも類似して いるかもしれない

9 出現パターンの抽出 個々のコードクローンではなく，その出現パターンを見ることでより巨視的な視点による分析が可能
ファイル2 ファイル4 ファイル6 a b c d a b c a b c d e f フ ァ イ ル 5 フ ァ イ ル 1 フ ァ イ ル 3 ファイル1～4同士の類似度は， ファイル1～4とファイル5，6の類似度より高いと考えられる

10 *：対象とするプロジェクトに一定回数以上出現するパターン
提案手法 CCFinderから得たコードクローン情報から各ファイルに含まれるコードクローンの出現パターンを求める 手法の手順 コードクローンを検出する コードクローン情報をもとに，FP-tree[3]を作成する コードクローンの頻出パターン*を求める *：対象とするプロジェクトに一定回数以上出現するパターン [3] J. Han, J. Pei and Y. Yin ”Mining Frequent Patterns without Candidate Generation” In Proc. of the ACM SIGMOD Conference on Management of Data,pp.1-12, 2000.

11 パターンに含まれるクローンの個数が2個以上の場合 パターンに含まれるクローンの個数が2個以上の場合
クローンパターン コードクローンの出現パターンを以降では「クローンパターン」と呼称 C6 C8 C7 定義 構成要素はクローンセットID 構成するクローンセットに属するコードクローンが，全て同じファイルに存在 クローンパターンの特徴 コードクローンの出現する順番は考慮しない パターンは複数のファイルに含まれる C1 C4 C2 C5 C3 ファイル2 ファイル1 ファイル3 ：CS1（クローンセット1）に属する 　コードクローン ：CS2（クローンセット2）に属する 　コードクローン パターンに含まれるクローンの個数が2個以上の場合 F1 [CS1,CS1] [CS1,CS2] [CS1,CS1,CS2] F2 [CS1,CS2] F3 [CS1,CS1] [CS1,CS2] [CS1,CS1,CS2] パターンに含まれるクローンの個数が2個以上の場合

12 1．コードクローンの検出 既存のコードクローン検出ツールを使用 クローンセット情報の構築
クローンパターンを構成する要素がクローンセットIDであるため コードクローンが属するクローンセットIDと，コードクローンを含むファイルとの対応付け

13 例：パターンを含むファイルの個数の最小値を3個とした場合
2．FP-treeの作成（1/2） 頻出クローンセットIDを取得 パターンを含むファイルの数の閾値を設定 閾値以上の個数のファイルに含まれるクローンセットをファイルの個数と共に保持 各ファイルについて，含む頻出クローンセットIDを総出現回数の降順でソート 総出現回数 ファイルID 1 2 3 4 5 クローンセットID a, b, c, d a, b, e, f c, d a, b, c, e a, b, c, e, f 頻出クローンセットID 閾値以上 閾値未満 a, b, c （a : 4個） （b : 4個） （c : 4個） （e : 3個） （d : 2個） （f : 2個） a, b, e c a, b, c, e a, b, c, e 例：パターンを含むファイルの個数の最小値を3個とした場合

14 2．FP-treeの作成（2/2） FP-treeを構築 FP-treeの特徴 木構造 各ノードではクローンセットIDとカウントを保持
各ノードからrootまでの経路上にあるノードが保持するクローンセットの組み合わせが，カウントの数だけ同一ファイル内に出現 前頁の表のFP-tree root c:1 a:4 b:4 c:3 e:1 e:2 { c } が1つのファイルに 含まれていることが分かる { a，b，c } が同時に3つのファイルに 含まれていることが分かる

15 前頁のFP-treeからcを含むパターンを見つける場合
3．頻出パターンの取得（1/2） FPーtreeから頻出パターンを取得 クローンセットID＝cを含む頻出パターンの取得手順 cを保持するノードのカウントと，rootまでの経路上のノードが保持するクローンセットIDを調べる cを含む全てのファイルについて1.の情報を調べ，統合する 2.の情報とパターンを含むファイル数の閾値から頻出パターンを求める a:4 a, b, cが同時に 3つのファイルに 現れる a, b, cが同時に3つのファイルに， cが4つのファイルに同時に現れる 頻出パターン ｛a, b, c｝ ｛c｝ b:4 cが1つの ファイルに現れる c:3 c:1 前頁のFP-treeからcを含むパターンを見つける場合

16 パターン間でクローンセットIDが包含関係になる例
3．頻出パターンの取得（2/2） 不要なパターンを除去 不要なパターンの条件 2つのパターンが同じファイルに含まれる パターンを構成するクローンセットIDが包含関係になっている 包含されているパターンを除去する 包含しているパターンに比べて，新たに得られる情報がないため ファイルID f1, f2, f3, f4 頻出パターンID 1 2 クローンセットID a, b, c, d a, b, c パターン間でクローンセットIDが包含関係になる例

17 実験の概要 実験の目的 実験の条件 JHotDraw（バージョン5.4）に適用
コードクローンの頻出パターンがコードクローン分析に有用かを調べる 実験の条件 コードクローン検出ツール：CCFinder パターンを構成するクローンセット数の最小値：2 パターンを含むファイル数の最小値：2 JHotDraw（バージョン5.4）に適用 ファイル数：484個（71736行） 検出したコードクローン：1604個 検出したクローンセット：323個 取得したパターン：40個

18 コードクローン分析に有用であるかの判断基準
パターンを構成するコードクローンがファイルの特徴を表しているか パターンを含むファイルが，コードクローンを含むファイルに比べて絞り込めているか CS1を含むファイルの集合F1 CS2を含むファイルの集合F2 パターンがファイルの特徴を表しているか －適切に表していれば，ファイルの類似度が高いといえる パターンを含むファイルが絞り込まれているか －単一のコードクローンからは得られない，特定の機能を持ったファイルの集合を取得できる － CS3を含むファイルの集合F3 パターンを含むファイルの集合F 全てのファイル 絞り込めている 絞り込めていない パターン｛CS1, CS2, CS3｝の場合

19 取得した頻出パターンの例（1/2） ：クローンペアになっているコード片 SendToBackCommand.java
31　public void execute() { 32　　　　super.execute(); 33　　　　setUndoActivity(createUndoActivity()); 34　　　　getUndoActivity().setAffectedFigures( 35　 view().selectionZOrdered()); 36　　　　FigureEnumeration fe = 37　 　　　　　getUndoActivity().getAffectedFigures(); 38　　　　while (fe.hasNextFigure()) { 39　 　view(). drawing( 64　public boolean undo() { 65　　　　if (!super.undo()) { 66　 return false; 67　　　　} 　　FigureEnumeration fe = 　　　　　　　getAffectedFigures(); 70　　　while (fe.hasNextFigure()) { 71 　　　　Figure currentFigure = 72 　　　　　　　　fe.nextFigure(); 43　public void execute() { 44　　　　super.execute(); 45　　　　setUndoActivity(createUndoActivity()); 46　　　　getUndoActivity().setAffectedFigures( 47 view().selection()); 48　　　　FigureEnumeration fe = 49 getUndoActivity().getAffectedFigures(); 50　　　　while (fe.hasNextFigure()) { 51 fe. nextFigure( 79　public boolean undo() { 80　　　if (!super.undo()) { 81 return false; 82　　　} 　　FigureEnumeration fe = 　　　　　　　　　getAffectedFigures(); 85　　　while (fe.hasNextFigure()) { 86 Figure f = fe.nextFigure(); SendToBackCommand.java ChangeAttributeCommand.java ：クローンペアになっているコード片

20 取得した頻出パターンの例（2/2） パターンを構成するコードクローン パターンを含むファイル 頻出パターンが持つ情報
メソッドexecute()：複数の図形を対象としたコマンドの実行を記述 メソッドundo()：そのファイルが記述するコマンドの取り消し処理を記述 パターンを含むファイル ChangeAttributeCommand.java SendToBackCommand.java 頻出パターンが持つ情報 複数の図形を対象としたコマンドを実行 そのコマンドを取り消す

21 execute()メソッドを持つが，複数の図形を対象としたものではない
ファイルの絞り込みを行ったパターン JHotDrawから取得したパターン40個中6個 具体例 前述の頻出パターン execute()の一部を含むファイル BringToFrontCommand.java ChangeAttributeCommand.java SendToBackCommand.java undo()の一部を含むファイル AlignCommand.java ConnectedTextTool.java UndoActivityクラスを持つが undo()メソッドの記述はない execute()メソッドを持つが，複数の図形を対象としたものではない execute()メソッドを持たない

22 考察 単一のコードクローンからは得られない情報を取得 取得した頻出パターンを含むファイルと類似した機能を持つファイルが存在
ファイルが持つ機能を表すパターン ファイルの絞り込みが出来たパターン 特定の機能を持つファイルに分類できた 取得した頻出パターンを含むファイルと類似した機能を持つファイルが存在 パターンを含むべきファイルの検出漏れ

23 まとめと今後の課題 まとめ 今後の課題 散布図上で効率的なクローン調査が可能となる手法を提案
JHotDrawに対して実験を行い，取得したパターンがコードクローン分析に有用であるか判断した 今後の課題 散布図への情報の付加 パターンを構成する要素の検討 CCFinderで検出するコードクローンの最小トークン数を変更 評価基準の検討