コードクローン履歴閲覧環境を用いたクローン評価の試み

Presentation on theme: "コードクローン履歴閲覧環境を用いたクローン評価の試み"— Presentation transcript:

1 コードクローン履歴閲覧環境を用いたクローン評価の試み
川口真司*　松下誠** 井上克郎**　飯田元* 　* 奈良先端科学技術大学院大学 ** 大阪大学 2006/11/27 第154回ソフトウェア工学研究会

2 コードクローンとは プログラム中に何度も類似した箇所が現れるコード片 主に、安易なコピー & ペーストによって生まれる
大規模ソフトウェアの保守において問題となっている ある一箇所のクローンにバグがあった場合，すべての類似箇所について同じ修正が必要かどうか，検討が必要 若干の修正が加わっていることが多く，網羅的に把握することが困難 2006/11/27 第154回ソフトウェア工学研究会

3 クローン抽出システム 文字列を利用するもの 依存関係グラフを利用するもの メトリクスを利用するもの
ソースコードの字句そのものから類似部を抽出 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 , Brisbane, Queensland, Australia, Nov 2000. 2006/11/27 第154回ソフトウェア工学研究会

4 問題点 検出されるクローンの数が膨大 すべてのクローンが一律に除去対象とは限らない 削除すべきクローンとそうでないものとの判別が必要
大規模ソフトウェアの場合に顕著 全体的な傾向からの考察はできても，改善行動に結びつけるのが困難 すべてのクローンが一律に除去対象とは限らない 削除すべきクローン 抽象化の手間を惜しんでコピー＆ペーストしたコード片 役割分担の関係上，変更が困難なコード片 削除すべきでない，削除しなくてもよいクローン 将来の変更を見越して，意図的に重複箇所としている デザインパターンやフレームワークを適用している箇所 削除すべきクローンとそうでないものとの判別が必要 2006/11/27 第154回ソフトウェア工学研究会

5 クローン評価に向けて クローンの中身を解析 クローンの発展過程，履歴を解析 クローンを含む関数，クラスについて解析
メトリクスの算出 依存関係の解析 開発者の意図までを把握するのは困難 クローンの発展過程，履歴を解析 クローンの過去を知ることで，関係した開発者やその意図を推し量ることはできないだろうか すぐ消されたクローンと，発生以来さまざまな部分にコピーされているクローンとでは明確な違いはあるのではないか クローンを作成した開発者によって，違いがあるのではないか 2006/11/27 第154回ソフトウェア工学研究会

6 クローン履歴・関係者の解析 クローンの発展過程，関係した開発者を解析する手法の提案
クローン履歴手法の紹介* クローン関係者解析手法 関係者: 作成者，編集者，削除者すべてを含んだ総称 得られた解析結果と，クローン評価との関連性に関する予備実験 変更種別（作成，編集，削除）回数がクローン関係者ごとに異なるかどうかの検証 単一コミットに含まれるクローンセット数と，クローン評価との関連の分析 　* 川口真司, 松下誠, 井上克郎: "版管理システムを用いたコードクローン履歴分析手法の提案", 電子情報通信学会論文誌 D, Vol.J89-D, No.10, pp , 2006 2006/11/27 第154回ソフトウェア工学研究会

7 クローンに関する諸定義 クローン クローンペア クローンセット クローン クローンペア クローンセット 類似文字列が存在するコード片
クローンの位置は (ファイル名，開始行番号，終了行番号) で表される クローンペア 互いに類似文字列であるクローンの対 クローンセット クローンペア関係において推移関係が成り立つ クローンの集合 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回ソフトウェア工学研究会

8 クローン履歴抽出手法 指定された期間 [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回ソフトウェア工学研究会

9 ・・・ クローン関係者 クローンの変更に何らかの形で関わった開発者 以下の3つの和集合 クローンを作成した開発者 クローンを編集した開発者
クローンを削除した開発者 削除: dean 作成: alex ・・・ F0 F1 編集: emily Ft-1 Ft 2006/11/27 第154回ソフトウェア工学研究会

10 関係者抽出手法 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: Another round of error message editing, covering backend/commands/. 2006/11/27 第154回ソフトウェア工学研究会

11 複数回のコミットがあった場合 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回ソフトウェア工学研究会

12 行番号の調整 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回ソフトウェア工学研究会

13 複数のコミットを考慮した解析手順 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回ソフトウェア工学研究会

14 クローン履歴の評価への応用 過去の履歴がクローン評価に利用可能かどうかを以下の2つの視点から検証する 分析対象
開発者によって，クローンとの関わり方に差があるかどうか ある一度のコミット時に編集したクローン数と，そこに含まれるクローンの品質との関連 分析対象 PostgreSQL のサブモジュール (src/backend/commands 以下のソースコード) 2003/01/01 ～ 2004/01/01 までを30日間隔で解析 2006/11/27 第154回ソフトウェア工学研究会

15 実験方法 実験1: 開発者とクローン変更回数 実験2: コミットに含まれるクローンセット数 開発者ごとのクローン変更回数を集計
ある時刻に，1つのクローンセットを変更していたら1回． ある時刻に，クローンセットを5個変更していたら，5回とカウント． 開発者によって，変更作業(作成，編集，削除)に差があるかどうかを 分析 クローンを追加してばかりの開発者がいないか 逆に，クローンの削除を多く行っている開発者はいないか 実験2: コミットに含まれるクローンセット数 同時に単一の開発者によって行われたコミットについて，そのとき編集したクローンセット数の分布を集計 （本実験では同時 = 1分以内とする） 含まれるクローンの傾向について分析 少数のクローンセットのみを編集しているコミット 大量のクローンセットを一度に編集しているコミット 2006/11/27 第154回ソフトウェア工学研究会

16 実験結果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回ソフトウェア工学研究会

17 実験結果2 – コミットから見た特性 62 大多数のコミットでは，そのとき編集されたクローンセットは一つ
クローンセットなのか． 中のクローン数こそが影響しているのではないか． いや，クローンセットであることによって，CCFinderでも似て非なると判定されたものが 統合できる可能性があるともいえる．（逆にいえばCCFinderが漏らしてるという言い方だけど） 62 大多数のコミットでは，そのとき編集されたクローンセットは一つ ただし，いくつかのコミットでは多数のクローンセットを一斉に編集している 2006/11/27 第154回ソフトウェア工学研究会

18 大量のクローンを編集したコミットの例 機械的な変換作業 クローンの発見が困難でなかったと考えられる このようなクローンは対処優先度が低い
< 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回ソフトウェア工学研究会

19 実験結果の考察 開発者に着目した分析 コミットに着目した分析 全体のコミット回数と比較して，クローン作成の多い開発者が見つかった
彼が作成したクローンのいくつかは他の開発者によって削除されていた 開発者によってクローンへのかかわり方は異なってくる コミットに着目した分析 コミット時に編集したクローンセット数の寡多から，着目しなくてもよいクローンセットが見つかった 膨大なクローン情報のスクリーニングに有用 2006/11/27 第154回ソフトウェア工学研究会

20 まとめと今後の課題 クローン履歴分析手法の紹介，およびクローン関係者抽出手法の提案 クローン評価のためのクローン履歴，関係者の分析
分析手法について 適正に開発者が漏れなく取得できているかどうかの評価 ブランチを考慮した分析 分析作業について 広範なデータ分析 PostgreSQL の他モジュールも含めた解析 他のソフトウェアを対象とした解析 実験結果のより精細な検証 その他，クローン評価に有用な仮説立案・検証 2006/11/27 第154回ソフトウェア工学研究会

21 2006/11/27 第154回ソフトウェア工学研究会

22 以下，予備役スライド 2006/11/27 第154回ソフトウェア工学研究会

23 クローン履歴・関係者の解析 クローンの発展過程を知るためには，最新時点のクローンの過去の状態を知る必要がある． クローン履歴手法の紹介*
ソースコードそのものは版管理システムにより入手可能 ただし，過去にあったクローンが現在も残っているか，残っているならばどこが該当部分かは自明ではない クローン履歴手法の紹介* クローン関係者解析手法 関係者: 作成者，編集者，削除者すべてを含んだ総称 実験・分析 　* 川口真司, 松下誠, 井上克郎: "版管理システムを用いたコードクローン履歴分析手法の提案", 電子情報通信学会論文誌 D, Vol.J89-D, No.10, pp , 2006 2006/11/27 第154回ソフトウェア工学研究会

24 クローン関係者抽出手法 入力 版管理システムが持つ情報 クローン履歴解析の結果 任意の時点のソースコード コミットの集合
変更日時 開発者 変更内容 クローン履歴解析の結果 各解析時点でのクローン 隣り合う解析時点間でのクローン履歴関係 こんなのいっぺんに文字で見せてもドンビキされるだけなので 　絵でやるか 　 （こういう部分だけからスタートしてることを意識しつつ）プロセスといっしょに説明するか 2006/11/27 第154回ソフトウェア工学研究会

25 関係者抽出手順 すべてのファイルの解析期間内に行われたコミットについて コミット日時と開発者を取得 (cvs log)
そのときに行われた作業内容を取得 (cvs diff) 各 diff エントリについて 変更を施した行にクローンがあれば そのクローンの前にクローン履歴がなければ「作成」 そのクローンについて，後ろクローン履歴がなければ「削除」 両方あれば，「編集」 2006/11/27 第154回ソフトウェア工学研究会

26 クローン評価に向けて クローンの中身に着目 クローンの属性に着目 ソースコードを静的/動的に解析 クラス，変数間の依存関係など
クローンの行数 クローンの開発過程（期間やファイル数など） クローンを作った，もしくは編集した開発者 2006/11/27 第154回ソフトウェア工学研究会

27 抽出手順 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回ソフトウェア工学研究会

28 行番号変換の適用方法 F1 F2 2006/11/27 第154回ソフトウェア工学研究会

29 複数回のコミットがあった場合 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回ソフトウェア工学研究会