Transcript slides - CS Technion

OOPSLA’06: Cohen, Gil, Maman
JTL – The Java Tools Language
Intuitively querying Java programs
Itay Maman
The Technion – Israel Institute of Technology
Joint work with Tal Cohen and Yossi Gil
October 24, 2006
OOPSLA’06, Portland
OOPSLA’06: Cohen, Gil, Maman
Wanted:
A class with a static method returning float
• The regular expression approach:
static float
static.*float.*\(.*\)
– (Inaccurate)
• The XQuery approach:
/class/method[
./return/@type="float"
and @modifiers="static"]
– (Too complicated to be used interactively)
• There’s also a JTL way…
2/16
OOPSLA’06: Cohen, Gil, Maman
In this Talk
• Motivation, Design considerations
• JTL 101
• Evaluation algorithm
3/16
OOPSLA’06: Cohen, Gil, Maman
Usage scenarios
• Existing solutions: CodeQuest, BDDBDDB, XIRC, JQuery,
ALPHA, …
• Software engineering tools
– Code lookup, (anti) pattern detection, …
• Programming languages
–
–
–
–
Static pointcuts in aspect-oriented programming
Mixins (Jam)
Concepts (ConceptC++)
Pluggable type systems (JavaCOP)
4/16
OOPSLA’06: Cohen, Gil, Maman
Queries embedded in the Program
• Java 5 already provides code queries
public<T extends Cloneable & Serializeable>
void f(T ts) { ... }
– Syntax close to Java
– Limited expressive power
• A hypothetical alternative (SQL)
public<SELECT * FROM extends WHERE (super = 'Cloneable' or
super = 'Serializeable') and subclass='T' ...>
void f(T ts) { … }
– Syntax significantly diverts from Java
– Difficult to write/read
5/16
OOPSLA’06: Cohen, Gil, Maman
Mission Statement
Define a logic language (over Java programs) which:
A. Is as powerful as Datalog
B. Has an intuitive, readable syntax
C. Has a simple data model
 Other solutions fall short
6/16
OOPSLA’06: Cohen, Gil, Maman
JTL: Unary Predicates
• A simple predicate:
const := static final field;
– Three sub-queries
– Space (and comma) denotes conjunction
• The subject variable
const := #static #final #field;
– The hash symbol, #, denotes the subject variable
– A variable in a prefix position => becomes the subject of the callee
• If not specified, defaults to # (the subject)
static,
final, etc. are library predicates, not keywords.
7/16
OOPSLA’06: Cohen, Gil, Maman
JTL: Binary Predicates
• Binary predicates
has_static_member X := class declares X, X static;
extends+ Y := extends Y | extends Y', Y' extends+ Y;
– Accept a subject + an additional parameter (in a postfix position)
– (Names of Variables/Parameters must begin with a capital letter)
• Subject chaining: Repeatedly using a variable as a subject
my_generic_method T :=
method, T extends Serializeable,
T extends Cloneable;
– Can be rewritten using the ampersand operator:
my_generic_method T := method,
T extends Serializeable & Cloneable;
8/16
OOPSLA’06: Cohen, Gil, Maman
JTL: Quantification { }
• Quantifying the members of a class
some_class := class {
static int field;
field => private;
many method;
}
– Subject variable iterates over a set
– Each condition must hold
– Quantifiers:
• Unary: exists, all, no, one, many
• Binary: => (implies)
Generator
• Quantifying with a generator
no_abstract_super := class extends+: {
no abstract;
}
• Default generator for classes: members:
• Default quantifier: exists
9/16
OOPSLA’06: Cohen, Gil, Maman
Other Features
Type literal
sortable_list := class extends /java.util.ArrayList {
static final long field 'SerialVersionUID;
public void sort();
}
Method signature
pattern
Name matching
(Regular expression)
• Type system
– MEMBER: constructors, methods, fields
– TYPE: interfaces, classes, primitive types, enum types, annotation
types
10/16
OOPSLA’06: Cohen, Gil, Maman
Delving into methods
• The idea: Symbolically name intermediate results
• The SCRATCH type
– Constants
– Values passed to parameters
– Values pushed onto the stack by JVM instructions
• Represent code sites
• Library predicates for checking whether a scratch is:
–
–
–
–
–
Copied
Used in a calculation
Written/Read from a field
Stored/loaded from the local variable array
...
11/16
OOPSLA’06: Cohen, Gil, Maman
Scratches in Action
copy* S := is S | copy S | copy S', S' copy* S;
chain_method := !void method {
returned => copy* S, S this;
};
getter_method := !void method declared_by C,
C declares F {
returned => copy* V, V getfield [I,F], I copy* S,
S this;
};
 Default generator expression for a method is: scratches:
– Generates all scratches of the method
12/16
OOPSLA’06: Cohen, Gil, Maman
Evaluation scheme
• JTL is translated into Datalog
• The Datalog program is evaluated top-down
• “need to know basis”
– The JTL evaluation algorithm does not see more information than it
needs
– Only necessary facts are extracted from the native predicates
=> No database setup is needed
- Which is a bottleneck in similar applications
13/16
OOPSLA’06: Cohen, Gil, Maman
Q: What’s special about p2?
p1 := # extends A, A abstract;
p2 := A extends #, A abstract;
p3 := A extends #, A abstract, # p4 A;
p4 := ...
(Suppose we invoke p1, p2, p3 with some type passed in as a subject)
• A: Result of p2 is infinite
– Result of p3 may be infinite (depending on the definition of p4)
• Consequences
1. Use exhaustive iteration
– Assume a closed world, usually: the classpath
– Performance penalty
2. Beware: Fragile results!!
14/16
OOPSLA’06: Cohen, Gil, Maman
Fragility
• Can we determine whether a query is fragile?
– In the general case: No
– In JTL’s case: Yes
• Requires the native predicates to maintain a simple property
• Recently proven by Gil and Zarivach
• JTL’s current implementation is more conservative
– Subject is not known => a runtime error
– Works well in most practical situations
15/16
OOPSLA’06: Cohen, Gil, Maman
Contributions
JTL: A powerful language, intuitive notation,
simple data model
– Java-like clauses become Datalog queries
– Queries on behavior
– Efficient implementation
16/16
OOPSLA’06: Cohen, Gil, Maman
http://www.cs.technion.ac.il/jtl
17/16