Saturday, September 17, 2011

AST Transformations: Prerequisites and Annotations

Before we are starting with the transformations themselves, we need to be able to execute them on the source code. Two ways exist to do this: global or local AST Transformations are possible. Since local transformations are much easier to test we will focus on these first.

The usual way to execute a transformation on the source code locally is using an annotation that marks the part of the abstract syntax tree to be transformed. So the first step is to create an annotation class for our use. If you have never heard of annotations before, now would be a good time to take a short break and read up on them.

Annotations allow us to annotate (nomen est omen) a part of the source code, providing additional information or instructions to either compiler or runtime system. An annotation is defined using the keyword @interface (the normal Java keyword interface prefixed with an @-sign). You can add elements that can contain additional information. If you use only one element it should be named value, which allows to leave out the element name when using the annotation, thus providing an elegant shortcut for providing the information. Additionally you can provide a default value for every element in case it is not defined by the user.

The parts of the source code that can be annotated are themselves defined using an annotation @TARGET that can take as different values TYPE, FIELD, METHOD, PARAMETER, CONSTRUCTOR, LOCAL_VARIABLE, ANNOTATION TYPE and PACKAGE or combinations of them. The names speak for themselves.

You can decide how long the annotation is kept using another annotation @RETENTION that takes three values. If SOURCE is used, then the annotation is discarded after the compiler run, CLASS is kept until the class is loaded and only RUNTIME is kept until the program is actually executed. So if you start experimenting and try to read an annotation using reflection be sure to use RUNTIME as the retention type.

Now let us use this information to create a first simple annotation that takes a value, annotates methods and is only used during compile-time (after all this is where the AST will be changed).

@Retention (RetentionPolicy.SOURCE)
@Target ([ElementType.METHOD])
public @interface FirstAnnotation {
    String value() default "this is the default value";

Seems simple? It actually is.

So far this is simple Java. Now if we want to use this annotation to signal an AST transformation we have to somehow wire the annotation to that transformation. This is done using another, groovy-specific annotation named @GroovyASTTransformationClass. This annotation takes as a value the fully qualified class name of the class implementing the AST transformation as a String. Now, if we put this together we get something like the following:

@Retention (RetentionPolicy.SOURCE)
@Target ([ElementType.METHOD])
@GroovyASTTransformationClass ("RequiresTransformation")
public @interface Requires {
String value() default "true";

If you get the distinct feeling that this might be part of the actual later example, you might not be wrong. Let me add, though, that for the sake of simplicity the whole example is put into the default package, which you probably shouldn't do at home.

Short Interlude - AST Structure
The structure of the AST can be arbitrarily complex (which is quite natural if you remember that it is a representation of the source code you just fed the compiler). I could now start to discuss all the gory details and walk you through the grammar and everything tied to it. But that is tedious. Instead, first of all, look at a few Groovy packages using your favorite IDE.

The first package is org.codehaus.groovy.ast, in which you find the structural elements that reflect the class level structure of your source code. FieldNode, MethodNode, Parameter, ConstructorNode ... You can compare these names to the possible @TARGET values above. The different values explicitly target these nodes, allowing you to focus on substructures instead of the AST as a whole.

Additionally to the structural elements we need the actual expressions and statements, which are built from the node type found in the packages org.codehaus.groovy.ast.expr and org.codehaus.groovy.ast.stmt (e.g. BooleanExpression in the first or IfStatement in the second package).

Please note that the screenshots of the different packages do not show the whole package, only a few entries are shown.

This all seems a bit theoretical, but now fire up your GroovyConsole. Enter the following short program:

def val = 1

and execute it (this is a workaround for a bug in Groovyconsole that otherwise renders the AST browser nonfunctional). As the next step choose the menu "Script  -> Inspect AST" and voilá, you can examine the live AST of the source code you entered. In fact you get two ASTs, the first being only the source code you entered, the second being the full Script class that is automatically generated from groovy scripts. Addtionally you can examine the AST in different phases (choose from the Dropdown menu). By default the compiler phase is "Instruction Selection".

For our purposes "Semantic Analysis" is the more interesting one.

If you compare the ASTs of the two phases shown above, you can see that, as described in the previous blog entry, the ReturnAdder inserts the needed return statements in the "Instruction Selection" phase. Now try an if-statement, throw an exception and define a method in the Groovy Console and view the respective ASTs to get a first understanding of how the AST is structured.

The AST Browser built into the Groovy Console is an indispensable tool if you want to understand how the AST is built, and I quite often use it when experimenting with AST transformations.

Transformation - The Example 
A nice example for a little AST transformation is an annotation that ensures that some preconditions are met when calling a method. We use the above defined annotation "Requires" and provide a boolean expression as a String. This expression is evaluated as the first statement in the method and if the condition is not met then an exception is thrown (making an assertion would be an alternative). So using this annotation would look like the following:

@Requires("divisor != 0")
public int divide10By(divisor) {

And the AST transformation should then create the following code:

public int divide10By(divisor) {
    if( ! (divisor != 0) )
        throw new Exception('Precondition violated: {divisor != 0}')

The idea is pretty simple, and even the implementation will not be complicated. First we have to create an AST for a static code into which we inject the boolean expression and part of the string. This AST has then to be added to the beginning of the method AST.

Nonetheless I find the functionality quite interesting and the implementation can be used as a basis to generate very interesting AST transformations. So stay tuned for the next blog entry where I will describe how to create the AST transformation itself.

Interesting Classes
java.lang.annotation.ElementType contains definitions for allowed target types
java.lang.annotation.RetentionPolicy contains definitions for the existing retention types.
package org.codehaus.groovy.ast contains the structural elements of the AST
package org.codehaus.groovy.ast.expr   contains every node type having to do with expressions
package org.codehaus.groovy.ast.stmt contains the node types creating statements


Mike Finney said...

Good stuff! Thanks!

Dmitry Semenov said...

if( ! (divisor != 0) ) = WTF?

stoney said...

Nice article. Btw there is a project that extends Groovy with Design by Contract annotations, like the @Requires you did in your example: GContracts.

Adam Boczek said...

Hi Joachim, great post, thanks.

The topic is quite interesting but first of all we should ask ourselves what are the usage scenarios of this functionality? Should we use an AST transformation for the enrichment of the existing classes like proposed here ( or maybe we should use it as a way for the introduction of aspect orientation or maybe as a “rule injector” (your example)… I look forward to reading your next posts.

CU, Adam

Joachim Baumann said...

@Mike: Thank you :-)

@Dmitry: The idea is that the code is automatically created using a static part "if( ! ( PLACEHOLDER ) )" and the part taken from the annotation "divisor != 0" placed in there instead of the "PLACEHOLDER" resulting in this not quite perfect negation. But nobody ever sees this code and the compiler will most probably optimize it.

@stoney: Ok. Didn't know that. That looks like a fully fledged package. But at least my example illustrates the possible implementation :-)

@Adam: AST transformations, in the first step, are only a tool to inject arbitrary functionality at compile-time. Injecting at compile-time has the advantage that the modification is seen by Java code as well as by Groovy code.

But underlying is the question of whether such language constructs provide needed functionality or are simply some means to play around (foolishly at times). The same question has to be asked e.g., with regard to aspect orientation. Which means, we are back at philosophical questions ...