Significant Duplication 検出実装

若松俊介

Significant Duplication

コードの重複の中で特に影響の大きいもの。
共通化するべき部分が共通化されていない場合などに発生する。

  • できる限り大きいまとまり
  • 十分大きい

Size of Exact Clone

コードの重複の大きさ。
重複が十分大きいかの判定で使用。

条件

  • 重複単体の場合
    • SEC>AVERAGE(LOC/operation)SEC > AVERAGE(LOC/operation)
    • AVERAGE(LOC/operation)AVERAGE(LOC/operation)は手動設定
  • 複数の重複のまとまりの場合
    • SEC>FEWSEC > FEW

Line Bias

コードの重複間の距離。
重複が1つの塊かの判定で使用。

条件

  • LBFEWLB \leq FEW

Size of Duplication Chain

重複の塊の大きさ。
コードの塊が十分大きいかの判定で使用。

条件

  • SDC2×(FEW+1)+1SDC \geq 2\times(FEW+1)+1
    • 各重複がFEWFEWより長い
    • 重複間の隙間分として+1+1

コードの重複検出

メトリクスの取り出しの前処理。
ASTを元にSuffix Treeを構築する手法を使用。

  1. AST構築
  2. AST→ノードの列
  3. ノードの列→Suffix Tree
  4. Suffix Tree→ノード列の重複
  5. ノード列の重複→コードの重複

AST→ノードの列

ポーランド記法のイメージ。
各ノードに子ノード数を紐づけるのがポイント。

Suffix Tree

接尾辞(文字列の最後NN文字)を木構造にしたもの。
文字数NNとして時間計算量O(N)O(N)で構築可能。
例)banana

Suffix Tree→コードの重複

Suffix Treeの深さ優先探索で検出可能。
時間計算量O(N)O(N)

ノード列の重複→コードの重複

子ノードの数を元にノード列を切っていく。

実演

課題

  • コードクローンをペアにする処理
    • 現在O(N3)O(N^3)になっており、非常に遅い
  • テスト整備
    • テストがないのでバグが眠っていそうで怖い

リポジトリ

参考文献