情報処理学会研究報告
IPSJ SIG Technical Report

ソースファイルの派生関係の自動抽出
神田 哲也1,a)

石尾 隆1,b)

井上 克郎1,c)

概要：ソフトウェアの進化において，1 つのソースコードから複数の派生ソースコードが作られることがある．それら派生ソースコードの中から最新のバグ修正が施されたものを選択したい場合や，開発が分岐した複数のソフトウェアから機能を集約したい場合には，ソースコードの派生関係を知ることが重要になる．本研究では，類似するファイルの差分に注目することで，ソースコード集合のバージョン履歴がない状態から，ソースファイルの派生関係を自動抽出する手法を提案する．具体的には，差分の行数をもとに最小全域木を構築することで，開発者が比較を行う際に読解する差分の量を最小化する．例としてオープ
ンソースのソースコードに手法を適用し，結果をもとに今後の課題について考察した．
キーワード：ソフトウェア進化，差分

Towards Automatic Extraction of
the Derivative Relationships of Source Files
Kanda Tetsuya1,a)Ishio Takashi1,b)

Inoue Katsuro1,c)Abstract: In software evolution, branching of development occurs in some cases. If a developer wants toselect a source ﬁle to which the latest bug ﬁxes was performed or to collect functions out of branched software,
it is important to know the derivative relationships of source ﬁles. In this paper, we focus on the diﬀerencesof similar ﬁles and propose an approach for automatic extraction of the derivative relationships of source ﬁles.
We construct a minimum spanning tree based on the number of lines of diﬀerence. The tree minimizes theamount of diﬀerence developers read. We performed a case study with open source software and discussed
for the future work.
Keywords: Software evolution, diﬀerence

1. はじめにソフトウェアは，機能を追加，削除あるいは修正されることにより進化する．ソフトウェアの進化は必ずしも一本

トウェアを改良し，進化させていくケースも考えられる．
開発チームが別個になる場合，ソースコードの管理も別個に行われるため，元のソフトウェアとの関連性が明らかでなくなる．

道ではなく，バージョン管理システムを用いて機能追加・

ソフトウェアの派生関係を知ることは，ソフトウェアのテスト用のブランチをリリース用のブランチと別に作り，再利用において重要となる．新たな派生ソフトウェアを並行して開発を行うことも多い．ときには元のソフトウェ

作るにあたって，できるだけ新しい，バグ修正の行われたアから派生して，以後別系統の進化をたどるソフトウェア

ソースファイルを選択して再利用したい場合 [1] や，開発も生まれる．この場合には，開発元とは別のチームがソフが分岐した複数のソフトウェアの機能を 1 つのプロダクト

1
a)
b)
c)

に集約したい場合に，複数の既存ソフトウェアの派生関係
大阪大学
Osaka University, Suita, Osaka, 565–0871, Japant-kanda@ist.osaka-u.ac.jp
ishio@ist.osaka-u.ac.jp
inoue@ist.osaka-u.ac.jp

c 2012 Information Processing Society of Japan

を調査する必要がある．
バージョン違いや分岐して進化したソフトウェア間のソースコードを比較すると，元が同一であるため非常に類1

情報処理学会研究報告
IPSJ SIG Technical Report

似度の高いものとなる．ソースコードの類似性に関する研

ศᒱ

ᶵ⬟㏣ຍ

ಟṇ

究として，コードクローン検出技術が挙げられる．コード

㛤Ⓨ䝤䝷䞁䝏㻔ᶵ⬟㻭㻕

クローンとは，ソースコード中に存在する互いに一致・類⤫ྜ䝸䝸䞊䝇䝤䝷䞁䝏

似したコード片のことであり，大規模なソフトウェア集合⤫ྜにおいてもソフトウェア間でのコードクローンが多く存在

㛤Ⓨ䝤䝷䞁䝏㻔ᶵ⬟㻮㻕

することが知られている．コードクローン検出技術では，
ソースコード中の類似する部分に着目しているが，元が同

ศᒱ

ᶵ⬟㏣ຍ

ಟṇ

一のソフトウェアのソースコードはその大部分がクローン

᫬⣔ิ㡰となってしまうため，そこからソースコード間の関係性を理解することは難しい．
本研究では，類似するファイルの差分に注目する．開発

図 1

開発ブランチを用いたソフトウェアの進化

Fig. 1 Software evolution with development branches

者が類似ファイルの比較をすべての組み合わせで行わずに済むよう，差分の量が最小になる比較順序を求めることで，ソースコード集合のバージョン履歴がない状態からソース
ファイルの派生関係を自動抽出する．

プロジェクトの分岐
進化の過程において，元のソフトウェアに変更を加えたものが，以後別系統のソフトウェアとして進化していく

第 2 章では，本研究の背景となる事項について述べる．

ことがある．ソフトウェアの開発プロジェクト自体が，別

その後，第 3 章で提案する解析手法について説明し．第 4の開発チームに移動し，プロジェクトが分岐することも章でいくつかのソースコードに対し提案手法を簡単に適用考えられる．オープンソースでの実例として有名なもの

した結果について述べる．第 5 章で関連研究を．第 6 章

は，FreeBSD や NetBSD，OpenBSD などの BSD 系のオで，まとめと今後の課題を記述する．

ペレーティングシステムがある．

2. 背景
2.1 ソフトウェアの派生

プロジェクト自体が分岐した場合，ソフトウェアリポジ
トリも別個のものとなる．しかし，これらの分岐したプロジェクトは以後無関係というわけでもなく，あるソフト

本稿では，あるソフトウェアのバージョン違いや，分岐ウェアの派生ソフトウェアがバージョンアップに際し，元によって派生したソフトウェアをまとめて「派生ソフトのソフトウェアの機能追加やバグ修正を取り込む場合もウェア」と呼ぶ．ソフトウェアの分岐の要因として，開発ある．このようなケースにおいて開発の分岐が発生した場

ブランチの作成とプロジェクト自体の分岐が挙げられる．

合，元のソフトウェアと派生ソフトウェアとがどのようにソフトウェアの進化を明らかにする試みは多く行われて関連しているのかが不明瞭になる．

いる．Prinzger らはメトリクスと可視化を組み合わせてソフトウェアの進化を示した [2]．Jaafar は，同時期に修正されるクラスに注目してソフトウェアのバージョン間の関係を抽出することを提案した [3]．

2.2 コードの類似関係
派生関係にあるソフトウェア間では元が同一であるために，対応するファイル同士は高い類似度を持つと考えられこれらの研究はソフトウェアのバージョン間の具体的なる．ソフトウェアの派生関係を明らかにするためには，あ差異については考慮しておらず，ソフトウェアの差異に関るバージョンのソースファイルが別のバージョンのどのする開発者の理解を支援することが目的ではない．

ソースファイルに派生したかという対応関係を求め，内容

開発ブランチを比較することになる．この対応関係を求めるためには，

ソフトウェアの開発において，リリース用のリリースブ
ランチと機能追加・テスト用の開発ブランチとにソース
コードを分岐させることが行われている [4]．

ソースコードの類似度が有効である．

Yoshimura ら は 産 業 向 け シ ス テ ム の ソ ー ス コ ー ド について，類似度の高いファイルの存在を可視化した [5]．

図 1 の例では 2 種類の開発ブランチで機能追加をし，安Yoshimura らの手法では，どのファイル同士が類似してい定したらリリースブランチに統合している．この場合，統るかをグラフの形で図示することができるが，類似してい合後の版はリリースブランチに属するが，リリースブラン

るファイル同士をグループ化するだけであり，それらのチの統合前の版よりも開発ブランチの直前の版のほうが，ファイル間の実際の関係については，ファイルの内容を手類似度が高い場合も考えられる．全てのバージョンを時系作業で調査する必要がある．

列順に並べると図 1 下のようになるが，上と比較して，ソInoue らが開発した Ichi Tracker[1] では，コード断片をフトウェアの派生関係を的確には表していないことがわ

ソースコード検索エンジンで検索し，検索結果のソース

かる．

ファイルをコード断片との類似度でクラスタリングする．
その上で，ソースファイルを時系列順に並べることにより

c 2012 Information Processing Society of Japan

2

情報処理学会研究報告
IPSJ SIG Technical Report

ソースコードの再利用の経緯を可視化する．だだし，この

䝣䜯䜲䝹㻝

䝣䜯䜲䝹㻞

䝣䜯䜲䝹㻟

ツールでは開発者が注目している 1 ファイルとの類似度だ

void P(){
methodA();
methodB();
methodC();
return;}void P(){
methodA();
return;}void P(){
methodA();
methodC();
return;}けを用いてファイルの可視化を行っており，互いに異なるファイルであっても元のファイルからの類似度が等しければ，同一のグループに所属しているかのように可視化されてしまう．
本研究ではソースコードの内容を用いて，ソフトウェアの派生関係の抽出を目指す．また，ファイル間の差異に重

䝣䜯䜲䝹㻞
ᕪศ
methodB();
methodC();(a) 差分の重複あり

点を置くことで，開発者の理解を支援する．

2.3 ソースファイルの比較
実際にソフトウェアの進化を理解するためには，「この

㔜」

ᕪศ
+
methodC();

䝣䜯䜲䝹㻞

䝣䜯䜲䝹㻟

䝣䜯䜲䝹㻝

void P(){
methodA();
return;}void P(){
methodA();
methodC();
return;}void P(){
methodA();
methodB();
methodC();
return;}ファイル同士が似ている」という情報だけではなく，「ファ
イル間でどの部分がどのように変更されたのか」という情報が必要になる．

ᕪศ+
methodC();

ソースファイルを比較する手段としては，2 ファイル間ᕪศ+
methodB();の差分を行の追加と削除の 2 種類で表現する UNIX diﬀ[6](b) 差分の重複なしが一般的である．本稿では差分とは Unix diﬀ の出力を指

図 2 比較順序による差分の重複の有無

すものとする．バージョン管理システムでは，あるファイ

Fig. 2 Overlaps in the diﬀerence

ルと，別々の変更を行った 2 ファイルとを比較，統合する 3-way マージ機能を備えているものもあるが，任意の 3がバージョン管理システムによって管理されていれば，コファイルを比較するものではない．任意の 3 ファイル以

ミットログからソフトウェアの派生履歴を追跡可能であ

上を比較するツールはいくつか存在するが，ほとんどは 2る．しかし，バージョン管理システムが用いられていないファイルの比較を並べたものであるため，ファイルの比較

場合，あるいはリポジトリが複数に分かれてしまっているは 2 ファイル間で行うことが一般的であると言える．

場合もあり，これらは常に利用可能な情報とは言えない．

類似するソースファイル間のすべての差分を調査するコ
ストは，ファイル数の増加に従い大きくなる．N 個のソー3. 提案手法

スファイルに対してファイル間比較を行うには，単純計算提案手法では，ソースファイルの近似した派生関係を定で N (N − 1)/2 回の比較が必要となり，ファイル数の 2 乗

義し，それに基づいて Java で書かれた類似ソフトウェアの速度で比較回数が増加する．これは計算機にとっては問集合の解析を以下の手順で行い，ソースファイルの派生関

題ないが，差分を実際に読み解く開発者の負担が非常に大係を自動抽出する．

きくなる可能性がある．
適当に比較順序を定めることで，比較回数は N − 1 回に減らすことが可能である．しかし，比較順序の設定方法によっては，2 つの差分間において重複する部分が存在して• 類似関係にあるファイルのグループ化• 類似関係にあるファイル間の派生関係の抽出
近似した派生関係の定義について述べ，各手順について，
詳細に説明していく．

しまう．例えば図 2(a) の順序で 3 つのファイルを比較する
場合，出力される 2 つの差分の中に methodC(); が 2 回出

3.1 派生関係の近似

現する．この例では差分は 1 行のメソッド呼び出しである

あるソースコード A1 を変更してソースコード A2 を作が，差分が複数行にわたる処理になるケースでも同様の重成したとき，A1 と A2 の間には派生関係があると言える．

複は起こりうる．重複する部分を何度も調査することは非

本稿ではこれを「本来の派生関係」と呼ぶ．本来の派生関

効率的であるので，差分の重複が少なくなるような比較順

係には，コードの進化の向き（この例では A1 → A2）が存序を考える必要がある．先の例では，図 2(b) の順に比較す在する．

ることで，差分の重複を解消することができる．差分の重ソースコードの解析のみで本来の派生関係を得ることは複が少ない比較順序としてはソフトウェアが進化していっ

難しいため，本研究ではソースコードから得られる情報にた順序をたどるのが妥当であるが，ソフトウェアの進化順

よって派生関係を近似する．関連研究 [1], [5] では，類似序が明確でない場合も考えられる．ソフトウェアが単一のするファイルを検出するためにファイル間の類似度を利用

組織で枝分かれなく進化しているならば，ソースファイル

していた．実際にファイルを比較する際には，ソースコー

を更新日時の順に並び替えればよい．また，ソースコード

ドを人間が読解するか，あるいはツールで処理することにc 2012 Information Processing Society of Japan

3

情報処理学会研究報告
IPSJ SIG Technical Report
ゎᯒᑐ㇟䛾
ྲྀᚓ

ࢯࣇࢺ࢙࢘࢔
ࢯࣇࢺ࢙࢘࢔
ࢯࣇࢺ࢙࢘࢔
ࢯࣇࢺ࢙࢘࢔
ࢯࣇࢺ࢙࢘࢔
ࢯࣇࢺ࢙࢘࢔
㢮ఝ䝋䝣䝖䜴䜵䜰㞟ྜ

_____
_____
_____
_____
_____
_____
_____
_____
_____
__________
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____

methodint
䝋䞊䝇䝣䜯䜲䝹
B int
i
䛾ṇつ໬
String
( i
=
int
tired
)method=
0iint== i B0“I am”(
0=)
0

析を行い，ソースコードを 1 行 1 トークンに切り分ける．
その後コメントおよび空白を除去する．これにより各ファ
イルが正規化された状態となる．今回は識別子名の正規化は行っていない．
類似度計算

㢮ఝᗘィ⟬

正規化後のファイル同士の差分をとり，追加，削除された行数と共通している行数を数え，類似度計算を行う．

䜾䝹䞊䝥໬

ファイル間差分の計算には，java-diﬀ[7] を用いた．正規化
後の 2 ファイル A,B の類似度 Simirality(A,B) は式 1 であらわされる．使用する差分計算ツールの出力により式 2 に

図 3

グループ化手順の概要

変形して利用可能である．

ストと関係があると考えた．そこで本研究では，派生関係

Similarity(A, B)
A,B 間で共通する行数=(1)
A,B 間で共通する行数 + A,B 間の差分の行数
A の行数 + B の行数 − A,B 間の差分の行数(2)=
A の行数 + B の行数 + A,B 間の差分の行数がないファイル間よりも，派生関係があるファイル間のA,B は正規化後のファイルであるので，「A の行数」とは方が差分の行数が小さいと仮定する．つまり，あるソース「A の元ファイルをトークン化しコメントと空白を除いたファイル A1 と，A1 から見て最も差分の行数が小さいソー長さ」である．

Fig. 3 An overview of grouping

なる．その際，ソースファイルがどれほど類似しているかの割合よりも，実際の行数のほうが差分の理解に必要なコスファイル A2 との間には派生関係があるとみなす．類似

また，ファイルサイズが大きく違うものは類似度が低い

ファイル集合の中で，最も差分の行数が小さいソースファため，今回はファイルサイズに２倍以上の差がある場合にイル間から順にすべてのファイルを連結することで，ファは類似度の計算を省略した．

イル集合の中での近似した派生関係を得る．以後本稿では類似度計算の後，ソースファイルを頂点，ファイル間の「派生関係」とは，この近似した派生関係を意味する．ど類似度を辺の重みとした無向重みつきグラフを生成する．

ちらのファイルが元になっているかはわからないため，こ

グループ化の定義では派生関係の向きは定めない．本来の派生関係で

次に，無向重みつきグラフの各辺について，類似度がしは進化の向きが存在するため，進化の始点となるファイル

きい値以下の辺を削除する．これにより類似度の高いファを決定可能である．この場合ソースファイルの比較の際にイル同士のみが連結されたグラフが生成される．辺を削除

は，始点となるファイルから順に本来の派生関係をたどれしたことにより，グラフは非連結な複数のグラフに分割さばよい．一方，本研究での派生関係は向きを定めていない

れる．分割された各グラフは，大量のソースファイル集合

ために，進化の始点がわからないために，始点となるファから類似関係にあるファイルをグループ化したものとなる．

イルを手作業で調査する必要がある．そこで，すべての類
似するソースファイルが派生関係で連結されたのち，差分を読む総行数が少なくなるようなファイルを計算することで，比較の際の始点を提示する．

3.3 類似関係にあるファイル間の派生関係の抽出
類似関係にあるファイルをグループ化した後，グループ
ごとにファイルの派生関係を抽出する．また，この手順においては派生関係をどのファイルからたどり始めるとよい

3.2 類似関係にあるファイルのグループ化
この手順は Yoshimura らの手法 [5] に基づき，類似ソフ

か，その始点となるファイルを提示する．
差分の計算

トウェアの集合から，類似関係にあるファイルを抽出しググループ内の正規化後のファイルについて，ソースファ

ループ化する．図 3 にグループ化までの手順の概要を示す．

イルを頂点，差分の行数を辺の重みとした無向重みつきグ

解析対象の取得

ラフを生成する．今回はグループ化の際に取得した差分の入力された類似ソフトウェアのファイル集合から，解析対象とするものを取得する．今回の解析では Java で記述されたものを対象とているため，入力されたファイル集合

行数をそのまま利用する．
最小全域木の構築
生成したグラフに対し，最小全域木を求める．全域木とから拡張子が.java のものを特定する．

は，あるグラフの部分グラフのうち，すべての頂点が連結

ソースファイルの正規化されており，かつ閉路が無いグラフである．最小全域木とコーディングスタイルの違いを吸収するためにソース

は，グラフを構成する辺の重みの総和が最小となる全域木

コードを正規化する．解析対象の各ファイルに対し字句解である．最小全域木を求めることで，すべてのファイルを

c 2012 Information Processing Society of Japan

4

情報処理学会研究報告
IPSJ SIG Technical Report↓ྥ㔜䜏䛴䛝䜾䝷䝣

3

5

6
5
8

7

6

7

㊥㞳䛾ྜィ
᭱ᑠ

᭱ᑠ඲ᇦᮌ
3

3
3

5
6

5

4

㊥㞳ࡢྜィ㸸⾜3

最小全域木の構築

5

10

5

7
7

5

14

㊥㞳ࡢྜィ㸸⾜
12
14

5

5
4

4

4

㊥㞳ࡢྜィ㸸⾜Fig. 6 Caluculating the sum of the deﬀerences䠖ᮌ䛻ྵ䜎䜜䛯䝣䜯䜲䝹

4

9

4

図 6 他ファイルへの差分の合計を計算

5䠖ᮌ䛻ྵ䜎䜜䛶䛔䛺䛔䝣䜯䜲䝹

6

8
5

10

3

㊥㞳ࡢྜィ㸸⾜

3

9

8

5

6

6

4

㊥㞳ࡢྜィ㸸⾜

4

5
8

5
5

5

Fig. 4 Structureing a minimum spanning tree

3

5

5

12

5

図 4

3

3

5
8

4
ᕪศࡢྜィ㸸⾜ᕪศࡢྜィ㸸⾜

8

5

5

4

3

4

㢮ఝ䝣䜯䜲䝹䜾䝹䞊䝥᭱ᑠ඲ᇦᮌ

4. ケーススタディ

3

3

5
5
4

5

5
4

4

手法を簡単に実装し，いくつかのソースコードに適用し4

ጞⅬ䠄௵ព䠅

図 5Prim 法による最小全域木の構築

Fig. 5 Finding a minimum spanning tree using Prim’s algorithmて結果の調査を行った．同一ソフトウェアのバージョン違いのほかに，ソフトウェアの単一のバージョン内のファイルに対しても解析を行い，類似ファイル同士の関係を可視化した．グループ化の際の類似度のしきい値は 0.8 とした．

含み，かつファイル間差分の行数の合計が最小となるよう

4.1 結果な木を得ることができる（図 4）．この木が，自動抽出した

単一バージョン内の類似ファイルの比較

ファイル間の派生関係である．最小全域木を求めるアルゴ

対象として携帯電話端末 F-05D[9] に含まれる Open-

リズムとして，Prim 法 [8] を用いた．アルゴリズムの適用

HealthManager のソースコードを用いた．抽出された 2

例を図 5 に示す．Prim 法では，始めに元となるグラフか

ファイル以上を含む類似ファイル集合は 13 あった．そのら任意の頂点を木に追加する．木に含まれる頂点から木に中から 1 つを抜き出したのが図 7 である．派生関係の始点含まれない頂点への辺のうち，重みが最も小さいものを順となる頂点は二重線で囲って示した．

次木に追加していく．重みが最も小さい片が複数ある場合

図 7(a) からわかるように，ファイル間の差分は 24 行とは，そのうちどれか 1 つを選択する．選択する辺によって48 行の 2 種類しかない．そのため図 7(b) はここから得ら

最小全域木の形は変わるものの，最終的な重みの合計は変れる唯一の最小全域木ではない．

化しないことがアルゴリズムで保証されている．この作業

図 7(b) の差分を読んだ結果，2 種類に分類することがでをすべての頂点が木に含まれるまで行った時，作成した木

きた．24 行の差分は，クラス名とリテラル名が変更されては最小全域木となっている．

いるほか，呼び出すクラス名が異なっていた．48 行の差分

始点の選定
「他のファイルへの差分」の合計が最小になるファイル
を，比較の始点として提示する．最小全域木内のすべての頂点について，他の頂点への経路の重みの合計を計算する．

は，24 行の差分の内容のほかに，メソッド名とその返り値の型も変更されていた．
同一ソフトウェアのバージョン間の比較対象として AlgoUML[10] の 8 つのバージョンを比較し

全域木は閉路を持たず任意の頂点間の経路が一意に定まるた．抽出された 2 ファイル以上を含む類似ファイル集合はので，この値も一意である．経路の重みの合計が最小にな

2247 あった．その中から抜き出したのが図 8 と図 9 である頂点を，比較の始点とする（図 6）．

る．各頂点のラベルの最初に付した番号がバージョン番号

提示した始点からの比較順序は開発者が読む差分の量をである．なお，全く変更のないファイル同士は派生関係で削減することを目的としているため，本来の派生関係の順

は同一の頂点にまとめてある．派生関係の始点となる頂点

序（ソースファイルの新旧）とは一致しないことに注意すには二重線で囲って示した．

る．最小全域木と，始点を示すことで，開発者が読むべき

図 8(b) を見てわかるとおり，ファイル CrUML.java は差分の量を減らしたファイルの派生関係を提示できる．

バージョン 0 から 7 まで 4 回の変更を受けており，その順

c 2012 Information Processing Society of Japan

5

情報処理学会研究報告
IPSJ SIG Technical Report
1: CrUML.java

0: ScanReportInfoMPGrouped.java

107
151

48

4: CrUML.java

0: CrUML.java

0: ScanReportInfoMPVar.java
0

48

48

107

2

48 24

24
0: ScanReportInfoMPFixed.java

24

151
67
2: CrUML.java

109
0

48
24
48

0

0: ScanReportInfoFixed.java

107

42

2

24
48

107

107

109
7: CrUML.java

24

24ScanReportInfoVar.java
0:

67

2

40

6: CrUML.java

3: CrUML.java

40
107

0

40

48
5: CrUML.java

0: ScanReportInfoGrouped.java(a) 類似ファイル集合の関係(a) 類似ファイル集合の関係
0: ScanReportInfoFixed.java

0: CrUML.java

24

151
1: CrUML.java
2: CrUML.java

0: ScanReportInfoMPFixed.java
48
24
0: ScanReportInfoVar.java

0: ScanReportInfoMPGrouped.java
24

67

0: ScanReportInfoGrouped.java
24
0: ScanReportInfoMPVar.java

3: CrUML.java(b) 抽出した派生関係
図 7 OpenHealthManager 内の類似ファイル集合

40

Fig. 7 Set of similar ﬁles in OpenHealthManager

6: CrUML.java
5: CrUML.java
4: CrUML.java

番通りに派生関係が抽出できている．

2

一方で，図 9(b) の例では，バージョン番号と順序が一致しない個所が見られた．バージョン 2 に向かう辺がバー

7: CrUML.java

ジョン 1 ではなくバージョン 0 から，バージョン 3 に向かう
辺がバージョン 2 ではなくバージョン 0 から出ていること(b) 抽出した派生関係が確認できる．このファイル集合を確認したところ，これらのファイルはインターフェイスであった．差分を調査す

図 8

AlgoUML:履歴復元に成功した例

Fig. 8 AlgoUML: an example that maches the version history

ると，バージョン 0 に「getAssocationRole」というメソッド宣言が存在し，バージョン 1 で「getAssociationRole」とめておくなどの工夫があると比較が容易になると考えらいうメソッド宣言が追加されていた．その後バージョン 2

れる．

では「getAssocationRole」が削除された．引数の部分は 2

AlgoUML のソースコードにおいて，バージョンの順番

つのメソッド宣言で差がなかったことから，バージョン 1と抽出した派生関係の形が一致しない例が見られた．あるからバージョン 2 の「メソッド宣言の削除」よりもバーバージョンで追加された要素が次のバージョンで削除されジョン 0 からバージョン 2 の「メソッド名の変更」のほうる「手戻り」は最小全域木の形に影響を与えることがわかが差分が少ないという結果になった．バージョン 2 とバーる．変更箇所が手戻りだけならば，バージョン履歴とは一ジョン 3 に関しても，一旦追加されたメソッド宣言が削除

致せずともソースコードの変化としては自然と考えられされたためにバージョン 0 からの差分の方が小さなものとる．しかし，同時に他の場所で機能追加が行われていた場なっていた．

合など，バージョン間で複数の変更があった際には手戻りによる差分の行数への影響は，ソースファイルの派生関係

4.2 考察F-05D のソースコードにおいては 1 つのファイルに同様の変更が施されていたため差分の大きさが同じ辺が複数生じていた．重みの同じ片が存在すると最小全域木は複数の形を取りうる．同一カ所への複数パターンの変更は，まとc 2012 Information Processing Society of Japan

が正確に抽出できなくなる要因となる恐れがある．

5. 関連研究5.1 コードクローン検出技術
ソースコードの類似性に関する技術の一つに，コードク

6

情報処理学会研究報告
IPSJ SIG Technical Report

ルを特定したといえる．

5: CollaborationsHelper.java
00

コードクローン検出技術ではソースコード中の類似する

54

3: CollaborationsHelper.java

4: CollaborationsHelper.java

0部分に着目しているが，本研究ではソフトウェアがどのよ
うに進化したかを把握するためにコードクローン検出技術

10
0

0

54

54

0

10

で得られる “どの部分が一致・類似しているのか” という情報ではなく，“どの部分が変更されたのか” という情報に

62
10

6: CollaborationsHelper.java

0: CollaborationsHelper.java

54
62

64

10

10

62
62

注目している．

5.2 リポジトリマイニング
バージョン管理システムは，ソフトウェア開発において

7: CollaborationsHelper.java

1: CollaborationsHelper.java

72
76

32

ソースファイルの変更履歴を保存し管理するために利用

40

2: CollaborationsHelper.java

される．大規模なソフトウェアリポジトリに対して，バー(a) 類似ファイル集合の関係

ジョン管理システムにより得られる情報を活用した解析は多く行われている．Śliwerski らは，CVS のリポジトリを

1: CollaborationsHelper.java

10

2: CollaborationsHelper.java

32 0: CollaborationsHelper.java

利用してバグを含む変更はどのような時に多いかを調査した [15]．Cubranic らはバージョン管理システムのほかにバグトラッキングデータベース，メーリングリストを組み合わせ，開発に関する情報を抽出した [16]．リポジトリに対するこれらの調査は，バージョン管理システムから様々な

54

6: CollaborationsHelper.java
3: CollaborationsHelper.java
5: CollaborationsHelper.java
4: CollaborationsHelper.java

10

情報を得て解析を行っている．本研究では，これらの情報なしに，ソースコードのみを用いて解析を行っている．

6. 今後の課題
今回の手法の実装は簡易的なものであり，また対象としたソフトウェア集合の規模も大きくない．より大きな，分

7: CollaborationsHelper.java(b) 抽出した派生関係
図 9

AlgoUML:履歴復元に失敗した例

Fig. 9 AlgoUML: an example that unmaches
the version history

岐を含むソフトウェア集合に対して実験を行うことが主な課題となる．その他の手法の改善点を挙げる．

6.1 ディレクトリ・アプリケーション単位での比較
今回はファイル単位での比較を行ったが，実際のアプリ
ケーションを比較する際には，ディレクトリ単位やアプリ

ローン検出技術がある．コードクローンとは，ソースコー

ケーション単位など，粒度を大きくしてソフトウェア自体ド中に存在する互いに一致・類似したコード片のことであの派生関係を把握出来るようにしたい．その際，ファイル

り，これまでに様々なコードクローン検出手法が研究され単位の派生関係とソフトウェアの派生関係で，出力されるている [11][12]．

グラフが異なる形になることも考えられる．個々のソース

コードクローン検出に関する既存研究では，複数のソ
フトウェア集合の解析を想定した手法も提案されており，ファイルの進化と，ソフトウェアの進化の間にどのような関係があるかを調査することが今後の課題となる．

その中にはファイル単位やメソッド単位など粒度の大きなクローンも含まれていることが既存研究で報告されて6.2 識別子名の正規化

いる．佐々木らはファイル単位でのクローン検出を行い，Bellon らは，コードクローンの差異の程度に基づき，コー

FreeBSD Ports Collection の中に約 68%のファイルクロー

ドクローンを 3 つに分類している [17]．そのうち，タイプンを検出した [13]．また，石原らは大規模ソフトウェア群

2 では，変数名や関数名，変数の型などが変更されているからメソッド単位のコードクローンを検出し，ファイルク

コードクローンを定義している．

ローンでないファイル間でもメソッドのクローンが存在す

今回の正規化では識別子名や型名はそのままの文字列とることを確認した [14]．これらの研究により，派生関係にして扱ったが，識別子名を適当な文字列に置換して正規化あるソフトウェア間ではファイルやメソッドが多く流用することで，識別子名のみの変更を無視し，処理の追加・されていることが明らかになっている．つまり，コードク

削除に注目した解析が行える．

ローン検出技術を用いてソフトウェア間で類似するファイc 2012 Information Processing Society of Japan

7

情報処理学会研究報告
IPSJ SIG Technical Report

6.3 類似度計算の高速化
テキストベースの差分比較手法は，コストが大きいこと

参考文献
[1]

が指摘されている．そのため，ソースコードを直接比較せず，メトリクスや統計的手法などを用いる研究も提案されている [18]．本手法では，類似度計算はすべてのファイル間で行うが，おおよそ類似していると思われるファイル同[2]

士をグループ化するための手段であるので，類似度計算を精度は劣るが高速な別の手法で行うことで処理の高速化が[3]期待できる．
一方，類似ファイルをグループ化した後の比較は，実際[4]にソースコードが異なるかが重要であると考えている．この部分に関しては，提案手法のようにテキストベースでの差分抽出を用いて，実際の差分に基づいた派生関係を抽出し，また開発者が読解するコードの絶対量を減らすことが[5]

適していると考えている．
[6]

6.4 派生関係の順序
今回の手法では差分の行数のみに着目して比較の始点を定めたため，提示する比較順序は本来の派生関係の順序とは無関係であった．ファイルが作成された日付がわかって

[7]
[8]

いるならば，古いファイルから新しいファイルへ進化する
形のグラフにすることで，より実態に近い派生関係が得ら[9]れると期待できる．
また，ソフトウェアの変更は機能削除よりも機能追加・修正の方が主であると考えられる．このことから，ソース

[10]
[11]

コードに対する変更は削除よりも追加のほうが多いと仮定
し，行の追加が大きく，削除が小さくなるような方向を求めることで，ソースファイルの派生関係の方向とすること[12]も検討できる．

6.5 他言語への適用[13]

今回は Java で記述されたプログラムを対象としたが，この手法は他の言語でも適用できると考えている．ソース
コードの正規化部分に関しては，言語に応じてトークン化[14]を行わなければならないが，トークン化が難しい場合など
はコメントや空白空行のみを除去する簡易的な正規化を行[15]うことで，少ないコストで多くの言語に応用できる．また，類似度計算や差分の計算は，テキストベースの手法である
ので，ソースコードが行単位で記述されているか，行単位[16]に分割可能であれば Java 以外の言語でも実行可能である．
謝辞

[17]

本研究は，日本学術振興会科学研究費補助金基盤研究（A）（課題番号:21240002）および若手研究 (A)（課題番
号:23680001）の助成を得た．

c 2012 Information Processing Society of Japan

[18]

Inoue, K., Sasaki, Y., Xia, P. and Manabe, Y.: Where
does this code come from and where does it go? – Integrated code history tracker for open source systems –, in
Proc. 34th International Conference on Software Engineering, pp. 331–341 (2012).
Pinzger, M., Gall, H., Fischer, M. and Lanza, M.: Visualizing multiple evolution metrics, in Proc. ACM Symposium on Software Visualization 2005, pp. 67–75 (2005).
Jaafar, F.: On the analysis of evolution of software artefacts and programs, in Proc. 34th International Conference on Software Engineering, pp. 1563–1566 (2012).
Tarvo, A., Zimmermann, T. and Czerwonka, J.: An
integration resolution algorithm for mining multiple
branches in version control systems, in Proc. 27th International Conference on Software Maintenance, pp.
402–411 (2011).
Yoshimura, K. and Mibe, R.: Visualizing code clone outbreak: An industrial case study, in Proc. 6th International Workshop on Software Clone, pp. 96–97 (2012).
Myers, E. W.: An O(ND) diﬀerence algorithm and its
variations, Algorithmica, Vol. 1, No. 1, pp. 251–266(1986).
incava.org
java-diﬀ,
http://www.incava.org/
projects/577828189.
Prim, C. R.: Shortest connection networks and some generalizations, Bell Syst.Tech.J., Vol. 36, pp. 1389–1041(1957).
携帯電話 (F-05D オープンソースソフトウェア) - FMWORLD.NET（個人） : 富士通:, http://spf.fmworld.
net/oss/oss/f-05d/.
argouml.tigris.org, http://argouml.tigris.org/.
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: amultilinguistic token-based code clone detection system
for large scale source code, IEEE Trans. Softw. Eng.,
Vol. 28, No. 7, pp. 654–670 (2002).
Li, Z., Lu, S., Myagmar, S. and Zhou, Y.: CP-Miner:
Finding Copy-Paste and Related Bugs in Large-Scale
Software Code, IEEE Trans. Softw. Eng., Vol. 32, pp.
176–192 (2006).
佐々木裕介, 山本哲男, 早瀬康裕, 井上克郎：大規模ソフト
ウェアシステムを対象としたファイルクローンの検出, 電子情報通信学会論文誌. D, 情報・システム, Vol. 94, No. 8,
pp. 1423–1433 (2011).
石原知也, 堀田圭佑, 肥後芳樹：大規模ソフトウェア群に対するメソッド単位のコードクローン検出, 電子情報通信学会技術研究報告 : 信学技報, Vol. 111, No. 481, pp.
31–36 (2012).
Śliwerski, J., Zimmermann, T. and Zeller, A.: When dochanges induce ﬁxes?, in Proc. 2nd International Workshop on Mining Software Repositories, pp. 1–5 (2005).
Cubranic, D. and Murphy, G.: Hipikat: recommending
pertinent software development artifacts, in Proc. 25th
International Conference on Software Engineering, pp.
408–418 (2003).
Bellon, S., Koschke, R., Antoniol, G., Krinke, J. andMerlo, E.: Comparison and Evaluation of Clone Detection Tools, IEEE Trans. Softw. Eng., Vol. 33, pp. 577–
591 (2007).
Kontogiannis, K., Demori, R., Merlo, E., Galler, M. andBernstein, M.: Pattern Matching for Clone and Concept
Detection, Autom. Softw. Eng., Vol. 3, No. 1/2, pp. 77–
108 (1996).

8