Assignment Collecting Strategies

%TOC%

---++ Introduction

%RED%Important:%ENDCOLOR% 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
the assignments.

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,
and a =config.xml= file for Checkstyle.

   * [[http://losser.labs.cs.uu.nl/~mbravenb/pt4-base.tar.gz][pt4-base.tar.gz]]

---++ Measuring Execution Paths

---+++ <nop>McCabe's Cyclomatic Complexity (=cyclomatic-complexity.str=)

Estimation: 15 minutes

In this exercise, we ignore local class declarations and anonymous
classes.

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 [[http://pmd.sourceforge.net/][PMD]] and
[[http://checkstyle.sourceforge.net/][Checkstyle]].

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 =cyclomatic-complexity.str= 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
complexity.

PMD:
   * [[http://pmd.sourceforge.net/rules/codesize.html#CyclomaticComplexity][Description]]
   * [[http://pmd.sourceforge.net/xref/net/sourceforge/pmd/rules/CyclomaticComplexity.html][Implementation]]

Checkstyle
   * [[http://checkstyle.sourceforge.net/config_metrics.html#CyclomaticComplexity][Description]]
   * [[http://cvs.sourceforge.net/viewcvs.py/checkstyle/checkstyle/src/checkstyle/com/puppycrawl/tools/checkstyle/checks/metrics/CyclomaticComplexityCheck.java?rev=1.9&view=markup][Implementation]]
   * [[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]]

Example:
<verbatim>
$ strc -i cyclomatic-complexity.str -la stratego-lib
$ parse-java -i Metric1.java | ./cyclomatic-complexity
[("foo",4),("bar",2)]
$ parse-java -i Metric2.java | ./cyclomatic-complexity
[("example",12)]
</verbatim>

---+++ NPATH Complexity (=npath-metric.str=)

Estimation: 45 minutes

One of the problems with <nop>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 =switch= 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
expressions.

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
     =java-typematch= module.

   * 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.

Example:
<verbatim>
$ strc -i npath-metric.str -la stratego-lib
$ parse-java -i Metric1.java | ./npath-metric
[("foo",6),("bar",2)]
</verbatim>

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)

Checkstyle:
   * [[http://checkstyle.sourceforge.net/config_metrics.html#NPathComplexity][Description]]
   * [[http://cvs.sourceforge.net/viewcvs.py/checkstyle/checkstyle/src/checkstyle/com/puppycrawl/tools/checkstyle/checks/metrics/NPathComplexityCheck.java?rev=1.4&view=markup][Implementation]]

---+++ Comparing to Checkstyle

If you want to, you can compare your results with the ones of
Checkstyle.

<verbatim>
$ java -jar checkstyle-all-4.1.jar samples/Metric1.java -c samples/config.xml
Starting audit...
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).
Audit done.
</verbatim>

---++ Collecting Uncaught Exceptions (=collect-uncaught-exceptions.str=)

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 =none= for every
method.

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
invocations.

Given this restriction, exceptions can be thrown by two language
constructs: =throw= statements and method invocations. Method
invocations have a =CompileTimeDeclaration= attribute, which you can
use to lookup the method declaration.

Some relevant strategies in =libdryad=:
   * =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.

Example:
<verbatim>
$ ./make-collect-uncaught
$ ./collect-uncaught-exceptions -i samples/Exceptions.java
thrower
  none
f
  - java.io.IOException
  - java.lang.Exception
  - java.lang.IllegalArgumentException
g
  - java.io.IOException
  - java.lang.Exception
h
  - java.io.IOException
  - java.lang.Exception
i
  none
j
  - java.io.IOException
k
  - java.lang.NullPointerException
innerF
  - java.util.NoSuchElementException
</verbatim>