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

信学技報
TECHNICAL REPORT OF IEICE.

行単位の差分情報を考慮した
抽象構文木のノード単位の差分出力
松本淳之介†

肥後芳樹†

楠本真二†

† 大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5
E-mail: †{j-matumt,higo,kusumoto}@ist.osaka-u.ac.jp
あらましバージョン管理システムを用いた開発において，開発者がソースコードの差分を理解することは重要である．

ソースコードの差分を表現したものを編集スクリプトと呼ぶ．編集スクリプトを出力するツールとして GumTree がある．GumTree は 2 つのバージョンのソースコードを入力として受けとり，抽象構文木のノード単位の挿入・削除・更新・移動といった編集スクリプトを出力する．しかし，GumTree の更新と移動を検知する精度は低く，差分の理解が困難であるという問題がある．GumTree の精度が低い原因の１つとして，抽象構文木の情報のみで編集スクリプトを出力しようとすることが挙げられる．そこで提案手法では抽象構文木の情報のみでなく，行単位の差分情報を用いて編集スクリプトを出力する．そしてオープンソースソフトウェアに対して提案手法が有効か実験を行い，提案手法が差分の理解に有効であることを確認した．
キーワード

差分理解，編集スクリプト，GumTree

1. ま え が き
ソフトウェア開発においてバージョン管理システムの導入は必須といえる．バージョン管理システムを用いた開発において，GumTree は抽象構文木のノード単位でソースコードの差分を出力する．さらに，ノードの挿入や削除といった操作に加えて，ノードの更新，ノードの移動といった計 4 種類の操作を出力することができる．

コードレビューや変更が競合した場合に，ソースコードの差分をGumTree 及び GumTree を改良したものが出力した編集スク理解する必要がある．そのような場面において，開発者を支援すリプトは多くの研究で利用されている．例えば，API のコードるためにソースコードの差分を分かりやすく表現する研究が数のサジェスト [3] や Maven のビルドファイルの解析 [4]，自動プ多く行われている．

ログラム修正 [5] であったり，JavaScript のバグのパターンの発ソースコードの差分を表現したものを編集スクリプトと呼ぶ．

見 [6] などに用いられている．

編集スクリプトを出力する方法として，一般的に Unix の diff

ただし，GumTree にも問題がある．移動と更新を適切に検知コマンドを用いることが多い．diff コマンドは Myers のアルゴすることができないということである [7]．実際に著者らが目視

リズム [1] を基に，行単位でソースコードが挿入・削除されたとでオープンソースソフトウェア (以下 OSS と呼ぶ) の差分を確認いう編集スクリプトを出力する．Git など，多くのバージョン管したが，更新であるべき変更が削除して挿入されていた．また，

理システムでこの diff コマンドは利用されている．

移動していないのに移動と出力されることも多数あった．そのしかし，diff コマンドには問題が 2 つある．1 つ目の問題と結果，編集スクリプトの操作の列が長くなってしまっていた．編して，差分を出力する粒度が粗いということである．開発者が理集スクリプトが長ければ長いほど，開発者はその編集スクリプト解したい対象の多くはソースコードである．ソースコードの行を理解することは難しくなると言われている [7] [8] [9]．の一部しか変更されていないにも関わらず，その全てが変更されそこで本研究では，編集スクリプトを短くすることを指針とたものとして出力されてしまい，編集されていないプログラムし，より理解のしやすい編集スクリプトを出力することを目標と要素まで編集されたと出力されてしまう．2 つ目の問題として，する．更新や移動の精度をあげるためには編集前のノードと編集操作の種類が少ないということである．diff コマンドには挿入後のノードのマッチングを適切に行う必要がある．GumTree でと削除の 2 種類の操作しかない．ソースコードの編集において，は抽象構文木の構造の情報のみを用いてマッチングを行なってい開発者が挿入や削除以外の操作をする場合，開発者の意図した差るが，本研究ではさらに diff コマンドを用いた行単位の差分の分を出力することができない．

情報を用いてマッチングを行っていく．diff コマンドによってこのような問題を解決する手法として，GumTree [2] がある．

変更されたと出力された行，変更されていないと出力された行の—1—

1.
/**
2.
* Removes all mappings from this map.
3.
*/
4.
public void clear() {5.
modify();6.
7.
nodeCount = 0;8.
rootNode[KEY] = null;9.
rootNode[VALUE] = null;10. }箟꧊⵸‫اך‬٦‫؝أ‬٦‫س‬

䯏Ⰵ

1.
/**
2.
* Removes all mappings from this map.
3.
*/
4.
public void clear() {5.
modify();6.
7.
nodeCount = 0;8.
rootNode[KEY.ordinal()] = null;9.
rootNode[VALUE.ordinal()] = null;10. }⵴ꤐ刿倜箟꧊䖓‫اך‬٦‫؝أ‬٦‫س‬獳⹛

図 1 GumTree の実行例遤⽃⡘‫ثحوך‬ٝ‫ؚ‬
EJGG‫و؝‬ٝ‫س‬箟꧊⵸䖓‫ך‬‫ا‬٦‫؝أ‬٦‫س‬䊴ⴓ‫ך‬剣搀‫ⶴⴓד‬遤⽃⡘‫ך‬䊴ⴓ䞔㜠䊴ⴓ‫׃ז‬‫ظ‬٦‫ךس‬‫ثحو‬ٝ‫ؚ‬‫ثحو‬ٝ‫ְזְג׸ׁؚ‬‫ظ‬٦‫س‬(VN5SFF ‫ثحوך‬ٝ‫הؚ‬箟꧊‫ךزفؙٔأ‬鎘皾䊴ⴓ֮‫׶‬

箟꧊‫زفؙٔأ‬‫ثحو‬ٝ‫ظ׋׸ׁؚ‬٦‫س‬⵴ꤐ遤‫ה‬䯏Ⰵ遤‫ثحوך‬ٝ‫ؚ‬

図 2 提案手法の概要

2 つのグループにソースコードを分け，それぞれのグループに対して異なるマッチング手法を用いてノードのマッチングを行う．

GumTree よりも短い編集スクリプトを提案手法が出力していいを編集スクリプトとして出力する．

GumTree の処理は以下の 2 つで構成されている．
1. ノードのマッチングることを確認するため，9 個の OSS のプロジェクトの差分に対2. マッチングの結果を基にした編集スクリプトの計算して提案手法を実行し，提案手法が有効であることを確認した．

ノードのマッチングをすることによって，GumTree は編集前のまた，提案手法で出力された編集スクリプトが理解しやすいも

AST から編集後の AST に対して，どのノードが追加・削除されのになっていることを確認するために，14 人の被験者に対して，たか，どのノードの位置が変更されたか，どのノードの値が更新実験を行い，理解しやすいものになっていることを確認した．

されたかという情報を得る．つまり，マッチングされたノードか

2. 抽象構文木の差分検知
2. 1 抽象構文木

ら，GumTree は編集スクリプトを計算することができる．この編集スクリプトの計算に関しては十分に最適化されている [10]．

GumTree が行うノードのマッチングはトップダウンフェーズ

抽象構文木 (以下 AST と呼ぶ) はソースコードを木構造で表とボトムアップフェーズの 2 段階で構成されている．まず，トッ現したものである．1 つのソースファイルに対して 1 つの AST

プダウンフェーズでは，入力された 2 つの AST に共通して存在を構築し，AST の各ノードは以下の 3 つで構成されている．

する部分木をマッチングする．その後のボトムアップフェーズ

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

では，トップダウンフェーズでマッチングした共通の部分木を基持っている．ただし，根ノードには親が存在していないので，何準として，それらに含まれていない部分木のうち類似する部分木も保持していない．

をマッチングする. マッチングをする際は部分木の類似度を計算

ラベル： if 文や変数宣言などといった文法上の型を表している．

し，それが閾値を超えていればマッチングする．

値： メソッド名や変数名など各ノードが持つラベル以外の情報である．持つ情報がない場合は null になる場合もある．

ただし，GumTree のマッチングには問題が残っている．マッ
チングするべきノードをマッチングさせることができず，必要以

2. 2 GumTree の差分検知

上に長い編集スクリプトを出力してしまう．図 1 にその例を示

提案手法は GumTree をベースとしているため，GumTree です．このソースコードは Commons-Collections に含まれるあるの AST の差分検知について述べる．GumTree は入力として編コミット間の編集スクリプトを GumTree で出力したものの一部集前のソースコードと編集後のソースコードを受けつける．そである．左右のソースコードを見比べると，8 行目と 9 行目以外れぞれのソースコードから AST を構築し，それらの木構造の違は変更されていないにも関わらず，GumTree は変更されたもの

—2—

1.
/**
2.
* Removes all mappings from this map.
3.
*/
4.
public void clear() {5.
modify();6.
7.
nodeCount = 0;
8.rootNode[KEY] = null;
9.rootNode[VALUE] = null;10. }箟꧊⵸‫اך‬٦‫؝أ‬٦‫س‬

1.
/**
2.
* Removes all mappings from this map.
3.
*/
4.
public void clear() {5.
modify();6.
7.
nodeCount = 0;8.+
rootNode[KEY.ordinal()] = null;9.+
rootNode[VALUE.ordinal()] = null;10. }箟꧊䖓‫اך‬٦‫؝أ‬٦‫س‬

図 3 行単位の差分として出力している．例えば 4 行目の public を見比べると同ある．そこで編集前後の 4 行目に含まれる各ノードのマッチン一のコードであるにも関わらず，削除と挿入になっている．これグを行う．このようなマッチングを行うことで 2. 章で説明したは変更前後の public がマッチングされていないことが原因であような AST の構造のみではマッチングされなかった public なる．もし変更前後で public をマッチングすることができれば，どのマッチングが可能となる．

GumTree は変更の前に存在した public が変更の後にも存在しているものと認識することができ，public が削除・挿入されたとは出力しない．

3. 提 案 手 法
3. 1 概要

3. 3 差分がある行マッチングされるべきノードは，編集の前後で大きく移動しないと仮定する．その仮定に基づいて，diff コマンドで出力された削除行と挿入行を関連づける．
差分がある行の前後には差分がない行があるので，その行の情報を基に削除行と挿入行を関連づける．連続した複数の行が提案手法は GumTree の手法をベースとしている．GumTree

まとめて削除・挿入されている場合は複数の行をまとめて関連づ

では、ノードのマッチングが終わった状態からの編集スクリプける．関連づけられた行の中からマッチングするべきノードのトの計算は十分に最適化されているので，提案手法ではノード探索を行う．のマッチングの改善に取り組む．提案手法の概要を図 2 に示す．

例えば，図 3 の編集前のソースコードの 8 行目と 9 行目にはノードのマッチングの精度を上げるために，提案手法では AST削除が出力されており，その前後の 7 行目と 10 行目は差分がなに関する情報だけでなく，diff コマンドを用いた行単位の差分い行である．よって編集前の 7 行目と完全一致する行が編集後情報を用いる．GumTree によるマッチングを行う前に diff コのソースコードに存在し，その行は編集後のソースコードの 7 行

マンドから得られた情報を基にマッチングを行う．

目である．同様に編集前のソースコードの 10 行目に完全一致す

diff コマンドで出力される行単位の差分から得られる情報は以下である．

る行は編集後のソースコードの 10 行目である．これらの情報か
ら，編集前の 7 行目と 10 行目に挟まれた削除と，編集後の 7 行•

どの行にどのような行が挿入されたか目と 10 行目に挟まれた挿入を関連づける．削除と挿入の関連づ•

どの行が削除されたかけられたら，その中に含まれるノードのマッチングを行う．

これらの情報を基に提案手法ではソースコードを，差分がないノードのマッチングは，部分木の類似度を用いて行う．部分

行と差分がある行の 2 つに分け，それぞれに対して異なるアプ木の類似度を用いたマッチングは GumTree でも行われており，ローチで探索範囲を狭めたノードのマッチングを行う．

部分木の類似度の計算には Jaccard 係数を用いる．

それだけではマッチングされなかったノードも存在するので，その後に GumTree のマッチングを行い，それらの結果から編集スクリプトの計算をする．

4. 実

験

提案手法を評価するため，2 つの評価実験を行なった．

3. 2 差分がない行
diff コマンドで差分がないと出力された行は，開発者は実際

表 1 実験対象の OSSに編集していないものと仮定する．差分がないと出力された行

OSS

言語

コミット数

は，編集前後で完全一致する行が存在し，その行に含まれる同じactivemq

Java10,021

commons-collections

Java

3,050

ラベルのノードをマッチングしていく．

commons-io

Java2,116

commons-lang

Java

5,263

commons-math

Java

6,317

hibernate-search

Java7,163

図 1 で示したソースコードに対して diff コマンドで行単位のspring-roo

Java

6,132

差分を計算した結果を図 3 に示す．例えば，編集前の 4 行目とvue

JavaScript

2,873

編集後の 4 行目には差分が発生しておらず，完全一致する行でjquery

JavaScript

6,363

ノードは必ずしも 1 行に収まっているとは限らない．複数行にまたがるノードは，ノードの先頭の行とノードの最後の行が差分のない行のときに，マッチングを行う．

—3—

図 4 実験 2 で被験者が編集スクリプトを確認するのに用いたツールの利用例

実験 1： 9 個の OSS を対象に，編集スクリプトが短くなっているか確認する実験
実験 2： 出力された編集スクリプトが実際に開発者にとって理解のしやすいものとなっているか確認するための被験者実験

4. 1 実験 1 について
Java，および JavaScript の OSS を対象に提案手法が GumTreeよりも短い編集スクリプトを出力できているか確かめる実験を行った．表 1 の OSS の全てのコミットに対して，各ファイルごとに GumTree を実行し，編集スクリプトの長さが 50 以上のJava ファイルおよび JavaScript ファイルを実験対象にした．編
集スクリプトの長さが短いものは改善の余地が少ないため，今回は実験の対象に含めていない．
実行した結果を表 2 に示す．どの OSS に対しても，編集スクリプトの長さの合計値と中央値が GumTree と比べて下がって図 5 各差分を理解するのに費やした時間の中央値の箱ひげ図いることがわかる．また，30∼80%の差分に対して，提案手法はGumTree より短い編集スクリプトを出力したこともわかる．

荷とならないように調整するためである．

得られた結果は正規分布に従っていないため，統計的に優位編集スクリプトの確認には，GumTree に含まれているツールかどうかの検定には Wilcoxon の符号順位検定を用いた．その結を用いた．このツールは図 4 のように Web ブラウザで視覚的に果全ての OSS において，p 値が 0.05 を下回り，GumTree と提編集スクリプトを確認することができるツールである．

案手法の間には統計的な優位差があることが確認できた．

まず被験者は，実験対象の 15 個の差分に取り組む前に別の 3

4. 2 実験 2 についてつの差分を確認し，ツールの使い方を学ぶ．その後，実験対象提案手法で短くなった編集スクリプトが開発者にとって理解の 15 個の差分を 1 つずつ確認し，どのような差分だったかを答しやすいものになっているか確認する被験者実験を行なった．

え，差分を確認するのにかかった時間を測る．

被験者は Git と Java を用いた開発の経験が 1 年以上ある 4 人

被験者を X と Y の 2 つのグループに分ける．X のグループの大学生・9 人の大学院生・1 人の研究者の合計 14 人である．

は，1 つ目の差分を GumTree で，2 つ目の差分を提案手法で，3実験 1 で対象にした commons-math の差分の中から，GumTreeつ目の差分を GumTree で，というように GumTree と提案手法が出力する編集スクリプトの長さが 50∼200 のもので，GumTreeを交互に使って編集スクリプトを確認していく．Y のグループと提案手法の差が大きいもの上位 15 個を対象にした．編集スクは，1 つ目の差分を提案手法で，2 つ目の差分を GumTree で，3リプトの長さが 50∼200 のものにしたのは被験者にとって過負つ目の差分を提案手法で，というように X と逆になるように確—4—

1.
/**
2.
* Removes all mappings from this map.
3.
*/
4.
public void clear() {5.
modify();6.
7.
nodeCount = 0;8.
rootNode[KEY] = null;9.
rootNode[VALUE] = null;10. }箟꧊⵸‫اך‬٦‫؝أ‬٦‫س‬

䯏Ⰵ

1.
/**
2.
* Removes all mappings from this map.
3.
*/
4.
public void clear() {5.
modify();6.
7.
nodeCount = 0;8.
rootNode[KEY.ordinal()] = null;9.
rootNode[VALUE.ordinal()] = null;
10. }

⵴ꤐ刿倜

箟꧊䖓‫اך‬٦‫؝أ‬٦‫س‬獳⹛

図 6 提案手法の実行例

れ，5 行目が移動していないのに移動したものと出力されてしま認していく．
各差分の理解に費やした時間の中央値を箱ひげ図にしたもの

う．図 1 と同一のファイルに対して提案手法を実行した例を図 6を図 5 に示す．全体の中央値に関して，提案手法が GumTree のに示す．図 6 は図 1 に比べて理解のしやすい編集スクリプトに半分の時間になっていることが分かる．

なったといえる．例えば，4 行目には行単位の差分が発生してお得られた時間の分布は正規分布に従ってないので，マンホイッ

らず，提案手法ではメソッド宣言のノードをマッチングすること

トニの U 検定を用いて，これらが統計的に優位であるか確認しができる．その結果，5 行目は編集の前後で同一の親を持つものた．サンプル数が少ないため，優位差が得られない差分もあったと扱うことができ，移動していないものとして出力することがでが，全体に関する優位差は得られ，提案手法の方が短い時間で理きる．このように，1 つのノードのマッチングで，他のノードの解することができるといえる．

扱いも変わることが多々あり，結果として短い編集スクリプトを5. 考出力できたと考えられる．

察

実験 2 では提案手法の方が，全体を通して短い時間で差分を理実験 1 では提案手法によって多くの差分で短い編集スクリプ解できることがわかった．理解に要した時間が短く，統計的な有トを出力することに成功しており，そのことからも提案手法が意差がみられた差分は，@Override の追加，などといった比較有効であることは分かる．commons-math の中にある差分では，的単純な差分のものが多かった．一方で，提案手法と GumTree

GumTree では 19,887 ととても長い編集スクリプトを出力したの間で統計的な有意差がみられなかったものは，クラス名の変ものもあった．しかし，提案手法ではその差分の長さを 9,742 に更，メソッドの API の変更といった複数の変更が混じった差分まですることができ，およそ 10,000 以上も短い編集スクリプトのように，差分として複雑ものであった．このことから，提案手を出力できている．

法は複雑な差分よりも単純な差分に対してより有効であること

短い編集スクリプトを出力できた最大の要因は行単位で差分が生じていない場合に，適切にマッチングをすることができたからだと考えられる．例えば，図 1 について再度考えてみる．

が分かる．

6. 妥当性の脅威

GumTree では 4 行目のメソッド宣言について適切にマッチング

提案手法はプログラミング言語に依存しないため，GumTreeをすることができておらず，clear() を削除して挿入，と出力さが適用可能なプログラミング言語の全てに対して適用可能であれている．さらに，メソッド宣言のノードのマッチングができる．実験 1 では，Java，および JavaScript で書かれたプロジェていないということは，5 行目の文の親ノードが変わったと扱わクトに対してのみ実験を行った．他の言語でも同様の結果が得

表 2 実験 1 の結果

OSS

対象の差分の数

合計

中央値

短い編集スクリプトを出力した割合

GumTree

提案手法

5,326 1,001,361

981,435

110

1088%

33%

commons-collections

1,640

426,383

394,574

122

115

3%

50%

commons-io

782

180,821

176,596

124.5

117.5

8%

34%

commons-lang

2,375

627,934600,855

130

126

5%

37%

commons-math

4,435 1,276,316 1,223,448

131

128

7%

39%

hibernate-search

4,364

750,287

105

103

13%

38%

4,880 1,296,941 1,271,632

activemq

spring-roo

766,425

GumTree 提案手法 GumTree

提案手法

130

129

12%

42%

vue

553

934,824

832,328

541

503

6%

84%

jquery2,364

579,349

536,540

103

100

6%

45%

—5—

られると予想されるものの，実際に GumTree よりも有用かどうかはわからない．

7. ま と め
本論文では，行単位の差分情報を用いることで，AST ノードのマッチングの精度を上げ，より短く，理解のしやすい編集スクリプトを出力する手法を提案した．提案手法を評価するために，

9 個の OSS で実験を行い，全てのプロジェクトで編集スクリプトの長さを短くすることに成功した．また，提案手法が出力する編集スクリプトが理解の助けになることを 14 人の被験者に対しternational Conference on Automated Software Engineering,
pp.660–671, ASE 2016, ACM, New York, NY, USA, 2016.
http://doi.acm.org/10.1145/2970276.2970315[9] Y. Higo, A. Ohtani, and S. Kusumoto, “Generating simpler
ast edit scripts by considering copy-and-paste,” The 32nd
IEEE/ACM International Conference on Automated Software Engineering (ASE2017), pp.532–542, Oct. 2017.
[10] S.S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J.
Widom, “Change detection in hierarchically structured information,” Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pp.493–504, SIGMOD ’96, ACM, New York, NY, USA, 1996.
http://doi.acm.org/10.1145/233269.233366て実験を行い，差分理解に費やす時間が全体として減ることを確認できた．
今後の課題としては，Java および JavaScript 以外の言語での実験を行い，提案手法の方が有用かどうかの確認をしていきたい．特に Python のようにインデントが意味を持つようなプログラミング言語の場合，行単位の差分がより発生しにくいと考えられ，Java や JavaScript の差分と比べて提案手法がより有効であると考えられる．
謝辞

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

献[1] E.W. Myers, “Ano(nd) diﬀerence algorithm and its variations,” Algorithmica, vol.1, no.1, pp.251–266, Nov. 1986.
https://doi.org/10.1007/BF01840446[2] J. Falleri, F. Morandat, X. Blanc, M. Martinez, and M.
Monperrus, “Fine-grained and accurate source code differencing,” ACM/IEEE International Conference on Automated Software Engineering, ASE ’14, Vasteras, Sweden - September 15 - 19, 2014, pp.313–324, 2014.
http://doi.acm.org/10.1145/2642937.2642982[3] 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 fine-grainedchanges,” Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp.511–522, FSE 2016, ACM, New York, NY, USA, 2016.
http://doi.acm.org/10.1145/2950290.2950333[4] C. Macho, S. Mcintosh, and M. Pinzger, “Extracting build
changes with builddiﬀ,” Proceedings of the 14th International Conference on Mining Software Repositories, pp.368–378, MSR ’17, IEEE Press, Piscataway, NJ, USA, 2017.
https://doi.org/10.1109/MSR.2017.65[5] J. Yi, U.Z. Ahmed, A. Karkare, S.H. Tan, and A. Roychoudhury, “A feasibility study of using automated program repair
for introductory programming assignments,” Proceedings ofthe 2017 11th Joint Meeting on Foundations of Software Engineering, pp.740–751, ESEC/FSE 2017, ACM, New York, NY,USA, 2017. http://doi.acm.org/10.1145/3106237.3106262[6] Q. Hanam, F.S.d.M. Brito, and A. Mesbah, “Discovering bug patterns in javascript,” Proceedings ofthe 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp.144–
156, FSE 2016, ACM, New York, NY, USA, 2016.
http://doi.acm.org/10.1145/2950290.2950308[7] V. Frick, T. Grassauer, F. Beck, and M. Pinzger, “Generating accurate and compact edit scripts using tree diﬀerencing,” 2018 IEEE International Conference on Software Maintenance and Evolution (ICSME), pp.264–274, 2018.
[8] G. Dotzler and M. Philippsen, “Move-optimized source codetree diﬀerencing,” Proceedings of the 31st IEEE/ACM In-—6—