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

信学技報
TECHNICAL REPORT OF IEICE.

抽象構文木を利用したファイル間のコード移動検出
藤本

章良†

肥後

芳樹†

松本淳之介†

楠本真二†† 大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5
E-mail: †{a-fujimt,higo,j-matumt,kusumoto}@ist.osaka-u.ac.jp
あらましソフトウェア開発において，開発者がソースコードの差分を理解することは重要である．ソースコードの差分を検出するツールとして GumTree がある．GumTree は編集前後のソースコードを入力として与えると，内部で抽象構文木を生成し，削除・挿入・移動・更新といった操作を抽象構文木のノード単位で検出する．しかし，GumTree は 1
つのファイルの差分しか計算できないため，ファイルをまたいだソースコードの移動を検出できないという問題点がある．そこで本研究では，プロジェクトに含まれる全てのソースファイルから 1 つの抽象構文木を構築し，ファイルをまたいだソースコードの移動を検出する手法を提案する．そしてオープンソースソフトウェアに対して提案手法を用いて実験を行った結果，全てのプロジェクトにおいてファイルをまたいだソースコードの移動を検出でき，最大で 2,406,459個のファイルをまたいだ移動を確認できた．また，検出結果を確認したところ，ファイルをまたいだソースコードの移動が発生する際，いくつかの特徴が得られた．
キーワード

差分，GumTree，抽象構文木

1. は じ め に差分を出力するツールである．AST のノードはソースコードのトークンとほぼ一致する．したがって，AST を利用することで，ソフトウェア開発において，バージョン管理システムの使用

diff コマンドに比べ，より適切な範囲で差分を出力可能になる．

は必須といえる．バージョン管理システムを用いた開発においさらにノードの削除や挿入以外にも，更新や移動を検出できる．

て，バージョン間のソースコードの差分を正確に，理解しやすい

GumTree 及び GumTree を改良したツールが出力した編集ス

形で開発者に示すことは重要である．開発者がソースコードのクリプトは多くの研究で利用されている. 例えば，Maven のビ

差分を理解することで，ソースコードの振る舞いの変更を把握しルドファイルの解析 [2] やバグ修正パターン検出の自動化 [3]，やすくなるからである．例えば，ある変更の後にバグが発生したバージョン管理システムを利用する際のコミットメッセージの場合，差分を確認することで，そのバグの原因となるソースコー

生成 [4]，API のコードのサジェスト [5] などに用いられている．

ドの特定が容易となる．そのため，ソースコードの差分を表示す

しかし，GumTree にも問題点が存在する．1 つのファイルのるツールが開発されており，Git をはじめとする多くのバージョ

差分しか計算できないため，ファイルをまたいだソースコードのン管理ツールには，diff コマンドが組み込まれている．

移動を検出できない点である．ファイルをまたいだソースコー

しかし，diff コマンドには 2 つの問題点が存在する．1 つ目

ドの移動は，リファクタリングにおいて頻繁に行われる．このよの問題点は，出力される差分の粒度が粗いという点である．diff

うな「移動」と出力されるべき変更が，「削除と挿入」として出コマンドは行単位でソースコードを比較するため，ある行の一部

力されてしまい，その結果，開発者がソースコードの変更に対し分のみが変更された場合でも，その行全体が変更されたとして出て誤った認識を持つ可能性がある．

力する．また，いくつかの行を if 文や for 文で囲んだブロック

そこで本研究は，1 つのファイルの差分しか計算できない

内に出し入れした場合，そのブロック全体が変更されたと出力す

GumTree を拡張して，プロジェクト全体の差分を計算し，ファる．このため，実際に変更が行われた箇所の把握が困難になる．

イルをまたいだソースコードの移動を検出できるようにするこ

diff コマンドの出力結果に基づいて，より詳細に変更箇所をハとを目的とする．複数のソースファイルからそれぞれ AST を生

イライトするツールも存在するが，後者の例ではハイライトが行成し，それらをまとめた 1 つの AST を構築する．変更前後のプわれない．2 つ目の問題点は，編集操作が削除と挿入の 2 種類しロジェクト全体の AST を比較することで，ファイルをまたいだか存在していない点である．すべての編集操作が削除または挿

ソースコードの移動を検出可能にする．

入の操作で出力されるため，それ以外の操作を行った場合，開発者が意図した差分が出力されない可能性がある．

提案手法を 8 個のオープンソースソフトウェアに適用し，ソー
スファイルをまたいだ移動を検出できることを確認した．またこれらの問題点を解決するためのツールとして，GumTree [1]それらが誤検出でないかどうかの検証を行った．さらに，提案手が提案されている．GumTree は，バージョンが異なる 2 つの法によって検出された，ファイルをまたいだソースコードの移動

ソースファイルを入力として与えると，抽象構文木（以下，AST）

を目視で確認し，ソースコード，及びファイル名といったファイを生成し，それらを比較することにより，AST のノード単位のルの情報にどのような特徴があるかを分析した．

—1—

変更前のファイル

変更後のファイル

Main.java

変更前

Main.java

public class Main {void main() {int[] a = {1, 2, 3};
println(ave(a));
}

0
1

0

3

2

1

2

挿入

4

4

変更前の AST変更後の AST

5

移動
更新

図 1 GumTree の差分検出

2. 準

int ave(int[] a) {int sum = Calc.sum(a);return sum / a.length;
}

削除

備

}

Calc.java
public class Calc {int sum(int[] a) {int sum;for (int i: a)sum += i;return sum;}}削除

2. 1 抽象構文木（AST）
AST は，ソースコードを構文解析して得られる木構造のデータである．AST の各ノードは以下の要素から構成されている．

変更後

public class Main {void main() {int[] a = {1, 2, 3};
println(Calc.ave(a));}}
Calc.java
public class Calc {int sum(int[] a) {int sum;for (int i: a)sum += i;return sum;}int ave(int[] a) {int sum = sum(a);return sum / a.length;
}

}

挿入

移動

更新

図 2 実際の編集操作と GumTree の出力が異なる例

図 2 の例では，ファイル Main.java と Calc.java が同時に

AST の各ノードは，木構造上の親ノードへの参照

変更されたと仮定する．この変更では，ファイル Main.java にを持つ．ただし，根ノードの親は存在しないので何も保持しない．

存在したメソッド ave() が Calc.java に移動されている．この

ラベル：変更の前後で，GumTree を用いてそれぞれのファイルの差分を

親ノード：

値：

if 文や変数宣言といった文法上の型を表す．

メソッド名や変数名などのラベル以外の情報である．

出力すると，Main.java の編集スクリプトはメソッド ave() の

2. 2 GumTree の差分検出

削除，Calc.java の編集スクリプトはメソッド ave() の挿入とGumTree は入力として，変更前後のソースファイルを受け取なる．しかし，実際に行われた操作を表現するには，メソッド

り，AST のノード単位の編集スクリプトを出力する．編集スク

ave() の移動の方が適切である．この違いにより，開発者がソーリプトとは，変更後のソースコードを得るために変更前のソース

スコードの変更について誤った認識を持つおそれがある．

コードに適用された編集操作の列である．GumTree は，削除・開発者に差分を表示する際，複数のファイルの変更を考慮す

挿入・移動・更新のうち行われた操作と，その操作が行われたることで，より適切な差分を出力できると著者らは考えた．そこAST のノードの情報を，編集スクリプトとして出力する．

で，本研究では複数のファイルが変更された際に，ファイルをま

GumTree は入力された変更前後のソースファイルから，それたいだ移動を検出する手法を提案する．ファイルをまたいだ移ぞれの AST を生成する．この 2 つの木の違いを差分として出力動を検出することによって，開発者がソースコードの変更をよりする．木構造の差分を計算するために，GumTree はマッチング

正しく理解できるようになると著者らは考えた．

を行う．マッチングとは，変更前後の AST のノードの対応付け

4. 提 案 手 法を行う処理である．対応付けられたノードは，変更の前後で同じノードとして扱われる．マッチングの結果と AST を参照し，変4. 1 概要

更前の AST に対して，どのノードが削除・挿入されたか，どの提案手法の概要を図 3 に示す．提案手法の入力は，変更前後

ノードの位置が変更されたか，どのノードの値が更新されたか，のプロジェクトに含まれる全てのソースファイルであり，出力はどのノードは変更が行われていないか，といった情報を得る．

編集スクリプトである．まず，入力として与えられたソースファ

図 1 は，GumTree の差分検出方法を模式的に表している．変イルから，それぞれに対応する AST を生成する．それらの AST

更前後のファイルから生成した AST にマッチングを行い，ノーを用いて，プロジェクト全体の AST を構築する．このプロジェドの対応付けがされている．図 1 では，マッチングの結果を数

クト全体の AST は，変更前と変更後で 1 つずつ作られる．プロ

字で表している．この例では，3 番のノードは変更前にしかない

ジェクト全体の AST の構築方法は，4. 2 節で述べる．

ため削除，5 番のノードは変更後にしかないため挿入，と編集ス

次に，構築したプロジェクト全体の AST に対してマッチング

クリプトに出力される．4 番のノードは変更前後のどちらにも存を行い，差分を計算する．プロジェクト全体の AST の差分計算在しているが，親のノードが変わったため移動と出力される．1には，GumTree の差分を計算する処理を再利用した．そして，番のノードは，更新と出力されている．更新は，変更の前後に同

GumTree の手法を用いて得られた編集スクリプトを出力する．

じノードが存在し，その値が変更された場合に出力される．

しかし，単純にプロジェクト内の全てのソースファイルから 1
つの AST を構築し差分を計算すると，計算に多大な時間を要し

3. 研 究 目 的

たり，移動を検出する精度が下がったりする可能性がある．そこ

GumTree は，1 つのファイルの変更について，どのような操で，4. 3，4. 4 節のような工夫を加え，これらの問題を回避する．

作が行われたかを検出できる．しかし，一度に複数のファイルに対して変更が行われることがあり，そのような場合，ファイルをまたいだソースコードの移動を検出することはできない．

4. 2 プロジェクト全体の AST の構築
プロジェクト全体の AST の構築を図 4 に示す．まず，プロ
ジェクト全体の AST を構築するため，ノードを 1 つ作成する．

—2—

入力

変更のある
ファイルを抽出

各ファイルから
AST を生成

マッチング
差分計算

プロジェクト全体のAST を構築

編集スクリプト生成

出力InsertDeleteDeleteMove
Move
UpdateInsert
Move
・・・

変更前

変更後

変更前後の
ソースファイル

変更のある
ソースファイル

各ソースファイルから生成された AST

プロジェクト全体の AST

編集スクリプト

プロジェクト全体の差分

図 3 提案手法の概要
各ソースファイルから生成した
AST をまとめる根ノード

根ノード

ソースファイルから生成した AST

A.java変更前

A.javavoid foo() {int num = 1;/* some code */}変更なし

void bar() {int num = 1;/* some code */}変更なし

B.javaプロジェクトに含まれる
ソースファイル

void foo() {int num = 1;/* some code */}B.java削除

図 4 プロジェクト全体の AST の構築

変更後

挿入

移動

void bar() {int num = 1;/* some code */}更新

図 5 移動していないのに移動と誤って検出した例

このノードを根ノードとし，ソースファイルから生成した AST①同じ名前のファイルから生成した AST をマッチング

を子ノードとして加えていく．生成した AST を子ノードとして②プロジェクト全体のAST をマッチング

加える順番は，ソースファイル名のアルファベット順である．

4. 3 変更のないファイルの除外
プロジェクトに含まれる全てのソースファイルからプロジェク

変更前

ト全体の AST を構築すると，プロジェクト全体の AST のノード数が増え，計算時間が長くなってしまう．また，変更されていないファイルから誤って変更があると検出される可能性がある．
そこでプロジェクト全体の AST を構築する段階で，ソースファ

変更後
1 段階目でマッチングされたノード
2 段階目でマッチングされたノード

イルごとに変更の有無を確認する．変更があるソースファイルから生成した AST だけをプロジェクト全体の AST に加える．

図 6 2 段階のマッチング

ファイル内容の変更の有無は Myers のアルゴリズム [6] を用いて調べる．得られた結果が，•全く変更がない•

行・スペース・タブの削除，挿入のみ

イルの部分木を取り出して，マッチングを行う．その後，プロ
ジェクト全体の AST についてマッチングを行う．
ファイルをまたいだ変更と比べて，ファイルをまたがない変のどちらかに該当する場合，そのファイルから生成される AST

更の方が多いと考えられる．そこで，同一ファイルの変更前後では，プロジェクト全体の AST には加えない．

の AST のマッチングを先に行う．これは AST ノードのマッチ

4. 4 2 段階のマッチング

ング候補を同一ファイル内のみにすることで，マッチング候補の差分の検出対象を 1 つのファイルからプロジェクト全体に拡大

数を減らし，適切にマッチングを行うことが狙いである．さらした際，変更されていないにも関わらず，類似したソースコードに，2 段階目のプロジェクト全体のマッチングでは，1 段階目で間で移動と出力される場合がある．これは，AST がプロジェク

まだマッチングされていないノードの中からマッチングを行い，ト全体に拡大される事により，GumTree がノードを適切にマッマッチングの候補を限定する．これによって，類似したソース

チングできていないことが原因である．誤検出の例を図 5 に示

コードが移動と誤検出される可能性を下げることができる．

す．この例では，変更の前後でメソッド foo()，bar() に含ま

図 5 の変更に対し，2 段階のマッチングを適用すると，1 段階

れる int num = 1; は変更されていない．しかし A.java の int

目の同一ファイルのマッチング時に，変更前後の A.java に含ま

num = 1; が B.java の int num = 1; に不適切にマッチングされる int num = 1; がマッチングされる．同様に，変更前後のれた結果，A.java から B.java に移動したと誤検出している．

B.java に含まれる int num = 1; がマッチングされる．この結適切にマッチングできない理由は，マッチング対象がプロジェ

果，int num = 1; に対する変更は行われていないと出力される．

クト全体に拡大されて候補が増えるため，適切なノードを探し出

5. 実

験

せないからである．そこで適切にマッチングするために，2 段階のマッチングを行う．2 段階のマッチングの方法を図 6 に示す．
まず，プロジェクト全体の AST の中から，同じ名前を持つファ提案手法を用いて，オープンソースソフトウェア（以下 OSS）
に対して実験を行った．実験の目的は次の 2 つである．

—3—

WorkbenchLayout.java（変更前）
private List getTrimContents(String areaId) {List trimContents = new ArrayList();Control[] children = layoutComposite.getChildren();for (int i = 0; i < children.length; i++) {// Skip any disposed or invisible widgets
if (children[i].isDisposed() || !children[i].getVisible()) {continue;}// Only accept children that want to be layed out in a particular// trim area
if (children[i].getLayoutData() instanceof TrimLayoutData) {TrimLayoutData tlData = (TrimLayoutData) children[i].getLayoutData();
if (tlData.areaId.equals(areaId)) {trimContents.add(children[i]);
}
}

}

}
return trimContents;

案手法を実行した際に，移動元と移動先のソースコードが大きく異なっているにも関わらず，ファイルをまたいだ移動であると出力された例である．原因として，検出対象を拡大したことにより，不適切なマッチングしてしまうことが考えられる．移動元と移動先のソースコードが異なっていた場合，提案手法がファイルをまたいだソースコードを適切に検出できるとはいえない．
提案手法が有効であることを確認するため，移動先に同様のソースコードが存在した場合，正しく移動を検出したと判断する．
目視確認をする際には，移動するノードを限定して確認する．

WorkbenchStatusDialogManager.java（変更後）
private boolean shouldAccept(StatusAdapter statusAdapter, int mask) {IStatus status = statusAdapter.getStatus();
IStatus[] children = status.getChildren();if (children == null || children.length == 0) {return status.matches(mask) || (handleOKStatuses && status.isOK());}
for (int i = 0; i < children.length; i++) {if (children[i].matches(mask)) {return true;}}
if (handleOKStatuses && status.isOK()) {return true;}
return false;}

図 7 移動元と移動先のソースコードが大きく異なる例

1. ファイルをまたいだソースコードの移動を検出できるか
2. ファイルをまたいだ移動にはどのような特徴があるか限定するノードの種類は，移動と検出された AST ノードの部分
木に含まれるノード数（以下，部分木の大きさ）によって決定した．ファイルをまたいだ移動を分析すると，移動する AST ノードのラベルの種類とその平均の部分木の大きさには傾向がある
ことが分かった．予備実験として，5. 1 節に含まれる OSS のうち，ArgoUML と Log4j，Tomcat に対して提案手法を実行した
際の，ファイルをまたいで移動したノードの種類ごとの平均の大きさを表 2 に示す．ただし，ファイルをまたいで移動したノードは種類が多いため，一部のノードを抜粋して掲載する．
目視確認では，平均的な部分木の大きさが大きいノードに関

以下では，この実験の内容について説明する．

して確認を行う．移動する部分木の大きさが大きいと，移動する

5. 1 実 験 対 象

ソースコードの量も多く，どのような機能が移動したかを開発者

GumTree [1] の評価実験に用いられた CVS-Vintage [7] に含が理解しやすくなると考えられる．ゆえに，部分木の大きさが大まれている OSS のうち，Git に移行されているソフトウェアをきい移動を正しく検出できるかを評価することが重要となる．

実験対象とした．実験対象の OSS を表 1 に示す．これらのプロ

移動する部分木の大きさが大きいノードを，有用な移動ノード

ジェクトは全て Java で開発されている．

と定義する．本研究では，有用な移動ノードとして MethodDec-

5. 2 実 験 方 法

laration，WhileStatement，ForStatement，IfStatement，Block

本研究では 2 種類の実験を行った．1 つ目が，ファイルをまたを選択した．目視確認では，ファイルをまたいで移動したこれらいだ移動を検出できているかの確認，2 つ目が，ファイルをまたのノードに対し，それぞれ最大 20 個をランダムに選び確認する．

いだ移動にはどのような特徴があるかを確認するための実験である．以下では，この 2 つの実験方法について説明する．

5. 2. 2 ファイルをまたいだ移動の特徴の確認
ファイルをまたいだソースコードの移動の特徴を調査する．ど5. 2. 1 ファイルをまたいだ移動の検出の確認のようなソースコードが移動しているか，変更の前後でのファイバージョン管理されている OSS に対し，全てのコミット前後

ル内容の違い，移動前後のファイル名の特徴，などを調べる．

でのソースファイルを，提案手法への入力として与える．検出し5. 3 実 験 結 果

た差分のうち，ファイルをまたいだ移動の数を計測する．

5. 3. 1 ファイルをまたいだ移動の検出の確認

次に，ファイルをまたいだ移動であると正しく検出できてい各 OSS とコミット数，ファイルをまたいだソースコードの移るか評価するため，検出されたファイルをまたいだ移動の中から動の検出数，検出された全ての移動数を表 3 に示す．ファイルを

サンプリングして目視確認を行う．図 7 は Eclipse に対して提またいだ移動の数の横に示されている括弧は，検出された全ての

表 1 実験対象の OSS プロジェクト

OSS 名

コミット数

実験対象の最終コミット日

移動に対するファイルをまたいだ移動の割合である．全てのプロジェクトで，ファイルをまたいだ移動が含まれることが分かる．

ArgoUML

16,1442015 年 1 月 11 日

dnsjava

1,771

2019 年 10 月 27 日

ノードのラベル

Eclipse（注 1）

29,8112019 年 11 月 17 日

MethodDeclaration

85.20

67.41

57.82

JHotDraw

763

2018 年 8 月 27 日

WhileStatement

159.08

61.75

74.63

JUnit 4

2,418

2019 年 11 月 2 日

ForStatement

104.27

40.66

58.21

Apache Log4j 2

10,7522019 年 11 月 1 日

IfStatement

117.97

23.83

30.65

Apache Struts

5,6972019 年 11 月 4 日

Block

53.25

50.17

39.86

Apache Tomcat

21,4922019 年 11 月 6 日

ImportDeclaration

2.00

2.00

2.00

FieldDeclaration

10.23

9.73

10.28

（注 1）
：org.eclipse.ui.workbench のみ調査した．Eclipse はプロジェクトの規模が非常に大きく，CVS-Vintage では eclipse.ui.workbench と eclipse.jdt.core
のみ調査している．eclipse.jdt.core に対しても実験を行ったが，実行時間が長く評価できなかったため，実験対象から除外した．

表2

移動したノードのラベルごとの平均の大きさ（一部抜粋）

ArgoUML Apache Log4j Apache Tomcat

Assignment

6.95

7.76

6.38

SimpleName

1.00

1.00

1.00

全体

10.26

8.55

7.69

—4—

100

Main.java

90

class Main {void read() {/* */}void write() {/* */}void prepare() {/* */}void execute() {/* */}}80

検出の適合率(%)

変更前

70
60
50
40
30
20
10
0
ArgoUML dnsjav a

Eclipse JHotDraw JUnit4

Log4j 2

StrutsTomcatMain.java

次に，ファイルをまたいだ有用な移動ノードがどの程度検出できたかを表 4 に示す．有用な移動ノードもファイルをまたいで移動していることが分かった．その数に注目すると，

MethodDeclaration，Block といったノードが移動する回数が多

変更前

void method() {while (!isDone()) {/* some codes */}doSomething();}

く，IfStatement が続く．WhileStatement や ForStatement の移と ForStatement の移動の数に大きな差がないことが分かった．
プロジェクトごとに，ファイルをまたいだ移動の検出精度の5. 3. 2 ファイルをまたいだ移動の特徴検出されたファイルをまたいだ移動の例を説明する．各ソース

C.java変更前

class C {void methodA() {/* */}void methodB() {/* */}}class Main {void prepare() {/* */}void execute() {/* */}}Sub.java

変更後

void extraction() {while (!isDone()) {/* some codes */}}Main.java

A.java変更後

abstract class A {void methodA() {/* */}}C.javaclass C extends A {void methodB() {/* */}}コードの例の紫色で示した部分が移動と検出された箇所である．
機能の分割・統合
大きいクラスが分割されて複数のクラスに分けられる時に，ファイルをまたいだメソッドの移動が検出された．その例を図 9

Main.java

図 10 メソッドへの切り出しのソースコードの例

適合率を二項分布に従うと仮定し，これを 95%信頼区間で表し以上の適合率で検出できていることが分かった．

class IO {void read() {/* */}void write() {/* */}}void method() {extraction();
doSomething();}動の数は比較的少ない．また Eclipse を除いて，WhileStatement

たのが図 8 である．その結果，半数以上のプロジェクトで 7 割

変更後

図 9 機能の分割のソースコードの例

プロジェクト名

図 8 ファイルをまたいだ移動の検出の適合率

IO.java

図 11 継承関係の変化のソースコードの例

スコードが移動される場合を確認した．移動前後のファイル名に示す．変更前は Main クラスに含まれていたメソッド read()に，Util，Helper といった名称が付く例が合計で 29 個あった．

と write() が IO クラスに移動している．この他にも，似た機能

またそれら以外は，元の名前と似た名称になることが多かった．

を持つクラスを統合するための移動もあった．

メソッドの移動以外にも，図 10 のような一部の処理のみを取

移動先のクラスが新たに作られる場合と，既存のクラスにソーり出してメソッド化するような変更があった．WhileStatement，

表 3 OSS での実験結果

ForStatement，IfStatement といったノードでこのような移動がOSS 名ファイルをまたいだ移動の数全ての移動の数見られた．メソッドの行数が長く，処理を別のメソッドに切り出

ArgoUML

9,645(10.6%)

91,005

すリファクタリングをした際に，このような移動が検出された．

dnsjava

1,591(0.488%)

326,041

Eclipse2,406,459(50.3%)

2,382,478

JHotDraw

5,477(0.639%)

847,494

継承関係の変化
クラス間の継承関係が変化するような場合に，ファイルをまたJUnit 4

15,160(0.14%)

102,043

いだ移動を検出した．図 11 は，新たに作成した抽象クラスに一Apache Log4j 2

22,191(9.57%)

209,618

部のソースコードが移動される例である．このような，具象ク

Apache Struts

20,027(11.3%)

176,458

ラスから抽象クラスへのソースコードの移動が多く検出された．

Apache Tomcat

51,932(1.55%)

335,490

反対に，抽象クラスから具象クラスへの移動も存在した．
その他にも，継承関係のある具象クラス間で，実装箇所の変更

表 4 有用な移動ノードの検出数

OSS 名

MethodWhile

ForSta- IfState-

Declaration Statement

tement

ment

Block

によるソースコードの移動も検出した．
短いソースコードの移動

ArgoUML

184

13

11

143

285

ファイルをまたいだ移動をするソースコードの中には，行数がdnsjava

91

0

1

25

18

短いソースコードも多く存在した．次のようなソースコードがEclipse49,91218308

JHotDraw

184

1

6

54

149

JUnit 4

373

1

2

9

219

Log4j 2740

8

912,800 79,038

96

583

Struts

459

8

6

187

527

Tomcat

1,040

16

14

1,113

2,448

挙げられる．

•

getter/setter（MethodDeclaration）•

return 文（Block）•

null チェック（IfStatement）

getter や setter の移動は，抽象クラスを追加した際によく見—5—られた．特に Tomcat では具象クラスから抽象クラスへの 13 個

分木の類似度を用いて，閾値が一定値を超えた場合にノードをの移動うち，6 個が getter または setter であった．

マッチングする．短いソースコードであれば，ソースコードの差

return 文はブロックの中に return; のように return 文のみ

異が出にくく類似度が高くなりやすい．そのため，よりマッチンが含まれるようなソースコードの移動である．このような移動グされやすくなり，検出される可能性が高くなると考えられる．

はほとんどのプロジェクトで検出された．

IfStatement で null チェックを行うソースコードの移動も検7. 妥当性の脅威出された．この if 文内では，新規インスタンスの作成のみや提案手法は特定のプログラミング言語に依存しないため，

return 文など短いソースコードがほとんどである．また，このGumTree を適用可能なプログラミング言語すべてにおいて適用

移動は Eclipse で非常に多く見られたが，他のプロジェクトでは可能である．本研究では，Java で記述されたプロジェクトに対確認を行ったサンプルの中にほとんど含まれなかった．

してのみ実験を行った．他の言語でもファイルをまたいだソー

6. 考

スコードの移動を検出できると予想されるが，実際に検出できる

察

かは分からない．

6. 1 ファイルをまたいだ移動の検出
実験結果より，提案手法を用いてファイルをまたいだソース

8. お わ り に

コードの移動を検出することが可能になることが分かった．検

本研究では，プロジェクトに含まれるソースファイルから，プ出した有用な移動ノードのうち，表 4 で示すように WhileState-

ロジェクト全体の AST を構築し差分を計算することで，ファイ

ment や ForStatement が移動した回数は少ない．表 5 は最新版

ルをまたいだソースコードの移動を検出する手法を提案した．提の ArgoUML，Log4j，Tomcat から生成した AST から，IfState-

案手法を用いて 8 個の OSS に対して実験を行ったところ，すべ

ment，WhileStatement，ForStatement の数を計測した結果でてのプロジェクトにおいてファイルをまたいだソースコードのある．WhileStatement や ForStatement は IfStatement に比べ移動を検出できた．今後の課題としては以下が考えられる．

て出現数が少なく，ファイルをまたいだ移動の検出数も少ない．

他の言語で開発された OSS への適用：

また，プロジェクト全体に検出範囲を拡大したが，適合率は最Java 以外の言語で開発されている OSS に対して提案手法を適用し，ファイルをまたも低いプロジェクトでも 60%，半数以上のプロジェクトで 70%

いだソースコードの移動を検出できるかを調査する．

以上となっており，ファイルをまたいだソースコードの移動の検検出した差分の可視化：

出に対して，提案手法は有効であるといえる．

スコードの移動を，より分かりやすい形で開発者に表示する．

検出されたファイルをまたいだソー

6. 2 ファイルをまたいだ移動の特徴

GumTree には，Web ブラウザ上で編集スクリプトを視覚的に確検出できたファイルをまたいだ移動のうち，機能の分割・統認できるツールがあり，これを改良することが考えられる．

合，継承関係の変化の共通点として，これらの操作はリファクタ
リングによって多く引き起こされると考えられる．同様の機能を抽出したり，肥大化した機能を分割したりする操作はリファクタリングにおいて多く行われる [8]．この操作に伴う移動が，提案手法によって検出できることが確認できた．
また，表 4 からは，MethodDeclaration が WhileStatementに比べて多いことがわかる．メソッドが 1 つの機能を持っていることが多く，ある機能を持つソースコードを他のファイルに移す際は while 文や for 文単体で移動させるよりもメソッドの移動が中心になると考えられる．そのため，表 4 のように，

MethodDeclaration の移動の数が多くなっていると考えられる．
目視確認を行なった際には，while 文や for 文を含んだメソッ
ドが，ファイルをまたいで移動していることが確認できた．

5. 3. 2 項で挙げた，短いソースコードの移動が多く検出された理由として，これらのソースコードはプログラム内に多く存在す
るということが考えられる．それらをマッチングした際，ファイルをまたいだノード同士のマッチングが多くなったと考えられる．さらに，ソースコードの長さも影響がある．GumTree は部
表 5 プロジェクトに含まれる if，while，for 文に対応するノードの数
ノードのラベル謝辞

本研究は，日本学術振興会科学研究費補助金基盤研究（B）（課題番号：17H01725）の助成を得て行われた．
文

献[1] J. Falleri, F. Morandat, X. Blanc, M. Martinez, and M. Monperrus, “Fine-grained and accurate source code diﬀerencing,”
International Conference on Automated Software Engineering, Vasteras, Sweden - 19, 2014, pp.313–324, 2014.
[2] C. Macho, S. McIntosh, and M. Pinzger, “Extracting build
changes with builddiﬀ,” The 14th International Conferenceon Mining Software Repositories, pp.368–378, 2017.
[3] F. Madeiral, T. Durieux, V. Sobreira, and M. Maia, “Towards
an automated approach for bug ﬁx pattern detection,” 2018.
[4] M.S. Ahmed and A. Tabassum, “Automatic contextual commit message generation: A two-phase conversion approach”.
[5] A.T. Nguyen, M. Hilton, M. Codoban, H.A. Nguyen, L.
Mast, E. Rademacher, T.N. Nguyen, and D. Dig, “API code
recommendation using statistical learning from ﬁne-grainedchanges,” International Symposium on Foundations of Software EngineeringACM, pp.511–522 2016.
[6] E.W. Myers, “Ano(nd) diﬀerence algorithm and its variations,” Algorithmica, vol.1, no.1, pp.251–266, Nov. 1986.
[7] M. Monperrus and M. Martinez, “Cvs-vintage: A dataset of
14 cvs repositories of java software”.
[8] M. Fowler, Refactoring: improving the design of existing
code, Addison-Wesley Professional, 2018.

ArgoUML Log4j Tomcat

IfStatement

12,426

5,080

WhileStatement

512

199

23,521
626

ForStatement

424

626

1,556

—6—