オブジェクト指向プログラムにおける
エイリアス解析・視覚化ツールの試作
近藤
大畑
井上
大阪大学大学院
2000/07/14
和弘
文明
克郎
基礎工学研究科
ソフトウェアサイエンス研究会
1
発表内容
OOプログラムに対するエイリアス解析手法の提案
既存の手法の問題点と対処法
Alias Flow Graph (AFG) によるエイリアス解析手法
AFG構築アルゴリズム
AFGによるエイリアス計算
Javaエイリアス解析・視覚化ツール
ツール設計
テキストウインドウ
エイリアスツリーウインドウ
ウインドウ間の連係
ツール概要と使用例
2000/07/14
ソフトウェアサイエンス研究会
2
エイリアス
(引数の参照渡し・参照変数・ポインタを介した間接
参照などで生じる, )同じメモリ領域を指す可能性の
ある式間の同値関係
参照変数
class Employee { … … }
class Manager extends
Employee {
Manager(String n, int s) {
super(n, s);
}
void manage(Employee e) {
e.set_boss(this);
e.add_salary(50);
}
}
2000/07/14
インスタンス生成式
class Office {
public static void main(String args[]) {
Employee A =
new Employee("Mr.A", 700);
Manager B =
new Manager("Mr.B", 850);
B.manage(A);
「エイリアス指
A.print();
B.print();
定」
}
}
ソフトウェアサイエンス研究会
3
エイリアス情報の利用
プログラム依存関係解析(プログラムスライス)
プログラムスライス ⇔
プログラム中のある文のある変数に着目し, その変数に
直接/間接的に依存関係のある部分を抽出したもの
データ依存関係の抽出
readln(a);
コンパイラ最適化
readln(b);
max := a;
冗長な命令の削除
min := b;
仮想関数呼び出し/関数へのポインタの排除
if a < b then begin
max := b;
デバッグ, プログラム理解
min := a;
end;
エイリアス関係の表示による特定オブジェクトの情報抽出
writeln(‘Max: ’, max, ‘\n’);
(型, メソッド, …)
writeln(‘Min: ’, min, ‘\n’);
2000/07/14
ソフトウェアサイエンス研究会
4
エイリアス情報の利用例
デバッグへの利用
実行結果
特定のオブジェクトに対する
エイリアスの表示
% java Office
Mr.A Salary : 700
750
Mr.B Salary : 900
850
class Employee { … … }
class Manager extends
Employee {
Manager(String n, int s) {
super(n, s);
}
void manage(Employee e) {
e.set_boss(this);
e.add_salary(50);
add_salary(50);
}
}
2000/07/14
class Office {
public static void main(String args[]) {
Employee A =
new Employee("Mr.A", 700);
Manager B =
new Manager("Mr.B", 850);
B.manage(A);
A.print();
B.print();
}
}
ソフトウェアサイエンス研究会
5
エイリアス計算手順
到達エイリアス集合(Reaching Alias, RA)を利用
RA(s) ⇔ 文sに到達可能なエイリアス組の集合
プログラム実行経路をたどりながら, 順次計算
文
到達エイリアス集合 RA(s)
1
Φ
2 {(1, a), (1, new Integer)}
3 {(1, a), (1, new Integer)},
{(2, b), (2, new Integer)}
Integer a, b, c;
4 {(1, a), (1, new Integer)},
1: a = new Integer(1);
2: b = new Integer(2);
{(3, c), (2, b), (3, b), (2, new Integer)}
3: c = b;
5 {(1, a), (1, new Integer)},
4: System.out.println(c);
{(4, c), (3, c), (2, b), (3, b), (2, new Integer)}
5: c = a;
6: System.out.println(c); 6 {(5, c), (5, a), (1, a), (1, new Integer)},
{(2, b), (3, b), (2, new Integer)}
2000/07/14
ソフトウェアサイエンス研究会
6
既存の手法の問題点
エイリアス解析共通の問題
1) 到達エイリアス(RA)集合に依存した解析
プログラムのフローに従って解析をすすめるため, 通常プログラムの
一部を変更しても全体を再解析する必要がある．
OOプログラムにおけるエイリアス解析特有の問題
2) 解析結果の再利用が考慮されていない
再利用性を持つOOプログラムでは, モジュール(クラス/メソッド)単
位でエイリアス情報を保持し再利用可能にすることで, 解析コスト
の削減が期待できるが, それが考慮されていない．
3) インスタンス属性の取り扱いコストが大きい
インスタンス内部のエイリアス情報を同一クラスのインスタンスで共
有する場合, 正確な解析結果が期待できない．すべてを区別す
る場合, 多くのコストが必要となる．
2000/07/14
ソフトウェアサイエンス研究会
7
提案する手法
本研究では, エイリアスフローグラフ(AFG)による, OO
プログラムに対するエイリアス解析手法を提案する
問題点への対処
1) 到達エイリアス(RA)集合に依存した解析
RA集合は, AFG構築のためのメソッド(クラス)内で
のエイリアス解析でのみ利用される．エイリアス計算
はグラフの到達問題に置き換えられる．
2) 解析結果の再利用が考慮されていない
AFGはメソッド(クラス)単位で構築され, 自身/依存する
メソッド(クラス)が変更されない限り, 再利用可能．
3) インスタンス属性の取り扱いコストが大きい
AFGはすべてのインスタンスに共通なエイリアス関係のみ
持ち, インスタンス独自のエイリアス関係は, エイリアス計
算時に導出．
2000/07/14
ソフトウェアサイエンス研究会
8
AFGによるエイリアス解析手法
Phase 1: AFGの構築
⇔ RA集合による直接のエイリアス関係の導出
class Test {
Calc a, b;
Integer c;
Test() {
a = new Calc();
b = new Calc();
a.inc();
b.add(1);
c = b.result();
}
}
Phase 2: AFGによるエイリアス計算
⇔ グラフの到達問題
2000/07/14
ソフトウェアサイエンス研究会
9
Phase 1:
AFG標準節点 ⇔ オブジェクトへの参照
AFG構築
インスタンス生成式
参照変数
AFG辺 ⇔ 2節点間の(代入文/引数渡し/同一変
数の参照 などによる)直接のエイリアス関係
1: Integer a = new Integer(1);
2: Integer b, c;
3: b = a;
4: c = b;
AFG ((1, new Integer), (1, a))
((1, a), (3, a))
((3, a), (3, b))
((3, b), (4, b))
((4, b), (4, c))
AFG特殊節点 ⇔ メソッド引数/メソッド戻り値/属性
2000/07/14
ソフトウェアサイエンス研究会
10
Phase 1:
AFG構築(続き)
AFG ⇔ AFG節点/AFG辺により構築
メソッド → メソッドAFG
クラス → クラスAFG
クラスAFG
public class Calc {
Integer i;
public Calc() {i = new Integer(0); }
public
void inc() {
AFG特殊節点（インスタンス属性）
i = new Integer(i.intValue() + 1);
}
AFG標準節点（参照変数）
public
void add(int c) {
i = new Integer(i.intValue() + c);
}
AFG特殊節点（メソッド戻り値）
public Integer result() {return(i); }
}
2000/07/14
ソフトウェアサイエンス研究会
メソッドAFG
11
Phase 2:
単純式x … 例: a, b, c, new Calc()
Step 1:
AFGによるエイリアス計算
グラフ到達問題
限定式x.y … 例: b.result()
Step 1:
Step 2:
Step 3:
(インスタンス)xに関するエイリアス計算
X に関する情報の抽出
(エイリアス集合をX)
yに関するエイリアス計算
public class Calc {
Integer i;
class Test {
public Calc() {i = new Integer(0); }
Calc a = new Calc();
public void inc() {
Calc b = new Calc();
i = new Integer(i.intValue() + 1);
Integer c;
}
Test() {
public void add(int c) {
a.inc();
i = new Integer(i.intValue() + c);
b.add(1);
}
c = b.result();
public Integer result() {return(i); }
}
2000/07/14 }
12
ソフトウェアサイエンス研究会
}
Phase 2:
AFGによるエイリア…(続き)
例: 限定式b.result()
bに関するエイリアス計算(エイリアス集合をB )
Step 2: B に関する情報の抽出
型: Calcクラス
メソッド: Calc::Calc(), Calc::add(), Calc::result()
Step 3: result()に関するエイリアス計算
Step 1:
class Test {
Calc a = new Calc();
Calc b = new Calc();
Integer c;
Test() {
a.inc();
b.add(1);
c = b.result();
}
}
2000/07/14
public class Calc {
Integer i;
public Calc() {i = new Integer(0); }
public void inc() {
i = new Integer(i.intValue() + 1);
}
public void add(int c) {
i = new Integer(i.intValue() + c);
}
public Integer result() {return(i); }
}
ソフトウェアサイエンス研究会
13
Javaエイリアス解析ライブラリ
ライブラリ構成
libantlr …構文解析
libjavamm …意味解析
libAFG …AFG構築
サイズ：17,000[自動生成] + 10,000行
開発環境
OS : Debian GNU/Linux
言語 : C++(C)
2000/07/14
ソフトウェアサイエンス研究会
14
発表内容
OOプログラムに対するエイリアス解析手法の提案
既存の手法の問題点と対処法
Alias Flow Graph (AFG) によるエイリアス解析手法
AFG構築アルゴリズム
AFGによるエイリアス計算
Javaエイリアス解析・視覚化ツール
ツール設計
テキストウインドウ
エイリアスツリーウインドウ
ウインドウ間の連係
ツール概要と使用例
2000/07/14
ソフトウェアサイエンス研究会
15
ツール設計
情報視覚化において必要な技法†
必要なもののみ表示する技法 全体と詳細を同時に見る方法
本研究においての着目点
エイリアス集合全体像の
エイリアス集合の視覚的な表示
把握と理解の簡易化
テキストウインドウ
ソースコードの強調表示
エイリアス部分
非エイリアス部分
エイリアスツリーウインドウ
エイリアスツリーによる表示
エイリアスの存在する
クラス・メソッドの把握
各エイリアスの詳細情報
ウインドウ間の連係
全体像とソースコードの対応
視点の移動と拡大表示
エイリアスツリーからの
ファイルオープン
†増井俊之, “情報視覚化の最近の研究動向, ” 電子情報通信学会第９回データ工学ワークショップ, 1998．
2000/07/14
ソフトウェアサイエンス研究会
16
テキストウインドウ
着目点：エイリアス集合の視覚的な表示
ソースコード → エイリアス部分, 非エイリアス部分
エイリアス部分
着目したい部分
強調表示：フォント, 背景色（エイリアス別）
非エイリアス部分
ソース中の割合大
目的に応じた表示方法を選択
「縮小（可変・線分化）, 継承」
の三種類の表示方法を実装
2000/07/14
ソフトウェアサイエンス研究会
17
非エイリアス部分の表示：縮小
縮小：可変
エイリアスからの距離でサイズを変更
制御構造を把握しつつエイリアス部分に注目可
縮小：線分化
行を線分化して表示（インデント, 長さは維持）
エイリアスのみに着目したい場合に有用
可変
2000/07/14
線分化
ソフトウェアサイエンス研究会
18
非エイリアス部分の表示：継承
継承
エイリアス表示前のソースコードの状態を継承
通常時に使用 → ソース全体を表示
縮小後に使用 → 縮小との和集合を表示
継承
線分化
2000/07/14
継承
ソフトウェアサイエンス研究会
19
エイリアスツリーウインドウ
着目点：エイリアス集合全体像の把握と理解の簡易化
エイリアスツリー
エイリアスの存在するクラス・メソッドを階層表示
情報表示リスト
エイリアスなどの詳細情報を表示
エイリアス指定
クラス
メソッド
エイリアス
エイリアスツリー
2000/07/14
情報表示リスト
ソフトウェアサイエンス研究会
20
ウインドウ間の連係
着目点：全体像とソースコードの対応
エイリアス集合全体像の表示
テキストウインドウ
エイリアスツリーウインドウ
ソースコード中のエイリアスの表示
ウインドウ間の対応
テキストウインドウ
エイリアスツリーウインドウ
着目対象
エイリアス
ノード
場所情報(ファイル)
表示ファイル
ファイル名
場所情報(行)
カーソル位置
行番号
エイリアス集合の区別
背景色の違い
サブツリーの違い
2000/07/14
ソフトウェアサイエンス研究会
21
ウインドウ連係の例
Animeter.java
中に存在する
エイリアスツリーを表示させる
imageURL についてのエイリアスを表示させる
エイリアス部分を強調表示
非エイリアス部分を「線分化」で表示
2000/07/14
ソフトウェアサイエンス研究会
22
ウインドウ連係の例
エイリアスツリーのノードから
クラス Hashtable,
エイリアスメソッド
old を選択
put 中の
エイリアス一覧を表示させる
old の存在するファイル
old の詳細な情報を表示
Hashtable.javaをオープン
2000/07/14
ソフトウェアサイエンス研究会
23
ウインドウ連係の例
Hashtable.java 中の
エイリアス部分を強調表示
old が存在する行にカーソルを移動
ウインドウ間の対応完了
old を拡大表示
非エイリアス部分を「線分化」で表示
2000/07/14
ソフトウェアサイエンス研究会
24
Javaエイリアス解析・視覚化ツール
ツール構成
図参照
サイズ: 約4,200行
開発環境
OS : Debian GNU/Linux
言語 : C++(C)
GUIライブラリ : GTK--(Gtk+)
2000/07/14
ソフトウェアサイエンス研究会
25
ツール適用範囲
デバッグ
エイリアス関係の表示によるデバッグ範囲の絞込み
(ファイル, クラス, メソッド, …)
プログラム理解
エイリアス関係の表示による特定オブジェクトの情報抽出
(型, メソッド, …)
現時点ではツールの有効性評価を行っていない
デバッグフェーズでのフォールト位置特定を
例として取り上げ, 有効性を検証する
2000/07/14
ソフトウェアサイエンス研究会
26
ツール使用例
フォールト事例
表計算Javaアプレット SpreadSheet.java
(JDK付属サンプルコード, サイズ:約1000行)
プログラム実行時に下図のようなフォールトが発生
(表計算の結果が誤っている)
実際にツールを利用して
フォールト位置を特定する
2000/07/14
ソフトウェアサイエンス研究会
27
ツール使用例
式を格納している変数
表計算式の解析を行うメソッド
エイリアスツリーを表示させて
formula に
非エイリアス部分の線分化により
ついてのエイリアスを表示させる
エイリアスの全体像を把握
parseFormula を調べる
ソースコードの表示領域は10%に縮小
2000/07/14
ソフトウェアサイエンス研究会
28
ツール使用例
メソッド parseValue の戻り値が
メソッド
両メソッド中のエイリアスに注目し
parseFormula,parseValue に
仮引数 formula となっていることが
のみエイリアスが存在することがわかる
エイリアスを含む文(約30行)を調べる
フォールト原因であることがわかる
2000/07/14
ソフトウェアサイエンス研究会
29
ツール使用例
正しくは restformula を返さなければ
正しい実行結果が得られる
ならないことを類推し修正する
2000/07/14
ソフトウェアサイエンス研究会
30
まとめ と 今後の課題
まとめ
本研究では, 我々が提案したオブジェクト指向プログラム
に対するエイリアス解析手法を実現した, Javaエイリアス
解析・視覚化ツールの試作を行った
本ツールは解析部とＵＩ部で構成され、ＵＩ部ではデバッグ,
プログラム理解のために解析結果の視覚化を行う
今後の課題
スライス解析ツールへの発展
ツールの有効性の評価
非エイリアス部分の表示方法の改良
2000/07/14
ソフトウェアサイエンス研究会
31
© Copyright 2024 ExpyDoc
