home *** CD-ROM | disk | FTP | other *** search
/ Programmer's ROM - The Computer Language Library / programmersrom.iso / ada / metric / mccabe.rno < prev    next >
Encoding:
Text File  |  1988-05-03  |  8.2 KB  |  228 lines
  1. .PA
  2. .K
  3. .RM 65
  4.  
  5. .HL COMMAND FORMAT
  6.  
  7. .LT
  8.  
  9.  
  10. -- MCCABE : Calculate the McCabe complexity measures.
  11. -- Version 3.01-1.1
  12.  
  13.  
  14. subtype FILE_NAME is STRING;
  15. subtype MAX_VALUE is INTEGER range 1 .. 99;
  16.  
  17. procedure MCCABE(
  18.    SOURCE_FILE    : in FILE_NAME;
  19.    OUTPUT_FILE    : in FILE_NAME := "";
  20.    MAX_COMPLEXITY : in MAX_VALUE := 20
  21.    );
  22.  
  23. -- SOURCE_FILE    : Input file name.
  24. -- OUTPUT_FILE    : Name of the report file (defaults to standard output).
  25. -- MAX_COMPLEXITY : Greatest complexity not flagged in output listing
  26. --                  (range: 1 .. 99, default: 20).
  27.  
  28. .EL
  29.  
  30.  
  31. .HL MCCABE DESCRIPTION AND USE
  32.  
  33. The McCabe measure computes complexity based on the control
  34. structure (or "flow graph") of the program.  The tool takes the name
  35. of an Ada source program text file and computes the cyclomatic
  36. complexity for every subprogram body contained
  37. in the file.  Specifications do not have a complexity associated
  38. with them.  The tool also takes an output file name and a number,
  39. MAX_COMPLEXITY, which  is the maximum complexity allowed for a
  40. program. If a procedure is found to have a complexity greater than
  41. the specified value, it will be flagged on the output listing.
  42. .P
  43. The McCabe tool builds the flow graph and computes the cyclomatic number
  44. for each program unit in the source file.  In addition, it sums the number
  45. of nodes and edges in all program units and computes a cyclomatic number
  46. for the entire file.  
  47. .P
  48. The tool assumes that a source program text is correct ADA (i.e., it is
  49. compiled cleanly); otherwise it terminates with a syntax error.
  50.  
  51. .HL MOTIVATION
  52.  
  53. The McCabe complexity measure is principally useful in two ways:
  54. as an aid in testing and as a numeric guidline for management purposes.
  55. In testing, the complexity number corresponds to the number of control
  56. paths through a subprogram and therefore the number of test cases
  57. required to test them all.  If the number of test cases is less than
  58. the complexity, then at least one of three conditions is true:
  59. .LS
  60. .LE
  61. more testing is required;
  62. .LE
  63. decision points can be removed;
  64. .LE
  65. in-line code can replace decision points.
  66. .ELS
  67. (See [McC] for a full explanation.)  As a programming and management
  68. guidline the tool provides a simple way of flagging subprograms which
  69. might cause problems.  The general method for keeping subprograms
  70. simple is to establish a size limit, e.g., 50 lines or 2 pages.
  71. This is really a surrogate for the lack af any good way of measuring
  72. simplicity.  The McCabe metric is just such a simplicity measure.
  73. The measure is only a guideline since a large CASE statement will
  74. have a correspondingly large complexity but it may only be the
  75. equivalent of a jump table.
  76. .P
  77. Each user will have to determine through experience how best to use
  78. the information provided by the tool.  The McCabe complexity number
  79. is just one measure of program complexity.  Although it can help to
  80. identify program units that may require further scrutiny, it is
  81. not at all reasonable to require that all program units have a
  82. cyclomatic complexity below a certain value.  A case statement for
  83. example is well structured, but can have a high complexity (on the order
  84. of the number of branches in the statement).  This does not mean that
  85. the program is poorly structured, only that each branch of the case
  86. statement must be tested.
  87.  
  88. .HL THEORY OF THE MCCABE METRIC
  89. .P
  90. The McCabe metric is based on the flow graph of a program.  The
  91. flow graph is a directed graph where the nodes represent basic
  92. blocks and the edges represent control flow between basic blocks.
  93. A basic block is a sequence of consecutive statements which may
  94. only be entered at the beginning and exited at the end.  When
  95. entered the instructions are executed in sequence without
  96. branching except at the end [Aho].  Figure 1 shows some flow
  97. graphs for different programming structures.
  98. .TP 10
  99. .LT
  100.  
  101.            if expression                  do while expression loop
  102.               then                            S1;
  103.                  S1                           end loop;
  104.               else
  105.                  S2
  106.               endif;
  107.  
  108. .EL
  109. .TP 12
  110. .LT
  111.  
  112.                if                            do while 
  113.               / \                            |  |  ^
  114.              V   V                           |  V  |
  115.             S1    S2                         |   S1
  116.              \   /                           V
  117.               V V                            end loop
  118.              endif
  119.  
  120.  
  121.             FIGURE 1
  122.  
  123. .EL
  124.  
  125. McCabe's cyclomatic complexity is defined as:
  126. .LT
  127.  
  128.               V(G) = e - n + 2p
  129.  
  130. .EL
  131. .NAP
  132. where 'e' is the number of edges in the flow graph, 'n' is the number
  133. of nodes, and 'p' is the number of connected components.  Ignoring
  134. the direction from the edges of the flow graph, if there exists a
  135. path between each pair of vertices I and J then we say the graph
  136. is a connected component.  Since there is a path from the entry
  137. node to every other node in the flow graph then (ignoring the
  138. directions of the edges) we will be able to get from any node I to
  139. any other node J by going through the entry node.  Therefore, in
  140. our case of computing the cyclomatic complexity for an individual
  141. subprogram p is always 1. The number of
  142. connected components becomes interesting when we would like to
  143. calcultate the cyclomatic complexity of a program that has a
  144. number of different subprograms.  McCabe defines the cyclomatic
  145. complexity of a system as the sum of the cyclomatic complexities
  146. of all the modules.  In this case p, the number of connected
  147. components would be the number of different modules.
  148. .AP
  149. .P
  150. If a subprogram has some unreachable code then McCabe's cyclomatic
  151. complexity formular does not make a lot of sense. In some cases
  152. the tool discovers such subprograms and flags them in the output
  153. with the message "unreachable code".
  154.  
  155. .HL INTERPRETATION OF ADA STATEMENTS
  156. .P
  157. There is a number of ADA statements which generate flow but building
  158. a flow graph for them is not obvious. Sometimes it happens because
  159. the flow of a statement can be interpreted in a number of ways
  160. (as for case and select statements); sometimes it happens because
  161. of the tool limits (as for a raise statement - the flow could go
  162. to an exception handler belonging to a same subprogram as the raise
  163. statement or it could go to a different subprogram in which case
  164. the tool does not have enough information to track the flow).
  165. .P
  166. This is a list of such statements with their corresponding
  167. interpretations.
  168. .LS
  169. .LE
  170. The complexity of an exception handler is added to the complexity
  171. of a containing subprogram.
  172. .LE
  173. Case, select statements and exception handlers are interpreted
  174. as if statement [McC]. For a case statement a corresponding
  175. if statement always has an else clause. Two forms of select
  176. statements - conditional entry call and timed entry call
  177. are always interpreted as if...then...else...end if.
  178. .LE
  179. Return, raise and terminate statements are ignored (as a stop
  180. statement in [McC]).
  181. .ELS
  182.  
  183. .HL OUTPUT FORMAT
  184. .P
  185. The output of the tool is a list of names of all the subprograms
  186. in the input file.  Each name is preceeded by 
  187. its cyclomatic complexity, the number of nodes and the number
  188. of edges in the flow graph.
  189. If any subprogram or function has a cyclomatic complexity above the
  190. specified value, it is flagged.  A sample output follows:
  191.  
  192. .LT
  193.  
  194.  
  195. MCCABE CYCLOMATIC COMPLEXITY:
  196.     SOURCE_FILE "EXAMPLE" - WITH MAX_COMPLEXITY 9
  197.  
  198.       COMPLEXITY         NUMBER OF
  199.       CYCLOMATIC        EDGES  NODES   SUBPROGRAM NAME
  200.  
  201.           4               10      8       subprog1
  202.           3                9      8       subprog2
  203.          14               37     25   *** subprog3
  204.           .               .       .              . 
  205.           .               .       .              .
  206.           .               .       .              .
  207.  
  208.      32               90     48      Total for 5 program units
  209.  
  210. .EL
  211. .PG
  212. .HL REFERENCES
  213.  
  214. .LS 2
  215. .LE
  216. [Aho]    Aho, A.V., Ullman, J.D., Principles of Compiler
  217. Design, Addision-wesley Publishing Company, pp 412-413, 1977.
  218. .LE
  219. [McC]    McCabe, T. J., "A Complexity Measure", IEEE Transactions on
  220. Software Engineering, Vol. SE-2, pp 308-320, December, 1976.
  221. .ELS
  222. .PG
  223. .RM 80
  224. .HL Appendix A: Installation and Modification
  225. .NF
  226. .REQUIRE "[-]read.me"
  227. .F
  228.