コードクローン履歴閲覧環境を用いたクローン評価の試み 川口真司* 松下誠** 井上克郎** 飯田元* * 奈良先端科学技術大学院大学 ** 大阪大学 2006/11/27 第154回ソフトウェア工学研究会
コードクローンとは プログラム中に何度も類似した箇所が現れるコード片 主に、安易なコピー & ペーストによって生まれる 大規模ソフトウェアの保守において問題となっている ある一箇所のクローンにバグがあった場合,すべての類似箇所について同じ修正が必要かどうか,検討が必要 若干の修正が加わっていることが多く,網羅的に把握することが困難 2006/11/27 第154回ソフトウェア工学研究会
クローン抽出システム 文字列を利用するもの 依存関係グラフを利用するもの メトリクスを利用するもの ソースコードの字句そのものから類似部を抽出 CCFinder* など 依存関係グラフを利用するもの 各種単位間の依存関係グラフの形から Baxter らの手法**など メトリクスを利用するもの 関数,クラスなどの単位ごとにメトリクスを定義し,その値が類似したものを抽出 Balazinska らの手法***など これらの手法により,大規模なソフトウェアからクローンを自動的に検出することが可能になった * T. Kamiya, S. Kusumoto, and K. Inoue. Ccfinder: A multilinguistic token-based code clone detection system for large scale source code. IEEE Transactions on Software Engineering, 28(7):654–670, Jul 2002. ** I. Baxter, A. Yahin, L. Moura, M. Anna, and L. Bier. Clone detection using abstract syntax trees. In Proc. International Conference on Software Maintenance 98, pp. 368–377, Mar 1998. *** M. Balazinska, E. Merlo, M. Dagenais, B. Lague, and K. Kontogiannis. Advanced clone-analysis to support object-oriented system refactoring. In Proc. 7th Working Conf. on Reverse Engineering (WCRE 2000), pp. 98.107, Brisbane, Queensland, Australia, Nov 2000. 2006/11/27 第154回ソフトウェア工学研究会
問題点 検出されるクローンの数が膨大 すべてのクローンが一律に除去対象とは限らない 削除すべきクローンとそうでないものとの判別が必要 大規模ソフトウェアの場合に顕著 全体的な傾向からの考察はできても,改善行動に結びつけるのが困難 すべてのクローンが一律に除去対象とは限らない 削除すべきクローン 抽象化の手間を惜しんでコピー&ペーストしたコード片 役割分担の関係上,変更が困難なコード片 削除すべきでない,削除しなくてもよいクローン 将来の変更を見越して,意図的に重複箇所としている デザインパターンやフレームワークを適用している箇所 削除すべきクローンとそうでないものとの判別が必要 2006/11/27 第154回ソフトウェア工学研究会
クローン評価に向けて クローンの中身を解析 クローンの発展過程,履歴を解析 クローンを含む関数,クラスについて解析 メトリクスの算出 依存関係の解析 開発者の意図までを把握するのは困難 クローンの発展過程,履歴を解析 クローンの過去を知ることで,関係した開発者やその意図を推し量ることはできないだろうか すぐ消されたクローンと,発生以来さまざまな部分にコピーされているクローンとでは明確な違いはあるのではないか クローンを作成した開発者によって,違いがあるのではないか 2006/11/27 第154回ソフトウェア工学研究会
クローン履歴・関係者の解析 クローンの発展過程,関係した開発者を解析する手法の提案 クローン履歴手法の紹介* クローン関係者解析手法 関係者: 作成者,編集者,削除者すべてを含んだ総称 得られた解析結果と,クローン評価との関連性に関する予備実験 変更種別(作成,編集,削除)回数がクローン関係者ごとに異なるかどうかの検証 単一コミットに含まれるクローンセット数と,クローン評価との関連の分析 * 川口真司, 松下誠, 井上克郎: "版管理システムを用いたコードクローン履歴分析手法の提案", 電子情報通信学会論文誌 D, Vol.J89-D, No.10, pp.2279-2287, 2006 2006/11/27 第154回ソフトウェア工学研究会
クローンに関する諸定義 クローン クローンペア クローンセット クローン クローンペア クローンセット 類似文字列が存在するコード片 クローンの位置は (ファイル名,開始行番号,終了行番号) で表される クローンペア 互いに類似文字列であるクローンの対 クローンセット クローンペア関係において推移関係が成り立つ クローンの集合 Clone A-1 クローン Clone A-1 Clone A-3 Clone A-1 Clone A-3 クローンペア Clone A-2 Clone A-1 Clone A-3 Clone B-2 Clone B-1 Clone A-2 クローンセット 2006/11/27 第154回ソフトウェア工学研究会
クローン履歴抽出手法 指定された期間 [0, t]、間隔Δt について期間 [0, t] を Δt ごとに分割、それぞれの時間におけるファイル群を F0, F1, ..., Ft と表す 過去のプロダクトの取得には版管理システム (ex. cvs, subversion, ...) を用いる となりあうバージョン間について分析 F0 をリポジトリから取得,クローンを抽出 F1 をリポジトリから取得,クローン抽出 F0, F1 のクローンについて,クローン履歴関係を分析 … Ft をリポジトリから取得,クローン抽出 Ft-1, Ft のクローンについて,クローン履歴関係を分析 ・・・ F0 F1 Ft-1 Ft 2006/11/27 第154回ソフトウェア工学研究会
・・・ クローン関係者 クローンの変更に何らかの形で関わった開発者 以下の3つの和集合 クローンを作成した開発者 クローンを編集した開発者 クローンを削除した開発者 削除: dean 作成: alex ・・・ F0 F1 編集: emily Ft-1 Ft 2006/11/27 第154回ソフトウェア工学研究会
関係者抽出手法 ft-1 ft 版管理システムから得られる差分情報を用いて ft-1 に編集元領域に存在するクローン 編集元の領域 があれば,そのコミットのauthorが変更者とする 編集元の領域 編集操作 a: 挿入 d: 削除 c: 変更 編集先の領域 8a9,18 > > … 行番号 行番号 8 挿入 9 Clone A 15 Clone A 18 18 22 Clone A 24 8a9,18 > > … 31 29 34 Clone A … Clone A ft-1 ft Commit revision 1.82 date: 2003/07/20 21:56:32; author: tgl; state: Exp; lines: +51 -29 Another round of error message editing, covering backend/commands/. 2006/11/27 第154回ソフトウェア工学研究会
複数回のコミットがあった場合 ft-1 ft 実際の追加対象は100行下 8a9,18 > > … 5a5,105 > 行番号 行番号 行番号 実際の追加対象は100行下 5 8 挿入 9 Clone A 15 18 18 Clone A 105 22 Clone A 24 109 Clone A 31 29 118 34 Clone A Clone A 124 Clone A 8a9,18 > > … 5a5,105 > > … 129 134 5行目に100行挿入 Clone A … … ft-1 ft Commit1 Commit2 2006/11/27 第154回ソフトウェア工学研究会
行番号の調整 ft ft-1 ft ft-1 衝突時には対応行が一意でない 最小、最大の推定値を考慮 9 18 24 29 34 39 8 a:挿入 9 Clone A 15 15 18 18 18 d:削除 22 Clone A 24 22 31 29 31 c:変更 34 Clone A 36 Clone A ft-1 行番号 衝突時には対応行が一意でない 最小、最大の推定値を考慮 2006/11/27 第154回ソフトウェア工学研究会
複数のコミットを考慮した解析手順 ft-1 ft 8a9,18 > > … 8a9,18 > > … 8a9,18 行番号 5 行番号 8 105 109 15 Clone A 18 Clone A 118 22 124 Clone A 31 8a9,18 > > … 8a9,18 > > … 8a9,18 > > … 129 Clone A 134 Clone A … … … ft-1 ft Commit1 Commit2 Commit3 2006/11/27 第154回ソフトウェア工学研究会
クローン履歴の評価への応用 過去の履歴がクローン評価に利用可能かどうかを以下の2つの視点から検証する 分析対象 開発者によって,クローンとの関わり方に差があるかどうか ある一度のコミット時に編集したクローン数と,そこに含まれるクローンの品質との関連 分析対象 PostgreSQL のサブモジュール (src/backend/commands 以下のソースコード) 2003/01/01 ~ 2004/01/01 までを30日間隔で解析 2006/11/27 第154回ソフトウェア工学研究会
実験方法 実験1: 開発者とクローン変更回数 実験2: コミットに含まれるクローンセット数 開発者ごとのクローン変更回数を集計 ある時刻に,1つのクローンセットを変更していたら1回. ある時刻に,クローンセットを5個変更していたら,5回とカウント. 開発者によって,変更作業(作成,編集,削除)に差があるかどうかを 分析 クローンを追加してばかりの開発者がいないか 逆に,クローンの削除を多く行っている開発者はいないか 実験2: コミットに含まれるクローンセット数 同時に単一の開発者によって行われたコミットについて,そのとき編集したクローンセット数の分布を集計 (本実験では同時 = 1分以内とする) 含まれるクローンの傾向について分析 少数のクローンセットのみを編集しているコミット 大量のクローンセットを一度に編集しているコミット 2006/11/27 第154回ソフトウェア工学研究会
実験結果1 – 開発者ごとの特性 対象サブモジュールに関係した開発者は10人 解析期間中にクローンの変更に関わっていたのは3人 全コミット数に対して, クローン追加が多い momjian petere tgl クローン追加 6 10 32 クローン削除 2 3 17 クローン編集 35 27 135 (小計) 43 40 184 総コミット数 1317 143 1428 2006/11/27 第154回ソフトウェア工学研究会
実験結果2 – コミットから見た特性 62 大多数のコミットでは,そのとき編集されたクローンセットは一つ クローンセットなのか. 中のクローン数こそが影響しているのではないか. いや,クローンセットであることによって,CCFinderでも似て非なると判定されたものが 統合できる可能性があるともいえる.(逆にいえばCCFinderが漏らしてるという言い方だけど) 62 大多数のコミットでは,そのとき編集されたクローンセットは一つ ただし,いくつかのコミットでは多数のクローンセットを一斉に編集している 2006/11/27 第154回ソフトウェア工学研究会
大量のクローンを編集したコミットの例 機械的な変換作業 クローンの発見が困難でなかったと考えられる このようなクローンは対処優先度が低い < elog(WARNING, "DefineAggregate: attribute \"%s\" not recognized", < defel->defname); --- > ereport(WARNING, > (errcode(ERRCODE_SYNTAX_ERROR), > errmsg("aggregate attribute \"%s\" not recognized", > defel->defname))); “Another round of error message editing, covering backend/commands/.” 機械的な変換作業 エラーメッセージ出力部の一括変換 クローンの発見が困難でなかったと考えられる grep 等を利用した文字列検索可能なクローン このようなクローンは対処優先度が低い 機械的に処理をすべき対象を同定可能 保守工程において障害とならない 2006/11/27 第154回ソフトウェア工学研究会
実験結果の考察 開発者に着目した分析 コミットに着目した分析 全体のコミット回数と比較して,クローン作成の多い開発者が見つかった 彼が作成したクローンのいくつかは他の開発者によって削除されていた 開発者によってクローンへのかかわり方は異なってくる コミットに着目した分析 コミット時に編集したクローンセット数の寡多から,着目しなくてもよいクローンセットが見つかった 膨大なクローン情報のスクリーニングに有用 2006/11/27 第154回ソフトウェア工学研究会
まとめと今後の課題 クローン履歴分析手法の紹介,およびクローン関係者抽出手法の提案 クローン評価のためのクローン履歴,関係者の分析 分析手法について 適正に開発者が漏れなく取得できているかどうかの評価 ブランチを考慮した分析 分析作業について 広範なデータ分析 PostgreSQL の他モジュールも含めた解析 他のソフトウェアを対象とした解析 実験結果のより精細な検証 その他,クローン評価に有用な仮説立案・検証 2006/11/27 第154回ソフトウェア工学研究会
2006/11/27 第154回ソフトウェア工学研究会
以下,予備役スライド 2006/11/27 第154回ソフトウェア工学研究会
クローン履歴・関係者の解析 クローンの発展過程を知るためには,最新時点のクローンの過去の状態を知る必要がある. クローン履歴手法の紹介* ソースコードそのものは版管理システムにより入手可能 ただし,過去にあったクローンが現在も残っているか,残っているならばどこが該当部分かは自明ではない クローン履歴手法の紹介* クローン関係者解析手法 関係者: 作成者,編集者,削除者すべてを含んだ総称 実験・分析 * 川口真司, 松下誠, 井上克郎: "版管理システムを用いたコードクローン履歴分析手法の提案", 電子情報通信学会論文誌 D, Vol.J89-D, No.10, pp.2279-2287, 2006 2006/11/27 第154回ソフトウェア工学研究会
クローン関係者抽出手法 入力 版管理システムが持つ情報 クローン履歴解析の結果 任意の時点のソースコード コミットの集合 変更日時 開発者 変更内容 クローン履歴解析の結果 各解析時点でのクローン 隣り合う解析時点間でのクローン履歴関係 こんなのいっぺんに文字で見せてもドンビキされるだけなので 絵でやるか (こういう部分だけからスタートしてることを意識しつつ)プロセスといっしょに説明するか 2006/11/27 第154回ソフトウェア工学研究会
関係者抽出手順 すべてのファイルの解析期間内に行われたコミットについて コミット日時と開発者を取得 (cvs log) そのときに行われた作業内容を取得 (cvs diff) 各 diff エントリについて 変更を施した行にクローンがあれば そのクローンの前にクローン履歴がなければ「作成」 そのクローンについて,後ろクローン履歴がなければ「削除」 両方あれば,「編集」 2006/11/27 第154回ソフトウェア工学研究会
クローン評価に向けて クローンの中身に着目 クローンの属性に着目 ソースコードを静的/動的に解析 クラス,変数間の依存関係など クローンの行数 クローンの開発過程(期間やファイル数など) クローンを作った,もしくは編集した開発者 2006/11/27 第154回ソフトウェア工学研究会
抽出手順 Clone A Clone A Clone A Clone A Clone A 挿入 2006/11/27 ファイル1 ファイル1 挿入 Clone A Clone A Clone A ファイル2 ファイル2 Clone A Clone A 2006/11/27 第154回ソフトウェア工学研究会
行番号変換の適用方法 F1 F2 2006/11/27 第154回ソフトウェア工学研究会
複数回のコミットがあった場合 8a9,18 > > … 15,18d24 < < … 22c31 -- f0 f1 行番号 行番号 行番号 8 挿入 8a9,18 > > … 15,18d24 < < … 22c31 -- 9 9 Clone A Clone A Clone A 15 18 18 18 24 22 24 Clone A 29 31 29 34 34 Clone A Clone A Clone A f0 f1 f2 2006/11/27 第154回ソフトウェア工学研究会