ソースコードの差分を用いた関数呼び出しパターンの抽

ソースコードの差分を用いた関数呼び出し
パターンの抽出手法の提案
中山崇，松下誠，井上克郎
大阪大学大学院情報科学研究科
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
ソフトウェア部品の利用法
ソフトウェア部品を再利用することは非常に重要である
再利用によって生産性や品質が向上するから
ソフトウェア部品を再利用するには、まずその部品の利用法
を理解しなければならない
部品の初期化の仕方や、実現したい処理に必要な関数群の呼び
出し順など
一般に、部品の利用法理解には付属するドキュメントなどを利用
する
ドキュメントなどが付属していない部品では利用法の学習が
困難であった
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2
関数呼び出しパターンによる利用法の理解
関数呼び出しパターンと呼ばれるものを抽出すること
で、部品の利用法理解を支援する研究が過去にな
されている
ソースコード中に頻繁に出現する関数の利用関係を関
数呼び出しパターンとしている
ファイルへの書き込
みはどのようにした
ら良いのだろう？
1.
2.
3.
4.
5.
fopen();
if(){
fprintf();
}
fclose();
これらの関数を
使えばいいのか！
2006/03/23
…
File *file = fopen(path,”w”);
if(file != null){
fprintf(file,string);
}
fclose(file);
…
具体的な使い方はパターンを
実現したコードから学べるな
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
既存のパターン抽出手法とその問題点
複数の機能が1つのまとまりとして認識されてしまうと
いう問題点を持つ
既存手法が以下の特徴を持つため
同時に現れる関数は同じ機能を実装するものとみなす
計算処理部
データ
書き出し部
…
calculate1();
calculate2();
open_file();
write_result();
close_file();
…
…
calculate1();
calculate2();
open_file();
write_result();
close_file();
…
calculate1();
calculate2();
open_file();
write_result();
close_file();
計算部を再利
用したいが、
write_resultも
関係あるの？
個別の機能に限定した関数呼び出しパターンが必要
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
4
研究の目的
既存手法の問題点を解決するために、個別の機能に限定
した関数呼び出しパターンを抽出し、部品利用法の理解に
役立てる
版管理システム内のソースコードの差分から個別の機能に
限定した関数呼び出しパターンを抽出する手法を提案
手法に基づいた関数呼び出しパターン抽出システムの構築
利用法学習を支援するために、パターンとそれを利用してい
るソースコードを閲覧できるパターンブラウザの構築
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
5
版管理システム
版管理システム
プロダクトの開発履歴を保存・提供する
システム
開発者はソースコードの変更を版管理シ
ステムに保存しながら開発作業を進める
変更内容は差分（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回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
差分に着目した関数呼び出しパターン
版管理システム内の差分を解析することで、個別の機能に
限定した関数呼び出しパターンが得られる
ソースコードの変更の保存は個別の機能毎に行われる
版管理システム内のソースコードの差分は個別の機能に関わるも
のである
…
変更
aaa();
bbb();
ccc();
ddd();
open_file();
write_result();
close_file();
…
2006/03/23
…
calculate1();
calculate2();
open_file();
write_result();
close_file();
…
「計算する」という機能に対する変更
パターン抽出
「計算する」という機能に
ついての関数呼び出しパターン
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
差分からの関数呼び出しパターン抽出の流れ
ソースコードの
差分の取得
版管理
システム
ソースコードの
特徴の取得
特徴シーケンス
の生成
Sequential pattern mining
によるパターン抽出
1.
2.
3.
1.
2.
ソースコードの差分ソースコードの特徴特徴シーケンス関数呼び出しパターン
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
ソースコードの特徴の取得
ソースコードの特徴
関数の利用例を構成する要素
本研究では以下のものをソースコードの特徴とした
関数呼び出し
条件文の開始、終了位置
繰り返し文の開始、終了位置
関数呼び出し
条件文の開始位置
条件文の終了位置
2006/03/23
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( )
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
特徴シーケンスの生成
特徴シーケンス
関数の利用実績を抽象化したもの
一つの関数定義内におけるソースコードの特徴のリスト
ただし、本手法では追加、および編集が起こった行におけるソー
スコードの特徴のみ対象とする
ソースコードの差分
追加・編集された行
2006/03/23
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( )
特徴シーケンス
1. baz( )
2. if( ) {
3. bar( )
4. }
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
Sequential pattern mining によるパターン抽出
Sequential pattern mining
与えられた複数のリストから、ユーザが指定した閾値以上
の頻度で共通して現れる部分リストを求める手法
マイニングアルゴリズムにはPrefixSpanを利用している
関数の利用実績に共通して現れる利用例を取り出
して関数呼び出しパターンとする
a(); if(){ b(); }
a(); if(){ b(); c(); }
2006/03/23
if(){ b(); c(); }
a(); if(){ b(); }
if(){ b(); }
if(){ b(); c(); }
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
無駄なパターンの除去
抽出されたパターンから無駄なものの除去を行う
無駄なパターン＝利用法理解の役に立たないパターン
制御文要素の対応が取れていないパターン
制御文要素の数が多すぎるパターン
関数の利用関係を表していないパターン
無駄なパターンが多いと、開発者が欲するパターンの探
索が困難になる
無駄なパターンの除去は2つのステップで行われる
マイニング時におけるパターンの除去
マイニング後におけるパターンの除去
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
マイニング時における無駄なパターンの除去
無駄なパターンを生成する射影に制限を加える
無駄なパターンの出力を抑制
計算時間を大幅に削減
射影
PrefixSpanアルゴリズムの中心となる操作
全シーケンスから特定の要素以降の接尾辞を抜き出す
要素aによる射影
1. a(); c();
2. if(){ a(); }
3. if(){ a(); c(); } b();
2006/03/23
要素数の
カウント
a:3
b:1
c:2
if:2
}:2
射影
1. c();
b:1
2. }
c:2
3. c(); } b(); }:2
…
…
…
前方に対応する制御文要素が
無いのでこれ以上探索しない
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
マイニング後における無駄なパターンの除去
マイニング時にチェックできないような無駄なパターンを
除去
制御文要素が数がパターン全体の要素数の3分の2を超
えている
関数呼び出し要素が1個以下しかない
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
システムの実装
開発者開発者
閲覧
チェックイン/
チェックアウト
パターン
ブラウザ部
パターンを含む
ソースコード
パターン情報
データベース部
CVS
リポジトリ
ソースコード
の差分
2006/03/23
開発履歴情報
特徴シーケンス
生成部
関数呼び出し
パターン
関数呼び出し
パターン抽出部
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
パターンブラウザ
関数呼び出しパターンリスト
関数呼び出し
パターン
パターンを実現している
ソースコード
パターンを含む
リビジョンのリスト
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
適用実験
提案手法を実際のオープンソースソフトウェアに適用して、以
下のことについてその有用性を確かめる
提案手法が部品の利用法の理解に役に立つかどうか
既存手法に存在した問題点が解決できているかどうか
実験対象にはThe Golem X11 Window Manager[3]を
用いた
約1分半の計算時間で74個のパターンを抽出できた
The Golem X11 Window Manager
開発期間
2001/3 ～ 2005/5
開発者数
3
ソースファイル数
180
総行数
55758
[3]The Golem X11 Window Manager, http://golem.sourceforge.net/ 第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17
2006/03/23
抽出された関数呼び出しパターン
1. client_sizeframe
2. if(){
3.
action_send_config
4. } // end if
client_sizeframe関数を用いてclientのリサイズを行う
リサイズの結果から条件分岐を行う
条件に沿っているならば、action_send_config関数を用い
てリサイズの結果を送信する
条件分岐まで含めた部品の利用法を
理解できるパターンを抽出できた
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
18
既存手法との比較
既存の関数呼び出しパターン抽出手法が持つ問題点を解
決できているかどうかを評価する
複数の機能が一つにまとめられてしまうという問題点
Golemから以下の二つの手法でパターンを抽出し、それらを
比較する
本研究で提案した、差分からパターンを抽出する手法
最新版のソースコードのみから特徴シーケンスを取得し、そこからパ
ターンを抽出する手法
「同じ箇所で呼び出される事の多い関数群を1つのパターンにまとめる」という
既存手法の特徴を持ちつつ、提案手法と同じ形式のパターンを出力する
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
19
既存手法と提案手法によるパターンの違い
デバッグ
出力マクロ
pixmapの
スケーリング
を行う関数
既存手法によるパターン
1. PDEBUG
2. if(){
3.
XCreatePixmap
4.
DefaultDepth
5.
image_scale
6.
image_put
7.
DefaultGC
8.
image_destroy
提案手法によるパターン
1. XCreatePixmap
2. DefaultDepth
3. image_put
4. DefaultGC
5. image_destroy
画像の描画に
関するパターン
image_scale
関数が無い
既存手法のパターンには関係無い処理が含まれて
いる
image_scale関数は画像の描画に必須ではない
提案手法によるパターンは、既存手法による
パターンに含まれる余分な要素を取り除いたものといえる
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
20
提案手法によるパターンの内訳
有用と判断したパターンカテゴリ*のうち、50％が既存
手法で抽出したパターンをさらに細かい単位に分割
するパターンを含んでいた
ただし、29％は最新版のソースコードに含まれない
部品のパターンを含むカテゴリであった
A
B
C
合計
14(50%) 6(21%) 8(29%) 28
A) 既存手法より細かい機能のパターン
B) 既存手法と同じパターン
C) 最新版に無い部品のパターン
表2：提案手法で得られた有用なパターンの内訳
*) パターンカテゴリとは、関数呼び出しパターンを同じ種類の関数呼び出し要素を持つ
もの同士で分類したものである
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
21
適用実験の考察
提案手法を用いて、ソフトウェア部品の利用法の理解に有
用な関数呼び出しパターンが得られた
提案手法を用いたパターンが、既存手法によって抽出した
パターンをさらに細かい単位に分割していた
既存手法で抽出できるが、提案手法では抽出できないパ
ターンも多く存在した
提案手法では最新版のソースコードには存在しない部品の
利用パターンも抽出していた
問題点を相互に補うために、2つの
手法をうまく組み合わせることが必要
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
まとめと今後の課題
版管理システムに蓄積されているソースコードの差分から、
個別の機能に限定した関数呼び出しパターンを抽出する手
法について提案した
版管理システム内のソースコードの差分が一つ機能に関わるもの
であることから
提案手法を実際のオープンソースソフトウェアに適用し、その
有効性を確認した
提案手法と既存手法を組み合わせることによる関数呼び出
しパターンの質の向上
利用法理解を支援するためのパターンブラウザの機能充実
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
23
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
24
抽出された関数呼び出しパターンの内訳
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
A) 既存手法より細かい機能のパターン
B) 既存手法と同じパターン
C) 最新版に無い部品のパターン
表2：有用なパターンの内訳
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
25
既存手法でしか抽出できなかったパターン
既存手法では抽出できたが、提案手法では抽出で
きなかったパターンが多く存在した
既存手法：440パターン（267カテゴリ）
提案手法：72パターン（46カテゴリ）
267カテゴリのうち、23カテゴリは提案手法によって抽出し
たパターンにも含まれていた
＊：同じ種類の関数呼び出し要素を持つもの同士を同じ
カテゴリとして分類している
2006/03/23
第151回ソフトウェア工学研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
26

Download Report