社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

プログラム依存グラフを用いたリファクタリング候補の特定と可視化
兼光智子†

肥後 芳樹†

楠本真二†† 大阪大学 大学院 情報科学研究科
あらまし

リファクタリングは，保守の効率化において重要であるが，手動によるリファクタリングは誤りが混入しやすいため，その作業を自動化する手法及びツールが必要である．本稿では，メソッド抽出リファクタリングの候補を支援する提示する手法を提案する．メソッド抽出リファクタリングとは，メソッドの一部を別のメソッドとして切り出すことである．これまでの研究により，メソッド抽出リファクタリングは他のリファクタリングの前に頻繁に行われることが示されており，メソッド抽出リファクタリングを支援することは重要である．既存研究では行数や複雑さを基にメソッド抽出リファクタリングの候補を提示するが，本来メソッドは機能に基づいて分割することが望ましい．本稿では，文の間のデータの繋がりに着目する．データの繋がりの強い部分が一つの機能を表すと考え，メソッド抽出リファクタリングの候補を求め，自動的に提示する手法を提案する．提案手法では，リファクタリング可能なところを特定するだけでなく，リファクタリングすべきところを提示する．
キーワード

保守

リファクタリング プログラム依存グラフ

Identifying and Visualization Refactoring Candidates for Extract
Method using Program Dependence Graph
Tomoko KANEMITSU† , Yoshiki HIGO† , and Shinji KUSUMOTO†† Graduate School of Information Science and Technology, Osaka University
Abstract Refactoring is important for eﬃcient software maintenance. However, tools supports are highly requiredfor performing refactoring because manual operations in refactoring are troublesome and error prone. This paper
proposes technique that indicates candidates of ”Extract Method” refactoring automatically. Extract Method refactoring is to create a new method from a code fragment in an existing member. It is shown that the Extract Method
refactoring is performed prior to other refactoring, and it is important to support Extract Method refactoring.
The existing study proposes candidates of Extract Method refactoring based on linage and complexity. However
it is originally desirable to divide methods based on their functionalities. This paper use the strong connection ofdata between sentences. We deem that strongly-connected data expresses a single function. This paper proposes
technique that indicates candidates of Extract Method refactoring based on strongly-connected data.
Key words Maintenance Refactoring Program Dependence Graph

1. ま え が き
ソフトウェアの設計品質はソフトウェアの開発や保守を効率目されている．リファクタリングとはソフトウェアの外部的振る舞いを保ったまま，ソフトウェアの内部構造を改善することによりソフトウェアの設計品質を高める技術である [1]．

的に行うための重要な因子である．近年，ソフトウェアの応用

しかしながら，手動によるリファクタリングは次の問題を抱

分野の拡大と共にソフトウェアが大規模・複雑化し，ソフトウェえている．どのようなときリファクタリングが必要であるかをアの保守に要するコストが増加してきている．このため，ソフ示す厳密な基準が存在しないため，この判断には多くの経験やトウェアの設計品質の重要度はますます高まっている．しかし，知識を必要とする [1]．大規模ソフトウェアから手動でリファ

大規模ソフトウェアの開発プロジェクトでは複数のプログラマクタリングすべき箇所を特定するのは非常に手間がかかる．特が，さまざまな要求を満たすようにソフトウェアを開発，修正定した箇所をどのようにリファクタリングすべきか決定するにしていくため，ソフトウェアの設計品質を高く保つことは難しは多くの経験や知識を必要とする [1]．これらの問題を軽減すい．このような問題に対処するために，リファクタリングが注るためには，リファクタリング作業を支援する手法が必要であ—1—

る．本稿では，代表的なリファクタリングパターンの一つであるメソッド抽出リファクタリングを支援する手法を提案する．

1: String sample1(){

メソッド抽出とは，既存のメソッドから適度な規模のコード片

2:

if(this.trueOrFalse()){

3:if(null == this.getPath()){

を新しいメソッドとして抽出する作業である．

4:

Project proj = this.getProject();

本稿では，リファクタリング候補を提案するためプログラ5:

ム依存グラフ (Program Dependence Graph) を利用する．メ

6:}

ソッド抽出リファクタリングを必要とするメソッドの候補とし

7:

StringBuilder text = new StringBuilder();8:

text.append("String A");て，長すぎるメソッドや制御ロジックが複雑なメソッドなどがthis.setPath(proj.getBaseDir());

9:

text.append("String B");

あげられるが，本来メソッドは行数や複雑さではなく，機能に

10:

text.append("String C");

基づいて分割することが望ましい．本稿では，一つの機能を構

11:

text.append("String D");成する文の間ではデータのつながりも強いと考え，プログラム

12:

return text.toString();

13:}else{

依存グラフを利用しデータの強さを定義した．それを用いて

14:

メソッド抽出リファクタリングを必要とするメソッドの候補を

15:検出する．また，既存研究ではリファクタリング候補の提示が16: }return "";}

ソースコード上に示すものが多いが，本稿ではグラフを可視化(a) ソースコードして表示することによりデータのつながりや強さを視覚的に確認することが可能である．

2. 準

備

12. 1 プログラム依存グラフ
3

プログラム依存グラフ (Program Dependence Graph) とは，

2

ソースコードの文をノードとしノード間の依存関係をエッジで表したグラフである．PDG を用いることで，データの流れな4714

どプログラムの振る舞いを表現することができる．PDG では以下の二種類の依存関係を表す．

5

データ依存 次の全てを満たす場合，二つの文 s1 から s2 の89間にはデータ依存が存在する．

•

文 s1 で変数 v が定義されている•

文 s2 で変数 v が参照されている•

文 s1 から文 s2 までの間の実行パスに変数 v が再定義さ1011れていないパスが存在する

12

制御依存 次の全てを満たす場合，二つの文 s3 から s4 の間には制御依存が存在する．

•

文 s3 が条件節である•

文 s4 を実行するかどうかが，文 s3 の結果に依存する(b) PDG

図 1 ソースコードと PDG の例

PDG の例を図 1 に示す．図 1(a) のソースコードを PDG で表したものが図 1(b) である．データ依存辺は実線で，制御依存辺は点線で表している．
通常の PDG では，オブジェクトのメソッド呼び出しは，全2. 2 メソッド抽出リファクタリング
メソッド抽出リファクタリングとは，メソッドの一部を新たなメソッドとして切り出すことであり，次の手順で実行される．てそのオブジェクトへの参照となるが，本稿で用いる PDG は，（ 1 ） 新たなメソッドとして抽出する文を選択する

オブジェクトの状態が変更となる文では，データの参照と代入（ 2 ） 選択した文をコピーし新たなメソッドとして定義するが行われると考える．図 1 にて，例を示す．図 1(a) の 7 行目

（ 3 ） 元の文を削除し新たに定義したメソッドへの呼び出しから 12 行目の文について考える．通常の PDG であれば，7 行に置き換える目の文から，8 行目から 12 行目までそれぞれにデータ依存辺メソッドが機能に基づき分解されることで保守性や再利用性が存在する．つまり，7 行目から 5 本のデータ依存辺が出るこが高まる．また，他のリファクタリングの前に実行されることとになる．しかし，本稿で用いる PDG では，8 行目から 11 行も多く重要でありこれまで多くの研究がされている．

目のメソッド append の呼び出しにて，text の中の状態が変わ

メソッド抽出可能な文の集合には以下の条件が必要である [1]．

るためそれぞれ変数 text の参照と代入と考える．図 1(b) のよ

選択範囲内から選択範囲外へのデータ依存辺が一本以下

うにデータ依存辺が引かれる．

•である

•

条件節内の return 文がない

—2—

また，Murphy-Hill らは，開発時実際に行われたリファクタ
01 public void method(int x){

01 public void method(int x){

リングの内容を調査してまとめた [2]．その結果，ある程度ま02

int i = 0;02

int i = 0;

とまった開発を行った後集中してリファクタリングを行うより，

03

int t = 0;03

int t = 0;04

04

開発の途中にリファクタリングを何度か行う場合の方が多いことが分かった．

i=x+1;

05

i=x+1;

if (x>0){06

if (x>0){

丸山らは，基本ブロックに基づきメソッド抽出リファクタリ

07

i=i+2;

07

t=t+3;

ングの候補を自動的に抽出する手法を提案した [3]．プログラム

08

t=t+3;

08}

05
06

全体からではなく，プログラムの基本ブロックで構成される領

09}

09

method2(x,i);10System.out.print("i:"+i);10System.out.print("t:"+t);

11System.out.print("t:"+t);11 }ログラマはリファクタリング対象のコードにおいて着目する変12数を指定し，ツールにより生成された候補から適切な候補を選

12 }13 public void method2(int x, int i){
14if (x>0){15i=i+2;

16}

17System.out.print("i:"+i);域（部分ブロック）からコードを抽出する．この手法では，プ択する．実験により，単一の基本メソッドから異なる大きさや引数を持つさまざまなメソッドを抽出することが出来ることを確認した．

18 }Tsantalis らは，丸山らの手法を発展させ，プログラム全体に対して適切なリファクタリング候補を自動的に提示する手法(a) メソッド抽出前(b) メソッド抽出後を提案した [4]．丸山らの手法では，メソッド抽出後のプログラムが振る舞いを保たない場合を指摘し，そのような候補を除外

図2

メソッド抽出の際，文が複製される場合する．また，丸山らの手法では着目する変数を指定する必要があるが，Tsantalis らの手法では，プログラム中の全てのメソッ•

break や continue などによる選択範囲外への実行フローがない

ド全ての変数に対してスライスの候補を計算する．そのため，開発者は解析前に変数を指定する必要がなく，解析後に出力さまた，条件節の内外の文を同時に抽出対象とした場合，そのれた複数のリファクタリング候補から適切なものを選ぶだけで条件節を元のメソッドと新しいメソッドの両方に複製する必要よい．実験により，システム設計者が実際にリファクタリングがある．図 2 に例を示す．図 2(a) がメソッド抽出する前とし，を行いたい候補を提示できたことを示した．

7 行目と 10 行目を新たなメソッドとして抽出する場合を考える．6 行目の if 文は，7 行目の実行に必要なので 6 行目も新た4. 提 案 手 法なメソッドとして抽出する範囲に含める．しかし同様に 6 行

PDG の可視化によるメソッド抽出リファクタリングの候補

目の if 文は，8 行目の実行に必要なので，元のメソッドにも残を提示する手法を提案する．メソッドは機能別に分割されるべす必要がある．よって，6 行目の if 文は元のメソッドと新しいきである．ノード間のデータ依存辺が多いノードの集合が一つメソッドの両方に複製されることとなり，メソッド抽出後は図の機能を表すと考えた．PDG の形状から各ノード間のデータ2(b) のようになる．

依存の強さを推測し，それを可視化時のノード間の距離として

3. 関 連 研 究反映させる．データのつながりが強いほどノード間の距離を短

Murphy-Hill らは，メソッド抽出リファクタリングを視覚的集合を，メソッドとして抽出すべき文の集合とする．ノード間に補助するツールを提案した [1]．提案したツールは，Selectionの距離を定義したグラフを表示することで，リファクタリング

Assist，Box View，Refactoring Annotations の三つである．

を実行して適切か視覚的に判断することが出来る．

くする．そして，ノード間の距離が近く密集しているノードのSelection Assist は，エディタで文を選択する際，if 文の全範

図 3 に提案手法の例を示す．図 3(a) のソースコードを，PDG囲など完全な文の範囲をハイライトで表示するだけであり，利とし提案手法によりノードを配置したものが図 3(b) である．8用者が手動でソースコードを選択する必要がある．複数行に行目にはデータ依存辺が 4 本入っており，10 行目にはデータ依またがる文や if 文の範囲を容易に確認することが可能である．

存辺が 2 本入っている．8 行目に入るデータ依存辺の本数の方

Box View は，コードのネスト構造をボックスで表示する．エが多いため，そのデータ依存辺の元の 3,5,6,7 行目のノードがディタで文を選択すると対応するボックスの色が変化し，ボッ8 行目のノードに近く配置されている．10 行目へ入るデータ依

クスを選択すると対応する文が選択状態となる．Refactoring

存辺の元である 2,8 行目のノードは離れて配置されている．こAnnotations は，ソースコード上にコントロールとデータのフの場合，ノードが密に配置されている 3,5,6,7,8 行目をメソッド

ローを矢印で表示する．実験により，彼らの提案した視覚的な抽出リファクタリングの候補とする．

補助ツールを使用した方が，より早く正確にリファクタリング

以下にノード間の距離として具体的に三種類のパラメータをが行えた．しかし，それらのツールでメソッドとして抽出する

定義する．これらの関係にあるノードは別のメソッドとして分文の選択は，人がソースコードを見て考える必要があり，またけるべきではないと考えられる．vi (i = 1, 2, 3) は各パラメー

その選択はソースコード上で連続した文に限られている．

タの影響を表す定数であり，ユーザがツール上で変更すること—3—ながりが強いと考える．この依存関係を Spread Data Depen01 public void method(int x, objectA test){dency(SDD) と定義し，この関係にあるデータ依存辺の長さを02

int i = 0;短くする．SDD のデータ依存辺の長さを以下のように定義す

03int t = 0;

る．n は，一つの文から出るデータ依存辺の数である．

04

if (x>0){05

int a = test.getA();06

int b = test.getB();07

int c = test.getC();

08

i = t + a + b + c + 1;

distanceSDD =

v2
n(2)

4. 3 Gathered Data Dependency
多くの変数をある文で参照している場合．

09}

10

System.out.println(i);a,b,c を考える．
例えば，次のような変数'$

int a = coeﬃcients.getA();(a) ソースコード

int b = coeﬃcients.getB();
int c = coeﬃcients.getC();
Answer ans =4

QuadraticFormula.getAnswer(a, b, c);&%

このようにメソッド呼び出しの準備などまとまった機能を表52していると考えられ，それらのつながりは強いと考える．この637依存関係を Gathered Data Dependency(GDD) と定義し，こ8の関係にあるデータ依存辺の長さを短くする．GDD のデータ依存辺の長さを以下のように定義する．m は，一つの文へ入るデータ依存辺の数である．

10(b) PDG

distanceGDD =図 3 提案手法による PDG の配置

5. 実

v3m(3)

装が可能である．
提案手法をツール ReAF(Refactoring Automated Finding)

4. 1 Atomic Data Dependency
ある文で定義された変数が一度しか参照されていない場合．

として実装した．入力は，対象とするソースコードを含むフォル

tmp を考える．
例えば，次のような変数
ダであり，対象言語は，Java である．ツールを実行すると，メ

ソッド単位の PDG が表示される．グラフ内の各エッジの長さは

ﬁnal java.lang.Object tmp = objectA;

上記パラメータに基づいている．構文解析部には MASU（注 1）を，objectA = objectB;objectB = tmp;

グラフの可視化には Jung（注 2）を使用している．

ツールの外観を図 4 に示す．左端にクラスとメソッドを階層

データ依存辺が一つのみ存在する場合であり，そのデータ依表示しており，そこから一つメソッドを選択する．選択すると存辺の両端のノードは同じメソッドにまとめておくと考えられ右端にそのメソッドの PDG グラフが表示され，中央にはソーる．この依存関係を Atomic Data Dependency(ADD) と定義スコードが表示される．グラフ上部のパラメータで微調節し，し，この関係にあるデータ依存辺の長さを短くする．ADD のノードが密集している範囲を選択する．選択したノードの集データ依存辺の長さを以下のように定義する．

合が新たなメソッドとして抽出可能な場合は「OK」と表示し，distanceADD = v1(1)

抽出不可能な場合は「NG」の表示とともに抽出不可能となる原因を強調表示する．また，選択したノードに対応するソース

4. 2 Spread Data Dependency

コード上の文を強調表示する．

ある文で定義した変数を他の多くの文で使用している場合．
例えば，次のような変数
tax_rate を考える．


ﬂoat tax_rate = 0.05;

グラフでのノードの大きさは，ネストが深いものほど小さく表示しており，制御構造も視覚的にわかりやすく表示している．
図 4 にて適用したソースコードは，M. Fowler によるリファ

int taxA = articleA.getPrice() * tax_rate;

クタリングに関する本の中でも使用されている例である [5]．ク

int taxB = articleB.getPrice() * tax_rate;

ラス Customer の中のメソッド statement のグラフを表示してint taxC = articleC.getPrice() * tax_rate;

よく参照される変数は重要な値であり，その参照関係はつ（注 1）：http://sourceforge.net/projects/masu/（注 2）：http://jung.sourceforge.net/—4—

図 4 ReAF

いる．レンタルショップの料金計算のうち，レンタルポイントに関連する部分がグラフの右に密な部分として提示できた．

6. 実

験

候補は提示されたか，提示された場合は実際にリファクタリン
グを実行したいか考える．ツールの実行順序は，半分が先にReAF を残りの半分が先にプラグインを実行した．
その後，各ツールの提示した候補についてやツールの使用感

6. 1 実 験 対 象

についてアンケートを行った．アンケートの項目は，以下の三コンピュータサイエンスを専攻している学部四年から博士後点についてそれぞれ四段階で質問した．

期課程三年の学生 14 人に対して ReAF と既存ツールとの比較実験を行った．半分の 7 人は自分が研究で作成している Java のソースコードに対して適用した．自分が作成したソースコードなので内容に熟知しており，開発の途中にリファクタリングを行うことを想定している．残りの 7 人は著者らで指定したソースコードに対して適用した．対象としたソースコードは他の学•可視化による提示がリファクタリング候補を見つけるのに役に立ったか•

ツールの操作性はよかったか•

リファクタリング候補を見つけるのにそのツールを再び利用したいか

6. 4 実 験 結 果

生が研究用に開発したソースコードであり，他人の書いたソー

6. 4. 1 リファクタリング候補の特徴スコードに対してリファクタリングすることを想定している．

ツールにて表示された候補のメソッドごと内容を表 1 に示す．

6. 2 比 較 対 象

メソッド単位で提示されたリファクタリング候補について，被比較対象とする既存ツールは，関連研究で述べた Tsantalis

験者が実際にリファクタリングを行いたいものであった場合，らの手法を用いた「JDeodrant」である [4]．基本ブロックに有用な候補提示としている．ReAF は，無用な候補より有用な基づいたスライスにより，リファクタリング候補を提示する．

候補提示が多く，また JDeodorant より多く有用な候補を提示

Tsantalis らにより Eclipse のプラグインとして実装されていすることが出来た．

る．対象とするプロジェクトやクラスを指定し，解析開始ボタ

また，ReAF が良い結果であったメソッド，JDeodorant がンを押すとリファクタリング候補を表に一覧として提示する．

良い結果であったメソッドについて行数を比較した．ReAF がその中から一つ候補を選択すると，その候補で抽出対象となる良い結果であったメソッドとは，ReAF が有用な候補を提示し文がソースコード上でハイライト表示になる．さらにその状態でリファクタリングボタンを押すと，リファクタリング前後の表 1 ツールの提示したリファクタリング候補内容ごとのメソッド数

ソースコードを比較でき，よければそのままリファクタリング

ツール 提示された候補の内容メソッド数を実行することも可能である．

ReAF

有用な候補提示27

無用な候補提示17

有用な候補提示24

6. 3 実 験 方 法
あらかじめ，各自がリファクタリングを行いたいメソッドを三つ用意し，その同じメソッドに対して二つのツールを適用す

JDeodorant

無用な候補提示8

候補提示なし12

る．その結果を見て，そのメソッドに対するリファクタリング—5—

JDeodorant が無用な候補を提示または候補提示がなかったメ

JDeodorant は，メソッドによっては出力候補が多く全てを確ソッドであり，JDeodorant が良い結果であったメソッドとは，認するのに時間がかかる．

ReAF が無用な候補を提示し JDeodorant が有用な候補を提示または候補提示がなかったメソッドである．結果を表 2 に示す．

7. あ と が き

JDeodorant は全体では平均行数が 63.286 であったが，一つだ

本稿では，プログラム依存グラフを利用しメソッド抽出リ

け外れて 270 行のものがあり，それを除くと残りは 103 行以下ファクタリングの候補を提示する手法を提案した．具体的には，で平均は 47.385 となった．ReAF は，文をノードとして表示

データ依存辺を用いデータのつながりの強さを定義し，データするためメソッドが長いほうがノード数が多くなる．そのため，のつながりの強い文の集合をメソッド抽出の候補とする．提案

ノードの疎密が明白になり良い候補を提示できたと考えられる．

手法を用いてリファクタリングの支援を行うツールを開発し，

6. 4. 2 使 用 感 想

学生に対して実験を行った．その結果，グラフ操作など操作性各ツールを使用した感想のアンケート結果を表 3 に示す．の点で問題がありリファクタリング決定時間は長かったが，短ReAF では，可視化の評価が高かったが操作性の評価が低い．

い解析時間で結果を出力することができ，14 人中 12 人からグ可視化の評価については，14 人中 12 人がグラフによる可視化

ラフによるリファクタリング候補提示は直感的でわかりやすいが直感的で候補を見つけやすいと回答した．操作性の評価が低という意見が得られた．

い原因は，グラフ操作や範囲選択の問題など本質的な機能以外今後の課題として，グラフ操作や柔軟な選択方式などユーのユーザビリティによるものであり，それらの改善によって評ザビリティの改良があげられる．また，グラフ上で密な部分や価は上がると考えられる．JDeodorant では，可視化・操作性ユーザーが別のメソッドとして分けたくない文同士のノードをともに評価が高かった．しかし，操作性の評価が高い理由は，一つにまとめる機能を追加することを考えている．

eclipse の慣れた画面で操作が行えるなどプラグインに起因した謝辞ものであった．さらに JDeodorant では，一文含むか含まない

本研究は一部，文部科学省「次世代 IT 基盤構築のための研かだけで他は同じ文などの似たような候補が多く提示され，確究開発」（研究開発領域名：ソフトウェア構築状況の可視化技術

認する際大変であるという意見もあった．ReAF では，同じ範の開発普及）の委託に基づいて行われた．また，日本学術振興

囲はグラフで確認できるためそのような候補を提示することは会科学研究費補助金基盤研究 (A)(課題番号:21240002) およびない．

(C)(課題番号:20500033)，文部科学省科学研究費補助金若手研6. 4. 3 時

間究 (B)(課題番号:22700031) の助成を得た．

各ツールでの解析時間と候補を提示してからリファクタリングを行うか決定するまでの時間を比較した．結果を表 4 に示
す．JDeodorant の時間には，候補提示がないメソッドに関する時間は含んでいない．ReAF の方が解析時間は短く，決定時間と時間合計は JDeodorant の方が短い．ReAF の解析時間はソースコード全体の PDG 構築時間であるが，JDeodorant ではさらに各メソッド内の変数ごとにスライスを計算するので時間がかかる．どちらも解析時間より決定時間の方が長かった．
時間がかかる原因として，ReAF はエッジの長さを決めて初めからノードを見やすい位置に配置できないので，グラフを整えるのに時間がかかる．グラフを整えるための時間は，グラフの操作性の悪さからさらに時間がかかっていると考えられる．
表 2 ツールによる差があるメソッドの比較
メソッド行数

平均値

最小値

ReAF

68.83325178

16270(103)JDeodorant 63.286(47.385)
表3JDeodorant

操作性 継続利用

可視化 操作性

継続利用

表 4 ツールの解析時間とリファクタリング決定時間

4412454393710662194033

最大値

35.3

1011001

最小値

0.02

3.214

2.286

2.714

3.286

3.143

2.9286

平均

8.2

数値平均

献

アンケート評価結果

ReAF
評価数値 可視化

最大値

文[1] E. Murphy-Hill and A. Black: “Breaking the barriers to
successful refactoring: Observations and tools for extract
method”, Proceedings of the 30th international conference
on Software engineeringACM New York, NY, USA, pp. 421–430 (2008).
[2] E. Murphy-Hill, C. Parnin and A. Black: “How we refactor, and how we know it”, Software Engineering, 2009. ICSE
2009. IEEE 31st International Conference onIEEE, pp. 287–297 (2009).
[3] K. Maruyama: “Automated method-extraction refactoringby using block-based slicing”, Proceedings of the 2001 symposium on Software reusability: putting software reuse incontextACM, pp. 31–40 (2001).
[4] N. Tsantalis and A. Chatzigeorgiou: “Identiﬁcation of extract method refactoring opportunities”, European Conference on Software Maintenance and ReengineeringIEEE, pp.
119–128 (2009).
[5] M. Fowler and K. Beck: “Refactoring: improving the designof existing code”, Addison-Wesley Professional (1999).

時間

ReAF

JDeodorant(s) 解析時間 決定時間

合計 解析時間

決定時間

合計

11621170

223600.8 621.2

2023.70.01

12.4

305.1 313.4

35.6

142.8 178.4

16.0—6—