you should update your Nix channel for
PT. This assignment uses some features that have been added to Dryad
very recently. If you work at home, you need to update your
installation as well.
From now, you are allowed to use any strategy from the Stratego
Library you want. Learning to use this library will help you a lot in
This assignment consists of three exercises. To save you some time, we
provide a template module for every exercise, some simple sample
files, a make script for the more difficult to build third exercise,
file for Checkstyle.
Measuring Execution Paths
McCabe's Cyclomatic Complexity (
Estimation: 15 minutes
In this exercise, we ignore local class declarations and anonymous
The cyclomatic complexity metric is used to measure the number of
execution paths. The number of execution paths affects the
understandability, maintainability, and testability of a program. This
measurement of the number of execution paths is one of the most
popular metrics in software engineering. It is supported by various
style checkers, such as PMD
Calculating the cyclomatic complexity is very easy, since it basically
is the number of nodes in the control-flow graph. Hence, you can count
the number of occurrences for language constructs that introduce
decision points. Decide for yourself what to do with switch statements
(i.e, count switches, cases, or case groups. See also the description
of cyclomatic complexity in PMD and Checkstyle. It might also be
interesting to look at the implementation of the metric in these
tools. The last subsection of this part of the assignment explains how
to invoke Checkstyle, if you want to compare the results.
Extend the template
by collecting all
outermost method declarations of a given compilation unit and
determining the cyclomatic complexity of every method. The program
should return a list of tuples of method names and their cyclomatic
- [[http://cvs.sourceforge.net/viewcvs.py/checkstyle/checkstyle/src/checkstyle/com/puppycrawl/tools/checkstyle/checks/metrics/AbstractComplexityCheck.java?rev=1.6&view=markup][AbstractComplexity.java][Implementation: abstract base class]]
$ strc -i cyclomatic-complexity.str -la stratego-lib
$ parse-java -i Metric1.java | ./cyclomatic-complexity
$ parse-java -i Metric2.java | ./cyclomatic-complexity
NPATH Complexity (
Estimation: 45 minutes
One of the problems with McCabe's cyclomatic complexity is that it
assumes that the testing effort is related to the number of nodes on
the control-flow graph. The NPATH complexity metric stresses that this
is not sufficient and measures the number of acyclic execution paths,
which means that it determines all execution paths, except for the
possible iterations of a loop.
Again, we ignore local class declarations and anonymous classes. This
time, we ignore the
statement as well. We implement a
simplified form of the NPATH complexity metric, where we ignore the
execution paths induced by lazy boolean operators and conditional
The algorithm is:
- For a block, multiply the number of paths of the subterms
- For a control-flow statement, add the paths of the subterms and optionally add additional paths (for example, the if/then and while need one additional path, but the if/then/else does not).
- For other block statements, return 1. You can use the
is-BlockStm strategy, which is defined in the supplied
- For everything else, just add the paths of the subterms, which basically assumes that only one of the subterms will be a statement (otherwise it would be control-flow).
Again, the template program returns a list of tuples of method names
and the complexity.
$ strc -i npath-metric.str -la stratego-lib
$ parse-java -i Metric1.java | ./npath-metric
If you don't use boolean operators in the sample Java programs, then
you can compare the results with the NPath metric of Checkstyle.
Again, it might be fun to compare the implementation with Checkstyle
(PMD does not implement this metric)
Comparing to Checkstyle
If you want to, you can compare your results with the ones of
$ java -jar checkstyle-all-4.1.jar samples/Metric1.java -c samples/config.xml
samples/Metric1.java:3:3: Cyclomatic Complexity is 4 (max allowed is 0).
samples/Metric1.java:3:3: NPath Complexity is 6 (max allowed is 0).
samples/Metric1.java:17:3: Cyclomatic Complexity is 2 (max allowed is 0).
samples/Metric1.java:17:3: NPath Complexity is 2 (max allowed is 0).
Collecting Uncaught Exceptions (
Estimation: 120 minutes
As part of the implementation of an extract method refactoring, the
uncaught exceptions in a code fragment need to be determined. This can
be implemented using a collecting strategy, similar to collecting free
variables. Extend the given template module to report the uncaught
exceptions for every method. The template will print
You need to handle the full Java language, including local class
declarations. However, for technical reasons you can ignore the
exceptions thrown by a constructor invocation: Dryad does not yet
attach an easy to use declaration attribute to constructor
Given this restriction, exceptions can be thrown by two language
statements and method invocations. Method
invocations have a
attribute, which you can
use to lookup the method declaration.
Some relevant strategies in
type-attr, returns the type of an expression
compile-time-declaration-attr, returns the compile-time declaration of a method invocation as a canonical method name.
lookup-method give a canonical method name, returns an object representing a method declarations
get-declared-exception-types returns the exception types a method declares to throw.
is-assignment-convertable(|to) succeeds if the current type is convertable to the type
to by an assignment conversion.
Of course, you can use any strategy you want, from the Dryad Library
as well as the Stratego Library.
$ ./collect-uncaught-exceptions -i samples/Exceptions.java