空間的距離

空間的距離とは，連続する2つの変更が行われたソースコード上の位置がどの くらい近いのかを指す．

ここで，プログラム要素の追加，削除，移動は，そのプログラム要素全体が変 更されたと考えるのが自然である．また，Javaにおいて，プログラム要素の名前，

引数，型（または戻り値の型）は，そのプログラム要素に対して決められた位置

（レイアウト上，そのプログラム要素の名前の近く）に存在するため，集約を行う かどうかの基準を用意する必要はないと考えた．以上より，空間的距離による集約 は，2つの変更がどちらもメソッド本体の書き換え(CMB)のときのみ活用する．

Algorithm 7: 集約候補の特定手順 Input: temporalThreshold

Input: spatialThreshold Input: allProgramChanges Output: candidateChangeGroups

1 change ←null;

2 preChange ← null;

3 changeGroup ← φ;

4 groupCount ←0;

5 fori = 0 to |allProgramChanges|-1 do

6 preChange ← change;

7 change ←allP rogramChanges[i];

8 if preChange = null∨

9 ( preChange.target= change.target ∧

10 temporalDistance(preChange, change)< temporalThreshold ∧

11 spatialDistance(preChange, change) < spatialThreshold) then

12 changeGroup ←changeGroup ∪ change;

13 end

14 else

15 candidateChangeGroups[groupCount++]← changeGroup;

16 changeGroup ←φ;

17 changeGroup ←changeGroup ∪ change;

18 end

19 end

Algorithm 8: 空間的距離の計算アルゴリズム Input: beforeCMB1

Input: afterCMB1 Input: beforeCMB2 Input: afterCMB2 Output: spatialDistance

1 N P_{CM B1} ←GetNodeSet(afterCMB1, beforeCMB1);

2 N PCM B2 ←GetNodeSet(beforeCMB2, afterCMB2);

3 spatialDistance ←1 + |N P_{CM B1}|+|N P_{CM B2}|- |N P_{CM B1} ∩N P_{CM B2} | ×2

4.2. 集約候補の特定 43

Algorithm 9: GetNodeSet(baseCode, otherCode) Output: nodeSet

1 diffStart← null;

2 diffEnd← null;

3 fori = 0 to min(|baseCode|, |otherCode|)do

4 if diffStart =null ∧ baseCode[i] 6=otherCode[i] then

5 diffStart← i;

6 end

7 if diffEnd =null ∧ baseCode[|baseCode|- i- 1] 6=otherCode[|otherCode|- i -1] then

8 diffEnd← |baseCode|-i-1;

9 end

10 end

11 baseAST← baseCodeを構文解析して得られたAST;

12 startNodeSet← φ;

13 endNodeSet ← φ;

14 foreachnode∈node|node∈baseAST∧nodeは特定の種類のノード do

15 if node.start ≤ diffStart∧ diffStart <node.end then

16 startNodeSet← startNodeSet∪node;

17 end

18 if node.start ≤ diffEnd ∧ diffEnd <node.end then

19 endNodeSet ←endNodeSet ∪ node;

20 end

21 end

22 nodeSet← startNodeSet∩endNodeSet;

表 4.1: 空間的距離の計算に用いるノードの種類

構文要素 NodeType

ブロック Block

do文 DoStatement for文 ForStatement if文 IfStatement switch文 SwitchStatement try文 TryStatement while文 WhileStatement

拡張for文 EnhancedForStatement

もし空間的距離の値があらかじめ設定されていた値より小さい場合，それらの変 更のペアが集約候補となる．

2つのメソッド本体の書き換えの変更（CMB1,CMB2）から，それらの空間的 距離を計算するアルゴリズムをアルゴリズム 8に示す．アルゴリズム 8は入力は CMB1 とCMB2のそれぞれの変更前後のメソッド本体のソースコードである．ま たそれぞれのソースコードについて，CMB1の変更前のメソッド本体のソースコー ドをbeforeCMB1，CMB1の変更後のメソッド本体のソースコードをafterCMB1， CMB2 の変更前のメソッド本体のソースコードをbeforeCMB2，CMB2 の変更後 のメソッド本体のソースコードをafterCMB2 とする．出力はCMB1 とCMB2 の 空間的距離を返す（spatialDistance）．

空間的距離の計算では，CMB1 の変更前後のメソッド本体のソースコード（be-foreCMB1とafterCMB1）から，afterCMB1を構文解析することで得られるAST 上における，CMB1の編集箇所となったAST要素（AST上に存在するノード）の

集合N S_{CM B1}を作成し，同様にCMB2 の変更前後のメソッド本体のソースコー

ド（beforeCMB2 とafterCMB2）から，beforeCMB2 を構文解析することで得ら れるAST上における，CMB2 の編集箇所となったノードの集合N S_{CM B2}を作成 する（1行目〜2行目）．ここでは，変更前後のソースコードからAST上の変更 箇所を表すノードの集合を取得するために，サブルーチン GetNodeSet(baseCode,

otherCode)（アルゴリズム9）を呼び出している．そしてこのようにして得られた

二つのノードの集合N S_{CM B1}とN S_{CM B2}に存在するノードを比較して，3行目に 示す計算式で空間的距離を求める（3行目）．

GetNodeSet（baseCode, otherCode）ではまず，baseCodeとotherCodeのテキ スト上の差分からこれらのコードの間で行われた変更における書き換え範囲の始

4.2. 集約候補の特定 45 点diffStart と終点diffEnd を特定する．書き換え範囲の特定では，baseCode と

otherCode の先頭からそれぞれ1文字ずつ比較し，比較した文字が初めて異なっ

たオフセットを書き換え範囲の始点diffStartとし，同様に末尾からそれぞれ1文 字ずつ比較して比較した文字が初めて異なったオフセットを書き換え範囲の終点 diffEndとする（3行目〜10行目）．

次にbaseCodeを構文解析することで得られるAST（baseAST）を作成し， diff-Start とdiffEnd から，baseAST 上での編集箇所を表すノードの集合を作成する．

baseAST 上での編集箇所を表すノードの集合の作成では，baseAST 上に存在する

表4.1に示すノードの中でdiffStartのオフセットがそのノードの範囲内となるノー ドの集合（startNodeSet），diffEndのオフセットがそのノードの範囲内となるノー ドの集合（endNodeSet）をそれぞれ作成し（14行目〜21行目），startNodeSetと endNodeSet に共通して存在するノードの集合（nodeSet）を出力として返す（22 行目）．表 4.1の「構文要素」は各ノードが構文上で何を表しているのかを意味 し，「NodeType」はEclipseがorg.eclipse.jdt.core.domで提供するAPIによって作 成される，ASTを構成するノードのタイプを意味する．

ここで，本手法ではCMB1とCMB2の空間的距離を計算するために，CMB1の 編集箇所をafterCMB1 から作成されたAST上のノードの集合で，CMB2 の編集

箇所をbeforeCMB2から作成されたAST上のノードの集合でそれぞれ表現し，異

なるAST上のノードの集合同士を比較することで空間的距離を求めている．通常，

お互いに基準としているASTが異なるノードの集合同士を比較することはできな い．しかし本手法においては，afterCMB1 から作成されたASTとbeforeCMB2か ら作成されたASTがそれぞれ持つ構造と値については同一と見なすことができ，

同じ構造と値を持つAST上のノードの集合を表現しているN S_{CM B1}とN S_{CM B2} は，擬似的に比較し空間的距離を計算することが可能となる．

afterCMB1 とbeforeCMB2から作成されるASTはそれぞれ，前回行われた変更 CMB1 を行った後のメソッド本体のASTと今回行われた変更CMB2を行う前の メソッド本体のASTである．そのため仮に，ある構文解析可能なスナップショッ トS₁のメソッドX()に対してCMB1 による編集操作とCMB2による編集操作が 続けて行われ，CMB1 とCMB2による編集操作の直後にそれぞれ構文解析可能な スナップショットS2，S3が作成された場合は，afterCMB1 とbeforeCMB2から作 成されるASTはどちらもS₂のメソッドX()のASTとなり，これら2つのASTは 完全に同一とみなせる．

また仮に，先ほどの例でCMB1による編集操作とCMB2による編集操作の間に 空白文字やコメント，Javadoc，import文などの挿入や削除がおこなわれ，CMB1に よる編集操作の直後にスナップショットS₂，空白文字やコメント，Javadoc，import 文などの挿入や削除の直後にスナップショットS3，CMB2による編集操作の直後

にスナップショットS4がそれぞれ作成された場合は，そのときのafterCMB1 は S₂，beforeCMB2 はS₃のものとなり，これら2つのソースファイルから作成され るASTはそれぞれのノードのオフセットなどが異なる場合があり，完全に同一で はない．しかし，S2とS₃の間にはメソッド本体のASTの構造や値を変化させる 書き換えは行われていないため，afterCMB1 とbeforeCMB2 からそれぞれ作成さ れるASTの構造と値は同一とみなせる（仮にメソッド本体の構造や値に変化があ る場合はS₂とS₃の間でCMBが特定される）．

少なくともafterCMB1 とbeforeCMB2 から作成されるASTの構造や値が同じ であれば，N P_{CM B1}とN P_{CM B2}のノードの集合の比較は可能である．ノードの集 合の比較の際には，その前にあらかじめafterCMB1 とbeforeCMB2からそれぞれ 作成された2つのASTをそれぞれ同じ探索アルゴリズムで探索し，それらのAST に含まれるノードに対して，探索した順番を表すIDを割り振っておく．そして，

N S_{CM B1}とN S_{CM B2}に存在するそれぞれのノードの比較する際（アルゴリズム8

の3行目）に，それらに存在するノードに割り振られたIDが同じかどうかで判断 すればよい．