第 3 章 プログラム変更の特定手法 17
3.4 クラス情報の比較
3.4.4 編集操作によるプログラム要素の削除・追加の特定
3.4. クラス情報の比較 31
図 3.3: 誤った対応付けの例
以上の手順を経て，Mt1に残されたメソッド（Mt1に存在してMt2に存在しな いメソッド）を，時刻t1から時刻t2の間に削除されたメソッドとみなし，メ ソッドの削除（DM）として特定する．また，Mt2に残されたメソッド（Mt1 に存在せずMt2に存在するメソッド）を，時刻t1から時刻t2の間に追加さ れたメソッドとみなし，メソッドの追加（AM）として特定する．
図 3.3では，フィールド”int a”と”int b”の2つのフィールドが存在するクラス を持つ構文解析可能な時刻t1のスナップショットSt1に対して以下の変更を行い，
構文解析可能な時刻t2のスナップショットSt2が作成されたものを表している．図 に示した3つの状態のソースファイルのうち，真ん中の状態のソースファイルで も構文解析が可能となるが，ここでは便宜上St1とSt2の間では構文解析可能なス ナップショットが作成されなかったと仮定する．
1. フィールド”int a”の削除
2. フィールド”int b”を”c”に名前変更
このとき，St1 から得られたCIt1は”int a”，”int a”をフィールドとして持ち，
St2から得られたCIt2は”int c”をフィールドとして持つ．そして，これらの変更 の間に構文解析可能なスナップショットが得られずこれら2つのクラス情報を比較 することになる場合，単純にフィールドを比較するだけでは（アルゴリズム 2の 3〜14行目の処理を行わなければ），CIt1の”int a”とCIt2の”int c”のペアを名前 変更の行われた同一のフィールドとみなし，実際に行われた変更内容とは誤った 結果を提示してしまう．そしてこのような例はクラスやメソッドについても同様 に起こりうる．
そのため本手法では，二つの構文解析可能なスナップショットから得られたクラ ス情報に含まれるプログラム要素を比較するだけでなく，それらのスナップショッ トの間に行われた編集操作から削除・追加されたと判断できるプログラム要素を 事前に対応付けの候補から除外することで，特定の精度を向上させている．
編集操作によるプログラム要素の削除の特定は，時刻t1のスナップショットSt1 に存在したプログラム要素を構成するすべての文字が削除されているかどうかで 判断する．詳細については，時刻t1のスナップショットSt1に存在したプログラム 要素pが時刻t1から時刻t2の間に行われた編集操作ops(t1,t2)によって削除さ れたかどうかを判別するアルゴリズムをアルゴリズム 4に示す．
入力は編集時刻kがt1< k < t2となる全ての編集操作を編集時刻が若い順に並 べたリスト（operations）と，削除されたかどうかを判別する対象であるプログラ
ム要素（entity）と，時刻t1のスナップショットのentityが記述されているソー
スファイル（sourcef ile）である．本アルゴリズムにおいては，sourcef ileは最初 の文字から最後の文字までが連なる文字のリストと捉えている．また，entityは 表 3.1に示したクラス，メソッド，フィールドのどれかであるため，プログラム 要素の開始位置，終了位置を表すオフセットstart,endをもつ．出力は判定結果
（result）として，entityが編集操作によって削除されたプログラム要素であれば trueの値を，そうでなければfalseの値を返す．
3.4. クラス情報の比較 33 判定の手順としてはまず，sourcef ileに存在するすべての文字を一意に識別す るために，sourcef ileに存在するすべての文字に対してその文字が時刻t1におけ
るsourcef ile上で何文字目なのかを表す初期オフセット（initialOf f set）を記録
しておく．さらに，sourcef ile上のある文字の初期オフセットがentityの範囲内 であれば，その文字をentityを構成する文字の集合（entityCharacters）へ追加 する（1行目〜8行目）．
次に，sourcef ileに対してoperationsに存在するすべての編集操作を適用する．
ソースファイルに対する編集操作の適用は3.2 節に示したとおりである．このと き，編集操作の適用によって削除された文字はsourcef ileから除外される（9行目
〜11行目）．
最後に，sourcef ileに残された文字の集合の中に，entityを構成する文字集合
entityCharactersの文字が一つも残っていない場合はentityは削除されたと判断
してresultにtrueを入れて返し，文字が一つでも残っている場合は削除されてい
ないと判断してresultにfalseを入れて返す（12行目〜17行目）．なお，12行目
のsourcef ileに残された文字の集合とentityに残された文字の集合の比較では，1
行目〜8行目で記録しておいた初期オフセットを用いる．
Algorithm 4: 編集操作によるプログラム要素の削除の特定 Input: operations
Input: entity Input: sourcefile Output: result
1 entityCharacters← φ;
2 fori = 0 to |sourcefile|-1 do
3 c← sourcefile[i];
4 c.initialOffset← i;
5 if entity.start ≤ c.initialOffset ∧c.initialOffset ≤ entity.end then
6 entityCharacters← entityCharacters∪c;
7 end
8 end
9 fori = 0 to |operations|-1 do
10 adopt(sourcefile, operations[i]);
11 end
12 if |entityCharacters ∩ sourcefile| =φthen
13 result← true;
14 end
15 else
16 result← false;
17 end
また，編集操作によるプログラム要素の追加の特定は，時刻t2のスナップショッ トSt2に存在したプログラム要素を構成するすべての文字が編集操作によって挿入 された文字かどうかで判断する．時刻t2のスナップショットSt2に存在しているプ ログラム要素pが時刻t1から時刻t2の間に行われた編集操作ops(t1,t2)によっ て追加されたかどうかを判別するアルゴリズムをアルゴリズム 5に示す．
入力は追加されたかどうかを判別する対象であるSt2に存在するプログラム要 素（entity）と，アルゴリズム 4と同様にoperationsとsourcef ileを持つ．また 同様にentityはstart, endをもつ．出力は判定結果（result）として，entityが 編集操作によって追加されたプログラム要素であればtrueの値を，そうでなけれ ばfalseの値を返す．
判定の手順としてはまず，sourcef ileに存在するすべての文字に対してその文 字が挿入された文字ではないことを表す値を判定用変数（isInserted）に記録し ておく．また，operationsに存在するすべての編集操作の挿入文字に対して，そ の文字が挿入された文字であることを表す値をisInsertedに記録しておく（1行 目〜11行目）．こうすることで，編集操作をすべて適用した後の時刻t2における
sourcef ileから，そのsourcef ileを構成するそれぞれの文字が時刻t1〜時刻t2の
間に行われた編集操作によって挿入された文字かどうかを判別できるようになる．
次に，sourcef ileに対してoperationsに存在するすべての編集操作を適用する．
ソースファイルに対する編集操作の適用は3.2 節に示したとおりである．このと き，編集操作の適用によって挿入された文字は再び削除されない限りsourcef ile に残る（12行目〜14行目）．
最後に，sourcef ileのentityの範囲に存在するすべての文字について挿入され た文字かどうかを調べ，その範囲にあるすべての文字が編集操作によって挿入さ れた文字であった場合はentityは追加されたと判断してresultにtrueを入れて 返し，挿入されていない文字（St1のsourcef ileに元から存在していた文字）が一 つでも存在する場合は追加されていないと判断してresultにfalseを入れて返す
（15行目〜21行目）．