(57)【要約】【課題】コールグラフを用いた解析時間を短縮する。【解決手段】解析装置１０は、解析対象プログラム１内の処理の複数の手続きを複数のノードで表し、手続き間の複数の呼び出し関係を複数のエッジで表したコールグラフ２を記憶する。解析装置１０は、コールグラフ２に基づいて、複数のノードそれぞれについて、複数のエッジを呼び出し元から呼び出し先へ辿ることで自ノードへ到達可能な他ノードの数を示す到達可能ノード数を取得する。次に解析装置１０は、複数のノードそれぞれを、到達可能ノード数に基づいた順番で解析対象ノードとして選定する。そして解析装置１０は、コールグラフ２に基づいて選定された解析対象ノードに関する解析を行い、解析対象ノードに関連する情報を取得する。【選択図】図１
2018073223.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
解析対象プログラム内の処理の複数の手続きを複数のノードで表し、手続き間の複数の呼び出し関係を複数のエッジで表したコールグラフに基づいて、前記複数のノードそれぞれについて、前記複数のエッジを呼び出し元から呼び出し先へ辿ることで自ノードへ到達可能な他ノードの数を示す到達可能ノード数を取得し、
前記複数のノードそれぞれを、前記到達可能ノード数に基づいた順番で解析対象ノードとして選定し、
前記コールグラフに基づいて選定された前記解析対象ノードに関する解析を行い、前記解析対象ノードに関連する情報を取得する、
処理を実行させる解析プログラム。
【請求項２】
前記解析対象ノードの選定では、前記到達可能ノード数が多いノードほど優先的に解析対象ノードとして選定する、
請求項１記載の解析プログラム。
【請求項３】
前記複数のノードそれぞれに対応付けて、自ノードへ到達可能な他ノードのノード識別子が登録された到達可能ノード集合が設けられており、
前記到達可能ノード数の取得では、前記複数のノードそれぞれの前記到達可能ノード集合に登録された前記ノード識別子の数を、前記複数のノードそれぞれの前記到達可能ノード数として取得し、
前記コンピュータに、さらに、
前記解析対象ノードの解析により、前記解析対象ノードから前記複数のエッジを辿ることで到達可能な新たな呼び出し先ノードが検出されるごとに、前記新たな呼び出し先ノードの前記到達可能ノード集合に、前記解析対象ノードの前記到達可能ノード集合に含まれる前記ノード識別子を追加する、
請求項１または２記載の解析プログラム。
【請求項４】
前記コンピュータに、さらに、
前記複数のノードのうち、一度も解析を行っていないノードの状態を未解析状態と判定し、少なくとも１度解析が行われ、最後の解析後に、自ノードの直接の呼び出し先ノードの情報が更新されたノードの状態を要解析状態と判定する処理を実行させ、
前記解析対象ノードの選定では、前記未解析状態のノードを、前記要解析状態のノードよりも先に前記解析対象ノードとして選定する、
請求項１ないし３のいずれかに記載の解析プログラム。
【請求項５】
前記状態の判定では、前記複数のノードのうち、前記未解析状態と前記要解析状態とのいずれでもないノードを解析済状態と判定し、
前記解析対象ノードの選定では、前記要解析状態のノードのうち、自ノードからの直接の呼び出し先ノードのすべてが前記解析済状態であるノードを、情報が安定的であると判定し、情報が安定的な前記要解析状態のノードを、情報が安定的でない前記要解析状態のノードよりも先に前記解析対象ノードとして選定する、
請求項４記載の解析プログラム。
【請求項６】
前記コンピュータに、さらに、
前記解析対象プログラムに基づいて、選定された前記解析対象ノードに対応する手続きから呼び出される他の手続きの有無を解析し、前記他の手続きに対応するノードが前記コールグラフ内に存在しないとき、前記他の手続きに対応するノードを前記コールグラフに追加する、
処理を実行させる請求項１ないし５のいずれかに記載の解析プログラム。
【請求項７】
コンピュータが、
解析対象プログラム内の処理の複数の手続きを複数のノードで表し、手続き間の複数の呼び出し関係を複数のエッジで表したコールグラフに基づいて、前記複数のノードそれぞれについて、前記複数のエッジを呼び出し元から呼び出し先へ辿ることで自ノードへ到達可能な他ノードの数を示す到達可能ノード数を取得し、
前記複数のノードそれぞれを、前記到達可能ノード数に基づいた順番で解析対象ノードとして選定し、
前記コールグラフに基づいて選定された前記解析対象ノードに関する解析を行い、前記解析対象ノードに関連する情報を取得する、
解析方法。
【請求項８】
解析対象プログラムと、前記解析対象プログラム内の処理の複数の手続きを複数のノードで表し、手続き間の複数の呼び出し関係を複数のエッジで表したコールグラフとを記憶する記憶部と、
前記コールグラフに基づいて、前記複数のノードそれぞれについて、前記複数のエッジを呼び出し元から呼び出し先へ辿ることで自ノードへ到達可能な他ノードの数を示す到達可能ノード数を取得し、前記複数のノードそれぞれを、前記到達可能ノード数に基づいた順番で解析対象ノードとして選定し、前記コールグラフに基づいて選定された前記解析対象ノードに関する解析を行い、前記解析対象ノードに関連する情報を取得する処理部と、
を有する解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、解析プログラム、解析方法、および解析装置に関する。
【背景技術】
【０００２】
ソフトウェアの開発において、作成されているプログラムのソースコードの解析を行うことがある。ソースコード解析では、例えばコールグラフが用いられる。コールグラフは、コンピュータプログラムのサブルーチン同士の呼び出し関係を表現した有向グラフである。コールグラフのノードが、処理の手続きを表現し、エッジが手続き間の呼び出しを示す。
【０００３】
コールグラフを用いて解析を行うコンピュータは、コールグラフ内のあるノードの情報を得る場合、そのノードから呼び出し先を辿ることで到達可能な他のすべてのノードの情報を取得する。なお、解析の過程で、解析対象のノードからの新たな呼び出し先のノードの存在が判明することがある。この場合、コンピュータは、呼び出し関係を呼び出し元から呼び出し先に辿ることで解析対象のノードに到達可能なノードについては、すでに解析済であっても再度解析を行うこととなる。また、コールグラフには閉路が存在し得る。閉路が存在する場合、コンピュータは、コールグラフ内の一部のノードについては何度も繰り返し解析することで、正しい情報を得ることができる。
【０００４】
コールグラフを用いた解析技術としては、例えばシステムプロセスのソースコードを構文解析するリバースエンジニアリングによって出力された物理モデルのコールグラフなどから論理モデルのユースケースを抽出するシステム分析方法が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２−１０８６０７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
コールグラフのノード数が増加すると、ノード間の呼び出し関係が複雑化し、個々のノードの解析回数も増加する。そのため、コールグラフに含まれるノード数の増加に伴い、解析するノードの延べ数が著しく増大する。その結果、コールグラフを用いた解析には多大な時間がかかる。
【０００７】
１つの側面では、本発明は、コールグラフを用いた解析時間を短縮することを目的とする。
【課題を解決するための手段】
【０００８】
１つの案では、以下の処理をコンピュータに実行させる解析プログラムが提供される。
コンピュータは、解析対象プログラム内の処理の複数の手続きを複数のノードで表し、手続き間の複数の呼び出し関係を複数のエッジで表したコールグラフに基づいて、複数のノードそれぞれについて、複数のエッジを呼び出し元から呼び出し先へ辿ることで自ノードへ到達可能な他ノードの数を示す到達可能ノード数を取得する。次にコンピュータは、複数のノードそれぞれを、到達可能ノード数に基づいた順番で解析対象ノードとして選定する。そしてコンピュータは、コールグラフに基づいて選定された解析対象ノードに関する解析を行い、解析対象ノードに関連する情報を取得する。
【発明の効果】
【０００９】
１態様によれば、コールグラフを用いた解析時間を短縮することができる。
【図面の簡単な説明】
【００１０】
【図１】第１の実施の形態に係る解析装置の機能構成例を示す図である。
【図２】第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。
【図３】ソースコードに示されるメソッド間の呼び出し関係の一例を示す図である。
【図４】コールグラフの一例を示す図である。
【図５】ノード間の“情報”の伝搬を説明する図である。
【図６】解析順による解析回数の違いを示す図である。
【図７】概算到達可能ノード数の算出例を示す図である。
【図８】プログラム解析機能の構成例を示す図である。
【図９】メモリ内に設けられた記憶機能の一例を示す図である。
【図１０】プログラム解析処理の手順を示すフローチャートである。
【図１１】ノード選定処理の手順の一例を示すフローチャートである。
【図１２】要解析ノード選定処理の手順の一例を示すフローチャートである。
【図１３】安定性判定処理の手順の一例を示すフローチャートである。
【図１４】コールグラフ構築処理の手順の一例を示すフローチャートである。
【図１５】ノード解析処理の手順の一例を示すフローチャートの前半である。
【図１６】ノード解析処理の手順の一例を示すフローチャートの後半である。
【図１７】再解析通知処理の手順の一例を示すフローチャートである。
【図１８】ノード更新処理の手順の一例を示すフローチャートである。
【図１９】未解析ノード登録処理の手順の一例を示すフローチャートである。
【図２０】要解析ノード登録処理の手順の一例を示すフローチャートである。
【図２１】解析結果出力処理の手順の一例を示すフローチャートである。
【図２２】ソースコードから生成されるコールグラフの一例を示す図である。
【図２３】各格納部内の情報の遷移の例を示す図である。
【図２４】初期状態から２周目までのコールグラフの構築・探索状況の一例を示す図である。
【図２５】３周目と４周目のコールグラフの構築・探索状況の一例を示す図である。
【図２６】５周目と６周目のコールグラフの構築・探索状況の一例を示す図である。
【図２７】７周目と８周目のコールグラフの構築・探索状況の一例を示す図である。
【図２８】９周目と１０周目のコールグラフの構築・探索状況の一例を示す図である。
【図２９】１１周目と１２周目のコールグラフの構築・探索状況の一例を示す図である。
【図３０】１３周目と１４周目のコールグラフの構築・探索状況の一例を示す図である。
【図３１】１５周目と１６周目のコールグラフの構築・探索状況の一例を示す図である。
【図３２】１７周目のコールグラフの構築・探索状況の一例を示す図である。
【図３３】解析画面例を示す図である。
【図３４】第２の実施の形態におけるノード選定方式と未解析優先方式との総計算時間の比較結果を示す図である。
【発明を実施するための形態】
【００１１】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
図１は、第１の実施の形態に係る解析装置の機能構成例を示す図である。解析装置１０は、記憶部１１と処理部１２とを有している。記憶部１１は、例えば解析装置１０が有するメモリまたはストレージ装置である。処理部１２は、例えば解析装置１０が有するプロセッサである。
【００１２】
記憶部１１は、解析対象プログラム１とコールグラフ２とを記憶する。解析対象プログラム１は、例えば高級言語で記述されたソースコードである。コールグラフ２は、解析対象プログラム１内の処理の複数の手続きを複数のノードで表し、手続き間の複数の呼び出し関係を複数のエッジで表した有向グラフである。処理の手続きは、例えば関数やメソッドである。
【００１３】
処理部１２は、コールグラフ２に基づいて、複数のノードそれぞれについて、複数のエッジを呼び出し元から呼び出し先へ辿ることで自ノードへ到達可能な他ノードの数を示す到達可能ノード数を取得する。例えば処理部１２は、複数のノードそれぞれに対応付けて、自ノードへ到達可能な他ノードのノード識別子が登録された到達可能ノード集合を設けておく。そして処理部１２は、複数のノードそれぞれの到達可能ノード集合に登録されたノード識別子の数を、複数のノードそれぞれの到達可能ノード数として取得する。
【００１４】
なお、各ノードの到達可能ノード集合は、例えばそのノードに対してエッジで直接接続された隣接ノードの情報を調査して判明する範囲での到達可能ノードのノードＩＤを含んでいるものでよい。この場合、到達可能ノード集合に基づいて得られる到達可能ノード数は概算値となる。到達可能ノード数を概算値でよいものとすることで、到達可能ノードの探索処理負荷が軽減される。
【００１５】
到達可能ノード数を取得後、処理部１２は、複数のノードそれぞれを、到達可能ノード数に基づいた順番で解析対象ノードとして選定する。例えば処理部１２は、到達可能ノード数が多いノードほど優先的に解析対象ノードとして選定する。例えば処理部１２は、解析対象ノードを選定する指標が、到達可能ノード数を含めて複数あるとき、到達可能ノード数以外の指標に差異がないノード間において、到達可能ノード数が多いノードを先に解析対象ノードとして選定する。
【００１６】
解析対象ノードを選定後、処理部１２は、コールグラフ２に基づいて、選定された解析対象ノードに関する解析を行い、解析対象ノードに関連する情報を取得する。例えば処理部１２は、取得した情報を、解析対象ノードに関連付けて保持する。また処理部１２は、解析対象ノードから複数のエッジを辿ることで到達可能な新たな呼び出し先ノードが検出されると、新たな呼び出し先ノードの到達可能ノード集合に、解析対象ノードの到達可能ノード集合に含まれるノード識別子を追加する。
【００１７】
このように、到達可能ノード数が多いノードを優先的に解析することで、情報が変更されたときの影響範囲が広いノードを先に解析することができる。その結果、呼び出し先のノードの情報が変更されることにより再解析を行うこととなるノードの発生確率を低くすることができ、解析するノードの延べ数が抑制される。その結果、解析時間が短縮される。
【００１８】
なお、処理部１２は、コールグラフ２内の各ノードの状態を判定し、その状態に応じて解析対象ノードを選定することもできる。例えば処理部１２は、複数のノードのうち、一度も解析を行っていないノードの状態を未解析状態と判定する。また処理部１２は、少なくとも１度解析が行われ、自ノードの最後の解析後に、自ノードにエッジで接続された隣接ノードの情報が更新されたノードの状態を要解析状態と判定する。そして処理部１２は、解析対象ノードの選定において、未解析状態のノードを、要解析状態のノードよりも先に解析対象ノードとして選定する。このように、未解析状態のノードを優先的に解析することで、情報が変更される可能性が高いノードほど先に解析され、再解析の発生回数を抑止することができる。
【００１９】
また処理部１２は、ノードの状態の判定において、複数のノードのうち、未解析状態と要解析状態とのいずれでもないノードを解析済状態と判定することもできる。このとき処理部１２は、解析対象ノードの選定において、要解析状態のノードのうち、自ノードからの直接の呼び出し先のノードのすべてが解析済状態であるノードを、情報が安定的であると判定する。そして処理部１２は、情報が安定的な要解析状態のノードを、情報が安定的でない要解析状態のノードよりも先に解析対象ノードとして選定する。これにより、情報が変更される可能性が高いノードほど先に解析され、再解析の発生回数を抑止することができる。
【００２０】
さらに、処理部１２は、コールグラフ２の構築と、コールグラフ２を用いた解析とを並行して実施することもできる。この場合、処理部１２は、解析対象プログラム１に基づいて、選定された解析対象ノードに対応する手続きから呼び出される他の手続きの有無を解析する。そして処理部１２は、呼び出し先の手続きに対応するノードがコールグラフ２内に存在しないとき、呼び出し先の手続きに対応するノードをコールグラフ２に追加する。ノードを追加したとき、処理部１２は、追加したノードを、呼び出し元のノードからエッジで接続する。
【００２１】
処理部１２は、未解析ノードかどうか、安定ノードかどうか、および到達可能ノード数の内の１つ以上を組み合わせて、解析対象ノードを選定することができる。図１の例では、以下のような手順で解析処理を行っている。
【００２２】
処理部１２は、まず、すべてのノードの状態が解析済かどうかを判定する（ステップＳ１１）。すべてのノードの状態が解析済であれば、解析処理は終了する。解析済の状態になっていないノードが少なくとも１つ存在すれば、処理部１２は、未解析ノードがあるか否かを判定する（ステップＳ１２）。未解析ノードがある場合、処理部１２は、到達可能ノード数が最大の未解析ノードのうちの１つを、解析対象ノードとして選定する（ステップＳ１３）。
【００２３】
未解析ノードがない場合、処理は、安定ノード（呼び出し先がすべて解析済の要解析ノード）があるか否かを判定する（ステップＳ１４）。安定ノードがある場合、処理部１２は、到達可能ノード数が最大の安定ノードのうちの１つを、解析対象ノードとして選定する（ステップＳ１５）。安定ノードがない場合、処理部１２は、到達可能ノード数が最大の要解析ノードのうちの１つを、解析対象ノードとして選定する（ステップＳ１６）。
【００２４】
解析対象ノードを選定後、処理部１２は、選定した解析対象ノードを解析する（ステップＳ１７）。処理部１２は、解析によって解析対象ノードに関する情報を取得する。例えば解析対象ノードからエッジを呼び出し先方向に辿って到達可能なノードのリスト（呼び出し先ノード集合）や、エッジを呼び出し先方向に辿って解析対象ノードに到達可能なノードのリスト（到達可能ノード集合）が、情報として取得される。解析を行うと、処理部１２は、解析対象ノードの状態を解析済に変更する。
【００２５】
解析後、処理部１２は、解析によって解析対象ノードの情報が変化したか否かを判定する（ステップＳ１８）。例えば処理部１２は、解析対象ノードからの呼び出し先のノード（エッジを呼び出し先方向に辿って到達可能なノード）が変化した場合、情報が変化したものと判定する。情報が変化した場合、処理部１２は、解析対象ノードの呼び出しを行う呼び出し元ノードの状態を要解析に変更する（ステップＳ１９）。
【００２６】
そして処理部１２は、解析対象ノードから直接呼び出される呼び出し先ノードの到達可能ノードを更新する（ステップＳ２０）。例えば処理部１２は、解析対象ノードの到達可能ノード集合に含まれるノード識別子を、直接の呼び出し先のノードの到達可能ノードの集合に追加する。その後、処理部１２は、処理をステップＳ１１に進め、すべてのノードが解析済状態になるまで、上記の処理を繰り返す。
【００２７】
このような処理により、未解析ノード優先、安定ノード優先、および到達可能ノード数が大きいノード優先を組み合わせて、適切な解析対象ノードの選定を行うことができる。例えば図１に示したコールグラフ２であれば、未解析状態のノード「Ｄ」とノード「Ｇ」が存在し、ノード「Ｄ」の到達可能ノード数は「２」であり、ノード「Ｇ」の到達可能ノード数は「１」である。そこで、到達可能ノード数が最大の未解析ノードであるノード「Ｄ」が、次の解析対象ノードとして選定される。このような選定を繰り返すことで、解析時間を大幅に短縮することができる。
【００２８】
〔第２の実施の形態〕
次に第２の実施の形態について説明する。
図２は、第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。コンピュータ１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１には、バス１０９を介してメモリ１０２と複数の周辺機器が接続されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、またはＤＳＰ（Digital Signal Processor）である。プロセッサ１０１がプログラムを実行することで実現する機能の少なくとも一部を、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現してもよい。
【００２９】
メモリ１０２は、コンピュータ１００の主記憶装置として使用される。メモリ１０２には、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０２には、プロセッサ１０１による処理に必要な各種データが格納される。メモリ１０２としては、例えばＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置が使用される。
【００３０】
バス１０９に接続されている周辺機器としては、ストレージ装置１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、機器接続インタフェース１０７およびネットワークインタフェース１０８がある。
【００３１】
ストレージ装置１０３は、内蔵した記録媒体に対して、電気的または磁気的にデータの書き込みおよび読み出しを行う。ストレージ装置１０３は、コンピュータの補助記憶装置として使用される。ストレージ装置１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、ストレージ装置１０３としては、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）を使用することができる。
【００３２】
グラフィック処理装置１０４には、モニタ２１が接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令に従って、画像をモニタ２１の画面に表示させる。モニタ２１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００３３】
入力インタフェース１０５には、キーボード２２とマウス２３とが接続されている。入力インタフェース１０５は、キーボード２２やマウス２３から送られてくる信号をプロセッサ１０１に送信する。なお、マウス２３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００３４】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２４に記録されたデータの読み取りを行う。光ディスク２４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００３５】
機器接続インタフェース１０７は、コンピュータ１００に周辺機器を接続するための通信インタフェースである。例えば機器接続インタフェース１０７には、メモリ装置２５やメモリリーダライタ２６を接続することができる。メモリ装置２５は、機器接続インタフェース１０７との通信機能を搭載した記録媒体である。メモリリーダライタ２６は、メモリカード２７へのデータの書き込み、またはメモリカード２７からのデータの読み出しを行う装置である。メモリカード２７は、カード型の記録媒体である。
【００３６】
ネットワークインタフェース１０８は、ネットワーク２０に接続されている。ネットワークインタフェース１０８は、ネットワーク２０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００３７】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示した装置も、図２に示したコンピュータ１００と同様のハードウェアにより実現することができる。
【００３８】
コンピュータ１００は、例えばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。コンピュータ１００に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、コンピュータ１００に実行させるプログラムをストレージ装置１０３に格納しておくことができる。プロセッサ１０１は、ストレージ装置１０３内のプログラムの少なくとも一部をメモリ１０２にロードし、プログラムを実行する。またコンピュータ１００に実行させるプログラムを、光ディスク２４、メモリ装置２５、メモリカード２７などの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１０１からの制御により、ストレージ装置１０３にインストールされた後、実行可能となる。またプロセッサ１０１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００３９】
コンピュータ１００は、ソースコードに基づいて、ソースコード内のメソッド間の呼び出し関係を示すコールグラフを生成する。そしてコンピュータ１００は、生成したコールグラフを利用して、ソースコードに示されるプログラムを解析する。プログラムの解析では、例えばオブジェクトの状態変化、オブジェクトへの依存の検出などが行われる。
【００４０】
以下、ソースコードがオブジェクト指向のプログラミング言語で記述されている場合を想定し、ソースコードから生成されるコールグラフについて説明する。
図３は、ソースコードに示されるメソッド間の呼び出し関係の一例を示す図である。ソースコードには、例えば複数のクラス３１〜３３が定義されている。クラス３１〜３３内には、メソッドを呼び出す記述が含まれる。メソッドでは、他のメソッドを呼び出し、呼び出した先のメソッドの実行結果を利用して、呼び出し元のメソッドを実行することができる。例えばクラス３１内に示されるメソッド「ｍ１」から、クラス３２内に示されるメソッド「ｍ２」が呼び出されている。このようなメソッド間の呼び出し関係があることで、図３の例では、「ｍ１（）」を呼び出すと、「Ａ．ｂ，Ａ．ｃ，Ｂ．ｓ，Ｃ．ｘ」の値が変わる可能性がある。また「ｍ１（）」の実行結果（返り値）は「Ａ．ｉ」の値に依存する。
【００４１】
このようにメソッドを介して、各クラスが影響を及ぼし合っている。例えば、オブジェクトの状態変化やオブジェクトへの依存を検出したい場合、メソッド間の呼び出し関係を解析することとなる。すなわち、メソッド間の呼び出し関係の解析は、プログラム理解支援やレビュー強化に活用できると期待できる。ただし、あるメソッドの解析結果が別のメソッドに波及し得るため、同じメソッドを複数回解析することとなり、プログラムの解析に時間がかかる。
【００４２】
あるメソッドの解析結果の影響が、どのメソッドに波及するのかを調査するのに、コールグラフが用いられる。
図４は、コールグラフの一例を示す図である。コールグラフ４０は、ソースコード３４内に示されている手続きを示すモジュール（メソッドや関数など）を示すノード４１と、モジュール間の呼び出し関係を示すエッジ４２を含んでいる。
【００４３】
コールグラフ４０は、データ表記４０ａ上は、「コールグラフＧ＝（Ｖ，Ｅ）」と表される。Ｖは ノード（メソッドや関数）の集合であり、データ表示上は「Ｖ＝｛ｍ１，ｍ２，ｍ３｝」と表される。Ｅはエッジ（呼び出し関係）の集合（Ｅ⊆Ｖ×Ｖ）であり、データ表記上は「Ｅ＝｛（ｍ１，ｍ１），（ｍ１，ｍ２），（ｍ１，ｍ３），（ｍ２，ｍ３），（ｍ３，ｍ２）」と表される。
【００４４】
なお、第２の実施の形態におけるコールグラフ４０のエッジ４２には、オーバーライド関係を表すエッジを含むものとする。オーバーライドとは、スーパークラスで定義されたメソッドをサブクラスで定義しなおし、動作を上書きすることである。オーバーライド関係を表すエッジは、オーバーライドされる側からする側への矢印で表される。コールグラフ４０にオーバーライドを示すエッジを含めることで、オーバーライドを含めた解析を行うことができる。
【００４５】
ここで、ソースコード解析において、コールグラフを構築・探索して、例えばあるノードの情報を取得する場合を考える。以下、ノードの情報を“情報”と表し、他の一般的な情報と区別する。
【００４６】
コールグラフ「Ｇ＝（Ｖ，Ｅ）」の分析により取得する“情報”としては、例えば、ステップ数、出現する変数などがある。図３の例であれば、「ｍ１（）」について「変更する変数」の“情報”を取得すると、「Ａ．ｂ，Ａ．ｃ，Ｂ．ｓ，Ｃ．ｘ」という結果が得られる。また「ｍ１（）」について「依存する変数」の“情報”を取得すると、「Ａ．ｉ」という結果が得られる。
【００４７】
ここで、取得対象の“情報”に示される値の数は、有限であるものとする。“情報”に示される値の数が有限であることで、探索問題の停止性を保証される。
コールグラフを用いた探索において、１つのノードを複数回解析することとなる原因の１つは、あるノードから別のノードへ「“情報”」が伝搬し得る点である。
【００４８】
図５は、ノード間の“情報”の伝搬を説明する図である。図５の例において、ソースコード３５を解析して、ノード「ｍ２」のステップ数を得たいものとする。ソースコード３５では、メソッド「ｍ２」がメソッド「ｍ１」を呼び出している。そのためコールグラフ４３において、ノード「ｍ２」からノード「ｍ１」へのエッジが存在する（ｉ．ｅ．（ｍ２，ｍ１）∈Ｅ）。
【００４９】
この場合、コンピュータ１００は、ノード「ｍ１」のステップ数もノード「ｍ２」のステップ数に計上する。すなわち、ノード「ｍ１」からノード「ｍ２」に“情報”の伝搬が発生している。逆にノード「ｍ２」からノード「ｍ１」への“情報”の伝搬はないものとして取り扱う。呼び出し元のノードから呼び出し先のノードへの“情報”伝搬が存在し得る問題も考えられるが、第２の実施の形態では、解析の対象外とする。
【００５０】
なおコンピュータ１００は、コールグラフの構築と探索を同時並行的に実施することができる。初期状態では、いくつかのノード（起点）の存在だけが明らかになっているものとする。存在が明らかとなっている各ノードを解析することで、そのノードの１つ先のノードの存在が判明する。
【００５１】
このようなコールグラフの構築並びに探索を同時並行的に行うコールグラフ構築・探索問題では、ノード数の増加に伴い解析されるノードの述べ数が著しく増大する。ここで、「次にどのノードを解析するか」を選定する方式を工夫することで、ノードの解析回数を抑制し、結果的に所要時間が短縮されると期待できる。
【００５２】
以下図６を参照して、ノードの選定順と解析回数との関係について説明する。
図６は、解析順による解析回数の違いを示す図である。解析順の善し悪しを分かりやすくするため、極めて単純なコールグラフ４４を考える。コールグラフ４４では、Ｎ（Ｎは１以上の整数）個のノードを有する。コールグラフ４４の各ノードは、左側のノードから呼び出され、右側のノードを呼び出す。左端のノードが起点であり、右端のノードが末尾である。
【００５３】
このようなコールグラフ４４の生成元となるソースコードを解析する場合、最適な解析順は、起点のノードから順に呼び出し先を辿りながら解析を進めていき、末尾のノードに到達したら、１つずつ呼び出し元に戻ってくるという順番である。このような順番でノードを選定して解析を行うと、末尾のノードのみ１度の解析で済み、それ以外は２度解析を行うことから、解析回数は「Ｎ＋（Ｎ−１）＝２Ｎ−１」となる。これは、オーダ表記で「Ｏ（Ｎ）」と表される。
【００５４】
他方、最悪な解析順は、逐次起点に戻りながら解析するという順番である。このような順番でノードを選定して解析を行うと、解析回数は「１＋２＋３＋・・・＋Ｎ＝Ｎ（Ｎ＋１）／２」となる。これはオーダ表記で「Ｏ（Ｎ2）」と表される。
【００５５】
このように、解析対象とするノードの選定順が異なれば、ノードを解析する回数も異なる。このことから、適切な順番でノードを選定すれば、解析回数を削減できることが理解できる。
【００５６】
従来のノードの選定方式としては、例えば、条件を満たすノードの中から解析するノードをランダムに選定する手法（ランダム方式）がある。ランダム方式では、無駄な解析が多く、処理に要する時間が著しく大きい。そこで、未解析のノードがあればその中から、なければそれ以外のノードから解析するノードをランダムに選定する手法（未解析優先方式）が考えられる。未解析優先方式は、ランダム方式よりは無駄な解析が抑制されるが、処理に要する時間は依然として大きい。
【００５７】
このように、従来のノード選定方式では、ノードの解析回数の削減効果が不十分である。そこで、ランダム方式や未解析優先方式より適切なノード選定方式について検討する。
適切なノード選定方式は、不要な解析の回数を抑え、合計処理時間の削減につなげることができるノード選定方式である。なお、このノード選定方式を用いて得られる結果が、従来のノード選定方式と同一であることが前提となる。
【００５８】
また、第２の実施の形態では、ノードの解析回数を最小にするノード選定方式ではなく、適切と思われるノードを、少ない計算量で選定できるノード選定方式を採用する。すなわち、コンピュータ１００は、適切なノードの選定を、なるべく簡単な処理で実現する。これは、より複雑な選定処理を行えば、より適切なノードを選定できる可能性があるが、選定処理に要するオーバーヘッドが大きくなり、全体の処理時間の短縮効果が薄れるためである。
【００５９】
複雑な処理で最もいいものを選ぶのではなく、簡単な処理でよさそうなものを選ぶために、第２の実施の形態では、以下の３つの指標を利用する。
１．ノードの状態（未解析なのか要解析なのか）
２．ノードに到達可能なノードの数
３．ノードが安定であるか否か
以下、３つの指標について詳細に説明する。
【００６０】
［指標１（ノードの状態）について］
指標１のノードの状態とは、解析対象となるノードが取り得る状態であり、未解析状態と要解析状態とがある。未解析状態のノードは、そのノードの存在は判明しているが、一度も解析していないノードである。未解析状態のノードからの呼び出し先に、他のノードが存在するか否かは未知である。
【００６１】
要解析状態のノードは、そのノードを一度以上解析したが、そこから先の“情報”の変化に伴い再解析を要するノードである。要解析状態のノードからの呼び出し先のノードは既知である。
【００６２】
第２の実施の形態では、コールグラフ構築・探索問題では、コールグラフの構築と探索を同時に行う。そのため、一部しか判明していないサブグラフ内の探索を優先して、サブグラフ内の“情報”を確定させても、後でグラフの全体像が明らかになったときにその“情報”に変化が生じる可能性がある。そこでコールグラフの構築処理を優先的に行った方が、ノードの解析回数を削減できる。そこでコンピュータ１００は、要解析状態のノードよりも未解析状態のノードを先に選定し、解析を行う。
【００６３】
［指標２（ノードに到達可能なノードの数）について］
あるノードの到達可能ノード数は、コールグラフのエッジの向きに沿って辿ったとき、そのノードに辿りつくことができるノードの数である。到達可能ノード数は、自分自身を除いて数えられる。到達可能ノード数が大きいほど自身の“情報”が変化したときに影響を受けるノードが多い。そこでコンピュータ１００は、到達可能ノード数が多いノードほど、解析対象として優先的に選定する。
【００６４】
ただし、コールグラフの規模が大きくなると、到達可能ノード数の算出に時間がかかる場合がある。そこで第２の実施の形態では、到達可能ノード数の概算値（概算到達可能ノード数）を用いる。
【００６５】
図７は、概算到達可能ノード数の算出例を示す図である。図７の例では、ノード４５を解析することで、ノード４５からノード４６へのエッジ４７が生成されたものとする。このとき、ノード４５に到達可能なすべてのノードは、ノード４６にも到達可能であるため、ノード４６の概算到達可能ノード数が更新される。同様にノード４６に到達可能なすべてのノードは、ノード４６から呼び出される他のノードにも到達可能である。しかし、概算到達可能ノード数の計算では、ノード４６から呼び出される他のノードの概算到達可能ノード数は更新されない。正確な到達可能ノード数を用いた方がより適切なノードを選定できる可能性はあるが、正確な到達可能ノード数の計算時間を勘案し、第２の実施の形態では、概算到達可能ノード数を用いる。
【００６６】
［指標３（ノードが安定であるか否か）について］
安定であるノードとは、そのノードから辿ることができるノードの状態が解析済状態となっているノードである。このようなノードは、そのノードから先では“情報”の変化が起きることがない、すなわち“情報”が安定している。安定したノードを解析すれば、以降そのノードを再解析する状況は生じない。
【００６７】
ノードの安定性の判別の際、あるノードが安定か否かを正確に判別するためには、そのノードから辿ることができるすべてのノードの状態を検査することとなる。しかしコールグラフが大規模になると、対象のすべてのノードの状態を検査するのは処理負荷が過大となる。そこで、第２の実施の形態では、安定性判別対象のノードからの直接の呼び出し先のノードの状態がすべて解析済ならば、安定性判別対象のノードは安定であると定義する。すなわち、コンピュータ１００は、安定性判別対象のノードに隣接したノードの“情報”のみから、おおよその安定性を判別する。これにより、判定に要する処理時間を抑えることができる。
【００６８】
以上説明した３つの指標を用いてノードを選定することで、プログラム解析時に、適切なノード選定を効率的に行うことができる。
次に、コンピュータ１００における、コールグラフ構築・探索を含むプログラム解析機能について説明する。
【００６９】
図８は、プログラム解析機能の構成例を示す図である。コンピュータ１００は、記憶機能として、ソースコード格納部１１１、コールグラフ格納部１１２、未解析ノード格納部１１３、要解析ノード格納部１１４、およびノード詳細情報格納部１１５を有する。
【００７０】
ソースコード格納部１１１は、図３などに示したような、複数のメソッドの呼び出し関係を有するソースコードを記憶する。ソースコード格納部１１１は、例えばメモリ１０２またはストレージ装置１０３を用いて実現される。
【００７１】
コールグラフ格納部１１２、未解析ノード格納部１１３、要解析ノード格納部１１４、およびノード詳細情報格納部１１５は、例えばプログラム解析時にメモリ１０２内に設けられる記憶領域によって実現される記憶機能である。
【００７２】
図９は、メモリ内に設けられた記憶機能の一例を示す図である。コールグラフ格納部１１２には、ノードの集合（Nodes）とエッジの集合（Edges）とが格納される。ノードの集合には、存在が確認できた手続きを示すモジュール（メソッドや関数など）に対応するノードの識別子が含まれる。エッジの集合には、手続き間の呼び出し関係に対応するエッジが含まれる。各エッジは、呼び出し元のノードの識別子と呼び出し先のノードの識別子との対で表される。
【００７３】
未解析ノード格納部１１３には、未解析状態のノード（未解析ノード）の識別子が、そのノードへの到達可能ノード数別で格納される。
要解析ノード格納部１１４には、要解析状態のノード（要解析ノード）の識別子が、そのノードへの到達可能ノード数別で格納される。
【００７４】
ノード詳細情報格納部１１５には、ノードごとに、そのノードへの到達可能ノードの識別子の集合と、呼び出し先ノードの識別子の集合とが格納される。
図９の例では、コールグラフ格納部１１２、未解析ノード格納部１１３、要解析ノード格納部１１４、およびノード詳細情報格納部１１５を、メモリ１０２が有するものとしているが、これらのうちの少なくとも一部を、ストレージ装置１０３内に設けてもよい。また各格納部で格納するデータの一部をストレージ装置１０３に格納することもできる。
【００７５】
図８の説明に戻る。コンピュータ１００は、処理機能として、解析制御部１２１、ノード選定部１２２、安定性判定部１２３、コールグラフ構築部１２４、ノード解析部１２５、再解析通知部１２６、ノード更新部１２７、未解析ノード登録部１２８、要解析ノード登録部１２９、および解析結果出力部１３０を有する。
【００７６】
解析制御部１２１は、プログラム解析全体を制御する。ノード選定部１２２は、コールグラフから解析対象のノードを選定する。安定性判定部１２３は、ノードの安定性を判定する。コールグラフ構築部１２４は、ソースコードに基づいてコールグラフを構築する。ノード解析部１２５は、ノードに対応するモジュールを解析する。再解析通知部１２６は、解析済となったノードのうち再度解析するノードを、要解析ノード登録部１２９に通知する。ノード更新部１２７は、各ノードの詳細情報を更新する。未解析ノード登録部１２８は、未解析ノードを未解析ノード格納部１１３に登録する。要解析ノード登録部１２９は、再度解析する要解析ノードを、要解析ノード格納部１１４に登録する。解析結果出力部１３０は、解析結果を出力する。
【００７７】
なお、図８に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、図８に示した各要素の機能は、例えば、その要素に対応するプログラムモジュールをコンピュータに実行させることで実現することができる。
【００７８】
次に、コンピュータ１００が実行する処理について、具体的に説明する。
図１０は、プログラム解析処理の手順を示すフローチャートである。プログラム解析処理は、解析の起点となるノードの集合を含む解析要求の入力に応じて実行開始される。またプログラム解析処理の結果として、コールグラフ「Ｇ＝（Ｖ，Ｅ）」とノードの“情報”「Ｉｎｆｏ（ｖ）（ｖ∈Ｖ）」とが出力される。以下、図１０に示す処理をステップ番号に沿って説明する。
【００７９】
［ステップＳ１０１］解析制御部１２１は、ノード選定部１２２を用いて、解析対象ノードを選定する。例えば解析制御部１２１は、ノード選定部１２２に対して、解析対象ノードの選定要求を送信する。するとノード選定部１２２により解析対象ノードが選定される。ノード選定部１２２は選定した解析対象ノードの識別子を出力する。解析対象ノードが存在しない場合、ノード選定部１２２は「ＮＵＬＬ」を出力する。解析制御部１２１は、ノード選定部１２２から、選定されたノードの識別子を取得する。
【００８０】
［ステップＳ１０２］解析制御部１２１は、解析対象ノードがあるか否かを判断する。例えば解析制御部１２１は、ノード選定部１２２の出力が「ＮＵＬＬ」以外であれば、解析対象ノードがあると判断する。解析対象ノードがある場合、解析制御部１２１は、処理をステップＳ１０４に進める。解析対象ノードがない場合、解析制御部１２１は、処理をステップＳ１０３に進める。
【００８１】
［ステップＳ１０３］解析制御部１２１は、解析結果出力部１３０を用いて解析の結果を出力する。例えば解析制御部１２１は、解析結果出力部１３０に対して、解析結果の出力要求を送信する。すると解析結果出力部１３０は、例えばノード詳細情報格納部１１５から解析結果データを取得して、解析結果をモニタ２１に出力する。
【００８２】
［ステップＳ１０４］解析制御部１２１は、選定された解析対象ノードが未解析ノードか否かを判断する。例えば解析制御部１２１は、未解析ノード格納部１１３を参照し、解析対象ノードの識別子が未解析ノード格納部１１３に格納されている場合、未解析ノードであると判断する。解析制御部１２１は、未解析ノードであれば、処理をステップＳ１０５に進める。また解析制御部１２１は、未解析ノードでなければ、処理をステップＳ１０６に進める。
【００８３】
［ステップＳ１０５］解析制御部１２１は、コールグラフ構築部１２４を用いて、解析対象ノードからの呼び出し先ノードをコールグラフ格納部１１２に登録する。例えば解析制御部１２１は、コールグラフ構築部１２４に、解析対象ノードの識別子を含むコールグラフ登録要求を送信する。コールグラフ登録要求に応じてコールグラフ構築部１２４で未解析ノードが解析され、呼び出し先ノードがコールグラフ格納部１１２に登録される。
【００８４】
［ステップＳ１０６］解析制御部１２１は、ノード解析部１２５を用いてノードの解析を実施する。例えば解析制御部１２１は、ノード解析部１２５に、解析対象ノードの識別子を含むノード解析要求を送信する。するとノード解析部１２５により、解析対象ノードに付与される“情報”（ノード詳細情報への登録内容）や、“情報”の変化の有無が解析される。
【００８５】
［ステップＳ１０７］解析制御部１２１は、ノード解析部１２５の解析結果に基づいて、解析前後で解析対象ノード（ｖ）の呼び出し先ノード（Ｉｎｆｏ（ｖ））が変化したか否かを判断する。呼び出し先ノードが変化した場合、解析制御部１２１は、処理をステップＳ１０８に進める。呼び出し先ノードが変化していない場合、解析制御部１２１は、処理をステップＳ１０９に進める。
【００８６】
［ステップＳ１０８］解析制御部１２１は、再解析通知部１２６を用いて、解析対象ノードの呼び出し元ノードの状態を、要解析状態に変更する。例えば解析制御部１２１は、再解析通知部１２６に、解析対象ノードの識別子を含む再解析設定要求を送信する。すると、再解析通知部１２６により、解析対象ノードの呼び出し元ノードの状態が、要解析状態に変更される。
【００８７】
［ステップＳ１０９］解析制御部１２１は、ノード更新部１２７を用いて、解析対象ノードの呼び出し先ノードの到達可能ノード集合を更新する。例えば解析制御部１２１は、ノード更新部１２７に対して、解析対象ノードの識別子を含むノード更新要求を送信する。するとノード更新部１２７により、ノード詳細情報格納部１１５における解析対象ノードの呼び出し先ノードの到達可能ノード集合が更新される。その後、解析制御部１２１は、処理をステップＳ１０１に進める。
【００８８】
このようにして、解析制御部１２１の制御のもと、コールグラフ構築・探索を伴うプログラム解析が実行され、解析結果を得ることができる。
次に、解析制御部１２１からの要求に応じて実行される処理について詳細に説明する。まず、ノード選定部１２２によるノード選定処理について説明する。
【００８９】
図１１は、ノード選定処理の手順の一例を示すフローチャートである。ノード選定部１２２は、解析制御部１２１からの解析対象ノードの選定要求に応じてノード選定処理を開始する。ノード選定部１２２は、ノード選定処理に当たり、到達可能ノード別に分類された未解析ノード群と要解析ノード群とを、それぞれ未解析ノード格納部１１３と要解析ノード格納部１１４とから取得する。ノード選定部１２２は、ノード選定処理の結果、次に解析すべきノード（解析対象ノード）の識別子を出力する。以下、図１１に示す処理をステップ番号に沿って説明する。
【００９０】
［ステップＳ１２１］ノード選定部１２２は、未解析ノード格納部１１３内に未解析ノードがあるか否かを判断する。例えばノード選定部１２２は、未解析ノード格納部１１３内のいずれかの到達可能ノード数に対応する未解析ノードの集合が空集合でなければ、未解析ノードがあると判断する。ノード選定部１２２は、未解析ノードがある場合、処理をステップＳ１２２に進める。またノード選定部１２２は、未解析ノードがない場合、処理をステップＳ１２５に進める。
【００９１】
［ステップＳ１２２］ノード選定部１２２は、未解析ノード格納部１１３から、到達可能ノード数が最大のノードを１つ選定する。
［ステップＳ１２３］ノード選定部１２２は、未解析ノード格納部１１３から、選定したノードの識別子を削除する。
【００９２】
［ステップＳ１２４］ノード選定部１２２は、選定したノードの識別子を、解析対象ノードの識別子として出力する。その後、ノード選定処理が終了する。
［ステップＳ１２５］ノード選定部１２２は、要解析ノード格納部１１４に要解析ノードがあるか否かを判断する。例えばノード選定部１２２は、要解析ノード格納部１１４内のいずれかの到達可能ノード数に対応する要解析ノードの集合が空集合でなければ、要解析ノードがあると判断する。ノード選定部１２２は、要解析ノードがある場合、処理をステップＳ１２７に進める。またノード選定部１２２は、要解析ノードがない場合、処理をステップＳ１２６に進める。
【００９３】
［ステップＳ１２６］ノード選定部１２２は、ノード選定結果として「ＮＵＬＬ」を出力する。その後、ノード選定処理が終了する。
［ステップＳ１２７］ノード選定部１２２は、要解析ノード選定処理を実行する。要解析ノード選定処理において、要解析ノードのうちの１つが解析対象ノードとして選定され、その解析対象ノードの識別子が出力される。
【００９４】
図１２は、要解析ノード選定処理の手順の一例を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。
［ステップＳ１３１］ノード選定部１２２は、要解析ノード格納部１１４から、到達可能ノード数が最大のノードを１つ仮選定する。
【００９５】
［ステップＳ１３２］ノード選定部１２２は、安定性判定部１２３を用いて、仮選定したノードが安定ノードか否かを判断する。例えばノード選定部１２２は、安定性判定部１２３に対して、仮選定したノード（安定性判定対象ノード）の識別子を含む安定性判定要求を送信する。安定性判定要求に応じて、安定性判定部１２３により、安定性対象ノードが安定か否かが判定される。安定性判定部１２３は、安定であると判定した場合「ＴＲＵＥ」を出力し、安定ではないと判定した場合「ＦＡＬＳＥ」を出力する。ノード選定部１２２は、安定性判定部１２３の出力値に基づいて、仮選定したノードが安定か否かを判断できる。ノード選定部１２２は、仮選定したノードが安定であれば、処理をステップＳ１３３に進める。またノード選定部１２２は、仮選定したノードが安定でなければ、処理をステップＳ１３４に進める。
【００９６】
［ステップＳ１３３］ノード選定部１２２は、仮選定したノードを出力ノードとして選定する。その後、ノード選定部１２２は処理をステップＳ１４１に進める。
［ステップＳ１３４］ノード選定部１２２は、要解析ノード格納部１１４内の仮選定したノードの識別子に対して、検査済みとマークする。このマークは、要解析ノード選定処理内でのみ使用される局所的なフラグである。その後、ノード選定部１２２は、仮選定したノードの識別子をメモリ１０２に退避する。
【００９７】
［ステップＳ１３５］ノード選定部１２２は、要解析ノード格納部１１４内に未検査の要解析ノードがあるか否かを判断する。ノード選定部１２２は、未検査の要解析ノードがあれば、処理をステップＳ１３７に進める。またノード選定部１２２は、未検査の要解析ノードがなければ、処理をステップＳ１３６に進める。
【００９８】
［ステップＳ１３６］ノード選定部１２２は、メモリ１０２に退避していた識別子に対応するノードを、出力ノードとして選定する。その後、ノード選定部１２２は、処理をステップＳ１４１に進める。
【００９９】
［ステップＳ１３７］ノード選定部１２２は、要解析ノード格納部１１４から、到達可能ノード数が最大のノードのうち、未検査のノードを１つ仮選定する。未検査のノードとは、ノードの識別子に検査済みのマークが付与されていないノードである。
【０１００】
［ステップＳ１３８］ノード選定部１２２は、安定性判定部１２３を用いて、仮選定したノードが安定ノードか否かを判断する。ノード選定部１２２は、仮選定したノードが安定であれば、処理をステップＳ１４０に進める。またノード選定部１２２は、仮選定したノードが安定でなければ、処理をステップＳ１３９に進める。
【０１０１】
［ステップＳ１３９］ノード選定部１２２は、要解析ノード格納部１１４内の仮選定したノードの識別子に対して、検査済みとマークする。その後、ノード選定部１２２は、処理をステップＳ１３５に進める。
【０１０２】
［ステップＳ１４０］ノード選定部１２２は、仮選定したノードを出力ノードとして選定する。その後、ノード選定部１２２は処理をステップＳ１４１に進める。
［ステップＳ１４１］ノード選定部１２２は、要解析ノード格納部１１４から、出力ノードとして選定したノードの識別子を削除する。
【０１０３】
［ステップＳ１４２］ノード選定部１２２は、出力ノードとして選定したノードの識別子を、解析対象ノードの識別子として出力する。その後、要解析ノード選定処理が終了する。
【０１０４】
図１１、図１２に示した処理によって、要解析ノードよりも未解析ノードが、解析対象ノードとして優先的に選定される。また未解析ノード同士では、到達可能ノード数が大きいノード程、解析対象ノードとして優先的に選定される。未解析ノード同士では、安定ノードのうち到達可能ノード数が最も大きいノードが、解析対象ノードとして優先的に選定される。未解析ノード内に安定ノードがなければ、未解析ノードのうち到達可能ノード数が最も大きいノードが、解析対象ノードとして優先的に選定される。
【０１０５】
次に安定性判定部１２３による安定性判定処理について詳細に説明する。
図１３は、安定性判定処理の手順の一例を示すフローチャートである。安定性判定部１２３は、安定性判定対象ノードの識別子を含む安定性判定要求に応じて安定性判定処理を開始する。安定性判定処理の結果、安定性判定対象ノードが安定か否かを示す値を出力する。以下、図１３に示す処理をステップ番号に沿って説明する。
【０１０６】
［ステップＳ１５１］安定性判定部１２３は、コールグラフ格納部１１２から、安定性判定対象ノードの呼び出し先ノードの識別子をすべて取得する。
［ステップＳ１５２］安定性判定部１２３は、取得した識別子で示されるノードに、未検査の呼び出し先ノードがあるか否かを判断する。未検査のノードとは、ノードの識別子に検査済みのマークが付与されていないノードである。取得したノードの識別子に付与される検査済みのマークは、安定性判定処理の中でのみ使われる局所的なフラグである。安定性判定部１２３は、未検査の呼び出し先ノードがあれば、処理をステップＳ１５４に進める。また安定性判定部１２３は、未検査の呼び出し先ノードがなければ、処理をステップＳ１５３に進める。
【０１０７】
［ステップＳ１５３］安定性判定部１２３は、安定性判定対象ノードが安定であることを示す情報「ＴＲＵＥ」を出力し、安定性判定処理を終了する。
［ステップＳ１５４］安定性判定部１２３は、ステップＳ１５１で取得した識別子で示されるノードの中から未検査の呼び出し先ノードを１つ選定し、そのノードの識別子に検査済みとマークする。
【０１０８】
［ステップＳ１５５］安定性判定部１２３は、選定したノードの状態が解析済か否かを判断する。例えば安定性判定部１２３は、選定したノードの識別子が、要解析ノード格納部１１４に登録されていない場合、そのノードは解析済であると判断する。安定性判定部１２３は、解析済であれば、処理をステップＳ１５２に進める。安定性判定部１２３は、解析済でなければ、処理をステップＳ１５６に進める。
【０１０９】
［ステップＳ１５６］安定性判定部１２３は、安定性判定対象ノードが安定でないことを示す情報「ＦＡＬＳＥ」を出力し、安定性判定処理を終了する。
このような安定性判定処理により、安定性判定対象ノードの呼び出し先ノードが、すべて解析済状態であれば、安定性判定対象ノードは安定であると判断される。安定性判定対象ノードの呼び出し先ノードのうち、解析済でない状態のノードが少なくとも１つでもあれば、安定性判定対象ノードは安定でないと判断される。
【０１１０】
次に、コールグラフ構築部１２４によるコールグラフ構築処理について詳細に説明する。
図１４は、コールグラフ構築処理の手順の一例を示すフローチャートである。コールグラフ構築部１２４は、未解析の解析対象ノードの識別子を含むコールグラフ登録要求に応じてコールグラフ構築処理を開始する。コールグラフ構築部１２４は、コールグラフ構築処理の結果、呼び出し先ノードの集合および呼び出しエッジの集合を出力する。出力した値は、コールグラフ格納部１１２に登録される。以下、図１４に示す処理をステップ番号に沿って説明する。
【０１１１】
［ステップＳ１６１］コールグラフ構築部１２４は、解析対象ノードを分析し、呼び出し先ノードをすべて特定する。例えばコールグラフ構築部１２４は、ソースコード格納部１１１から、ソースコード内の解析対象ノードに対応するモジュールを取得する。そしてコールグラフ構築部１２４は、取得したモジュール内の記述を解析し、他のメソッドまたは関数を呼び出す命令に基づいて、呼び出し先のノードを特定する。
【０１１２】
［ステップＳ１６２］コールグラフ構築部１２４は、未処理の呼び出し先ノードがあるか否かを判断する。未処理のノードとは、ノードの識別子に検査済みのマークが付与されていないノードである。取得したノードの識別子に付与される検査済みのマークは、コールグラフ構築処理の中でのみ使われる局所的なフラグである。コールグラフ構築部１２４は、未処理の呼び出し先ノードがある場合、処理をステップＳ１６３に進める。またコールグラフ構築部１２４は、未処理の呼び出し先ノードがない場合、コールグラフ構築処理を終了する。
【０１１３】
［ステップＳ１６３］コールグラフ構築部１２４は、未処理の呼び出し先ノードを１つ選定し、そのノードの識別子に処理済みとマークする。
［ステップＳ１６４］コールグラフ構築部１２４は、コールグラフ格納部１１２を参照し、選定したノードがコールグラフに登録済みか否かを判断する。コールグラフ構築部１２４は、選定したノードが登録済みであれば、処理をステップＳ１６６に進める。またコールグラフ構築部１２４は、選定したノードが未登録であれば、処理をステップＳ１６５に進める。
【０１１４】
［ステップＳ１６５］コールグラフ構築部１２４は、選定したノードをコールグラフ格納部１６５に登録する。
［ステップＳ１６６］コールグラフ構築部１２４は、解析対象ノードと選定したノードとを結ぶエッジを作成し、コールグラフ格納部１１２に登録する。その後、コールグラフ構築部１２４は、処理をステップＳ１６２に進める。
【０１１５】
このようにして、未解析のノードを解析する際に、コールグラフの構築処理が行われる。
次に、ノード解析部１２５によるノード解析処理について詳細に説明する。
【０１１６】
図１５は、ノード解析処理の手順の一例を示すフローチャートの前半である。ノード解析部１２５は、解析対象ノードの識別子を含むノード解析要求に応じて、ノード解析処理を開始する。ノード解析部１２５は、ノード解析処理の結果、解析対象ノードに付与される“情報”と、その“情報”が解析前後で変化したか否かを示す値とを出力する。以下、図１５に示す処理をステップ番号に沿って説明する。
【０１１７】
［ステップＳ１７１］ノード解析部１２５は、ノード詳細情報格納部１１５から、解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））を取得し、取得した呼び出し先ノード（Ｉｎｆｏ（ｖ））をメモリ１０２に退避する。
【０１１８】
［ステップＳ１７２］ノード解析部１２５は、解析対象ノードを分析し、解析対象ノードから得られる呼び出し先ノード（Ｉｎｆｏ（ｖ））を特定する。
［ステップＳ１７３］ノード解析部１２５は、コールグラフ格納部１１２から、呼び出し先ノードをすべて取得する。
【０１１９】
［ステップＳ１７４］ノード解析部１２５は、未処理の呼び出し先ノードがあるか否かを判断する。未処理の呼び出し先ノードとは、ノードの識別子に検査済みのマークが付与されていない呼び出し先ノードである。取得したノードの識別子に付与される検査済みのマークは、ノード解析処理の中でのみ使われる局所的なフラグである。ノード解析部１２５は、未処理の呼び出し先ノードがある場合、処理をステップＳ１７５に進める。またノード解析部１２５は、未処理の呼び出し先ノードがない場合、処理をステップＳ１８１（図１６参照）に進める。
【０１２０】
［ステップＳ１７５］ノード解析部１２５は、未処理の呼び出し先ノードを１つ選定し、そのノードの識別子に処理済みとマークする。
［ステップＳ１７６］ノード解析部１２５は、選定したノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））をノード詳細情報格納部１７６から取得する。
【０１２１】
［ステップＳ１７７］ノード解析部１２５は、選定したノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））を、解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））として付与する。例えばノード解析部１２５は、選定したノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））のうち、解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））に含まれていないノードの識別子を特定する。そしてノード解析部１２５は、特定したノードの識別子を、解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））のリストに追加する。その後、ノード解析部１２５は、処理をステップＳ１７４に進める。
【０１２２】
図１６は、ノード解析処理の手順の一例を示すフローチャートの後半である。以下、図１６に示す処理をステップ番号に沿って説明する。
［ステップＳ１８１］ノード解析部１２５は、解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））を、ノード詳細情報格納部１１５に格納する。
【０１２３】
［ステップＳ１８２］ノード解析部１２５は、解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））を、メモリ１０２に退避しておいた呼び出し先ノード（Ｉｎｆｏ（ｖ））と比較する。
【０１２４】
［ステップＳ１８３］ノード解析部１２５は、解析前後で解析対象ノードの呼び出し先ノード（Ｉｎｆｏ（ｖ））が変化したか否かを判断する。ノード解析部１２５は、変化がある場合、処理をステップＳ１８４に進める。またノード解析部１２５は、変化がない場合、処理をステップＳ１８５に進める。
【０１２５】
［ステップＳ１８４］ノード解析部１２５は、“情報”が解析前後で変化したか否かを示す値として、変化したことを示す「ＴＲＵＥ」を出力する。その後、ノード解析部１２５は、処理をステップＳ１８６に進める。
【０１２６】
［ステップＳ１８５］ノード解析部１２５は、“情報”が解析前後で変化したか否かを示す値として、変化していないことを示す「ＦＡＬＳＥ」を出力する。
［ステップＳ１８６］ノード解析部１２５は、解析対象ノードの状態を解析済に設定する。例えばノード解析部１２５は、未解析ノード格納部１１３または要解析ノード格納部１１４から、管理対象ノードの識別子を削除する。その後、ノード解析部１２５は、ノード解析処理を終了する。
【０１２７】
このようにして、解析対象ノードが解析され、解析対象ノードの呼び出し先ノードが更新されるとともに、処理結果として、解析前後での呼び出し先ノードの変化の有無が出力される。
【０１２８】
次に、再解析通知部１２６による再解析通知処理について詳細に説明する。
図１７は、再解析通知処理の手順の一例を示すフローチャートである。再解析通知部１２６は、解析対象ノードの識別子を含む再解析設定要求に応じて再解析通知処理を開始する。再解析通知部１２６は、再解析通知処理の結果、呼び出し元ノードの状態を要解析状態へ変更すると共に、ノード詳細情報格納部１１５へ到達可能ノードを登録する。以下、図１７に示す処理をステップ番号に沿って説明する。
【０１２９】
［ステップＳ１９１］再解析通知部１２６は、コールグラフ格納部１１２から、解析対象ノードの呼び出し元ノードの識別子をすべて取得する。
［ステップＳ１９２］再解析通知部１２６は、未処理の呼び出し元ノードがあるか否かを判断する。未処理の呼び出し元ノードとは、ノードの識別子に検査済みのマークが付与されていない呼び出し元ノードである。取得したノードの識別子に付与される検査済みのマークは、再解析通知処理の中でのみ使われる局所的なフラグである。再解析通知部１２６は、未処理の呼び出し元ノードがある場合、処理をステップＳ１９３に進める。また再解析通知部１２６は、未処理の呼び出し元ノードがない場合、再解析通知処理を終了する。
【０１３０】
［ステップＳ１９３］再解析通知部１２６は、未処理の呼び出し元ノードを１つ選定し、そのノードの識別子に処理済みとマークする。
［ステップＳ１９４］再解析通知部１２６は、選定したノードの状態が未解析であるか否かを判断する。例えば再解析通知部１２６は、選定したノードの識別子が未解析ノード格納部１１３に格納されている場合、状態が未解析であると判断する。再解析通知部１２６は、状態が未解析の場合、処理をステップＳ１９２に進める。また再解析通知部１２６は、状態が未解析でなければ、処理をステップＳ１９５に進める。
【０１３１】
［ステップＳ１９５］再解析通知部１２６は、選定したノードの状態を要解析に設定する。
［ステップＳ１９６］再解析通知部１２６は、要解析ノード登録部１２９を用いて、選定したノードを要解析ノード格納部１１４へ登録する。その後、再解析通知部１２６は、処理をステップＳ１９２に進める。
【０１３２】
このようにして、再度解析するべきノードの状態を、要解析に設定することができる。
次に、ノード更新部１２７によるノード更新処理について詳細に説明する。
図１８は、ノード更新処理の手順の一例を示すフローチャートである。ノード更新部１２７は、解析対象ノードの識別子を含むノード更新要求に応じてノード更新処理を開始する。ノード更新部１２７は、ノード更新処理の結果、呼び出し先ノードの到達可能ノード集合を更新する。
【０１３３】
［ステップＳ２０１］ノード更新部１２７は、コールグラフ格納部１１２から、解析対象ノードの呼び出し先ノードをすべて取得する。
［ステップＳ２０２］ノード更新部１２７は、未処理の呼び出し先ノードがあるか否かを判断する。未処理の呼び出し先ノードとは、ノードの識別子に検査済みのマークが付与されていない呼び出し先ノードである。取得したノードの識別子に付与される検査済みのマークは、ノード更新処理の中でのみ使われる局所的なフラグである。ノード更新部１２７は、未処理の呼び出し先ノードがあれば、処理をステップＳ２０３に進める。またノード更新部１２７は、未処理の呼び出し先ノードがなければ、ノード更新処理を終了する。
【０１３４】
［ステップＳ２０３］ノード更新部１２７は、未処理の呼び出し先ノードを１つ選定し、そのノードの識別子に処理済みとマークする。
［ステップＳ２０４］ノード更新部１２７は、選定したノードの到達可能ノード集合と解析対象ノードの到達可能ノード集合とを、ノード詳細情報格納部１１５から取得する。
【０１３５】
［ステップＳ２０５］ノード更新部１２７は、選定したノードの到達可能ノード集合に、解析対象ノードと、解析対象ノードの到達可能ノード集合のすべての要素とを追加する。
【０１３６】
［ステップＳ２０６］ノード更新部１２７は、選定したノードの到達可能ノード集合を、ノード詳細情報格納部１１５に登録する。
［ステップＳ２０７］ノード更新部１２７は、選定したノードの状態を判断する。ノード更新部１２７は、選定したノードが解析済の状態であれば、処理をステップＳ２０２に進める。ノード更新部１２７は、選定したノードが要解析の状態であれば、処理をステップＳ２０８に進める。ノード更新部１２７は、選定したノードが未解析の状態であれば、処理をステップＳ２０９に進める。
【０１３７】
［ステップＳ２０８］ノード更新部１２７は、要解析ノード登録部１２９を用い、選定したノードを要解析ノード格納部１１４へ登録する。例えばノード更新部１２７は、選定したノード（登録対象ノード）の識別子を含む要解析ノード登録要求を、要解析ノード登録部１２９に送信する。その後、ノード更新部１２７は処理をステップＳ２０２に進める。
【０１３８】
［ステップＳ２０９］ノード更新部１２７は、未解析ノード登録部１２８を用い、選定したノードを未解析ノード格納部１１３へ登録する。例えばノード更新部１２７は、選定したノード（登録対象ノード）の識別子を含む未解析ノード登録要求を、未解析ノード登録部１２８に送信する。その後、ノード更新部１２７は処理をステップＳ２０２に進める。
【０１３９】
次に、未解析ノード登録部１２８による未解析ノード登録処理について詳細に説明する。
図１９は、未解析ノード登録処理の手順の一例を示すフローチャートである。未解析ノード登録部１２８は、登録対象ノードの識別子を含む未解析ノード登録要求に応じて未解析ノード登録処理を開始する。未解析ノード登録部１２８は、未解析ノード登録処理の結果、登録対象ノードを未解析ノード格納部１１３へ登録する。以下、図１９に示す処理をステップ番号に沿って説明する。
【０１４０】
［ステップＳ２２１］未解析ノード登録部１２８は、ノード詳細情報格納部１１５から登録対象ノードの到達可能ノード集合を取得し、その要素数を計数する。
［ステップＳ２２２］未解析ノード登録部１２８は、登録対象ノードが未解析ノード格納部１１３に登録済みか否かを判断する。例えば未解析ノード登録部１２８は、未解析ノード格納部１１３を参照し、登録対象ノードの識別子が、到達可能ノード数別の未解析ノード集合のいずれかに含まれている場合、登録済みであると判断する。未解析ノード登録部１２８は、登録対象ノードが登録済みであれば、処理をステップＳ２２３に進める。また未解析ノード登録部１２８は、登録対象ノードが未登録であれば、処理をステップＳ２２４に進める。
【０１４１】
［ステップＳ２２３］未解析ノード登録部１２８は、未解析ノード格納部１１３から、登録対象ノードを削除する。
［ステップＳ２２４］未解析ノード登録部１２８は、未解析ノード格納部１１３から、ステップＳ２２１で計数した要素数（到達可能ノード数）に対応する未解析ノード集合を取得する。
【０１４２】
［ステップＳ２２５］未解析ノード登録部１２８は、取得した未解析ノード集合に登録対象ノードの識別子を要素として追加し、その未解析ノード集合を、未解析ノード格納部１１３内の元の位置に書き戻す。その後、未解析ノード登録部１２８は、未解析ノード登録処理を終了する。
【０１４３】
次に、要解析ノード登録部１２９による要解析ノード登録処理の手順について詳細に説明する。
図２０は、要解析ノード登録処理の手順の一例を示すフローチャートである。要解析ノード登録部１２９は、登録対象ノードの識別子を含む要解析ノード登録要求に応じて要解析ノード登録処理を開始する。要解析ノード登録部１２９は、要解析ノード登録処理の結果、登録対象ノードを要解析ノード格納部１１４へ登録する。以下、図２０に示す処理をステップ番号に沿って説明する。
【０１４４】
［ステップＳ２３１］要解析ノード登録部１２９は、ノード詳細情報格納部１１５から登録対象ノードの到達可能ノード集合を取得し、その要素数を計数する。
［ステップＳ２３２］要解析ノード登録部１２９は、登録対象ノードが要解析ノード格納部１１４に登録済みか否かを判断する。例えば要解析ノード登録部１２９は、要解析ノード格納部１１４を参照し、登録対象ノードの識別子が、到達可能ノード数別の要解析ノード集合のいずれかに含まれている場合、登録済みであると判断する。要解析ノード登録部１２９は、登録対象ノードが登録済みであれば、処理をステップＳ２３３に進める。また要解析ノード登録部１２９は、登録対象ノードが未登録であれば、処理をステップＳ２３４に進める。
【０１４５】
［ステップＳ２３３］要解析ノード登録部１２９は、要解析ノード格納部１１４から、登録対象ノードを削除する。
［ステップＳ２３４］要解析ノード登録部１２９は、要解析ノード格納部１１４から、ステップＳ２３１で計数した要素数（到達可能ノード数）に対応する要解析ノード集合を取得する。
【０１４６】
［ステップＳ２３５］要解析ノード登録部１２９は、取得した要解析ノード集合に登録対象ノードの識別子を要素として登録し、その要解析ノード集合を、要解析ノード格納部１１４内の元の位置に書き戻す。その後、要解析ノード登録部１２９は、要解析ノード登録処理を終了する。
【０１４７】
次に、解析結果出力部１３０による解析結果出力処理について詳細に説明する。
図２１は、解析結果出力処理の手順の一例を示すフローチャートである。解析結果出力部１３０は、解析結果の出力要求に応じて解析結果出力処理を開始する。解析結果出力部１３０は、解析結果出力処理の結果、ソースコードの解析結果をモニタ２１に表示する。以下、解析結果出力処理をステップ番号に沿って説明する。
【０１４８】
［ステップＳ２４１］解析結果出力部１３０は、コールグラフ格納部１１２内のコールグラフに基づいて、解析対象のソースコード中のすべてのメソッドを一覧表示する。
［ステップＳ２４２］解析結果出力部１３０は、利用者からの、１つのメソッドの選定入力を受け付ける。
【０１４９】
［ステップＳ２４３］解析結果出力部１３０は、利用者が何らかのメソッドを選定したか否かを判断する。解析結果出力部１３０は、選定入力が行われた場合、処理をステップＳ２４４に進める。解析結果出力部１３０は、選定入力が行われなかった場合、解析結果出力処理を終了する。選定入力が行われなかった場合とは、例えばメソッドが選定されずにメソッド一覧画面が閉じられた場合である。
【０１５０】
［ステップＳ２４４］解析結果出力部１３０は、ノード詳細情報格納部１１５から、選定されたメソッドの“情報”を取得し、取得した“情報”をモニタ２１に表示する。
［ステップＳ２４５］解析結果出力部１３０は、選定されたメソッドの“情報”を基に、そのメソッドに関連する別のメソッドを特定し、その一覧と詳細情報をモニタ２１に表示する。その後、解析結果出力部１３０は、処理をステップＳ２４２に進める。
【０１５１】
以上のようにして、コールグラフを用いたソースコードの解析を効率的に行うことができる。以下、コールグラフを用いた解析を、具体例を用いて説明する。
図２２は、ソースコードから生成されるコールグラフの一例を示す図である。図２２に示すコールグラフ５０は、８個のノードを有している。各ノードの識別子を「Ａ」〜「Ｈ」とする。ここで、コールグラフ５０が生成されるようなソースコードを、ノード「Ａ」とノード「Ｂ」とを起点として解析する場合を想定する。
【０１５２】
プログラム解析処理を開始直後は、各格納部には初期状態が設定され、ノードが１つずつ解析される。ノードが解析されるごとに、各格納部の内容が更新される。
図２３は、各格納部内の情報の遷移の例を示す図である。初期状態では、起点ノードのみが判明している。すなわちコールグラフ格納部１１２内に、起点となるノード「Ａ」、「Ｂ」が設定されている。ノード「Ａ」、「Ｂ」は未解析状態であり、呼び出し関係が不明である。呼び出し関係が不明の場合、ノード「Ａ」、「Ｂ」の到達可能ノード数は「０」となる。そこで、未解析ノード格納部１１３の到達可能ノード数「０」の未解析ノード集合に、ノード「Ａ」、「Ｂ」が登録されている。
【０１５３】
初期状態では、ノード「Ａ」とノード「Ｂ」とは、ノード選定処理における優劣がない。この場合、ノード選定部１２２は、次に解析するノードとしてノード「Ａ」とノード「Ｂ」とのどちらを選定してもよい。図２３の例では、ノード「Ａ」が先に選定され、解析されたものとする。
【０１５４】
ノード「Ａ」を解析することで、ノード「Ｃ」とノード「Ｇ」との存在が判明する。すなわち、ノード「Ａ」に対応するメソッドの解析により、そのメソッド内でノード「Ｃ」に対応するメソッドの呼び出しと、ノード「Ｇ」に対応するメソッドの呼び出しとが行われていることが判明する。その結果、コールグラフ格納部１１２には、ノード「Ｃ」、「Ｇ」が追加されると共に、エッジ（Ａ，Ｃ）、（Ａ，Ｇ）が追加される。
【０１５５】
新たに追加されたノード「Ｃ」、「Ｇ」は未解析状態であるが、それぞれの到達可能ノードとしてノード「Ａ」が存在していることが分かっている。そこで、未解析ノード格納部１１３の到達可能ノード数「１」の未解析ノード集合に、ノード「Ｃ」、「Ｇ」が登録されている。なおノード「Ａ」は解析されたことで解析済状態となり、未解析ノード格納部１１３から削除されている。
【０１５６】
またノード「Ａ」の解析により、ノード詳細情報格納部１１５も更新されている。例えば、ノード「Ｃ」の到達可能ノードとしてノード「Ａ」が設定されている。またノード「Ｇ」の到達可能ノードとしてノード「Ａ」が設定されている。さらにノード「Ａ」の呼び出し先ノードとしてノード「Ｃ」と「Ｇ」が設定されている。
【０１５７】
このようにノードが解析されるごとに、各格納部内の登録内容が更新される。更新された登録内容に基づいて、次に解析するノードを適切に選定することができる。例えば図２３の例では、未解析状態のノードのうち、ノード「Ｃ」と「Ｇ」は到達可能ノード数が「１」であるが、ノード「Ｂ」は到達可能ノード数が「０」である。そこでノード選定部１２２は、ノード「Ｃ」と「Ｇ」のどちらかを、次に解析するノードとして選定する。
【０１５８】
このような解析対象のノードの選定と、ノードの解析結果に応じた登録内容の更新とを交互に繰り返すことで、コールグラフが生成されていくと共に、ノード詳細情報格納部１１５に各ノードの詳細情報が格納されていく。そしてすべてのノードが解析済状態になったときにノード詳細情報格納部１１５に登録されている“情報”が、解析結果となる。
【０１５９】
以下、図２４〜図３２を参照して、コールグラフの構築・探索の様子を具体的に説明する。以下の説明では、図１０に示したステップＳ１０１〜Ｓ１０９の１回ずつの処理を１周とし、繰り返し処理の進捗状況を、何周目の処理なのかで表すこととする。また図２４〜図３２では、未解析状態のノードを網掛けの円で示し、要解析のノードを黒塗りの円で示し、解析済のノードを白抜きの円で示す。さらに図２４〜図３２では、各ノードの近くに、そのノードの到達可能ノード（Reachable）と呼び出し先ノード（Info）とを示す。
【０１６０】
図２４は、初期状態から２周目までのコールグラフの構築・探索状況の一例を示す図である。初期状態では、起点ノードであるノード「Ａ」とノード「Ｂ」とがコールグラフに示されている。最初の解析対象ノードとしてノード「Ａ」とノード「Ｂ」とのいずれも選定可能であるが、図２４の例ではノード「Ａ」が選定され、１周目の解析が実行されたものとする。
【０１６１】
１周目（ノード「Ａ」の解析）の処理後、コールグラフにはノード「Ｃ」とノード「Ｇ」とが追加されると共に、これらのノードへのノード「Ａ」からのエッジが追加されている。ノード「Ａ」の呼び出し先ノードには、ノード「Ｃ」とノード「Ｇ」とが追加されている。ノード「Ｃ」の到達可能ノードには、ノード「Ａ」が追加されている。ノード「Ｇ」の到達可能ノードには、ノード「Ａ」が追加されている。ノード「Ａ」は、状態が未解析から解析済に変更されている。
【０１６２】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２４の例では、ノード「Ｃ」とノード「Ｇ」の到達可能ノード数が「１」で最大であり、この２つのノードのいずれかを選定可能である。ここで、ノード「Ｃ」が選定され、２周目の解析が実行されたものとする。
【０１６３】
２周目（ノード「Ｃ」の解析）の処理後、コールグラフにはノード「Ｄ」が追加されると共に、これらのノードへのノード「Ｃ」からのエッジが追加されている。ノード「Ｃ」の呼び出し先ノードには、ノード「Ｄ」が追加されている。ノード「Ｄ」の到達可能ノードには、ノード「Ｄ」の呼び出しを行うノード「Ｃ」に加え、ノード「Ｃ」の到達可能ノードに設定されているノード「Ａ」が追加されている。ノード「Ｃ」は、状態が未解析から解析済に変更されている。ノード「Ｃ」を解析した結果、ノード「Ｃ」の持つ“情報”に変化が生じたため、ノード「Ａ」の状態が解析済から要解析に変更されている。
【０１６４】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２４の例では、ノード「Ｄ」の到達可能ノード数が「２」で最大であるため、ノード「Ｄ」が選定され、３周目の解析が実行される。
【０１６５】
図２５は、３周目と４周目のコールグラフの構築・探索状況の一例を示す図である。３周目（ノード「Ｄ」の解析）の処理後、コールグラフにはノード「Ｅ」とノード「Ｆ」が追加されると共に、これらのノードへのノード「Ｄ」からのエッジが追加されている。ノード「Ｄ」の呼び出し先ノードには、ノード「Ｅ」とノード「Ｆ」が追加されている。ノード「Ｅ」の到達可能ノードには、ノード「Ｆ」の呼び出しを行うノード「Ｄ」に加え、ノード「Ｄ」の到達可能ノードに設定されているノード「Ａ」とノード「Ｃ」が追加されている。ノード「Ｆ」の到達可能ノードには、ノード「Ｆ」の呼び出しを行うノード「Ｄ」に加え、ノード「Ｄ」の到達可能ノードに設定されているノード「Ａ」とノード「Ｃ」が追加されている。ノード「Ｄ」は、状態が未解析から解析済に変更されている。ノード「Ｄ」を解析した結果、ノード「Ｄ」の持つ“情報”に変化が生じたため、ノード「Ｃ」の状態が解析済から要解析に変更されている。
【０１６６】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２５の例では、ノード「Ｅ」とノード「Ｆ」の到達可能ノード数が「３」で最大であり、この２つのノードのいずれかを選定可能である。ここで、ノード「Ｅ」が選定され、４周目の解析が実行されたものとする。
【０１６７】
４周目（ノード「Ｅ」の解析）の処理後、コールグラフにはノード「Ｅ」からノード「Ｃ」へのエッジが追加されている。ノード「Ｅ」の呼び出し先ノードには、ノード「Ｅ」が直接呼び出すノード「Ｃ」に加え、ノード「Ｃ」の呼び出し先ノードに設定されているノード「Ｄ」が追加されている。ノード「Ｃ」の到達可能ノードには、ノード「Ｃ」の呼び出しを行うノード「Ｅ」に加え、ノード「Ｅ」の到達可能ノードに設定されているノード「Ｄ」が追加されている。ノード「Ｅ」は、状態が未解析から解析済に変更されている。ノード「Ｅ」を解析した結果、ノード「Ｅ」の持つ“情報”に変化が生じたため、ノード「Ｄ」の状態が解析済から要解析に変更されている。
【０１６８】
なお４周目では、ノード「Ｃ」の到達可能ノードにノード「Ｄ」とノード「Ｅ」が追加されたため、到達可能ノードの設定を正確に行うのであれば、ノード「Ｄ」やノード「Ｆ」についても、到達可能ノードにノード「Ｄ」とノード「Ｅ」が追加されることとなる。ただし、到達可能ノードの設定を正確に行おうとすると、コールグラフの規模が大きくなったとき、呼び出し関係の追跡範囲が膨大となり、処理負荷が大きくなりすぎる。そこで第２の実施の形態では、コンピュータ１００は概略的に到達可能ノードの設定を行っている。すなわち、解析対象ノードに隣接するノードしか到達可能ノードの更新を行わない。これにより、到達可能ノードの設定処理を効率化でき、コールグラフの構築・探索処理の効率化が図れる。
【０１６９】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２５の例では、ノード「Ｆ」の到達可能ノード数が「３」で最大であるため、ノード「Ｆ」が選定され、５周目の解析が実行される。
【０１７０】
図２６は、５周目と６周目のコールグラフの構築・探索状況の一例を示す図である。５周目（ノード「Ｆ」の解析）の処理後、コールグラフに変更はない。また各ノードの“情報”も変更されていない。ノード「Ｆ」は、状態が未解析から解析済に変更されている。
【０１７１】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２６の例では、ノード「Ｇ」の到達可能ノード数が「１」で最大であるため、ノード「Ｇ」が選定され、６周目の解析が実行される。
【０１７２】
６周目（ノード「Ｇ」の解析）の処理後、コールグラフにはノード「Ｈ」が追加されると共に、ノード「Ｇ」からノード「Ｈ」へのエッジが追加されている。ノード「Ｇ」の呼び出し先ノードには、ノード「Ｈ」が追加されている。ノード「Ｈ」の到達可能ノードには、ノード「Ｈ」の呼び出しを行うノード「Ｇ」に加え、ノード「Ｇ」の到達可能ノードに設定されているノード「Ａ」が追加されている。ノード「Ｇ」は、状態が未解析から解析済に変更されている。
【０１７３】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２６の例では、ノード「Ｈ」の到達可能ノード数が「２」で最大であるため、ノード「Ｈ」が選定され、７周目の解析が実行される。
【０１７４】
図２７は、７周目と８周目のコールグラフの構築・探索状況の一例を示す図である。７周目（ノード「Ｈ」の解析）の処理後、コールグラフにはノード「Ｈ」からノード「Ｅ」へのエッジが追加されている。ノード「Ｈ」の呼び出し先ノードには、ノード「Ｈ」から直接呼び出すノード「Ｅ」に加え、ノード「Ｅ」の呼び出し先ノードに設定されているノード「Ｃ」とノード「Ｄ」が追加されている。ノード「Ｅ」の到達可能ノードには、ノード「Ｅ」の呼び出しを行うノード「Ｈ」に加え、ノード「Ｈ」の到達可能ノードに設定されているノード「Ｇ」が追加されている。ノード「Ｈ」は、状態が未解析から解析済に変更されている。
【０１７５】
次の解析対象ノードは、未解析ノードのうち、到達可能ノード数が最大のノードの中から選ばれる。図２７の例では、未解析ノードがノード「Ｂ」のみであるため、ノード「Ｂ」が選定され、８周目の解析が実行される。
【０１７６】
８周目（ノード「Ｂ」の解析）の処理後、コールグラフにはノード「Ｂ」からノード「Ｄ」へのエッジが追加されている。ノード「Ｂ」の呼び出し先ノードには、ノード「Ｂ」から直接呼び出すノード「Ｄ」に加え、ノード「Ｄ」の呼び出し先ノードに設定されているノード「Ｅ」とノード「Ｆ」が追加されている。ノード「Ｄ」の到達可能ノードには、ノード「Ｂ」が追加されている。ノード「Ｂ」は、状態が未解析から解析済に変更されている。
【０１７７】
以上の処理により、未解析状態のノードがなくなっている。従って、呼び出し関係で辿ることができるすべてのノードがコールグラフに含まれており、コールグラフは完成している。また要解析ノードの中に安定ノードはない。そこで、次の解析対象ノードは、要解析ノードの中から選ばれる。図２７の例では、要解析ノードのうち、ノード「Ｄ」の呼び出し先ノードはノード「Ｅ」とノード「Ｆ」であり、これらのノードはいずれも解析済である。またノード「Ｇ」の呼び出し先ノードはノード「Ｈ」のみであり、このノード「Ｈ」は解析済である。従って、ノード「Ｄ」とノード「Ｇ」は共に安定ノードになっている。ノード「Ｄ」の到達可能ノード数は「３」であり、ノード「Ｇ」の到達可能ノード数は「１」である。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｄ」が、次の解析対象ノードとして選定され、９周目の処理が実行される。
【０１７８】
図２８は、９周目と１０周目のコールグラフの構築・探索状況の一例を示す図である。９周目（ノード「Ｄ」の解析）の処理後、ノード「Ｄ」の呼び出し先ノードには、ノード「Ｈ」の呼び出し先であるノード「Ｅ」の呼び出し先ノードに設定されているノード「Ｃ」が追加されている。ノード「Ｅ」の到達可能ノードには、ノード「Ｅ」の呼び出しを行うノード「Ｄ」の到達可能ノードに設定されているノード「Ｂ」が追加されている。ノード「Ｆ」の到達可能ノードには、ノード「Ｆ」の呼び出しを行うノード「Ｄ」の到達可能ノードに設定されているノード「Ｂ」が追加されている。ノード「Ｄ」は、状態が要解析から解析済に変更されている。
【０１７９】
９周目の処理が終わったとき、要解析ノードであるノード「Ｃ」の呼び出し先ノードはノード「Ｄ」のみであり、このノード「Ｄ」は解析済である。従って、ノード「Ｃ」は安定ノードになっている。ノード「Ｃ」の到達可能ノード数は「３」であり、以前より安定ノードとなっているノード「Ｇ」の到達可能ノード数「１」よりも多い。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｃ」が、次の解析対象ノードとして選定され、１０周目の処理が実行される。
【０１８０】
１０周目（ノード「Ｃ」の解析）の処理後、ノード「Ｃ」の呼び出し先ノードには、ノード「Ｃ」の呼び出し先であるノード「Ｄ」の呼び出し先ノードに設定されているノード「Ｃ」、ノード「Ｅ」、およびノード「Ｆ」が追加されている。ノード「Ｄ」の到達可能ノードには、ノード「Ｄ」の呼び出しを行うノード「Ｃ」の到達可能ノードに設定されているノード「Ｅ」が追加されている。ノード「Ｃ」は、状態が要解析から解析済に変更されている。ノード「Ｅ」は、呼び出し先であるノード「Ｃ」の“情報”が変更されたため、状態が解析済から要解析に変更されている。
【０１８１】
１０周目の処理が終わったとき、要解析ノードであるノード「Ｅ」の直接の呼び出し先ノードはノード「Ｃ」のみであり、このノード「Ｃ」は解析済である。従って、ノード「Ｅ」は安定ノードになっている。ノード「Ｅ」の到達可能ノード数は「６」であり、以前より安定ノードとなっているノード「Ｇ」の到達可能ノード数「１」よりも多い。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｅ」が、次の解析対象ノードとして選定され、１１周目の処理が実行される。
【０１８２】
図２９は、１１周目と１２周目のコールグラフの構築・探索状況の一例を示す図である。１１周目（ノード「Ｅ」の解析）の処理後、ノード「Ｅ」の呼び出し先ノードには、ノード「Ｅ」の呼び出し先であるノード「Ｃ」の呼び出し先ノードに設定されているノード「Ｅ」とノード「Ｆ」が追加されている。ノード「Ｃ」の到達可能ノードには、ノード「Ｃ」の呼び出しを行うノード「Ｅ」の到達可能ノードに設定されているノード「Ｂ」、ノード「Ｇ」、およびノード「Ｈ」が追加されている。ノード「Ｅ」は、状態が要解析から解析済に変更されている。ノード「Ｄ」とノード「Ｈ」は、呼び出し先であるノード「Ｅ」の“情報”が変更されたため、状態が解析済から要解析に変更されている。
【０１８３】
１１周目の処理が終わったとき、要解析ノードであるノード「Ｄ」の直接の呼び出し先ノードはノード「Ｅ」とノード「Ｆ」であり、これらのノードは共に解析済である。また要解析ノードであるノード「Ｈ」の呼び出し先ノードはノード「Ｅ」のみであり、このノード「Ｅ」は解析済である。従って、ノード「Ｄ」とノード「Ｈ」は安定ノードになっている。ノード「Ｄ」の到達可能ノード数は「４」であり、ノード「Ｈ」の到達可能ノード数は「２」である。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｄ」が、次の解析対象ノードとして選定され、１２周目の処理が実行される。
【０１８４】
１２周目（ノード「Ｄ」の解析）の処理後、ノード「Ｄ」の呼び出し先ノードには、ノード「Ｄ」の呼び出し先であるノード「Ｅ」の呼び出し先ノードに設定されているノード「Ｄ」が追加されている。ノード「Ｆ」の到達可能ノードには、ノード「Ｆ」の呼び出しを行うノード「Ｄ」の到達可能ノードに設定されているノード「Ｅ」が追加されている。ノード「Ｄ」は、状態が要解析から解析済に変更されている。
【０１８５】
１２周目の処理が終わったとき、要解析ノードであるノード「Ｂ」の直接の呼び出し先ノードはノード「Ｄ」のみであり、このノード「Ｄ」は解析済である。要解析ノードであるノード「Ｃ」の呼び出し先ノードはノード「Ｄ」のみであり、このノード「Ｄ」は解析済である。従って、ノード「Ｂ」とノード「Ｃ」は安定ノードになっている。ノード「Ｈ」は以前より安定ノードである。これらの安定ノードのうち、到達可能ノード数が最も多いのはノード「Ｃ」である。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｃ」が、次の解析対象ノードとして選定され、１３周目の処理が実行される。
【０１８６】
図３０は、１３周目と１４周目のコールグラフの構築・探索状況の一例を示す図である。１３周目（ノード「Ｃ」の解析）の処理後、ノード「Ｄ」の到達可能ノードには、ノード「Ｄ」の呼び出しを行うノード「Ｃ」の到達可能ノードに設定されているノード「Ｇ」とノード「Ｈ」が追加されている。ノード「Ｃ」は、状態が要解析から解析済に変更されている。
【０１８７】
１３周目の処理が終わったとき、要解析ノードのうちノード「Ｂ」とノード「Ｈ」が安定ノードである。これらの安定ノードのうち、到達可能ノード数が最も多いのはノード「Ｈ」である。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｈ」が、次の解析対象ノードとして選定され、１４周目の処理が実行される。
【０１８８】
１４周目（ノード「Ｈ」の解析）の処理後、ノード「Ｈ」の呼び出し先ノードには、ノード「Ｈ」の呼び出し先であるノード「Ｅ」の呼び出し先ノードに設定されているノード「Ｆ」が追加されている。ノード「Ｈ」は、状態が要解析から解析済に変更されている。
【０１８９】
１４周目の処理が終わったとき、要解析ノードのうちノード「Ｂ」とノード「Ｇ」が安定ノードである。これらの安定ノードのうち、到達可能ノード数が最も多いのはノード「Ｇ」である。そこで、安定ノードのうち到達可能ノード数が最大であるノード「Ｇ」が、次の解析対象ノードとして選定され、１５周目の処理が実行される。
【０１９０】
図３１は、１５周目と１６周目のコールグラフの構築・探索状況の一例を示す図である。１５周目（ノード「Ｇ」の解析）の処理後、ノード「Ｇ」の呼び出し先ノードには、ノード「Ｇ」の呼び出し先であるノード「Ｈ」の呼び出し先ノードに設定されているノード「Ｃ」、ノード「Ｄ」、ノード「Ｅ」、およびノード「Ｆ」が追加されている。ノード「Ｇ」は、状態が要解析から解析済に変更されている。
【０１９１】
１５周目の処理が終わったとき、要解析ノードのうちノード「Ａ」とノード「Ｂ」が安定ノードである。これらの安定ノードの到達可能ノード数は共に「０」である。従って、ノード「Ａ」とノード「Ｂ」のいずれのノードも、次の解析対象ノードとして選定可能である。図３１の例では、次の解析対象ノードとしてノード「Ａ」が選定され、１６周目の処理が実行されたものとする。
【０１９２】
１６周目（ノード「Ａ」の解析）の処理後、ノード「Ａ」の呼び出し先ノードには、ノード「Ａ」の呼び出し先であるノード「Ｃ」またはノード「Ｇ」の呼び出し先ノードに設定されているノードが追加される。追加されたノードは、ノード「Ｄ」、ノード「Ｅ」、ノード「Ｆ」、およびノード「Ｈ」である。ノード「Ａ」は、状態が要解析から解析済に変更されている。
【０１９３】
１６周目の処理が終わったとき、要解析ノードはノード「Ｂ」のみである。そこで、次の解析対象ノードとしてノード「Ｂ」が選定され、１７周目の処理が実行される。
図３２は、１７周目のコールグラフの構築・探索状況の一例を示す図である。１７周目（ノード「Ｂ」の解析）の処理後、ノード「Ｂ」の呼び出し先ノードには、ノード「Ｂ」の呼び出し先であるノード「Ｄ」の呼び出し先ノードに設定されているノード「Ｃ」が追加されている。ノード「Ｂ」は、状態が要解析から解析済に変更されている。
【０１９４】
１７周目の処理が終わったとき、すべてのノードが解析済の状態になっている。したがって、コールグラフの構築・探索処理は終了となり、解析結果が出力される。解析結果は、例えばモニタ２１に表示される。
【０１９５】
図３３は、解析画面例を示す図である。図３３の例では、あるメソッドに修正を加え、そのメソッドがある変数の値を書き換える可能性が生じた場合を想定している。このような場合、メソッドに修正を加えた利用者は、書き換えられる可能性がある変数に依存するメソッドがどれかを知りたい。そこでコンピュータ１００を用いて、コールグラフを用いた影響波及分析が行われる。
【０１９６】
例えば利用者が解析制御部１２１の起動をコンピュータ１００に指示すると、図３３に示すような解析画面６０が表示される。利用者は、解析対象のソースコード名を、ソースコード入力部６１に入力する。その後、利用者が解析ボタン６２を押下すると、解析制御部１２１の制御の下、ソースコードが解析される。解析が終わると、メソッド一覧表示部６３に、ソースコードに含まれているすべてのメソッドが表示される。利用者がメソッド一覧表示部６３からメソッドを選定すると、選定されたメソッドによって影響を受けるすべてのメソッドが、影響メソッド表示部６４に表示される。
【０１９７】
またメソッド一覧表示部６３で選定されたメソッドの内容（プログラムコード）が、影響元メソッド表示部６５に表示される。影響メソッド表示部６４で選定されたメソッドの内容（プログラムコード）が、影響先メソッド表示部６６に表示される。
【０１９８】
第２の実施の形態では、コールグラフを解析する際に、解析対象ノードを適切な順番で選定しているため、効率的に解析が実行される。そのため、解析ボタン６２が押下されてから、短時間でメソッド一覧表示部６３にメソッド一覧が表示される。そしてメソッド一覧表示部６３からメソッドが選定されると、即座に、影響メソッド表示部６４に影響を受けるメソッドが表示される。
【０１９９】
以上説明したように、第２の実施の形態によれば、ソースコードを効率的に解析することができる。以下、第２の実施の形態による方式でノード選定を行ったときの解析時間を、他の方式でノード選定を行ったときの解析時間との比較結果を示す。他の方式は、ランダム方式と未解析優先方式である。ランダム方式は、次の解析対象ノードをランダムに選定する方式である。未解析優先方式は、未解析のノードを優先的に、次の解析対象ノードとして選定する方式である。
【０２００】
ここで、コールグラフのノード数をＮ（Ｎは１以上の整数）とする。またコールグラフ中の各メソッドの長さ（行数）の平均をｍ（ｍは正の実数）とする。
またコールグラフ構築・探索問題の計算量は、「（Ｓ＋Ｍ）×Ｐ」で表すことができる。ここでＳはノードの選定処理にかかる時間である。Ｍは１つのノードの解析に要する時間である。Ｐはノードの解析回数である。各選定方式の計算量をオーダ表記で表すと、以下のようになる。
【０２０１】
［第２の実施の形態におけるノード選定方式の計算量］
まずノード選定の計算時間を考察する。最悪の場合、１つのノードを選定するためにすべてのノードを検査することになる。そのため、ノード選定の計算時間Ｓは、Ｏ（Ｎ）となる。ノードの処理時間は方式に依存せず、Ｏ（ｍ）である。最悪時のノード解析回数Ｐは、あるノードの到達可能ノードとしてｒ個（ｒは１以上の整数）のノードがあるとしても、他の方式のような無駄な解析が発生せず、計算量はＯ（Ｎ）となる。従って、総計算量は、以下の通りである。
・Ｓ＝Ｏ（Ｎ）
・Ｍ＝Ｏ（ｍ）
・Ｐ＝Ｏ（Ｎ）
・総計算量＝Ｏ（Ｎ2＋ｍＮ）
［ランダム方式の計算量］
ノードの選定はランダムなので、ノード選定の計算時間Ｓは、Ｏ（１）である。１つのノードの処理時間Ｍは、ノード選定方式に依存せず、Ｏ（ｍ）である。ｒ個のノードの存在がわかっている時点での最悪時のノード解析回数Ｐは、「１＋２＋，…，＋ｒ＝ｒ（ｒ＋１）／２」と計算できる。これはオーダ表記ではＯ（ｒ2）となる。１≦ｒ≦Ｎを満たすそれぞれのｒについてＯ（ｒ2）なので、「１2＋２2＋，…，＋Ｎ2＝Ｎ（Ｎ＋１）（２Ｎ＋１）／６」となる。オーダ表記ではＯ（ｒ3）となる。従って、総計算量は、以下の通りである。
・Ｓ＝Ｏ（１）
・Ｍ＝Ｏ（ｍ）
・Ｐ＝Ｏ（Ｎ3）
・総計算量＝Ｏ（ｍＮ3）
［未解析優先方式の計算量］
ノード選定とノード処理時間は上述のランダム方式と同じである。最悪時のノード解析回数は、Ｎ個のノードの存在が判明してからの解析回数が「１＋２＋，…，＋Ｎ＝Ｎ（Ｎ＋１）／２」となる。オーダ表記ではＯ（Ｎ2）となる。従って、総計算量は、以下の通りである。
・Ｓ＝Ｏ（１）
・Ｍ＝Ｏ（ｍ）
・Ｐ＝Ｏ（Ｎ2）
・総計算量＝Ｏ（ｍＮ2）
コンピュータ１００で解析することとなるようなプログラムは、ソースコードが大規模である。するとノード数Ｎとメソッドの長さの平均ｍも大きくなりがちとなる。ノード数Ｎが増加すると、ランダム方式ではＮの３乗のオーダで処理が増加するが、第２の実施の形態ではＮの２乗のオーダで済んでいる。また未解析優先方式では、メソッドの平均長さｍがＮの２乗に掛け合わされており、メソッドの長さが長くなったときの、処理量の増加が、第２の実施の形態に比べて大きい。すなわち、第２の実施の形態に示したノード選定方式が最も計算量が少なくて済むことが分かる。
【０２０２】
図３４は、第２の実施の形態におけるノード選定方式と未解析優先方式との総計算時間の比較結果を示す図である。図３４の例では、コールグラフのノード数が、５ノード、１０ノード、２０ノード、５０ノード、１００ノード、２００ノード、５００ノード、および１０００ノードの場合における解析時間をグラフで示している。各グラフ内の左側が第２の実施の形態におけるノード選定方式（Optomized）であり、右側が未解析優先方式（UnresolveFirst）である。各ノード数における解析を複数回実行し、解析時間の平均値を太線による横棒で示している。また平均値からの標準偏差σの範囲を矩形で示し、２σの範囲を細線による横棒で示している。
【０２０３】
図３４に示すように、コールグラフの規模が大きくなると、第２の実施の形態におけるノード選定方式による処理効率の方が、明らかに未解析優先方式よりも解析時間が短くなっている。
【０２０４】
以上説明したように、第２の実施の形態によれば、到達可能ノード数が多いノードを優先的に解析するようにしたことで、ノードの情報が変更されたときの影響範囲が広いノードを優先的に解析することができる。すなわち他のノードに与える影響が大きいノードほど先に解析することで、ノードの繰り返し解析回数を削減し、解析時間を短縮することができる。
【０２０５】
なお第２の実施の形態では、到達可能ノード数として、正確な値ではなく概算値が用いられる。これにより到達可能ノード数の算出時間を短縮することができ、処理の効率化が図れる。
【０２０６】
さらに第２の実施の形態では、要解析状態のノードの中に安定ノードがある場合には、安定ノードが優先的に解析される。安定ノードは、呼び出し先ノードの情報が今後変更される可能性が低く、残り１回の解析で済む可能性が高い。安定ノードを優先的に解析することで、情報が未確定のノードを早期に減らすことができる。情報が未確定のノード数が少なくなれば、適切な解析対象ノードを選定することも容易となる。
【０２０７】
要解析状態のノードが安定ノードかどうかの判断についても、概略的に求められている。すなわち、判断対象のノードから直接呼び出されるノードがすべて解析済状態であれば、判断対象のノードは安定ノードと判断される。これにより、安定ノードかどうかの判定を効率的に行うことができる。すなわち安定ノードかどうかの判定を行うことによる処理の増加が最小限に抑えられている。
【０２０８】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０２０９】
１  解析対象プログラム
２  コールグラフ
１０  解析装置
１１  記憶部
１２  処理部
【図１】
2018073223.tif 000003
【図２】
2018073223.tif 000004
【図３】
2018073223.tif 000005
【図４】
2018073223.tif 000006
【図５】
2018073223.tif 000007
【図６】
2018073223.tif 000008
【図７】
2018073223.tif 000009
【図８】
2018073223.tif 000010
【図９】
2018073223.tif 000011
【図１０】
2018073223.tif 000012
【図１１】
2018073223.tif 000013
【図１２】
2018073223.tif 000014
【図１３】
2018073223.tif 000015
【図１４】
2018073223.tif 000016
【図１５】
2018073223.tif 000017
【図１６】
2018073223.tif 000018
【図１７】
2018073223.tif 000019
【図１８】
2018073223.tif 000020
【図１９】
2018073223.tif 000021
【図２０】
2018073223.tif 000022
【図２１】
2018073223.tif 000023
【図２２】
2018073223.tif 000024
【図２３】
2018073223.tif 000025
【図２４】
2018073223.tif 000026
【図２５】
2018073223.tif 000027
【図２６】
2018073223.tif 000028
【図２７】
2018073223.tif 000029
【図２８】
2018073223.tif 000030
【図２９】
2018073223.tif 000031
【図３０】
2018073223.tif 000032
【図３１】
2018073223.tif 000033
【図３２】
2018073223.tif 000034
【図３３】
2018073223.tif 000035
【図３４】
2018073223.tif 000036