Page History

...

Use Case 4: Find overloaded methods with multiple parameters that share a single type.

Covariant Arrays

Wiki MarkupIn Java and C#, array subtyping is covariant, meaning that type B\[\] is considered a subtype of A\[\] whenever B is a subtype of A. However, this relation can cause runtime exceptions. Consider the following Java code where Banana and Apple are subtypes of Fruit:

Banana[] bananas = new Banana[5];
Fruit[] fruit = bananas;
fruits[0] = new Apple(); // ArrayStore Exception
peelBanana(bananas[0]); // Apple???

Wiki MarkupThe assignment to the first element of the variable fruit on line 3 will cause an ArrayStore exception. Although statically, the variable fruit has type Fruit\[\], its runtime type is Banana\[\] and thus we cannot use it to store an Apple.

Use Case 5: Find occurences of covariant array uses in assignment, method calls, constructor instantiations and return statements.

...

This new feature introduced two source incompatibility incompatibilities with respect to Java 6. The code below illustrates the changes. Previously, the statement throw exception would throw a Foo exception. Now, it throws a DaughterOfFoo exception. As a consequence, the catch block catch(SonOfFoo anotherException) is not reachable anymore as the try only throws a DaughterOfFoo exception.

...

Use Case 6: Find occurences of nested try/catch blocks that rethrow an exception.

Evaluation

[This section is work in progress]

X = can't be supportednot supported

✓ = can be supported

? = not sure

*1: can find overloaded methods but not sharing single type: method(?C, ?M1), method(?C, ?M2), likeThis(?M1, ?M2). Tested with operations available in eclipse plugin. Paper describe different operations that don't seem to be supported.

*2: .QL documentation & tool is kept secretive for competitive advantage protection 

Covariant Arrays

- no support for statement level information

JTL

•  no working Eclipse plugin found. (authors emailed)
• argument list pattern (sec 2.2) public _ (_, String, *) : any public method that accept a String as its second argument and returns any type
• quantifiers: no, all, exists...
• anonymous class
• pattern naming (integral := byte | short | int | long)
• variable binding
• no structural matching of AST (deemed difficult because uses class files) (so can't look match on a loop for example or find all local variables in method)
• unmigrated-wiki-markupno submethod information (local vars etc)
• read\[F\]/write\[F\] predicates to indicate whether a method reads/write to a field. Nice feature: write\[_\] tells whether method writes to a field at all. Q: How do we do this recursively? All methods within the method are not writing to fields...
• no support for generics (according to documentation)

Use case 1 not possible because no support for local variable decl. Use case 2 & 3 not possible because no support for generics/wildcards (due to bytecode source). Use 4 not possible because no support for statements & types of expressions. Use case 6 not possible because no control flow support.

BBQ

• doesn't detect local inner classes (local & anonymous). Only inner classes (doesn't differentiate): class in all classes
• no access to local variable declared in methods
• no support for generics.
• no support for constructors (considered as method init) 
• no AST structural matching. (e.g loops ...)
• no variable binding/unification
• set operators (union, intersection)
• support for read/write of fields references

Similar reasons to JTL.

Wiki Markup*{+}SOUL \[authors replying on Tuesday\]+*

Jquery

• All Java AST supported by logic queries. (tight symbiosis with Eclipse JDT) 
• When there isn't a dedicated predicate, the language allows to query the Eclipse semantic analyzer directly. (this solves the covariant arrays use case)
• template matching doesn't support all features. (for example generics, wildcards, try/catch blocks)

Jquery

• http://jquery.cs.http://jquery.cs.ubc.ca/documentation/toc.html
• http://jquery.cs.ubc.ca/documentation/appendix2.html
• variable binding through predicates
• Wiki Markupsupport for read & efftects of fields (write) \ [writes(?B,?F,?L) means: "Block ?B writes to field ?F at location ?L"\]
• no structural (statement) matching (e.g pattern match on a loop or body of a method)
• no generics support
• no quantifiers

Similar reasons to JTL.

Wiki Markup*+.QL \[authors emailed\]+*

• New version stores every AST node unit in DB
• has notion of aggregates (count, sum, max, min, avg)
• ".QL: Object-Oriented Queries made Easy"

Very expressive. Though sql statements may not scale for control flow matching. (direct ast pattern matching is clearer for some use cases)unmigrated-wiki-markup

*{+}Jackpot \[emailed Jan from Netbeans\]+*

• https://bitbucket.org/jlahoda/jackpot30/wiki/RulesLanguageAdditionalDocs

PMD

• no support for types of expr
• no support for grouping elements by a characteristic (eg overloaded methods)
• http://wiki.netbeans.org/JavaDeclarativeHintsFormat
•  

PMD

• http://http://www.ing.iac.es/~docs/external/java/pmd/rules/design.html
• http://code.google.com/p/code-cop-code/wiki/PmdRulesCodecop
• structural matching: all AST hiearchy can be queried through Xpath expression
• can't express subtype relations. E.g. assignments where RHS is supertype of left handside and different
• no variable binding
• support generic constructors but not bind it to enclosing class: //ConstructorDeclaration//TypeParameters
• no support for read/write effects

No variable binding support which restricts a lot of the analysis. 

Taxonomy

...

[This section is work in progress]

Query Language Features

...

• variable binding & cross reference
• quantifiers (forall, exists, no)
• predicatestypes information of AST nodes + type constraints (subtype relations)
• set operators
• generics / wildcards
• read/write references
• anonymous class
• aggregates (grouping results)
• pattern matching? (i.e JTL style for argument list, SOUL like for AST matching)
• aggregate operators
• behavioural template matching
• list pattern matching (parameters, genericsuniversal quantifiers (forall, exists, no)
• querying style

Java Language Features supported

• Attributed AST Nodes
• control flow statements
• local variables
• generics / wildcards
• anonymous class

Conclusion/Ideas

[This section is work in progress]

Relational based query languages not low level enough. 

...

Idea: decouple query-by-example from constraints on variables. - two different views-

Time Plan

...

...

Week 1

...

Week 2

...

Week 3

...

Week 4

...

Week 5

...

July

...

Raoul in Cambridge

...

• Source Code Query Languages Literature Review

...

• Source Code Query Languages Taxonomy

...

• Joel: away Stockholm
• Come up with syntax examples to express use cases
• Design

...

• Joel: away Stockholm
• Design
• Tools Research
• Write grammar

...

August

...

•  
• Parser

...

September

...

...

...

...

...

...

October

...

Joel JavaOne

...

...

Raoul in Cambridge

...

Raoul in Cambridge

...

Raoul in Cambridge

It seems pure template based languages are not expressive enough and so are pure logic-based queries. 

Sweet spot a combination of both mechanisms (which SOUL provides).

Implementation

Tools available

• Parser generator
  • antlr (http://www.antlr.org/)
• Language Development Toolkit
  • Xtext (http://www.eclipse.org/Xtext/) IDE support out of the box
• Database/Indexing
  • Lucene (jackpot is based on it)
  • Relational databases (Oracle, MySQL, PostgreSQL...)
• Static Analysis
  • PMD api
  • Eclipse AST
  • Tree API (annotation processing framework)

Time Plan

Demo Plan

Aim

Give a live demonstration of the query language for two use cases: Covariant Arrays assignments & Overloaded Methods sharing single type

Deadline

7th September

Plan

Build the minimum vertical implementation to make this possible. This consists of the following milestones:

1) Create a database representation of a Java program, which stores information attributed AST nodes of assignments and method declarations. (deadline: 17/8)

2) Develop backend API that will query the database. (deadline: 23/8)

3) Design query language, different types of queries it will support (deadline: 29/8)

4) Build minimum grammar & parser & compiler to query the two use cases (deadline: 6/9)

5) Output results frontend (deadline: 7/9)

Extra Time

Extra time will be used to expand the infrastructure horizontally: 

- Support more AST nodes and relations

- Support more types of queries

- Extend backend

- Test coverage

- Web interface for Demo

Relevant Literature

[1] Brian Goetz. Language designer's notebook: Quantitative language design. 

Color scheme:

• Alex
• Joel
• Raoul

Relevant Literature

Wiki Markup\[1\] Brian Goetz. Language designer's notebook: Quantitative language design. [http://www.ibm.com/developerworks/java/library/j-ldn1/|http://www.ibm.com/developerworks/java/library/j-ldn1/].

Wiki Markup\[2\] Chris Parnin, Christian Bird, and Emerson Murphy-Hill. 2011. Java generics adoption: how new features are introduced, championed, or ignored. In Proceedings of the 8th Working Conference on Mining Software Repositories (MSR '11)'11)

Wiki Markup\[3\] Ewan Tempero, Craig Anslow, Jens Dietrich, Ted Han, Jing Li, Markus Lumpe, Hayden Melton, and James Noble. 2010. The Qualitas Corpus: A Curated Collection of Java Code for Empirical Studies. In Proceedings of the 2010 Asia Pacific Software Engineering Conference (APSEC '10)

Wiki Markup\[4\] Joseph Gil and Keren Lenz. 2010. The use of overloading in JAVA programs. In Proceedings of the 24th European conference on Object-oriented programming (ECOOP '10)

Wiki Markup\[5\] Raoul-Gabriel Urma and Janina Voigt. Using the OpenJDK to Investigate Covariance in Java. Java Magazine May/June 2012.

Related Projects

Wiki Markup\[a\] Refactoring NG. [ http://kenai.com/projects/refactoringng|http://kenai.com/projects/refactoringng]

\[b\] Tal Cohen, Joseph (Yossi) Gil, and Itay Maman. 2006. JTL: the Java tools language. In Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications (OOPSLA '06)

/refactoringng

[b] Tal Cohen, Joseph (Yossi) Gil, and Itay Maman. 2006. JTL: the Java tools language. In Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications (OOPSLA '06)

[c] Browse By Query.  Wiki Markup\[c\] Browse By Query. [http://browsebyquery.sourceforge.net/|http://browsebyquery.sourceforge.net/]