j-1 - Software Engineering Laboratory

情報検索技術に基づく
関数クローン検出を用いた
変更管理システムの開発
佐野真夢1, 吉田則裕2,
春名修介1, 井上克郎1
1
2
大阪大学
名古屋大学
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン
• 同一または類似した部分を持つコード片のこと
– ソースコードのコピーアンドペーストなどにより生じる
• ソフトウェアの保守コストを大きくする要因
あるコード片に
バグがあれば
他のコードクローンにも
バグがあるかもしれない
調査の手間
クローンセット
コードクローン
2
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
クローンの分類[1]
分類
タイプ1
タイプ2
タイプ3
タイプ4
定義
空白, コメント等のコーディングスタイルを除いて完全に
一致している
タイプ1 に加え, ユーザ定義名や型の違いを除いて構文上
一致している
タイプ2 に加え, 文が挿入・変更・削除されている
構文上は異なる実装だが, 同一処理を実行している
各タイプに応じたクローン検出ツールが存在している
[1] Roy et, al., Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach, Science of Computer
Programming, 2009
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
クローンの分類（タイプ3）
種類
意味
タイプ1
空白, コメント等のコーディングスタイルを除いて完全に一致している
タイプ2
タイプ1 に加え, ユーザ定義名や型の違いを除いて構文上一致している
タイプ3
タイプ2 に加え, 文が挿入・変更・削除されている
タイプ4
構文上は異なる実装だが, 同一処理を実行している
int sum(int[] data){
int sum = 0;
for(int i=0;i<data.length;i++){
sum = sum + data[i];
}
return sum;
}
int sum(int[] data){
int sum = 0;
for(int i=0;i<data.length;i++){
sum += data[i];
}
return sum;
}
4行目の文が異なる
4
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
クローンの分類（タイプ4）
種類
意味
タイプ1
空白, コメント等のコーディングスタイルを除いて完全に一致している
タイプ2
タイプ1 に加え, ユーザ定義名や型の違いを除いて構文上一致している
タイプ3
タイプ2 に加え, 文が挿入・変更・削除されている
タイプ4
構文上は異なる実装だが, 同一処理を実行している
int sum(int[] data){
int sum = 0;
for(int i=0;i<data.length;i++){
sum = sum + data[i];
}
return sum;
}
int sum(int[] data){
int sum = 0,i=0;
while(i<data.length){
sum += data[i]; i++;
}
return sum;
}
for文とwhile文で実装が異なる
5
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
クローンの変更管理の必要性
• クローンを修正する場合, 他クローンの同時修
正を検討する必要がある
• 大規模なソフトウェアほど多くのクローンを含む
– 修正の度に, クローンを検出し, 手作業で修正され
たかどうか調査するのは非効率
コードクローン変更を自動管理するシステムが必要
6
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
CloneNotifier[2]
クローンの同時修正を支援するための変更管理システム
ソースコードの
コードクローンの検出
取得
※タイプ1, 2
版管理システム
クローン検出ツール
CCFinder
変更された
コードクローンを把握
変更情報に基づき
コードクローンを分類
開発者
コードクローンの
分類結果の提示
[2] 山中ら, コードクローン変更管理システムの開発と実プロジェクトへの適用, 情報処理学会論文誌, 2013.
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
コードクローン
変更管理システム
7
問題点
• CloneNotifierはタイプ3, 4 のクローンを検出できない
– 文の挿入, 削除, 変更が行われたクローン
– 構文上の実装は異なるが, 処理が同じクローン
• 同時修正の際には, これらも確認すべき
void AscendingSort(int list[])
{
比較対象のミス
void DescendingSort(int list[]) {
for(i = 0; i < n-1; i++) × j+1 → ○for(i
j-1 = 0; i < n-1; i++)
for(j = n-1; j > i; j--)
for(j = n-1; j > i; j--)
if(list[j+1] > list[j]) {
if(list[j+1] < list[j]) {
修正: if(list[j-1] > list[j]) {
修正: if(list[j-1] < list[j]) {
temp = list[j];
temp = list[j];
list[j] = list[j-1];
list[j] = list[j-1];
list[j-1] = temp;
list[j-1] = temp;
比較演算子が異なる
}
}
→
タイプ3
}
}
検出できない同時修正の例（タイプ3）
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
山中らのクローン検出ツール[3]
• テキストマイニング技術を利用したクローン検出ツール
• 関数単位でクローンを検出する
• タイプ1～4 の全てのクローンを高速に検出可能
Function A
ワード回数
000
000
xxx
3
yyy
2
・・・
・・・
Function A
𝑎1 , 𝑎2 , 𝑎3 , …
類似度
0.95
0.70
Function B
ワード回数
ソースコード
入力
Function A
Function B
xxx
2
yyy
4
・・・
・・・
ワード抽出
Function B
𝑏1 , 𝑏2 , 𝑏3 , …
特徴ベクトル
計算
Function C
Function D
Function E
クラスタリング
[3] 山中ら, 情報検索技術に基づく高速な関数クローン検出, 情報処理学会論文誌, 2014.
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
0.70
0.90
・・・
関数対クローン
Function A

Function B
Function C
Function D
Function C
Function E
Function D

Function E
・・・
・・・
クローン検出
9
研究概要
• 山中らのクローン検出ツールを利用し, 新しい
クローン変更管理システムを開発
– 従来のCloneNotifier を改変する形で実装
• クローン検出ツール CCFinder を山中らのクローン検出
ツールに置換
• クローン（関数）の位置特定処理の追加
– 山中らの検出ツールがクローンの位置情報を出力しないため
• 開発したシステムの評価実験
10
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価実験
• 新CloneNotifierが, 従来のCloneNotifierでは
検出できない事例を実際に検出できるか調査
– 新CloneNotifier：山中らの検出ツールを使用（タイプ1～4）
– 従来のCloneNotifier： CCFinder を使用（タイプ1～2）
• 調査対象
– PostgreSQL[4]
• OSS のデータベース管理システム（C言語）
• 2005/01/01 ～ 2005/06/30 の 6ヶ月間
• 1週間単位で区切り
[4] http://www.postgresql.org/
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
評価手順
1. 各期間内の新・旧プロジェクトを取得し, 新CloneNotifierを
適用した結果を得る
– 得られる結果は変更があったクローンセットの集合
– 旧: 各期間内の一番古い状態, 新: 各期間内での最新状態
2. 結果から実際にコードに対する修正が行われた事例のみを
抽出する（手動）
– クローン自体の追加・削除・移動を除外
3. さらに, 従来のCloneNotifierで検出できない事例（タイプ3, 4
への修正）を抽出し, 一貫した修正か否かを分類する
12
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価結果(1/2)
新 CloneNotifier で検出されたクローンセット修正事例の数
従来CloneNotifierでは従来CloneNotifierでも合計
検出不可
検出可能
126
219
345
約 1/3 が従来の CloneNotifier では検出できない
事例であった
13
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価結果(2/2)
従来の CloneNotifer で検出できない有用な修正事例の数
一貫した非一貫した他に適用
整形
合計
修正
修正
不能な修正コメントのみ
73
16
32
5
126
一貫した修正 = クローンセットの全クローンが対象の場合のみ
非一貫した修正 = 1つでも一貫修正がなく, かつ一部でも適用可能な修正があれば
他に適用不能 = 明らかに適用できない or する必要が無い
従来の CloneNotifier で検出できない 89件の
有用なクローン修正事例を検出できた
14
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫した修正1）
Changed Cloneset 2005/03/12 → 2005/03/18
src/backend/access/common/printtup.c
src/backend/access/common/printtup.c
printtup
printtup_internal_20
printtup(HeapTuple tuple, TupleDesc typeinfo, ...)
{
...
heap_deformtuple(...)
forブロックの
...
有無
for(i=0;i<natts;++i) {
...
Datum origattr = myState->values[i], attr;
if(myState->nulls[i] == 'n') {
pq_sendint(&buf,-1,4);
continue;
}
呼出し関数
}
...
がある
タイプ3
修正前
printtup_internal_20(HeapTuple tuple, TupleDesc typeinfo, ...)
{
...
heap_deformtuple(...)
...
for(i=0;i<natts;++i) {
if(myState->nulls[i] != 'n')
j |= k;
...
}
...
for(i=0;i<natts;++i) {
局所変数が多い
...
Datum origattr = myState->values[i], attr;
bytea *outputbytes;
if(myState->nulls[i] == 'n')
continue;
}
...
}
}
15
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫した修正1）
Changed Cloneset 2005/03/12 → 2005/03/18
src/backend/access/common/printtup.c
src/backend/access/common/printtup.c
printtup
printtup_internal_20
タイプ3
修正後
引数の変更
printtup(TupleTableSlot *slot, ...)
{
TupleDesc typeinfo = ...;
...
slot_getallattrs(slot);
...
printtup_internal_20(TupleTableSlot *slot, ...)
{
TupleDesc typeinfo = ...;
...
変数・関数
slot_getallattrs(slot);
呼出しの追加
...
for(i=0;i<natts;++i) {
if(slot->tts_isnull[i])
j |= k;
...
}
nullチェックの ...
for(i=0;i<natts;++i) {
方法を変更 for(i=0;i<natts;++i) {
...
...
Datum origattr = slot->tts_values[i], attr;
Datum origattr = slot->tts_values[i], attr;
if(slot->tts_isnull[i]) {
bytea *outputbytes;
pq_sendint(&buf,-1,4);
if(slot->tts_isnull[i])
continue;
continue;
}
}
参照先の変更
}
...
...
}
}
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
有用な事例（一貫した修正2）
Changed Cloneset 2005/05/21 → 2005/05/27
src/backend/utils/adt/nabstime.c
src/backend/utils/adt/nabstime.c
timepl
timemi
修正前
タイプ3
timepl(PG_FUNCTION_ARGS)
timemi(PG_FUNCTION_ARGS)
比較の向き
{
{
が異なる
...
...
if(AbsoluteTimeIsReal(t1) &&
if(AbsoluteTimeIsReal(t1) &&
RelativeTimeIsValid(t2) &&
RelativeTimeIsValid(t2) &&
((t2 > 0) ? (t1 < NOEND_ABSTIME - t2)
((t2 > 0) ? (t1 > NOSTART_ABSTIME + t2)
: (t1 > NOSTART_ABSTIME - t2)))
: (t1 < NOEND_ABSTIME + t2)))
...
...
}
}
比較の向き
が異なる
演算子が異なる
17
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫した修正2）
Changed Cloneset 2005/05/21 → 2005/05/27
src/backend/utils/adt/nabstime.c
src/backend/utils/adt/nabstime.c
timepl
timemi
修正後
タイプ3
timepl(PG_FUNCTION_ARGS)
{
...
if(AbsoluteTimeIsReal(t1) &&
RelativeTimeIsValid(t2) &&
((t2 > 0 && t1 < NOEND_ABSTIME - t2) ||
(t2 <= 0 && t1 > NOSTART_ABSTIME - t2)))
...
}
timemi(PG_FUNCTION_ARGS)
{
...
if(AbsoluteTimeIsReal(t1) &&
RelativeTimeIsValid(t2) &&
((t2 > 0 && t1 > NOSTART_ABSTIME + t2) ||
(t2 <= 0 && t1 < NOEND_ABSTIME + t2)))
...
}
三項演算子を解消し, and/or のみの表現に変更
18
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫しない修正1）
Changed Cloneset 2005/04/02 → 2005/04/08
src/backend/utils/adt/numeric.c
src/backend/utils/adt/numeric.c
src/backend/utils/adt/numeric.c
int2_sum
int4_sum
int8_sum
修正前
タイプ3
※ int2_sum と int4_sum は一貫した修正.
int4_sum(...)
int8_sum(...)
{
{
int64 oldsum;
Numeric oldsum;
...
...
oldsum = PG_GETARG_INT64(0);
oldsum = PG_GETARG_NUMERIC(0);
代入する式の違い
if(PG_ARGISNULL(1))
if(PG_ARGISNULL(1))
PG_RETURN_INT64(oldsum);
PG_RETURN_NUMERIC(oldsum);
newval = oldsum + (int64) PG_GETARG_INT32(1);
newval = DirectFunctionCall1(...);
PG_RETURN_INT64(newval);
PG_RETURN_DATUM(DirectFunctionCall2(..));
}
}
引数となる式の違い
19
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫しない修正1）
Changed Cloneset 2005/04/02 → 2005/04/08
src/backend/utils/adt/numeric.c
src/backend/utils/adt/numeric.c
src/backend/utils/adt/numeric.c
int2_sum
int4_sum
int8_sum
修正後
タイプ3
※ int2_sum と int4_sum は一貫した修正.
int4_sum(...)
{
分岐処理の追加
...
if(fcinfo->context && IsA(...)) {
int64 *oldsum = (int64*) PG_GETARG_POINTER(0);
if(!PG_ARGISNULL(1))
*oldsum = *oldsum+(int64) PG_GETARG_INT32(1);
PG_RETURN_POINTER(oldsum);
} else {
int64 oldsum = PG_GETARG_INT64(0);
if(PG_ARGISNULL(1))
PG_RETURN_INT64(oldsum);
newval = oldsum + (int64) PG_GETARG_INT32(1);
PG_RETURN_INT64(newval);
}
}
int8_sum(...)
{
...
追加は無いが,
外見上は適用できる可能性が
考えられる
oldsum = PG_GETARG_NUMERIC(0);
if(PG_ARGISNULL(1))
PG_RETURN_NUMERIC(oldsum);
newval = DirectFunctionCall1(...);
PG_RETURN_DATUM(DirectFunctionCall2(..));
}
20
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫しない修正2）
Deleted Cloneset
src/bin/pg_ctl/pg_ctl.c
src/bin/pg_ctl/pg_ctl.c
2005/04/30 → 2005/05/06
do_stop
do_restart
do_stop(void)
{
...
else if(pid < 0) {
pid = -pid;
writestderr(_("..."), progname, pid);
exit(1);
}
if(kill((...) != 0) { ... }
if(!do_wait) { ... }
else {
print_msg(...);
...
}
修正前
タイプ3
関数呼出しが多い
do_restart(void)
{
...
else if(pid < 0) {
pid = -pid;
writestderr(_("..."), progname, pid);
writestderr(...);
exit(1);
}
if(kill((...) != 0) { ... }
if分岐がある
print_msg(...);
...
}
}
21
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
有用な事例（一貫しない修正2）
Deleted Cloneset
src/bin/pg_ctl/pg_ctl.c
src/bin/pg_ctl/pg_ctl.c
2005/04/30 → 2005/05/06
do_stop
do_restart
do_stop(void)
{
...
else if(pid < 0) {
pid = -pid;
適用すべきか検討は必要
writestderr(_("..."), progname, pid);
exit(1);
}
if(kill((...) != 0) { ... }
if(!do_wait) { ... }
else {
print_msg(...);
...
}
}
修正後
タイプ3
do_restart(void)
{
...
else if(pid < 0) {
pid = -pid;
if(postmaster_is_alived(pid) {
writestderr(_("..."), progname, pid);
writestderr(...);
exit(1);
プロセス生存チェック
}
の追加
}
if(postmaster_is_alived(pid) {
if(kill((...) != 0) { ... }
print_msg(...);
...
} else { ... }
}
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
まとめと今後の課題
• 新しいクローン変更管理システムの開発
• 開発したシステムの有用性評価
• 今後の課題
– 従来の CloneNotifier との比較
• 従来版のみが検出できるクローンの調査
• 両システムで検出できるクローンの調査
– 対象プロジェクトの追加
23
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Download Report