修正前後のプログラムの差分に基づく書換えパターン生成についての研究—書換えパターンの記述範囲決定の支援—
2009SE015 朝岡百合子 2009SE096 神谷優希
指導教員：吉田敦

1

はじめに%before
if ((${v:ID_VAR} = ${cast:EXPR}malloc(${size:EXPR})) == NULL)${stmt:STMT}$;%after${v} = ${cast}my_malloc(${size});%end

ソフトウェア開発では，既存の処理と同じような処理を記述するときに，既存の記述をコピーするなど，ほぼ同じ記述をそのまま書くことがある．その際に複数行にわたる類似した記述であるコードクローン [3] や，コー
図 1 書換えパターンの例 [5]ドクローンの条件には満たないが，重複した内容を持つ
void test (void)
定型的な記述などが発生する．それらの記述に変更を加{char *p;える場合，すべての変更箇所に同様の書換え作業が必要
if ((p = (char *)malloc(sizeof(char) * 100)) == NULL){
fprintf(stdrr, "no memory!\n");となる．このとき，変更箇所の見落としがあれば変更漏
exit(1);れが発生したり，単純作業の繰り返しの修正で記述ミス}
proc(p);が起こる可能性がある．それらの人為的なミスを防ぐに
free(p);}はパターンによる書換えが効果的である．しかし，書換えパターンは，書換えを行いたい箇所の書換え漏れがな
図 2 TEBA を用いた書換えの入力例
く，かつ，書換えを行わない箇所の記述を含まないように作る必要がある．部分的な抽象化や，書換え箇所の前後に出現する記述の共通性に基づいた制約を記述するな 2 プログラム書換え系ツール
ど，人の手で生成するには手間がかかる．
本研究ではプログラムの書換えに TEBA を用いる．
本研究では，修正前と後の 2 つのプログラムの差分を TEBA を用いると編集中のテキストから書換え対象の用いた書換えパターンの生成支援を提案する．具体的に 断片をコピーすることで書換え作業を記述でき，抽象構は，ユーザがプログラムの一箇所だけを修正し，修正前 文木などの他の表現に写像する必要がない．それにより，後の差分から書換えパターンの雛形を生成する．さらに， 書換えパターンの生成支援ツールの実装が簡単になる．
ユーザに指示を求め，補正を行う．雛形はユーザが必要に
図 1 は TEBA の書換えパターン，図 2 と図 3 は図 1応じて編集することを前提とする．書換えパターン生成 を使用した書換えの入力と出力を示す．TEBA の書換えの際に，パターンを直接記述するよりも実際にプログラ パターンでは書換え前を表現する記述を「変換前パタームを書換える方が書換え作業を具体的に考えやすく，書 ン」，書換え後を表現する記述を「変換後断片」と呼ぶ．
換え後の正しさも検証しやすい．なお，本研究では，プ 書換えパターンは図 1 のように%before の直後に変換前ログラム書換え系として TEBA[5] を利用し，C 言語のプ パターンを，%after の直後に変換後断片を記述する．パログラムを書換え対象とする．
ターン変数は可変部分となる箇所に記述し，一般化をす
複数の修正対象の間で異なる記述を吸収する方法とし る．変換前パターンでは “${名前:型}”，また変換後断片て，パターン変数などを用いた一般化が必要である．し では “${名前}” と記述する．型は適合する構文要素を表かし，一般化によって，書換えない箇所もパターンに適 し，字句の種別か，ユーザが定義する字句パターンの名合する可能性がある．そこで，一般的には，同一の処理の 前を用いる．
前後に共通の記述が出現することから，書換え箇所の記述に加え書換え箇所の前後に出現する記述も含めて書換 3 書換えパターンの生成方法パターンを生成することで適用範囲を絞る．そのために， 3.1 書換えパターンの生成方法の全体の流れ
実際に書換パターンを適用して書換えられた箇所から正書換えパターン生成方法全体の流れを図 4 に示す．入
しい書換え箇所をユーザに選択させ，それらの前後に出力として修正前および修正後プログラムを与えると，雛現する共通する記述をパターンに追加する．なお，ユーザに選択させる理由は，正しい箇所を自動的に判定する
void test (void)
ことが難しいことにある．
{
char *p;
技術的な課題は，書換えパターンに追加する記述の範p = (char *)my_malloc(sizeof(char) * 100);proc(p);
囲の決定方法と，その記述範囲の差異を吸収する方法をfree(p);明らかにすることである．
}
図 3 TEBA を用いた書換えの出力例

形となる「初期パターン」を生成する．初期パターンは， 4 書換えパターンの記述範囲決定について差が生じた範囲だけを切り出し，目的となる他の箇所に4.1 記述範囲決定の処理についても適用するよう手作業で記述の一部を一般化したものである．修正前プログラムにその書換えパターンを適用し， 書換えパターンが適用された箇所の中で，書換えの目その結果を差分としてユーザに提示する．書換え対象外 的の箇所を「書換え必要箇所」，それ以外の箇所を「書換の箇所が書き変わっていたら，書換え対象の箇所をユー え不要箇所」と呼ぶ．書換え必要箇所の前後で共通するザが指定する．その情報を元に再度書換えパターンを補 字句を持つ範囲を「共通範囲」と呼ぶ．
図 6 に図 4 の必要箇所選択後のパターン生成処理の詳正し，再び書換え結果をユーザに提示する．ユーザが目細を示す．初期パターンによる書換えを適用したプログ的のパターンを得られるまで，これを繰り返す．
ラムと修正前プログラムの差分からユーザは書換えられた箇所を確認し，必要箇所を選択する．必要箇所を入力すると，記述範囲を出力する．差分として抽出された字句をすべて含む構文要素を書換えパターンに記述し，その後，書換え必要箇所の前後に出現する記述の種別の並びを比較し，記述範囲を決定する．
書換え必要箇所の前後に出現する記述を TEBA を用いて解析し，属性付き字句系列から種別の並びを比較をする．属性付き字句系列とは，抽象構文木を字句系列で表現したもので，すべての字句は種別属性を持ち，その値は字句解析の字句定義で与えられる名前である．種別で比較をすることで識別子などの差異を吸収する．また，図6 の共通範囲抽出では記述範囲に必要な部分の記述の差異を吸収するために一般化を行う．
図 4 書換えパターン生成方法全体の流れ
図 7 に必要箇所の共通範囲を用いた記述範囲決定の流れを示す．選択された書換え必要箇所の前後に出現する記述を抽出し，任意の 2 つの書換え必要箇所の前後に出3.2 初期パターン生成の詳細
現する字句の種別の並びを比較，共通範囲を抽出し記述
図 5 に図 4 の初期パターン生成の詳細を示す．プログ範囲とする．書換え必要箇所が 3 つ以上ある場合，すでラムの修正前後の差分から，差異が生じた範囲の断片をに抽出された共通範囲と共通範囲抽出を行なっていないそのまま記述したパターンを生成する．次に，他の書換任意の 1 つの書換え必要箇所を比較し共通範囲を求める．
えたい箇所に適用するために，手作業で記述の一部をパその共通範囲が，すでに抽出した共通範囲より小さい場ターン変数に置き換える一般化を行い，初期パターンを合，新しく求めた共通範囲を全箇所に対する共通範囲と生成する．
して選択する．この選択をすべての書換え必要箇所に対して繰り返し，共通範囲を決定する．なお，提案手法では必ずしも正確に書換え必要箇所だけに限定できないので，不必要な書換えについては手作業で戻せるよう，書換え前の状態を前処理命令の#ifdef で囲って残す．

図 5 図 4 の初期パターン生成の詳細

3.3

書換えパターンに記述する範囲

書換えパターンに記述する修正前後のプログラムの範囲を「記述範囲」と呼ぶ．差分から，直接変更した箇所と前後を含めた共通部分を特定し，記述範囲を決定する．

図 6 必要箇所選択以降の処理の手順

…
/*必要な記述範囲 開始*/
if(option == ’q’)
col = get_col (n_col[n-1]);//この関数内の引数が異なる

if (col == NULL){
error (0, errno, _("col_get failed"));//この関数を書換え
ok = false;}
else
set_next_col(col);/*必要な記述範囲 終了*/
ok &= change_file_owner (fts, ent, uid, gid,required_uid, required_gid, chopt);…

図 9 書換え必要箇所 2[2]

図 7 書換え必要箇所の共通範囲を用いた記述範囲決定の流れ…
/*必要な記述範囲 開始*/
if(option == ’p’)
col = get_col (f_col);//この関数内の引数が異なる
if (col == NULL){
error (0, errno, _("col_get failed"));//この関数を書換え
ok = false;}
else
set_col(col);/*必要な記述範囲 終了*/
ok &= change_file_owner (fts, ent, uid, gid,required_uid, required_gid, chopt);…

図 8 書換え必要箇所 1[2]4.2字句の種別の並びの抽象化の方法

書換え必要箇所の前後に共通範囲を求める際に，完全に一致する箇所を求めると 1 つの字句の種別が異なるだけでも範囲がそこまでに留まり，必要な箇所だけへの限定が十分に行えない．そこで，一部の字句の種別の差異を許容する方法を用いる．図 8 と図 9 は書換えを行いたい箇所の例である．例えば，図 8 と図 9 では，変更された箇所の前にある col = get_col (f_col); とcol = get_col (n_col[n-1]); の記述は字句は完全には一致しないが，意味を考えれば，本来は共通範囲に含めるべき文である．そこで，プログラムの意味を考える
うえで重要な部分だけに着目するよう抽象化を行う．本研究で抽象化を行う箇所は以下の 2 つである．

• 制御文の条件式が異なる箇所• 同一名の関数呼び出しの実引数が異なる箇所
これらの箇所を任意の式を表すパターン変数に置き換え，詳細を捨象する．
図 10 は図 8 と図 9 を書換え必要箇所として，抽象化せずに生成した書換えパターン，図 11 は抽象化を用いて生成した書換えパターンを示す．

5

評価と考察

生成された書換えパターンが目的の箇所のみに適用されるか評価をする．評価実験は，図 4 の書換えパターン生%beforeif (col == NULL){
error (0, errno, _("col_get failed"));//この関数を書換え
ok = false;}
else
set_next_col(col);%afterif (col == NULL){
get_error (errno);//書換えられた関数
ok = false;}
else
set_next_col(col);図 10 種別の並びがすべて一致した共通範囲の書換えパターン
成についてツールを実装し，初期パターンと記述範囲のパターン変数は手動で整合させた．GNU Core Utilies[2]にコードクローン検索ツールである NiCad[1] を適用し，コードクローンセットを得た．そのコードクローンセッ
ト内の 1 つのコードクローンに対して一箇所変更を加え，差分を抽出し，書換えパターンを生成した．評価方法は以下の通りである．

1. 修正前後のコードクローンの差分から書換えパターンを生成
2. プログラムに適用し，書換え必要箇所だけに適用されているかを確認%beforeif(option == ’q’)
col = get_col (${expr:EXPR*});//この関数内の引数が異なる
if (col == NULL){
error (0, errno, _("col_get failed"));//この関数を書換え
ok = false;}
else
set_next_col(col);%afterif(option == ’q’)
col = get_col (${expr});//この関数内の引数が異なる
if (col == NULL){
error (0, errno, _("col_get failed"));//この関数を書換え
ok = false;}
else
set_next_col(col);%end

図 11 種別の並びを抽象化し，生成した書換えパターン

1 %\begin{verbatim}
2 …
3 /*必要な記述範囲 開始*/
4 if (!target_directory)
5 {
6if (2 <= n_files&&7target_directory_operand (file[n_files - 1],8&sb, &new_dst))
9
target_directory = file[--n_files];10
else if (2 < n_files)
11
error (EXIT_FAILURE, 0,
12_("target %s is not a directory"),
13
quote (file[n_files - 1]));//この関数を書換え
14 }
15 /*必要な記述範囲 終了*/
16 …
17 %\end{verbatim}

1 %\begin{verbatim}
2 …
3 /*必要な記述範囲 開始*/
4 if (!target_directory)
5 {6assert (2 <= n_files);
7if (target_directory_operand (file[n_files - 1]))
8target_directory = file[--n_files];9
else if (2 < n_files)
10error (EXIT_FAILURE, 0,
11_("target %s is not a directory"),
12
quote (file[n_files - 1]));//この関数を書換え
13 }
14 /*必要な記述範囲 終了*/
15 …
16 %\end{verbatim}

図 13 書換え必要箇所 2[2]図 12 書換え必要箇所 1[2]提案手法の精度を適合率と再現率で評価した．それぞれ以下の式 1，式 2 で求める．
適合率 =書き換わった書換え必要箇所の数
実際に書換えられた箇所の数(1)%beforeerror (EXIT_FAILURE, 0,_("target %s is not a directory")${expr:EXPR*});%aftertarget_error(${expr});%end

図 14 記述範囲を広げる前の書換えパターン

い差分が抽出される場合がある．本研究では作業内容に一致する差分を手作業で選択し使用した．2 つ目に一般化の自動化があり，本研究では図 4 の初期パターン一般化
5 つのコードクローンセットに対して評価を行なったとは手作業で行った．これら 2 つを自動化することで，よころ，適合率は平均 0.87，再現率は平均 1.0 となった．再現り労力と時間の削減が可能となる．3 つ目として記述範率 1.0 からすべての書換え必要箇所に書換えが適用される
囲を広げる方法の改善がある．本研究では，記述範囲をことがわかった．しかし，提案手法だけでは書換え必要箇広げるために抽象化を行う箇所を 2 つ提案し，評価を行所に限定して書換えられないので，適合率が 0.87 となった．
なったが，高い精度で記述範囲を決定できるよう改善す
図 12 と図 13 に提案手法では失敗した例を示す．図 14 はることが求められる．
記述範囲を広げる前の書換えパターンである．図 12 は 11行目の error 文を target_error 文に書き換え，図 13 も 参考文献
同様に 10 行目の error 文を target_error 文に書き換え[1] C.K. Roy and J.R. Cordy, “NICAD: Accurate Deる．記述範囲として図 12 と図 13 の 4 行目までの記述が必
tection of Near-Miss Intentional Clones Using Flexi要であった．図 13 で 6 行目に assert (2 <= n_files);ble Pretty-Printing and Code Normalization,” Proc.
が存在したので，抽象化を用いても図 14 を最適な必要なICPC, pp.172–181, Jun. 2008.
記述範囲まで広げられなかった．これを改善するために[2] GNU Project, “Coreutils — GNU core utilities,”
は，種別の並びの抽象化方法を拡張していく必要がある．
http://www.gnu.org/s/coreutils/, Jan. 2011.
評価方法として，コードクローンセットから書換え必要箇所をあらかじめ選択したが，プログラムの意味を考 [3] 神谷 年洋，“コードクローンとは，コードクローンが引き起こす問題，その対策の現状，” 電子情報通信学
慮していないので，現実的な書換え対象の選び方とは異会誌，vol.87，no.9，pp.791–797，Sep. 2004．
なる．前後に出現する文脈が類似したコードクローンを再現率 =書き換わった書換え必要箇所の数
書換えを行いたい箇所の数(2)書換え必要箇所として設定するなどより現実的な書換えを用いた評価が必要である．

6

おわりに

本研究ではプログラムに存在するコードクローンや定型的な記述を書換えるパターン変換の自動生成の支援を目指し，修正前，修正後プログラムの差分から書換えパターンを生成し，書換え必要箇所の前後に出現する共通の記述を自動的に書換えパターンに組み込む手法を提案した．実装と評価を行い，提案手法によって高い精度で書換え箇所を目的の箇所に絞り込めることを確認した．
今後の課題は次の 3 つである．1 つ目は差分の選択の自動化である．差分の抽出では LCS を求めるアルゴリズムを使用したが，LCS は複数存在し，作業内容と一致しな[4] 神谷 年洋，楠本 真二，井上 克郎，“コードクローン検出における新手法の提案および評価実験，” 電子情報通信学会技術研究報告，ソフトウェアサイエンス，
vol.100，no.570，pp.41–48，Jan. 2001．
[5] 吉田 敦，蜂巣 吉成，沢田 篤史，張 漢明，野呂 昌
満，“属性付き字句系列に基づくソースコード書き換え支援環境，” 情報処理学会論文誌，vol.53，no.7，
pp.1832–1849，Jul. 2012．