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.

...

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

JTLJTL

•  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.

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

Jquery

SOUL

• 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 predicatesunmigrated-wiki-markup
• support 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.

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

.QL

• 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)

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

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

...

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

PMD

• http://www.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

• Model: Relational vs Tree
• control flow statements 
• variable binding & cross reference
• types 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)
• universal quantifiers (forall, exists, no)
• querying style

Conclusion/Ideas

Relational based query languages not low level enough. 

Tree based query languages not expressive enough.

Idea: mix both

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

• .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
• quantifiers (forall, exists, no)
• predicates
• set operators
• aggregate operators
• behavioural template matching
• list pattern matching (parameters, generics)
• 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. 

Tree based query languages not expressive enough.

Idea: mix both

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

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/]