コードクローン履歴閲覧環境を用いたクローン評価の試み
川口 真司 †松下 誠 ‡井上 克郎 ‡飯田元 †† 奈良先端科学技術大学院大学情報科学研究科‡ 大阪大学大学院情報科学研究科

ソフトウェアの保守工程における大きな問題の一つとしてクローンが指摘されており，これまでに様々なクローン検出手法が提案されている．しかし，ソフトウェアが大規模になるほど検出されるクローンも膨大なものとなるため，どのクローンが対処が必要なのかについての判断の支援が求められている．本研究では，そのような支援の一環としてクローンの作成，編集に関わった開発者に着目する．そのために版管理システムが保持している過去の履歴情報を解析する．また解析手法を PostgreSQL に対して適用し，得られた情報を対処が必要かどうかの判定に用いることができるか分析を行った．

Evaluation of Code Clone Using Clone History Browser

Shinji Kawaguchi†

Makoto Matsushita‡

Katsuro Inoue‡

Hajimu Iida††Graduate School of Information Science and Technology, Nara Institute of Science and Technology‡Graduate School of Information Science and Technology, Osaka University

Code clones are serious problem in software maintenance process. To solve this problem, many code clone detection methods are proposed however, not only showing clones, but also supporting to decide which clones aredeleted. Therefore, we present the analysis to detect developers who edit each clone. We apply the method toPostgreSQL and analyze the relationship between clone triage and developers who write or touch the clone.

-1-1

はじめにる，クローン関係者抽出手法を提案する．本手法

保守工程におけるさまざまな問題のなかでも非を用いることで，開発者の能力を加味したクロー

常に大きな問題の一つとして，ソースコード中にンの評価や，例えばクローンを最も多く作成して含まれる重複コード (以下，クローン) が挙げられいるのは誰か，といった開発者の評価の指針になる [4]．

りうる情報の提供が可能になる．

これまでにクローンを検出するための様々な手そして，クローン履歴や提案する手法によって法が提案されており，そのいくつかは実際に利用抽出されたクローンを作成，編集した開発者やそ可能なシステムとして実用化されている．さらに，の履歴がクローンの品質にどのような影響がある発見されたクローンを効率的に閲覧，除去するたかについての分析を行う．そのために PostgreSQLめのシステムも提案されている．これらのシステに対して提案手法を適用し，その結果から開発者ムを用いることによってソフトウェアに含まれてや変更履歴とクローンの性質との関係について議いるコードクローンを調査，除去するための労力論する．

が大幅に軽減される．

2 前提とするシステム

しかし，これらのクローン摘出ツールによる様々

2.1 クローン分析システム

な適用実験の結果，大規模なソフトウェアにはそクローン分析手法には大きくわけてソースコーれだけ大量のクローンが含まれていること，それドの字句解析に基づく手法 [1,4,6] と，特徴メトリら大量のクローン全てが必ずしも削除するべきククスに基づく手法 [3,7] に分けられる．ソースコーローンでないことがわかってきた．ある種のイディドの字句解析に基づく手法 では，ソースコード中オム的な一連のコードの流れや，デザインパターで同一の文字列を検索することでクローンの検出ンを構成するコード片などはその一例と言える．

を行う．特徴メトリクスに基づく手法では，例えそのため，得られたクローン情報をソフトウェ

ばクラスや関数，ファイルのようなプログラム中アの品質改善に結びつけるには，どのクローンがのある種の単位ごとに特徴メトリクスを定義・算優先的に対処すべきかを提示する必要がある．

出し，それらのメトリクス値が類似したものをク本研究では，クローンが優先して対処されるべローンとして抽出する手法である．一般には字句きかどうかを評価するために，そのクローンの履解析に基づく手法のほうがコストが増えるが，よ歴と過去にクローンの作成や編集に関わった開発り細粒度なクローンを抽出できる．

者に着目する．例えば，熟練した開発者であれば

本 研 究 で は ，字 句 解 析 ベ ー ス の 検 出 ツ ー ル

不用意にコピー&ペーストをすることは少なく，重CCFinder [4] を利用してクローン履歴の分析を行う．CCFinder は高いスケーラビリティを有しており，大規模なソフトウェアに対しても実用的な時複した部分も何らかの意図があって残していると考えられる．また，そのような開発者が作成したクローンならば残すべき価値が高いクローンの可間でクローンの抽出を行える．また，実際にさま能性が高い．逆に未熟な開発者が作成したクローざまな大規模ソフトウェアへ適用され，その有用ンにはそのような必然性がなく，何らかの対応が性が確認されている [8]．

必要であるという予測が成り立つ．

クローン分析を行う際，CCFinder は空白や改行，このような情報を分析するためには，ソースコーコメント等を除去するとともに，入力テキスト中ドをいつ誰がどのように編集したかという詳細なの変数名や関数名等を同一記号に縮退させる．そ

履歴情報が必要となる．従来であればこのようなの後に，しきい値以上の長さの共通字句列を探索

情報を網羅的に蓄積することは非常に困難であっし，全ての対のリストを出力する．コピー& ペー

たが，近年の版管理システムの普及により自動的ストによってクローンが作られた場合，変数名なにこれらの情報を収集することが可能となった．

どが変更されないことは稀であり，何らかの形でそこで，本研究では版管理システムが保持する変数名などがコピー先のコンテキストに合致する情報から各クローンを編集したのが誰かを特定すよう書きかえられることが多い．CCFinder では変-2-

Clone A-3
Clone A-3



Clone A-1

Clone A-1

Clone B-1

Clone B-1

Clone A-3

Clone A-3

Clone A-1
Clone B-1

Clone A-4

Clone A-4, A-5
Clone A-4, A-5



Clone A-2
Clone B-2
Clone B-3

Clone B-5
Clone B-4

Clone A-2

Clone B-2

Clone B’-1

Clone B’-3

Clone B-3, B-4, B-5
Clone B-3, B-4, B-5

Clone A-2

Clone B’-2

Clone B-2

Clone B’-3          

Clone B’-2

Clone A-5

Clone B’-1

Clone B’-3
Clone B’-3



図 1: クローンの変更履歴
数名，関数名を同一記号とみなすことによって適法を 3.3 節にて述べる．
切にコピーを検出できる．また，長大な共通字句

3.1 諸定義列が存在したときに，その部分字句列が併せて出

本解析手法では時間と共に変更されるソースコー力されるのを防ぐために，それぞれ互いに包含関ドを ∆t ごとに区切って考える (図 2)．分析の対象係でないもののみをクローンとして出力する．

を版管理システムの管理下にあるソースコードファ

2.2

版管理システム

イルの集合とし，ある時刻 t における集合を プロ
ダクト (Product) Ft と呼ぶ．

版管理システムとは CVS [2] や Subversion [9]のようにプロダクトの保管・管理に用いられるシ

いま，各ファイルを文字列と考え，その連続すステムである．過去のクローンの状態を知るためる部分列をコード片 (Code snippet) と呼ぶ．そしには，何らかの方法で過去の時点でのクローンをて，Ft に含まれるコード片のうち，共通字句列と知る必要があるが，版管理システムが普及する以なるコード片の対 (a, b) を Ft に関するクローンペ

前は過去のソースコードを取得する標準的な方法

ア (Clone pair)，a や b をそれぞれ Ft に関する クは存在しなかった．版管理システムでは，管理下ローン (Clone) と呼ぶ．このとき a と b はクローのプロダクトを任意の時点の状態に復元して取得

ン関係 (Clone relationship) にあるという．また，する機能が提供されている．

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

版管理システムには様々な実装が存在するが，ほとんどの版管理システムはプロダクトそのものだ

3.2 クローン履歴分析

けでなく，「いつ」「だれが」「どの部分」を編集し我々はこれまでに過去のクローンから新しい時たかを逐一保存している．これらの情報を抽出し，点のクローンへの対応関係をクローン履歴関係とCCFinder を用いて得られるクローン情報と突きあわせることで，それぞれのクローンを作成した開定義し，その抽出を行う手法を提案している [11]．

発者を特定することができる．なお，本稿では版

このような履歴関係を用いることで，例えば図1 のように当初二つのクローンセット A, B が 3 つ

管理システムとして CVS を用いるものとする．のクローンセット A, B, B’ に変化しているとき，3

クローン関係者分析手法

このような関係をたどることで，A-3 は過去の時

本節では，クローンの作成や削除，途中の編集

点では A-1，A-2 からコピーされたことや，B’-1,などに関わった開発者を分析するクローン関係者
分析手法について述べる．まず，3.1 節にてクロー

B’-2, B’-3 は元々 B-1, B-2 のコピーだったものが編集された結果，別々のクローンセットとなってンに関する単語の定義を行い，次に 3.2 節にて，過いることなどがわかる．

去に筆者らが提案したクローン履歴分析手法につこの手法では，指定された解析開始時間 tbegin ，いて述べる．それらを踏まえてクローン関係者手

解析終了時間 tlast で定義される期間を与えられた-3-Code snippet

Insertcp: Clone pair
H: Clone history relationship
File
Delete

F0

Ft-1

Ft

∆t

F:Product (Collection of files)

図 2: クローンとクローン履歴関係
解析間隔 ∆t で区切る．そして，それぞれの時刻された) が成りたつ．そこで，これら全てのケースt において CCFinder を用いてクローンを抽出し，t − 1 に存在するクローンが t のクローンのどれに対応するかを解析を行う (図 2)．

をコード片 a の子とする．このように複数の子が3.2.1 行番号対応関係

3 Case 3)• 開始行の一行前に挿入生成されるケースは以下の 3 つである．

• 開始行，終了行が編集されている箇所を含む (図差分情報の解析にあたり，時刻 t より ∆t だけ像を定義している．本写像はクローン履歴分析だ• 終了行に挿入
本研究においては Ft−1 → Ft への写像のみを扱うため，削除操作ではこのような複数候補を考えけでなく，後述のクローン関係者抽出手法でも利る必要はない．

過去の時点におけるプロダクト Ft−1 に含まれるコード片に対して，Ft に含まれるコード片への写以上述べた 3 つの編集操作による影響をすべて用しているため，その概要についてここで述べる．

足しあわせて写像先を決定する．

もし a よりも前の部分に変更箇所があれば，その内容に応じて写像先 b の開始行，終了行を調整

3.3 クローン関係者抽出手法する．図 3 の Case 1 はコード片 a の前で編集操作

3.3.1 概要が行われた場合の例である．このとき，a の前で本手法では，CVS によって得られるログ情報と，行われた編集操作の全てを勘案して a の写像先 b各リビジョンにて何行目が編集されたかという情の開始行，終了行は a のそれのそれぞれ 4 行後ろ報を元にクローン関係者の同定を行う．とする．また a に含まれる部分に変更が加えられまず解析対象の各ファイルについてログ情報をていた場合には，その内容に応じて b の終了行を取得する．ログ情報からは「リビジョンの一覧」調整する．図 3 の Case 2 では a 内に 2 行新しい行と，各リビジョンごとの「リビジョン番号」「編集が追加されているため，b の終了行は a のそれに日時」「編集を行った開発者」「コミットログ」が対して 2 行追加した値とする．

得られる．

最後に，クローン片の端の部分で書きかえ操作

次に，コミットログによって得られたリビジョが発生した場合について述べる．図 3 の Case 3 でンの集合に対して，各リビジョン間においてどのはコード片 a の開始行を跨がる形で書きかえされような編集操作が行われたかを逐次的に取得する．ている．このような場合，「コード片 a の上に 2 行

この編集操作の中に，編集日時に存在するクロー挿入があった」という解釈と，「コード片 a に 2 行ンを編集しているものがあれば，「編集を行った開の挿入がされた」という解釈，およびその中間 (1発者」をそのクローンの編集者とする．差分から行がコード片の上に，1 行はコード片 a 中に挿入編集されたクローンを特定する方法については次-4-Case 1t-1

Case 2t

Case 3t-1

t-1t
insert 2 lines

ainsert 6 linesadelete 2 lines
move 4 lines underba

increase 2 lines

treplace
4 lineswith
6 linesb’’
b b’
All b, b’, b’’
are children of a.

b図 3: コード片の写像
節で詳述する．

ソフトウェア名
解析対象モジュール
解析期間
解析対象の行数

上記の手続きをくりかえして，クローンが編集されたそれぞれの時点において，どの開発者がそれを行ったかを特定する．

PostgreSQL
pgsql/src/backend/commands
2003/01/01 〜 2004/01/01
32092 行 (2004/01/01 時点)

表 1: 実験対象の詳細

3.3.2 差分からのクローン特定

4 実験

リビジョン間の編集情報は「編集が行われた領4.1 実験の概要域」と「編集内容」の繰り返しとなっている．このうち，クローン特定に用いる「編集が行われた

ここでは著名なオープンソースソフトウェアの領域」の情報は次の 3 つの情報から構成される．

一つである PostgreSQL の一部ソースコードに対(1) 編集元の領域．編集元が何行目から何行目か．
(2) 編集操作．追加，削除，編集の 3 種類．

して本手法を適用し，そこから得られる情報とク(3) 編集先の領域．編集先が何行目から何行目か．
これらの情報から，そのコミットにおいて開発する．解析対象の詳細は表 1 に示す．

ローンの対処優先度についての関係について考察
本実験では，クローン履歴分析およびクローン者がどの部分を編集したかがわかる．それらの領関係者分析を PostgreSQL に対して適用し，各開発域の中にクローンが存在した場合，そのクローン者がクローンの編集を行った回数などを計測するはこの編集によって何らかの変更をされているとことで，それらの計測値とクローンの性質の間に考えられる．そこで，Ft−1 に含まれるクローンのどのような関係があるかを調査した．

うち，編集元の領域に存在するクローン，および実験は (1) 各開発者ごとにクローンの増減回数

Ft に含まれるクローンのうち編集先の領域に存在に差が見られるか，(2) 大規模な変更に含まれるクするクローンについて，その時点でのクローンのローンと小規模な変更に含まれるクローンの性質に編集者をコミットを行った開発者とする．

差があるか，という 2 つの視点から分析を行った．

ただし，行番号は t−1, t 間で行なわれた他の編集開発者ごとのクローン変更回数は，あるコミッ内容による影響を受ける．例えば，時間 t−1 と t のトであるクローンセットに対して何らかの変更を000施していた場合を 1 回とする．つまり 1 回のコミッ間に 2 つのコミットがあり，それぞれ t , t にコミッ
000

トされている場合を考える (t − 1 < t < t < t)．

トで 3 つのクローンセットを同時に変更していた

このとき，Ft−1 と Ft0 ではファイルの状態が異な場合には 3 回の変更をした，とカウントされる．

る．そのため，t00 における解析では Ft−1 での行番

また，クローンセットに対する変更を以下の 3 つ号をそのまま用いることはできない．そこで，3.2に分類する．

0

クローンの追加クローンセットに新しいクローン節で述べた行番号対応関係分析手法を t で行なわが追加されている．

れた編集内容に対して適用し，行番号の対応付け

クローンの削除クローンセット内のクローンが減を行う．

少している，もしくはクローンセット全体が削除されている．

-5-

momjian petere tgl
6103223173527135
4340184

表 2: 開発者ごとのクローン変更回数
tgl
1428 (42.4%)
momjian 1317 (39.1%)
petere143 (4.2%)
scrappy143 (4.2%)
vadim
121 (3.6%)
その他
214 (6.3%)

  

図 4: コミットによって変更されたクローンセット
数の度数分布図
ミットが 21 回，2 つのクローンセットを編集して

表 3: 解析対象における開発者ごとのコミット回数
クローンの編集クローンの中身が編集されている．

いるコミットが 13 回あったことを示している．
このグラフから，ほとんどのコミットは単一のクローンセット内のクローン数に変化はない．

クローンセットを編集しているが，いくつかのコなお，追加，削除時に同時に編集が行われていミットでは非常に多数のクローンセットを編集した場合でも，それぞれクローンの追加，クローンていることがわかる．この中でも多数のクローンの削除が行われたものとする．

4.2

  

クローン追加クローン削除クローン編集(合計)

セットを編集している上位 5 つのコミットログを実験結果

表 4 に示す．これらのログからもわかるとおりそ4.2.1 開発者ごとのクローン追加，削除回数のの編集内容はエラーメッセージ出力方法の統一な比較

ど機械的に変更可能な箇所となっている．実際に編集内容を確認した限りでは，変更の際には文字コミット時のクローン操作内容を開発者ごとに列検索などを利用して機械的に変更箇所を把握し集計したものを表 2 に示す．

たものと推測される．

最もクローンの変更回数が多いのは tgl であるが，tgl は作業量が多いために，それだけクローン逆に言えば，このようなクローンセットは必要にに関わる回数も多くなっている．また，実際には応じて機会的に網羅することが容易であり，そのコミッタではない開発協力者が書いたソースコーまま残しておいても保守の障害とはならない，すドを tgl が責任者としてコミットしていることも，なわちクローン削除の優先度が低いクローンセッ

tgl の編集回数が多い一因となっている．解析対象

トであると言える．

における各開発者のコミット回数を表 3 に示す．

5 考察

表 3 のコミット回数を考慮すると，petere のク

本実験では，PostgreSQL の一部モジュールを対ローン追加の比率は他の開発者のそれに比べると象として，各開発者ごとにクローンの追加や削除高いことがわかる．実際に petere による機能追加に関して特徴的な挙動を抽出できるかどうかを試にはコピー & ペーストが多く，petere が作成したみた．その結果，ある開発者についてクローン追加

クローンについては注意を払う必要がある可能性の比率が高いことが判明した．実験対象のモジューがある．

ルについてクローンの編集を行っている開発者が4.2.2 コミットごとのクローンセット数の分析

当初の予想より少ない 3 人のみだったため，この次に，一度のコミットにおいて編集されたクロー事象のみを持って断定的な主張を展開することはンセット数に着目し，その分布について調査を行っ難しいが，開発者によってクローンに対する意識た．図 4 はクローンセット数によるヒストグラムが異なる可能性は高い．

である．X 軸はコミットによって変更したクロー

次に，コミットに含まれるクローンセット変更ンセット数，Y 軸はその頻度を表している．つま数に着目した結果，多数のクローンセットが単一り，1 つのクローンセットのみを編集しているコのコミットで編集されている場合には，それらの-6-編集クローンセット数
6227262523

コミットログ
Another round of error message editing, covering backend/commands/.
First bits of work on error message editing.
Adjust ’permission denied’ messages to be more useful and consistent.
pgindent run.
Message editing: remove gratuitous variations in message wording, standard-ize terms, add some clariﬁcations, ﬁx some untranslatable attempts at dynamic
message building.
表 4: 編集クローンセット数上位 5 件のコミットログ
クローンは自動的に網羅可能であり，ソフトウェを削除すべきか否かをを判定する指標として活用
ア保守工程においてもコスト増大要因としての性できるかを検討するための分析を行った．

格は薄いと考えられる．

今後の課題として，今回の分析で得られた知見

ただし，そのような変更がクローンセットの極を検証するためのより広汎な分析が挙げられる．特一部でのみ行われており，その他の部分は依然とに開発者に関する分析では関わっている開発者はして，網羅することが難しい部分である可能性も3 人のみであった．これは調査対象を一部モジュールに限定しすぎたことが原因であり，より多くのソースコードに対して分析が必要である．

否定できない．今後は，そのような部分についてもより踏みこんだ分析を行っていきたい．

6

また，版管理システムの多くはブランチと呼ば関連研究れる機能を持っている．これはプロダクトの状態

クローンの履歴を調査する研究としては，Kimをいくつか並列に持てるようにする機能であるが，らの研究 [5] が挙げられる．Kim らは我々の手法

提案手法ではブランチを考慮していない．そのたと同様に CCFinder を用いてクローンの履歴抽出をめ，ブランチ上で行われた編集作業は全く考慮さ試みており，クローンセットの生存期間に着目しれていない．大規模なオープンソースソフトウェて生存期間の分布がどのようになっているか，生アではブランチを利用している開発グループも多存期間の違いによってクローンにどのような特徴く，提案手法でもブランチを考慮した分析を行えがあるかを調査している．Kim らの研究では，履るよう拡張を考慮していきたい．

歴抽出の対象となっているのはクローンセットであり，個々のクローンについての詳細な履歴は対参考文献

象としていない．それに対して本研究では一つ一[1] Baker, B. S.: A Program for Identifying Dupli-

つのクローンを単位とした履歴を抽出することでcated Code, Computing Science and Statistics,
Vol. 24, pp. 49–57 (1992).

より細粒度な解析をすることで，開発者などの情報を取りこむことを可能にしている．

[2] CVS: . http://www.cvshome.org/.

また，吉田ら [10] は Java ソースコードを対象として，クローンが存在するクラスに着目したク[3] Johnson, J. H.: Identifying redundancy insource code using ﬁngerprints, Proc. Centre

ローンメトリクスを定義し，それらの値からリファクタリングを支援する手法を提案している．このようなファイルの内容を解析した情報の活用もまfor Advanced Studies on Collaborative research(CASCON’93), Toronto, Ontario, Canada, pp.

た重要であると考えられる．

171–183 (1993).

7まとめ[4] Kamiya, T., Kusumoto, S. and Inoue, K.:
CCFinder: A Multi-Linguistic Token-based

本研究では，版管理システムが保持する履歴情報とクローン履歴情報に基づいて，クローン編集者情報を自動的に抽出する手法を提案した．また，

Code Clone Detection System for Large Scale
Source Code, IEEE Trans. Software Engineer-

クローン関係者やクローン履歴を用いてクローン

ing, Vol. 28, No. 7, pp. 654–670 (2002).

-7-

[5] Kim, M., Sazawai, V., Notkin, D. and Murphy,
G. C.: An Empirical Study of Code Clone Genealogies, Proc. 10th European Software Engineering Conf. and 13th Foundations of Software
Engineering (ESEC/FSE 2005), Lisbon, Portugal, pp. 17–21 (2005).
[6] Li, Z., Lu, S., Myagmar, S. and Zhou, Y.: CPMiner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code., Proc.
Sixth Symposium on Operating System Designand Implementation (OSDI’04), pp. 289–302(2004).
[7] Merlo, E., Antoniol, G., Penta, M. D. and Rollo,
V. F.: Linear Complexity Object-Oriented Similarity for Clone Detection and Software Evolution Analyses, Proc. 20th IEEE Int. Conf.
on Software Maintenance (ICSM’04), Chicago,
Illinois, USA, pp. 412–416 (2004).
[8] 門田暁人, 佐藤慎一, 神谷年洋, 松本健一: コー
ドクローンに基づくレガシーソフトウェアの品質の分析, 情報処理学会論文誌, Vol. 44,

No. 8, pp. 2178–2188 (2003 年 8 月).
[9] Subversion: .
tigris.org/.

http://subversion.

[10] Yoshida, N., Higo, Y., Kamiya, T., Kusumoto,S. and Inoue, K.: On Refactoring Support Basedon Code Clone Dependency Relation, Proc.
11th IEEE Int. Software Metrics Symposium(METRICS2005), Como, Italy, p. 16 (2005).
[11] 川口真司, 松下誠, 井上克郎: 版管理システムを用いたコードクローン履歴分析手法の提案,
電子情報通信学会論文誌 D, Vol. J89-D, No. 10,
pp. 2279–2287 (2006).

-8-