Language Tour: JTL by Example

Welcome to JTL

If you want to learn to write JTL queries, you came to the right place. This five-minutes tutorial will get you started.

Luckily JTL is a very simple language. It has an intuitive query-by-example syntax which makes it really easy to write JTL queries. In fact, JTL is simple enough that we can cover both simple issues (such as: finding a class with a public field) as well as sophisticated issues (such as: finding all setter methods of a class) in these five minutes.

OK. Let's get started...

Here is our first JTL query: public static double method(int, int); This will match static methods that take two int parameters and return a double value. Easy, right?

Specifically, this query is composed of a series of conjugated terms, such as "public" or "static". Conjunction can be marked by a comma, or by a space; in special cases, such as before an argument list pattern, no separation is needed.

Of course, JTL also supports disjunction and negation, as in "public|protected" or "!static". Square brackets can be used to override operator precedence.

Let us now write a query detect methods taking three int parameters and returning a subclass of Java's Date class: public static D method(int, int, int), D extends* /java.util.Date;

In this example we use the variable D to capture the return type of the method. We then pass this variable to another query, extends* to assert that D is indeed a subclass of java.util.Date. Simply put, extends* is a query which finds the chain of superclasses of the inspected class. This always at the inspected class itself and goes all the way up to java.lang.Object.

As its name suggest, extends* is a natural extension of the extends query which finds the immediate super-class of its input. Although it a standard query in JTL's library, we could, if we wanted to, to define it ourselves, in two simple steps: extends+ C := extends C | extends C', C' extends+ C; extends* C := is C | extends+ C; Note the recursive definition of extends+, a useful predicate in its own right.

Let us take a quick break and summarize the syntactic rules that were illustrated by the examples that we saw:

  • We can define our own queries using the ":=" operator.
  • Query name must begin with a lower case letter, as in: "extends" or "public".
  • Variables and parameters must begin with a capital letter.
  • Both queries and variables can end with special characters like "*", "+" or "'".
  • Every query has one special parameter which is considered to be the element being inspected. There's no need to define this parameter - it is always defined for every query. When an expression calls a query, the expression's inspected element is passed, by default, to the called query: in the expression static public the two queries static and public will inspect the same element, which is the element that the whole expression inspects.
  • We can overrule the default by explicitly specifying an element to be inspected by the called query. To do this we need to place the variable holding our element before the called query. In extends C', C' extends+ C, we have the variable C' which is placed before the call to extends+, thereby forcing extends+ to take this variable as its inspected element.

Searching for Classes

So, finding methods is easy; but JTL would have been of limited usability without its support for complex class patterns. For example, the following will find any class that contains a factory method but no public constructor: classWithFactory := is T, class { no public constructor; public static T method; }

While the example is highly readable, let us analyze its semantics in detail. The first term, is T, captures the element being inspected (necessarily a class, since it will be matched by the following class predicate) into the variable T, for use inside the inner scope. Next, the { ... } block is a set query that builds a set of matching elements and then applies the enclosed list of predicate to this set.

By default, the set generator is the binary predicate members, meaning that the set comprises all class members of the inspected class. To this set of members we now apply two requirements: first, that it contains no item that matches public constructor, and second, that it contains at least one public static method that returns the enclosing type.

JTL supports other quantifiers in addition to negation and the existential quantifier; for example, using the universal quantifier all, we can detect "structs" -- classes that contain nothing but public fields: struct := class { all public field; }

As a final example on this subject, let's see how generators other than members can be put to use. The following predicate: multipleAbstractParents := class extends+: { many abstract; } will match any class that has multiple abstract classes in its transitive list of superclasses. The generator used, denoted by ":", is extends+; this generates a set of classes. Then, the quantifier many requires that more than one member of this set be (in this case) abstract.

Peeking Inside Methods

Going beyond queries on the structure of types and the declarations of members, JTL also exposes the data-flow graph of methods, thereby allowing users to query the behavior of methods.

This mechanism is based on the realization that, using static analysis, one can identify all locations inside the method's body where a new value is computed. It is also possible to analyze where (and how) each such value, called a scratch, is used throughout the method.

When evaluating a method, the JTL engine will first generate a scratch value for each location in a method where a new value is computed; input values (i.e., parameters) are also considered scratches. It then tracks down how these scratches are put to use. Intuitively, this analysis discovers facts like: "this scratch is passed as a parameter in a method call, "that scratch is used as an operand in a computation that yields another scratch," and so on.

The facts associated with each scratch are exposed by a set of standard library predicates. For example, the unary predicate parameter holds for a scratch produced by an assignment from a parameter of the method. The binary predicate from X holds if the scratch being inspected is produced by an assignment from X. We can therefore detect all scratches that are parameters, or else originate from parameters (aliasing), using this recursive query: fromParam := parameter | from S, S fromParam;

Of course, queries that match scratch values are rarely useful by themselves; programmers are searching for methods or classes, not for interim calculation steps. So let us put fromParam to good use, building on it to search for setter methods: fromParam := parameter | from S, S fromParam; setterMethod := void (_) { fromParam put_field[F,_]; } declared_by C, F declared_by C;

A setter method, as matched by this query, is a void method that takes a single parameter. It has a scratch value originating from that parameter (that would normally be the parameter itself), and that value is used in an assignment (a JVM put_field instruction) to some field F. That field has to be defined in the same class C, that declares the setter method itself.

This simple example is surprisingly powerful. Unlike many other tools for detecting setter methods, it does not rely on naming conventions (the method doesn't have to be called "set...") or other informal practices. What we have is a mathematically sound query with well-defined semantics.

Using JTL Programmatically

JTL is distributed as a JAR file (3MB in size, including all dependencies). The standard library uses bytecode inspection techniques for extracting facts from the program at hand; the source code of a program is not required, making binary libraries fully searchable. Fact extraction is performed on demand: only the facts required by the currently executing JTL query are indeed extracted from the program. This approach proved to be much more efficient than eagerly populating a fact database.

The top-level gate into the JTL world is class jtl.system.api.JTL. We can create various instances of this class, but we will usually use the pre-made default object, JTL.INSTANCE. The simplest way to evaluate a query is to invoke one of the overloaded versions of run(). In these versions, the first parameter is always a string specifying a JTL program, while additional parameters are input values, in various formats (fully-qualified names, java.lang.Class objects, etc.).

Here is a small Java program that uses the setterMethod query for finding all setter methods in class DatagramPacket import jtl.system.api.JTL; import java.net.DatagramPacket; public class Example { public static void main(String[] args) throws Exception { System.out.println(JTL.INSTANCE.run( "fromParam := parameter | from S, S fromParam;" + "setterMethod := void (_) { fromParam put_field[F,_]; } " + " declared_by C, F declared_by C;" + "main M := class { setterMethod is M; };", DatagramPacket.class)); } }

The run() method takes care of compiling and running the JTL program. It expects the JTL code to contain a predicate called main.

After compilation (which includes type-checking), the running phase begins: run() will evaluate the main predicate while using the given input (namely, class DatagramPacket) as the element that main inspects (aka: the subject). Note that main can compute its M parameter from its subject so the only input we need is the class to test.

The relation calculated by the predicate is returned to the caller. Here, we simply print it to standard output.

Of course, the library also support ahead-of-time compilation of JTL queries: The JTL.compile() method returns an Executable object, which has its own set of run() methods. This approach is more efficient when the same query, or a set of queries, is executed repeatedly, each time with different input values.