HTTPS SSH

JastAddJ-IntraFlow

An extension to the JastAdd extensible Java compiler (JastAddJ) adding
intra-procedural control flow, dataflow, and dead assignment analysis
on top of the abstract syntax tree. This approach is described in more
detail in the following paper:

  • Extensible Intraprocedural Flow Analysis at the Abstract Syntax Tree Level
    Emma Söderberg, Torbjörn Ekman, Görel Hedin, Eva Magnusson
    Science of Computer Programming, Elsevier Science B. V.,
    Volume 78, Issue 10, 1 October 2013, Pages 1809–1827
    Download paper here

The flow analysis modules were originally developed for Java 5. They
have since been extended to support also Java 6 and 7. An extension
for Java 8 is planned.

Obtaining the Modules

The latest compatible version of JastAddJ is a submodule in this
repo. To clone the IntraFlow code together with this version of
JastAddJ, use:

git clone git@bitbucket.org:jastadd/jastaddj-intraflow.git --recursive

Note the --recursive flag! If you have previously cloned this
repository and forgot the --recursive flag, use:

git submodule init
git submodule update

You should now be able to build and run the tests:

cd jastaddj-intraflow
ant test

If you do not wish to check out the submodule, e.g. if you already
checked out JastAddJ somewhere else, you can change the property
jj.root in the build.xml file to point to another location.

Test Organization

Currently, only control flow is tested. There are no test cases yet for dataflow analysis or dead assignment detection.
Control flow is tested by generating a control flow graph in dot format.

The testing framework looks for tests in the directory tests. The
tests are organized in sub-directories according to the type of Java
element they are involved with.

Each test directory must contain the file Test.input. This is what
identifies the directory as being a test directory.

Each test directory typically contains the following files:

  • description: a short description of the test case
  • Test.input: a Java file to be analyzed during the test
  • out.expected: the expected control flow graph
  • Test.java: currently not used
  • Test.properties: test case options (see below)

Test Suites

Two test suites are currently defined:

  • src/java/test/TestAll.java This test suite runs all currently
    integrated tests.
  • src/java/test/TestBugs.java This test suite contains tests that do
    not currently pass due to known bugs.

New test suites can be defined by copying and modifying the existing
ones. The test suite properties are specified in the static
initializer.

Example of how to initialize the test properties so that only block
statement tests are run, with internal node names written in the visual
control flow graphs:

static {
  properties.put("nodeNbrs", "true");
  properties.include("block");
}

The set of tests that will be executed may be defined using
properties.include() and properties.exclude(). The framework will
start with the empty set of tests and add all included tests. If
nothing is explicitly included, all tests will be added to the
set. Then, any tests that are explicitly excluded are removed from the
set. The remaining set of tests will be executed.

Properties may be defined with properties.put(). The following
properties are supported:

  • nodeNbrs: turns on node numbers for every single test, see below.

Test Running

There are two commands that test the module:

ant test
ant testvis

The testvis target generates PNG files of the control flow graphs
using Graphviz Dot. The path to dot must be specified in
build.properties.

The following steps are performed for each test:

  1. Test case properties are extracted from the file Test.properties
    if it exists. See below.
  2. The file Test.input is parsed and analyzed by the JastAddJ
    compiler. A Graphviz dot specification for the control flow graph of
    the first body declaration is generated and written to the file
    out.dot.
  3. The out.dot file is compared to the out.expected file in the
    test directory. See below for details.
  4. If there are differences in the files, an additional dot
    specification is written to diffGraph.dot, showing the differences
    between the expected and actual output.
  5. (if the testvis target in the build script is run) A PNG image of
    the resulting graph, out.png is generated. If there were differences
    between the expected and actual output, a PNG image diffGraph.png is
    also generated. This image shows unexpected elements in red. Missing
    expected elements are coloured red and drawn with dashed lines.

All generated files are put in a sub-directory to tmp with the same
name as the sub-directory to tests.

Test Properties

The Test.properties file may contain the line

options=<options>

<options> is a comma-separated list containing any options supported
by the JastAddJ version in use, and/or any of the following options
specific to the test framework:

  • --rigid: This can be used if nodes in the generated graph image
    are placed in the wrong order, but may result in more cluttered edges.
  • --nodeNbrs: This option appends the internal node numbers used in
    the dot specification to the drawn nodes, for debugging graph
    specifications. It can also be specified for a whole suite of tests
    (without the double dash), see above.

Adding new test cases

A minimal test directory contains the files Test.input and
out.expected. Test.input is a Java file free of compile-time
errors. out.expected contains a representation of the expected
control flow graph for the first body declaration in the input file.

The format of the out.expected files is flexible. Only the lines
that specify control flow edges are considered, so the files do not
have to contain the whole Graphviz specification. At a minimum, a line
must be in the format X -> Y in order for the test runner to be able
to match it to the output. If X and Y are not sibling nodes, it
is recommended to also provide the option [constraint=false] for the
edge, because then the diff graph will be more accurate and/or stable
in case of a failed test. The test runner can also handle
end-of-line-style comments (//comment continues until end of line)
in the out.expected files.

To facilitate the creation of out.expected files,
util.ASTDotGraphPrinter can be used. This utility accepts the same
options as the test framework. The following example assumes that the
class file is located in bin and Beaver in
jastaddj/tools. Internal node numbers will be visible in the
generated graph:

java -cp bin:jastaddj/tools/beaver-rt.jar util.ASTDotGraphPrinter in.java --nodeNbrs > out.dot
dot out.dot -Tpng -O

The above commands will generate a PNG image of the CFG called
out.dot.png. If the --nodeNbrs option was used, the nodes in the
image will have a number N within parentheses at the end. Nodes are
named simpleClassName_N in the dot specifications, so a node
labeled AST.Block (1) in the image can be referred to with Block_1
in the out.expected file.

At the moment, images for the more complex graphs are sometimes not
very readable. The children of a node are sometimes displayed in an
incorrect order or even mixed with children of another node. This can
sometimes be fixed using the --rigid option, see above.

Tools Used

JastAddJ-IntraFlow uses the same libraries as JastAddJ. See the Readme
for JastAddJ for more information.

Additionally, the IntraFlow modules use JUnit for unit tests. In order
to be able to visualize the control graphs and highlight errors in the
test cases, Graphviz must be installed.

Building

The build file is configured to look for the Java 4, 5, 6, and 7 frontend modules
from the JastAddJ compiler specification. The
paths to these modules are configured in the build.properties file.

To do a basic build run:

  $ ant

Eclipse users are recommended to use the frontend-gen target
instead, which skips the javac step.

Selecting liveness or reaching definition analysis

By default, the build includes liveness analysis, but not reaching definition analysis.
You can include reaching definition analysis by uncommenting the exclusion of the file
JavaReaching1.4.jrag in the build.xml file.

There are two implementations of dead assignment analysis; one
uses liveness analysis (JavaDeadAssigns.jrag), and the other uses the reaching definition
analysis (JavaDeadAssignsReaching.jrag). By default, the one using liveness analysis is included in the build.
You can switch to the other one by commenting/uncommenting the exclusion of the files in the build file. Note that you cannot include both at the same time, because they define the same attributes, but in different ways. Note also that if you switch to JavaDeadAssignsReaching.jrag, you need to include the JavaReaching1.4.jrag analysis as well.

The build file contains comments on how you can edit it to select the different variants.

Example main program for dead assignment analysis

The class org.jastadd.jastaddj.flow.JavaDeadAssignChecker is an example main program that identifies dead assignments in Java programs. Its source code is located in src/java. It subclasses the FrontEnd class in the JastAddJ compiler. Try it out as follows (standing in the jastaddj-intraflow directory):

java -cp bin:jastaddj/tools/beaver-rt.jar org.jastadd.jastaddj.flow.JavaDeadAssignChecker examples/AssignTest.java

To see what options are available:

java -cp bin:jastaddj/tools/beaver-rt.jar org.jastadd.jastaddj.flow.JavaDeadAssignChecker -help

Example main program for liveness analysis

The class org.jastadd.jastaddj.flow.JavaLivenessChecker is an example main program that prints the live variables after each statement in Java programs. Its source code is located in src/java. It subclasses the FrontEnd class in the JastAddJ compiler. Try it out as follows (standing in the jastaddj-intraflow directory):

java -cp bin:jastaddj/tools/beaver-rt.jar org.jastadd.jastaddj.flow.JavaLivenessChecker examples/DataFlowTest.java

Liveness information is computed by the attributes in the file
src/jastadd/JavaLiveness1.4.jrag.

The program makes use of the aspect src/jastadd/PrintLiveness.jrag to traverse the AST of each compilation unit and print the information for each statement.

  • Copyright (c) 2007-2014, JastAddJ-IntraFlow Committers

All rights reserved.

JastAddJ-IntraFlow is covered by the Modified BSD License.
The full license text is distributed with this software.
See the LICENSE file.