論文

より短い編集スクリプトを目指して— 行単位の差分情報に基づく GumTree の拡張 —松本淳之介† a)

肥後

芳樹†

楠本

真二†

Towards Generating Shorter Edit Scripts— An Extension of GumTree Based on Line Diﬀerences —Junnosuke MATSUMOTO†a) , Yoshiki HIGO† , and Shinji KUSUMOTO†

あらまし ソフトウェア開発においてコードレビューは頻繁に行われ，レビューをする開発者はソースコードの差分を理解する必要がある．編集前のソースコードを編集後のソースコードに変換する操作の列を編集スクリ
プトと呼び，開発者はその編集スクリプトを理解することでソースコードの差分を理解する．編集スクリプトを出力するツールとして GumTree がある．GumTree は二つのバージョンのソースコードを入力として受けとり，抽象構文木のノード単位の挿入・削除・更新・移動といった 4 種類の操作で構成された編集スクリプトを出力する．しかし，GumTree が更新と移動を検知する精度は低く，差分の理解が困難であるという問題がある．
GumTree の精度が低い原因の一つとして，抽象構文木の情報のみで編集スクリプトを出力しようとすることが挙げられる．そこで提案手法では抽象構文木の情報のみでなく，行単位の差分情報を用いて編集スクリプトを出力する．そしてオープンソースソフトウェアに対して提案手法が有効か実験を行い，提案手法が差分の理解に有効であることを確認した．
キーワード

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

1. ま え が きはなくトークン単位の差分を出力する

ソフトウェア開発においてコードレビューは頻繁にに利用する場合には，二つの問題があると著者らは考行われており，開発者はソースコードの差分を理解すえている．一つ目の問題は差分を出力する粒度が不適

る必要がある．そのような場面において，開発者を支切ということである．開発者が理解したい対象の多く援するためにソースコードの差分を分かりやすく表現

はソースコードである．diff ではソースコードの行する研究が数多く行われている．

の一部しか編集されていないにもかかわらず，その行

しかし，diff や wdiff をソースコードの差分表示

編集前のソースコードを編集後のソースコードに変全てが編集されたと出力され，編集されていないプロ

換する操作の列を編集スクリプトと呼び，開発者はそグラム要素まで編集されたと出力される．また，例えの編集スクリプトを理解することでソースコードの差ば波括弧 ({}) では，始め括弧 ({)・終わり括弧 (}) と分を理解する．編集スクリプトを出力する方法として，いった対応関係があり，二つの括弧で一つのプログラ

コマンドラインツールである Unix の diff を用いる

ム要素を表している．しかし，diff は片方だけが編集ことが多い．diff は Myers のアルゴリズム [1] を基された (若しくはされていない)，という編集スクリプに，行単位でソースコードが挿入・削除されたというトを出力することが多々ある．これらは diff がソー

編集スクリプトを出力する．また，diff から派生しスコードを単なるテキストファイルとして扱っている

たツールも開発されており，例えば wdiff は行単位でことが原因である．このことから，構造化されている
ソースコードの差分を出力するのに diff は適してい†ないことがわかる．

大阪大学，吹田市
Osaka University, Suita-shi, 565–0871 Japana) E-mail: j-matumt@ist.osaka-u.ac.jp
DOI:10.14923/transinfj.2019JDP7100

電子情報通信学会論文誌

二つ目の問題は操作の種類が少ないということである．diff の出力には挿入と削除の 2 種類の操作しかc 一般社団法人電子情報通信学会 2020
D Vol. J103–D No. 8 pp. 579–590 

579

電子情報通信学会論文誌 2020/8 Vol. J103–D No. 8

ない．オプションを指定することで，更新という操作

加えて，行単位の差分の情報を用いたマッチング処理を表現することは可能であるが，あくまで削除と挿入を提案する（注 1）．diff によって変更されたと出力されの組み合わせでしかない．また，トークンの位置が近た行，変更されていないと出力された行の二つにソーいという理由で更新という操作を出力しているが，そスコードを分け，それぞれに対して異なるマッチング

れがプログラム要素として更新されているかは考慮し手法を用いてノードのマッチング処理を行う．

ていない．このようにソースコードの編集において，GumTree よりも短い編集スクリプトを提案手法が開発者が挿入や削除以外の操作をする場合，開発者の出力していることを確認するため，7 個の OSS 差分

意図した編集を表現することができない．

に対して提案手法を実行し，提案手法が有効であるこ

このような問題を解決する手法として GumTree [2]とを確認した．また，提案手法が理解しやすい編集ス

がある．GumTree は抽象構文木のノード単位でソー

クリプトを出力していることを確認するため，14 人のスコードの差分を出力する．更にノードの挿入や削除

被験者に対して実験を行い，GumTree より理解しやといった操作に加えて，ノードの更新や移動といったすい編集スクリプトを出力していることを確認した．

計 4 種類の操作を出力することができる．GumTree

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

及び GumTree を改良した手法が出力した編集スク
リプトは多くの研究で利用されている．例えば API

2. 1 抽象構文木のコードのサジェスト [3] や Maven のビルドファイ

抽象構文木 (以降 AST と呼ぶ) とはソースコードをルの解析 [4]，自動プログラム修正 [5], [6] であったり，表現した木構造である．一つのソースファイルに対し

JavaScript のバグのパターンの発見 [7] などに用いらて一つの AST が構築され，AST の各ノードは以下のれている．ただし，GumTree には移動と更新の検知

五つで構成されている．

精度が低いという課題がある [8]．実際に著者らが目視

ID 各 AST 内で固有の識別子

でオープンソースソフトウェア (以下 OSS と呼ぶ) の親ノードへの参照 各ノードは木構造上の親ノードへ差分を確認したところ，更新であるべき変更が削除しの参照をもつ．ただし根ノードには親が存在しないのて挿入と出力されたり，プログラム要素が移動していで，何も保持しない．

ないのに移動されたと出力されており，編集スクリプ

子ノードへの参照 各ノードは木構造上の子ノードへトが必要以上に長くなった．編集スクリプトが長けれの参照をもつ．ただし葉ノードには子が存在しないのば長いほど，開発者はその編集スクリプトを理解するで，何も保持しない．

ことが難しくなると言われている [8]〜[10]．

ラベル

そこで本研究では，より短く理解のしやすい編集ス
クリプトの生成を目標とし，GumTree の改良を行う．

GumTree の課題である更新や移動の精度をあげるた

値

if 文や変数宣言など文法上の型を表す．

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

2. 2 GumTree の差分検知

めに，編集前のノードと編集後のノードのマッチング

AST の差分を検知する手法として，GumTree [2]

処理をより適切に行う必要がある．マッチング処理とがある．GumTree は入力として編集前のソースコー

は編集の前後でどのノードが同じノードか対応づけ

ドと編集後のソースコードを受けとる．それぞれのることであり，その結果から編集スクリプトを計算す

ソースコードから AST を構築し，それらの木構造のる．例えば，編集前のソースコードのノードが対応づ違いを編集スクリプトとして出力する．

けられなかった場合，GumTree はそのノードが編集

GumTree の出力する編集スクリプトは以下の種類

前のソースコードには存在しているが編集後のソースの操作から構成される．

コードには存在していないと認識し，このノードに対挿入

して削除という編集操作を計算する．どのノードとど

ノードの追加を表す．挿入するノードの ID として t，のノードが対応づけられるかは抽象構文木の構造の情ラベルとして l，値として v ，挿入後に親ノードとす

報を基に計算される．

るノードの ID として tp ，何番目の子にするかを表す

編集スクリプトが長くなる原因として，抽象構文木

insert(t, tp , i, l, v)

数値として i を引数にもつ．

の構造の情報のみを用いたマッチング処理にあると著者らは考えた．そこで本研究では抽象構文木の情報に
580

（注 1）
：本論文は文献 [11] に対して詳細な評価を行った論文である．

論文／より短い編集スクリプトを目指して— 行単位の差分情報に基づく GumTree の拡張 —削除 delete(t)一つの編集スクリプトに含まれる操作の数を本論文

ノードの削除を表す．削除するノードの ID として t

では編集スクリプトの長さと呼ぶ．図 1 に編集スクリを引数にもつ．

プトの例と AST を操作する例を示す．この例の場合，

更新 update(t, v)

編集スクリプトの長さは 6 である．

ノードの値の更新を表す．更新の対象となるノードの

GumTree の処理は以下の二つで構成されている．

ID として t，新しい値として v を引数にもつ．

（ 1 ） ノードのマッチング処理

移動 move(t, tp , i)

（ 2 ） マッチング処理の結果を基にした編集スクリ

部分木の移動を表す．移動する部分木の根ノードの ID

プトの計算処理として t，移動先の親ノードの ID として tp ，何番目の子にするかを表す数値として i を引数にもつ．

GumTree が行うノードのマッチング処理はトップ
ダウンフェーズとボトムアップフェーズの 2 段階で構

図 1 編集スクリプトの例と，その編集スクリプトに基づいて AST を操作する例
Fig. 1 An example of an edit script, and an exmple that it converts AST.

581

電子情報通信学会論文誌 2020/8 Vol. J103–D No. 8

図 2 GumTree の実行例
Fig. 2 The results of GumTree.

成されている．まずトップダウンフェーズでは，入力された二つの AST の根から辿っていき，二つの AST

3. 研 究 動 機

間で完全一致する部分木を対応づける．ボトムアップ

GumTree はしばしば不適切な対応づけを行い，そフェーズでは，トップダウンフェーズで対応づけられの結果必要以上に長い編集スクリプトを出力する問

た部分木の根ノードから，編集前の親を辿り，その編題がある．図 2 にその例を示す．これは Commons-

集前の親ノードと対応づける候補のノードを編集後のCollections（注 2）内のある二つのコミット（注 3）間の Tree-

AST から探す．ボトムアップフェーズでは候補のノー

BidiMap.java に対して GumTree を実行し，出力さドを根とした部分木の類似度を計算し，それがしきい

れた編集スクリプトの一部である．左右のソースコー

値を超えていれば対応づける．

ドを見比べると，8 行目と 9 行目しか編集されていな

その後，マッチング処理の結果を基に GumTree は

いにもかかわらず，GumTree は全ての行が挿入，削編集スクリプトを計算する．マッチング処理の結果か

除，若しくは移動されたと出力している．例えば 4

ら，各ノードは以下の三つに分類される．

行目は削除と挿入になっている．これは編集前後の•編集前の AST にのみ存在するノード

public や void などのノードが対応づけられていな•

編集後の AST にのみ存在するノード

いことが原因である．もし編集前後で public を対応•

編集前後の AST に存在するノード

づけることができれば，GumTree は編集前に存在し編集前にのみ存在するノードは，言い換えれば編集後た public が編集後にも存在していると認識することには消えているので編集によって削除されたことがわができ，public が削除・挿入されたとは出力しない．

かる．同様に編集後にのみ存在するノードは編集に

この編集前後のノードのマッチング処理の結果をよって挿入されたことがわかる．編集前後の AST に

図 3 に示す．GumTree はトップダウンフェーズで完存在するノードの値が変わっていればそのノードが更全一致する高さが 2 以上の部分木を対応づけ，その結新されたことがわかる．また，編集前後の AST に存果図 3 のようになる．GumTree はトップダウンフェー

在し，挿入や削除を考慮した上で親ノードに対する並ズの後にボトムアップフェーズのマッチング処理を行

び順が編集前後で変わっていたり，編集前後で親ノー

うが，ボトムアップフェーズのマッチング処理はそのドが変わっていれば，そのノードの位置が移動したこ

ノードの部分木の類似度が高くなければ対応づけない．

とがわかる．同じ親ノード，親ノードに対して同じ位

そのため，この例のようにトップダウンフェーズで対置，かつ同じ値であればそのノードは編集されていな応づけられたノードの数が少ない場合，そのノード

いことがわかる．

は対応づけられない．例えば MethodDeclaration の

このように，マッチング処理の結果から GumTree

ノードの場合，そのノードの部分木の類似度は低く，は編集スクリプトを計算することができる．二つの木

ボトムアップフェーズで MethodDeclaration のノーとマッチング処理の結果からその木構造の違いを計算

ドは対応づけられない．

する際の計算に GumTree は Chawathe らのアルゴリ

このように GumTree は AST の構造の情報のみを

ズム [12] を採用している．このアルゴリズムの計算量利用してマッチング処理を行い，結果として必要以上は最適化されており，編集スクリプトを計算する上での改善すべき瑕疵が知られていない．
582

（注 2）
：https://github.com/apache/commons-collections（注 3）：コミットID: d16bc8509fc423540a131184552649de1bbcaf98

論文／より短い編集スクリプトを目指して— 行単位の差分情報に基づく GumTree の拡張 —図3

マッチング処理の結果．白色のノードは対応づけられたノードを，灰色のノードは対応づけられなかったノードを表している．図を簡潔にするため，この図では部分
木単位での対応づけのみ示しているが，実際は各ノードが 1 対 1 で対応づけれられている．
Fig. 3 The example which presents matching of AST nodes. White nodes arematched node, and gray nodes are non-matched nodes. In this ﬁgure, we
showed the matching results per subtree in order to make the ﬁgure simple.

に長い編集スクリプトを出力する．

更されてどの行が変更されていないかがわかる．それ4. 提 案 手 法らの情報を基に提案手法ではソースコードを，変更が4. 1 概て異なるアプローチで探索範囲を狭めたマッチング処

要ない行と変更がある行の二つに分け，それぞれに対し提案手法は GumTree を基にしている．GumTree

理を行う．探索範囲を狭めたマッチング処理の後，対では編集スクリプトの計算は十分に最適化されている

応づけられていないノードに対して GumTree のマッので，提案手法ではノードのマッチング処理を改善す

チング処理を行い，それらの結果から編集スクリプト

る．提案手法の概要を図 4 に示す．マッチング処理のの計算をする．図 5 は図 2 のソースコードに対して提精度を上げるために，提案手法では AST に関する情案手法を実行した結果である．この編集スクリプトは報だけでなく，diff を用いた行単位の差分情報を用い

図 2 の編集スクリプトより簡潔に差分を示せている．

る．GumTree によるマッチング処理を行う前に diffから得られた情報を基にマッチング処理を行う．

diff で出力される行単位の差分から，どの行が変4. 2 変更がない行
diff で変更がないと出力された行は，開発者は実際に編集していないと提案手法では扱う．変更がないと
583

電子情報通信学会論文誌 2020/8 Vol. J103–D No. 8

Fig. 4

Fig. 5

Fig. 6図 4 提案手法の概要
The overview of our methodology.

図 5 提案手法の実行例
An edit script generated by our methodology.

図 6 図 2 のソースコードに対して diff を実行した結果
The results that we executed diﬀ command for the source code diﬀerencein Figure 2.

出力された行は，編集前後で完全一致する行が存在し，

4. 3 変更がある行

その行の中の全てのノードが対応づけられる．ノード

変更がある行については，diff で出力された削除は必ずしも 1 行に収まっているとは限らない．複数行と挿入を関連づけし，その関連づけられた中でノードにまたがるノードは，ノードの先頭の行とノードの最の対応づけを行う．変更がある行の前後には，変更が後の行が変更のない行のときに対応づける．

ない行が存在し，それらが編集の前後で共通している

図 2 で示したソースコードに対して diff で行単位とき，その削除と挿入を関連づける．連続した複数のの差分を計算した結果を図 6 に示す．例えば，編集前

行がまとめて削除・挿入されている場合はそれらの行の 4 行目と編集後の 4 行目は変更のない行であり，完を一つの削除と挿入としてまとめて関連づける．

全一致する行である．そこで編集前後の 4 行目に含ま

図 7 を例に考える．図 7 の編集前のソースコード

れる各ノードを対応づける．このようなマッチング処の 2 行目と 3 行目には削除が出力されており，その前理を行うことで 3. で説明したような AST の構造のみ

後の 1 行目と 4 行目は変更がない行である．変更がな

では対応づけられなかった public などを対応づける

い行は編集の前後で対応関係があるので，編集前の 1

ことが可能となる．

行目に対応するのは編集後の 1 行目である．同様に編584

論文／より短い編集スクリプトを目指して— 行単位の差分情報に基づく GumTree の拡張 —Table 1OSS
dnsjava
Eclipse JDT Core
JHotDraw
JUnit4Log4j
StrutsTomcat

表 1 実験 1 の結果
The results of the experiment 1.

コミット数

対象の差分の数

1,749
24,054
2,186
2,397
3,275
5666
21,097

5,539
364,872
29,463
14,864
27,46052,44452,876

短い編集スクリプトを出力した割合
GumTree
提案手法
3.97%
17.73%
3.66%
22.06%
2.98%
8.39%
3.20%
20.04%
3.23%
41.11%
1.05%
7.58%
3.32%
18.10%

究 [2] で用いられているデータセット [13] を実験に用いた．これは CVS で管理されている 14 個の Java のOSS を集めたデータセットである．実験ではその 14個の OSS のうち，Git に移行された 7 個の OSS を対象とした．実験対象の OSS を表 1 に示す．これらのOSS に対して，master ブランチ (master ブランチが
図7

行単位の差分の例．破線は変更のない行の対応関係を表している．
Fig. 7 The example of diﬀ command’s results.
Dashed lines present matching lines.

存在しない場合はメインで開発されているブランチ)に含まれる各コミットの Java ファイルの差分を実験対象とした．実験対象の差分ごとに GumTree と提案
手法を実行し，出力される編集スクリプトの長さを比較する．

集前の 4 行目に対応するのは編集後の 4 行目である．

実験の結果を表 1 に示す．7% ∼ 40%の差分に対しこれらの情報から，編集前の 1 行目と 4 行目に挟まれて，提案手法の方が短い編集スクリプトを出力した．

た削除と，編集後の 1 行目と 4 行目に挟まれた挿入を

一方，1% ∼ 4%の差分に対しては，提案手法の方が関連づける．一方，7 行目の削除の前後は 6 行目と 8

GumTree より長い編集スクリプトを出力した．

行目であり，それらに対応するのは編集後の 7 行目とまた，どのような差分に対して提案手法が有効か確

8 行目である．しかし，7 行目と 8 行目の間に挿入さ認するため，GumTree が出力した編集スクリプトの長れた行が存在しないため，7 行目の削除はどの挿入とさで分類した結果を表 2 に示す．各範囲の編集スクリも関連づけられない．5 行目の挿入についても同様で

プトの長さは正規分布に従っていないため，Wilcoxon

ある．

の符号順位検定を用いて統計的に有意であるか検定

削除と挿入を関連づけられたら，その中のノードにを行った．その結果全ての範囲において，p 値が 0.05

対してマッチング処理を行う．まず同じ値，同じラベを下回り，GumTree と提案手法の間には統計的に有ルをもつ葉ノードを探し，対応づける．その後対応づ

意な差があることが確認できた．また，Cliﬀ のデル

けられた葉ノードを起点に GumTree のボトムアップ

タ [14] を用いて効果量を求めたところ，多くの範囲でアルゴリズムを適用し，他のノードを対応づける．

無視できない結果となっており，5,000 ∼ 10,000 の範

5. 実

験

囲で提案手法が特に有効であることがわかる．

5. 2 実験 2 について

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

提案手法で短くなった編集スクリプトが開発者に

実験 1 7 個の OSS を対象に，編集スクリプトが短くとって理解しやすいか確認する被験者実験を行った．

なるか確認する実験

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

実験 2 開発者にとって理解しやすい編集スクリプト

4 人の大学生・9 人の大学院生・1 人の大学教員の合計が出力されることを確認するための被験者実験14 人である．

5. 1 実験 1 について実 験 に は Apache Commons Math を 用 い た ．

OSS を対象に，提案手法が GumTree よりも短い

Apache Commons Math を用いたのは，扱うドメ

編集スクリプトを出力できるか実験を行った．既存研インが数値計算であり，ネットワークや DB を扱う
585

電子情報通信学会論文誌 2020/8 Vol. J103–D No. 8
表 2

実験 1 の結果を GumTree が出力した編集スクリプトの長さに基づいて分類した
結果
Table 2 The results that the edit scripts in experiment 1 were classiﬁed based on
the size of GumTree’s edit script.
GumTree が出力した対象の差分の数
編集スクリプトの長さの範囲
0 ∼ 50340,03950 ∼ 100
51,348100 ∼ 150
26,594150 ∼ 200
14,683200 ∼ 250
10,531250 ∼ 300
6,484
300 ∼ 350
6,073
350 ∼ 400
4,866
400 ∼ 4503,916
450 ∼ 500
2,967
500 ∼ 550
2,685
550 ∼ 600
2,326
600 ∼ 650
1,841
650 ∼ 700
1,060
700 ∼ 750
1,241
750 ∼ 800
828
800 ∼ 850695
850 ∼ 900
586
900 ∼ 950662
950 ∼ 1,000
1,199
1,000 ∼ 2,000
8,109
2,000 ∼ 3,000
1,440
3,000 ∼ 4,000
741
4,000 ∼ 5,000
261
5,000 ∼ 6,000
404
6,000 ∼ 7,000
290
7,000 ∼ 8,000
228
8,000 ∼ 9,000
97
9,000 ∼ 10,000
50
10,000 ∼38

実行時間の中央値 (秒)GumTree
提案手法
0.04
0.04
0.10
0.11
0.13
0.15
0.13
0.16
0.15
0.19
0.14
0.2
0.18
0.25
0.19
0.28
0.17
0.26
0.18
0.24
0.29
0.40
0.33
0.52
0.20
0.32
0.29
0.40
0.52
0.79
0.37
0.56
1.02
1.74
0.40
0.87
0.78
1.41
0.47
0.84
0.79
1.44
0.95
2.48
2.52
3.82
2.82
25.81
0.65
1.08
2.65
27.64
4.11
9.77
2.94
8.56
0.64
10.11
1.59
13.82

長さの中央値
GumTree 提案手法
8
8
71
68
121
117
173
167
223
214
277
266
327
313
375
358
423
409
467
456
530
514
577
554
627
606
673
655
722
703
774
756.5
824
802
874
845
928
916
982
953
1,334
1,289
2,451
2,332
3,315
3,254
4,537
4,209
5,198
5,170
6,237
6,026
7,404
7,079
8,093
8,013
9,767
9,233
11,207 10,120.5

長さについての効果量
negligible
negligible
small
small
small
small
mediummediummediummediummediummediumlarge
mediumlarge
mediumlarge
large
mediumlarge
negligible
small
small
medium
large
large
large
large
large
mediumOSS などと異なり，差分を理解する際にプログラミンを避けるため，GumTree が出力する編集スクリプト

グ以外の知識を必要としないからである．

の長さが 50 ∼ 200 の差分を用いた結果，図 8 から分

Apache Commons Math の 差 分 の 中 か ら ，かるとおり二つの手法間での長さの差が −5 ∼ 0 の範

GumTree が出力する編集スクリプトの長さが 50 ∼囲に多くの差分が集中した．これは長さが 50 ∼ 200

200 で，どちらが短いかに関係なく GumTree の編集スの編集スクリプトは既に最短な編集スクリプトである

クリプトと提案手法の編集スクリプトの差が大きい上場合が多く，二つの手法が出力する編集スクリプトに位 15 個を対象にした．編集スクリプトの長さを 50 ∼差がないからである．二つの手法が同様の長さの編集200 に限定したのは被験者にとって過負荷とならない

スクリプトを出力するこのような差分を用いても，提ように調整するためである．Apache Commons Math

案手法が GumTree よりも理解しやすい編集スクリプの差分の数は 24,989 個であり，その中で GumTree がトを出力できているか確認することができないため，出力する編集スクリプトの長さが 50 ∼ 200 であった

今回の実験では理解に差が出やすい差分を用いた．

差分の数は 2,941 個であった．また，その 2,941 個の提案手法が出力する編集スクリプト，及び GumTree

差分に対して，二つの手法が出力した編集スクリプトが出力する編集スクリプトの確認には，図 2 や図 5 のの差の分布を図 8 に示す．

ように Web ブラウザで視覚的に編集スクリプトを確

また，二つの手法間での編集スクリプトの長さの差認することができる GumTree の機能を用いた．このが大きい 15 個を用いたのは，明確に異なる編集スク

機能は編集スクリプト内の編集操作の順序によって表

リプトを用いることで実験結果に差を出しやすくする

示が変わることはない．

ことが目的である．被験者にとって過負荷になること
586

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

論文／より短い編集スクリプトを目指して— 行単位の差分情報に基づく GumTree の拡張 —Fig. 8図 8 各手法が出力した編集スクリプトの長さに対する差の分布
The distribution of diﬀerences between the lengths of an edit script generated by each methodology.

前に別の三つの差分を確認し，ツールの使い方を学ぶ．
その後，実験対象の 15 個の差分を一つずつ確認し，どのような差分だったかを答え，差分を確認するのにかかった時間を測る．
被験者を X と Y の二つのグループに分ける．このとき，グループ内の大学生，大学院生，教員の人数が均等になるように割り振った．X のグループは，奇数番目の差分に対して GumTree が出力する編集スクリ
プトを確認し，偶数番目の差分に対して提案手法が出力する編集スクリプトを確認する．Y のグループは，奇数番目の差分に対して提案手法が出力する編集スク
リプトを確認し，偶数番目の差分に対して GumTreeが出力する編集スクリプトを確認する．なお，被験者にはどちらの手法の差分を確認しているか知らせずに

図9各差分を理解するのに費やした時間の中央値の箱ひげ図
Fig. 9 The results of experiment 2: the medians oftime for each diﬀerence.

実験を行った．

15 個の差分の順番はランダムに決めた．奇数番目のきるので，理解が不十分な差分は 210 個（差分 15 種

差分と偶数番目の差分に対して，提案手法と GumTree

類 × 被験者 14 人）のうち 3 個のみであり，それらはの編集スクリプトの差の平均を求めたところ，長さは全て GumTree が出力した差分であった．

6 しか変わらず，奇数番目の差分と偶数番目の差分に

図 9 は各差分の理解に費やした時間の中央値を箱ひ対して，編集スクリプトの長さがどちらかに偏ってはげ図で表している．全体の中央値に関して，提案手法

いない．

が GumTree の半分の時間になっている．

被験者は時間を計りながり差分を確認する．被験者得られた時間の分布は正規分布に従っていないので，はその差分でどのような変更が行われてたのかを理解

Mann Whitney の U 検定を用いて，これらが統計的し，その理解に費やした時間とその変更の内容をテキに有意であるか確認した．サンプル数が少ないため有ストファイルに記述する．

意な差が得られない差分もあったが，全体に関する有

著者らがそのテキストファイルを読み，各差分の変更内容に対して明らかに間違った内容を記述している，
若しくは各差分の変更内容を表現するのに明らかに説明が足りていない場合，その差分を十分に理解できて意な差は得られ，提案手法の方が短い時間で理解することができたといえる．

6. 考

察

いないと扱い，取り除いた．制限時間を設けていない

実験 1 では提案手法によって多くの差分で短い編集ため，被験者は理解するまで差分を確認することがでスクリプトを出力することに成功しており，そのこと
587

電子情報通信学会論文誌 2020/8 Vol. J103–D No. 8からも提案手法が有効であることは分かる．表 2 の結できないためだと考えられる．

果から，GumTree の出力する編集スクリプトの長さ

また，表 2 の結果からわかるように多くの範囲でが 0 ∼ 300 である差分に対しては提案手法も同等の実行時間が長くなった．多くの範囲では高々1 秒の増

長さの編集スクリプトを出力し，GumTree の出力す加ではあるものの，一部の範囲では 10 秒以上も長くる編集スクリプトの長さが 1,000 を超える差分に対しなった．実行時間が 10 秒も以上長くなった範囲は，て，提案手法は中央値が 50 以上も短い編集スクリプト

GumTree の出力する編集スクリプトの長さが 1,000を出力している．これらのことから，今回の実験では以上の範囲であることから，提案手法は変更の量が多GumTree が出力する編集スクリプトの長さが 1,000

いほど長い実行時間を必要とすると考えられる．これを超える差分に対して提案手法は特に有効的であり，は特に変更された行数が多いときに顕著であり，関連

GumTree の出力する編集スクリプトが長いほど提案づけられた削除と挿入のそれぞれの行数が多いと関連手法が有効であると考えられる．実際，GumTree のづけるノードの候補の数が増えるため，関連づけられ出力した編集スクリプトの長さが 31,484 と長い差分た削除と挿入の中からノードの対応づけを行う処理がも実験対象の中には存在したが，提案手法ではその差実行速度を低下させていると考えられる．

分の長さを 10,195 にまで減らすことができ，およそ

実験 2 では提案手法の方が，全体を通して短い時間

20,000 以上も短い編集スクリプトを出力できていた．

で差分を理解できていた．理解に要した時間が短く，また効果量が 4,000 ∼ 10,000 の範囲で large になって統計的に有意な差がみられた差分は，@Override の追いることからも，GumTree が長い編集スクリプトを加といった比較的単純な差分が多かった．一方で統計出力した差分に対して提案手法が特に有効であること的な有意な差が出なかった差分は，クラス名の変更やがわかる．以上のことから，提案手法は全ての範囲に

メソッドの API の変更といった複数の変更が一つの差

おいて GumTree より短い，若しくは同等の編集スク分の中に存在し，差分として複雑であった．また，どリプトを出力できていることがわかる．

ちらの差分についても提案手法の方が短い編集スクリ

短い編集スクリプトを出力できた最大の要因は完全

プトを出力していた．これらのことから，差分の理解

一致する行に含まれるノードに対して，適切に対応づという点で，提案手法は複雑な差分よりも単純な差分けることができたからだと考えられる．再度，図 2 とに対してより有効であることが分かる．

図 5 について考えてみる．図 2 では 4 行目のメソッ
ド宣言について適切に対応づけることができておらず，

7. 関 連 研 究

clear() を削除して挿入，と出力されている．更に，Guillermo らは，GumTree が出力する編集スクリメソッド宣言のノードが対応づけられていないことか

プトが開発者の意図を十分に表現できていないと指摘

ら，5 行目の modify(); の親ノードが変わったと扱わしている [15]．彼らは GumTree を C#のプロジェク

れ，5 行目が移動していないのに移動したと出力され

トに適用し，86 個の差分のうち 27%の差分が開発者る．一方，図 5 は図 2 に比べて理解のしやすい編集の意図を表現できていなったと述べている．GumTree

スクリプトになったといえる．例えば，4 行目には行のマッチング処理に問題があることを指摘し，更に単位の差分が発生しておらず，提案手法ではメソッド

GumTree は AST を単なる木構造と扱っていること

宣言のノードを対応づけることができる．その結果，に問題があると述べている．彼らは GumTree がマッ

5 行目は編集の前後で同一の親をもつと扱うことがでチング処理をする際に，プログラミング言語の特徴を

き，移動していないと出力することができる．このよ考慮する必要があると提言している．

うに，一つのノードを対応づけることで，他のノード

また，Veit らはプログラミング言語の特徴を考の扱いも変わり，結果として短い編集スクリプトを出慮した GumTree の拡張として IJM (Iterative Java

力できたと考えられる．

Matcher) を提案している [8]．IJM は Java の特徴を

一方，1% ∼ 4%の差分に対して提案手法は GumTree

利用し，(1) 部分的な対応づけ (2) 名前による対応づよりも長い編集スクリプトを出力した．これは，メソッ

け (3) ノードのマージ，の三つのアプローチで構成さド抽出リファクタリングなど，編集の前後でメソッドれている．部分的な対応づけでは同一のメソッドからに抽出されたノードの位置が大きく変わる変更を行っ

該当するノードを探す．名前による対応づけでは，変た場合に，削除と挿入の関連付けを適切に行うことが数名などの名前を考慮する．ノードのマージでは差分588

論文／より短い編集スクリプトを目指して— 行単位の差分情報に基づく GumTree の拡張 —を理解する際に不必要なノードを親ノードとマージしは著者らが手作業により行ったため，その判断には著た AST を構築する．これら三つの手法により，短く者らの主観が含まれている．そのため，第三者が判断正確な編集スクリプトの出力を行う．

を行った場合，同様の結果になるとは限らない．

一方，IJM は Java に特化した手法であるため，Java以外のプログミング言語に適用できない．更に AST

9. む す びの構造を変更しているため，差分の理解には適してい

本論文では，行単位の差分情報を用いることで，ASTるが，自動プログラム修正などの GumTree を応用しノードを対応づける精度を上げ，より短く，理解のした研究で用いることができないという問題がある．

やすい編集スクリプトを出力する手法を提案した．提なお，IJM は AST の構造を変更し，ノードの数が案手法を評価するために，7 個の OSS で実験を行い，変わってしまうため，編集スクリプトの長さの違いを全てのプロジェクトで編集スクリプトの長さを短くす

平等に評価することが難しいので，今回の実験では比ることに成功した．また，提案手法が出力する編集ス

較対象にしていない．ただし，提案手法と IJM は排クリプトが理解の助けになることを 14 人の被験者に他的な手法ではなく，組み合わせて使うことができる

対して実験を行い，差分理解に費やす時間が全体としと著者らは考えている．

て減ることを確認できた．

また，著者らは異なる手法で GumTree の拡張を

今後の課題としては，Java 以外の言語での実験を行行っている [10]．この手法は提案手法と同様に編集ス

い，提案手法の方が有用かどうかの確認をしていきた

クリプトの長さを短くし，より理解しやすい編集スク

い．特に Python のようにインデントが意味をもつよ

リプトを生成することを目的としている．GumTree

うなプログラミング言語の場合，行単位の差分がよりを拡張し，挿入・削除・移動・更新の他にコピーアン発生しにくいと考えられ，Java の差分と比べて提案手

ドペーストという編集操作を追加している．編集操作

法がより有効であると考えられる．

を追加するため，提案手法と全く異なる編集スクリプ

謝辞 本研究は日本学術振興会科学研究費補助金基トを出力するため，純粋な比較を行うことができない

盤研究 (B) (課題番号:17H01725) の助成を得て行わため，今回の実験では比較していない．なお，この手れた．
文法と提案手法も IJM と同様排に他的な手法ではなく，提案手法と組み合わせて使うことができると著者らは[1]

献E.W. Myers, “Ano(nd) diﬀerence algorithm and its
variations,” Algorithmica, vol.1, no.1, pp.251–266,

考えている．

Nov. 1986.

8. 妥当性の脅威[2]

J. Falleri, F. Morandat, X. Blanc, M. Martinez, and
M. Monperrus, “Fine-grained and accurate source

実験 1 では恣意的にデータセットを選ぶことを避け

code diﬀerencing,” ACM/IEEE International Confer-

るために，既存研究 [2] で用いられているデータセッ

ence on Automated Software Engineering, ASE ’14,
Vasteras, Sweden - Sept. 15 - 19, 2014, pp.313–324,

ト [13] を用いた．このデータセットは Java を対象にしているため，実験対象は Java で記述された OSS の

2014.
[3]

A.T. Nguyen, M. Hilton, M. Codoban, H.A. Nguyen,
L. Mast, E. Rademacher, T.N. Nguyen, and D. Dig,みとなった．Java 以外のプログラム言語でも同様の結“Api code recommendation using statistical learn-

果が得られるとは限らない．

ing from ﬁne-grained changes,” Proc. 2016 24th

実験 2 で用いた Web ブラウザで編集スクリプトを

ACM SIGSOFT International Symposium on Foun-

確認するツールは編集操作の順序によって表示が変わ

dations of Software Engineering, FSE 2016, pp.511–
522, 2016.

ることはない．そのため編集操作の順序が理解に影響を与えるかどうかは評価していない．

[4]

ing build changes with builddiﬀ,” Proc. 14th Interna-

実験 2 では被験者が大学生，大学院生，教員である

tional Conference on Mining Software Repositories,

かに基づいて被験者を二つのグループに分けて実験を行った．プログラミングの経験年数など他の指標に基づいてグループ分けを行った場合，実験の結果が変わる可能性がある．
実験 2 の差分の理解が十分であったかどうかの判断

C. Macho, S. Mcintosh, and M. Pinzger, “Extract-

MSR ’17, pp.368–378, 2017.
[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,” Proc. 2017 11th Joint Meetingon Foundations of Software Engineering, ESEC/FSE

589

電子情報通信学会論文誌 2020/8 Vol. J103–D No. 8

松本淳之介

2017, pp.740–751, 2017.
[6]

M. Tufano, J. Pantiuchina, C. Watson, G. Bavota,
and D. Poshyvanyk, “On learning meaningful codechanges via neural machine translation,” Proc. 41stInternational Conference on Software Engineering,
ICSE ’19, pp.25–36, 2019.

[7]

平成 30 大阪大学基礎工学部情報科学科卒業．現在，大阪大学大学院情報科学研究科博士前期課程在学中．リポジトリマイニ
ングに関する研究に従事．

Q. Hanam, F.S.d.M. Brito, and A. Mesbah, “Discovering bug patterns in javascript,” Proc. 2016 24th
ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016, pp.144–
156, 2016.

[8]

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.

[9]

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

[10]

肥後 芳樹

（正員）

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

Y. Higo, A. Ohtani, and S. Kusumoto, “Generating simpler ast edit scripts by considering copy-andpaste,” The 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE2017),
pp.532–542, Oct. 2017.

[11]

J. Matsumoto, Y. Higo, and S. Kusumoto, “Beyond gumtree: A hybrid approach to generate edit
scripts,” Proc. 16th International Conference on Mining Software Repositories, MSR ’19, pp.550–554,
2019.

[12]

S.S. Chawathe, A. Rajaraman, H. Garcia-Molina,
and J. Widom, “Change detection in hierarchicallystructured information,” Proc. 1996 ACM SIGMODInternational Conference on Management of Data,
SIGMOD ’96, pp.493–504, 1996.

[13]

M. Monperrus and M. Martinez, Cvs-vintage:

A

dataset of 14 cvs repositories of java software, 2012.
[14]

N. Cliﬀ, “Dominance statistics: Ordinal analyses toanswer ordinal questions,” The Psychological Bulletin, vol.114, pp.494–509, 1993.

[15]

G. de laTorre, R. Robbes, and A. Bergel, “Imprecisions diagnostic in source code deltas,” Proc. 15th
International Conference on Mining Software Repositories, MSR ’18, pp.492–502, 2018.

（2019 年 12 月 25 日受付，2020 年 3 月 13 日再受付，
4 月 24 日早期公開）

590

楠本 真二

（正員）

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