Milestone 4 : Static Analysis for Error Reporting

Your task in this milestone is set in the context of the StaticJava compiler; you will not be dealing with the language features in ExtendedStaticJava. You will implement a static analysis and use the results of the reaching definitions (RD) analyses to provide reports of potential errors in the program. These will be implemented using the control flow graph (CFG) and monotone dataflow framework (MDF) components in the SJC compiler.

Specifically, you are to extend the main method of the SJC compiler so that it

• reports unreachable statements in SJ programs;
• reports references to potentially unitialized variables references; and
• reports unused assignment statements.

Your extended SJC compiler should issue error messages of the form:

• "unreachable statement : " concatenated with the string for the JDT statement node. For compound statements, you need only list the entire compound once do not list all of the contained statements as well.
• "uninitialized variable x in statement : " concatenated with the string for the JDT statement and where x is the string for the variable name.
• "unused assignment : " concatenated with the string for the JDT assignment statement.

For extra credit, you can implement available expressions (AE), as discussed in class, and/or constant propagation (CP). CP calculates whether a variable reference must produce a single constant value. You are free to choose a convenient format for presenting the results of AE and CP applied to an input program. You can receive up to 25 additional points for completing this extra credit.

You must submit your assignment through the course Project Upload site by 11:59pm CDT on Friday Nov 16, 2007. Solutions submitted after the deadline will have their score reduced by 10% for each hour that they are late; late times will be rounded up to the next highest hour for this calculation.

Download the file myname-milestone4.zip

This contains a skeletal implementation of the milestone with a JUnit test ing framework for your use.

In order to import the projects into your workspace, do the following:

Goto the "File" menu, select "Import". Expand "General" and select "Existing Pro jects into Workspace". Click "Next". Select "Select archive file:" and click the "Browse" button associated with it. In the file browser, points to the myname-m ilestone4.zip that you downloaded.

You should see "myname-milestone4", check the box, and click "Finish".

If you run Eclipse appropriately (i.e., using Java 5.0 and the right versions of plugins and by following the instructions in the course quick notes website), y our workspace should be set.

Make sure you rename "myname" in the project's name into your CIS username by ri ght clicking the project, select "Refactor" -> "Rename...".

• Remember that in RD we represent that memory locations are initialized elsewhere in the program as either the FieldDeclaration (for fields) or SingleVariableDeclaration (for meethod parameters) and we represent that a local variable is uninitialized using VariableDeclarationStatement (for local variables).
• You will find it convenient for a number of analyses to implement a customized ASTNode visitor to gather all of the necessary data for producing your gen/kill sets. For example, you may need gather the variables or expressions that are referenced, but not assigned to, in statements (e.g., assignments, method calls, if, while, ...). Given that statements may contain arbitrarily complex expression a visitor is the best way to traverse the expression structure. When gathering expressions, make sure that syntactically identical expressions are mapped to the same value in your representation, i.e., don't use the expression JDT node to represent the expression.
• If you are trying to test your unreachable code detector you can compare to the output calculated by Eclipse itself (it underlines unreachable code in red). Note that our implementation shows all unreachable statements whereas Eclipse only shows the first in a sequential block of unreachable statements - so ours is a bit nicer! Eclipse will also show you potentially uninitialized variable references. Eclipse does not currently show you unused assignment statements.
• When processing statements in your analyses, recall that JDT Blocks are considered statements. In fact, they will be considered the "extremal" statements for the method body, so the MDF "init" value will be applied to the input of that block. You should take care when generating gen/kill sets for blocks so that you don't unintentionally gather facts for blocks that will be redundant with respect to the statements contained within the block. One way to protect against this is to only generate an non-empty gen/kill set for the specific type of statement that your analysis targets (i.e., actually test the type of statement and then generate the return set).

You are to implement your solution as an extension to the sjc compiler. Submit the entire project as a zip file so that we can unzip your project and execute the SJC compiler with your extensions. Put the analysis driver and output producing files into the appropriate directories, i.e., StaticErrorDetection.java goes in src-sjc/sjc/analysis, and StaticErrorDetectionTest.java goes in src-sjc-test/sjc/test. Please do not modify these files except to add new test cases to the JUnit test.

Your solution should consist of the following :

• your extended SJC analysis components;
• test cases for each of the different error reports that your compiler can produce that illustrates the functionality of your error checks installed in src-sjc/src-examples;
• an extended version of the JUnit test driver StaticErrorDetection.java, located under the src-sjc-test directory of the project structure, that runs your test cases and including Factorial.java and Power.java

As with all programming, I expect that you provide reasonable internal documentation describing tricky/subtle parts of your implementation. If you have any limitations in your implementation you should include documentation describing those as well, since if we find them we will assume that you did not. In addition, if you solve the extra credit, I expect you to describe your analysis output format.

This project will be graded in large part by subjecting it to a large number of tests. It is in your best interest to do a good job of testing.