| author | emcmanus |
| Mon Mar 03 10:32:38 2008 +0100 (2 months ago) | |
| changeset 11 | 41d9c673dd9d |
| permissions | -rw-r--r-- |
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.isEmpty())
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 String s = sve.getValue();
494 q = Query.match(alhs, patternValueExp(s));
495 break;
496 }
497
498 case 2: { // IN
499 expect(LPAR);
500 List<ValueExp> values = new ArrayList<ValueExp>();
501 values.add(value());
502 while (skip(COMMA))
503 values.add(value());
504 expect(RPAR);
505 q = Query.in(lhs, values.toArray(new ValueExp[values.size()]));
506 break;
507 }
508
509 default:
510 throw new AssertionError();
511 }
512
513 if (not)
514 q = Query.not(q);
515
516 return q;
517 }
518
519 private ValueExp value() {
520 ValueExp lhs = factor();
521 int i;
522 while ((i = skipOne(PLUS, MINUS)) >= 0) {
523 ValueExp rhs = factor();
524 if (i == 0)
525 lhs = Query.plus(lhs, rhs);
526 else
527 lhs = Query.minus(lhs, rhs);
528 }
529 return lhs;
530 }
531
532 private ValueExp factor() {
533 ValueExp lhs = term();
534 int i;
535 while ((i = skipOne(TIMES, DIVIDE)) >= 0) {
536 ValueExp rhs = term();
537 if (i == 0)
538 lhs = Query.times(lhs, rhs);
539 else
540 lhs = Query.div(lhs, rhs);
541 }
542 return lhs;
543 }
544
545 private ValueExp term() {
546 boolean signed = false;
547 int sign = +1;
548 if (skip(PLUS))
549 signed = true;
550 else if (skip(MINUS)) {
551 signed = true; sign = -1;
552 }
553
554 Token t = current();
555 next();
556
557 if (t instanceof DoubleLit)
558 return Query.value(sign * ((DoubleLit) t).number);
559 if (t instanceof LongLit) {
560 long n = ((LongLit) t).number;
561 if (n == Long.MIN_VALUE && sign != -1)
562 throw new IllegalArgumentException("Illegal positive integer: " + n);
563 return Query.value(sign * n);
564 }
565 if (signed)
566 throw new IllegalArgumentException("Expected number after + or -");
567
568 if (t == LPAR) {
569 ValueExp v = value();
570 expect(RPAR);
571 return v;
572 }
573 if (t.equals(FALSE) || t.equals(TRUE)) {
574 return Query.value(t.equals(TRUE));
575 }
576 if (t.equals(CLASS))
577 return Query.classattr();
578
579 if (t instanceof StringLit)
580 return Query.value(t.string); // Not toString(), which would requote '
581
582 // At this point, all that remains is something that will call Query.attr
583
584 if (!(t instanceof Id) && !(t instanceof QuotedId))
585 throw new IllegalArgumentException("Unexpected token " + t);
586
587 String name1 = name(t);
588
589 if (skip(SHARP)) {
590 Token t2 = current();
591 next();
592 String name2 = name(t2);
593 return Query.attr(name1, name2);
594 }
595 return Query.attr(name1);
596 }
597
598 // Initially, t is the first token of a supposed name and current()
599 // is the second.
600 private String name(Token t) {
601 StringBuilder sb = new StringBuilder();
602 while (true) {
603 if (!(t instanceof Id) && !(t instanceof QuotedId))
604 throw new IllegalArgumentException("Unexpected token " + t);
605 sb.append(t.string);
606 if (current() != DOT)
607 break;
608 sb.append('.');
609 next();
610 t = current();
611 next();
612 }
613 return sb.toString();
614 }
615
616 private StringValueExp stringvalue() {
617 // Currently the only way to get a StringValueExp when constructing
618 // a QueryExp is via Query.value(String), so we only recognize
619 // string literals here. But if we expand queries in the future
620 // that might no longer be true.
621 Token t = current();
622 next();
623 if (!(t instanceof StringLit))
624 throw new IllegalArgumentException("Expected string: " + t);
625 return Query.value(t.string);
626 }
627
628 // Convert the SQL pattern syntax, using % and _, to the Query.match
629 // syntax, using * and ?. The tricky part is recognizing \% and
630 // \_ as literal values, and also not replacing them inside [].
631 // But Query.match does not recognize \ inside [], which makes our
632 // job a tad easier.
633 private StringValueExp patternValueExp(String s) {
634 int c;
635 for (int i = 0; i < s.length(); i += Character.charCount(c)) {
636 c = s.codePointAt(i);
637 switch (c) {
638 case '\\':
639 i++; // i += Character.charCount(c), but we know it's 1!
640 if (i >= s.length())
641 throw new IllegalArgumentException("\\ at end of pattern");
642 break;
643 case '[':
644 i = s.indexOf(']', i);
645 if (i < 0)
646 throw new IllegalArgumentException("[ without ]");
647 break;
648 case '%':
649 s = s.substring(0, i) + "*" + s.substring(i + 1);
650 break;
651 case '_':
652 s = s.substring(0, i) + "?" + s.substring(i + 1);
653 break;
654 case '*':
655 case '?':
656 s = s.substring(0, i) + '\\' + (char) c + s.substring(i + 1);
657 i++;
658 break;
659 }
660 }
661 return Query.value(s);
662 }
663 }