AST Analysis: Variable & Method Renaming

In this exercise we will implement variable & method renaming on MiniJava ASTs.

Developing some familiarity with the MiniJava AST.
Implementing useful analyses and transformations on top of the AST.
Understanding scoping and resolving variables' name.
Traversing the class inheritance hierarchy.
Resolving method calls according to the static type of the object.

In the next exercises you will these, especially the latter three points, to perform code generation and semantic checking on the AST. You will probably want to reuse some of the code from the current exercise when performing these tasks.

You will support renaming variables and methods. Renaming variables supports renaming local variables, formal parameters, and fields. You don't need to support renaming the formal parameter of the main method (it's treated differently in MiniJava). The resulting program must be semantically equivalent to the original.

Assume that the given variable/method name and the line number uniquely define the declaration which you will rename. The line number is in the lineNumber element under either the tag vardecl, formal, field, or methoddecl.

You do not need to check that there won't be a name collision after renaming to the new name provided.

Assume that the given MiniJava program passes all the semantic checks for Java programs, and also satisfies all the semantic restrictions special to MiniJava. The full list of checks appears in the semantic checking exercise, where we will (later in the course) enforce these restrictions; in this exercise we will simply assume that such programs have already been filtered out. For example, valid MiniJava programs disallow the declaration of a field with the same name as in the superclass, so you don't need to support this in the symbol table.

Usage

The command
java -jar mjavac.jar unmarshal rename var <original var name> <line number> <new name> inputProg.xml outputProg.xml
will write to outputProg.xml the AST of a program obtained by renaming the variable with the specified name whose declaration appears in the specified line number (according to outputProg.xml, not the original Java file) into the new name specified. (In the examples we provide, the line number in the XML indicates the line where the next token after the declaration begins, which might be a bit confusing at times; this has to do with some parser-related laziness on my behalf. Ignore the original lines in the file and use the ones specified in the XML.)
The XML representation of ASTs is explained here and in the recitation.

The command
java -jar mjavac.jar unmarshal rename method <original method name> <line number> <new name> inputProg.xml outputProg.xml
will write to outputProg.xml the AST of a program obtained by renaming the method with the specified name whose declaration appears in the specified line number (according to outputProg.xml, not the original Java file) into the new name specified.

Important: the output XML must be exactly the same (ignoring formatting) as the input XML, except of course for changing the name where appropriate; don't change any line numbers etc. Otherwise our grader will be miserable, and such things tend to propagate to everyone else involved.

Examples

Here (see the readme).

Solution Guidelines

Resolving Variables' Names and Scoping

As mentioned earlier, by "variable" we mean both a local variable, a formal parameter, and a field. In MiniJava there are no global variables, and there are no nested local scopes in methods. (This should make your life easier.)

When renaming a variable you must rename all of the references to this variable. Thus, whenever the code refers to a name that matches the variable you're renaming, you must check whether this name refers to that variable - it could also refer to a different local variable of the same name, or to a field.

Note that a variable may be used both as an l-value (namely, it is assigned to) or as part of an r-value (namely, in an expression for the value assigned) or some other expression (loop condition etc.).

Traversing the Class Inheritance Hierarchy

When renaming a method you must also rename all the methods it overrides and that override it, and the calls to these methods. Suppose you want to rename a method defined in B; then given a class C you need to know whether it is a subclass of B. You also need to know whether A is a superclass of B that has a method with the same name, so if C is a subclass of A (even if not of B!), it is also affected. (Recall that overloading is not part of MiniJava - otherwise you would have need to check whether the method has the same signature. Here the name is indicative enough.)

To simplify the process of deciphering the relationships between classes you can exploit the limitation in MiniJava that the superclass must appear in the file before the class (see the description and the list of semantic checks).

Resolving Method Calls

To correctly rename a method you will need to analyze each method call to see if it is to the method you wish to rename. It is incorrect to rely solely on the method's name, because the same name can be used in several different classes; for example, foo may be a name of a method in both B and C (even with completely different signatures) when neither is a subclass of the other.

Resolving the method call o.f(...) thus depends on the object on which it is invoked: you need to know the static type of o. We will talk about static typing in depth later in the course. In this exercise (and the following), exploit the restriction that in MiniJava, method invocations can only be performed on an object that is the result of very simple expressions: in o.f(arg1, ...) expressions, o must be either a local variable, a field, a new A(), or this, but more complex expressions for o are disallowed. In all these cases, the static type is clear (in the variable declaration or in the expression itself), so you can use it to generate code.

Also here, recall that overloading is not supported in MiniJava.

I Don't Want To Miss a Thing

Make sure you perform the renaming on all program elements, including all statements and expressions (e.g. conditions in if, the index expression in an assignment to array, ...). Look carefully at the fields of each AST node, and consider how your analysis should continue the traversal over the tree through each of them.

Last Tip

It's perfectly OK to perform the renaming by modifying the AST you load, and we have provided setter methods for this purpose. However, make sure to perform the changes only after completing your traversals of the AST; otherwise, your visitors observe an AST that's not quite the original program.