src/main/java/org/z3950/zing/cql/CQLParser.java

   1
   2 package org.z3950.zing.cql;
   3 import java.io.IOException;
   4 import java.util.Properties;
   5 import java.io.InputStream;
   6 import java.io.FileInputStream;
   7 import java.io.FileNotFoundException;
   8 import java.io.Reader;
   9 import java.io.StringReader;
  10 import java.util.ArrayList;
  11 import java.util.HashSet;
  12 import java.util.List;
  13 import java.util.Set;
  14
  15
  16 /**
  17  * Compiles CQL strings into parse trees of CQLNode subtypes.
  18  *
  19  * @see         <A href="http://zing.z3950.org/cql/index.html"
  20  *                      >http://zing.z3950.org/cql/index.html</A>
  21  */
  22 public class CQLParser {
  23     private CQLLexer lexer;
  24     private PositionAwareReader par; //active reader with position
  25     private final int compat;   // When false, implement CQL 1.2
  26     private final Set<String> customRelations = new HashSet<String>();
  27
  28     public static final int V1POINT1 = 12368;
  29     public static final int V1POINT2 = 12369;
  30     public static final int V1POINT1SORT = 12370;
  31     public final boolean allowKeywordTerms;
  32
  33     static private boolean DEBUG = false;
  34     static private boolean LEXDEBUG = false;
  35
  36     /**
  37      * The new parser implements a dialect of CQL specified by the
  38      * <tt>compat</tt> argument:
  39      * <ul>
  40      *  <li>V1POINT1 - CQL version 1.1
  41      *  </li>
  42      *  <li>V1POINT2 - CQL version 1.2
  43      *  </li>
  44      *  <li>V1POINT1SORT - CQL version 1.1 but including
  45      *          <tt>sortby</tt> as specified for CQL 1.2.
  46      *  </li>
  47      * </ul>
  48      */
  49     public CQLParser(int compat) {
  50         this.compat = compat;
  51         this.allowKeywordTerms = true;
  52     }
  53
  54     /**
  55      * Official CQL grammar allows registered keywords like 'and/or/not/sortby/prox'
  56      * to be used unquoted in terms. This constructor allows to create an instance
  57      * of a parser that prohibits this behavior while sacrificing compatibility.
  58      * @param compat CQL version compatibility
  59      * @param allowKeywordTerms when false registered keywords are disallowed in unquoted terms
  60      */
  61     public CQLParser(int compat, boolean allowKeywordTerms) {
  62         this.compat = compat;
  63         this.allowKeywordTerms = allowKeywordTerms;
  64     }
  65
  66     /**
  67      * The new parser implements CQL 1.2
  68      */
  69     public CQLParser() {
  70         this.compat = V1POINT2;
  71         this.allowKeywordTerms = true;
  72     }
  73
  74     private static void debug(String str) {
  75         if (DEBUG)
  76             System.err.println("PARSEDEBUG: " + str);
  77     }
  78
  79     /**
  80      * Registers custom relation in this parser. Note that when a custom relation
  81      * is registered the parser is no longer strictly compliant with the chosen spec.
  82      * @param relation
  83      * @return true if custom relation has not been registered already
  84      */
  85     public boolean registerCustomRelation(String relation) {
  86       return customRelations.add(relation);
  87     }
  88
  89     /**
  90      * Unregisters previously registered custom relation in this instance of the parser.
  91      * @param relation
  92      * @return true is relation has been previously registered
  93      */
  94     public boolean unregisterCustomRelation(String relation) {
  95       return customRelations.remove(relation);
  96     }
  97
  98     /**
  99      * Compiles a CQL query.
 100      * <P>
 101      * The resulting parse tree may be further processed by hand (see
 102      * the individual node-types' documentation for details on the
 103      * data structure) or, more often, simply rendered out in the
 104      * desired form using one of the back-ends.  <TT>toCQL()</TT>
 105      * returns a decompiled CQL query equivalent to the one that was
 106      * compiled in the first place; <TT>toXCQL()</TT> returns an
 107      * XML snippet representing the query; and <TT>toPQF()</TT>
 108      * returns the query rendered in Index Data's Prefix Query
 109      * Format.
 110      *
 111      * @param cql       The query
 112      * @return          A CQLNode object which is the root of a parse
 113      * tree representing the query.  */
 114     public CQLNode parse(String cql) throws CQLParseException, IOException {
 115         return parse(new StringReader(cql));
 116     }
 117
 118     /**
 119      * Compiles a CQL query.
 120      * <P>
 121      * The resulting parse tree may be further processed by hand (see
 122      * the individual node-types' documentation for details on the
 123      * data structure) or, more often, simply rendered out in the
 124      * desired form using one of the back-ends.  <TT>toCQL()</TT>
 125      * returns a decompiled CQL query equivalent to the one that was
 126      * compiled in the first place; <TT>toXCQL()</TT> returns an
 127      * XML snippet representing the query; and <TT>toPQF()</TT>
 128      * returns the query rendered in Index Data's Prefix Query
 129      * Format.
 130      *
 131      * @param cql       The query
 132      * @return          A CQLNode object which is the root of a parse
 133      * tree representing the query.  */
 134     public CQLNode parse(Reader cql)
 135         throws CQLParseException, IOException {
 136         par = new PositionAwareReader(cql);
 137         lexer = new CQLLexer(par, LEXDEBUG);
 138
 139         lexer.nextToken();
 140         debug("about to parseQuery()");
 141         CQLNode root = parseTopLevelPrefixes("cql.serverChoice",
 142                 new CQLRelation(compat == V1POINT2 ? "=" : "scr"));
 143         if (lexer.ttype != CQLLexer.TT_EOF)
 144             throw new CQLParseException("junk after end: " + lexer.render(),
 145               par.getPosition());
 146
 147         return root;
 148     }
 149
 150     private CQLNode parseTopLevelPrefixes(String index, CQLRelation relation)
 151         throws CQLParseException, IOException {
 152         debug("top-level prefix mapping");
 153
 154         if (lexer.ttype == '>') {
 155             return parsePrefix(index, relation, true);
 156         }
 157
 158         CQLNode node = parseQuery(index, relation);
 159         if ((compat == V1POINT2 || compat == V1POINT1SORT) &&
 160             lexer.ttype == CQLLexer.TT_SORTBY) {
 161             match(lexer.ttype);
 162             debug("sortspec");
 163
 164             CQLSortNode sortnode = new CQLSortNode(node);
 165             while (lexer.ttype != CQLLexer.TT_EOF) {
 166                 String sortindex = matchSymbol("sort index");
 167                 ModifierSet ms = gatherModifiers(sortindex);
 168                 sortnode.addSortIndex(ms);
 169             }
 170
 171             if (sortnode.keys.size() == 0) {
 172                 throw new CQLParseException("no sort keys", par.getPosition());
 173             }
 174
 175             node = sortnode;
 176         }
 177
 178         return node;
 179     }
 180
 181     private CQLNode parseQuery(String index, CQLRelation relation)
 182         throws CQLParseException, IOException {
 183         debug("in parseQuery()");
 184
 185         CQLNode term = parseTerm(index, relation);
 186         while (lexer.ttype != CQLLexer.TT_EOF &&
 187                lexer.ttype != ')' &&
 188                lexer.ttype != CQLLexer.TT_SORTBY) {
 189             if (lexer.ttype == CQLLexer.TT_AND ||
 190                 lexer.ttype == CQLLexer.TT_OR ||
 191                 lexer.ttype == CQLLexer.TT_NOT ||
 192                 lexer.ttype == CQLLexer.TT_PROX) {
 193                 int type = lexer.ttype;
 194                 String val = lexer.sval;
 195                 match(type);
 196                 ModifierSet ms = gatherModifiers(val);
 197                 CQLNode term2 = parseTerm(index, relation);
 198                 term = ((type == CQLLexer.TT_AND) ? new CQLAndNode(term, term2, ms) :
 199                         (type == CQLLexer.TT_OR)  ? new CQLOrNode (term, term2, ms) :
 200                         (type == CQLLexer.TT_NOT) ? new CQLNotNode(term, term2, ms) :
 201                                                  new CQLProxNode(term, term2, ms));
 202             } else {
 203                 throw new CQLParseException("expected boolean, got " +
 204                                             lexer.render(), par.getPosition());
 205             }
 206         }
 207
 208         debug("no more ops");
 209         return term;
 210     }
 211
 212     private ModifierSet gatherModifiers(String base)
 213         throws CQLParseException, IOException {
 214         debug("in gatherModifiers()");
 215
 216         ModifierSet ms = new ModifierSet(base);
 217         while (lexer.ttype == '/') {
 218             match('/');
 219             if (lexer.ttype != CQLLexer.TT_WORD)
 220                 throw new CQLParseException("expected modifier, "
 221                                             + "got " + lexer.render(),
 222                   par.getPosition());
 223             String type = lexer.sval.toLowerCase();
 224             match(lexer.ttype);
 225             if (!isSymbolicRelation()) {
 226                 // It's a simple modifier consisting of type only
 227                 ms.addModifier(type);
 228             } else {
 229                 // It's a complex modifier of the form type=value
 230                 String comparision = lexer.render(lexer.ttype, false);
 231                 match(lexer.ttype);
 232                 String value = matchSymbol("modifier value");
 233                 ms.addModifier(type, comparision, value);
 234             }
 235         }
 236
 237         return ms;
 238     }
 239
 240     private CQLNode parseTerm(String index, CQLRelation relation)
 241         throws CQLParseException, IOException {
 242         debug("in parseTerm()");
 243
 244         String word;
 245         while (true) {
 246             if (lexer.ttype == '(') {
 247                 debug("parenthesised term");
 248                 match('(');
 249                 CQLNode expr = parseQuery(index, relation);
 250                 match(')');
 251                 return expr;
 252             } else if (lexer.ttype == '>') {
 253                 return parsePrefix(index, relation, false);
 254             }
 255
 256             debug("non-parenthesised term");
 257             word = matchSymbol("index or term");
 258             while (lexer.ttype == CQLLexer.TT_WORD && !isRelation()) {
 259               word = word + " " + lexer.sval;
 260               match(CQLLexer.TT_WORD);
 261             }
 262
 263             if (!isRelation())
 264                 break;
 265
 266             index = word;
 267             String relstr = (lexer.ttype == CQLLexer.TT_WORD ?
 268                              lexer.sval : lexer.render(lexer.ttype, false));
 269             relation = new CQLRelation(relstr);
 270             match(lexer.ttype);
 271             ModifierSet ms = gatherModifiers(relstr);
 272             relation.ms = ms;
 273             debug("index='" + index + ", " +
 274                   "relation='" + relation.toCQL() + "'");
 275         }
 276
 277         CQLTermNode node = new CQLTermNode(index, relation, word);
 278         debug("made term node " + node.toCQL());
 279         return node;
 280     }
 281
 282     private CQLNode parsePrefix(String index, CQLRelation relation,
 283                                 boolean topLevel)
 284         throws CQLParseException, IOException {
 285         debug("prefix mapping");
 286
 287         match('>');
 288         String name = null;
 289         String identifier = matchSymbol("prefix-name");
 290         if (lexer.ttype == '=') {
 291             match('=');
 292             name = identifier;
 293             identifier = matchSymbol("prefix-identifer");
 294         }
 295         CQLNode node = topLevel ?
 296             parseTopLevelPrefixes(index, relation) :
 297             parseQuery(index, relation);
 298
 299         return new CQLPrefixNode(name, identifier, node);
 300     }
 301
 302     private boolean isRelation() {
 303         debug("isRelation: checking ttype=" + lexer.ttype +
 304               " (" + lexer.render() + ")");
 305         if (lexer.ttype == CQLLexer.TT_WORD &&
 306             (lexer.sval.indexOf('.') >= 0 ||
 307              lexer.sval.equals("any") ||
 308              lexer.sval.equals("all") ||
 309              lexer.sval.equals("within") ||
 310              lexer.sval.equals("encloses") ||
 311              (lexer.sval.equals("exact") && compat != V1POINT2) ||
 312              (lexer.sval.equals("scr") && compat != V1POINT2) ||
 313              (lexer.sval.equals("adj") && compat == V1POINT2) ||
 314              customRelations.contains(lexer.sval)))
 315           return true;
 316
 317         return isSymbolicRelation();
 318     }
 319
 320     private boolean isSymbolicRelation() {
 321         debug("isSymbolicRelation: checking ttype=" + lexer.ttype +
 322               " (" + lexer.render() + ")");
 323         return (lexer.ttype == '<' ||
 324                 lexer.ttype == '>' ||
 325                 lexer.ttype == '=' ||
 326                 lexer.ttype == CQLLexer.TT_LE ||
 327                 lexer.ttype == CQLLexer.TT_GE ||
 328                 lexer.ttype == CQLLexer.TT_NE ||
 329                 lexer.ttype == CQLLexer.TT_EQEQ);
 330     }
 331
 332     private void match(int token)
 333         throws CQLParseException, IOException {
 334         debug("in match(" + lexer.render(token, true) + ")");
 335         if (lexer.ttype != token)
 336             throw new CQLParseException("expected " +
 337                                         lexer.render(token, true) +
 338                                         ", " + "got " + lexer.render(),
 339               par.getPosition());
 340         int tmp = lexer.nextToken();
 341         debug("match() got token=" + lexer.ttype + ", " +
 342               "nval=" + lexer.nval + ", sval='" + lexer.sval + "'" +
 343               " (tmp=" + tmp + ")");
 344     }
 345
 346     private String matchSymbol(String expected)
 347         throws CQLParseException, IOException {
 348
 349         debug("in matchSymbol()");
 350         if (lexer.ttype == CQLLexer.TT_WORD ||
 351             lexer.ttype == CQLLexer.TT_NUMBER ||
 352             lexer.ttype == '"' ||
 353             // The following is a complete list of keywords.  Because
 354             // they're listed here, they can be used unquoted as
 355             // indexes, terms, prefix names and prefix identifiers.
 356             // ### Instead, we should ask the lexer whether what we
 357             // have is a keyword, and let the knowledge reside there.
 358             (allowKeywordTerms &&
 359             lexer.ttype == CQLLexer.TT_AND ||
 360             lexer.ttype == CQLLexer.TT_OR ||
 361             lexer.ttype == CQLLexer.TT_NOT ||
 362             lexer.ttype == CQLLexer.TT_PROX ||
 363             lexer.ttype == CQLLexer.TT_SORTBY)) {
 364             String symbol = (lexer.ttype == CQLLexer.TT_NUMBER) ?
 365                 lexer.render() : lexer.sval;
 366             match(lexer.ttype);
 367             return symbol;
 368         }
 369
 370         throw new CQLParseException("expected " + expected + ", " +
 371                                     "got " + lexer.render(), par.getPosition());
 372     }
 373
 374
 375     /**
 376      * Simple test-harness for the CQLParser class.
 377      * <P>
 378      * Reads a CQL query either from its command-line argument, if
 379      * there is one, or standard input otherwise.  So these two
 380      * invocations are equivalent:
 381      * <PRE>
 382      *  CQLParser 'au=(Kerninghan or Ritchie) and ti=Unix'
 383      *  echo au=(Kerninghan or Ritchie) and ti=Unix | CQLParser
 384      * </PRE>
 385      * The test-harness parses the supplied query and renders is as
 386      * XCQL, so that both of the invocations above produce the
 387      * following output:
 388      * <PRE>
 389      *  &lt;triple&gt;
 390      *    &lt;boolean&gt;
 391      *      &lt;value&gt;and&lt;/value&gt;
 392      *    &lt;/boolean&gt;
 393      *    &lt;triple&gt;
 394      *      &lt;boolean&gt;
 395      *        &lt;value&gt;or&lt;/value&gt;
 396      *      &lt;/boolean&gt;
 397      *      &lt;searchClause&gt;
 398      *        &lt;index&gt;au&lt;/index&gt;
 399      *        &lt;relation&gt;
 400      *          &lt;value&gt;=&lt;/value&gt;
 401      *        &lt;/relation&gt;
 402      *        &lt;term&gt;Kerninghan&lt;/term&gt;
 403      *      &lt;/searchClause&gt;
 404      *      &lt;searchClause&gt;
 405      *        &lt;index&gt;au&lt;/index&gt;
 406      *        &lt;relation&gt;
 407      *          &lt;value&gt;=&lt;/value&gt;
 408      *        &lt;/relation&gt;
 409      *        &lt;term&gt;Ritchie&lt;/term&gt;
 410      *      &lt;/searchClause&gt;
 411      *    &lt;/triple&gt;
 412      *    &lt;searchClause&gt;
 413      *      &lt;index&gt;ti&lt;/index&gt;
 414      *      &lt;relation&gt;
 415      *        &lt;value&gt;=&lt;/value&gt;
 416      *      &lt;/relation&gt;
 417      *      &lt;term&gt;Unix&lt;/term&gt;
 418      *    &lt;/searchClause&gt;
 419      *  &lt;/triple&gt;
 420      * </PRE>
 421      * <P>
 422      * @param -1
 423      *  CQL version 1.1 (default version 1.2)
 424      * @param -d
 425      *  Debug mode: extra output written to stderr.
 426      * @param -c
 427      *  Causes the output to be written in CQL rather than XCQL - that
 428      *  is, a query equivalent to that which was input, is output.  In
 429      *  effect, the test harness acts as a query canonicaliser.
 430      * @return
 431      *  The input query, either as XCQL [default] or CQL [if the
 432      *  <TT>-c</TT> option is supplied].
 433      */
 434     public static void main (String[] args) {
 435         char mode = 'x';        // x=XCQL, c=CQL, p=PQF
 436         String pfile = null;
 437
 438         List<String> argv = new ArrayList<String>();
 439         for (int i = 0; i < args.length; i++) {
 440             argv.add(args[i]);
 441         }
 442
 443         int compat = V1POINT2;
 444         if (argv.size() > 0 && argv.get(0).equals("-1")) {
 445             compat = V1POINT1;
 446             argv.remove(0);
 447         }
 448
 449         if (argv.size() > 0 && argv.get(0).equals("-d")) {
 450             DEBUG = true;
 451             argv.remove(0);
 452         }
 453
 454         if (argv.size() > 0 && argv.get(0).equals("-c")) {
 455             mode = 'c';
 456             argv.remove(0);
 457         } else if (argv.size() > 1 && argv.get(0).equals("-p")) {
 458             mode = 'p';
 459             argv.remove(0);
 460             pfile = (String) argv.get(0);
 461             argv.remove(0);
 462         }
 463
 464         if (argv.size() > 1) {
 465             System.err.println("Usage: CQLParser [-1] [-d] [-c] " +
 466                                "[-p <pqf-properties> [<CQL-query>]");
 467             System.err.println("If unspecified, query is read from stdin");
 468             System.exit(1);
 469         }
 470
 471         String cql;
 472         if (argv.size() == 1) {
 473             cql = (String) argv.get(0);
 474         } else {
 475             byte[] bytes = new byte[10000];
 476             try {
 477                 // Read in the whole of standard input in one go
 478                 int nbytes = System.in.read(bytes);
 479             } catch (IOException ex) {
 480                 System.err.println("Can't read query: " + ex.getMessage());
 481                 System.exit(2);
 482             }
 483             cql = new String(bytes);
 484         }
 485
 486         CQLParser parser = new CQLParser(compat);
 487         CQLNode root = null;
 488         try {
 489             root = parser.parse(cql);
 490         } catch (CQLParseException ex) {
 491             System.err.println("Syntax error: " + ex.getMessage());
 492             System.exit(3);
 493         } catch (IOException ex) {
 494             System.err.println("Can't compile query: " + ex.getMessage());
 495             System.exit(4);
 496         }
 497
 498         try {
 499             if (mode == 'c') {
 500                 System.out.println(root.toCQL());
 501             } else if (mode == 'p') {
 502                 InputStream f = new FileInputStream(pfile);
 503                 if (f == null)
 504                     throw new FileNotFoundException(pfile);
 505
 506                 Properties config = new Properties();
 507                 config.load(f);
 508                 f.close();
 509                 System.out.println(root.toPQF(config));
 510             } else {
 511                 System.out.print(root.toXCQL());
 512             }
 513         } catch (IOException ex) {
 514             System.err.println("Can't render query: " + ex.getMessage());
 515             System.exit(5);
 516         } catch (UnknownIndexException ex) {
 517             System.err.println("Unknown index: " + ex.getMessage());
 518             System.exit(6);
 519         } catch (UnknownRelationException ex) {
 520             System.err.println("Unknown relation: " + ex.getMessage());
 521             System.exit(7);
 522         } catch (UnknownRelationModifierException ex) {
 523             System.err.println("Unknown relation modifier: " +
 524                                ex.getMessage());
 525             System.exit(8);
 526         } catch (UnknownPositionException ex) {
 527             System.err.println("Unknown position: " + ex.getMessage());
 528             System.exit(9);
 529         } catch (PQFTranslationException ex) {
 530             // We catch all of this class's subclasses, so --
 531             throw new Error("can't get a PQFTranslationException");
 532         }
 533     }
 534 }