ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

編集スクリプトへのコピーアンドペースト操作の導入によるコード差分の理解向上の試み
大谷 明央1,a)

肥後 芳樹1,b)

楠本 真二1,c)

概要：ソフトウェアの変更内容を理解することはコードレビュー等において重要であり，これまでに数多
くの変更内容の理解支援を行う手法が提案されている．その中でも抽象構文木を用いた手法はプログラムの構造を考慮して変更内容を表現するため，Diﬀ のような行単位の表現に比べて人間が理解しやすいとされている．本研究では，既存の抽象構文木を用いた手法を改良することにより，より理解しやすく変更を表現する手法を提案する．提案手法では，ソースコードの実装において開発者がしばしば行うコピーア
ンドペーストの操作を取り入れて，変更を表現する．提案手法を実装して，複数のオープンソースソフト
ウェアに対して適用し，その有効性が確認できた．

1. はじめに一方の抽象構文木をもう一方の抽象構文木に変更するための操作の手順を表したものである [7]．編集スクリプトにソースコードのレビューやバージョン管理システムにおおいて，変更内容は抽象構文木の頂点への操作の連なりとける変更の競合が発生した場合のように，ソースコードにして表現される．変更において行われる操作が多いほど，対して行われた変更を詳しく理解する必要がある状況が存

人間が変更内容を理解する負担が大きくなるため，編集ス

在する．そのような場面において，ソフトウェア開発プロ

クリプトの長さを用いることで人間が変更内容を理解する

ジェクトに携わる人間を支援するために，変更の内容をわ際の労力を表すことができる [8]．生成される編集スクリ

かりやすく表現する研究が数多く行われている．

プトが短いほど人間にとって変更内容を理解しやすい．

ソースファイルの変更内容を表現する手法のうち広く使

抽象構文木に基づく手法には，非常に多くの頂点を含む

われるのは，テキストに基づいて変更内容を表示する手

抽象構文木を対象にした場合や，頂点の移動を考慮した場法である [1][2][3]．例えば，Unix の diﬀ では，入力として合において，編集スクリプトの生成に長い時間を要するとソースファイルを 2 つ与えると，Myers のアルゴリズム [1]いう課題点がある．この課題点を解決するために，Falleriを適用し，行の追加や削除を示して変更内容を表現する．

らは，編集スクリプトの生成の過程で経験則を用いること

しかし，テキストに基づく手法には，プログラムの構造をで大きな抽象構文木に対しても効率的に移動を考慮した編考慮できていないという弱点がある．そのため，表現され集スクリプトを生成する方法を考案した [8]．また，Falleri

た変更内容が人間にとって理解しやすいものになるとは限らは実際のソフトウェア開発に用いられたリポジトリを対らない．

象に実験を行い，Falleri らの手法が実用的な速度で動作す

テキストに基づく手法の弱点を克服した手法として，抽ることを示した．また他の手法と比較することで，生成す象構文木を用いた手法がある [4][5][6][7]．抽象構文木に基る編集スクリプトが人間にとってより理解しやすいことをづく手法は，プログラムの構造を考慮して変更内容を表現示した．

するため，人間はその変更内容をより理解しやすい．抽象本研究では，既存の手法よりもさらに人間にとって理解

構文木に基づく手法では，編集スクリプトを生成することしやすく変更内容を表現することを目的として，Falleri らにより，プログラムの構造を考慮して変更内容を表現する．

の手法を改良した．Falleri らの手法では挿入，削除，移動，編集スクリプトとは，2 つの抽象構文木が与えられたとき，更新を組み合わせて変更内容を表現する．しかしながら，

1

a)
b)
c)

大阪大学
Osaka University, Suita, Osaka 565–0810, Japana-ohtani@ist.osaka-u.ac.jp
higo@ist.osaka-u.ac.jp
kusumoto@ist.osaka-u.ac.jp©2016 Information Processing Society of Japan

ソースコードの実装においては，上記の操作に加えてコピーアンドペーストも頻繁に行われる [9][10]．そのため，
コード片のコピーアンドペーストが行われた場合，Falleriの手法を用いると，新しい頂点が多数挿入されたかたちで4ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

変更内容が表現される．その結果，編集スクリプトが長く

public	  class	
  Test{	  	
  public	  String	
  foo(int	  i){	  	  	  	
  if(i	
  ==	
  0)	
  return	
  "Foo!";	
  
	
  }	
  
}	

なってしまう．
本研究では，コピーアンドペースト操作を導入した編集
スクリプトの生成手法を提案する．コピーアンドペースト(a) ソースコード操作を導入することにより，より短い編集スクリプトを生成できるようになるため，人間にとってより理解しやa	

すい表現になると著者らは考えた．また，本研究では，提b	

案手法を実装し，手法の有効性を評価するための実験を行った．実験では，14 のオープンソースソフトウェアのリ
ポジトリを含む CVS-Vintage dataset を対象とし，13,699の変更を対象に提案手法と Falleri らの手法を比較した．

CVS-Vintage dataset は Felleri らが実験に利用したデータc	f	

Modiﬁer:	  	
  public	d	Compila(on	
  
Unit	

Type	
  
Declara(on	e	SimpleName:	
  
Test	

Method	  Declara(on	g	Modiﬁer:	  	
  public	

k	

i	

h	

SimpleType	l	

SimpleName:	  String	

Primi(veType:	  int	

セットであり，本研究でも同じデータセットに対して実験を行う．実験の結果，提案手法を用いることにより従来手

j	SingleVariable	
  Declara(on	

SimpleName:	
  foo	

m	

SimpleName:	
  i	

Block	n	
IfStatement	o	
 InﬁxExpression:	
  

p	

r	

s	

==	

q	

法に比べて短い編集スクリプトと生成できることを確認した．以下に，実験によって得られた結果をまとめる．

SimpleName:	
  i	

NumberLiteral:	  0	

Return	  Statement	

StringLiteral:	  “Foo!”	(b) AST• 18%の変更に対して提案手法が生成する編集スクリプ

図 1: AST の例

トは Falleri らの手法が生成する編集スクリプトより短い．

• 残りの 82%の変更では，両者の長さは同じであった．

が同一であることがわかっている [10]．コピーアンドペー• 提案手法の実行時間は Falleri らの手法と比較して長ストによって生成されたソースコードは，コピー元のソー

くなるが，96%の変更において Falleri らの手法の 1.5

スコードとコードクローン関係になる．

倍以内の時間で実行することができる．

• 96%の変更において提案手法は 2 秒以内に編集スクリ
プトを生成することができる．

2. 準備
2.1 抽象構文木
抽象構文木（Abstract Syntax Tree，以下 AST）とは，

2.3 コードクローン
コードクローン（以下，クローン）とはソースコード中に存在する同一，あるいは類似するコード片のことである．
クローンは既存ソースコードのコピーアンドペースによる再利用など，様々な理由で発生する [11], [12], [13], [14] ．
クローンは，その類似度に基づいて以下の 3 種類に分類さソースコードの構文情報を表現した木構造である．ASTれることが多い．

は順序木であり，子頂点の数に制限はない．例として，簡TYPE-1 空白，タブ，改行文字，コメント等のプログラ

単な Java ソースコードとそれに対応する AST を図 1 にムの振る舞いに影響を与えないソースコード中の要素示す．この AST はプログラムの構造に対応する 19 の頂点を除いて完全に同一のクローン．

を持つ．AST の頂点は，ID とソースコードの要素に対応

TYPE-2 変数名や関数名等のユーザ定義名の違いやリテするラベルとソースコード内の実際のトークンに対応する

ラルの違いのような字句単位での差異を含むクローン．

値を持つ．例えば，図 1b において「NumberLiteral:0」はTYPE-3 字句単位よりも大きな違いを含むクローン．

NumberLiteral がラベル，0 が値を表す。AST 上の頂点はこれまでにさまざまな検出手法が提案されているが，ク構文上の 1 つの要素を表し，枝で直接結ばれた子頂点はそローンの定義は手法ごとに異なる．そのため，異なる手法の詳細情報を表す．例えば，図 1b において，IfStatementを利用して同一ソースコードからクローンを検出した場の構文情報は，その子頂点により表されており，その内容

合，その検出結果は異なる．

は InfixExpression および ReturnStatement であることが分かる．

3. 編集スクリプト
編集スクリプトは，2 つの AST が与えられたときに一方

2.2 コピーアンドペースト
ソフトウェア開発において，開発者はソースコードをの AST をもう一方の AST に変更するために必要な操作の列である [5][7][8]．既存研究では，編集スクリプトは以下

頻繁にコピーアンドペーストする [9]．また，Ahmed らのの種類の操作から構成される．

研究により，開発者が行うコピーアンドペーストのうち，

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

63.52%においてコピー元のファイルとコピー先のファイル©2016 Information Processing Society of Japan

頂点の追加を表す．挿入する頂点の ID として t，頂点5

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)のラベルとして l，頂点の値として v ，挿入後に親頂点a	とする頂点の ID として tp ，何番目の子にするかを表b	

す数値として i を引数に持つ．
削除

c	

d	

e	
f	

d	

h	

a	

eを移動	

b	
c	

g	

e	
f	

b	
c	

g	

d	
e	

h	

delete(t)f	

頂点の削除を表す．削除する頂点の ID として t を引

a	

数に持つ．

b	

更新

a	

hを挿入	

h	

頂点の値の更新を表す．更新の対象となる頂点の ID

c	
g	

e	
f	

b	

cを削除	

d	

update(t, v)g	a	

として t，頂点に格納する新しい値として v を引数に

e	

h	

g	

gを挿入	

d	
f	

g	
g	

(a) AST の操作

持つ．
移動

insert(h,	
  d,	
  1,	
  …,	
  …)	
  
move(e,	
  d,	
  2)	
  
insert(g,	
  d,	
  3,	
  …,	
  …)	
  
delete(c)	

move(t, tp , i)

部分木の移動を表す．移動する部分木の根頂点の ID
として t，移動先の親頂点の ID として tp ，何番目の子(b) 対応する編集スクリプトにするかを表す数値として i を引数に持つ．

図 2: 編集スクリプトの例

図 2 に AST への編集の例を示す．図 2(a) では，AST において，頂点 h を頂点 d の 1 番目の子として挿入し，頂点

e を頂点 d の 2 番目の子として移動，頂点 g を頂点 d の 3が Chawathe らのアルゴリズム [7] であり，移動を含む編

番目の子として挿入，頂点 c を削除，の順で操作を行って集スクリプトを効率的に生成することができる．しかし，いる．このように，AST の編集は対象の AST に操作を適Chawathe らのアルゴリズムには制約があり，ソースファ

用することで行う．また，この場合の編集スクリプトは図イルを表現した細粒度な AST にそのままでは適用するこ2(b) である．ただし，ここでは挿入された頂点のラベルととができない．

値は省略している．

また，XML 文書を対象として編集スクリプトを生成す

編集スクリプトを構成する操作の数を編集スクリプトのるアルゴリズムが提案されている [16][17]．これらのアル長さと呼ぶ．図 2(b) の編集スクリプトの長さは 4 である．

ゴリズムは Chawathe らのアルゴリズムと異なり制約を持編集スクリプトが長いほど，多くの操作が含まれる．多くたない．しかし，これらのアルゴリズムは速度を最も重視の操作が行われる変更は人間にとって理解に要する労力がしており，人間にとって変更内容を理解しやすい編集スク

大きい [8]．よって，編集スクリプトの長さは人間が変更内リプトを生成することを重視していない．

容を理解するために要する労力を表す．そのため，編集ス

AST において編集スクリプトを生成するアルゴリズム

クリプトはその長さが短いほど，人間にとって理解しやすのうち，最も有名なアルゴリズムが ChangeDistiller[5] でい編集スクリプトであるといえる．

ある．ChangeDistiller は Chawathe らのアルゴリズムに影響を受けており，AST においてより効果的に動作するよう

3.1 既存の編集スクリプト生成手法に調整されている．しかし，ChangeDistiller は簡略化した編集スクリプトを生成するためにこれまでに多くの手法

AST を対象としており，1 つの文に多くの要素を持ちうるが研究されている [4][5][6][7] ．編集スクリプトを生成する言語において，ChangeDistiller は細粒度な編集スクリプト手法のうち，AST における頂点の追加，削除，更新を考慮を生成できない．

する手法が研究されている [15]．その中で最も短い時間で編集スクリプトを生成する手法は RTED[6] である．それ

3.2 GumTree

でも計算量は少なくなく，大きなソースファイルに対してFalleri らは，細粒度な AST において，実用的な時間の短い時間で編集スクリプトを生成することができない．ま範囲内で移動を考慮した短い編集スクリプトを生成する

た，これらの手法は，ソースコードの変更時に頻繁に現れ

GumTree を開発した [8]．GumTree の概要を図 3 に示す．

るコードの移動を考慮しておらず，移動元の頂点を全て削

GumTree は図 1(a) および図 4(a) のようなソースファイル

除し移動後の頂点を全て追加するという方法で変更内容をの組を入力として与えると，図 4(b) のような形式で編集表現することになる．その結果，編集スクリプトは長くな

スクリプトを生成し出力する．

り，理解しづらくなる．
頂点の移動を考慮して短い編集スクリプトを生成するこ

GumTree は入力として与えられた 2 つのソースファイ
ルに対して以下の処理を行い編集スクリプトを生成し出力とは NP 困難である．そのため，経験則を用いることによする．

り，移動を考慮した上で比較的短い編集スクリプトを生

STEP1（構文解析） 与えられた 2 つのソースファイル成する手法が研究されている．その内で最も有名なもの

それぞれについて構文解析を行い，AST を生成する．

©2016 Information Processing Society of Japan6

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

入力	STEP1	
構文解析	

2つの	
  
ソースファイル	

STEP3	
編集スクリプトの生成	STEP2	
マッピングの生成	STEP2-1	
トップダウンフェーズ	
STEP2-2	
ボトムアップフェーズ	
ASTの組	

出力	

Edit Script	

ASTのマッピング	

図 3: GumTree の概要

public	  class	
  Test{	  	
  private	
  String	
  foo(int	  i){	  	  	  	
  if(i	
  ==	
  0)	
  return	
  “Bar";	
  
	
  	
  	
  else	  if(i	  ==	
  -­‐1)	
  return	
  “Foo!”;	
  
	
  }	
  
}	

public	  class	
  Test{	  	
  public	  String	
  foo(int	  i){	  	  	  	
  if(i	
  ==	
  0)	
  return	
  "Foo!";	
  
	
  }	
  
}	

(a) 変更前のソースファイル(a) 変更後のソースファイル
insert(t1,	
  n,	
  2,	
  ReturnStatement,	
  ε)	
  insert(t2,	
  t1,	  1,	  StringLitteral,	  Bar)	
  insert(t3,	
  n,	
  3,	
  IfStatement,	
  ε)	
  insert(t4,	
  t3,	  1,	  InfixExpression,	  ==)	  insert(t5,	
  t4,	  1,	  SimpleName,	
  i)	
  insert(t6,	
  t4,	  2,	  PrefixExpression,	  -­‐)	
  insert(t7,	
  t6,	  1,	  NumberLiterral,	  1)	
  move(p,	
  t3,	  2)	  update(c,	  private)	

(b) 出力される編集スクリプト

図 4: GumTree が出力する編集スクリプトの例（図 1 のソースコードに対して変更を加えたもの）

public	  class	
  Test{	  	
  private	
  String	
  foo(int	  i){	  	  	  	
  if(i	
  ==	
  0)	
  return	
  “Bar";	
  
	
  	
  	
  else	  if(i	  ==	
  -­‐1)	
  return	
  “Foo!”;	
  
	
  }	
  
}	

更新	
 挿入	
 移動	
(b) 変更後のソースファイル

図 5: GumTree が出力した編集スクリプトに基づいた変更
内容の強調表示3.3 研究動機
ソースコードの実装において，コピーアンドペーストがSTEP2（マッピング） STEP1 で生成した 2 つの AST

頻繁に行われる [9]．しかしながら GumTree は，挿入，削について，STEP2-1 および STEP2-2 の処理を行うこ

除，更新，移動の 4 種類の操作で編集スクリプトを表現すとにより，2 つの AST における頂点や部分木のマッピるため，開発者のコピーアンドペーストという 1 つの操作

ングを生成する．

が複数の挿入の操作で表現されることになる．

STEP2-1（トップダウンフェーズ） 2 つの AST 間

図 6 のようにコピーアンドペーストを含む変更をにおいて TYPE-2 クローンの検出を行うことで，2

GumTree に与えた場合を例として説明する．この変更

つの AST に共通して存在する部分木を発見する．

では，新しいメソッド newFoo が追加されている．メソッ

STEP2-2（ボトムアップフェーズ） STEP2-1 におド newFoo はメソッド foo と TYPE-2 クローンの関係にいて発見した部分木のマッピングを基準として，こある．図 6(b) は変更後のソースコードの AST を表す．まこまででマッピングに含まれていない部分木のうちた，説明のため AST の各頂点の ID としてアルファベット

類似する部分木を発見する．

を付加している．この変更に対して，GumTree が生成し

STEP3（編集スクリプト生成） STEP1 で生成した 2 つた編集スクリプトは図 6(c) である．この編集スクリプトよの AST と，STEP2 で生成したマッピングを用いて編り，この変更において様々な 15 の新しい頂点が挿入され集スクリプトを生成する．編集スクリプトの生成にはたことがわかる．

Chawathe らのアルゴリズム [7] を用いる．

しかし，実際に挿入された頂点群（部分木）は，変更前

GumTree は生成した編集スクリプトに基づき変更内容の AST に存在していた AST の頂点群（部分木）と同様

をソースコード上に表すことができる．図 4(b) の編集スのものである．そのため，既存の頂点を利用することによ

クリプトに基づく変更内容の表示例を図 5 に示す．緑色でり，この編集スクリプトをより簡潔に表すことができる．

ハイライトした部分が挿入に対応する．この例ではソース

また，この例において，挿入された部分木は既存の部分木

コードの 2 箇所への挿入が行われている．黄色でハイライと同じ形である．よって，部分木の根頂点のみへの操作とトした部分が更新を表している．青色でハイライトした部

して表すことで（図 6(d)），編集スクリプトを大幅に短縮

分が移動を表しており，return 文が if 文の直後から if 文のできる．

else 節に移動している．

©2016 Information Processing Society of Japan7

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

入の繰り返しではなく 1 つのコピーアンドペーストとしpublic	  class	
  Test{	  	
  public	  String	
  foo(int	  i){	  	  	  	
  if(i	
  ==	
  0)	
  return	
  "Foo!";	
  
	
  }	
  
	
  public	  String	
  newFoo(int	  i){	  	  	  	
  if(i	
  ==	
  0)	
  return	
  "newFoo!";	
  
	
  }	
  
}	

て表すことで，人間にとってより理解しやすい編集スクリ
プトを生成できる．提案手法では編集スクリプトを構成する操作として，挿入，削除，更新，移動に加えてコピーア
ンドペーストを追加することで，人間にとってより理解しやすい編集スクリプトを生成する．図 6 の場合だと編集(a) 変更後のソースファイル

スクリプトを大幅に短くすることができる．この例におい
a	

b	

c	

f	

d	

Modiﬁer:	  	
  public	

て，提案手法が生成する編集スクリプトは GumTree が生

Compila(on	
  
Unit	

成する編集スクリプトよりも短いだけでなく，コピーアン

Type	
  
Declara(on	

ドペーストや更新といった具体的な変更内容をイメージしe	

SimpleName:	
  
Test	

g	
Modiﬁer:	  	
  public	h	SimpleType	k	

やすい．そのため，提案手法が生成する編集スクリプトはMethod	  Declara(on	l	SimpleName:	  String	i	
SimpleName:	  	
  foo	

Primi(veType:	
  
int	

j	

SingleVariable	
  Declara(on	m	SimpleName:	
  i	

Block	

理解しやすいといえる．
n	

SimpleName:	
  i	

本研究では GumTree を拡張することで提案手法を設計

IfStatement	o	
 InﬁxExpression:	
  

p	

r	

s	

==	

q	

NumberLiteral:	
  0	

している [8]．提案手法の概要を図 7 に示す．提案手法は 2

Return	  Statement	

つのソースファイルを入力とし，GumTree と同様に 3 つStringLiteral:	  “Foo!”	

の STEP を経て編集スクリプトを生成する．提案手法におe’	

いて，編集スクリプトを構成する操作は挿入，削除，更新，Method	  Declara(on	

f’	

g’	
Modiﬁer:	  	
  public	SimpleType	

I’	

h’	
 SimpleName:	
  l’	
 Primi(veType:	  String	int	

j’	

SingleVariable	
  Declara(on	

newFoo	k’	
 SimpleName:	
  Block	m’	
 SimpleName:	
  

n’	

o’	
 InﬁxExpression:	
  

p’	

r’	
 NumberLiteral:	  s’	

IfStatement	

i	

==	

q’	
 SimpleName:	
  i	

GumTree が生成する編集スクリプトよりも人間にとって

0	

移動，コピーアンドペーストの 5 種類である．このうち，挿入，削除，更新，および移動の定義は 3 章で述べた従来の編集スクリプトの定義と同じである．コピーアンドペー
ストの定義を以下に示す．

Return	  Statement	

StringLiteral:	
  “newFoo!”	

(b) 変更後の AST

コピーアンドペースト C&P (t, tp , i)
部分木のコピーアンドペーストを表す．コピーアンド
ペーストする部分木の根頂点の ID として t，コピーア
ンドペースト先の親頂点の ID として tp ，何番目の子

insert(e’,	
  b,	
  	
  4,	
  MethodDeclaration,	  ε)	
  insert(f’,	
  e’,	  1,	  Modifier,	
  public)	
  insert(g’,	
  e’,	  2,	  SimpleType,	  String)	
  insert(k’,	
  g’,	  1,	  SimpleName,	
  String)	
  insert(h’,	  e’,	  3,	  SimpleName,	
  newFoo)	
  insert(i’,	
  e’,	  4,	  SingleVariableDeclaration,	  ε)	
  insert(l’,	
  i’,	  1,	  PrimitiveType,	
  int)	
  insert(m’,	
  i’,	  2,	  SimpleName,	
  i)	
  insert(j’,	
  e’,	  5,	  Block,	
  ε)	
  insert(n’,	
  j’,	  1,	  IfStatement,	
  ε)	
  insert(o’,	
  n’,	  1,	  InfixExpression,	  ==)	  insert(q’,	
  o’,	  1,	  SimpleName,	  ε)	
  insert(r’,	
  o’,	  2,	  NumberLiteral,	  0)	
  insert(p’,	
  n’,	  2,	  ReturnStatement,	
  ε)	
  insert(s’,	
  p’,	  1,	  StringLiteral,	
  newFoo!)	
  (c) Gum Tree が出力する編集スクリプトにするかを表す数値として i を引数に持つ．

4.2 手順提案手法は GumTree のアルゴリズムを拡張している．
図 7 では，提案手法において拡張あるいは追加した STEPを赤で示している．拡張あるいは追加した STEP の概要を以下に示す．

STEP2-1（トップダウンフェーズ） 2 つの AST 間において TYPE-2 のクローン検出を行うことで，2 つのAST に共通して存在する部分木を発見する．さらに，
平行してコピーアンドペースト操作の対象となりうる

c&p(e,	
  b,	
  4)	
  
update(h’,	  newFoo)	
  update(s’,	
  “newFoo!”)	

部分木を抽出する．

STEP2-3（C&P 識別フェーズ） STEP2-1 において発(d) 提案手法が出力する編集スクリプト

見した，コピーアンドペーストによって作成された部

図 6: コピーアンドペーストが行われた変更の例（図 1 の分木の候補である，2 つの AST に共通して存在する部

ソースコードに対して変更を加えたもの）

分木の組のうち，STEP2-1 と STEP2-2 においてマッピングされていないものを発見し，コピーアンドペー
ストによって作成された部分木とする．

4. 提案手法
4.1 概要
3.3 節で説明したように，追加された部分木を頂点の挿©2016 Information Processing Society of JapanSTEP3（編集スクリプト生成） STEP1 で生成した 2 つの AST と，STEP2 で生成したマッピングを用いて編
集スクリプトを生成する．STEP2-3 において識別した部分木をコピーアンドペーストによって作成するも8ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

入力	STEP1	
構文解析	

2つの	
  
ソースファイル	

STEP3	
編集スクリプトの生成	STEP2	
マッピングの生成	STEP2-1	
トップダウンフェーズ	
STEP2-2	
ボトムアップフェーズ	
STEP2-3	
ASTの組	
C&P認識フェーズ	出力	

Edit Script	

ASTのマッピング	

図 7: 提案手法の概要のとして処理する．
以降，上記の各 STEP について詳細に説明する．

ト操作の候補から除外する．

C&P 操作の判定において制約を設けた．提案手法では，TYPE-2 のクローン検出により共通する部分木を発見する

4.3 STEP2-1（トップダウンフェーズ）

ため，識別子名やリテラルなどは正規化される．そのため，

STEP2-1 では，GumTree において行われる処理と並行

文法上の理由により，偶然同じ形になった部分木もコピー

してコピーアンドペースト操作の対象となりうる部分木のアンドペーストとして識別される可能性がある．例えば，候補を抽出する．2 つの AST を比較することにより，部分

変数宣言において，宣言する変数の変数名と，代入する値

木のマッピングを行う．トップダウンフェーズは以下の手の双方が異なっていても，部分木は同じ形となるため，コ順で実行される．

ピーアンドペーストと識別される可能性がある．このよう( 1 ) TYPE-1 および TYPE-2 クローンの関係にある部分

な誤検出を防ぐため，提案手法では，部分木の形が同じで木を発見し記録する．

( 2 ) TYPE-1 クローンの関係にある部分木のうち，1 対 1

あっても，その部分木を構成する頂点が持つ全ての値が異なる場合はコピーアンドペーストとして識別しない．

の関係にある（各 AST に 1 つずつのみ存在している）
組をマッピングに追加する．

4.5 STEP3（編集スクリプトの生成）( 3 ) TYPE-1 クローンの関係にある部分木のうち，1 対多

編集スクリプトの生成において，挿入，削除，移動，更あるいは多対多の関係にある部分木について，最も類

新の検出は GumTree と同様に Chawathe らのアルゴリズ

似度が高い組のみをマッピングに追加する．ここで用ムを用いる [7]．ただし，提案手法では，Chawathe らのアいる類似度は GumTree において定義された類似度でルゴリズムを拡張して，検出する操作としてコピーアンドある．

ペーストを加えている．この STEP では各 AST を一度ず

( 4 ) ここまででマッピングされていない TYPE-1 クローンつ探索することにより編集スクリプトを生成している．

の関係にある部分木の組と，TYPE-2 クローンの関係( 1 ) 変更後の AST を幅優先探索することにより挿入，移にある部分木の組をコピーアンドペースト操作の候補

動，更新に加えてコピーアンドペーストを検出する．

として記録する．

( 2 ) 変更前の AST を後行順に探索することにより削除を検出する．

4.4 STEP2-3（C&P 識別フェーズ）

幅優先探索の際に，C&P 識別フェーズにおいてコピーア

STEP2-1 では，C&P 操作とみなす変更を決定する．変

ンドペーストとしてマッピングされた頂点を発見すると，

更後の AST を先行順に探索し，下記の条件を満たす頂点

その頂点はコピーアンドペーストされた頂点であると判断を探す．

され，編集スクリプトにコピーアンドペーストとして追加• ここまでの STEP においてマッピングに追加されていない．

• コピーアンドペースト操作の候補としてトップダウン
フェーズで記録されている．
条件を満たす頂点を発見すると，変更前の AST において

される．

5. 実験
ここでは，提案手法と GumTree の比較を行った実験について述べる．

対応する頂点（トップダウンフェーズでクローンとして検出された部分木）とともに，コピーアンドペーストされた

5.1 準備頂点としてマッピングに追加する．そして，コピーアンド

3.1 章で述べたように，編集スクリプトを生成する手法

ペーストされたとしてマッピングに追加された頂点を根ととして GumTree 以外の手法も存在する．しかし，Falleri

する部分木に含まれる全ての子頂点をコピーアンドペース

らの研究において，GumTree がそれらの手法より，変更©2016 Information Processing Society of Japan9

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

内容を人間にとって理解しやすく表現できることが示されている [8]．そのため，提案手法と GumTree を比較することで，提案手法の有効性を評価する．
提案手法と GumTree において，下記のしきい値を用

´
´

´
´
´

´

´

´

いた．

´

´

´
´

´
´

´

´

´

´

´

´
´

• 不要なマッピングを減らすため，トップダウンフェー

´
´

´
´

´

´

´
´

´

´

´
´

´

´

´

´

´
´

´
´

´

´

´

´

´
´

´
´

´
´

´
´

´

´

´

´

´

´

´
´

´

´

ズにおいてマッピングする部分木の高さの最小値を 2

´

´

´

´

´
´

´

´
´

´

´

´
´
´

´

´

´

´

´

´

´
´

´

´

´
´

´

´
´

´

´

´

´

´
´

とする．

´

´

´
´
´

´
´

´

´

´

´

´
´

• ボトムアップフェーズにおいて部分木をマッピングする際に用いる類似度の最小値を 0.5 とする．

• 計算時間を短縮するため，ボトムアップフェーズにおいてマッピングする部分木の頂点数の最大値を 100 と

図 8: 編集スクリプトの長さが異なる変更における長さの比較する．
これらのしきい値は Falleri らの実験において設定された値である [8]．

´

本実験では，実験対象として 14 のプロジェクトで構成
´
´

´
´
´

´

されるデータセットである CVS-Vintage dataset を用い

´
´

´

´

´

た [18]．CVS-Vintage dataset には 43,250 のソースファイ

´
´
´
´

´
´

´
´
´

´
´
´

´

´

´

ル，ソースファイルへの変更が行われた 352,182 のリビ

´
´

´

´

´
´
´

´

´
´
´
´

´

´

´
´

´
´
´

´
´
´
´
´
´
´

´
´
´

´

´

´

ジョンが含まれている．

´
´

´

´
´
´
´

´

´

´

´
´
´
´

´

´
´

´
´
´
´
´
´
´
´
´

´
´

´

´
´
´
´
´
´

´
´

´
´
´
´
´
´
´

´
´

´
´

´
´

´

´

´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´

´
´
´
´
´

´
´
´

´
´
´
´
´
´
´

´

´
´

´
´

´
´
´

´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´

´
´

´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´

´
´

´
´
´
´

´

´

´

´

´

´
´
´
´

´

´

´
´
´

´

´
´
´

´

´
´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´

´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´

´
´
´
´
´
´

´
´
´
´
´
´

´
´
´
´
´
´
´
´
´
´
´
´

´

´
´
´
´

´
´

´
´
´

´
´
´
´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´
´
´
´
´
´
´
´
´
´
´
´
´
´

´
´
´
´

5.2 手順
本実験では，2 つのツールを用いて編集スクリプトを生成し，それらを比較することで評価を行う．本実験では，1 つ
図 9: 全ての変更に対する実行時間の比較のコミット前後の各ソースファイルの対を 1 つの変更と呼ぶ．つまり，あるコミットにおいて改版されたソースファ
イルの数がそのコミットにおける変更の数となる．2 つのする．

ツールへの入力として与える変更は CVS-Vintage datasetに含まれる 14 のプロジェクトのリポジトリから取得する．

5.3 評価基準

この実験では各プロジェクトから，1,000 の変更を取得す

本実験では，各ツールが生成する編集スクリプトの長さ

る．リポジトリに含まれる全変更数が 1,000 に満たない場と各ツールが編集スクリプトを生成するために要する実行

合は，全変更を使用する．実験に用いる変更の取得は下記

時間を評価基準とした．編集スクリプトが短いほど，人間の手順で行う．

が変更の内容を理解するための負担が少なくなる．そのた( 1 ) リポジトリから，ソースファイルが変更されたリビ

め，より短い編集スクリプトを生成するツールほど優れてジョンを特定し，そのリビジョンにおいて変更された

いる．

ソースファイルを取得する．

( 2 ) 取得したソースファイルのそれぞれについて，直前の5.4 結果リビジョンから対応するソースファイルを取得する．

13,699 の変更について 2 つのツールの編集スクリプトの長( 3 ) 対応する変更前のソースファイルと変更後のソースさを比較し，18%の変更において提案手法の方が GumTree

ファイルを 1 つの変更として保存する．

よりも短い編集スクリプトを生成していることがわかっ( 4 ) 保存した変更のうち，提案手法に入力として与えた場

た．82%の変更については，提案手法と GumTree の編集

合に長さ 1 以上の編集スクリプトを生成する変更のみ

スクリプトの長さは同じであった．提案手法が GumTreeを残す．フォーマットの変換やコメントの追加のみかよりも長い編集スクリプトを生成している変更はまったくらなる変更等が取り除かれる．

なかった．

( 5 ) 残った変更からランダムに 1,000 選択する．

表 1 は，提案手法の方が短い編集スクリプトを生成した

以上の手順から，13,699 の変更を取得した．こうして取得

変更に対して，2 つのツールの変更の長さを表している．

した変更を入力とし，提案手法と GumTree へ入力としてまた，図 8 では，各変更において提案手法を用いることに与え，編集スクリプトの長さとツールの実行時間を取得

より編集スクリプトがどの程度変化するかを箱ひげ図を用©2016 Information Processing Society of Japan10

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

表 1: ツールによって編集スクリプトの長さが異なる場合における編集スクリプトの長さ
ソフトウェア

最大値

第 3 四分位数

中央値

第 1 四分位数

最小値

GumTree

提案手法

GumTree

提案手法

GumTree

提案手法

GumTree

提案手法

GumTree

提案手法

argouml

3,049

2,708

231

198

69

49

30

22

4

2

carol

1,586

1,581

230.5

214

116

107

53.75

32

7

3

columba

892

872

128

100

47

39

18

11

5

1

dnsjava

1,632

1,544

192

166.5

75

71

33

18

4

2

jboss

2,876

2,457

223.75

208.5

75.5

61.5

32

21.25

5

2

jedit

2,858

2,853

202

178

79

67

29

24.5

4

2

jhotdraw

1,691

1,686

172.75

144

71.5

64

28.75

18.75

4

2

junit

751

728

141.75

133

74.5

63.5

32.75

25.75

7

2

log4j

3,029

2,827

195

165

75

60

33

24

4

2

jdtcore13,26912,628

194.5

168.5

84

65

36

22.5

4

2

workbench

3,651

3,351

195

170

72

55

22

12

4

2

scarab

3,016

2,928

189.5

175.5

83

70

30.5

16.5

5

2

struts

1,486

1,313

159.25129.25

59

43

33

16

5

1

tomcat

2,152

2,064

162

150.5

54

43

24.5

17.5

4

2

いて表している．縦軸は GumTree が生成する編集スクリた変更を示す．図上部のソースコードが変更前のソース

プトの長さを 1.0 としたときの提案手法が生成する編集ス

コード，図下部が変更後のソースコードである．この変更

クリプトの長さを表す．横軸が対応するソフトウェアを表

では，setReception というメソッドが追加されている．

す．全てのソフトウェアにおいて，中央値がおよそ 0.8 か

変更前にあったメソッドを再利用し，図中の点線で囲ま

ら 0.9 の間にある．つまり，半数の変更において，提案手れた setReception というメソッドを追加している．setRe-

法を使うことにより 10%から 20%程度は編集スクリプトがception の内部では，変数名やメソッド呼び出し文で呼び短くなっていることがわかる．具体的な数値を挙げると，

出すメソッドの名前は異なるが非常に似た処理を行って58.5%の変更において編集スクリプトが 10%以上短縮され

いる．

ていた．

この変更について，提案手法と GumTree の双方による変次に実行時間について述べる．実行時間は編集スクリプ

更内容の表現は図 10 のようになる．図 10(b) は GumTree

トの長さが異なる変更のみではなく，全変更について調査による表現である．変更後のソースコードを見ることによを行った．図 9 は，各変更において提案手法を用いること

り，緑色のコード片が追加されたことがわかる．図 10(c)により実行時間がどの程度変化するかを箱ひげ図を用いては提案手法による表現である．変更前のソースコードにお表している．

いて，紫色でハイライトされたコード片はコピー元と判定

縦軸は，GumTree を用いた場合の実行時間を 1 としたされたコード片である．また，変更後のソースコードを見ときの提案手法の実行時間を表す．横軸は対応するソフト

ることによりこのコード片が別の箇所にペーストされたウェアを表す．GumTree と比較して提案手法は実行時間がと判定されていることがわかる．黄色でハイライトされた

長くなっている．全ての変更における提案手法と GumTree

コード片はコピー元とコピー先で異なる部分を表していの実行時間を，ウィルコクソンの符号順位検定を用いてる．これらは，ペースト後に更新されたと判定されたこと

有意水準α=0.05 で検定したところ，統計的に優位な差がを意味する．

あった．しかしながら，提案手法が編集スクリプトの生成

GumTree による表現では，変更後のソースコードにおに要する時間はそれほど長くはない．96%の変更においていて，setReception という新しいメソッドが追加されたこ

提案手法は GumTree の 1.5 倍以下の実行時間で編集スクとがわかる．しかし，追加されたメソッドは既存のメソッリプトを生成していた．また，75%の変更において提案手

ド setReceiver と似ていること，およびそのメソッドをコ

法は 1 秒以内に編集スクリプトを生成し，96%の変更におピーアンドペーストにより再利用した可能性があることはいて 2 秒以内に編集スクリプトを生成していた．

わからない．
提案手法による表現では，追加されたメソッドは既存メ

5.5 考察ソッドと似ており，コピーアンドペーストおよび軽微な修5.5.1 提案手法が編集スクリプトを大幅に短縮できる場合

正により追加された可能性があることを示している．もし実験において，編集スクリプトを大幅に短縮できた変更

この編集スクリプトの利用者がコピー元のメソッドについの具体例を説明する．図 10 に ArgoUML において行われて知識がある場合は，追加されたメソッドを理解する助け©2016 Information Processing Society of Japan11

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

public	  abstract	
  class	  	
  AbstractCommonBehaviorHelperDecorator	
  implements	
  CommonBehaviorHelper	
  {	
  
…	
  
	
  public	
  void	  setReceiver	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	  receiver)	
  {	
  
	
  	
  	
  impl.setReceiver(handle,	
  receiver);	
  
	
  }	
  
…	
  
	
  public	
  void	  setRecurrence	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	
  expr)	
  {	
  
	
  	
  	
  impl.setRecurrence(handle,	
  expr);	
  
	
  }	
  
…	
  
}	

public	  abstract	
  class	  	
  AbstractCommonBehaviorHelperDecorator	
  implements	
  CommonBehaviorHelper	
  {	
  
…	
  
	
  public	
  void	  setReceiver	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	  receiver)	
  {	
  
	
  	
  	
  impl.setReceiver(handle,	
  receiver);	
  
	
  }	
  
…	
  
	
  public	
  void	  setRecurrence	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	
  expr)	
  {	
  
	
  	
  	
  impl.setRecurrence(handle,	
  expr);	
  
	
  }	
  
…	
  
}	

public	  abstract	
  class	  	
  AbstractCommonBehaviorHelperDecorator	
  implements	
  CommonBehaviorHelper	
  {	
  
…	
  
	
  public	
  void	  setReceiver	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	  receiver)	
  {	
  
	
  	
  	
  impl.setReceiver(handle,	
  receiver);	
  
	
  }	
  
…	
  
	
  public	
  void	  setRecurrence	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	
  expr)	
  {	
  
	
  	
  	
  impl.setRecurrence(handle,	
  expr);	
  
	
  }	
  
…	
  
}	

public	  abstract	
  class	  	
  AbstractCommonBehaviorHelperDecorator	
  implements	
  CommonBehaviorHelper	
  {	
  
…	
  
	
  public	
  void	  setReceiver	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	  receiver)	
  {	
  
	
  	
  	
  impl.setReceiver(handle,	
  receiver);	
  
	
  }	
  
…	
  
	
  public	
  void	  setReception	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Collection	
  c)	
  {	
  
	
  	
  	
  impl.setReception(handle,	
  c);	
  
	
  }	
  
…	
  
	
  public	
  void	  setRecurrence	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	
  expr)	
  {	
  
	
  	
  	
  impl.setRecurrence(handle,	
  expr);	
  
	
  }	
  
…	
  
}	

public	  abstract	
  class	  	
  AbstractCommonBehaviorHelperDecorator	
  implements	
  CommonBehaviorHelper	
  {	
  
…	
  
	
  public	
  void	  setReceiver	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	  receiver)	
  {	
  
	
  	
  	
  impl.setReceiver(handle,	
  receiver);	
  
	
  }	
  
…	
  
	
  public	
  void	  setReception	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Collection	
  c)	
  {	
  
	
  	
  	
  impl.setReception(handle,	
  c);	
  
	
  }	
  
…	
  
	
  public	
  void	  setRecurrence	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	
  expr)	
  {	
  
	
  	
  	
  impl.setRecurrence(handle,	
  expr);	
  
	
  }	
  
…	
  
}	

public	  abstract	
  class	  	
  AbstractCommonBehaviorHelperDecorator	
  implements	
  CommonBehaviorHelper	
  {	
  
…	
  
	
  public	
  void	  setReceiver	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	  receiver)	
  {	
  
	
  	
  	
  impl.setReceiver(handle,	
  receiver);	
  
	
  }	
  
…	
  
	
  public	
  void	  setReception	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Collection	
  c)	
  {	
  
	
  	
  	
  impl.setReception(handle,	
  c);	
  
	
  }	
  
…	
  
	
  public	
  void	  setRecurrence	
  
	
  	
  	
  	
  	
  (Object	  handle,	
  Object	
  expr)	
  {	
  
	
  	
  	
  impl.setRecurrence(handle,	
  expr);	
  
	
  }	
  
…	
  
}	

(a) メソッドが追加された変更(b) GumTree の出力(c) 提案手法の出力

図 10: 提案手法によって編集スクリプトを短縮できた例になることも期待できる．
この例における編集スクリプトの長さは，GumTree は

コピーアンドペースト操作の対象とした部分木を TYPE-1
および TYPE-2 に限定したことだと著者らは考えている．

20，提案手法は 5 である．提案手法を用いることにより編もし TYPE-3 のクローンもコピーアンドペーストの対象に集スクリプトは 75%短縮されている．

した場合は，コピーアンドペースト後の操作の数が多くな

5.5.2 編集スクリプトの長さが等しい場合

るため，提案手法の編集スクリプトはより長くなってしま

実験では，82%の変更において，提案手法と GumTree

うと考えられる．しかしながら，提案手法の編集スクリプの変更の長さは同じであった．これらの変更において，提ト中により多くのコピーアンドペーストが含まれるように案手法の生成した編集スクリプトにコピーアンドペーストなるため，人間がより理解しやすい編集スクリプトになるの操作は含まれていなかった．つまり，コピーアンドペー

可能性もある．

ストの操作とみなせる AST の変更が存在した場合には編集スクリプトは必ず短くなるという結果であった．

5.6 実験の妥当性について

理論上はコピーアンドペースト操作を導入することで編

実験では Java にて記述されたソースファイルのみを使集スクリプトが長くなってしまうことはありうる．コピー用した．提案手法や GumTree のアルゴリズムは Java の特

アンドペーストの後に，コピーアンドペーストされた部分

徴とは無関係だが，他の言語を対象とした場合において異木の全ての頂点において更新が行われた場合，提案手法

なる結果が得られる可能性がある．

による編集スクリプトは 1 だけ長くなるはずである．ま

実験において提案手法と GumTree の双方において，した，コピーアンドペーストの後に，コピーアンドペースト

きい値は Falleri らの研究において用いられた値と同じ値

された部分木のうち 1 つを除く全ての頂点において更新を使用している．しきい値が異なれば，各ツールは異なるが行われた場合，提案手法による編集スクリプトの長さは振る舞いをする．実験結果について，しきい値の影響を評

GumTree と等しくなるはずである．しかし，提案手法の価するにはより多くの実験が必要とされる。

コピーアンドペーストを含む編集スクリプトが GumTree

実験において，Falleri らの実験と同様に，実験対象としのコピーアンドペーストを含まない変更以上の長さであって CVS-Vintage dataset を使用した．他のデータセットをた場合がまったくなかった．

実験対象に使用した場合に異なる結果が得られる可能性がこの結果に支配的な影響を与えたのは，提案手法において©2016 Information Processing Society of Japan

ある．

12

ソフトウェアエンジニアリングシンポジウム 2016
IPSJ/SIGSE Software Engineering Symposium (SES2016)

6. おわりに[9]

本論文では，ソースファイルの変更内容を人間が理解しやすく表現するために，コピーアンドペーストを考慮することにより既存手法の GumTree を改良した．また，提案手法の有効性を評価するために評価実験を行った．実[10]

験では，提案手法と GumTree を比較することで提案手法を評価した．実験において，CVS-Vintage dataset を用いて 14 のソフトウェアの開発履歴から 13,699 の変更を実験[11]

対象として取得した．取得した変更に対して提案手法とGumTree が生成する編集スクリプトの長さと，編集スクリ[12]

プトの生成に要する実行時間を比較した．その結果，提案
手法は GumTree より短い編集スクリプトを生成できることを確認した．また，ほとんどの変更に対して提案手法は[13]

数秒以内で編集スクリプトを生成できることを確認した．
今後の課題は以下の通りである．

• より多くのソフトウェアに対して実験を行う．

[14]• 被験者実験を行い，コピーアンドペーストを考慮した表現により，変更内容がどの程度理解しやすくなった[15]か調査する．

• TYPE-3 クローンをコピーアンドペーストとして識別できるよう手法を改良する．

[16]

謝辞
[17]

本研究は，日本学術振興会科学研究費補助金基盤研究(S)(課題番号：25220003) の助成を得て行われた．
参考文献
[1]
[2]

[3]

[4]

[5]

[6]

[7]

[8]

E. W. Myers. An o(nd) diﬀerence algorithm and its variations. Algorithmica, Vol. 1, pp. 251–266, 1986.
W. Miller and E. W. Myers. A file comparison program.
Software: Practice and Experience, Vol. 15, No. 11, pp.
1025–1040, 1985.
M. Asaduzzaman, C. K. Roy, K. A. Schneider, and M. D.
Penta. Lhdiﬀ: A language-independent hybrid approachfor tracking source code lines. In ICSM, pp. 230–239.
IEEE Computer Society, 2013.
M. Hashimoto and A. Mori. Diﬀ/ts: A tool for finegrained structural change analysis. In WCRE, pp. 279–
288, 2008.
B. Fluri, M. Wuersch, M. PInzger, and H. Gall. Change
distilling: Tree diﬀerencing for fine-grained source codechange extraction. IEEE Trans. Softw. Eng., Vol. 33,
No. 11, pp. 725–743, November 2007.
M. Pawlik and N. Augsten. Rted: A robust algorithm
for the tree edit distance. Proc. VLDB Endow., Vol. 5,
No. 4, pp. 334–345, December 2011.
S. Chawathe, A. Rajaraman, H. Garcia-Molina, and
J. Widom. Change detection in hierarchically structured
information. SIGMOD Rec., Vol. 25, No. 2, pp. 493–504,
June 1996.
J. Falleri, F. Morandat, X. Blanc, M. Martinez, and
M. Monperrus. Fine-grained and accurate source code
diﬀerencing. In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engi-©2016 Information Processing Society of Japan[18]

neering, ASE ’14, pp. 313–324, 2014.
M. Kim, L. Bergman, T. Lau, and D. Notkin. An Ethnographic Study of Copy and Paste Programming Practices
in OOPL. In Proceedings of the 2004 International Symposium on Empirical Software Engineering, pp. 83–92,
2004.
T. M. Ahmed, W. Shang, and A. E. Hassan. An empirical study of the copy and paste behavior during development. In Proceedings of the 12th Working Conferenceon Mining Software Repositories, MSR ’15, pp. 99–110,2015.
肥後芳樹, 楠本真二, 井上克郎. コードクローン検出とその関連技術. 電子情報通信学会論文誌, Vol. J91-D, No. 6,
pp. 1465–1481, 2008.
堀田圭佑, 肥後芳樹, 楠本真二. 生成防止，分析効率化，不具合検出を中心としたコードクローン管理支援技術に関する研究動向. コンピュータソフトウェア, Vol. 31, No. 1,
pp. 14–29, 2014.
神谷年洋, 肥後芳樹, 吉田則裕. コードクローン検出技術の展開. コンピュータソフトウェア, Vol. 28, No. 3, pp.
28–42, 8 2011.
Dhavleesh Rattan, Rajesh Bhatia, and Maninder Singh.
Software Clone Detection: A Systematic Review. Information and Software Technology, Vol. 55, No. 7, pp.
1165–1199, 2013.
P. Bille. A survey on tree edit distance and related problems. Theor. Comput. Sci., Vol. 337, No. 1-3, pp. 217–
239, June 2005.
G. Cobena, S. Abiteboul, and A. Marian. Detectingchanges in xml documents. In Inproceedings of the 18th
International Conference on Data Engineering, pp. 41–
52, 2002.
R. Al-Ekram, A. Adma, and O. Baysal. diﬀx: An algorithm to detect changes in multi-version xml documents.
In Proceedings of the 2005 Conference of the Centre forAdvanced Studies on Collaborative Research, pp. 1–11,
2005.
M. Monperrus and M. Martinez. Cvs-vintage: A datasetof 14 cvs repositories of java software. Technical Reporthal-00769121, INRIA, 2012.

13