論

学生論文特集文

プロジェクト全体の抽象構文木構築によるファイル間の移動コード
検出
藤本

章良†

肥後 芳樹†

松本淳之介†

楠本 真二†

Detecting Source Code Moves across Files by Using a Project-Level Abstract Syntax Tree
Akira FUJIMOTO† , Yoshiki HIGO† , Junnosuke MATSUMOTO† , and Shinji KUSUMOTO†

あらまし ソフトウェア開発において，開発者がソースコードの差分を理解することは重要である．差分を検出するツールとして GumTree がある．GumTree は変更前後のソースファイルを入力として受け取ると抽象構文木を生成し，削除・挿入・移動・更新といった操作を抽象構文木のノード単位で検出する．しかし，GumTree は
単一ファイルの差分しか検出できないため，ファイルを横断するソースコードの移動を検出できない．本研究では，GumTree を拡張しファイルを横断するソースコードの移動を検出する手法を提案する．提案手法では，プロジェクトに含まれる全てのソースファイルから一つの大きな抽象構文木を構築し，検出精度向上のために抽象構
文木に対して 2 段階のマッチングを行う．8 個のオープンソースソフトウェアに対して提案手法を用いて実験を行った結果，88,848 個のコミットの中から合計で 89,418 個のファイルを横断する移動を検出でき，ファイルを横断するソースコードの移動やファイル名に幾つかの特徴が得られた．また既存ツールと比較を行った結果，既存ツールを上回る数の移動を検出した．
キーワード

差分，GumTree，抽象構文木

行単位でソースコードを比較するため，ある行の一部

1. ま え が き

分のみが変更された場合でも，その行全体が変更されソフトウェア開発において，バージョン管理ツール

たと出力する．このため，実際にどの部分に対して変は多くのプロジェクトで導入されており [1]，バージョ更が行われたかが分かりづらくなる [5], [8]．diﬀ の出ン間のソースコードの差分を正確に，理解しやすく開力結果に基づいて，より詳細に変更箇所を強調表示す

発者に示すことは重要である．開発者がソースコード

るツール（注 1）も存在するが，同じ行の中で複数箇所のの差分を理解することで，振る舞いの変化を把握しや変更が発生すると変更箇所以外も強調表示される可能すくなるからである [2], [3]．例えばある変更の後にバ性がある．二つ目の課題は，編集操作が削除と挿入のグが発生した場合，差分を確認することでそのバグの2 種類しか存在していない点である．全ての編集操作原因となるソースコードの特定が容易となる．そのたが削除または挿入の操作として出力されるため，ソーめソースコードの差分を検出するツールが開発されてスコードの移動や更新といった削除と挿入以外の操作

おり，Myers のアルゴリズム [4] を実装した Unix のを行った場合，開発者が意図した操作として出力されdiﬀ をはじめ，様々な差分検出ツール [5]〜[7] が開発さない．

れている．バージョン管理ツールの一つである Git では，内部に diﬀ コマンドが組み込まれている．

これらの課題を解決するためのツールとして，抽象構
文木（以下，AST）を利用した差分検出ツール [3], [9]〜しかし，Unix の diﬀ に代表される行単位の差分検出[11] が開発されている．その一つとして，GumTree [10]ツールには二つの課題が存在する．一つ目の課題は，がある．GumTree は，ある変更前後のソースファイル

出力される差分の粒度が粗いという点である．diﬀ はを入力として受け取ると，それぞれの AST を生成し，† 大阪大学，吹田市

それらを比較して AST のノード単位の差分を出力す

Osaka University, Suita-shi, 565–0871 Japan
DOI:10.14923/transinfj.2020PDP0027

242

電子情報通信学会論文誌 D Vol. J104–D（注 1）：diﬀ-highlight．https://github.com/git/git/tree/master/contrib/diﬀ-highlight

No. 4 pp. 242–254 © 一般社団法人電子情報通信学会 2021

論文／プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出るツールである．AST を利用することで行単位での比較よりも細かい粒度で比較可能となり，変更が行われ

2. 準

備

た範囲のみの差分を出力可能である．更にノードの削

2. 1 抽象構文木

除や挿入以外にも，移動や更新を検出できる．

抽象構文木（注 2）は，ソースコードを構文解析して得

GumTree 及び，GumTree を改良したツールが出力しられる順序木である．一つのソースファイルから一つた編集スクリプトは多くの研究で利用されている．例の AST が生成される．AST の各ノードは以下の五つ

えば，Maven のビルドファイル解析 [12] やバグ修正パの要素で構成されている．

ターン検出の自動化 [13]，バージョン管理のコミット

ID 各 AST 内で固有の識別子

メッセージ生成 [14]，API メソッドの提案 [15] などに親ノード用いられている．

つ．ただし，根ノードの親は存在しないので何も保持

しかし，GumTree にも課題が存在する．各ファイル

AST の各ノードは，親ノードへの参照をもしない．

に対して個別に差分計算を行うため，ファイルを横断

子ノード

するソースコードの移動を検出できない．ファイルをつ．ただし，葉ノードの子は存在しないので何も保持

AST の各ノードは，子ノードへの参照をも横断するソースコードの移動は，リファクタリングにしない．

おいて頻繁に行われる [16]．「移動」と出力されるべき

ラベル

このような変更が，「削除と挿入」として出力されてし

値 各ノードがもつラベル以外の情報である．例えば，

まい，その結果，開発者がソースコードの変更に対し識別子のノードはメソッド名や変数名を値として保持て誤った認識をもつ可能性がある．

する．

そこで，ファイルを横断するソースコードの移動を検出可能にすることを本研究の目的とする．そのため

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

AST のエッジは，その両端のノードに直接の親子関係があることを示す．

に GumTree を拡張し，複数のソースファイルから生

2. 2 GumTree の差分検出成した AST を一つのプロジェクト全体の AST にまと

GumTree は入力された変更前後のソースファイル

め，差分を計算する手法を提案する．提案手法では，

からそれぞれの AST を生成し，二つの AST の違いを

計算時間短縮のために必要なソースファイルのみから

AST のノード単位の編集スクリプトとして出力する．

AST を生成し，検出精度向上のためにプロジェクト全

編集スクリプトとは，変更後の AST を得るために変更

体の AST に対し 2 段階のマッチングを行う．

前の AST に適用された編集操作の列である．木構造

提案手法の評価を行うために，8 個のオープンソーの差分を計算するために，GumTree はマッチングを行

スソフトウェアに対して実験を行い，88,848 個のコう．マッチングとは，変更前後における AST のノー

ミットの中から合計で 89,418 個のソースファイルを横ド間に対応付けを行う処理である．

断する移動を検出できた．加えて，それらが差分の理

GumTree のマッチングは，トップダウンフェーズ

解につながる移動であるかどうかの調査を行った．まとボトムアップフェーズの 2 段階で構成されている．

た，既存のリファクタリング検出ツールに対し，ファトップダウンフェーズでは，二つの AST の根ノードかイルを横断するソースコードの移動の数を比較した．

ら葉ノードに向けて辿っていき，完全一致する部分木

比較対象としたツールは，リファクタリング操作の一をマッチングする．ボトムアップフェーズでは，トッ

つとしてソースコードの移動を検出可能であり，提案

プダウンフェーズでマッチングされていないノードに手法との検出結果の違いを調査した．更に，提案手法

対して類似度を用いてマッチングを行う．ボトムアッが検出したファイルを横断するソースコードの移動をプフェーズは葉から根に向かって辿り，根ノードにた

目視で確認し，ソースコードがファイルを横断して移どり着くと完了となる．

動する際に，ソースコードやファイル名にどのような特徴があるかを分析した．

マッチングされたノードは，変更の前後で同じノードとして扱われる．マッチングの結果と AST を参照
し，変更前の AST に対して削除・挿入・移動・更新が行われたノードを得る．ただし，AST の類似度をもと（注 2）：Abstract Syntax Tree: AST

243

電子情報通信学会論文誌 2021/4 Vol. J104–D No. 4

図1

GumTree の差分検出にマッチングを行うため，必ずしも開発者が行った操作と一致するとは限らない．
図 1 は，GumTree の差分検出方法を模式的に表している．変更前後のファイルから生成した AST に対してマッチングを行う．図 1 では，マッチングの結果を
各ノードの右下の数字で表しており，同じ数字のノードはマッチングされていることを示している．変更
前後の AST ノードのマッチング結果を基に Chawatheら [17] の計算手法を用いて，GumTree は木構造の違いを差分として出力する．この例では，4 番のノードは変更前の AST にのみ存在するため削除，7 番のノード
は変更後の AST にのみ存在するため挿入と出力される．5 番のノードは変更前後のどちらにも存在しているが，親のノードが変わったため移動と出力される．

6 番のノードは木構造上の違いはないが，ノードの値
が “Gum” から “Tree” に変更されたため更新と出力される．

3. 研 究 目 的
GumTree は，変更を削除・挿入・移動・更新の四つの操作を用いて表現する．しかし，AST は各ファイルに対して構築されるため，ソースファイル A からソースファイル B にコードが移動される変更が行われた場
合，その変更を移動であると認識できない．そのような場合に GumTree は，ソースファイル A からはコードが削除され，ソースファイル B にはコードが追加されたという編集スクリプトを出力する．

図2

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

図 2 の例では，ファイル Main.java と Calc.java
が同時に変更されたと仮定する．この変更では，ファGumTree を用いてそれぞれのファイルの差分を出

イル Main.java に存在したメソッド average() が力すると，Main.java の編集スクリプトはメソッド

Calc.java に移動されている．この変更の前後で，

average() の削除，Calc.java の編集スクリプトは244

論文／プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出

図 3 提案手法の概要

メソッド average() の挿入となる（図 2 (a)）．しかし，実際に行われた操作を表現するには，メソッド

average() の移動とする方が適切である（図 2 (b)）．
この違いにより，開発者がソースコードの変更について誤った認識をもち，ソースコードの振る舞いの違いを理解するのに時間がかかったり，バグの発見が遅れたりするおそれがある．本研究では複数のファイルが
図4変更された場合に，ファイルを横断する移動を検出す

プロジェクト全体の AST の構築る手法を提案する．

4. 提 案 手 法ていく．ただし AST を加える順番は，プロジェクト提案手法の概要を図 3 に示す．提案手法の入力は，

ルートディレクトリからそのファイルへのパス名の昇対象のプロジェクトに含まれる変更前後のソースファ順とする．

イル全てであり，出力は編集スクリプトである．まず，

4. 2 変更のないファイルの除外

入力として与えられた各ソースファイルから AST を

プロジェクトに含まれる全てのソースファイルから生成する．それらの AST を用いて，プロジェクト全

プロジェクト全体の AST を構築すると，差分の計算対体の AST を構築する．このプロジェクト全体の AST象となる AST ノードの数が増え，提案手法の実行時

は，変更前と変更後で一つずつ作られる．プロジェク

間が長くなってしまう．また，変更されていないファト全体の AST の構築方法は，4. 1 で述べる．

イルも検出対象とすることで，無変更であるにもかか

次に，構築したプロジェクト全体の AST に対してわらず操作が行われたと誤って検出する可能性があ

マッチングを行う．その結果を用いて，プロジェクト

る．そこでプロジェクト全体の AST を構築する段階

全体の差分を計算し出力する．プロジェクト全体ので，ソースファイルごとに変更の有無を確認する．変

AST の差分計算には GumTree の差分を計算する処理

更されたソースファイルのみから AST を生成し，プをそのまま再利用し，編集スクリプトを出力する．

ロジェクト全体の AST に加える．

しかし，単純にプロジェクト内の全てのソースファ

ファイル内容の変更の有無は Myers のアルゴリズ

イルから単一の巨大な AST を構築し差分を計算する

ム [4] を用いて調べる．得られた結果が以下のいずれと，計算に多大な時間を要したり差分を検出する精度かに該当する場合は，そのファイルからは AST を生が下がったりする．そこで，4. 2 及び 4. 3 の工夫によ

成しない．

•

全く変更がない

4. 1 プロジェクト全体の AST の構築•

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

プロジェクト全体の AST の構築を図 4 に示す．ま4. 3 2 段階のマッチング

り，これらの問題を回避する．

ず，プロジェクト全体の AST を構築するため，ノー差分の検出対象をファイルからプロジェクト全体にドを一つ作成する．このノードを根ノードとし，ソー拡大した場合，変更されていないにもかかわらず類

スファイルから生成した AST を子ノードとして加え似したソースコード間で移動と出力される場合がある．この原因は，AST がプロジェクト全体に拡大し，
245

電子情報通信学会論文誌 2021/4 Vol. J104–D No. 4

図5

不適切なマッチングによる誤検出の例

図 6 2 段階のマッチング
図 7 2 段階のマッチングを適用した際の出力

GumTree がノードを適切にマッチングできていないためである．誤検出の例を図 5 に示す．この例では，段階目のマッチング終了時にまだマッチングされてい変更の前後で A.java の 2 行目に書かれた int num =ないノードの中からマッチングを行う．これにより既1; は変更されていない．しかし図中の赤線で示して存手法ではマッチングできなかった，異なるファイル

いるように，A.java の int num = 1; が B.java のint num = 1; に不適切にマッチングされた．その結果，A.java の foo() から B.java の bar() に移動したと誤検出している．
適切にマッチングできない理由は，マッチング対象がプロジェクト全体に拡大されてマッチングするノードの候補が増えるためである．そこで適切にマッチングするために，2 段階のマッチングを行う．2 段階のマッチングの方法を図 6 に示す．まず，プロジェクト
全体の AST の中で同じファイルから生成した部分木を取り出して，マッチングを行う．その後，プロジェ
クト全体の AST に対してマッチングを行う．

1 段階目では，変更前後で同一ファイルから生成し間の AST ノードをマッチングできる．また，マッチ
ングするノードの候補を 1 段階目でマッチングされていないノードに限定することにより，類似したソース
コードが移動と誤検出される可能性を下げられる．
図 5 の変更に対して，2 段階のマッチングを適用す
ると，1 段階目の同一ファイルのマッチング時に，変更前後の A.java に含まれる int num = 1; がマッチングされる（図 7 (a)）．この結果，A.java の int num= 1; に対する変更は行われていないと出力される．
また，2 段階目のマッチングでは変更前の B.java に含まれる method2() と変更後の A.java に含まれる

method2() がマッチングされる（図 7 (b)）．これにより，ファイルを横断する移動を検出できる．

た AST ノードのマッチングを行う．これは AST ノードのマッチング候補を同一ファイルのみにすることで，マッチング候補の数を減らし，適切にマッチングを行うことが狙いである．また，この段階でのマッチング
は単一ファイルの変更前後の AST をマッチングしており，既存手法にあたる．

2 段階目のプロジェクト全体のマッチングでは，1
246

5. 実

験

提案手法の評価や提案手法が出力した結果を分析するため，提案手法を実装した Graftast（注 3）を用いて複数のオープンソースソフトウェア（以下，OSS という）
（注 3）：https://github.com/kusumotolab/Graftast

論文／プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出
表 1 実験対象の OSS プロジェクト
OSS 名
ArgoUMLdnsjava
Eclipse（注 4）
JHotDraw
JUnit 4
Apache Log4j 2
Apache Struts
Apache Tomcat

コミット数 実験対象範囲の最終コミット日
16,1442015 年 1 月 11 日
1,771
2019 年 10 月 27 日
29,8112019 年 11 月 17 日
763
2018 年 8 月 27 日
2,4182019 年 11 月 2 日
10,7522019 年 11 月 1 日
5,697
2019 年 11 月 4 日
21,4922019 年 11 月 6 日

表2検出したファイルを横断する移動の数

OSS 名
ArgoUMLdnsjava
EclipseJHotDraw
JUnit 4
Apache Log4j 2
Apache Struts
Apache Tomcat

ファイル間の移動の数
10,316(23.1%)
1,664( 7.3%)
28,112(22.0%)
11,800(27.9%)
3,365(25.0%)
8,031(15.2%)
4,042(14.9%)
22,088(19.2%)

全ての移動の数
44,70722,851
127,693
42,23913,442
52,67827,093
114,863

表 3 既存手法と提案手法の増減数に対して実験を行った．以下では，この実験の内容に

OSS 名
ArgoUMLdnsjava
EclipseJHotDraw
JUnit 4
Apache Log4j 2
Apache Struts
Apache Tomcat

ついて説明する．

5. 1 実 験 対 象
GumTree の評価実験に用いられたデータセット [18]に含まれている OSS のうち，Git に移行されているソ
フトウェアを実験対象とした．実験対象の OSS を表 1に示す．これらのプロジェクトは全て Java で開発され削除−16,852−1,461−35,006−10,212−3,713−8,967−6,474−50,693

挿入
移動 更新−16,852 3,471
800−1,461413
66−35,006 6,450 1,110−10,212 2,265
375−3,713671
121−8,967 1,650
270−6,474 1,330
185−50,693 12,223 1,138ている．

5. 2 実験 1 ファイルを横断するソースコードの移
動検出

がある．
既存手法との比較結果を表 3 に示す．各項目は提案

提案手法によってファイルを横断するソースコード

手法の検出数から既存手法の検出数を引いた値である．

をどの程度検出できるかを調査する．Git でバージョ

全てのプロジェクトにおいて，削除・挿入の検出数がン管理されている OSS に対し，あるコミットに含まれ減少し，移動の数が増加している．これは，図 2 のよるソースファイルを変更後のソースファイル，その親

うに既存手法では削除と挿入となる出力が，提案手法

コミットに含まれるソースファイルを変更前のソース

によってファイルを横断する移動として出力された結ファイルとして，提案手法へ入力し差分を検出する．

果である．削除・挿入の減少数が移動の増加数と一致

これを master ブランチ上に存在する全てのコミットにしていないのは，複数の削除・挿入されたノードをま対して適用する．検出した差分のうち，ファイルを横とめて一つの移動と検出したためである．

断する移動の数を計測する．

また表 2 の “ファイル間の移動の数” と表 3 の “移また，既存手法と提案手法で編集スクリプトがどの動” の数が異なっているが，これは検出対象となるファように変化したのか調査する．既存手法には，変更前

イルが異なっているためである．既存手法との比較に後のプロジェクトにおいて全ての同名ファイルの組をおいて，条件を揃えるため提案手法の検出対象を制限

入力として与え，得られた編集スクリプトから各編集している．それぞれの検出対象は以下のとおりである．

操作の数を合計する．
各 OSS ごとに，ファイルを横断するソースコードの移動の検出数，検出された全ての移動数を表 2 に示
す．ファイル間の移動数の横に示されている括弧は，検出された全ての移動の数に対するファイルを横断す
る移動の数の割合である．全てのプロジェクトにおい•提案手法による移動検出（表 2）：プロジェクト内の全てのソースファイル•

既存手法との比較（表 3）：変更前後の両方に存在するソースファイル

5. 3 実験 2 ファイルを横断するソースコード検出の精度て，ファイルを横断する移動が含まれている．その割提案手法によって検出できたファイルを横断する移合はプロジェクトによって 7.3%〜27.9% とばらつき動に対して，その精度を評価する．提案手法が検出したファイルを横断する移動の中には，図 8 のように移（注 4）：org.eclipse.ui.workbench のみ調査した．Eclipse はプロジェクトの規模が非常に大きく，CVS-Vintage では eclipse.ui.workbench と eclipse.jdt.core
のみ調査している．我々は eclipse.jdt.core に対しても実験を行ったが，実行にかかる時間が長すぎたため実験対象から除外した．

動前後のソースコード片が大きく異なっている場合がある．これは，for 文の移動に加えて，その内部に対して if 文の挿入やステートメントの挿入・削除といっ247

電子情報通信学会論文誌 2021/4 Vol. J104–D No. 4

図 9 移動前後のソースコード片の類似度の分布

移動の中で，開発者の差分理解につながる検出結果が
図8

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

あるかを既存手法と比較し調査する．

Apache Tomcat で行われたリファクタリングコミッ
た複数の操作の組み合わせとして検出された結果であトの前後に，WsSession.java と Util.java をそれる．検出されたそれぞれの操作は誤りではないが，for

ぞれ既存手法を用いて差分検出を行うと，図 10 の結果

文の移動のみに注目した場合，この検出結果が適当でが得られた．これは，WsSession.java のメソッドであるとはいえない．

ある getMeesageType が削除され，Util.java では

そこで，提案手法が検出したファイルを横断する移メソッド getMeesageType が挿入されたという出力で動に対し移動前後のソースコード片の類似度を用いてある．一方，提案手法を用いて差分の検出を行ったと精度の評価を行う．例えば図 8 の場合，移動前後のころ，図 11 のような結果が得られた．これは，既存手ソースコード片が大きく異なっており類似度は低い．

法では削除と挿入として検出されたが，提案手法では一方で類似度が高い場合，二つのソースコード片が適ファイルを横断する移動として検出された例である．

切にマッチングし正しく移動を検出した可能性が大きこの結果から開発者は，メソッド getMeesageTypeい．したがって，類似度が高い移動が多いほど提案手

は Util.java で新たに作成されたメソッドではなく，法が検出する移動の精度が高いと判断する．

WsSession.java から移動されたメソッドであること

この実験においてはソースコード片の類似度を

1−

同様に，Apache Tomcat におけるバグ修正コミット

変更前後の移動コードのノード数合計の前後で既存手法と提案手法の比較を行った．既存手と定義した．移動前後のソースコード片が完全に一致した場合，編集スクリプトの長さは 0 となり類似度は1 になる．反対に大きく異なっていた場合は移動前後のソースコード片の編集スクリプトの長さが長くなる
ため類似度が低下する．
提案手法が検出した全てのファイルを横断する移動に対し類似度を計算し，その結果から得られたヒストグラムが図 9 である．類似度が 1，すなわち移動前後のコード片が完全に一致した移動が全体の 80% 以上を占めていることがわかる．また約 93% が類似度 0.7以上となっており，提案手法の移動検出の精度は十分であると考える．

5. 4 実験 3 差分の理解につながる事例の調査
実験 1 より，提案手法がファイルを横断するソース
コードの移動を多数検出できることが明らかになった．
この実験では提案手法が検出したファイルを横断する
248が理解しやすくなる．

GumTree で計算した編集スクリプトの長さ

法を JspServletWrapper.java と JspServlet.java
に対して適用したところ，JspServletWrapper.java
ではある catch 節の削除，JspServlet.java では，新規コードの挿入とその中の一部が同じファイル内での移動であると出力された（図 12）．同コミットに対し，提案手法を適用すると図 13 の結果が得られた．これは，JspServletWrapper.java で削除されたコードの
一部が，JspServlet.java にファイルを横断して移動したと提案手法が新たに検出したことを示している．
開発者は，この結果から JspServletWrapper.javaで行っていた一部の処理が JspServlet.java で行われるように変更されたことが理解しやすくなる．
これらの例のように，提案手法の検出結果により開発者が差分の理解をしやすくなる事例が複数あり，提案手法は既存手法に比べ有用であるといえる．

論文／プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出

図 10 既存手法によるリファクタリング時の差分検出結果

図 11 提案手法によるリファクタリング時の差分検出結果

図 12

既存手法によるバグ修正時の差分検出結果

5. 5 実験 4 ファイル間の移動コードを検出できる
既存ツールとの比較

比較対象の既存ツールとしてリファクタリング検出
ツールである RefactoringMiner [19] を選択した．このリファクタリング検出ツール [19]〜[21] の中には

ツールは，リファクタリング操作として，メソッド・

ファイルを横断するソースコードの移動やそれに類すクラスの移動，メソッドのプルアップ，メソッドへのる操作を検出できるツールがある．同じプロジェクト

抽出，パッケージの変更などが検出可能である．

に対して，提案手法によって得られる検出結果と既存

この実験では，RefactoringMiner によって検出されたのリファクタリング検出ツールを用いて得られる検出操作のうち，メソッドの移動，メソッドのプルアップ，

結果を比較し，提案手法がファイルを横断するソース

メソッドのプッシュダウンの数と，提案手法で検出しコードの移動検出に対して有効であるかを評価する．

た移動ノードが MethodDeclaration である移動の数を249

電子情報通信学会論文誌 2021/4 Vol. J104–D No. 4

図 13

提案手法によるバグ修正時の差分検出結果比較する．ただし，RefactoringMiner が検出したメソッドのプルアップやプッシュダウンは複数件のメソッドの移動として出力されるが，この実験ではそれらの移動を 1 件の移動として集計する．これは n 個のメソッドを一つのメソッドに集約した場合，RefactoringMiner
では n 件の移動が発生したと出力される一方で，提案
手法はメソッドのプルアップやプッシュダウンといった操作を 1 件のメソッドの移動として検出するため，比較の条件を一致させるためである．

表4

提案手法と RefactoringMiner が検出したファイルを横断するメソッドの移動数

OSS 名
ArgoUMLdnsjava
JHotDraw
JUnit 4
Apache Log4j 2
Apache Struts
Apache Tomcat

表5

両手法 提案手法のみ
148
92
53
73
78
223
94
119
124
519
191
117
895
315

RefactoringMiner は，Git リポジトリ全体のリファク

77
9
73
39
104
95
384

メソッドが宣言されたクラスによる分類

こ の 実 験 は ，5. 1 で 挙 げ た OSS の う ち

eclipse.ui.workbench を 除 い た OSS を 対 象 に す る ．

RM（注 5）のみ

匿名クラスのメソッドの移動
内部クラスのメソッドの移動

両手法 提案手法のみ RM のみ
0
26
0
35
67
37

タリングを検出するため，一部のモジュールやディレ
クトリに限定した範囲で行われたリファクタリング

種類による分類結果を表 5 に示す． 匿名クラス内での検出ができなかったためである．また，Refactoring-

宣言されたメソッドが通常のクラス内に移動する事例

Miner の実行時には検出するブランチに master ブラン

は，提案手法のみで検出された．例として，図 14 のチを指定した．これは，提案手法と検出対象範囲となような移動が検出された．また，内部クラスで宣言さるコミットを一致させるためである．

れたメソッドの通常クラス内への移動は，提案手法や

各 OSS に対して，提案手法と RefactoringMiner を適用し，検出できたファイルを横断する移動の数を表 4

RefactoringMiner どちらも検出できたが，検出数は提案手法の方が多いという結果が得られた．

に示す．表 4 では，提案手法と RefactoringMiner のど

匿名クラスと通常クラス間でのメソッドの移動が提ちらも検出した移動の数，提案手法のみが検出した移案手法でのみ検出できたのは，移動の検出方法の違い

動の数，RefactoringMiner のみが検出した移動の数を記が理由であると考えられる．RefactoringMiner はルール載している．Apache Tomcat 以外のプロジェクトにおベースでリファクタリング操作の検出を行う．Refac-

いて，提案手法が検出した移動の数が RefactoringMiner

toringMiner は JDT（注 6）の AST を用いて解析を行っていの検出した移動の数を上回った．
次に，移動したメソッドが宣言されていたクラスの250（注 5）：RefactoringMiner の略表記
（注 6）：Eclipse プラグイン（https://projects.eclipse.org/projects/ eclipse.jdt）

論文／プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出

図 14

匿名クラス内のメソッド undo() が通常クラス内に移動する例

るが，ルールの一つとして，リファクタリング検出対象のメソッドは TypeDeclaration のノード内で宣言されるメソッドのみである．JDT の AST では，匿名クラス
は AnonymousTypeDeclaration ノードと対応しており，
通常のクラスや内部クラスが対応する TypeDeclarationとは異なる．ゆえに，匿名クラス内のメソッドはリ
ファクタリングの検出対象から外れるため，匿名クラスと通常クラス間での移動は検出できなかったと考えられる．
一方，提案手法で用いる Java ソースファイルから生図 15成される AST も JDT の AST に基づいているが，差分ファイルを横断する移動が発生したソースコードの例の検出には GumTree のアルゴリズムを用いて移動を検出する．2. 2 で説明したように，このアルゴリズムで特徴，などを調べる．調査するノードは，MethodDec-

ノードが移動したと判定されるのは，マッチングされた

laration，WhileStatement，ForStatement，IfStatement，ノードの親が変更前後で異なる場合である．したがっBlock の五つである．

て，親のノードの種類が AnonymousTypeDeclaration で検出されたファイルを横断する移動の中で特徴的であっても移動を検出可能である．よって，表 5 のようあった移動の例を幾つか紹介する．各図のソースコー

な結果となった．
また，移動したメソッドが通常のメソッドかコンストラクタであるかを調査した．提案手法と Refactoring-

ド例の紫色で示した部分が移動と検出された箇所である．
機能の分割・統合

Miner どちらからも検出された数は 6 個，提案手法の大きいクラスを複数のクラスに分割するときに，ファみが検出した数は 137 個，RefactoringMiner のみが検イルを横断するメソッドの移動が検出された．その例

出した数は 12 個であり，コンストラクタの移動はどを図 15 (a) に示す．変更前は Main クラスに含まれてちらの手法からも検出できるものの，その数は提案手いたメソッド read() と write() が IO クラスに移動法の方が多いという結果が得られた．

している．このほかにも，似た機能をもつクラスを統

5. 6 実験 5 ファイルを横断するソースコードの移動の特徴
提案手法が検出したファイルを横断するソースコー

合して一つのクラスにするための移動もあった．
移動先のクラスが新たに作られる場合と，既存のクラスにソースコードが移動される場合を確認した．移ドの移動の特徴や傾向を調査する．移動したノードの動前後のファイル名に，Util，Helper といった名称が種類や処理の内容に加え，変更の前後でファイルの内付く例が合計で 334 個あった．またそれら以外には，

容がどのように変化したかや，移動前後のファイル名の元の名前と似た名称になる場合が多かった．
251

電子情報通信学会論文誌 2021/4 Vol. J104–D No. 4

メソッドの移動以外にも，図 15 (b) のような一部の

ソースコードの長さも影響がある．GumTree は部分木処理のみを取り出してメソッド化する変更があった．

の類似度を用いて，しきい値が一定値を超えた場合にWhileStatement，ForStatement，IfStatement のノードでマッチングを行う．短いソースコードであれば，ソー

このような移動が見られた．変更前のメソッドの行数

スコードの差異が出にくく類似度が高くなりやすい．

が長く，処理を別のメソッドに切り出すリファクタリ

そのため，よりマッチングされやすくなるので，移動ングをした場合に，このような移動が多く検出された．

として検出される可能性が高くなると考えられる．

継承関係の変化
クラス間の継承関係が変化する場合に，ファイルを横断する移動を検出した．図 15 (c) は，新たに作成し

6. 妥当性の脅威
本研究における妥当性の脅威について述べる．

た抽象クラスに一部のソースコードが移動される例

提案手法は特定のプログラミング言語に依存しないである．具象クラスから抽象クラスへのソースコード

ため，GumTree を適用可能なプログラミング言語全ての移動が多く検出された．反対に，抽象クラスから具において適用可能である．本研究では，Java で記述さ象クラスへの移動も存在した．その他にも，継承関係れたプロジェクトに対してのみ実験を行った．他の言のある具象クラス間で，実装箇所の変更によるソース

語でもファイルを横断するソースコードの移動を検出

コードの移動も検出した．

できると予想されるが，実際に検出できるかは分から

継承関係のあるファイル間での移動は，Abstract という名称がつくファイルの他に，Default という名称がつく例が多く確認された．
検出できたファイルを横断する移動のうち，機能の分割・統合，継承関係の変化，部分的なメソッドへの切り出しといった操作はリファクタリングにおいて多く行われる [22], [23]．典型的なリファクタリングに伴う移動が，提案手法によって検出できた．
またファイルを横断するソースコードの移動の中には，行数が短いソースコードも存在した．次のソース
コードが挙げられる．

•

getter/setter（MethodDeclaration）•

return 文（Block）•

null チェック（IfStatement）

getter や setter の移動は，抽象クラスを追加した場
合によく見られた．

return 文はブロックの中に return; のように return
文のみが含まれるソースコードの移動である．このような移動はほとんどのプロジェクトで検出された．

IfStatement で null チェックを行うソースコードの移動も検出された．この if 文内では，新規インスタンスの作成のみや return 文など短いソースコードも含まれている．
このような短いソースコードの移動が多く検出された理由として，これらのソースコードは定型処理としてプログラム内に多く存在していると考えられる．それらをマッチングしたとき，異なるファイル間でのノードのマッチングが多くなったと考えられる．更に，
252ない．
事例の調査においては，差分の理解につながる移動であるかを目視で確認した．しかし，この結果は著者らの主観に大きく依存する．そのため，差分の理解につながる移動と判断した例が，他の開発者にとっては差分の理解につながらない移動となる可能性がある．
また，提案手法との比較対象として，RefactoringMinerを用いた．その他の既存ツールを用いた場合，検出できるファイルを横断する移動の数や検出された移動の特徴について，異なる実験結果になる可能性がある．

7. む す び
本研究では，各ファイルに対して個別に差分の計算を行う GumTree を拡張し，プロジェクト全体のソース
ファイルの中からファイルを横断するソースコードの移動を検出する手法を提案した．提案手法では，プロジェクトに含まれる全てのソースファイルから，プロ
ジェクト全体の AST を構築し，その差分を計算する．
提案手法を用いて 8 個の OSS に対して実験を行った
ところ，合計で 89,418 個のファイルを横断する移動を検出できた．既存ツールと比較を行い，提案手法でのみ検出できる移動のパターンが存在することがわかった．更に移動したソースコードを調査した結果，リファクタリングに伴う移動をはじめ，移動するソース
コードの特徴やファイル名の傾向が明らかになった．
今後の課題としては以下が考えられる．
他の言語で開発された OSS への適用

Java 以外の言語で開発されている OSS に対して提案手法を適用し，ファイルを横断するソースコードの

論文／プロジェクト全体の抽象構文木構築によるファイル間の移動コード検出

移動が検出できるかを調査する．

[13]

F. Madeiral, T. Durieux, V. Sobreira, and M. Maia, “Towards anautomated approach for bug fix pattern detection,” 2018.

検出した差分の可視化
現状では，検出した差分は編集スクリプトとして出力されるが，直感的に差分を理解しづらい．そこで，[14]

M.S. Ahmed and A. Tabassum, “Automatic contextual commit
message generation: A two-phase conversion approach,” 2018.

[15]

A.T. Nguyen, M. Hilton, M. Codoban, H.A. Nguyen, L. Mast,

検出されたファイルを横断するソースコードの移動

E. Rademacher, T.N. Nguyen, and D. Dig, “API code recommen-を，より分かりやすく開発者に表示する．GumTree に

dation using statistical learning from fine-grained changes,” International Symposium on Foundations of Software Engineering,

は，Web ブラウザを用いて編集スクリプトを視覚的に確認できるツールがあり，このツールへの改良が考え

pp.511–522, ACM, 2016.
[16]

られる．
謝辞

ability: A way to go?,” IEEE International Software Metrics Symposium, 2005.

本研究は，日本学術振興会科学研究費補助金

基盤研究（B）（課題番号：17H01725）の助成を得て行[17]

MOD Rec., vol.25, no.2, pp.493–504, 1996.

文

献

[18]
[19]

tory,” International Conference on Software Engineering, pp.483–

neering, pp.36–39, 2009.

494, 2018.

D. Binkley, “An empirical study of the eﬀect of semantic diﬀer[20]ence, pp.663–670, 2005.

K. Huang, B. Chen, X. Peng, D. Zhou, Y. Wang, Y. Liu, andW. Zhao, “ClDiﬀ: Generating concise linked code diﬀerences,”[21]

ing, pp.263–274, 2006.

gineering, pp.679–690, New York, NY, USA, 2018.
E.W. Myers, “An O(ND) diﬀerence algorithm and its variations,”[22]

G. Canfora, L. Cerulo, and M. Di Penta, “Ldiﬀ: An enhanced line
diﬀerencing tool,” IEEE International Conference on Software Engineering, pp.595–598, 2009.

[6]

A. Loh and M. Kim, “LSdiﬀ: A program diﬀerencing tool to iden-

M. Fowler, Refactoring: Improving the design of existing code,
Addison-Wesley Professional, 2018.

Algorithmica, vol.1, no.1, pp.251–266, 1986.
[5]

Z. Xing and E. Stroulia, “Refactoring detection based on UMLDiﬀ
change-facts queries,” Working Conference on Reverse Engineer-

ACM/IEEE International Conference on Automated Software En[4]D.C. Atkinson and T. King, “Lightweight detection of program refactorings,” Asia-Pacific Software Engineering Confer-

Program Comprehension, pp.97–106, 2002.
[3]

N. Tsantalis, M. Mansouri, L.M. Eshkevari, D. Mazinanian, and D.
Dig, “Accurate and eﬃcient refactoring detection in commit his-Workshop on Cooperative and Human Aspects on Software Engi-

ences on programmer comprehension,” International Workshop on

M. Monperrus and M. Martinez, “CVS-Vintage: A dataset of 14
cvs repositories of java software,” 2012.

B. De Alwis and J. Sillito, “Why are software projects movingfrom centralized to decentralized version control systems?,” ICSE

[2]

S.S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom,“Change detection in hierarchically structured information,” SIG-

われた．
[1]

B. Geppert, A. Mockus, and F. Robler, “Refactoring for change-[23]

T. Mens and T. Tourwe, “A survey of software refactoring,” IEEE
Trans. Softw. Eng., vol.30, no.2, pp.126–139, 2004.

（2020 年 5 月 29 日受付，9 月 29 日再受付，
12 月 2 日早期公開）

tify systematic structural diﬀerences,” ACM/IEEE International
Conference on Software Engineering - Volume 2, pp.263–266,
2010.
[7]

Z. Xing and E. Stroulia, “UMLDiﬀ: An algorithm for objectoriented design diﬀerencing,” IEEE/ACM International Conference on Automated Software Engineering, pp.54–65, 2005.

[8]

大森隆行，丸山勝久，“開発者による編集操作に基づくソー
スコード変更抽出，” 情処学論，vol.49, no.7, pp.2349–2359,
2008.

[9]

B. Fluri, M. Wuersch, M. Pinzger, and H. Gall, “Change distilling:

藤本 章良
令 2 大阪大学基礎工学部情報科学科卒．
現在，同大学大学院情報科学研究科博士前期課程在学中．ソースコード分析に関する研究に従事．

Tree diﬀerencing for fine-grained source code change extraction,”
IEEE Trans. Softw. Eng., vol.33, no.11, pp.725–743, 2007.
[10]

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, pp.313–
324, 2014.

[11]

G. Dotzler and M. Philippsen, “Move-optimized source code tree
diﬀerencing,” IEEE/ACM International Conference on AutomatedSoftware Engineering, pp.660–671, 2016.

[12]

C. Macho, S. McIntosh, and M. Pinzger, “Extracting build changes
with builddiﬀ,” International Conference on Mining Software
Repositories, pp.368–378, 2017.

253電子情報通信学会論文誌 2021/4 Vol. J104–D No. 4

肥後 芳樹

（正員）

2002 大阪大学基礎工学部情報科学科中退．
2006 同大学大学院博士後期課程了．2007 同大学大学院情報科学研究科コンピュータサ
イエンス専攻助教．2015 同准教授．博士（情報科学）．ソースコード分析，特にコー
ドクローン分析，リファクタリング支援，
ソフトウェアリポジトリマイニング及び自動プログラム修正に関する研究に従事．情報処理学会，日本ソフトウェア科学会，
IEEE 各会員．

松本淳之介
平 30 大阪大学基礎工学部情報科学科
卒．令 2 同大学大学院情報科学研究科コンピュータサイエンス専攻博士前期課程了．
在学時リポジトリマイニングに関する研究
に従事．

楠本 真二

（正員）

1988 大阪大学基礎工学部卒．1991 同大

学大学院博士課程中退．同年同大学基礎工学部助手．1996 同講師．1999 同助教授．
2002 同大学大学院情報科学研究科助教授．
2005 同教授．博士（工学）．ソフトウェアの生産性や品質の定量的評価に関する研究に従事．情報処理学会，IEEE，IFPUG 各会員．

254