関数呼出依存グラフに基づくプログラミング支援

関数呼出依存グラフを用いた
ライブラリの用例検索
名古屋大学工学研究科
計算理工学専攻阿草研究室
渥美紀寿
背景
• 高級言語ではライブラリが提供
– 入出力，文字列操作，整列操作等
プログラム中に多くのライブラリが使用される
• ライブラリの知識が必要
– マニュアルの参照
– 既存のソースコードから文字列検索
マニュアルの参照
（例）ライブラリ関数connect第一引数に関する説明
パラメータsはソケットです。このタイプがSOCK_DGRAM の場合
、この呼び出しはソケットが結び付けられる通信相手を指定しま
す。このアドレスは送信データグラムの送信先であり、受信デー
タグラムの送信元となる唯一のアドレスです。ソケットのタイプが
SOCK_STREAM の場合、この呼び出しは通信相手のソケットに
接続を確立しようとします。
実際にはライブラリ関数socketの返り値を与える
既存のソースコードから
文字列による検索
finger/net.c: if (Tflag && connect(s, (struct sockaddr *)&sin,
ftp/cmds.c:
disconnect(0, 0);
ftp/fetch.c: if (connect(s, res->ai_addr, res->ai_addrlen) < 0) {
ftp/fetch.c:
disconnect(0, NULL);
ftp/fetch.c:
disconnect(0, NULL);
if ((s = socket(hp->h_addrtype, SOCK_STREAM, 0)) < 0) {
perror("finger: socket");
return;
}
if (Tflag && connect(s, (struct sockaddr *)&sin, sizeof (sin))) {
perror("finger: connect");
return;
}
目的
• ライブラリの用法を調べる手段
– マニュアルの参照
マニュアルを参照しただけでは得られない情報がある
– 既存のソースコードから用例検索
文字列検索では同じ用法を区別できない
用法によって用例を分類し，効率よく検索したい
ライブラリの組み合わせを用法として捉える
関数呼出依存グラフ（FCDG）
• ライブラリの組み合わせを表現するものとし
て関数呼出依存グラフを提案
– ライブラリ関数間のデータ依存関係
– ライブラリ関数と条件式の間のデータ依存関係
– 条件式とライブラリ関数間の制御依存関係
データ依存関係
•
データ依存関係
– 関数呼び出し f の戻り値が関数呼び出し g の
引数となっている場合
1. g ( … , f ( ), … ) ;
2. a = f ( ) ; … ; g ( … , a , … ) ;
f と g の間のデータ依存関係
3. a = f(); if (a == NULL) { ... }
f と条件式の間のデータ依存関係
制御依存関係
• 制御依存関係
– 条件式 c の真偽によって関数呼び出し f が実行
されるか否かが決まる場合
if ( c ) {
f( );
}
while ( c ) {
f ( );
}
c と f の間の制御依存関係
FCDGの例
fp = fopen( ... );
if (fp = = NULL) {
fprintf( ... );
exit( ... );
}
fclose(fp);
fopen
==
NULL
t
fclose
fprintf
exit
t
部分FCDG
• FCDG
– 複数の機能が組み合わされている
特定のライブラリに着目した場合
そのライブラリに関する機能のみを抽出
注目している関数に特化したFCDGが必要
部分FCDG
部分FCDGの例
fopenを含む
FCDGの中で
(fopen, !=NULL)
(fopen, fclose)
の組み合わせが
多く存在
fopen
!=
NULL
fseek
!=
0
t
getc
fclose
t
注目しているライブラリ関数getc
putchar
!=
EOF
用法による用例の分類
部分FCDGによる分類
テンプレート
コード
部分FCDG
FCDGデータベース
部分FCDGを用法として捉える
テンプレートコードにより
用法を提示
ライブラリの用例検索
ソースコード
コード断片
コード断片
コード断片
ソースコード
データベース
テンプレート
コード
FCDG
データベース
FCDG
部分FCDG
部分FCDGによる分類
FreeBSD 4.3-STABLEの/usr/bin以下のコマンドのソース
プログラムの関数呼出依存グラフデータベースを基に
fopen を検索した結果
同じ関数呼出
依存グラフの
割合
関数呼出依
存グラフに含
まれる関数名
２６
２２
１３
９
fopen
fopen
fclose
fopen
perror
exit
fopen
fgets
fclose
まとめ
• ライブラリの用例検索の必要性
• ライブラリに関する依存関係
• ライブラリの組み合わせの取得
– 関数呼出依存グラフ
• 用法による分類
– 適度な単位で分類できた
効率的に用例を検索できる
今後の課題
• 関数を跨いだ依存解析
• 類似した関数呼出依存グラフ
– 部品化
• ドキュメントとの対応
• プログラム理解支援環境への適用
– 関数から取得された関数呼出依存グラフ
の類似性

Download Report