Assignment Collecting Strategies

Introduction

Important: 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.

• pt4-base.tar.gz

Measuring Execution Paths

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 PMD and 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:

• Description
• Implementation

Checkstyle

• Description
• 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:

$ 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)]

NPATH Complexity (npath-metric.str)

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 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:

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

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:

• Description
• Implementation

Comparing to Checkstyle

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

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

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:

$ ./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