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