2012年4月30日月曜日

循環的複雑度 ( Cyclomatic Complexity ) とは何ぞや

注意:この記事だけアクセスが多くて逆に不安になっております。
不正確な記述が含まれる可能性が大なので、必ずほかの記事も当たっていただければと思います。

今回は、循環的複雑度(Cyclomatic Complexity)について書きます。

これは、ソースコードのメトリクス(定量的に評価した値)の一つです。
条件複雑度(Conditional Complexity)とも呼ばれます。
簡単なメトリクスとしては、関数の行数やコメント行数など単純なものもありますが、
循環的複雑度はもう少し"プログラムの内容を考慮した"メトリクスです。

循環的複雑度とは、一言で言うと、
"あるひとつの関数がどれだけ複雑か"度
です。もう少し詳しく言えば、
"あるひとつの関数について、どれぐらい分岐があるか" 度
を表す数値です。
プログラムの中の各関数について、この複雑度の数値が計算されます。

Wikipediaに書いてあるようなフォーマルな定義だと、
"関数の制御フローを有効グラフとして書いたときの、(グラフの辺数) - (グラフの頂点数) + 2×(連結コンポーネント数)"
という感じで、「定義自体が複雑じゃボケ!」と言いたくなってしまいます。
(フォーマルな定義はそれはそれで面白い部分があるので時間があれば紹介するかもしれません。
なぜ循環的複雑度と呼ぶのか、もそちらに従っていますので。)

実際のところはもっともっと簡単に計算できます。
NDepend という .NET 向けのメトリクス計測ツールでは、以下のように計測しているとしています。
http://www.ndepend.com/Metrics.aspx#CC による)

関数の循環的複雑度 = 1 + 関数の中に以下のものが出てきた回数:
if、while、for、foreach、case、default、continue、goto、&&、||、catch、?: (三項演算子)、??

つまり "デフォルトの複雑度は 1 で、分岐が発生するたびに 1 増やすよ" といっているだけです。
自分が知っている別のツールでも同じような感じですので、結局これで十分ということのようです。
非常に簡単でわかりやすい尺度です。
値が小さければ小さいほど、その関数には分岐は少なく、構造が単純で理解がしやすい、ということになります。
逆に、値がデカければデカいほど、分岐が多く、構造が複雑で理解がし辛い、というわけです。
テストに必要なテストケースの数もこれに直結しています。

例えば、次の(無意味な)関数 foo の複雑度は 5 です(if や for 等を数えればすぐわかると思います)。

「良いプログラム」ならば「(その中の各関数の)循環的複雑度が小さい」は大抵の場合正しいと思います。
読みやすくなるように考えて作られたプログラムであれば、
ある程度の処理の単位で関数化が行われているはずであり、
結果としてひとつの関数内の分岐の数(=複雑度の値)はある程度で抑えられているはずだからです。
対偶を取ると、「循環的複雑度が大きい」ならば、「良くないプログラムである」ということです。

逆に、「循環的複雑度が小さい」ならば「良いプログラム」であるか、といえば私はそうは思いません。
これは、コーディングルールに似ています。
良いプログラムはコーディングルールを守って書かれているでしょうが、
コーディングルールが守られているからといって必ずしも良いプログラムとは言えません。
コーディングルールをちゃんと守る事も、複雑度をある程度で抑えることも、
どちらも単にコーディングをする上で守るべき最低限の事をしているに過ぎないからです。

ただ、性質上どうしても複雑度が大きくなってしまう処理や、
人の目にはそこまで複雑には見えなくても、複雑度の計算結果は大きくなる処理があります。
特に swich-case や if文 の中に || や && が多くある場合は顕著です。
例えば、以下の例はその典型例でしょう。
stackoverflow - why would I refactor this code as Cyclomatic Complexity is 58

もちろん、複雑度を一定以下に抑えるように関数/コードを書くことは推奨されてしかるべきですが、
その一方で、ある一つの絶対的なしきい値を設けて
「複雑度がそれ以上になる関数は絶対禁止」とするのはやりすぎかなと考えます。
あくまでも目安としてしきい値を設定しておいて、
それを超える関数については分割などのリファクタリングを検討するようにする、という程度が良いと思っています。

一応、一般的に言われているのは次のような基準です。参考程度に。
  • 1-10 : シンプルで、リスクが小さい関数
  • 11-20 : 中程度の複雑さとリスクの関数
  • 21-50 : 複雑、リスクが高い関数
  • 50以上 : マジでヤバイ関数

個人的には 20 以上だとちょっと嫌だな、という感じです。
まあ、普通に考えて書いていれば、基本的に 10 以内に収まると思います。
ちなみに、職場で見つけた一番ヤバかったのは 47 の関数でした
(そこは後でリファクタリングにより20まで落としましたが)。
stackoverflowだと、171 の関数を見たことがあるよ、という投稿があったりしたので、
それに比べると全然マシなのかな、という気もしてきます。
stackoverflow - What is the highest Cyclomatic Complexity of any function you maintain? And how would you go about refactoring it?

余談。
循環的複雑度はあくまで、一つの関数に対してその複雑度を測っています。
なので、ある関数の一部を切り出して関数化してあげるだけで、複雑度の値は落ちます。
「全体の処理の流れ自体は変わっていないのに、小手先で複雑度の値を下げて意味はあるのか?」
という議論もあるかと思います。
一理あるのですが、以下のようなメリットはあると思います。
  • 関数化して適切な名前をつけることで読みやすくなる
  • 関数が分かれればそれだけテストしやすくなる
ま、複雑なプログラムは大抵、設計自体の問題であることがほとんどですが。

参考
http://ja.wikipedia.org/wiki/循環的複雑度
http://en.wikipedia.org/wiki/Cyclomatic_complexity
http://www.teknologika.com/blog/what-the-heck-is-cyclomatic-complexity/
http://www.ndepend.com/Metrics.aspx#CC
http://ishare.intellicorp.com/cs/cto/b/ctrueman/archive/2011/08/20/estimating-the-complexity-of-abap-programs-the-good-bad-and-ugly.aspx
http://stackoverflow.com/questions/911637/what-is-cyclomatic-complexity

2012年4月1日日曜日

node-websocket-server と Firefox11 とで通信するとうまく動かない?

!!!注!!! この記事は書かれたのが2012年4月とかなり古いです。状況は大幅に変わっていると思いますので、参考程度でお願いします。

最近ちょっとnode.jsをローカルに入れて弄っています。
で、WebSocketとやらを実験的に触ってみようと、
よく紹介されている node-websocket-server というパッケージを npm で入れてみました。
しかし、なんだかローカルのnode.jsサーバー + node-websocket-server と
Firefox11 とを通信させようとしてもうまく動かなくて困ってしまいました。

調べてみると、node-websocket-server の本家はここみたいです。
https://github.com/miksago/node-websocket-server

ただ、作者が忙しいみたいで、最近は更新が止まっています。
代わりにそれをforkした以下だともう少し先に進んでいます。
https://github.com/VanCoding/node-websocket-server
node.js で 出来るだけ最新の node-websocket-server を使う。 の記事を参考にさせていただきました)
上記のは一応、websocket protocolの draft 16 まで対応してます、という体です。

wikipediaによれば、Firefox 11やChrome16以降では RFC6455  (draft17 の次、ほぼ最終版?) に従った実装がされているので、
後者のパッケージの方を使えば、比較新しいしちゃんと動くのかなあと期待したわけです。
で、改めてこれを入れてみて動かしてみたのですが・・・

うーん。やっぱりFirefox 11では動かない。
ふと思いついて、試しにChrome 16を使ってみると・・・なんとうまく動いてしまいました。
えっ? なんで? なんでなの!?
混乱しながらlogを仕込んで調べてみたら、さらに次のようなことがわかりました。

WebSocketのシェイクハンド時に用いるHTTPヘッダの Connection フィールドについて、
昔のdraftでは "Upgrade" というトークンのみが入っていることが期待されていたようです。
しかし、比較的新しい仕様 (draft13 以降) では、
"Upgrade" が含まれていれば他のトークンも含まれてよいことになっています。
Firefox11ではそれに従い、

Connection: Keep-alive, Upgrade

と入っているみたいです。
結果として(昔のdraftに従って書かれた) node-websocket-serverだと
シェイクハンド時のチェックで invalid 扱いになりはじかれてしまいます。
具体的には、node-websocket-server の lib/ws/server.js にある、次の行の部分です。



そのチェックコードを以下のように弄ったら、Firefoxでもうまく動きました。うわーい。
(修正は faye-websocket-node のコードを参考にしています)



パッケージとして公開するならもっとちゃんとメンテしてくれないと困る、というお話でした。