Assignment Patterns Rules Strategies Traversals

Introducing the Stratego Compiler and Interpreter

In this assignment you will use Stratego to implement a number of small Java program transformations. Stratego can be executed in an interpreter or by compiling it first and then running the executable program.

Stratego Programs

A Stratego programs has a main strategy, which can optionally be specified on the command-line and defaults to main. Usually, this main strategy is an io-wrap of some strategy. The io-wrap strategy takes care of command-line arguments, input and output.

The skeleton of the Stratego program for this assignment is:

module pt2
imports
  Java-15
  libstrategolib

strategies

  main =
    io-wrap(exc-4)

strategies

  exc-4 =
    id

Note that this program imports Java-15. This module is part of java-front and for this exercise it is easier to copy it to your working directory:

$ cp ~/.nix-profile/share/java-front/Java-15.rtree .

This Stratego Signature for Java describes the AST representation of Java in Stratego, similar to an RTG. You can find the complete signature at ~/.nix-profile/share/java-front/Java-15.str.

Stratego Compiler

Stratego programs can be compiled using the Stratego Compiler:

$ strc -i pt2.str

The resulting program will be much faster than the interpreter, but the compilation itself takes some time. However, for larger examples this additional compilation time is well spent.

If the Stratego program imports libstrategolib (which is the case for pt2.str, then you need to link with libstratego-lib:

$ strc -i pt2.str -la stratego-lib

After compilation, the Stratego program can be applied in a pipeline:

$ echo "x == true" | parse-java -s Expr | ./pt2 | pp-java
x

Stratego Interpreter

A Stratego program can also be interpreted. This is usually a bit faster then compilation followed by a single application, but soon gets slower if you want to apply the program multiple times.

$ echo "x == true" | parse-java -s Expr | stri pt2.str | pp-java
x

Of course, you'll get a different result, since this is one of the assignments.

Stratego Shell

For interactively learning the Stratego language, you can use the Stratego Shell. You can start the Stratego Shell using the shell command stratego-shell. In the Stratego Shell, use the following command to learn more about the commands of the Stratego Shell.

stratego> :help

As an example of a command, you can close the Stratego Shell with :quit, :exit or :q.

The Stratego Shell can be included in a pipe. In this assignment we will use the Java language, so you can use parse-java to parse input program and then pipe the result into the Stratego Shell. Optionally, you can specify a sequence of commands on the command line, separated by ;;.

$ echo "class Foo { void Foo() {} }" | parse-java -s TypeDec | \
    stratego-shell --cmd 'import pt2;; exc-14' | pp-java
class Foo
{
  Foo()
  { }
}

Note that you can invoke any strategy in this way (in this case exc-14) and that the strategy is not wrapped in an io-wrap. Also, note that this is again the solution of one of the exercise. In your skeleton, this strategy is not yet defined and if you define it as id, the output will be the same as the input.

If you don't provide a --cmd argument, then the interactive Stratego Shell will be started and the current term will be the current term of the pipe. For example:

$ echo "if(x != y);" | parse-java -s BlockStm | stratego-shell
stratego> :show
If(NotEq(ExprName(Id("x")),ExprName(Id("y"))),Empty)
stratego> 

Stratego Modules

Stratego Modules are stored in files with the .str extension. You can import Stratego modules into the Stratego Shell with the command import.

stratego> import SmallExercises

Standard library modules can also be included in this way:

stratego> import integers

But, it is more common to import the headers of the separately compiled Stratego Library:

stratego> import libstrategolib

You can use tab expansion to see what strategies are defined.

Introspection and Debugging

In the Stratego Shell, you can use some commands for debugging and inspecting the current environment.

• :show prints the current term

• :binding and :bindings commands can be used to reflect over the current state of your Stratego program.

• :trace on will from now print a very detailed description of the strategies that are evaluated by the Stratego Shell. You can turn it off using :trace off.

• The strategy #bar introduces a break point bar. If evaluation reaches this break point, then a break shell will be opened. You can inspect the state of the program in this break shell and continue evaluation using :continue.

Using the Stratego Library

In some parts of this assignment, you are allowed to use the Stratego Library. The library contains many useful strategies for io, list processing, traversals, and so on. API and source documentation of the Stratego Library is available online (see the navigation bar).

Pattern Matching and Strategies

Create a new Stratego module pt2.str based on the previously given template and define the following strategies. Please follow the suggested naming suggestions (exc-x). Prefix all your own strategies, including auxiliary ones, with exc.

Most of the exercises are examples of bug pattern that many bug detection tools will support. It's interesting to see how easy these bug detections are to implement in a language that supports pattern matching.

In this part of the assignment, you are not allowed to use congruences, generic traversals, or library strategies, unless explicitly mentioned.

Find Control-flow Statements (exc-1)

Implement a strategy that succeeds if the current term is a Java control-flow statement, such as the if statement, for and while loop. Completeness is not important, but support at least 3 constructs.

Parse the inputs using parse-java -s BlockStm

Example:

echo "while(true) doFoo();" | parse-java -s BlockStm | stratego-shell --cmd 'import pt2;; exc-1'

The strategy should fail for non control-flow statements.

Find Empty If Statements (exc-2)

Implement a strategy that succeeds if it is applied to an if statement that has no statements (i.e. the empty statement) in its then or else branch (for example if(x);). Usually, this indicates a bug.

Find Equality Check of True (exc-3)

Implement a strategy that succeeds if the current term is an equality operator where one of the operands is the literal true. Equality comparison to true is usually considered poor style.

Parse the inputs using parse-java -s Expr

Remove Equality Check of True (exc-4)

Implement rewrite rules that remove the equality check to true. So, the comparison of an expression to true should be rewritten to the expression itself. Apply the rewrite rules in the strategy exc-4, and make it succeed in all cases.

Again, parse the inputs using parse-java -s Expr

Find Control-flow Statements without Braces (exc-5)

Implement a strategy that succeeds if the current term is Java

control-flow statement, where one of the statements of control-flow is not a block. For example, it should succeed for the Java statement if(x) return y;, but should fail for the Java statement if(x) { return y; }. Again, completeness is not important, but at least support a few different control-flow statements.

Note that you can give all rules the same name, but you can also use different names and combine them yourself with the choice operator.

Parse the inputs using parse-java -s BlockStm

Introduce Braces for Control-flow Statements (exc-6)

Implement a set of conditional rewrite rules that introduce blocks in the branches control-flow statements, but only if the blocks are missing. Cover a few different control-flow statements. Again, define the rules separately and try to apply them in exc-6.

Parse the inputs using parse-java -s BlockStm

Find Self Assignment (exc-7)

Implement a strategy that succeeds if the current term is an expression that is a self-assignment, i.e. the left-hand side is identical to the right-hand side. Self-assignment is a common bug in constructors and setter methods.

Parse the inputs using parse-java -s Expr

Invert .equals Constant (exc-8)

For invocations of the equals method that involve a string literal, it is often a good idea to have the string literal on the left-hand side and not as the argument of the invocation. This will more gracefully handle the case where the other expression is null.

Define a conditional rewrite rule that rewrites such comparisons, but only if just one of the expressions is a literal. Example: bar.equals("foo") should be rewritten to "foo".equals(bar).

It is ok to assume that the MethodName(AmbName(Id("?")) is a variable, since we cannot apply disambiguation yet: for disambiguation, you need to have a full compilation unit, and for transforming a compilation unit we need traversals.

Try to apply the rewrite rule in the strategy exc-8

Parse the inputs using parse-java -s Expr

Invert If Not (exc-9)

Implement a rewrite rule that swaps the branches of an if statement if the conditional is an inequality check. Of course, you also need to change the inequality conditional to an equality. Again, invoke the rewrite rule from exc-9.

Example:

if(x != y)
  doSomething();
else
  doSomethingElse();

should be rewritten to:

if(x == y)
  doSomethingElse();
else
  doSomething();

Define a similar rule for the not operator:

if(!x)
  doSomething();
else
  doSomethingElse();

should be rewritten to:

if(x)
  doSomethingElse();
else
  doSomething();

Get Last Statement of Method (exc-10)

Define a strategy that returns the last statement of a method. For example, if applied to void foo() { bar(); return x; } the strategy should return return x;.

The strategy must be defined using a single pattern match, so you are not allowed to use composition operators (sequential, or whatever). But, you are allowed to define an auxiliary strategy for getting the last element of the list of statements.

Parse the input, which is a method declaration, using the start symbol ClassBodyDec.

Apply First (exc-11)

Define a strategy that applies a strategy parameter s to the first term of a list for which s succeeds. The strategy should fail if the argument cannot be applied to any of the elements. For example, exc-apply-first(\ 1 -> 4 \) applied to [3, 2, 1, 2, 3, 1] should return [3, 2, 4, 2, 3, 1].

Apply the strategy to a small example in exc-11.

Empty Catch Clause (exc-12)

Define a strategy that if applied to a Java statement succeeds if the statement is a try-catch block where one or more of the catch clauses is empty. Of course, defining an empty catch clause is bad style. Most bug detection tools support these checks.

Note that you can use the exc-apply-first strategy for this. Check that you solution can handle empty catches in a try-catch-finally.

Introduce Print Stack Trace (exc-13)

Implement a strategy that inserts prints of the stack trace of an exception in these empty catch clauses. This is done by invoking the printStackTrace method of the exception. Write a separate rule for introducing the print statement in a catch clause. Invoke this rule from your strategy.

It's allowed to use the standard map strategy in this exercise.

Resolve Method Constructor Confusion (exc-14)

Another common mistake in Java code is to define a return type in front of a constructor, which means that it becomes a method. These methods can be recognized by their name, which is the same as the class in which they are defined.

Use the exc-apply-first strategy to implement a strategy that rewrites the first wrong method declaration of a class to a constructor declaration. Of course, you define a rewrite rule for the actual rewrite to the method. This rule has to be parameterized with the name of the class. Example:

public class Foo {
  int x;

  void Foo() {
    x = 0;
  }

  void bar() {
  }
}

should be rewritten to:

public class Foo {
  int x;

  Foo() {
    x = 0;
  }

  void bar() {
  }
}

It is important that the strategy fails if there is no wrong method declaration. Next, use the standard repeat strategy to rewrite all wrong method declarations of a type declaration.

Parse the inputs with parse-java -s TypeDec.

Semantics of Choice and Guarded Choice (exc-15)

Find an example that shows the semantic difference between s1; s2 <+ s3 (left choice) and s1 < s2 + s3 (conditional choice). You don't have to use Java in this example: just use integers, lists, or whatever you want.

Traversals

Congruences

In the following two exercises you are not allowed to use generic traversals. All traversing code must be implemented using congruences.

However, we advice you to reuse the basic elements of a traversal. So, you can define traversal primitives all-Java, some-Java, and one-Java (if necessary) specific for Java constructs and define the traversal strategies by composing them.

Recursive Rewriting (exc-16)

In the first part of this assignment you have defined a number of rewrite rules that apply rewritings to the current term. In this exercise, you apply these rewriting recursively all over the tree. For this, define a congruence-based traversal that traverses a compilation unit by descending into the statements used in the class. Support a reasonable set of class body declarations and control-flow statements, but don't spend too much time on this. The point is to illustrate a congruence-based traversal and how the transformations are applied during the traversal, not to deliver a product.

Note that because you have developed the rewrite rules first, you have been forced to cleanly separate the traversal strategy from the rewrite rules. This is good style. If you have to refactor the previously defined rules (for example because you have defined the rewriting entirely in a single strategy), then just do this and remember why the rule was not reusable in this strategy.

Apply all your rewritings:

• Remove Equality Check of True
• Introduce Braces for Control-flow Statements
• Invert .equals Constant
• Invert If Not
• Introduce Print Stack Trace
• Resolve Method Constructor Confusion

Note that some rewrite rules apply to the same language construct. Solve this in you rewriting strategy: don't hack this into the reusable traversal primitives that you have defined. You don't want to force all strategies to repeat the application of the rewrite rules.

An example, illustrating some (not all!) of these problems:

public class Foo
{
  void f()
  {
    if(x != true)
      doFoo();
    else
    {
      try
      {
        doBar();
      }
      catch(Exception exc)
      {
      }
    }
  }

  void Foo(String x)
  {
    if(x.equals("Blaat"))
      this.x = x;
  }
}

$ parse-java -i Foo.java | ./pt2 | pp-java
public class Foo
{
  void f()
  {
    if(x)
    {
      try
      {
        doBar();
      }
      catch(Exception exc)
      {
        exc.printStackTrace();
      }
    }
    else
    {
      doFoo();
    }
  }

  Foo (String x)
  {
    if("Blaat".equals(x))
    {
      this.x = x;
    }
  }
}

Replace Symbolic Constant (exc-17)

Sloppy user-interface code based on the Java BorderLayout sometimes uses string literals to define the position of a component. Of course, the constants of the BorderLayout should be used for this. For example, p.add(component, "North") should be written as p.add(component, BorderLayout.NORTH).

First, define a rewrite rule that if applied to a type-checked expression, rewrites these sloppy invocations of the add method of javax.swing.JPanel to use these BorderLayout constants. Use the DeclaringClass annotation of the expression to figure out if you are dealing with the right add method.

Next, apply this rewrite rule recursively to a Java program by reusing the congruence-based traversal strategy of the previous exercise.

For this example you have to apply the dryad-front type checker instead of just parse-java. Add the following code to your module to make the DeclaringClass constructor available:

signature
  constructors
    DeclaringClass : Type -> Attribute
    
strategies

  declaring-class-attr = 
    ?_{a*}
    ; <fetch-elem(?DeclaringClass(<id>))> a*

Example:

import java.awt.BorderLayout;
import javax.swing.*;

public class Gui 
{
  public static JPanel gui()
  {
    JPanel p = new JPanel(new BorderLayout(10, 10));
    p.add(new JLabel("Enter something:"), "North");
    p.add(new JScrollPane(new JTextArea(20, 20)), "Center");
    return p;
  }

  public static void main(String[] ps)
  {
    JFrame frame = new JFrame();
    frame.getContentPane().add(gui());
    frame.pack();
    frame.setVisible(true);
  }
}

$ dryad-front --tc on -i Gui.java | ./pt2 | pp-java
import java.awt.BorderLayout;
import javax.swing.*;

public class Gui
{
  public static javax.swing.JPanel gui()
  {
    javax.swing.JPanel p = new javax.swing.JPanel(new java.awt.BorderLayout(10, 10));
    p.add(new javax.swing.JLabel("Enter something:"), BorderLayout.NORTH);
    p.add(new javax.swing.JScrollPane(new javax.swing.JTextArea(20, 20)), BorderLayout.CENTER);
    return p;
  }

  public static void main(java.lang.String[] ps)
  {
    javax.swing.JFrame frame = new javax.swing.JFrame();
    frame.getContentPane().add(gui());
    frame.pack();
    frame.setVisible(true);
  }
}

Generic Traversals (exc-18 and exc-19)

Redefine the two previous exercises using generic traversals. Try to find out if you need a single-pass, multi-pass, exhaustive, topdown, or bottomup rewriting strategy. If you have figured this out, then don't fix your previous congruence-based traversal if you find a problematic case that you could not handle earlier.

Try the effect of some different traversals, even if you see the solution immediately.

Mixing Generic and Data Type Specific Traversals

The traversal you've implemented in the previous exercises are not that common in real program transformation problems. Instead of doing the complete traversal specific for a certain data type or completely generic, the traversal is often a mixture of a generic traversal and some data type specific cases.

Find Return in Finally Clause (exc-20)

A return statement in a finally clause should be avoid, because this return statement can completely change the original result of the method: a return or a thrown exception in the try part. This is not the purpose of a finally clause, therefore compilers often warn about this:

class Fred
{
  boolean error;

  int g()
  {
    if(error)
      throw new IllegalStateException();
    else
      return 4;
  }

  int f()
  {
    try
    {
      return g();
    }
    finally
    {
      return 5;
    }
  }
}

$ javac Fred.java -Xlint
Fred.java:22: warning: [finally] finally clause cannot complete normally
    }
    ^
1 warning

For this exercise, write an transformation that annotates these questionable return statements with the string "Error". This is not entirely trivial. Thanks to local and anonymous class declarations, not every return statement in a finally clause is incorrect. So, you need to handle these constructs in a special way.

It is useful to think about this transformation as format checking. For this problem, a Java source file should be written in two different languages: in a finally clause, the allowed language is a subset of the complete Java language: no return statements are allowed. If we encounter a local or anonymous class declaration, then we switch back to the complete language.

A useful pattern for the implementation of these problems is to have two strategies, one for the complete language and one for the subset. In both strategies, specific cases are handled and maybe the context is switched to the other strategy. By default, they just traverse.

You need about 10 lines of code for this, so if your strategy is much longer, then you're doing something wrong

Example:

class Fred
{
  int f()
  {
    try
    {
      return g();
    }
    finally
    {
      class Bla
      { 
        void test()
        {
          return 6;
        }
      }
      return 5;
    }
  }
}

$ parse-java -i Fred.java | ./pt2 | pp-aterm
...
  [ Try(
      Block(
        [Return(Some(Invoke(Method(MethodName(Id("g"))), [])))]
      )
    , []
    , Block(
        [ ClassDecStm(
            ClassDec(
              ClassDecHead([], Id("Bla"), None, None, None)
            , ClassBody(
                [ MethodDec(
                    MethodDecHead([], None, Void, Id("test"), [], None)
                  , Block([Return(Some(Lit(Deci("6"))))])
                  )
                ]
              )
            )
          )
        , Return(Some(Lit(Deci("5")))){"Error"}
        ]
      )
    )
...

Submission

Pack your Stratego modules in a .tar.gz or .zip file and send your solution by email to martin@cs.uu.nl. The same day, you will get a short notification that I've received your solution. If you don't get this reply, then please contact me.

Questions

After the lab session you can still send questions to pt@cs.uu.nl or join #stratego at irc.freenode.com.