論 文
版管理システムを用いたクローン履歴分析手法の提案
川口 真司† a)松下誠††

井上 克郎††

Clone History Analysis Using Conﬁguration Management System
Shinji KAWAGUCHI†a) , Makoto MATSUSHITA†† , and Katsuro INOUE††

あらまし ソフトウェアの保守工程における大きな問題の一つとしてクローンが指摘されている．コピーされて生成されたクローンは多少の編集が施されることが多く，そのような場合でも適切にクローンが検出できるよ
うにするため様々なクローン検出手法が提案されている．これらの手法は最新時のソースコードに対して分析を行うが，より施された編集が少ない時点に遡ってクローン分析を適用することで，最新時の分析だけでは得られないクローンを得ることができる．このような過去にクローン関係にあったコードを抽出するためには過去のソースコードにおけるクローン解析結果に加えて，過去に存在したクローンが現在のソースコードのどこに対応するのかという情報，すなわちクローン履歴が必要である．本論文では，版管理システムに蓄積されたソース
コードを対象としてクローンの履歴を抽出する手法を提案する．本手法ではまずクローン分析を過去の時点に遡って順次適用し，各時点間のクローンについてクローン履歴を抽出する．また，PostgreSQL に対して提案手法を適用し，抽出できるクローンの有用性について考察を行う．
キーワード

クローン，履歴，ソフトウェアリポジトリとで，クローン解消作業の負担を減らすために利用さ

1. ま え が きれている．

近年，ソフトウェアの大規模化にともないソフトウェ

しかし，実際には関連性が高いにも関わらず，最新アの開発工程において保守工程の占める割合は年々増のバージョンを分析するだけではクローンとして抽出

加の一途を辿っている．保守工程におけるさまざまなできないコード片が存在する．図 1 にそのようなコー問題のなかでも非常に大きな問題の一つとして，ソード片の例を示す．図 1 は時刻 t − 1, t におけるソース

スコード中に含まれる重複コード (以下，クローン) がコードに含まれるクローンを表している．時刻 t − 1

挙げられる [1]．もしクローンの一つに不具合が見つにおいて二つのクローンセット (互いにクローン関係

かった場合，すべてのクローンを調査し，それぞれににあるクローンの集合) が存在している．そして，時刻対して同様の修正を施すことになる可能性が高い．こt においてクローンセット B のうち一部のクローンにの作業はソフトウェアが大規模であればあるほど困難

編集が加えられた結果，二つのクローンセット B 0 , C 0となる．

に分かれている．

この問題に対処するべく，これまでにクローンを検

このとき，もしクローンセット B 0 に不具合が見つ出するための様々な手法が提案されており，そのいくかった場合には，クローンセット B 0 だけではなく，若つかは実際に利用可能なシステムとして実用化されて干の編集を加えられたクローンセット C 0 もまた見過いる [2]．このようなクローン抽出システムは，大規

ごせないコピーの一部である (以後，クローンセット

模なソフトウェアから自動的にクローンを発見するこC 0 をクローンセット B 0 の分岐クローンセットと呼ぶ．
逆も同様)．しかし，これまでに提案されているクロー†

奈良先端科学技術大学院大学情報科学研究科，生駒市

ン分析では現時点での情報のみを用いて分析を行うた

Graduate School of Information Science, Nara Institute of Science and Technol-

め，時刻 t においてはクローンセット B 0 にとってク

ogy, 8916-5 Takayama-cho, Ikoma-shi, 630-0101 Japan††

大阪大学大学院情報科学研究科，豊中市
Graduate School of Information Science and Technology, Osaka University, 1-3
Machikaneyama-cho, Toyonaka-shi, 560-8531 Japana) E-mail: s-kawagt@is.naist.jp

ローンセット C 0 はクローンセット A0 と同じく無関係
なクローンセットでしかない．
このようなクローンセット同士の関係を抽出するに

電子情報通信学会論文誌 X Vol. Jxx–X No. xx pp. 1–9 xxxx 年 xx 月

1

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

Clone A-2

void createColumnCache(COLUMN *c){CacheInfo *cache = malloc(sizeof(CacheInfo));
setColumnUntara(cache);
setColumnKantara(c, cache);}Clone A-1

Clone Set A

Clone Set A’

Clone B-1

Clone B-1
Clone B-2

Clone B-2
Clone B-3

void createTableCache(TABLE *p){
CacheInfo *cache = malloc(sizeof(CacheInfo));initialCacheInfo(cache);setCacheInfo(p, cache);}

Added a conditional statement

Clone A-2

Clone A-1

Clone Set B’

Clone B-4
Clone B-5

Clone C-1

Clone Set B
Clone B-3, B-4, B-5
are edited.

Clone C-3

Clone C-2

Clone Set C’

Ft-1

void createTableCache(TABLE *p){if (! isTableImmutable(p)){
TableCacheInfo *cache =malloc(TableCacheInfo );initialTableCacheInfo(cache, p);
setTableKantara(p, cache);} else {ReadOnlyTableCacheInfo *cache =malloc(ReadOnlyTableCacheInfo );initialTableCacheInfo(cache, p);
setTableKantara(p, cache);}}B-1, 2 and C-1, 2, 3 are similar.

Ft

図 1 クローンの変更履歴
Fig. 1 Clone Evolution

は，過去のソースコードにおけるクローン解析結果にメント等を除去するとともに，入力テキスト中の変数

加えて，過去に存在したクローンが現在のソースコー

名や関数名等を同一記号に縮退させる．その後に，しドのどこかに対応しているのか，対応しているとすれきい値以上の長さの共通字句列を探索し，全ての対のばそれがどこなのかという情報が必要である．

リストを出力する．コピー& ペーストによってクロー

そこで，本研究では過去と現在のクローン間の繋がンが作られた場合，変数名などが変更されないことはりを分析するための手法として，クローン履歴分析を稀であり，何らかの形で変数名などがコピー先のコン提案する．クローン履歴分析では，現時点のクローン

テキストに合致するよう書きかえられることが多い．

が過去のバージョンのどのクローンに対応するのか，

CCFinder では変数名，関数名を同一記号とみなすこ

今あるクローンがどのような変遷を辿ってきたのかをとによって適切にコピーを検出できる．また，長大な特定する．

共通字句列が存在したときに，その部分字句列が併せ

2. 前提とするシステム
2. 1 クローン分析システム
クローン分析手法には大きくわけてソースコードの字句解析に基づく手法 [1, 3, 4] と，特徴メトリクスに基づく手法 [5, 6] に分けられる．ソースコードの字句
解析に基づく手法 では，ソースコード中で同一の文字列を検索することでクローンの検出を行う．特徴メト
リクスに基づく手法では，例えばクラスや関数，ファイルのようなプログラム中のある種の単位ごとに特徴
メトリクスを定義・算出し，それらのメトリクス値が類似したものをクローンとして抽出する手法である．
一般には字句解析に基づく手法のほうがコストが増えるが，より細粒度なクローンを抽出できる．
本研究では，字句解析ベースの検出ツール CCFinder[1] を利用してクローン履歴の分析を行う．CCFinderて出力されるのを防ぐために，それぞれ互いに包含関係でないもののみをクローンとして出力する．

2. 2 版管理システム
版管理システムとは CVS [8] や Subversion [9] のようにプロダクトの保管・管理に用いられるシステムである．版管理システムでは，管理下のプロダクトを任意の時点の状態に復元して取得する機能が提供されている．
冒頭でとりあげた分岐クローンセットを取得するた
めには，過去のソースコードにおけるクローン解析結果が必要であることはすでに述べた．このような情報を得るためには，版管理システムを用いて過去のソースコードを取得し，そのソースコードに対してクローン分析手法を適用すればよい．

3. 諸 定 義は高いスケーラビリティを有しており，大規模なソフ
トウェアに対しても実用的な時間でクローンの抽出を

本節では分析対象となるクローンについて定義を与行える．また，実際にさまざまな大規模ソフトウェア

える．その上で異なる時点におけるコード片の対応関へ適用され，その有用性が確認されている [7]．

係を表す写像の概要と，クローン履歴関係の定義につクローン分析を行う際，CCFinder は空白や改行，コ2

いて述べる．

論文／版管理システムを用いたクローン履歴分析手法の提案

Code snippet

Insertcp: Clone pair
H: Clone history relationship
File
Delete

F0

Ft-1

Ft

∆t

F:Product (Collection of files)

図 2 クローンとクローン履歴関係
Fig. 2 Clone and Clone History Relationship3. 1 ク ロ ー ン
クローン履歴分析のために定義したクローン履歴モ
デルを図 2 に示す．本モデルでは時間と共に変更されるソースコードを ∆t ごとに区切って考える．分析の対象を版管理システムの管理下にあるソースコード
ファイルの集合とし，ある時刻 t における集合をプロ
ダクト (Product) Ft と呼ぶ．

3. 3 クローン履歴関係
Ft−1 のコード片 a と Ft のコード片 b が以下のいずれかを満たす場合，a, b 間には クローン履歴関係(Clone history relationship) があるといい，クローン
履歴関係が成りたつコード片の組 (a, b) の集合を Htと表す (図 3)．Ht は以下に述べる HCt , HTt , HAt の和集合として定義される．

いま，各ファイルを文字列と考え，その連続する部分（ 1 ） HCt : (a, a0 ) が Ft−1 に 関 す る ク ロ ー ン ペ ア，

列をコード片 (Code snippet) と呼ぶ．そして，Ft に含(b, b0 ) が Ft に関するクローンペアで，b が a の，まれるコード片のうち，共通字句列となるコード片の対 (a, b) を Ft に関するクローンペア (Clone pair)，ab0 が a0 の子となる a0 , b0 が存在する．
（ 2 ） HAt : a は Ft−1 に関するクローン，b は Ft にや b をそれぞれ Ft に関する クローン (Clone) と呼ぶ．

関 す る ク ロ ー ン で ，b と 1 行 以 上 重 複 す る 位

このとき a と b はクローン関係 (Clone relationship)

置 に あ る b0 ∈ Change∆t に つ い て (a, b0 ) がにあるという．また，クローン関係を同値関係と考え，{Ft−1 ∪ Change∆t } についてのクローンペアであ

その同値類をクローンセット (Clone set) と呼ぶ．

3. 2 コード片の写像
次に時刻 t より ∆t だけ過去の時点におけるプロダ
クト Ft−1 に含まれるコード片に対して，Ft に含まれるコード片への写像を定義する．例えば Ft−1 にある
コード片がもし編集されていなければ，Ft にも同じ内容のコード片が必ず存在する．また，時刻 t においてる．ただし，Change∆t は Ft のコード片の集合の
うち Ft−1 からの変更時に追加，編集された部分，{Ft−1 ∪ Change∆t } は Ft−1 全体に Change∆tのコード片を追加した部分とする．
（ 3 ） HTt : a は Ft−1 に関するクローン，もしくは Ft−1のコード片で ∃x, (x, a) ∈ HTt−1 ．b は a の子で

a と b のテキスト類似度が高い (テキスト類似度の詳細は後述)．

編集されたテキストを含むコード片についても，図 4のように編集操作を考慮して近似的に対応関係にある

HCt は Ft−1 , Ft の両方に存在する同一のクローン

コード片候補を求められる．このような両者の関係をを表す．本定義は Ft−1 でクローンペアを構成するク写像として定義する．本写像によって Ft−1 のコード

ローン a, a0 が，写像先の b, b0 においてもクローンペ

片 r が空文字列でない Ft のコード片 s に写像される

アを構成している，ということを表す．

時，r を s の親，s を r の子とする．なお写像の詳細な定義は 4. 3 節で述べる．

HAt は Ft において追加されたクローンの履歴を表す．このようなコード片は，既にあるクローンセット
3電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

HCt

HAt
InsertInsert

a

a
HCt

HTt

b

b

HAt

Delete

a

HAt

a’

HCt

Ft-1

b’

a’

Ft

Ft-1

Fig. 3

Ft

HTt

b

Ft-1

Ft

図 3 3 種類の履歴関係
Three Types of Clone History Relationshipのどれとも等しくクローン履歴関係があると考える． （ 0 ） H0 = ∅, CT0 = ∅．
これは，既存クローンのうちどれか一つを原本と決めることは難しく，またそうすることの意義も薄いからである．

（ 1 ） t = 0 の F0 を版管理システムから取得し，クローン解析手法を用いて C0 を求める．
（ 2 ） for t = 1, 2, ..., T

このように本手法では HAt を HCt と分けて定義している．HCt では親子関係が明示的に一意に定まるのに対して，HAt では親が属するクローンセット
内のクローンすべてとクローン履歴関係が存在することになる．そのため，HAt と HCt を分けることでク
ローン履歴関係がより正確なものとなる．
最後の HTt は，かつてクローンを構成していたが最新版ではクローンペアであったコード片が削除，また(2-a) 版管理システムから Ft を取得し，クローン解析手法を用いて Ct を求める．

(2-b) Ft−1 に関する全てのクローンとそれぞれの子について，HCt を求める．

(2-c) {Ft−1 ∪ Change∆t } に対して CCFinder を適用して，HAt を求める．

(2-d) Ct−1 の残りと CTt−1 について HTt を求める．

は編集されて別のクローンセットに属するようになったためにクローンでなくなった，いわば元クローンというべきコード片についてクローン履歴対応関係を抽出するための定義である．
ただし，クローンペアに一度でもなった部分全てを追いつづけるのは非効率である．また，何らかの変更が加わった場合には，その時点で過去のコードとの関連は希薄になる．そこで，テキストの変更度合いを表す尺度としてテキスト類似度を定義する．このテキス
ト類似度はコード片中に占める同一テキストの割合を表す．そして，テキストがほとんど変更されていない
場合にのみクローン履歴対応関係があるものとする．

4. クローン履歴関係抽出手法

このように，本手法では解析を行う期間 [0 · · · T ]を ∆t ごとに区切って考え，クローン履歴対応関係

H1 , H2 , ..., HT を順次，抽出する．
以下に各手順の詳細，および HCt , HTt の抽出時に利用する親子関係を定義するための写像について述べる．

4. 2 各手順の詳細
本節では Ft の解析における各手順について，その詳細を述べる．なお，前節のアルゴリズムにより，時刻 t についての解析をはじめる時点で t − 1 までの各
情報 (Ft−1 , Ct−1 , Ht−1 , CTt−1 ) は既知である．

(2-a) 版管理システムから Ft を取得し，クローン解析
手法を用いて Ct を求める

4. 1 概要以下にクローン履歴対応関係抽出手法の手順を示す．

入力: (版管理システム)
出力: Ft , Ct

なお，クローン履歴解析を適用する期間の始まりを時

まず当該時刻のプロダクト Ft を版管理システムか

刻 0， 終わりを時刻 T で表し，Ct を Ft に関するクら取得し，クローン解析を適用して Ct を得る．本研

ローンの集合，CTt を HTt を満たすコード片のうち究においてはクローン解析手法として CCFinder を用

Ft に属するコード片の集合とする．

い，その解析結果を Ct とする．

4

論文／版管理システムを用いたクローン履歴分析手法の提案(2-b) Ft−1 に関する全てのクローンについて HCt をに含まれるため HAt の解析対象となる．従って HTt

求めるの解析を行う際には，そのようなケースを考慮する必

入力: Ft−1 , Ft , Ct−1 , Ct
出力: HCt

Ft−1 に含まれる全てのクローンペアについて，そ要はない．

4. 3 コード片の写像

れぞれのクローンの子が Ft に関するクローンペアと本研究ではコード片 a ∈ Ft−1 からコード片 b ∈ Ft

なっているかどうかを検証する．もしこの条件を満たへの写像を，各ファイルの行番号の対応関係に基づいしていれば，それぞれの親子ペアは HCt に含まれるて定義する．CCFinder の出力には，コード片がどのものとする．

ファイルの何文字目から始まるか，という情報が含ま(2-c) {Ft−1 ∪ Change∆t } に対して CCFinder を適用れているため，行番号に基づく対応関係を適用するこ

して，HAt を求めるとができる．

入力: Ft−1 , Ft , Change∆t , Ct−1 , Ct

まず時刻 t − 1 と時刻 t において，コード片 a が含

出力: HAt

まれるファイルに変更がなかった場合，a の写像先 b

次に Ft−1 と Change∆t の間にクローン解析を適用の開始行，終了行は a と全く同じとする．

する．そして a ∈ Ft−1 , b0 ∈ Change∆t なるクローン

次に，コード片 a が含まれるファイルに何らかの編

ペア (a, b0 ) があれば，b0 が指す位置にあるクローン

集操作が行われていた場合を考える．もし a よりも前b ∈ Ct を考え (a, b) を HAt に加える．

の部分に変更箇所があれば，その内容に応じて写像先実際に適用する際には，編集された行とその前後 10

b の開始行，終了行を調整する．図 4 の Case 1 はコー

行を Change∆t とする．本研究では CCFinder が検出

ド片 a の前で編集操作が行われた場合の例である．こするクローンの最小トークン数を初期設定の 30 トーのとき，a の前で行われた編集操作の全てを勘案してクンで適用しているため，差分が 30 トークンよりも小a の写像先 b の開始行，終了行は a のそれのそれぞれさい場合にはクローンとして検出されなくなる．前後

4 行後ろとする．また a に含まれる部分に変更が加え

10 行を含めることで，このような差分を含むクローンられていた場合には，その内容に応じて b の終了行をを適切に扱うことができる．

調整する．図 4 の Case 2 では a 内に 2 行新しい行が(2-d) Ct−1 の残りと CTt−1 について HTt を求める

追加されているため，b の終了行は a のそれに対して

入力: Ft−1 , Ft , Ct−1 , HCt , HAt , CTt−1
出力: HTt

2 行追加した値とする．
最後に，クローン片の端の部分で書きかえ操作が発最後に Ct−1 に含まれるコード片のうち HCt , HAt

生した場合について述べる．図 4 の Case 3 ではコー内のペアに含まれないコード片，および CTt−1 に含ド片 a の開始行を跨がる形で書きかえされている．こまれるコード片 a について，その子 b とのテキスト類のような場合，「コード片 a の上に 2 行挿入があった」

似度を計測して HTt の抽出を行う．テキスト類似度という解釈と，「コード片 a に 2 行の挿入がされた」とは以下の式で定義する．

いう解釈，およびその中間 (1 行がコード片の上に，1

T extSim(a, b) =2|a ∩ b|.
|a| + |b|

ただし |a| = a の行数，|a ∩ b| は GNU diff によって同一と判定された行数とする．そしてテキスト類似度が0.7 以上のコード片 b が存在したとき，(a, b) ∈ HTtとする．なお，コード片 a に対して子は複数ありうる

行はコード片 a 中に挿入された) が成りたつ．そこで，
これら全てのケースをコード片 a の子とする．このように複数の子が生成されるケースは以下の 3 つである．

•

開始行，終了行が編集されている箇所を含む (図4 Case 3)• 開始行の一行前に挿入

ため，HTt の条件を満たすコード片も複数存在し得•る．このときには類似度が最大のコード片のみを HTt

本研究においては Ft−1 → Ft への写像のみを扱うの対象とする．
このように HTt の判定条件は，ほぼ同一のテキストかどうかの判定となっている．もしクローン自身も何らかの変更があった場合には，この部分は Change∆t

終了行に挿入ため，削除操作ではこのような複数候補を考える必要はない．
以上述べた 3 つの編集操作による影響をすべて足しあわせて写像先を決定する．
5電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

Case 1t-1

Case 2tCase 3t-1

t-1

tinsert 2 lines

insert 6 linesaadelete 2 lines
move 4 lines underbaincrease 2 linestreplace
4 lineswith
6 linesb’’
b b’
All b, b’, b’’
are children of a.

b
図 4 コード片の写像
Fig. 4 Mapping of Code Snippet

5. 実

験

4. で述べた手法を用いることで図 1 におけるクロー
ンセット B’, C’ 間のような分岐クローンセットを抽出することができる．本節では，PostgreSQL を対象として本手法を適用し，実際に分岐クローンセットをどの程度抽出できているかの検証を行う．

5. 1 実 験 方 法
PostgreSQL リポジトリのなかから，ソースコード
か格納されている src ディレクトリ以下の全てのファCCFinder では検出できない潜在的に存在するコードク
ローンもかなりの数に上るため，全てのクローンセッ
トを検証することは現実的ではないからである．

5. 2 実 験 結 果
Branched clone set

4

Branched clone set (miss)0

Deleted clone set

5

Useless clone set15

表 1 クローン減少箇所の調査結果
Table 1 Clone Decreasing Places

イルを対象とした．これらのファイルを 2005/01/01〜2005/6/30 までの 6 ヶ月間について ∆t を 1 週間と実験手法を適用した結果，クローン減少箇所は計 24

して，計 24 時点についてクローン履歴関係の抽出を箇所あった (表 1)．そのうち 4 つのクローンセットに行った．

分岐クローンセットが存在し (Branched clone set)，そPostgreSQL を対象とした理由は，第一に提案手法

れらのクローン履歴関係が適切に抽出できていることで用いている CVS リポジトリが公開されていること，を確認した．そして，実際には分岐クローンセットで第二に PostgreSQL が非常に広く活用されており，開あるにも関わらず，分岐クローンセット内のクローン発も活発に行われているからである．

についてクローン履歴関係が適切に抽出できていな

そして各バージョンに含まれるクローン ct ，および

かったケース (Branched clonse set (miss)) は存在しな

ct とクローン履歴対応関係にある ct−1 について，ct

かった．また，5 箇所がクローンセット内のクローンが属するクローンセットと ct−1 が属するクローンセッのいくつかが削除されたもの (Deleted clone set)，残りトを考え，図 1 における Clone Set B と Clone Set B’

15 箇所はそもそもクローンとして有用でないものでのようにクローンセット中のクローン数が減少していあった (Useless clone set)．

る箇所を ” クローン減少箇所” として抽出した．

有用でないクローンとは，printf 文が連続している

次に，それぞれのクローン減少箇所において，そこ部分や数十，数百の定数定義が続いている部分などのに含まれるクローンセットが分岐クローンセットであように，単純な構文が 10 行以上連続している部分をるかどうかの判定を人手により行い，もし分岐クロー

指す．CCFinder は構文木として同形であればクローン

ンセットが存在すればクローン履歴関係を正しく抽出として検出を行うため，このような単純な構文が繰りできているかどうか検証した．

かえされている箇所もクローンとして検出される．しこのように本実験ではクローンセット内のクローン

かし，このような部分はそもそもクローンとして検出数の減少が確認できたクローンセットのみに着目した．

する必要がなく，実際にユーザにとっても中身を検討

これは，実際に開発されているソフトウェアには数百する価値がない．したがって，本実験においてはそのから数万もの大量のコードクローンが存在し，さらにような箇所を評価から除外している．

6

論文／版管理システムを用いたクローン履歴分析手法の提案
145 Datum
146 rtmarkpos(PG_FUNCTION_ARGS)
147 {
148
IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0);149
RTreeScanOpaque p;
150
RTSTACK *o,
151
*n,
152
*tmp;
153
175
176
177
178
179 }

Clone 1’

freestack(p->s_markstk);
p->s_markstk = o;Clone 1

PG_RETURN_VOID();

Clone 1

Clone 1’

rtree/rtscan.crtree/rtscan.c

124 Datum
125 gistmarkpos(PG_FUNCTION_ARGS)
126 {
127
IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0);128
GISTScanOpaque p;
129
GISTSTACK *o,
130
*n,
131
*tmp;
132
154
155
156
157
158 }

pgsql/src/backend/access/gistfreestack(p->s_markstk);
p->s_markstk = o;Clone 1

Clone 1

Clone 1

Clone 1

gist/gistscan.c

gist/gistscan.c

2005/01/15

2005/01/22

157 Datum
158 rtmarkpos(PG_FUNCTION_ARGS)
159 {
160
IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0);161
RTreeScanOpaque p;
162
RTSTACK *o,
163
*n,
164
*tmp;
165
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203 }

freestack(p->s_markstk);
p->s_markstk = o;/* Update markbuf: make sure to bump ref count on curbuf */if (BufferIsValid(p->markbuf)){
ReleaseBuffer(p->markbuf);
p->markbuf = InvalidBuffer;}
if (BufferIsValid(p->curbuf)){
IncrBufferRefCount(p->curbuf);
p->markbuf = p->curbuf;}
PG_RETURN_VOID();

PG_RETURN_VOID();

図 5 過去にクローンペアであったコード片の例
Fig. 5 Example of code snippets used to be clone pair

図 5 に分岐クローンセットとなったクローン減少箇所の例を示す．2005 年 1 月 15 日の時点では 4 つら分類することで，クローンの性質を探求することを目的としている．

のコード片がクローンであった．一週間後，そのうち任意のコード片ではなく，関数を対象とする履歴の 2 つに編集が加えられ，それぞれ独立したクローン追跡手法もいくつか提案されている [11, 12]．Godfrey

セット Clone 1 と Clone 1’ になった．図 5 右側は新しら [11] は関数のペアを対象とした 5 つの評価基準をい Clone 1’ の抜粋である．このように Clone1’ は太字

定義している．これらは関数名の類似度，関数宣言部

で示した処理が追加されただけで，本質的には Clone1の類似度，LOC 等のメトリクスの類似度，呼び出し元

同様のことを行っており，これらのコード片の間にはや呼び出し先の類似度，および上記 4 つをユーザが組依然として強い類似性がある．本手法により過去の履

みあわせたものから構成され，ユーザが指定した計算歴を辿ることで，これらのコード片の関係を抽出する

尺度に基づいてバージョン間の関数同士の対応関係をことができる．

求めている．また Antoniol ら [13] は，クラス単位で6. 関 連 研 究
クローンの履歴を調査する研究としては，Kim らの研究 [10] が挙げられる．Kim らは我々の手法と同様に

CCFinder を用いてクローンの履歴抽出を試みており，
クローンセットの生存期間に着目して生存期間の分布がどのようになっているか，生存期間の違いによってクローンにどのような特徴があるかを調査している．

Kim らの研究では，履歴抽出の対象となっているのはの履歴追跡手法を提案している．
このほかの関連研究として版管理システムを利用して何らかの有益な情報を引きだそうとする研究が挙げられる．これまでに，版管理システムに存在する開発履歴から関連性の高い関数を提示する研究 [14, 15]や，バグ修正支援 [16]，行数の変化や開発者ごとの編集を行った行数などを図示する試み [17, 18] が行われている．

7. ま と め

クローンセットであり，個々のクローンについての詳細な履歴は対象としていない．それに対して本研究で本論文では，クローン履歴解析手法を提案した．まは一つ一つのクローンを単位とした履歴を抽出しておた PostgreSQL を対象に適用実験を行い，クローン履

り，より具象的な解析を行っている．また，本研究の歴関係を用いて，かつてクローンだったコード片が正

目的は分岐クローンセットの発見による要修正箇所のしく抽出できること，抽出したコード片は派生元の提示という開発者に焦点を当てたものであるのに対し

コード片と強い関連を持っていることを確認した．

て，Kim らの研究はクローンを生存期間という観点か

今後の課題としては，まず，より目的に沿った形で
7

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xxのクローン履歴情報閲覧システムの構築が挙げられる．
クローンの履歴は開発プロセス全体の把握やクローン発生源の特定，クローンの管理等さまざまな応用が考えられるが，抽出結果を活用するためには分析した結果を目的に沿う形で表示する必要がある．
また分析手法そのものについても評価，改善が必要

2004.

門田暁人，佐藤慎一，神谷年洋，松本健一，“コードクローンに基づくレガシーソフトウェアの品質の分析，” 情報処理学会論文誌，vol.44，no.8，pp.2178-2188，2003 年 8 月.
[8] CVS, http://www.cvshome.org/.
[9] Subversion, http://subversion.tigris.org/.
[10] M. Kim, and D. Notkin, “Using a clone genealogy extractor for[7]

understanding and supporting evolution of code clones,” Proc. 2ndである．クローンの履歴となりうるもののうち本手法

Intl. Workshop on Mining Software Repositories (MSR 2005),

で分析できる範囲，できない範囲を厳密に調査する必要がある．また既存の類似手法との結果比較も重要でpp.17-21, Saint Louis, Missouri, May 2005.
[11]

M.W. Godfrey, and L. Zou, “Using origin analysis to detect merging and splitting of source code entities,” IEEE Trans. Softwareあると考える．
現時点で判明している取得できないクローン履歴とEngineering, vol.31, no.2, pp.166-181, Feb 2005.
[12]

N. Gold, and A. Mohan, “A framework for understanding con-

しては，一度削除されたクローンが，その後の変更にceptual changes in evolving source code,” Proc. 19th Intl. Conf.

より復活した場合がある．前述したとおり全てのバー

on Software Maintenance (ICSM 2003), pp.22-26, Amsterdam,

ジョン間においてクローン履歴分析をするのは現実的

2003.
[13]

G. Antoniol, M.D. Penta, and E. Merlo, “An automatic approach

ではないため，たとえば削除されたクローンについて

to identify class evolution discontinuities,” Proc. 7th Int. Work-

も逐次記録していき，過去の削除されたクローンも差

shop on Principles of Software Evolution (IWPSE’04), pp.31-40,
Kyoto, Japan, Sep 2004.

分解析の対象として加えることが考えられる．しかし，この手法は削除されたクローン数によっては膨大な計[14]

version histories to guide software changes,” IEEE Trans. Soft-

算量を要するため，既存の開発パターンを調査して削除されたクローン数の推移傾向を調査したい．

ware Engineering, vol.31, no.6, pp.429-445, Jun 2005.
[15]

Engineering, vol.31, no.6, pp.446-465, Jun 2005.
[16]

文の一部は文部科学省「e-Society 基盤ソフトウェアの文[1]Trans. Software Engineering, vol.31, no.6, pp.466-480, Jun 2005.

Linguistic Token-based Code Clone Detection System for Large
Scale Source Code,” IEEE Trans. Software Engineering, vol.28,
no.7, pp.654-670, 2002.
[2]

[17]

S.G. Eick, T.L. Graves, A.F. Karr, A. Mockus, and P. Schuster,“Visualizing software changes,” IEEE Trans. Software Engineer-献T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder: A Multi-

C.C. Willams, and J.K. Hollingsworth, “Automatic mining ofsource code repositories to improve bug ﬁnding techniques,” IEEE総合開発」および日本学術振興会の科学研究費補助金
基盤研究 (A) （課題番号：17200001）の助成を得た．

D. Cubranic, G.C. Murphy, J. Singer, and K.S. Booth, “Hipikat: A
project memory for software development,” IEEE Trans. Software

謝辞 本研究において多大なご協力を頂いた産業技術総合研究所 神谷年洋氏に深く感謝する．また，本論

T. Zimmermann, P. Weissgerber, S. Diehl, and A. Zeller, “Mining

ing, vol.28, no.4, pp.396-412, Apr 2002.
[18]

C. Collberg, S. Kobourov, J. Nagra, J. Pitts, and K. Wampler,“A system for graph-based visualization of the evolution of software,” Proc. ACM symposium on Software visualization (SOFTVIS 2003), pp.77-86, San Diego, California, USA, Jun 2003.

（平成 xx 年 xx 月 xx 日受付）

E. Burd, and J. Bailey, “Evaluating clone detection tools for use
during preventative maintenance,” Proc. 2nd IEEE Int. Workshop
on Source Code Analysis and Manipulation (SCAM 2002), pp.3643, Montreal, Canada, Oct 2002.

[3]

B.S. Baker, “A program for identifying duplicated code,” Com-

[4]

Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “CP-Miner: A tool forputing Science and Statistics, vol.24, pp.49-57, 1992.
ﬁnding copy-paste and related bugs in operating system code.,”Proc. Sixth Symposium on Operating System Design and Implementation (OSDI’04), pp.289–302, 2004.
[5]

J.H. Johnson, “Identifying redundancy in source code using ﬁngerprints,” Proc. Centre for Advanced Studies on Collaborative

川口 真司
平 13 阪大・基礎工・情報卒．平 18 同大
大学院博士課程了．同年奈良先端大・情報・
情報システム・助手．博士 (情報科学)．ソ
フトウェアプロセス，ソフトウェア開発支援の研究に従事．情報処理学会会員．

research (CASCON’93), pp.171-183, Toronto, Ontario, Canada,
Oct 1993.
[6]

E. Merlo, G. Antoniol, M.D. Penta, and V.F. Rollo, “Linear complexity object-oriented similarity for clone detection and software
evolution analyses,” Proc. 20th IEEE Int. Conf. on Software Maintenance (ICSM’04), pp.412-416, Chicago, Illinois, USA, Sep

8

松下

誠

平 5 阪大・基礎工・情報卒．平 10 同大
大学院博士課程了．同年同大・基礎工・情論文／版管理システムを用いたクローン履歴分析手法の提案
報・助手．平 14 阪大・情報・コンピュータ
サイエンス・助手．平 17 阪大・情報・コン
ピュータサイエンス・助教授．博士 (工学)．
ソフトウェアプロセス，オープンソースソ
フトウェア開発の研究に従事．情報処理学会，日本ソフトウェ
ア科学会，ACM 各会員．

井上克郎 （正員）昭 54 阪大・基礎工・情報卒．昭 59 同大
大学院博士課程了．同年同大・基礎工・情報・助手．昭 59〜61 ハワイ大マノア校・情報工学科・助教授．平元阪大・基礎工・情報・講師．平 3 同学科・助教授．平 7 同学科・教授．平 14 阪大・情報・コンピュータ
サイエンス・教授．博士 (工学) ソフトウェア工学の研究に従事．
情報処理学会，日本ソフトウェア科学会，IEEE，ACM 各会員．

9

Abstract Since a code clone is one of the major problems for maintenance phase, several code clone detection methods have been proposed. We focus on another clone relation, branched clone set - clone sets used to be one clone set.
Such clone sets are also highly related. To retrieve branched clone sets, we propose a method retrieving histories of code
clones. We applied our method for PostgreSQL and evaluated whether we can get branched clone sets using code clone
histories.
Key words Code Clone, Revision, Software Repository