[Solved] Assignment 4: Static Analysis

5/5 – (3 votes)

This assignment explores static analysis. Specifically, it asks you to implement a type-checker for the miniJava language and an analysis that detects missing return statement in miniJava programs. You will implement these two tasks by writing a single program, to be called Checker.java. The program readsin an miniJava AST tree, and traverses the tree to perform the type-checking and the analysis tasks. This assignment also includes an optional task for detecting uninitialized variables. The assignment carries a total of 100 points (not counting the optional part, which carries an additional 15 points).

The assignment assumes familiarity with the OO tree-traversal techniques discussed in Labs 7 and 8, and is intended to be attempted after you have completed those labs.PreparationDownload the zip file hw4.zip from the D2L website. After unzipping, you should see an assignment3 directory with the following items:hw4.pdf this documentmjManual14.pdf the miniJava language manualChecker0.java a starting version of the checking and analysis programast a directory containing the AST definition program file, Ast.java (the same as in hw3), and a set of Java programs for an AST parsertst a directory containing sample miniJava programs programs in both .java and .ast forms (the same as in hw3)tst2 a directory containing miniJava programs with type errors and programs for testing the two anaysesMakefile for building the parserrunck a script for running testsCopy Checker0.java to Checker.java and add code to it to complete this assignment.

Program StructureConceptually, the type-checker and the return-statement analysis are to be implemented as computations over miniJava AST trees. But instead of inserting local computation routines into individual AST node classes as we have seen in Labs 7 and 8, we take a slightly different approach in this assignment. Youll stillwrite code for individual AST nodes, but instead of modifying the Ast.java program file, all your code will be placed in a separate file, Checker.java. With an AST tree read in from input via the provided astParser, a couple of dynamic dispatch routines will send the execution to the proper individual routines to perform type-checking and return-statement analysis. Take a look inside the program Checker0.java to see more details of the program structure.

Environment ManagementAs we have seen in Lab 8, environments are a key part of many computations over ASTs. They are used for mapping variables to their types or values, functions to their definitions, and so forth. They provide symbol-related contexts for computations at individual AST nodes. For the tasks of this assignment, we alsoneed environment support. For instance, to type-check expression a+b, we need to know variables a and bs types; to type-check a NewObj node, we need to verify the corresponding class exists; and to type-check a method call, we need to find the methods definition, so that we can verify that the number and types ofactual arguments match those of the formal parameters.In miniJava, variable declarations may only appear at class level or at method level. In other words, there are no nested scopes in the form of statement blocks. This means that there are only three scope levels in a miniJava program. The global scope, in which classes are defined; a class scope for each class, in which fields and methods are defined; and a method scope for each method, in which local variables and parameters are declared.Accordingly, we use the following environments in the checker program: A name-definition environment for classes. While a mapping from Strings to ClassDecl AST nodes would work, it would not be very convenient for accessing a classs parents information, which is frequently needed in type-checking. So we define a wrapper data structure to have a direct pointer from a class declaration to its parents declaration:static class ClassInfo {Ast.ClassDecl cdecl;ClassInfo parent;}The class environment hence is defined to be a mapping from Strings to ClassInfo nodes. A name-type environment for a methods local variables and parameters, e.g. a mapping from Strings to Type AST nodes. Note that local variables and parameters of a method are in the same name space (e.g. a local variable and a parameter cant share the same name), hence they are represented in a single environment.Since methods scopes are non-overlapping, we use a single static copy, typeEnv, for representing this environment. Your checker program should reset this environment to empty at the beginning of the check routine for the MethodDecl node, so each method will have a fresh new copy of the enrironment. For field variables and method declarations, we choose not to create separate mapping environments. Instead, we rely on the ClassDecl AST nodes own flds (a VarDecl[]) and mthds(a MethodDecl[]) components. For instance, to find a field xs type, we would (linearly) search the host ClassDecl nodes flds component for a matching VarDecl and fetch the type information from it.A pair of utility routines, findFieldDecl(String fname) and findMethodDecl(String mname),serve as the equivalence to environments get() routine for fields and methods. Both are to be invoked from a ClassInfo object.The reason for this choice is because the name space for fields and the name space for methods are both complicated by the languages inheritance features (e.g. we have to include ancestors fields, but not those that are overshadowed, etc.). So we chose simplicity over performance on this one.Overall, the following are the static variables defined for environment support. The whole environmentmanagement portion of the type-checking program is provided to you in Checker0.java.2from Checker0.java//// Global Variables// -// classEnv an environment (a className-classInfo mapping) for class declarations// typeEnv an environment (a var-type mapping) for a methods params and local vars// thisCInfo points to the current classs ClassInfo// thisMDecl points to the current methods MethodDecl//private static HashMap<String, ClassInfo classEnv = new HashMap<String, ClassInfo();private static HashMap<String, Ast.Type typeEnv = new HashMap<String, Ast.Type();private static ClassInfo thisCInfo = null;private static Ast.MethodDecl thisMDecl = null;Your Task 1: Type-Checking (70 points)The main task of this assignment is to implement a type-checker for the miniJava language. The type-checker traverses the input AST tree, and for each node in the tree, check its correctness with respect to miniJavas typing rules. Once a type error is detected, the checker program raises a TypeException and quits.The miniJava languages typing rules follows that of Javas. Here are some highlights. For cases that are not covered here (shouldnt be many), consult miniJavas language manual and Java documents. Every class, method, or variable used in a program must be declared. For a variable, the declaration must appear before its uses. Variable initialization, assignment statement, and actual argument to formal parameter mapping must all follow type compatibility requirements. (See Type Compatibility section below.) The number of actual arguments in a method call must match that of the methods formal parameters.Every return objects type from a method must match the methods declared return type. The test of If and While statements must be boolean. The argument of Print statement must be integer, boolean, or String. The object with which a method or a field is accessed must be a class object. The object in an ArrayElm node must be an array object; and the index must be integer. Arithmetic operations must have integer operands; logical operations must have boolean operands;equality comparisons (== and !=) must have operands with comparable types; other relationaloperations must have integer operands.In the provided program, Checker0.java, type-checking hints are provided for all AST nodes.Note that every check routine for an AST expression node needs to return the expressions type in the form of an Ast.Type object. For some nodes, this may involve analysis and searching. Also, it goes without saying the every check routine should recursively check its components by invoking their corresponding check routines.Type Compatibility (10 points)Javas type compatibility rules are expressed by the following two routines:

Type Compatibility Routines// Returns true if tsrc is assignable to tdst.//boolean assignable(Ast.Type tdst, Ast.Type tsrc) {// if tdst==tsrc or both are the same basic type// return true// else if both are ArrayType // structure equivalence// return assignable result on their element types// else if both are ObjType // name equivalence// if (their class names match, or// tdsts class name matches one of tsrcs ancestors class name)// return true// else// return false}// Returns true if t1 and t2 can be compared with == or !=.//private static boolean comparable(Ast.Type t1, Ast.Type t2) throws Exception {return assignable(t1,t2) || assignable(t2,t1);}As part of your type-checking task, you are asked to convert the pseudo code in the first routine to actual Java code. This part carries a separate 10 points of its own.Your Task 2: Detecting Missing Return Statement (20 points)For a method that has a non-void return type, a return statement is required within every possible execution path of it. The Java compiler, javac, performs a static analysis to detect and flag method that is missing a return statement. For instance, compiling the following program,retn01.javaclass Test {public int m() {// missing return statement}public static void main(String[] a) { }}javac would issue an error:linux javac retn01.javaretn01.java:4: error: missing return statement}1 errorLike many other static analyses, this one calculates an approximation of the programs runtime behavior;that is, its prediction of the runtime behavior may be wrong in some cases. But the analysis only errs in one direction: it might flag some methods that really will always execute a return statement, but it never fail to flag a method that might actually not execute a return statement. As an example, for the following program,

retn02.javaclass Test {public int m() {if (true)return 1;// missing return statement}public static void main(String[] a) { }}we can be certain that the return statement will always be executed, yet, javac will still flag a missing return statement error.In this part, you will design and implement a return-statement analysis by adding code to the type-checking program you wrote for the first part. In your analysis, you may assume that all expressions values are unknown. You may also assume that the input AST has already been type-checked, i.e. that it represents a type-correct program.A set of test programs for this analysis are included in the tst2 directory: retn0[1-8].java. You may want to use them to help you derive a strategy. You may also run javac on more programs to see its behavior on this analysis. (Note that in some cases, javac uses expressions values to refine the analysiss result, which you dont need to do.) You are free to introduce new global or local variables for your need. (Hint: Focus on If and While nodes.)Optional Task: Detecting Uninitialized Variables (15 extra points)This part is optional. You should only attempt this after you finished both required tasks. The extra pointsyou earn from this part can be used to offset any points you lost in this or previous assignments. However, if youve already got 100% on your assignments, then the extra points would not have any real effect on your grade. Being a strongly-typed language, Java requires that every variable be initialized before being used. A static analysis is included in javac to catch uninitialized variables. For instance, the following programinit01.javaclass Test {public void m() {int i = 1;int j;System.out.println(i + j); // j not initialized}public static void main(String[] a) { }}will trigger an error:linux javac init01.javainit01.java:5: error: variable j might not have been initializedSystem.out.println(i + j); // j not initialized1 errorYour task is to add this analysis to your Checker.java program. You may use the same assumptions as in the return-statement analysis. In fact, the implementation strategies for these two analyses are similar, although this analysis is a little more challenging. A set of test programs for this analysis are included in the tst2 directory: init0[1-6].java.

All programs in the tst directory have been type-checked. You should expect to see the message passed static check when running your checker:linux ./runck tst/test01.ast tst/test01: passed static checkThe programs, typerr*.ast, in the tst2 directory each contains a type error. The runscript will compare your checkers error messages with reference messages in the .err.ref files.Your error messages should match the corresponding reference ones in nature. However, they dont need to match character-by-character.