1 /*

     2  * Copyright 2008 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any questions.

    24  */

    25 

    26 package javax.management;

    27 

    28 import java.util.ArrayList;

    29 import java.util.Formatter;

    30 import java.util.List;

    31 import java.util.Set;

    32 import java.util.TreeSet;

    33 

    34 /**

    35  * <p>Parser for JMX queries represented in an SQL-like language.</p>

    36  */

    37 /*

    38  * Note that if a query starts with ( then we don't know whether it is

    39  * a predicate or just a value that is parenthesized.  So, inefficiently,

    40  * we try to parse a predicate and if that doesn't work we try to parse

    41  * a value.

    42  */

    43 class QueryParser {

    44     // LEXER STARTS HERE

    45 

    46     private static class Token {

    47         final String string;

    48         Token(String s) {

    49             this.string = s;

    50         }

    51 

    52         @Override

    53         public String toString() {

    54             return string;

    55         }

    56     }

    57 

    58     private static final Token

    59             END = new Token("<end of string>"),

    60             LPAR = new Token("("), RPAR = new Token(")"),

    61             COMMA = new Token(","), DOT = new Token("."), SHARP = new Token("#"),

    62             PLUS = new Token("+"), MINUS = new Token("-"),

    63             TIMES = new Token("*"), DIVIDE = new Token("/"),

    64             LT = new Token("<"), GT = new Token(">"),

    65             LE = new Token("<="), GE = new Token(">="),

    66             NE = new Token("<>"), EQ = new Token("="),

    67             NOT = new Id("NOT"), INSTANCEOF = new Id("INSTANCEOF"),

    68             FALSE = new Id("FALSE"), TRUE = new Id("TRUE"),

    69             BETWEEN = new Id("BETWEEN"), AND = new Id("AND"),

    70             OR = new Id("OR"), IN = new Id("IN"),

    71             LIKE = new Id("LIKE"), CLASS = new Id("CLASS");

    72 

    73     // Keywords that can appear where an identifier can appear.

    74     // If an attribute is one of these, then it must be quoted when

    75     // converting a query into a string.

    76     // We use a TreeSet so we can look up case-insensitively.

    77     private static final Set<String> idKeywords =

    78             new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);

    79     static {

    80         for (Token t : new Token[] {NOT, INSTANCEOF, FALSE, TRUE, LIKE, CLASS})

    81             idKeywords.add(t.string);

    82     };

    83 

    84     public static String quoteId(String id) {

    85         if (id.contains("\"") || idKeywords.contains(id))

    86             return '"' + id.replace("\"", "\"\"") + '"';

    87         else

    88             return id;

    89     }

    90 

    91     private static class Id extends Token {

    92         Id(String id) {

    93             super(id);

    94         }

    95 

    96         // All other tokens use object identity, which means e.g. that one

    97         // occurrence of the string constant 'x' is not the same as another.

    98         // For identifiers, we ignore case when testing for equality so that

    99         // for a keyword such as AND you can also spell it as "And" or "and".

   100         // But we keep the original case of the identifier, so if it's not

   101         // a keyword we will distinguish between the attribute Foo and the

   102         // attribute FOO.

   103         @Override

   104         public boolean equals(Object o) {

   105             return (o instanceof Id && (((Id) o).toString().equalsIgnoreCase(toString())));

   106         }

   107     }

   108 

   109     private static class QuotedId extends Token {

   110         QuotedId(String id) {

   111             super(id);

   112         }

   113 

   114         @Override

   115         public String toString() {

   116             return '"' + string.replace("\"", "\"\"") + '"';

   117         }

   118     }

   119 

   120     private static class StringLit extends Token {

   121         StringLit(String s) {

   122             super(s);

   123         }

   124 

   125         @Override

   126         public String toString() {

   127             return '\'' + string.replace("'", "''") + '\'';

   128         }

   129     }

   130 

   131     private static class LongLit extends Token {

   132         long number;

   133 

   134         LongLit(long number) {

   135             super(Long.toString(number));

   136             this.number = number;

   137         }

   138     }

   139 

   140     private static class DoubleLit extends Token {

   141         double number;

   142 

   143         DoubleLit(double number) {

   144             super(Double.toString(number));

   145             this.number = number;

   146         }

   147     }

   148 

   149     private static class Tokenizer {

   150         private final String s;

   151         private final int len;

   152         private int i = 0;

   153 

   154         Tokenizer(String s) {

   155             this.s = s;

   156             this.len = s.length();

   157         }

   158 

   159         private int thisChar() {

   160             if (i == len)

   161                 return -1;

   162             return s.codePointAt(i);

   163         }

   164 

   165         private void advance() {

   166             i += Character.charCount(thisChar());

   167         }

   168 

   169         private int thisCharAdvance() {

   170             int c = thisChar();

   171             advance();

   172             return c;

   173         }

   174 

   175         Token nextToken() {

   176             // In this method, c is the character we're looking at, and

   177             // thisChar() is the character after that.  Everything must

   178             // preserve these invariants.  When we return we then have

   179             // thisChar() being the start of the following token, so

   180             // the next call to nextToken() will begin from there.

   181             int c;

   182 

   183             // Skip space

   184             do {

   185                 if (i == len)

   186                     return null;

   187                 c = thisCharAdvance();

   188             } while (Character.isWhitespace(c));

   189 

   190             // Now c is the first character of the token, and tokenI points

   191             // to the character after that.

   192             switch (c) {

   193                 case '(': return LPAR;

   194                 case ')': return RPAR;

   195                 case ',': return COMMA;

   196                 case '.': return DOT;

   197                 case '#': return SHARP;

   198                 case '*': return TIMES;

   199                 case '/': return DIVIDE;

   200                 case '=': return EQ;

   201                 case '-': return MINUS;

   202                 case '+': return PLUS;

   203 

   204                 case '>':

   205                     if (thisChar() == '=') {

   206                         advance();

   207                         return GE;

   208                     } else

   209                         return GT;

   210 

   211                 case '<':

   212                     c = thisChar();

   213                     switch (c) {

   214                         case '=': advance(); return LE;

   215                         case '>': advance(); return NE;

   216                         default: return LT;

   217                     }

   218 

   219                 case '!':

   220                     if (thisCharAdvance() != '=')

   221                         throw new IllegalArgumentException("'!' must be followed by '='");

   222                     return NE;

   223 

   224                 case '"':

   225                 case '\'': {

   226                     int quote = c;

   227                     StringBuilder sb = new StringBuilder();

   228                     while (true) {

   229                         while ((c = thisChar()) != quote) {

   230                             if (c < 0) {

   231                                 throw new IllegalArgumentException(

   232                                         "Unterminated string constant");

   233                             }

   234                             sb.appendCodePoint(thisCharAdvance());

   235                         }

   236                         advance();

   237                         if (thisChar() == quote) {

   238                             sb.appendCodePoint(quote);

   239                             advance();

   240                         } else

   241                             break;

   242                     }

   243                     if (quote == '\'')

   244                         return new StringLit(sb.toString());

   245                     else

   246                         return new QuotedId(sb.toString());

   247                 }

   248             }

   249 

   250             // Is it a numeric constant?

   251             if (Character.isDigit(c) || c == '.') {

   252                 StringBuilder sb = new StringBuilder();

   253                 int lastc = -1;

   254                 while (true) {

   255                     sb.appendCodePoint(c);

   256                     c = Character.toLowerCase(thisChar());

   257                     if (c == '+' || c == '-') {

   258                         if (lastc != 'e')

   259                             break;

   260                     } else if (!Character.isDigit(c) && c != '.' && c != 'e')

   261                         break;

   262                     lastc = c;

   263                     advance();

   264                 }

   265                 String s = sb.toString();

   266                 if (s.indexOf('.') >= 0 || s.indexOf('e') >= 0) {

   267                     double d = parseDoubleCheckOverflow(s);

   268                     return new DoubleLit(d);

   269                 } else {

   270                     // Like the Java language, we allow the numeric constant

   271                     // x where -x = Long.MIN_VALUE, even though x is not

   272                     // representable as a long (it is Long.MAX_VALUE + 1).

   273                     // Code in the parser will reject this value if it is

   274                     // not the operand of unary minus.

   275                     long l = -Long.parseLong("-" + s);

   276                     return new LongLit(l);

   277                 }

   278             }

   279 

   280             // It must be an identifier.

   281             if (!Character.isJavaIdentifierStart(c)) {

   282                 StringBuilder sb = new StringBuilder();

   283                 Formatter f = new Formatter(sb);

   284                 f.format("Bad character: %c (%04x)", c, c);

   285                 throw new IllegalArgumentException(sb.toString());

   286             }

   287 

   288             StringBuilder id = new StringBuilder();

   289             while (true) { // identifier

   290                 id.appendCodePoint(c);

   291                 c = thisChar();

   292                 if (!Character.isJavaIdentifierPart(c))

   293                     break;

   294                 advance();

   295             }

   296 

   297             return new Id(id.toString());

   298         }

   299     }

   300 

   301     /* Parse a double as a Java compiler would do it, throwing an exception

   302      * if the input does not fit in a double.  We assume that the input

   303      * string is not "Infinity" and does not have a leading sign.

   304      */

   305     private static double parseDoubleCheckOverflow(String s) {

   306         double d = Double.parseDouble(s);

   307         if (Double.isInfinite(d))

   308             throw new NumberFormatException("Overflow: " + s);

   309         if (d == 0.0) {  // Underflow checking is hard!  CR 6604864

   310             String ss = s;

   311             int e = s.indexOf('e');  // we already forced E to lowercase

   312             if (e > 0)

   313                 ss = s.substring(0, e);

   314             ss = ss.replace("0", "").replace(".", "");

   315             if (!ss.equals(""))

   316                 throw new NumberFormatException("Underflow: " + s);

   317         }

   318         return d;

   319     }

   320 

   321     // PARSER STARTS HERE

   322 

   323     private final List<Token> tokens;

   324     private int tokenI;

   325     // The current token is always tokens[tokenI].

   326 

   327     QueryParser(String s) {

   328         // Construct the complete list of tokens immediately and append

   329         // a sentinel (END).

   330         tokens = new ArrayList<Token>();

   331         Tokenizer tokenizer = new Tokenizer(s);

   332         Token t;

   333         while ((t = tokenizer.nextToken()) != null)

   334             tokens.add(t);

   335         tokens.add(END);

   336     }

   337 

   338     private Token current() {

   339         return tokens.get(tokenI);

   340     }

   341 

   342     // If the current token is t, then skip it and return true.

   343     // Otherwise, return false.

   344     private boolean skip(Token t) {

   345         if (t.equals(current())) {

   346             tokenI++;

   347             return true;

   348         }

   349         return false;

   350     }

   351 

   352     // If the current token is one of the ones in 'tokens', then skip it

   353     // and return its index in 'tokens'.  Otherwise, return -1.

   354     private int skipOne(Token... tokens) {

   355         for (int i = 0; i < tokens.length; i++) {

   356             if (skip(tokens[i]))

   357                 return i;

   358         }

   359         return -1;

   360     }

   361 

   362     // If the current token is t, then skip it and return.

   363     // Otherwise throw an exception.

   364     private void expect(Token t) {

   365         if (!skip(t))

   366             throw new IllegalArgumentException("Expected " + t + ", found " + current());

   367     }

   368 

   369     private void next() {

   370         tokenI++;

   371     }

   372 

   373     QueryExp parseQuery() {

   374         QueryExp qe = query();

   375         if (current() != END)

   376             throw new IllegalArgumentException("Junk at end of query: " + current());

   377         return qe;

   378     }

   379 

   380     // The remainder of this class is a classical recursive-descent parser.

   381     // We only need to violate the recursive-descent scheme in one place,

   382     // where parentheses make the grammar not LL(1).

   383 

   384     private QueryExp query() {

   385         QueryExp lhs = andquery();

   386         while (skip(OR))

   387             lhs = Query.or(lhs, andquery());

   388         return lhs;

   389     }

   390 

   391     private QueryExp andquery() {

   392         QueryExp lhs = predicate();

   393         while (skip(AND))

   394             lhs = Query.and(lhs, predicate());

   395         return lhs;

   396     }

   397 

   398     private QueryExp predicate() {

   399         // Grammar hack.  If we see a paren, it might be (query) or

   400         // it might be (value).  We try to parse (query), and if that

   401         // fails, we parse (value).  For example, if the string is

   402         // "(2+3)*4 < 5" then we will try to parse the query

   403         // "2+3)*4 < 5", which will fail at the ), so we'll back up to

   404         // the paren and let value() handle it.

   405         if (skip(LPAR)) {

   406             int parenIndex = tokenI - 1;

   407             try {

   408                 QueryExp qe = query();

   409                 expect(RPAR);

   410                 return qe;

   411             } catch (IllegalArgumentException e) {

   412                 // OK: try parsing a value

   413             }

   414             tokenI = parenIndex;

   415         }

   416 

   417         if (skip(NOT))

   418             return Query.not(predicate());

   419 

   420         if (skip(INSTANCEOF))

   421             return Query.isInstanceOf(stringvalue());

   422 

   423         if (skip(LIKE)) {

   424             StringValueExp sve = stringvalue();

   425             String s = sve.getValue();

   426             try {

   427                 return new ObjectName(s);

   428             } catch (MalformedObjectNameException e) {

   429                 throw new IllegalArgumentException(

   430                         "Bad ObjectName pattern after LIKE: '" + s + "'", e);

   431             }

   432         }

   433 

   434         ValueExp lhs = value();

   435 

   436         return predrhs(lhs);

   437     }

   438 

   439     // The order of elements in the following arrays is important.  The code

   440     // in predrhs depends on integer indexes.  Change with caution.

   441     private static final Token[] relations = {

   442             EQ, LT, GT, LE, GE, NE,

   443          // 0,  1,  2,  3,  4,  5,

   444     };

   445     private static final Token[] betweenLikeIn = {

   446             BETWEEN, LIKE, IN

   447          // 0,       1,    2,

   448     };

   449 

   450     private QueryExp predrhs(ValueExp lhs) {

   451         Token start = current(); // for errors

   452 

   453         // Look for < > = etc

   454         int i = skipOne(relations);

   455         if (i >= 0) {

   456             ValueExp rhs = value();

   457             switch (i) {

   458                 case 0: return Query.eq(lhs, rhs);

   459                 case 1: return Query.lt(lhs, rhs);

   460                 case 2: return Query.gt(lhs, rhs);

   461                 case 3: return Query.leq(lhs, rhs);

   462                 case 4: return Query.geq(lhs, rhs);

   463                 case 5: return Query.not(Query.eq(lhs, rhs));

   464                 // There is no Query.ne so <> is shorthand for the above.

   465                 default:

   466                     throw new AssertionError();

   467             }

   468         }

   469 

   470         // Must be BETWEEN LIKE or IN, optionally preceded by NOT

   471         boolean not = skip(NOT);

   472         i = skipOne(betweenLikeIn);

   473         if (i < 0)

   474             throw new IllegalArgumentException("Expected relation at " + start);

   475 

   476         QueryExp q;

   477         switch (i) {

   478             case 0: { // BETWEEN

   479                 ValueExp lower = value();

   480                 expect(AND);

   481                 ValueExp upper = value();

   482                 q = Query.between(lhs, lower, upper);

   483                 break;

   484             }

   485 

   486             case 1: { // LIKE

   487                 if (!(lhs instanceof AttributeValueExp)) {

   488                     throw new IllegalArgumentException(

   489                             "Left-hand side of LIKE must be an attribute");

   490                 }

   491                 AttributeValueExp alhs = (AttributeValueExp) lhs;

   492                 StringValueExp sve = stringvalue();

   493                 q = Query.match(alhs, sve);

   494                 break;

   495             }

   496 

   497             case 2: { // IN

   498                 expect(LPAR);

   499                 List<ValueExp> values = new ArrayList<ValueExp>();

   500                 values.add(value());

   501                 while (skip(COMMA))

   502                     values.add(value());

   503                 expect(RPAR);

   504                 q = Query.in(lhs, values.toArray(new ValueExp[values.size()]));

   505                 break;

   506             }

   507 

   508             default:

   509                 throw new AssertionError();

   510         }

   511 

   512         if (not)

   513             q = Query.not(q);

   514 

   515         return q;

   516     }

   517 

   518     private ValueExp value() {

   519         ValueExp lhs = factor();

   520         int i;

   521         while ((i = skipOne(PLUS, MINUS)) >= 0) {

   522             ValueExp rhs = factor();

   523             if (i == 0)

   524                 lhs = Query.plus(lhs, rhs);

   525             else

   526                 lhs = Query.minus(lhs, rhs);

   527         }

   528         return lhs;

   529     }

   530 

   531     private ValueExp factor() {

   532         ValueExp lhs = term();

   533         int i;

   534         while ((i = skipOne(TIMES, DIVIDE)) >= 0) {

   535             ValueExp rhs = term();

   536             if (i == 0)

   537                 lhs = Query.times(lhs, rhs);

   538             else

   539                 lhs = Query.div(lhs, rhs);

   540         }

   541         return lhs;

   542     }

   543 

   544     private ValueExp term() {

   545         boolean signed = false;

   546         int sign = +1;

   547         if (skip(PLUS))

   548             signed = true;

   549         else if (skip(MINUS)) {

   550             signed = true; sign = -1;

   551         }

   552 

   553         Token t = current();

   554         next();

   555 

   556         if (t instanceof DoubleLit)

   557             return Query.value(sign * ((DoubleLit) t).number);

   558         if (t instanceof LongLit) {

   559             long n = ((LongLit) t).number;

   560             if (n == Long.MIN_VALUE && sign != -1)

   561                 throw new IllegalArgumentException("Illegal positive integer: " + n);

   562             return Query.value(sign * n);

   563         }

   564         if (signed)

   565             throw new IllegalArgumentException("Expected number after + or -");

   566 

   567         if (t == LPAR) {

   568             ValueExp v = value();

   569             expect(RPAR);

   570             return v;

   571         }

   572         if (t.equals(FALSE) || t.equals(TRUE)) {

   573             return Query.value(t.equals(TRUE));

   574         }

   575         if (t.equals(CLASS))

   576             return Query.classattr();

   577 

   578         if (t instanceof StringLit)

   579             return Query.value(t.string); // Not toString(), which would requote '

   580 

   581         // At this point, all that remains is something that will call Query.attr

   582 

   583         if (!(t instanceof Id) && !(t instanceof QuotedId))

   584             throw new IllegalArgumentException("Unexpected token " + t);

   585 

   586         String name1 = name(t);

   587 

   588         if (skip(SHARP)) {

   589             Token t2 = current();

   590             next();

   591             String name2 = name(t2);

   592             return Query.attr(name1, name2);

   593         }

   594         return Query.attr(name1);

   595     }

   596 

   597     // Initially, t is the first token of a supposed name and current()

   598     // is the second.

   599     private String name(Token t) {

   600         StringBuilder sb = new StringBuilder();

   601         while (true) {

   602             if (!(t instanceof Id) && !(t instanceof QuotedId))

   603                 throw new IllegalArgumentException("Unexpected token " + t);

   604             sb.append(t.string);

   605             if (current() != DOT)

   606                 break;

   607             sb.append('.');

   608             next();

   609             t = current();

   610             next();

   611         }

   612         return sb.toString();

   613     }

   614 

   615     private StringValueExp stringvalue() {

   616         // Currently the only way to get a StringValueExp when constructing

   617         // a QueryExp is via Query.value(String), so we only recognize

   618         // string literals here.  But if we expand queries in the future

   619         // that might no longer be true.

   620         Token t = current();

   621         next();

   622         if (!(t instanceof StringLit))

   623             throw new IllegalArgumentException("Expected string: " + t);

   624         return Query.value(t.string);

   625     }

   626 }