Entries tagged as npath complexity

Related tags

Sunday, August 22. 2010

Slides of my "Understanding Software Metrics" talk online

I have just published the slides from my "Understanding Software Metrics" talk at FrOSCon 2010.

Posted by Manuel Pichler in php at 10:34 | Comments (2) | Trackbacks (0)
Defined tags for this entry: , , , ,
Bookmark Slides of my "Understanding Software Metrics" talk online at del.icio.us Digg Slides of my "Understanding Software Metrics" talk online Bloglines Slides of my "Understanding Software Metrics" talk online Technorati Slides of my "Understanding Software Metrics" talk online Bookmark Slides of my "Understanding Software Metrics" talk online at YahooMyWeb Bookmark Slides of my "Understanding Software Metrics" talk online at blogmarks Stumble It!

Sunday, April 25. 2010

PHP_Depend 0.9.12 release

I am proud to announce the 0.9.12 release of PHP_Depend. PHP_Depend is a low level static code analysis tool. It takes the given source and calculates several software metrics for the code. This data can be used by software-developers, architects and designers to control the quality of a software-product without time consuming code audits.

This new release of PHP_Depend has done a great step into the direction of a token free PHP_Depend version. This means future versions of PHP_Depend will work without the need to traverse linear token streams up and down, to measure metrics. Instead PHP_Depend will rely on it's internal abstract syntax tree, that represents the logical structure of the analyzed source code. With this solution it will be possible to implement several new features that will make PHP_Depend more useful, for example static callgraph analysis.

  • Implemented #97: Replace current token approach in CCN- and NPath-Analyzer with AST-Nodes. Implemented in svn revision #1248.
  • Implemented #125: PHP_Depend silently parses list statements. Fixed in svn revision #1223. Thanks to Joey Mazzarelli for providing this patch.
  • Implemented #126: Generate reproducable node identifiers instead of random numbers. Implemented in svn revision #1244.
  • Fixed #128: Variable variables in foreach statement cause an exception. Fixed in svn revision #1237.
  • Fixed #133: Fatal error: Maximum function nesting level of '100' reached, aborting! in /usr/share/pear/PHP/Depend/Util/Log.php on line 109. Fixed in svn revision #1257.
  • Fixed #134: ASTReturnStatement is not derived from ASTStatement. Fixed in svn revision #1250.
  • Fixed #135: Several Statement classes do not inherit ASTStatement. Fixed in svn revision #1255.

As always, you can get the latest PHP_Depend version from its PEAR channel: pear.pdepend.org:

mapi@arwen ~ $ pear channel-discover pear.pdepend.org
mapi@arwen ~ $ pear install pdepend/PHP_Depend-beta

Or you can fetch the sources from the subversion reposition:

mapi@arwen ~ $ svn co http://svn.pdepend.org/trunk pdepend

And additionally you can find a repository mirror on github:

mapi@arwen ~ $ git clone git://github.com/manuelpichler/pdepend.git
Posted by Manuel Pichler in php, php_depend, phpugdo, projects at 14:44 | Comments (0) | Trackbacks (0)
Defined tags for this entry: , , ,
Bookmark PHP_Depend 0.9.12 release at del.icio.us Digg PHP_Depend 0.9.12 release Bloglines PHP_Depend 0.9.12 release Technorati PHP_Depend 0.9.12 release Bookmark PHP_Depend 0.9.12 release at YahooMyWeb Bookmark PHP_Depend 0.9.12 release at blogmarks Stumble It!

Friday, August 7. 2009

PHP_Depend-0.9.7 Bugfix release

The NPath complexity calculation was broken in PHP_Depend 0.9.6. This bug was fixed in PHP_Depend 0.9.7.

Posted by Manuel Pichler in php, php_depend, phpugdo, projects at 23:24 | Comments (0) | Trackbacks (0)
Defined tags for this entry: , , , ,
Bookmark PHP_Depend-0.9.7 Bugfix release at del.icio.us Digg PHP_Depend-0.9.7 Bugfix release Bloglines PHP_Depend-0.9.7 Bugfix release Technorati PHP_Depend-0.9.7 Bugfix release Bookmark PHP_Depend-0.9.7 Bugfix release at YahooMyWeb Bookmark PHP_Depend-0.9.7 Bugfix release at blogmarks Stumble It!

Tuesday, July 7. 2009

The value of complexity metrics - Cyclomatic Complexity (1/2)

Software metrics are currently on everyone's lips and a frequently discussed topic. There are many conference talks, blog posts and other presentations that talk about software metrics. But to me it seems as if this subject is a closed book for many developers, so I decided to write this little post about a special category of software metrics, the complexity metrics.

Complexity metrics are a theoretical approach to measure the subjective complexity of a software fragment, where the words software fragment stand for a paraphrase for functions, methods, classes and nearly every logical unit that can be found in a software system. The most prevalent procedure to calculate complexity values is static code analysis, where an application parses the raw source code of a project, counts different statements and expressions and packs up the determined results in simple classification numbers. And with this information you already know the main concepts behind most software metrics, classification numbers and counting. As you can see there is no magic behind the scene, the only thing required is a good background knowledge to interpret those values.

The Cyclomatic Complexity Number or short CCN is the oldest complexity metrics. The first time this software metric was mentioned was 1976 by Thomas J. McCabe. This metric counts the available decision paths in a software fragment to determine its complexity. Each decision path starts with one of the conditional statements from the following list, so that it is fairly easy to detect them in existing source code.

  • ?
  • case
  • elseif
  • for
  • foreach
  • if
  • while

A look at this list of statements may result in the questions: Is this list wrong, it doesn't list else and default? But it is correct. The assumption is that both statements will contain the defaut execution path of a program which also exists when there are no special cases to capture.

Each decision path gets the value 1 and the sum of all these values represents the Cyclomatic Complexity of the analyzed software fragment. Note that each function and method also counts with a value of 1 With this knowlegde we can now calculate the complexity of the following example code:

  1.  
  2. <?php                                 
  3. class CyclomaticComplexityNumber
  4. {
  5.     public function exampe( $x, $y ) // (1)
  6.     {                                               
  7.         if ( $x > 23 || $y < 42 ) // (1)
  8.         {                                 
  9.             for ( $i = $x; $i >= $x &&amp; $i <= $y; ++$i ) // (1)
  10.             {
  11.             }
  12.         }
  13.         else
  14.         {
  15.             switch ( $x + $y )
  16.             {
  17.                 case 1: // (1)
  18.                     break;
  19.                 case 2: // (1)
  20.                     break;
  21.                 default:
  22.                     break;
  23.             }
  24.         }
  25.     }
  26.     file_exists('/tmp/log') or touch('/tmp/log');
  27. }
  28.  

Based on the previous definition the Cyclomatic Complexity Number of the example code example is 5. But you may have noticed that this approach does not capture all decision paths that exist. We haven't catched those paths that came from the by the boolean expression || line 6 and && line 8, and the logical or expression in line 25. A variation of the Cyclomatic Complexity Number that also captures those paths is the so called CCN2. The CCN2 is the most widely used variation of this software metrics. Tools like PHPUnit, PMD and Checkstyle report it as Cyclomatic Complexity of an analyzed software fragment.

Now we get a complexity value of 8 when we apply the CCN2 to the previous example, what is a growt of the software's complexity of 60%.

Due to the fact that Cyclomatic Complexity Number was originally invented for procedural programming languages, this definition for the Cyclomatic Complexity Number still misses one element to measure the complexity of an object oriented software system. With the concept of exceptions a software gets additional decision paths for each catch statement used in the source code. While try contains the code for the regular execution code without special cases, similar to else and default statements.

  • ?
  • &&
  • ||
  • or
  • and
  • xor
  • case
  • catch
  • elseif
  • for
  • foreach
  • if
  • while

Now that we know what the Cyclomatic Complexity Number is, what can we do with the measured information? We can find the complexity hotspots in a system, for example the top ten artifacts with the highest complexity, but this is only important during an initial analyses phase to get the big picture of an application. For a continuous inspection this information is not so important. A continuous analyses requires thresholds that help to categories calculated values. During the time four values have emerged as good thresholds for the Cyclomatic Complexity Number of a software system.

  • A software fragment with a CCN value between 1-4 has low complexity.
  • A complexity value between 5-7 is moderate and still easy to understand.
  • Everything between 6-10 has a high complexity, while everything greater 10 is very complex and hard to understand.

You may ask, why should I care about the complexity of a software system, where is the value of benefit in this metric?

Mostly the complex parts of an application contain business critical logic. But this complexity has negative impacts on the readability and understandability of source code. Those parts will normally become a maintainence and bug fixing nightmare, because no one knows all the constraints, side effects and what's exactly going on in that part of the software. This situation results in the well known saying "Never touch a running system" which in turn mostly ends in copy&paste programming. The situation can even become more critical when the original author leaves the development team or the company.

Finally a small example how to apply the new knowledge about the Cyclomatic Complexity Number, thresholds and the negative impacts of complex software to an existing development process. The following source listing shows a complex method taken from PHP_Depend's source. This method has a Cyclomatic Complexity Number of 16 and I must admit that the original author needed some time to understand what was going on in this method.

  1.  
  2. <?php
  3. // ...
  4. private function _countCalls(AbstractCallable $callable)
  5. {
  6.     $callT  = array(
  7.         TokenizerI::T_STRING,
  8.         TokenizerI::T_VARIABLE
  9.     );
  10.     $chainT = array(
  11.         TokenizerI::T_DOUBLE_COLON,
  12.         TokenizerI::T_OBJECT_OPERATOR,
  13.     );
  14.     $called = array();
  15.  
  16.     $tokens = $callable->getTokens();
  17.     $count  = count($tokens);
  18.     for ($i = 0; $i < $count; ++$i) {
  19.         // break on function body open
  20.         if ($tokens[$i]->type === TokenizerI::T_CURLY_BRACE_OPEN) {
  21.             break;
  22.         }
  23.     }
  24.  
  25.     for (; $i < $count; ++$i) {
  26.         // Skip non parenthesis tokens
  27.         if ($tokens[$i]->type !== TokenizerI::T_PARENTHESIS_OPEN) {
  28.             continue;
  29.         }
  30.         // Skip first token
  31.         if (!isset($tokens[$i - 1]) || !in_array($tokens[$i - 1]->type, $callT)) {
  32.             continue;
  33.         }
  34.         // Count if no other token exists
  35.         if (!isset($tokens[$i - 2]) &&amp; !isset($called[$tokens[$i - 1]->image])) {
  36.             $called[$tokens[$i - 1]->image] = true;
  37.             ++$this->_calls;
  38.             continue;
  39.         } else if (in_array($tokens[$i - 2]->type, $chainT)) {
  40.             $identifier = $tokens[$i - 2]->image . $tokens[$i - 1]->image;
  41.             for ($j = $i - 3; $j >= 0; --$j) {
  42.                 if (!in_array($tokens[$j]->type, $callT)
  43.                     &&amp; !in_array($tokens[$j]->type, $chainT)
  44.                 ) {
  45.                     break;
  46.                 }
  47.                 $identifier = $tokens[$j]->image . $identifier;
  48.             }
  49.  
  50.             if (!isset($called[$identifier])) {
  51.                 $called[$identifier] = true;
  52.                 ++$this->_calls;
  53.             }
  54.         } else if ($tokens[$i - 2]->type !== TokenizerI::T_NEW
  55.             &&amp; !isset($called[$tokens[$i - 1]->image])
  56.         ) {
  57.             $called[$tokens[$i - 1]->image] = true;
  58.             ++$this->_calls;
  59.         }
  60.     }
  61. }
  62.  

The first thing to do is to make sure that the test suite is good enough to ensure that the required refactorings will not change the public behavior of the component or class. When this is donw and we are sure our that api breaks will be detected by the test suitewe can start to extract logic into separate methods.

The following example shows the result of the refactoring:

  1.  
  2. <?php
  3. // ...
  4. private function _countCalls(AbstractCallable $callable)
  5. {
  6.     $called = array();
  7.  
  8.     $tokens = $callable->getTokens();
  9.     $count  = count($tokens);
  10.     for ($i = $this->_findOpenCurlyBrace($tokens); $i < $count; ++$i) {
  11.  
  12.         if ($this->_isCallableOpenParenthesis($tokens, $i) === false) {
  13.             continue;
  14.         }
  15.  
  16.         if ($this->_isMethodInvocation($tokens, $i) === true) {
  17.             $image = $this->_getInvocationChainImage($tokens, $i);
  18.         } else if ($this->_isFunctionInvocation($tokens, $i) === true) {
  19.             $image = $tokens[$i - 1]->image;
  20.         } else {
  21.             $image = null;
  22.         }
  23.  
  24.         if ($image !== null) {
  25.             $called[$image] = $image;
  26.         }
  27.     }
  28.     $this->_calls += count($called);
  29. }
  30.  

The subjective feeling of readability heavily depends on the complexity of control structures, as we can see by a comparison of the original and the refactored version of the method example. The new version with its Cyclomatic Complexity Number of 5 is much easier to read and understand.

This text is the first of two blog posts. The second article will give a short introduction into the NPath Complexity You liked this article and you are interested in this and other quality assurence related topics? - Then you should now order your copy of the Book Quality Assurance in PHP Projects. The book talks about nearly all aspect of quality assurence, with practical tips and expert knowledge contributed by certain PHP professionals.

Posted by Manuel Pichler in php, php_depend, phpugdo, phpundercontrol, planet-php, projects at 21:20 | Comments (2) | Trackbacks (0)
Defined tags for this entry: , , , , , ,
Bookmark The value of complexity metrics - Cyclomatic Complexity (1/2) at del.icio.us Digg The value of complexity metrics - Cyclomatic Complexity (1/2) Bloglines The value of complexity metrics - Cyclomatic Complexity (1/2) Technorati The value of complexity metrics - Cyclomatic Complexity (1/2) Bookmark The value of complexity metrics - Cyclomatic Complexity (1/2) at YahooMyWeb Bookmark The value of complexity metrics - Cyclomatic Complexity (1/2) at blogmarks Stumble It!

Wednesday, December 31. 2008

PHP_Depend-0.9.1 released

Just now I released PHP_Depend 0.9.1, the major feature in this new version is an implementation of the NPath Complexity metric, beside that feature the main focus for this release was on performance improvements of the current implementation.

  • Closed #21: Support for the NPath Complexity metric.
  • Fixed #78: Parser fails for comment in function signature.
  • Closed #79: Token objects instead of arrays.

An additional test concept was introduced with the 0.9.* branch of PHP_Depend. Nightly builds test PHP_Depend against a series of open source projects to detect deadlocks like endless loop or similar issues. This procedure is also used to test each release candidate of PHP_Depend. The tested project are:


You can get the latest PHP_Depend version through its PEAR channel pear.xplib.de or as a subversion checkout of the 0.9.1 tag.
Please do not checkout "trunk", it is totally unstable at the moment and I will not provide any support for it. 

mapi@arwen ~ $ svn co http://svn.pdepend.org/tags/0.9.1
Posted by Manuel Pichler in php, php_depend, phpugdo, planet-php, projects at 10:31 | Comments (0) | Trackbacks (0)
Defined tags for this entry: , , , ,
Bookmark PHP_Depend-0.9.1 released at del.icio.us Digg PHP_Depend-0.9.1 released Bloglines PHP_Depend-0.9.1 released Technorati PHP_Depend-0.9.1 released Bookmark PHP_Depend-0.9.1 released at YahooMyWeb Bookmark PHP_Depend-0.9.1 released at blogmarks Stumble It!
(Page 1 of 1, totaling 5 entries)

Projects

Further stuff

See also

Zend Certified Engineer (ZCE)
Hire the Quality Assurance Expert Manuel Pichler
Visit the XING profile of Manuel Pichler
Visit the open source ohloh profile of Manuel Pichler

Categories



All categories