情報処理学会研究報告
IPSJ SIG Technical Report

1. ま え が きプログラム依存グラフを用いた
Template Method パターン適用によるコードクローン集約支援
堀 田

圭 佑†1

肥

後

芳

樹†1

楠 本 真

近年，ソフトウェア工学における研究対象として，コードクローンが注目されている．コー
ドクローンとは，ソースコード中の同一，あるいは類似するコード片のことをいい，主にコピーアンドペースト等によって発生するといわれている．一般的に，コードクローンの存在
はソフトウェアの保守を困難にすると考えられている．これは，あるコード片に修正を加えた際，そのコード片とコードクローン関係にある他のコード片についても同様の修正を検討

二†1

しなければならない可能性が高いためである．このため，コードクローンを自動的に検出す
る，あるいはその集約を支援する手法が多数提案されている1) ．

近年，ソフトウェアの保守性を低下させる要因の 1 つとしてコードクローンが注目されており，これまでにその集約を支援する手法が多数提案されている．中でもTemplate Method パターン適用による集約支援手法は，差分を含むコードクローンを集約可能なため高い効果が期待できるが，既存手法にはいくつかの課題点が存在する．本稿ではプログラム依存グラフを用いることで既存研究の課題点を改善した，
Template Method パターン適用によるコードクローン集約支援手法を提案する．

コードクローンの集約を支援する手法の 1 つとして，Template Method パターンと呼ばれるデザインパターンを適用する手法が提案されている2),3) ．Template Method パターンとは，共通の親クラスを持つ類似メソッドを対象とし，メソッド間で共通の処理を親クラスに記述し，メソッドごとに異なる処理を子クラスに記述する，というパターンである．このパターンを用いたコードクローン集約手法では，メソッド間でコードクローンとなっている箇所を共通の処理として親クラスに引き上げ，コードクローンとなっていない箇所を子クラ

A Technique to Support Removing Code Cloneby Applying Template Method Patternwith Program Dependence Graph

スに記述することで，コードクローンの集約を実現している．この手法の最大の特長として，対象となるメソッドがコードクローンとなっていない箇所を含んでいても適用が可能である，という点が挙げられる．しかし，既存手法には以下に挙げる課題点が存在する．

• 変数名などのユーザ定義名のみが異なるコードクローンを集約できない．

KEISUKE HOTTA,†1 YOSHIKI HIGO†1
and SHINJI KUSUMOTO†1• 意味的に同じ処理を行っているコードでも，その表現方法が異なる場合は集約できない．
そこで本稿ではこれらの課題点を改善するため，プログラム依存グラフを用いた Template

Method パターンの適用支援手法を提案する．
Recently, code clone has received much attention. And many research eﬀorts
have performed on removing code clones. Especially, it is highly expected thatthe removing technique with Template Method pattern has high applicability
because it can remove code clones which has some gaps. However previous
research eﬀorts remain some issues. In this paper, we propose a new techniqueof removing code clones by applying Template Method pattern with program
dependence graph to resolve these issues.

2. 準

備

2.1 Template Method パターン
Template Method パターンとは，Gamma らによって提案されているデザインパターンの 1 つである4) ．このパターンは共通の親クラスを持つメソッドペアに対し，メソッド間で共通の処理を親クラスに，異なる処理をそれぞれの子クラスに記述するというものである．

Template Method パターンの適用例を図 1 に示す．この例では，Site を共通の親クラスとする 2 つのクラスの間に類似メソッド getBillableAmount() が存在している．このメソッド†1 大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka Universityの共通部分を親クラスに引き上げ，異なる部分をそれぞれ新たなメソッドとして抽出している．

1

c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical Report
return getBaseAmount() + getTaxAmount();

Site

Site

getBillableAmount()
getBaseAmount()
getTaxAmount()

Pull Up

Residential Site

Lifeline Site

getBillableAmount()

getBillableAmount()

double base = units * rate;
double tax = base * Site.TAXRATE;
return base + tax;

Residential Site
getBaseAmount()
getTaxAmount()

method
enter

<1>

<2>

<3>
<4>

<5>

<7>
データ依存辺

制御依存辺図 2 PDG の例
Fig. 2 An Example of PDG

Lifeline Site
getBaseAmount()
getTaxAmount()

return units * rate;

2.3 PDG を用いたコードクローン検出

return base * Site.TAXRATE;

double base = units * rate * 0.5;
double tax = base * Site.TAXRATE * 0.2;
return base + tax;

Fig. 1

1: x = 0;
2: y = 0;
3: z = MAX;
4: while (y < z) {5:
y = x + 1;
6: }7: println(y);これまでにコードクローンの自動検出手法は多数提案されており，それらは検出時に用い

return units * rate * 0.5;

るデータ構造によって分類できる．その 1 つである PDG を用いた検出は，PDG 上で同形

return base * Site.TAXRATE * 0.2;

部分グラフとなっている箇所をコードクローンとして検出する手法である．この手法の最大

図 1 Template Method パターンの適用例
An Example of the Application of Template Method Patternの利点として，コード順序が異なる場合や，for 文と while 文等の表現の異なる場合といった，他の検出手法では検出不可能なコードクローンを検出できるという点が挙げられる．
本稿で用いる検出ツール Scorpio7) はこの PDG を用いた検出に分類される検出ツールでこのように修正することで，多態性によってそれぞれのクラスに応じた getBaseAmount()
5)

ある．Scorpio は PDG の比較時に，各頂点が表現するコード片からハッシュ値を生成し，及び getTaxAmount() が呼び出され，適用前後で振る舞いが保たれる ．
このように，Template Method パターンの適用によってメソッド間に共通していた処理

そのハッシュ値を用いて頂点同士の一致性を判定している．このハッシュ値の生成時に特殊が親クラスにまとめて記述されるため，適用前にコードクローンとなっていたコードが集な処理を行っており，ユーザ定義名のみが異なるコードクローンを検出可能である．

約され，ソフトウェアの保守性向上が期待できる．また，Template Method パターンはメ

3. 提 案 手 法

ソッド間に異なる処理が含まれていても適用可能であり，コピーアンドペースト等でコード3.1 概を生成した後に修正が加えられた場合でも適用が可能であるという特長がある．

2.2 プログラム依存グラフ

要

提案手法は，対象とするメソッドの対，各メソッドの PDG，及びそのメソッド間のコープログラム依存グラフ (Program Dependence Graph6) , 以降 PDG) とは，プログラム中

ドクローン情報を入力とし，各メソッドについて親クラスに引き上げるべき頂点集合，及びの要素 (文) 間の依存関係を表した有向グラフである．依存関係には次の 2 種類が存在する．

子クラスに残すべき頂点集合を出力する．子クラスに残すべき頂点集合については，1 つのデータ依存 文 s で変数 v を定義し，変数 v が再定義されることなく文 t において参照さメソッドとして抽出すべき頂点集合も併せて出力する．

れる場合，文 s から文 t にデータ依存があるという．

3.2 用語の定義

制御依存 文 s が条件文または繰り返し文の条件式であり，その条件判定の結果によって文

定義 3.1 (対象メソッドペア) ownerclass(m) をメソッド m が実装されているクラス，

t が実行されるか否かが直接決定される場合，文 s から文 t へ制御依存があるという．

ParentClasses(c) をクラス c の先祖クラスの集合であると仮定する．このとき，式 (1) を

図 2 の例では，4 行目で変数 y ，z の値が参照されているため，2，3，5 行目から 4 行目

満たす 2 つのメソッド (m0 ，m1 ) の対を対象メソッドペアと呼ぶ．

へのデータ依存関係がある．また，5 行目は 4 行目によって実行の有無が定まるため，4 行(ownerclass(m0 ) 6= ownerclass(m1 )) ∧ ∃c(c ∈ ParentClasses(ownerclass(m0 )) ∧c ∈ ParentClasses(ownerclass(m1 )))目から 5 行目への制御依存関係がある．また，一般的に PDG はメソッドの入り口に相当す(1)

定義 3.2 (到達辺集合, 出発辺集合, 出発頂点, 到着頂点) ある頂点 n について，n を到る頂点を持ち，その頂点からメソッド直下のすべての文へ制御依存関係が存在する．

2

c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical Report

達頂点とする辺の集合を到達辺集合と定義し,BackwardEdges(n) と表記する．また頂点 nx : if (this.getVerbose()) {x+1: long endTime = System.current.TimeMillis();x+2: logStats(startTime, endTime, (int) totalLength);x+3: }

を出発頂点とする辺の集合を出発辺集合と定義し,ForwardEdges(n) と表記する．また，ある辺 e について，e の出発頂点を fromnode(e)，到達頂点を tonode(e) とする．

< x+1 >
< x+2 >

： 共通部分となっているコード

定義 3.3 (PDG 頂点集合，PDG 辺集合) あるメソッド m について Nodes(m) を m<x>: 共通部分となっている頂点

図 3 差異部分から共通部分への制御依存
Fig. 3 An Example of Control Dependence Edge from Diﬀerent-Part to Common-Partの PDG 頂点集合，及び頂点集合 N について Edges(N ) を N の PDG 辺集合と定義する．
定義 3.4 (クローンペア) 入力として与えられた対象メソッドペア (m0 ，m1 ) 間のすべてのクローンペアの集合を ClonePairs(m0 , m1 ) とする．このとき，式 (2) を満たす頂点集

条件 1:差異頂点集合が return 文を含まない

合 N0 ，N1 の対をクローンペアと呼び，cp(N0 , N1 ) と表記する．
(N0 , N1 ) ∈ ClonePairs(m0 , m1 )差異頂点集合が表現する文に return 文が含まれる場合，差異頂点集合を新規メソッドとして抽出した際，作成したメソッドはそのメソッド自身とそのメソッドを呼び出す親クラス(2)

定義 3.5 (共通頂点集合，メソッド内共通頂点集合) 対象メソッドペアの共通頂点集合に引き上げたメソッドの 2 つのメソッドを同時に脱け出さなければならない．このような場

CommonNodePairs(m0 , m1 ) を式 (3) で定義する．

合，提案手法は入力されたメソッドペアに対しての Template Method パターン適用は不可能と判定する．すなわち，statement(n) を頂点 n が表現する文，return(s) を文 s が return

CommonNodePairs(m0 , m1 ) := {(s, t) : ∃cp(N0 , N1 ) ∈ ClonePairs(m0 , m1 )((s ∈ N0 ) ∧ (t ∈ N1 ))} (3)文のときのみ真となる述語論理式であるとするとき，以下の論理式 hasReturn(m0 , m1 ) をまた，対象メソッドペア (m0 ，m1 ) の各メソッドについて，そのメソッドのメソッド内共充足する対象メソッドペア (m0 ，m1 ) を適用不可能であると判定する．

通頂点集合 CommonNodes(mi ) (i = 0, 1) を式 (4) で定義する．
CommonNodes(mi ) := {n ∈ Nodes(mi ) : (∃(s, t) ∈ CommonNodePairs(m0 , m1 ) ((s = n) ∨ (t = n)))}hasReturn(m0 , m1 ) := ∃i ∈ {0, 1}(∃n ∈ DiﬀNodes(mi )(return(statement(n))))条件 2:差異頂点集合からメソッド内共通頂点集合への制御依存が存在しない(4)

control (e) を辺 e が制御依存辺のときのみ真となる述語論理式であるとする．このとき，定義 3.6 (差異頂点集合) 対象メソッドペア (m0 ，m1 ) の各メソッドについて，そのメ

対象メソッドペア (m0 ，m1 ) について，論理式 invalidControl (m0 , m1 ) を以下に定義する．

ソッドの差異頂点集合 DiﬀNodes(mi ) (i = 0, 1) を式 (5) で定義する．
DiﬀNodes(mi ) := {n ∈ Nodes(mi ) : n ∈/ CommonNodes(mi )}

3.3 処

(6)

invalidControl(m0 , m1 ) := ∃i ∈ {0, 1}(∃e ∈ Edges(Nodes(mi ))((control(e)) ∧(fromnode(e) ∈ DiﬀNodes(mi )) ∧ (tonode(e) ∈ CommonNodes(mi ))))

(5)

(7)

invalidControl (m0 , m1 ) を充足する対象メソッドペア (m0 ，m1 ) の差異頂点集合を新

理

本節では提案手法の処理内容について述べる．なお，提案手法は下記の手順で実行される．

規メソッドとして抽出することは不可能である．これは図 3 のように，差異頂点集合がStep1 Template Method パターンの適用に必要な条件の解決．

条件式とブロック文の一部のみを含んでいる場合に生じる問題である．この条件は共通

Step2 1 つのメソッドとして抽出すべき頂点集合の特定．

頂点集合に含む頂点ペア情報を操作することで解決が可能である．以下にその解決方法

Step3 Step2 で特定した頂点集合同士のメソッドペア間での対応付け．

resolveIC (CommonNodePairs(m0 , m1 )) を示す．
Input: CommonNodePairs(m0 , m1 )Output: CommonNodePairs(m0 , m1 )(¬invalidControl(m0 , m1 ))for all (n0 , n1 ) such that (n0 , n1 ) ∈ CommonNodePairs(m0 , m1 ) do
for all be such that ((be ∈ BackwardEdges(n0 )) ∧ control(be) ∧ fromnode(be) ∈ DiﬀNodes(m0 ))doCommonNodePairs(m0 , m1 ) ← CommonNodePairs(m0 , m1 ) − (n0 , n1 )end forfor all be such that ((be ∈ BackwardEdges(n1 )) ∧ control(be) ∧ fromnode(be) ∈ DiﬀNodes(m1 ))以降の小節で各ステップについて詳細に述べる．

3.3.1 Step1:必要条件の解決
Template Method の形成にはいくつかの必要条件が存在するため，対象メソッドペアへの適用が可能か否かを判定する必要がある．適用ができない場合，共通頂点集合を必要条件を満たすように操作し，共通頂点集合の操作では必要条件の解決ができない場合は適用が不可能であると判断する．以下に満たさなければならない必要条件とその解決方法を述べる．

3

c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical ReportdoCommonNodePairs(m0 , m1 ) ← CommonNodePairs(m0 , m1 ) − (n0 , n1 )end forend forreturn CommonNodePairs(m0 , m1 )ゴリズムを説明する．

3.3.2 Step2:抽出頂点集合，抽出頂点集合群の特定なる論理式とするとき，頂点集合 N からのデータ依存辺の集合 output(N ) を式 (9) で定義

対象メソッドペア (m0 ，m1 ) の各メソッドについて，その差異頂点集合から 1 つの新規する．

返り値集合の特定ある抽出頂点集合 dg をメソッドとして抽出した際，返すべき値の集合である返り値集合

ReturnValues(dg) を特定する．はじめに，data(e) を辺 e がデータ依存辺のときのみ真とメソッドとして抽出すべき頂点の集合である抽出頂点集合を特定し，それらの集合である抽

output(N ) := {e ∈ Edges(N ) : ((fromnode(e) ∈ N ) ∧ (tonode(e) ∈/ N ) ∧ data(e))}

出頂点集合群 DiﬀGroups(mi ) (i = 0, 1) を特定する．

また，頂点集合 N を保持するメソッドを ownermethod (N )，Variables(m) をメソッド

まず，頂点集合 N に含まれる頂点のうち，頂点 n から辺を辿って到達可能な頂点集合をm で使用される変数の集合とし，var (de) をデータ依存辺 de が表す変数とする．このとき，特定する処理 search(n, N ) を以下に定義する．

返り値集合 ReturnValues(dg) を式 (10) で定義する．

Input: n:基点，N :探索可能頂点集合
Output: n から辺を辿って到達可能かつ N に含まれる頂点集合T ←nfor all e such that e ∈ ForwardEdges(n) do
if tonode(e) ∈ N thenT ← T + search(tonode(e), N )end ifend forreturn T

ReturnValues(dg) := {v ∈ Variables(ownermethod(dg)) : ∃e ∈ output(dg)(v = var (e))} (10)対応付けアルゴリズム
以下の説明では，対象メソッドペアを (m0 ，m1 ) とし，各メソッドを mi (i = 0, 1) とする．
はじめに，ある抽出頂点集合 N に対し, その抽出頂点集合へのデータ依存辺を持ち，かつそのデータ依存辺の出発頂点がメソッド内共通頂点集合に含まれるような辺集合 input(N, mi )を式 (11) で定義する．
input(N, mi ) := {e ∈ Edges(Nodes(mi )) : ((fromnode(e) ∈ CommonNodes(mi ))∧(tonode(e) ∈ N ))}(11)次に，2 つの頂点集合 S, T に対して merge(S, T ) を以下に定義する．
merge(S, T ) := S ∪ T

(9)

(8)

また，2 つの頂点 n0 , n1 の対が共通頂点集合に含まれるか否かを判定する式 clone(n0 , n1 )このとき，DiﬀGroups(mi ) を特定する処理 detectDiﬀGroups(mi ) を以下に示す．

を式 (12) で定義する．

Input: DiﬀNodes(mi )Output: DiﬀGroups(mi )DiﬀGroups(mi ) ← ∅for all n such that n ∈ DiﬀNodes(mi ) dodg ← search(n, DiﬀNodes(mi ))DiﬀGroups(mi ) ← dg
for all adg such that (adg ∈ DiﬀGroups(mi ) ∧ ∃n ∈ dg(n ∈ adg)) do
DiﬀGroups(mi ) ← DiﬀGroups(mi ) − adg + merge(adg, dg)
end forend forclone(n0 , n1 ) := ∃(a, b) ∈ CommonNodePairs (m0 , m1 ) ((n0 = a ∧ n1 = b)∨(n0 = b ∧ n1 = a))(12)

次に，typeE (e) を辺 e の種類 (データ依存辺か制御依存辺か)，typeV (v) を変数 v の型を表すものとし，|S| を集合 S の要素数とする．このとき，2 つの抽出頂点集合 DG0 ,DG1への依存辺の集合 B0 ，B1 に対し，それらの依存辺の出発頂点が共通頂点集合内で対応しているか否かを判定する論理式 sameInput(B0 , B1 ) を式 (13) で定義する．また,DG0 ,DG1からのデータ依存辺が表す変数の集合 V0 ，V1 に対し，それらの変数が表す型及び変数の数

3.3.3 Step3:抽出頂点集合同士の対応付けが一致するか否かを判定する式 sameOutput(V0 , V1 ) を式 (14) で定義する．

対象メソッドペア (m0 ，m1 ) の各メソッドにおける抽出頂点集合群 DiﬀGroups(m0 )，sameInput(B0 , B1 ) := (∀b0 ∈ B0 , ∃b1 ∈ B1 ((typeE (b0 ) = typeE (b1 ))∧clone(fromnode(b0 ), fromnode(b1 )))∧(∀b1 ∈ B1 , ∃b0 ∈ B0 ((typeE (b0 ) = typeE (b1 ))∧clone(fromnode(b0 ), fromnode(b1 )))DiﬀGroups(m1 ) の各要素同士で対応を取り，抽出頂点集合ペア DiﬀGroupPairs(m0 , m1 )を特定する．まずこの手順に必要となる返り値集合の特定手法を述べた後，この手順のアル

4

(13)

c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical Report
sameOutput(V0 , V1 ) := (|V0 | = |V1 |) ∧(∀v0 ∈ V0 , ∃v1 ∈ V1 (typeV (v0 ) = typeV (v1 )))∧(∀v1 ∈ V1 , ∃v0 ∈ V0 (typeV (v0 ) = typeV (v1 )))Input: (m0 , m1 ), Nodes(m0 ), Nodes(m1 ), Edges(Nodes(m0 )), Edges(Nodes(m1 )),ClonePairs(m0 , m1 )Output: (CommonNodePairs(m0 , m1 ), DiﬀGroupPairs(m0 , m1 ))DiﬀGroupPairs(m0 , m1 ) ← ∅CommonNodePairs(m0 , m1 ) ← detectInitCN
DiﬀNodes(m0 ) ← detectDN (m0 )DiﬀNodes(m1 ) ← detectDN (m1 )if hasReturn(m0 , m1 ) thenreturn (NULL, NULL) /* invalid method pair */end if
if invalidControl(m0 , m1 ) thenCommonNodePairs(m0 , m1 ) ← resolveIC (CommonNodePairs(m0 , m1 ))DiﬀNodes(m0 ) ← detectDN (m0 )DiﬀNodes(m1 ) ← detectDN (m1 )end ifDiﬀGroups0 ← detectDiﬀGroups(m0 )DiﬀGroups1 ← detectDiﬀGroups(m1 )DiﬀGroupPairs(m0 , m1 ) ← detectDGPairs(DiﬀGroups0 , DiﬀGroups1 )return CommonNodePairs(m0 , m1 ), DiﬀGroupPairs(m0 , m1 )(14)

このとき，抽出頂点集合間の対応の有無を判定する式 same(S, T ) を式 (15) に定義する．
same(S, T ) := sameInput(input(S, ownermethod(S)), input(T, ownermethod(T ))) ∧sameOutput(ReturnValues(S), ReturnValues(T ))(15)以上の定義のもとで，抽出頂点集合の対応を取る処理 detectDGPairs(DiﬀGroups(m0 ),DiﬀGroups(m1 )) を以下に示す。
Input: DiﬀGroups(m0 ), DiﬀGroups(m1 )Output: DiﬀGroupPairs(m0 , m1 )DiﬀGroupPairs(m0 , m1 ) ← ∅RDG ← ∅
for all dg0 such that dg0 ∈ DiﬀGroups(m0 ) do
pd ← f alse
for all dg1 such that dg1 ∈ DiﬀGroups(m1 ) do
if same(dg0 , dg1 ) thenDiﬀGroupPairs(m0 , m1 ) ← DiﬀGroupPairs(m0 , m1 ) + (dg0 , dg1 )RDG ← RDG + dg1
pd ← true
break
end ifend forif pd = f alse thenDiﬀGroupPairs(m0 , m1 ) ← DiﬀGroupPairs(m0 , m1 ) + (dg0 , NULL)
end ifend forfor all dg1 such that dg1 ∈ DiﬀGroups(m1 ) ∧ dg1 ∈/ RDG doDiﬀGroupPairs(m0 , m1 ) ← DiﬀGroupPairs(m0 , m1 ) + (NULL, dg1 )end forreturn DiﬀGroupPairs(m0 , m1 )

4. 実

装

提案手法を Java を用いて実装した．入力となる PDG 情報及びコードクローン情報の特定には，ソースコード解析ツール MASU8) とコードクローン検出ツール Scorpio を用いた．

4.1 入 力 支 援
提案手法では入力として対象となるメソッドペアをあらかじめ指定する必要がある．しかし，膨大なソースコードから対象メソッドペアを特定することは困難であると考えられる．
このため，本実装では Scorpio で検出されたコードクローン情報から適用可能な候補を自動的に特定し，その一覧を利用者に提示することで適用可能候補の特定の支援を行う．

ここで対応関係の取られた抽出頂点集合 dgpair (dg0 , dg1 ) ∈ DiﬀGroupPairs(m0 , m1 ) は

4.2 言語依存支援

同じシグネチャを持つメソッドとして抽出すべき箇所となる．いずれか一方が NULL の場

提案手法はプログラミング言語に依存せずに適用可能であるが，適用対象のプログラミ

合，その処理は一方のメソッドにしか含まれない処理であり，その処理を含まないメソッド

ング言語に応じた処理を追加することでより的確な支援が実現可能であると考えられる．

には同じシグネチャを持つ何もしないメソッドを作成する必要が生じる．

MASU 及び Scorpio が Java のみに対応しているため，本実装ではパターン適用時の必要

3.4 処理の流れ

条件に Java に特化した条件を追加した．以降で追加した条件について述べる．

提案手法の処理の流れを以下に示す．なお，入力情報から CommonNodePairs(m0 , m1 ) を

条件 3:抽出頂点集合が返すべき値が 1 つ以下である

特定する処理を detectInitCN とし，CommonNodePairs(m0 , m1 ) から DiﬀNodes(mi ) (i =Java では 1 つのメソッドは 1 つ以下の値しか返すことができない．このため，提案手法0, 1) を特定する処理を detectDN と表記している．

で特定した抽出頂点集合が新規メソッドとして抽出不可能である可能性がある．そこで本実

5c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical Report

装では，3.3.2 で述べた抽出頂点集合特定処理の終了後に処理を追加する．

抽出頂点集合A

1: int x = 0;
2: while (x < 100) {3: x = x * 2;
4: int y = random();
5: x = x + y;
6: }まず，ある頂点集合 N について，Bounds(N ) を式 (16) で定義する．
Bounds(N ) := {n ∈ N : (∃e ∈ ForwardEdges(n)(tonode(e) ∈/ N ))}(16)

次に，NodesContainEdgesOfOther (N, v) を式 (17) で定義する．
NodesContainEdgesOfOther (N, v) := {n ∈ N : ∃e ∈ F orwardEdges(n)(data(e) ∧ (tonode(e) ∈/ N ) ∧ (var(e) 6= v))}

<1>
抽出頂点集合B

<2>
<5>

<4>
<6>

図 4 制約の追加による抽出頂点集合の分離問題
Fig. 4 A Problem of Secession of Extract-Nodes Set by Adding the Block Statement Constraint(17)

このとき，次に示す処理を DiﬀGroups(mi ) に施すことで条件の解決を行う．
Input: DiﬀGroups(mi )Output: DiﬀGroups(mi ) (sartisfying ∀dg ∈ DiﬀGroups(mi )(|ReturnValues(dg)| <= 1))
for all dg such that dg ∈ DiﬀGroups(mi ) doif (|ReturnValues(dg)| > 1) thenmax ← 0U ←∅for all v such that v ∈ ReturnValues(dg) do
S ← dgT ←∅repeatT ← Bounds(S)S ← S − NodesContainEdgesOfOther (T, v)
until (|NodesContainEdgesOfOther (T, v)| = 0)
if |S| ≥ max thenmax = |S|U ←S
end ifend for
DiﬀGroups(mi ) ← DiﬀGroups(mi ) − dg + U
RN ← dg − U
for all n such that n ∈ RN do
tdg ← search(n, RN )for all atdg such that (atdg ∈ DiﬀGroups(mi ) ∧ ∃a ∈ tdg(a ∈ atdg)) do
DiﬀGroups(mi ) ← DiﬀGroups(mi ) − atdg + merge(atdg, tdg)
end forend forend ifend for

そこで本実装では，MASU から得た構文情報を用いて条件の解決を行う．
ま ず は じ め に ，3.3.2 に お い て PDG を 走 査 す る search(n, N ) を 実 行 す る 際 に ，sameBlock(f, t) という条件を追加する．すなわち，search(n, N ) を以下のように変更する．
Input: n:基点，N :探索可能頂点集合
Output: n から辺を辿って到達可能かつ N に含まれる頂点集合T ←nfor all e such that e ∈ ForwardEdges(n) do
if tonode(e) ∈ N ∧ sameBlock (fromnode(e), tonode(e)) thenT ← T + search(tonode(e), N )end ifend forreturn T

ここで，頂点 n を直接保持するブロックを ownerblock (n) とするとき，2 つの頂点 f ，tを保持するブロック文の一致性を判定する式 sameBlock (f, t) を式 (18) に定義する．
sameBlock (f, t) := (ownerblock (f ) = ownerblock (t))(18)

この制約を追加することで，同じブロック内に含まれる頂点のみが抽出頂点集合として特定されるため，前述の問題点を解決することが可能となる．しかし，この制約を追加することで，抽出頂点集合の大きさが各ブロック文までに制限されてしまい，抽出頂点集合の数が増大してしまうという課題点が生じる．図 4 の場合，制約の追加前はすべての文が 1 つの抽出頂点集合に含まれるが，制約を追加することでこれらが 2 つに分断される．
この問題を解決するために，ブロック文の集約処理をさらに追加する．以降このブロック
文集約処理について述べる．
あるブロック文 s について，そのブロックを構成する頂点集合を BlockNodes(s) とする．

条件 4:抽出頂点集合がブロック文をまたぎ，かつその一部分のみしか含んでいない

このとき，ブロック文の全頂点が最頂点集合に含まれるかを判定する式 allDN (s, mi ) を式

この条件は条件 2 と類似する条件だが，こちらは try 文などの，条件式を含まないブロッ(19) に定義する．

ク文によって生じる問題である．条件式を含まないブロック文の場合は制御依存関係が発生

allDN (s) := ∀n ∈ BlockNodes(s)(n ∈ DiﬀNodes(mi ))しないため，PDG の情報のみを用いてこの条件を満たすか否かを判別することはできない．

6

(19)

c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical Report

存手法では return 文を新規メソッドとして抽出する箇所に含める必要があり，パターンの

また，BlockStatements(m) をメソッド m のブロック文の集合とする．以上の定義を用適用に複雑な処理を要する．しかし，提案手法ではこの return 文を親クラスに引き上げるいて，3.3.2 の処理を行う直前に以下に述べる処理を追加する．
for all s such that BlockStatements(mi ) do
if allDN (s, mi ) thenn ← mergeNode(BlockNodes(s))
DiﬀNodes(mi ) ← DiﬀNodes(mi ) − BlockNodes(s) + n
end ifend forことができ，適用後のコードの複雑さが既存手法と比較して軽減されていると考えられる．
また，Apache Ant に付属しているテストケースを実行し，この修正の有無によって挙動が変化していないことを確認した．さらに，メソッドペアの各メソッドの頂点総数に占める共通頂点の割合を表す類似度 (2 ∗ |CloneN odeP airs|/|N odes(m0 )| + |N odes(m1 ))| が0.8〜0.9 という制約を設けて得られた候補のうち 27 の候補に対してパターンの適用を行っ

ここで，owner (N ) を頂点集合 N を直接保持するブロック文とするとき，mergeNode(N )たところ，いずれの候補についても適用前後で挙動に変化がないことが確認できた．しかは頂点集合 N を基に以下の条件を満たす単一頂点 n を生成する処理である．
BackwardEdges(n) = {e ∈ Edges(N ) : ((fromnode(e) ∈ N ) ∧ (tonode(e) ∈/ N ))}
ForwardEdges(n) = {e ∈ Edges(N ) : ((fromnode(e) ∈/ N ) ∧ (tonode(e) ∈ N ))}ownerblock (n) = owner (BlockNodes(owner (N )))し，可視性の調整等で作成したツールが示した抽出頂点集合以外の箇所を新規メソッドとし
(20)
(21)
(22)

て抽出する必要がある場合や，反対にツールが抽出頂点集合と示した箇所を共通部分として親クラスに引き上げることができる場合がいくつか存在した．

4.3 候補の提示

6. 関 連 研 究

実装したツールは適用対象の PDG とソースコードの提示機能を有している．ソースコー

提案手法と既存手法を比較した表を表 2 に示す．Juillerat らは，ソースコードから抽象

ド表示では，共通部分をハイライト表示し，差異部分については 1 つのメソッド内に抽出す

構文木 (Abstract Syntax Tree，以降 AST) を構築し，それをもとに Template Method パ

べき文を同じ色枠で囲んで表示することで集約の支援を行う．

ターンの適用を自動化する手法を提案している2) ．Juillerat らの手法では 2 つのメソッドのまた，対象メソッドペアにメソッド間の類似度などのメトリクスをいくつか定義し，利用

AST を比較し，同形部分木となっている箇所を共通部分とみなすことで Template Method者がそれらのメトリクスの閾値を自由に設定できる機能を実装した．これは，利用者によっ

パターン適用の自動化を実現している．この手法の特長として，適用後のソースコード例をて集約したいと考える条件が異なると考えられるため，利用者が自由に候補を選定可能にす

提示することができるという点と，実行に要する時間的，空間的コストが小さいという点ることで，集約したいと思える候補がより発見しやすくなると考えたためである．

5. 評が挙げられる．しかし，各頂点が表すコード片の文字列が一致するか否かで AST の頂点を価比較しており，ユーザ定義名の違いを吸収することはできず，また AST を用いているため
コードの順序の違いや表現の違いを吸収することができないという課題点が存在する．

提案手法を実装したツールを用いて，Apache Ant に対して適用実験を行った．Apache

政井らは，Juillerat らの手法と同様に AST を用いて Template Method パターンの適用

Ant の規模及びツールの実行に要した時間を表 1 に示す．

を支援する手法を提案している3) ．政井らの手法は適用後のソースコードを提示する機能は適用実験の結果，282 の適用候補が検出された．図 5 に検出された候補と適用例を示す．
この例では変数 op と image という，ユーザ定義名の異なる変数が使用されており，既存手

表 2 既存手法との比較
Table 2 Comparison between Existing Methods and Proposed Method

法ではこれらの変数に関わる return 文を共通部分とみなすことができない．そのため，既Table 1

用いるデータ構造
コード順序の違いの吸収
ユーザ定義名の違いの吸収表現の違いの吸収
実行コスト

表 1 実験対象と所要時間
Target Software System and Execution Time

行数

ファイル数

212,401829

所要時間と実験環境

110s (CPU: Xeon 2.67GHz(4 core)，メモリ: 4GB)

7

Juillrat らの手法2)
AST
×
×
×
◎

政井らの手法3)

提案手法

AST

PDG

×
×
4

c 2011 Information Processing Society of Japan

情報処理学会研究報告
IPSJ SIG Technical Report
TransformOperation

Pull Up: Code Clone
RotateexecuteDrawOperation()for (int I = 0; I < instructions.size(); i++) {ImageOperation instr = ((ImageOperation) instructions.elementAt(i));
if (instr instanceof DrawOperation) {return getPlanarImage(instr);}
return null;
Polymorphism
}

Scale

RotateScaleexecuteDrawOperation()for (int I = 0; I < instructions.size(); i++) {ImageOperation instr = ((ImageOperation) instructions.elementAt(i));
if (instr instanceof DrawOperation) {PlanarImage op = ((DrawOperation) instr).executeDrawOperation();op = performRotate(op);return op;}
return null;}TransformOperation
executeDrawOperation()
getPlanarImage(ImageOperation instr)

getPlanarImage(ImageOperation instr)

for (int I = 0; I < instructions.size(); i++) {ImageOperation instr = ((ImageOperation) instructions.elementAt(i));
if (instr instanceof DrawOperation) {PlanarImage op = ((DrawOperation) instr).executeDrawOperation();op = performRotate(op);return op;}
Extract
return null;}

getPlanarImage(ImageOperation instr)

PlanarImage op = ((DrawOperation)
instr).executeDrawOperation();op.performRotate(op);return op;

PlanarImage image = null;
performScale(image);
return image;

図 5 適用例
Fig. 5 An Example of Application of Template Method Pattern with Proposed Method

文部科学省科学研究費補助金若手研究 (B)(課題番号：22700031) の助成を得た．

持たないが，AST の比較時に特殊な処理を施すことで，Juillerat らの手法の課題点として挙げられているコードの順序の違いを吸収することに成功している．また，適用可能な候補

参 考に対し，適用時に新たにメソッドとして抽出すべき箇所の戻り値の型や引数等の検査を行文

献1) 肥後芳樹，楠本真二，井上克郎：コードクローン検出とその関連技術，電子情報通信学会論文誌， Vol.J91-D, No.6, pp.1465–1481 (2008).
2) Juillerat, N. and Hirsbrunner, B.: Toward an Implementation of the ”Form Template Method Refactoring”, 7th IEEE International Working Conference on Source
Code Analysis and Manipulation, pp.81–90 (2007).
3) 政井智雄，吉田則裕，松下 誠，井上克郎：類似メソッド集約のための差分抽出支援，
電子情報通信学会技術報告， Vol.110, No.60, pp.45–50 (2010).
4) Gamma, E., Helm, R., Johnson, R. and Vlissides, J.M.: Design Patterns : Elementsof Reusable Object-Oriented Software, Addison-Wesley Professional (1995).
5) Fowler, M., Beck, K., Brant, J., Opdyke, W. and Roberts, D.: Refactoring: Improving the Design of Existing Code, Addison-Wesley Professional (1999).
6) Ferrante, J., Ottenstein, K.J. and Warren, J.D.: The Program Dependence Graphand Its Use in Optimization, ACM Transactions on Programming Languages andSystems, Vol.9, No.3 (1987).
7) 肥後芳樹，楠本真二：プログラム依存グラフを用いたコードクローン検出法の改善と評価，情報処理学会論文誌， Vol.51, No.12, pp.2149–2168 (2010).
8) 三宅達也，肥後芳樹，楠本真二，井上克郎：多言語対応メトリクス計測プラグイン開発基盤 MASU の開発，電子情報通信学会論文誌 D， Vol.J92-D, No.9, pp.1518–1531(2009).

うことで適用容易性を判定し，提示する機能を備えている．ただし，AST の各頂点の比較
を値の比較で行っており，変数名のように頂点の値が文字列である場合，文字列の一致性によって頂点の比較を行っている．このため，Juillerat らの手法と同様にユーザ定義名の違いを吸収することができず，また表現の違いの吸収についても対応していない．
これらの既存手法と比較すると，提案手法の最大の長所としてユーザ定義名や表現の違いを吸収可能であるという点が挙げられる．また，提案手法を実装したツールでは適用可能な候補の特定を併せて行っており，適用対象を容易に発見できるという利点がある．しかし，提案手法は事前に PDG を構築する必要があるため実行コストが大きく，また適用例の提示機能や，抽出容易性の提示機能を備えていないという点も課題点として挙げられる．

7. あ と が き
本稿では，PDG を用いて Template Method パターンの適用が可能な候補を特定し，親クラスに引き上げるべき箇所と子クラスに残すべき箇所を利用者に提示することでコードクローンの集約を支援する手法を提案した．今後の課題として，パターン適用後のソース
コード例の提示，及び 3 つ以上の類似メソッドへの拡張などが挙げられる．
謝辞 本研究は，日本学術振興会科学研究費補助金基盤研究 (C)(課題番号：20500033)，

8

c 2011 Information Processing Society of Japan