ソフトウェアメトリクス1: 循環的複雑度

 ソフトウェアの品質を測定するためのメトリクス(指標)はいろいろありますが、本記事ではソースコードの品質を評価する指標の一つ、循環的複雑度を取り上げたいと思います。1970年代に提唱されたメトリクスであり、現在のソフトウェア開発には合わないという意見もありますが、他の指標と合わせて使うことで依然として有用なメトリクスとなります。

循環的複雑度の定義

 循環的複雑度(英: Cyclomatic Complexity) は、その名称から、単にプログラム内のループの個数を数えるものであると誤解されていることも多いですが、実際にはプログラムの構造を「制御フローグラフ(英: Control flow graph)」で表した際のグラフ内部の循環の数に着目してソフトウェアプログラムの複雑性を測定する指標です。1976年にMcCabe によって提案されました。ちなみに制御フローグラフとは、プログラムの実行中にプログラムを通過する可能性のあるすべての経路を有向グラフで表現したもので、Frances E. Allen によって提唱されたものです

 Fig 1 に制御フローグラフの例を示します。ここで、プログラムの開始位置をノード a, 終了位置をノード f とします。プログラム中の反復や条件分岐が開始する位置と終了する位置もそれぞれノードとなり、図の例ではノードb からe となっています。ノード間をつなぐ逐次処理の部分はエッジとなり矢印で表現されます。ちなみに、逐次処理部分は、プログラム行数が何行であっても(0行であっても) 1つのエッジとなります。

制御フローグラフ
Fig 1: 制御フローグラフの例 (McCabe 1976 より転載)

循環的複雑度の定義は以下のとおりです

V(G) = E – N + 2P

ここで、

  • V: 循環的複雑度
  • G: 制御フローグラフ(ただし、強連結グラフに変換)
  • E: 制御フローグラフのエッジ(辺)の数
  • N: 制御フローグラフのノード(頂点) 数
  • P: 連結されているコンポーネントの数

です。McCabe の循環的複雑度の定義では、プログラムの制御グラフを「強連結(英: Strongly Connected)グラフ」に変換してから計算します。強連結グラフとは、すべての頂点が他のすべての頂点から到達可能であるグラフです。Fig 1を例に説明すると、プログラムの流れとしては1 から 9 のエッジ(実線) のみなのですが、これに仮想的なエッジ10(点線) を追加することで、全てのノードから他の全てのノードに到達可能とします。
 また、Pの「コンポーネントの数」は、ひとまとまりのグラフとしてまとめられる数です。単一のプログラム(またはサブルーチンやメソッド)を対象にしている場合は、グラフのまとまりは1つなので、P=1 となります。よって、より簡略化された循環的複雑度 V’ は

V'(G) = E – N + 2

となります。例として挙げたFig 1 の制御フローグラフで循環的複雑度を計算すると

V'(G) = エッジの数 9 – ノードの数 6 + 2 = 5

となります。

測定のためのツールと結果の解釈

 循環的複雑度を計算するために、有償・無償の様々なツールが提供されています。代表的な例をあげますと

  • OCLint – C言語向けの静的解析ツール
  • GMetrics – Java 向けのメトリクス分析ツール
  • lizard – コマンドラインの循環的複雑度計測ツール

また、Microsoft Visual Studioや、IntelliJ IDEAなどの統合開発環境でも利用できます。弊社のサービスのSider でも、近日中にlizard が利用可能になる予定です。

 計算で得られた循環的複雑度の解釈については諸説ありますが、MathWorks 社のものを引用すると以下のとおりです。

循環的複雑度複雑さの状態バグ混入確率
10以下非常に良い構造25%
30以上構造的なリスクあり40%
50以上テスト不可能70%
75以上いかなる変更も誤修正を生む98%
表1: 循環的複雑度の解釈

Grady による1994年の論文によれば、Hewlett-Packard 社における850,000 行のFortrun のコードを分析した結果、モジュールの循環的複雑度とそのコードが編集された回数には密接な関係があったとしています。3回以上の変更が必要なモジュールについての変更コストとスケジュールの影響を分析した結果、この論文ではモジュールに許容される最大の循環的複雑度は15と結論づけています。

他に例を上げれば、例えばMicrosoft Visual Studio では、循環的複雑度が25 を超えるとワーニングが出て、リファクタリングを促します

循環的複雑度を巡る議論

 循環的複雑度は制御フローグラフのノード数や辺の数にのみ注目しているので、文字通りのコードの「複雑度」を判定するためのメトリクスとしては適切ではないという意見があります。例として、“Software Metrics” から引用したFig 2のグラフを見てみましょう。

異なる複雑度の例
Fig 2: ”Software Metrics” Norman Fenton, James Bieman 著 より転載

制御フローグラフ x は 2つのIF文分岐、グラフ y は 1つのIF文分岐、グラフ z は1つのFORループを持っています。循環的複雑度を計算すると、それぞれ、

  • V'(x) = 8 – 7 + 2 = 3
  • V'(y) = 4 – 4 + 2 = 2
  • V'(z) = 3 – 3 + 2 = 2

となります。グラフy よりグラフ x が複雑であるということは直感的にも理解できますが、グラフ y とグラフz の複雑性が同程度であるとか、グラフ x がグラフz より複雑である、というのはどうでしょうか。おそらく意見のわかれるところでしょう。実際にはコードを見て判断する必要があります。

 では、循環的複雑度はどのように用いるのが適切でしょうか。Intelでは、複雑度の測定とモジュールの変更数のデータが収集されており、データは顧客から報告されたバグと結びつけられています。モジュールの複雑度と、バグ報告による変更回数という2つのメトリクスを使って、リファクタリング開始の判断をすることで、リファクタリングのROIが高められたとしています。

こちらの日本ユニシスによる報告書では、循環的複雑度が50を超えるモジュールを重点的にコードレビューすることで、即時に修正すべきバグを効率的に発見できたとしています。報告書では、

メトリクス活用のポイントとして、メトリクス分析の結果だけでは品質の良し悪しを判断することはできないが,分析によって得られた結果を有効に活用し,「現物確認の徹底」と「品質データの蓄積と再利用」を遵守することによって,初めてシステム開発でのソフトウェアの品質向上という目的に対して成果を上げることが可能となる.

と述べています。

また、循環的複雑度を複雑性の指標として使うのではなく、必要なテストケースの数を算出するのに使用している事例もあります。循環的複雑度は、分岐の数を数え上げているため、完全な分岐網羅率(C1)を達成するのに必要なテストケース数の上限とほぼ等しくなります。よって、単体テストのカバレッジが100%になるための一つの目安として、単体のテストケース数を循環的複雑度の数値に近づけるという方法が考えられます。

以上のように、循環的複雑度は、文字通りの「複雑性」を直接判定するメトリクスとしては実は不適切な場面も多いのですが、長く使われてきた歴史あるメトリクスで、簡単に計測できるツールも揃っています。意味を正しく理解し、他のメトリクスと組み合わせて有効に使っていきましょう。

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.