提案するクローン検出手法

本研究においては，名前の変形や構造の識別を可能にするために，ソースファイルをトー 字句解析

変形

検出

変形されたトークン列上での クローン

整形

変形されたトークン列から 変形前のトークン列への

マッピング 変形された

トークン列 ソースファイル

クローン トークン列

クローン検出

図 6.1 提 案するコードクローン検 出 手法 の概 要

クン列として表現することとした．従って，ソースファイル中の構造（文や関数の定義）はトーク ン列 の部 分 列 として表 現 される．名 前 の変 形 や構 造 の識 別 は，トークン列 の変 形 ルールに よって実 現 することとした．提 案 するトークン単 位 の比 較 によるのクローン検 出 プロセスの全 体を図 6.1に示す．プロセスは以下の4つのステップから構成される．

(1) 字句解析

ソースファイルの各 行 がプログラミング言 語 の字 句 ルールに従 ってトークンに切 り分 けら れる．すべてのソースファイルのトークンを連結してひとつのトークン列にするので，単一 のソースファイルからクローンを検出 するのとまったく同じ方 法 で，複数 のソースファイル からクローンを検出することができる．

(2) 変形

トークン列 は以 下 の(2－1),(2－2)を経 て変 形 される．同 時 に，変 形 されたトークン列 か ら変形前のトークン列へのマッピングが保存され，後の整形ステップで用いられる．

(2－1) 変形ルールによる変形

変 形 ルールによって，トークン列 が変 形 され，トークンが付 け加 えられたり，削 除 さ れたり，変更されたりする．表 6.1 と表 6.2 に示す変形ルールは，識別子の正 規 化（RC1, RC2, RJ1, RJ2）および構造の識別RC3, RC4, RJ3, and RJ4)を行う.

表 6.1 C++向 けの変 形ルール

# ルール

RC1 (Name '::')+ Name2 Æ Name2

ここで，+演 算 子 は正 規 表 現 の後 置 演 算 子 であり，1回 以 上 の繰 り返 しを意 味 する．

RC2 Name '<' ParameterList '>' Æ Name

ここで，ParameterList は名 前 ，数 値 ，文 字 列 ，演 算 子 ，’,’，および式 の並 び．

式 はトークンの並 びであり，’(‘で始 まって，対 応 する’)’で終 了 し，’;’を含 まない．

RC3 '=' '{' InitalizationList, '}' Æ '=' '{' UniqueIdentifier '}'

ここで，InitalizationList は名 前 ，数 値 ，文 字 列 ，演 算 子 ，’,’, ‘(‘, ‘)’, ‘{‘, および’}’の並 び．

UniqueIdentifier はユニークなトークンであり，ほかの場 所 には出 現 しない．

RC4 トップレベルの定 義 や宣 言 の終 わりにUniqueIdentifier を挿 入 する．

(2－2)パラメータ置換

次 に，型 ，変 数 ，定 数 に関 係 するすべての識 別 子 が，単 一 の特 殊 なトークンに置 き換 えられる（この置 換 は「parameterized match」[3]の前 処 理 である）．この置 換により，変数名が付け替えられたコード断片を等価とみなすことができる．

(3) 検出

変形されたトークン列のすべての部分列のうち，等価なペアがクローンとして検出される．

各クローンは，4つ組 (cp, cl, op, ol)として表現される．ここで，cpと opは それぞれ 最初のコード断片ともうひとつのコード断片の位置であり，cl と ol はそれらの長さであ る．

(4) 整形

クローンの位 置 が入 力 ソースファイル上 での行 番 号 に変 換 され，整 形 されて出 力 され る．

表 6.2 Java向けの変形 ルール

# Rule

RJ1 ( PackageName ‘.’ )+ ClassName Æ ClassName

ここで，PackageNameは小 文 字 で始 まる語 ．ClassNameは大 文 字 で始 まる語 ． RJ2 NDotOrNew NClassName ‘(‘Æ NDotOrNew CalleeIdentifier ‘.’ NClassName ‘(‘

ここで，NDotOrNew は’.’や’new’以 外 で始 まるトークン．NClassName は小 文 字 で始 まる 語. CalleeIdentifier は省 略 されているcalleeをあらわす語.

RJ3 '=' '{' InitalizationList, '}' Æ '=' '{' UniqueIdentifier '}' ']' '{' InitalizationList, '}'

Æ ']' '{' UniqueIdentifier '}'

ここで，InitalizationList は名 前 ，数 値 ，文 字 列 ，演 算 子 ，',', '(', ')', '{',および'}'の並 び.UniqueIdentifierはユニークなトークンであり，他 の場 所 には出 現 しない．

RJ4 トップレベルの定 義 や宣 言 の後 にUniqueIdentifierを挿 入 する．

図 6.2に，コードクローン検出プロセスを説明するための例となるC++コードを示す．左側の 数 字 は行 番 号 である．この入 力 はトークンに切 り分 けられる．切 り分 けられ，変 形 ルールによ って変形されたトークン列を図 6.3に示す．行 1, 3, 11, および 13 は短くなっている．次 にパラメータ置換 によって再 び変 形 される．パラメータ置 換を受けた後 のトークン列を図 6.4 に示す．この例では，識別子が単一のトークン $pに置き換えられている．

1 void print_lines(const set<string>& s) { 2 int c = 0;

3 set<string>::const_iterator i 4 = s.begin();

5 for (; i != s.end(); ++i) { 6 cout << c << ", "

7 << *i << endl;

8 ++c;

9 } 10 }

11 void print_table(const map<string, string>& m) { 12 int c = 0;

13 map<string, string>::const_iterator i 14 = m.begin();

15 for (; i != m.end(); ++i) { 16 cout << c << ", "

17 << i->first << " "

18 << i->second << endl;

19 ++c;

20 } 21 }

図 6.2 コードクローン検出 プロセスを説 明 するための例 題 コード

1 void print_lines ( const set & s ) { 2 int c = 0 ;

3 const_iterator I 4 = s . begin ( ) ;

5 for ( ; i != s . end ( ) ; ++ i ) { 6 cout << c << ", "

7 << * i << endl ; 8 ++ c ;

9 } 10 }

11 void print_table ( const map & m ) { 12 int c = 0 ;

13 const_iterator I 14 = m . begin ( ) ;

15 for ( ; i != m . end ( ) ; ++ i ) { 16 cout << c << ", "

17 << i -> first << " "

18 << i -> second << endl ; 19 ++ c ;

20 } 21 }

図 6.3 変形ルールによって変形されたトークン列

最終的に，クローン，すなわち，トークン列内の等価な部分列が検出される．ここで ti をi 番目のトークン (1 <= i <= 114)とする．さらに，行列{ dxy }を，dxy = 1 if tx is equal to ty, 0 otherwise，と定義する.行列の一部を図 6.5に示す．図で，dxy = 1かつx > yの部分 は’*’で示した．対称性より，dxy = dyx であり，また，明らかにdxx = 1であるので，x <= y の 部 分 には何 も置 かない．クローンは，行 列 の主 対 角 線 に平 行 な（右 下 がりの）‘*’の線 分 とし て検出される．行 1から7のコード断片と，行 11 から17のコード断片² がクローンとして検 出される．行8から10までのコード断片と，行 19から21までのコード断片がもうひとつのク ローンとなる．行9，10，20，21は互いにクローンとなるが，非常に短くて自明なクローンであ り，クローン検出時に検 出するクローンの最小行 数でフィルタリングすることにより取り除くこと ができる．

2 より厳 密 には，「行11から始 まって行17の最 初 のトークンまでのコード断 片 と，行1から始 まって行7の最 初 のトー クンまでのコード断 片 ・・・」である．ツールの出 力 の中 では，クローンの位 置 は行 番 号 で示 される．

1 $p $p ( $p $p & $p ) { 2 $p $p = $p ;

3 $p $p

4 = $p . $p ( ) ;

5 for ( ; $p != $p . $p ( ) ; ++ $p ) { 6 $p << $p << $p

7 << * $p << $p ; 8 ++ $p ;

9 } 10 }

11 $p $p ($p $p & $p ) { 12 $p $p = $p ;

13 $p $p

14 = $p . $p ( ) ;

15 for ( ; $p != $p . $p ( ) ; ++ $p ) { 16 $p << $p << $p

17 << $p -> $p << $p 18 << $p -> $p << $p ; 19 ++ $p ;

20 } 21 }

図 6.4 パラメータ置 換を行 った後のトークン列