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.