ソースコードの差分を用いた関数呼び出し パターンの抽出手法の提案 中山 崇，松下 誠，井上 克郎 大阪大学大学院情報科学研究科

ソフトウェア部品の利用法 ソフトウェア部品を再利用することは非常に重要である 再利用によって生産性や品質が向上するから ソフトウェア部品を再利用するには、まずその部品の利用法を理解しなければならない 部品の初期化の仕方や、実現したい処理に必要な関数群の呼び出し順など 一般に、部品の利用法理解には付属するドキュメントなどを利用する ドキュメントなどが付属していない部品では利用法の学習が困難であった 2006/03/23 第151回ソフトウェア工学研究会

関数呼び出しパターンによる利用法の理解 関数呼び出しパターンと呼ばれるものを抽出することで、部品の利用法理解を支援する研究が過去になされている ソースコード中に頻繁に出現する関数の利用関係を関数呼び出しパターンとしている … File *file = fopen(path,”w”); if(file != null){ fprintf(file,string); } fclose(file); ファイルへの書き込 みはどのようにした ら良いのだろう？ fopen(); if(){ fprintf(); } fclose(); これらの関数を 使えばいいのか！ 具体的な使い方はパターンを 実現したコードから学べるな 2006/03/23 第151回ソフトウェア工学研究会

計算部を再利用したいが、write_resultも関係あるの？ 既存のパターン抽出手法とその問題点 複数の機能が1つのまとまりとして認識されてしまうという問題点を持つ 既存手法が以下の特徴を持つため 同時に現れる関数は同じ機能を実装するものとみなす 計算部を再利用したいが、write_resultも関係あるの？ … calculate1(); calculate2(); open_file(); write_result(); close_file(); … calculate1(); calculate2(); open_file(); write_result(); close_file(); 計算処理部 calculate1(); calculate2(); open_file(); write_result(); close_file(); データ 書き出し部 個別の機能に限定した関数呼び出しパターンが必要 2006/03/23 第151回ソフトウェア工学研究会

研究の目的 既存手法の問題点を解決するために、個別の機能に限定した関数呼び出しパターンを抽出し、部品利用法の理解に役立てる 版管理システム内のソースコードの差分から個別の機能に限定した関数呼び出しパターンを抽出する手法を提案 手法に基づいた関数呼び出しパターン抽出システムの構築 利用法学習を支援するために、パターンとそれを利用しているソースコードを閲覧できるパターンブラウザの構築 2006/03/23 第151回ソフトウェア工学研究会

版管理システム 版管理システム 版管理システムへの変更の保存は一般に個別の機能毎に行われる[1][2] プロダクトの開発履歴を保存・提供するシステム 開発者はソースコードの変更を版管理システムに保存しながら開発作業を進める 変更内容は差分（diffの出力）として保存される 版管理システムへの変更の保存は一般に個別の機能毎に行われる[1][2] チェックアウト 版管理 システム 編集 開発者 コミット ソースコード コミットは個別の 機能毎に行われる [1] H.. Gall, M. Jazayeri, and J. Krajewski: CVS Release History Data for Detecting Logical Couplings In Proceedings of the 6th International Workshop on Principles of Software Evolution, Washington, DC, USA, 2003 [2] T. Zimmermann, P. Weisgerber, S. Diehl, and A. Zeller: Mining Version Histories to Guide Software Changes In Proceedings of the 26th International Conference on Software Engineering, Washington, DC, USA, 2004 2006/03/23 第151回ソフトウェア工学研究会

差分に着目した関数呼び出しパターン 版管理システム内の差分を解析することで、個別の機能に限定した関数呼び出しパターンが得られる ソースコードの変更の保存は個別の機能毎に行われる 版管理システム内のソースコードの差分は個別の機能に関わるものである … aaa(); bbb(); ccc(); ddd(); open_file(); write_result(); close_file(); … calculate1(); calculate2(); open_file(); write_result(); close_file(); 変更 「計算する」という機能に対する変更 パターン抽出 「計算する」という機能に ついての関数呼び出しパターン 2006/03/23 第151回ソフトウェア工学研究会

差分からの関数呼び出しパターン抽出の流れ ソースコードの 差分の取得 ソースコードの 特徴の取得 特徴シーケンス の生成 Sequential pattern mining によるパターン抽出 版管理 システム ソースコードの特徴と特徴シーケンスについて何も情報がないのでこの画面にいみがない ソースコードの特徴と特徴シーケンスの概要（関数の利用例ですとか）を言っておく ソースコードの差分 ソースコードの特徴 特徴シーケンス 関数呼び出しパターン 2006/03/23 第151回ソフトウェア工学研究会

ソースコードの特徴の取得 ソースコードの特徴 関数の利用例を構成する要素 本研究では以下のものをソースコードの特徴とした 関数呼び出し 条件文の開始、終了位置 繰り返し文の開始、終了位置 関数呼び出し要素 制御文要素 int main(void) { int a; a = baz(); a = foo(a); if(a != 0){ a = bar(a); } printf(“%d\n”,a); ソースコードの特徴 baz( ) foo( ) if( ) { bar( ) } printf( ) 関数呼び出し 条件文の開始位置 条件文の終了位置 2006/03/23 第151回ソフトウェア工学研究会

特徴シーケンスの生成 特徴シーケンス 関数の利用実績を抽象化したもの 一つの関数定義内におけるソースコードの特徴のリスト ただし、本手法では追加、および編集が起こった行におけるソースコードの特徴のみ対象とする ソースコードの差分 int main(void) { int a; a = baz(); a = foo(a); if(a != 0){ a = bar(a); } printf(“%d\n”,a); ソースコードの特徴 特徴シーケンス baz( ) foo( ) if( ) { bar( ) } printf( ) baz( ) if( ) { bar( ) } 追加・編集された行 2006/03/23 第151回ソフトウェア工学研究会

Sequential pattern mining によるパターン抽出 与えられた複数のリストから、ユーザが指定した閾値以上の頻度で共通して現れる部分リストを求める手法 マイニングアルゴリズムにはPrefixSpanを利用している 関数の利用実績に共通して現れる利用例を取り出して関数呼び出しパターンとする a(); if(){ b(); } a(); if(){ b(); } if(){ b(); } a(); if(){ b(); c(); } if(){ b(); c(); } if(){ b(); c(); } 2006/03/23 第151回ソフトウェア工学研究会

無駄なパターンの除去 抽出されたパターンから無駄なものの除去を行う 無駄なパターンの除去は2つのステップで行われる 無駄なパターン＝利用法理解の役に立たないパターン 制御文要素の対応が取れていないパターン 制御文要素の数が多すぎるパターン 関数の利用関係を表していないパターン 無駄なパターンが多いと、開発者が欲するパターンの探索が困難になる 無駄なパターンの除去は2つのステップで行われる マイニング時におけるパターンの除去 マイニング後におけるパターンの除去 2006/03/23 第151回ソフトウェア工学研究会

マイニング時における無駄なパターンの除去 無駄なパターンを生成する射影に制限を加える 無駄なパターンの出力を抑制 計算時間を大幅に削減 射影 PrefixSpanアルゴリズムの中心となる操作 全シーケンスから特定の要素以降の接尾辞を抜き出す 要素aによる射影 c(); } c(); } b(); b:1 c:2 }:2 … … 射影 a:3 b:1 c:2 if:2 }:2 要素数の カウント a(); c(); if(){ a(); } if(){ a(); c(); } b(); 前方に対応する制御文要素が 無いのでこれ以上探索しない 2006/03/23 第151回ソフトウェア工学研究会

マイニング後における無駄なパターンの除去 マイニング時にチェックできないような無駄なパターンを除去 制御文要素が数がパターン全体の要素数の3分の2を超えている 関数呼び出し要素が1個以下しかない 制御文要素の対応が取れていない 再利用できないパターンだから 制御文要素の数がパターン全体の要素数の3分の2を超えている この場合、大半の制御文要素は関数呼び出しとは関係ないから 関数呼び出し要素が1個以下しかない 関数呼び出し同士の関連を表したパターンとはいえないから 2006/03/23 第151回ソフトウェア工学研究会

システムの実装 開発者 開発者 パターン ブラウザ部 閲覧 パターンを含む ソースコード パターン情報 チェックイン/ チェックアウト データベース部 CVS リポジトリ 関数呼び出し パターン 開発履歴情報 特徴シーケンス 生成部 関数呼び出し パターン抽出部 ソースコード の差分 2006/03/23 第151回ソフトウェア工学研究会

パターンブラウザ 関数呼び出しパターンリスト 関数呼び出し パターン パターンを実現している ソースコード パターンを含む リビジョンのリスト 2006/03/23 第151回ソフトウェア工学研究会

適用実験 提案手法を実際のオープンソースソフトウェアに適用して、以下のことについてその有用性を確かめる 提案手法が部品の利用法の理解に役に立つかどうか 既存手法に存在した問題点が解決できているかどうか 実験対象にはThe Golem X11 Window Manager[3]を用いた 約1分半の計算時間で74個のパターンを抽出できた The Golem X11 Window Manager 開発期間 2001/3 ～ 2005/5 開発者数 3 ソースファイル数 180 総行数 55758 総リビジョン数：2680 総コミットトランザクション数：607 2006/03/23 [3]The Golem X11 Window Manager, http://golem.sourceforge.net/ 第151回ソフトウェア工学研究会

抽出された関数呼び出しパターン client_sizeframe関数を用いてclientのリサイズを行う リサイズの結果から条件分岐を行う if(){ action_send_config } // end if client_sizeframe関数を用いてclientのリサイズを行う リサイズの結果から条件分岐を行う 条件に沿っているならば、action_send_config関数を用いてリサイズの結果を送信する 条件分岐まで含めた部品の利用法を 理解できるパターンを抽出できた 2006/03/23 第151回ソフトウェア工学研究会

既存手法との比較 既存の関数呼び出しパターン抽出手法が持つ問題点を解決できているかどうかを評価する 複数の機能が一つにまとめられてしまうという問題点 Golemから以下の二つの手法でパターンを抽出し、それらを比較する 本研究で提案した、差分からパターンを抽出する手法 最新版のソースコードのみから特徴シーケンスを取得し、そこからパターンを抽出する手法 「同じ箇所で呼び出される事の多い関数群を1つのパターンにまとめる」という既存手法の特徴を持ちつつ、提案手法と同じ形式のパターンを出力する 2006/03/23 第151回ソフトウェア工学研究会

既存手法と提案手法によるパターンの違い 既存手法のパターンには関係無い処理が含まれている 既存手法によるパターン PDEBUG if(){ XCreatePixmap DefaultDepth image_scale image_put DefaultGC image_destroy 提案手法によるパターン XCreatePixmap DefaultDepth image_put DefaultGC image_destroy 画像の描画に 関するパターン デバッグ 出力マクロ pixmapの スケーリング を行う関数 image_scale 関数が無い 既存手法のパターンには関係無い処理が含まれている image_scale関数は画像の描画に必須ではない 提案手法によるパターンは、既存手法による パターンに含まれる余分な要素を取り除いたものといえる 2006/03/23 第151回ソフトウェア工学研究会

提案手法によるパターンの内訳 有用と判断したパターンカテゴリ*のうち、50％が既存手法で抽出したパターンをさらに細かい単位に分割するパターンを含んでいた ただし、29％は最新版のソースコードに含まれない部品のパターンを含むカテゴリであった 既存手法より細かい機能のパターン 既存手法と同じパターン 最新版に無い部品のパターン A B C 合計 14(50%) 6(21%) 8(29%) 28 表2：提案手法で得られた有用なパターンの内訳 *) パターンカテゴリとは、関数呼び出しパターンを同じ種類の関数呼び出し要素を持つ もの同士で分類したものである 2006/03/23 第151回ソフトウェア工学研究会

適用実験の考察 問題点を相互に補うために、2つの 手法をうまく組み合わせることが必要 提案手法を用いて、ソフトウェア部品の利用法の理解に有用な関数呼び出しパターンが得られた 提案手法を用いたパターンが、既存手法によって抽出したパターンをさらに細かい単位に分割していた 既存手法で抽出できるが、提案手法では抽出できないパターンも多く存在した 提案手法では最新版のソースコードには存在しない部品の利用パターンも抽出していた 問題点を相互に補うために、2つの 手法をうまく組み合わせることが必要 2006/03/23 第151回ソフトウェア工学研究会

まとめと今後の課題 版管理システムに蓄積されているソースコードの差分から、個別の機能に限定した関数呼び出しパターンを抽出する手法について提案した 版管理システム内のソースコードの差分が一つ機能に関わるものであることから 提案手法を実際のオープンソースソフトウェアに適用し、その有効性を確認した 提案手法と既存手法を組み合わせることによる関数呼び出しパターンの質の向上 利用法理解を支援するためのパターンブラウザの機能充実 2006/03/23 第151回ソフトウェア工学研究会

2006/03/23 第151回ソフトウェア工学研究会

抽出された関数呼び出しパターンの内訳 Golemから抽出されたパターンのうち、67％が利用法の理解に有用なパターンであった 有用なパターンを含むパターンカテゴリは全体の73％であった パターンカテゴリ：同じ種類の関数呼び出しを含むパターンごとに分類したもの 有用 不要 合計 パターン 48(67%) 24(33%) 72 カテゴリ 33(73%) 12(27%) 45 表1：抽出されたパターンの内訳 有用と判断したパターンカテゴリのうち、50％が既存手法で抽出したパターンをさらに細かい単位に分割するパターンを含んでいた ただし、29％は最新版のソースコードに含まれない部品のパターンを含むカテゴリであった 既存手法より細かい機能のパターン 既存手法と同じパターン 最新版に無い部品のパターン A B C 合計 14(50%) 6(21%) 8(29%) 28 表2：有用なパターンの内訳 2006/03/23 第151回ソフトウェア工学研究会

既存手法でしか抽出できなかったパターン 既存手法では抽出できたが、提案手法では抽出できなかったパターンが多く存在した 既存手法：440パターン（267カテゴリ） 提案手法：72パターン（46カテゴリ） 267カテゴリのうち、23カテゴリは提案手法によって抽出したパターンにも含まれていた ＊：同じ種類の関数呼び出し要素を持つもの同士を同じ カテゴリとして分類している 2006/03/23 第151回ソフトウェア工学研究会