Explanation

For the design of the CQL module as a whole, see Design of the CQL module.

Since AQL is a basis for both JQL and CQL as well as other flavors found in other Atlassian products, we figured we would make an independent AQL parser that can then be used to parse CQL queries, and other flavors in the future if needs be. In any case, it's pretty cool to have a parser that's independent from the vocabulary when it's possible, so this is a decision we could have taken anyway.

The Confluence Query Language (CQL) and Jira Query Language (JQL) are both variants of the Atlassian Query Language (AQL), with the same grammar.

We discuss the design of our hand-crafted AQL parser, which we use to convert Confluence Query Language (CQL) queries to Solr.

An attempt to use a parser generator (SableCC)

Atlassian uses ANTLR4 to parse AQL queries, as evidenced by the dependencies of their atlassian-query-lang  maven package, on which their Confluence CQL Plugin package depends.

We could have taken obvious decision  to use a parser generator as well. Nobody was ever fired for basing their parser on ANTLR.

It so happens that we have a custom query language in XWiki, XWQL, based on JPQL and SableCC a parser generator which looks elegant and has the compeling property of completely separating the grammar definition from the Java code that supports the parser. Notably there's no block of Java code initializing the Abstract Syntax Tree (AST) nodes. Which makes the SableCC grammar of XWQL quite readable and close to what one would have written on paper to formally describe its grammar.

These compeling aspects of SableCC, the chances that our work would have less chance to look like Atlassian's than if we chose ANTLR4 as well and the fact that it's already used in XWiki made us pick SableCC to write the AQL grammar.

However, most of the time was spent fighting the parser generator instead of doing meaningful progress, so we switched to an hand-crafted parser.

Advantages of hand-crafted parsers

Many widespread parsers are actually hand-crafted. They has several advantages:

• Maintenance
  • Easier debugging. Errors in a generated parser can be arcane and difficult to trace.
  • Easier testing. Ensuring coverage is straightforward. When developping for XWiki, we have readily available tools to ensure the code is covered. Noticing what features of the parser are covered and which ones are not is trivial and this helps build a comprehensive test suite.
  • Less complexity in the build step. Usually, parser generator generate code that can then be used. As long as the parser itself is not compiled, calls to the parser will look like they are wrong in IDEs. This generated code is also potentially difficult to read and understand.
  • No hidden assumptions in the parser generator (what counts as white space, what encoding works, etc)
• Better error messages. With generated parsers, it is more difficult to provide user-friendly error messages. End users will be usually shown raw errors exposing technicalities like token names or grammar rules. In works cases, the parser will say something like "Unexpected token '='", without explaining why. We took great care issuing error messages that are as comprehensible as possible. Worst case, we know exactly what the parser was trying to do at which line, which column and witch kind of expression it was trying to parse when encountering a syntax error. Error messages can be easily customised for the common syntax errors (although for CQL, there are usually no errors because expressions come from migrated content, the CQL queries have already run in Confluence and should be syntactically valid - errors will be more likely due to unsupported features which, again, can be clearly pointed out as such by the parser)
• Ease of use. With a hand-crafted parser, it is easy to expose exactly the right APIs with the right level of abstraction (without irrelevant details, but with the relevant ones).

Hand-crafted parsers, on the other hand, can be very messy and difficult to understand. This can be mitigated by following some rules. We present this in the next section.

How the AQL parser is written

One class per AST node, with the parser state included

This is nothing fancy, and parser generators also tend to do this. There's one class per AST node type. These classes are very simple and would be records if have had access to the right version of Java at the time of writing it. They have members that represent what they mean.

Additionally,

• Some of the nodes are subclasses of other (possibly abstract) nodes, which helps making the relation between the node types obvious. For instance,
  • AQLStringLiteral and AQLNumberLiteral both extend AbstractAQLAtomicValue, which extends AbstractAQLRightHandValue.
  • AQLAtomicClause is an AbstractAQLClause which has three children: a field name, an operator (of type AQLAtomicClauseOperator), and a right hand value of type  AbstractAQLRightHandValue, which can be a AQLStringLiteral or a AQLNumberLiteral among other things
• Each AST node has a copy of the parser state (of type AQLParserState) which holds the current position, the current line and the current column in the AQL query string. This makes it easy for the next pass to point out where an error is exactly located.

Utility methods for advancing and backtracking

This parser doesn't use a lexer at all: the AQL query isn't tokenized. Rather, each node is recursively parsed by following the AQL grammar rules. Terminal symbols are manually parsed as they are encountered.

To help with actually reading the AQL string, we use a reader class that defines methods to read the next or peek at the next character, to read the next word by specifying the characters that end the word, to skip whitespace characters and to "unread" (backtrack) one or more characters. This reader has the entire string to parse in memory.

This design has two big implications:

• the parsing is not streamed (it's not SAX-like)
• the parser cannot handle huge strings

which is fine for AQL. Queries are supposedly quite small in terms of string size.

One method per grammar rule or per terminal expression

While having a grammar file that doesn't contain any "ugly implementation details" Java code was a compelling aspect of SableCC, with this hand-crafted parser, we are at the opposite extreme in terms of purity. The grammar rules are purely encoded in Java code. We cannot really pretend that we are following a nice academic grammar. As such, the code can get really messy, where (un)reading caracters is all mixed with advancing in the grammar rule, and where it's not even that clear which grammar rule is being applied.

Ultimately, with hand-crafted parsers, all the academic theory behind formal languages and grammars which is the common language that can help one understand what is going on in a parser is at risk of being thrown out of the window, leaving one alone with the dragons left by the parser's author.

To limit this catastrophy, we follow the following three strategies, losely but as much as possible:

• We emit strongly typed ast nodes, with inheritance representing the super types of a node.
• Each grammar rule is written in its own method, which itself calls a method for each (terminal or non-terminal) term of the rule.
• We (losely) follow this naming convention:
  • method parseNodeType parses a node of type my node type. A failure to parse the term is a syntax error and must cause the whole parsing to fail
  • method maybeParseNodeType tries to parse a node of type my node type, but it is allowed to fail. When this happens, it silently returns null.
  • method parseRemainingNodeType parses a node of type my node type, but the caller has already started to parse it, usually to decide which node to parse. For instance, when parsing an atomic value, which can be a numeral, a string, or something else, parseAtomicValue reads the first character, and determines whether it is a figure, or a quote, or something else, and calls the corresponding #parseRemaining*# method. This clearly breaks purity: suddenly, a grammar rule messes with parsing its children. This is a tradeoff that, in practice, can simplify the code or bring some small performance improvement by removing some backtracking, hopefully without making the code too messy.