Selector


1   /*
2    * The contents of this file are subject to the terms
3    * of the Common Development and Distribution License
4    * (the "License").  You may not use this file except
5    * in compliance with the License.
6    *
7    * You can obtain a copy of the license at
8    * https://glassfish.dev.java.net/public/CDDLv1.0.html.
9    * See the License for the specific language governing
10   * permissions and limitations under the License.
11   *
12   * When distributing Covered Code, include this CDDL
13   * HEADER in each file and include the License file at
14   * https://glassfish.dev.java.net/public/CDDLv1.0.html.
15   *
16   * If applicable add the following below this CDDL HEADER,
17   * with the fields enclosed by brackets "[]" replaced with
18   * your own identifying information: Portions Copyright
19   * [year] [name of copyright owner]
20   */
21  
22  /*
23   * @(#)Selector.java    1.9 05/02/06
24   *
25   * Copyright 2006 Sun Microsystems, Inc.  All Rights Reserved.
26   */
27  
28  package net.walend.somnifugi.sql92;
29  
30  import java.util.HashMap  ;
31  import java.util.HashSet  ;
32  import java.util.Iterator  ;
33  import java.util.LinkedList  ;
34  import java.util.Map  ;
35  import java.util.Stack  ;
36  
37  
38  /**
39   * A class that implements JMS selectors. See section 3.8 of the JMS 1.1 spec.
40   *
41   */
42  public class Selector
43  {
44      
45      public static boolean DEBUG = false;
46      public static boolean VERBOSE_DEBUG = false;
47      
48      // Tokens that can appear in a selector string. Note that some
49      // tokens are considered "compound". I.e. they are built from
50      // one or more primitive tokens.
51      static final int INVALID              = 500;    // Illegal token
52      static final int STARTING             = 0;
53      
54      // Operators
55      static final int OR                   = 1;    // OR, or
56      static final int AND                  = 2;    // AND, and
57      static final int NOT                  = 3;    // NOT, not
58      
59      static final int NOT_EQUALS           = 4;    // <>
60      static final int LTE                  = 5;    // <=
61      static final int LT                   = 6;    // <
62      static final int GTE                  = 7;    // >=
63      static final int GT                   = 8;    // >
64      static final int EQUALS               = 9;    // =
65      
66      static final int UNARY_PLUS           = 10;   // +
67      static final int UNARY_MINUS          = 11;   // -
68      static final int MULTIPLY             = 12;   // *
69      static final int DIVIDE               = 13;   // /
70      static final int PLUS                 = 14;   // +
71      static final int MINUS                = 15;   // -
72      
73      static final int BETWEEN              = 16;   // BETWEEN, between
74      static final int NOT_BETWEEN          = 17;   // Compound: "NOT BETWEEN"
75      static final int IN                   = 18;   // IN
76      static final int NOT_IN               = 19;   // Compound: "NOT IN"
77      static final int LIKE                 = 20;   // LIKE
78      static final int ESCAPE               = 21;   // ESCAPE
79      static final int NOT_LIKE             = 22;   // Compound: "NOT LIKE"
80      static final int IS_NULL              = 23;   // Compound: "IS NULL"
81      static final int IS_NOT_NULL          = 24;   // Compound: "IS NOT NULL"
82      static final int IS                   = 25;   // IS
83      static final int IS_NOT               = 26;   // Compound "IS NOT"
84      static final int LEFT_PAREN           = 27;   // (
85      static final int RIGHT_PAREN          = 28;   // )
86      
87      static final int COMMA                = 29;   // ,
88      // Operands
89      static final int IDENTIFIER           = 101;   // Java identifier
90      static final int STRING               = 102;   // '...'
91      static final int DOUBLE               = 103;   // -57.92
92      static final int LONG                 = 104;   // +347
93      static final int TRUE                 = 105;   // TRUE, true
94      static final int FALSE                = 106;   // FALSE, false
95      static final int JMS_FIELD            = 107;   // JMS*
96      static final int RANGE                = 108;   // Compound: "15 AND 19"
97      static final int LIST                 = 109;   // Compound: "('US', 'UK', 'Peru')"
98      static final int WHITESPACE           = 110;   // Whitespace
99      static final int NULL                 = 111;   // NULL token
100     static final int UNKNOWN              = 112;   // Unknown result
101     static final int RE                   = 113;   // LIKE regular expression
102     
103     // Markers
104     static final int AND_MARKER           = 200;
105     static final int OR_MARKER            = 201;
106     
107     /*
108      * The JMS specification specifically states that type conversions
109      * between Strings and numeric values should not be performed.
110      * See JMS 1.1 section 3.8.1.1. For example if you set a string property:
111      *    msg.setStringProperty("count", "2")
112      * then the following should evaluate to false because a string cannot be
113      * used in an arithmetic expression:
114      *    "count = 2"
115      * The above expression should be "count = '2'"
116      * The older selector implementation supported this type conversion
117      * for some expressions. This introduces the possibility that some
118      * applications may be relying on this bug, and will break now that
119      * it is fixed. This boolean let's use switch to the old behavior.
120      *
121      * If convertTypes is true, then the selector evaluator will convert
122      * string values to numeric values. Currently for only = and <>
123      */
124     private static boolean convertTypes = false;
125     
126     /*
127      * True to short circuit boolean evaluation. For example
128      * if you have "e1 AND e2", you do not need to evaluate e2 if e1 is
129      * false. This boolean is just a safetyvalve in case there is a flaw
130      * in the shortCircuit algorithm
131      */
132     private static boolean shortCircuit = true;
133     
134     private boolean usesProperties = false;
135     private boolean usesFields     = false;
136     
137     private static HashMap  <String  ,Integer  > keywords = null;
138     
139     private static HashSet  <String  > headers = null;
140     
141     // Original selector string
142     private String        selector = null;
143     
144     // Compiled selector string. An array of SelectorTokens in RPN
145     private Object  []      compiledSelector = null;
146     
147     // Stack used for evaluation
148     private Stack  <SelectorToken> stack = new Stack  <SelectorToken>();
149     
150     // The selector cache is used to cache selectors. This way we can
151     // return the same Selector instance for identical selector strings.
152     // The selectors are cached in a WeakValueHashMap. This means once
153     // the Selector is no longer referenced it is garbage collected and
154     // removed from the HashMap.
155     private static WeakValueHashMap selectorCache = null;
156     
157     static
158     {
159         keywords = new HashMap  <String  ,Integer  >();
160         
161         keywords.put("NOT", new Integer  (NOT));
162         keywords.put("AND", new Integer  (AND));
163         keywords.put("OR", new Integer  (OR));
164         keywords.put("BETWEEN", new Integer  (BETWEEN));
165         keywords.put("LIKE", new Integer  (LIKE));
166         keywords.put("IN", new Integer  (IN));
167         keywords.put("IS", new Integer  (IS));
168         keywords.put("ESCAPE", new Integer  (ESCAPE));
169         keywords.put("NULL", new Integer  (NULL));
170         keywords.put("TRUE", new Integer  (TRUE));
171         keywords.put("FALSE", new Integer  (FALSE));
172         
173         headers = new HashSet  <String  >(6);
174         
175         headers.add("JMSDeliveryMode");
176         headers.add("JMSPriority");
177         headers.add("JMSMessageID");
178         headers.add("JMSTimestamp");
179         headers.add("JMSCorrelationID");
180         headers.add("JMSType");
181         
182         selectorCache = new WeakValueHashMap("SelectorCache");
183     }
184     
185     public static void setConvertTypes(boolean b)
186     {
187         convertTypes = b;
188     }
189     
190     public static boolean getConvertTypes()
191     {
192         return convertTypes;
193     }
194     
195     public static void setShortCircuit(boolean b)
196     {
197         shortCircuit = b;
198     }
199     
200     public static boolean getShortCircuit()
201     {
202         return shortCircuit;
203     }
204     
205     /**
206      * Compiles a selector string into a Selector object.
207      * This also checks to ensure that the passed selector string
208      * is a valid expression.
209      *
210      * @param   selector    Selector string as specified in JMS 1.1
211      */
212     public static Selector compile(String   selector)
213         throws SelectorFormatException
214     {
215         
216         if (selector == null || selector.length() == 0)
217         {
218             return null;
219         }
220         
221         Selector o = null;
222         synchronized (selectorCache)
223         {
224             // First check if selector is already in cache.
225             o = (Selector)selectorCache.get(selector);
226             
227             if (o == null)
228             {
229                 // Selector not in cache. Create a new one and stick it in the
230                 // cache.
231                 o = new Selector(selector);
232                 o.compile();
233                 selectorCache.put(selector, o);
234             }
235         }
236         
237         return o;
238     }
239     
240     /**
241      * Create a Selector.
242      *
243      * @param   selector    Selector string as specified in JMS 1.1
244      */
245     private Selector(String   selector)
246     {
247         this.selector = selector;
248     }
249     
250     /**
251      * Compile the Selector
252      * <p>
253      * Compiles the selector into its binary form. This must
254      * be called before match(). A call to compile also performs
255      * an evaluation to make sure the selector is a valid expression.
256      */
257     synchronized void compile() throws SelectorFormatException
258     {
259         
260         /*
261          * This isn't the most efficient implementation possible,
262          * but compilation doesn't need to be as fast as evaluation.
263          * Note that we do some extra work (mainly by tracking more
264          * token values than we need to) to make debugging easier.
265          * Also, we do this in multiple passes simply because it is easier
266          * to understand, and optimizing compile speed is not a priority.
267          *
268          * A compiled selector consists of a token stream. This steam
269          * is held in a LinkedList initially, but is an Object[] in its
270          * final compiled form. Each token is ecapsulated by a SelectorToken
271          * object. This object contains the token constant (OR, STRING, etc)
272          * as well as an optional associated value (like the actual
273          * string value for a STRING token).
274          *
275          * By the time the compilation is done we want everything boiled
276          * down to operators and operands.
277          *
278          * The final compiled form is in Reverse Polish Notation (RPN).
279          */
280         
281         /* First pass: tokenize into primatives.
282          * Add a trailing space to the selector cleanly terminate parsing
283          */
284         LinkedList   l = tokenize(selector + " ");
285         
286         if (VERBOSE_DEBUG)
287         {
288             dumpTokens(l);
289         }
290         
291         /* Second pass: aggregate primatives into compound tokens (if any)
292          * For example this converts the 3 primative tokens: IS NOT NULL
293          * to the single token IS_NOT_NULL
294          */
295         l = aggregate(l);
296         if (VERBOSE_DEBUG)
297         {
298             dumpTokens(l);
299             System.out.println();
300         }
301         
302         /* Third pass: prepare
303          * This pass prepares some of the more funky operations
304          * (LIKE, BETWEEN, IN, etc) for evaluation. For example it
305          * takes all the strings in the IN list and puts them in
306          * a hash table and making that a single operand.
307          */
308         l = prepare(l);
309         if (VERBOSE_DEBUG)
310         {
311             dumpTokens(l);
312             System.out.println();
313         }
314         
315         /* Fourth pass: Perform any additional validation
316          */
317         validate(l);
318         
319         /* Fith pass: convert to RPN. This removes parens and
320          * prepares the stream for simple stack based execution.
321          * The output from this is an Object[] of SelectorTokens
322          */
323         compiledSelector = convertToRPN(l);
324         
325         if (DEBUG)
326         {
327             System.out.println(toDebugString());
328         }
329         
330         // At this point compiledSelector has a token stream that is all
331         // ready for evaluation! We perform one evaluation to catch any
332         // errors that may occur at runtime. We do this with empty
333         // property hashtables
334         
335         this.match(new HashMap  (0), new HashMap  (0));
336     }
337     
338     /**
339      * Parse selector string into token primatives. This uses
340      * a state machine to track state. Each state has a number.
341      */
342     private LinkedList  <SelectorToken> tokenize(String   selector)
343     throws SelectorFormatException
344     {
345         LinkedList  <SelectorToken> buf = new LinkedList  <SelectorToken>();
346         int len = selector.length();
347         int state = 0;
348         
349         // A buffer to hold the token string.
350         StringBuffer   tokenBuf = new StringBuffer  (80);
351         
352         int token = STARTING;
353         int lastToken = STARTING;
354         int radix = 10;
355         int i = 0;
356         
357         for (i = 0; i < len; i++)
358         {
359             char c = selector.charAt(i);
360             Object   value = null;
361             
362             switch (state)
363             {
364                 
365                 case 0:
366                     tokenBuf.delete(0, tokenBuf.length());
367                     switch (c)
368                     {
369                         case ',':
370                             token = Selector.COMMA;
371                             tokenBuf.append(c);
372                             value = tokenBuf.toString();
373                             break;
374                         case '=':
375                             if (lastToken == Selector.EQUALS)
376                             {
377                                 // We do an explicit check for == since this may be
378                                 // a common error.
379                                 throw new SelectorFormatException(
380                                         "Invalid operator ==, use =",
381                                         selector, i);
382                             }
383                             token = Selector.EQUALS;
384                             tokenBuf.append(c);
385                             value = tokenBuf.toString();
386                             break;
387                         case '/':
388                             token = Selector.DIVIDE;
389                             tokenBuf.append(c);
390                             value = tokenBuf.toString();
391                             break;
392                         case '*':
393                             token = Selector.MULTIPLY;
394                             tokenBuf.append(c);
395                             value = tokenBuf.toString();
396                             break;
397                         case '(':
398                             token = Selector.LEFT_PAREN;
399                             tokenBuf.append(c);
400                             value = tokenBuf.toString();
401                             break;
402                         case ')':
403                             token = Selector.RIGHT_PAREN;
404                             tokenBuf.append(c);
405                             value = tokenBuf.toString();
406                             break;
407                         case '-':
408                             // If last token was an operator then this is unary
409                             if (lastToken == STARTING ||
410                                     (isOperator(lastToken) && lastToken != RIGHT_PAREN ) )
411                             {
412                                 token = Selector.UNARY_MINUS;
413                                 tokenBuf.append(c);
414                                 value = tokenBuf.toString();
415                             }
416                             else
417                             {
418                                 token = Selector.MINUS;
419                                 tokenBuf.append(c);
420                                 value = tokenBuf.toString();
421                             }
422                             break;
423                         case '+':
424                             // If last token was an operator then this is unary
425                             if (lastToken == STARTING ||
426                                     (isOperator(lastToken) && lastToken != RIGHT_PAREN ) )
427                             {
428                                 token = Selector.UNARY_PLUS;
429                                 tokenBuf.append(c);
430                                 value = tokenBuf.toString();
431                             }
432                             else
433                             {
434                                 token = Selector.PLUS;
435                                 tokenBuf.append(c);
436                                 value = tokenBuf.toString();
437                             }
438                             break;
439                         case '>':
440                             // GT or GTE.
441                             tokenBuf.append(c);
442                             state = 1;
443                             break;
444                         case '<':
445                             // LT, LTE, or NOT_EQUALS
446                             tokenBuf.append(c);
447                             state = 2;
448                             break;
449                         case '\'':
450                             // Start of a string literal
451                             state = 9;
452                             break;
453                         case '.':
454                             // Start of a float
455                             tokenBuf.append(c);
456                             state = 6;
457                             break;
458                         case '0':
459                             // Start of octal or hex numeric constant
460                             tokenBuf.append(c);
461                             state = 3;
462                             break;
463                         default:
464                             if (Character.isJavaIdentifierStart(c))
465                             {
466                                 // Start of an identifier
467                                 tokenBuf.append(c);
468                                 state = 11;
469                             }
470                             else if (Character.isDigit(c))
471                             {
472                                 // Start of a number
473                                 tokenBuf.append(c);
474                                 state = 5;
475                             }
476                             else if (Character.isWhitespace(c))
477                             {
478                                 // Whitespace. Ignore.
479                                 token = Selector.WHITESPACE;
480                             }
481                             else
482                             {
483                                 // Invalid character
484                                 throw new SelectorFormatException(
485                                         "Invalid character " + c,
486                                         selector, i);
487                             }
488                     }
489                     break;
490                     
491                     // Saw a >
492                 case 1:
493                     switch (c)
494                     {
495                         case '=':
496                             tokenBuf.append(c);
497                             token = Selector.GTE;
498                             value = tokenBuf.toString();
499                             state = 0;
500                             break;
501                         default:
502                             token = Selector.GT;
503                             value = tokenBuf.toString();
504                             state = 0;
505                             i--; // pushback delimiter
506                             break;
507                     }
508                     break;
509                     
510                     
511                     // Saw a <
512                 case 2:
513                     switch (c)
514                     {
515                         case '=':
516                             tokenBuf.append(c);
517                             token = Selector.LTE;
518                             value = tokenBuf.toString();
519                             state = 0;
520                             break;
521                         case '>':
522                             tokenBuf.append(c);
523                             token = Selector.NOT_EQUALS;
524                             value = tokenBuf.toString();
525                             state = 0;
526                             break;
527                         default:
528                             token = Selector.LT;
529                             value = tokenBuf.toString();
530                             state = 0;
531                             i--; // pushback delimiter
532                             break;
533                     }
534                     break;
535                     
536                     // Either an octal or hex numeric constant
537                 case 3:
538                     // We go to state 5 whether it's a hex or an octal constant.
539                     // This means we may get something like 049h which is invalid.
540                     // But when we go to construct the java.lang number object
541                     // we'll catch this.
542                     if (c == 'x' || c == 'X')
543                     {
544                         // Hex. Don't remember X, just that we're in base 16
545                         radix = 16;
546                         state = 5;
547                     }
548                     else if (Character.isDigit(c))
549                     {
550                         // Octal
551                         radix = 8;
552                         tokenBuf.append(c);
553                         state = 5;
554                     }
555                     else
556                     {
557                         // Hit a delimeter. Back up and make state 5 handle this 0
558                         i--;
559                         state = 5;
560                     }
561                     break;
562                     
563                     // Working on a number!
564                 case 5:
565                     if ( (radix == 16 && isHexDigit(c)) ||
566                             Character.isDigit(c) )
567                     {
568                         tokenBuf.append(c);
569                     }
570                     else if (c == '.')
571                     {
572                         // It's a float. Go get decimal portion
573                         tokenBuf.append(c);
574                         state = 6;
575                     }
576                     else if (c == 'E' || c == 'e')
577                     {
578                         // It's a float. Go get exponential
579                         tokenBuf.append(c);
580                         state = 7;
581                     }
582                     else
583                     {
584                         // Hit delimeter. It's just an integer
585                         token = Selector.LONG;
586                         
587                         // Handle this here, cause if the value is MIN_LONG
588                         // we can't create the absoute value of it!
589                         if (lastToken == UNARY_MINUS)
590                         {
591                             tokenBuf.insert(0, '-');
592                             // Remove UNARY_MINUS from token stream
593                             buf.removeLast();
594                         }
595                         
596                         try
597                         {
598                             value = Long.valueOf(tokenBuf.toString(), radix);
599                             radix = 10;
600                         }
601                         catch (NumberFormatException   e)
602                         {
603                             throw new SelectorFormatException(
604                                     "Invalid numeric constant: " + e.getMessage(),
605                                     selector, i);
606                         }
607                         state = 0;
608                         
609                         if (c == 'l' || c == 'L')
610                         {
611                             // If it is a trailing L then we skip it.
612                             // We always use longs
613                         }
614                         else
615                         {
616                             i--; // pushback delimiter
617                         }
618                     }
619                     break;
620                     
621                     // Working on decimal portion of a float
622                 case 6:
623                     if (Character.isDigit(c))
624                     {
625                         tokenBuf.append(c);
626                     }
627                     else if (c == 'E' || c == 'e')
628                     {
629                         // Go get exponential
630                         tokenBuf.append(c);
631                         state = 7;
632                     }
633                     else
634                     {
635                         // Hit delimeter.
636                         token = Selector.DOUBLE;
637                         try
638                         {
639                             value = Double.valueOf(tokenBuf.toString());
640                         }
641                         catch (NumberFormatException   e)
642                         {
643                             throw new SelectorFormatException(
644                                     "Invalid numeric constant: " + e.getMessage(),
645                                     selector, i);
646                         }
647                         state = 0;
648                         if (c == 'd' || c == 'D' || c == 'f' || c == 'F')
649                         {
650                             // Trailing qualifier. Just skip it. Everything is a D
651                         }
652                         else
653                         {
654                             i--; // pushback delimiter
655                         }
656                     }
657                     break;
658                     
659                     // Starting to work on exponential portion of a float
660                 case 7:
661                     if (Character.isDigit(c))
662                     {
663                         tokenBuf.append(c);
664                         state = 8;
665                     }
666                     else if (c == '-')
667                     {
668                         tokenBuf.append(c);
669                         state = 8;
670                     }
671                     else
672                     {
673                         // Hit delimeter. Nothing after the E
674                         token = Selector.DOUBLE;
675                         try
676                         {
677                             value = Double.valueOf(tokenBuf.toString());
678                         }
679                         catch (NumberFormatException   e)
680                         {
681                             throw new SelectorFormatException(
682                                     "Invalid numeric constant: " + e.getMessage(),
683                                     selector, i);
684                         }
685                         state = 0;
686                         if (c == 'd' || c == 'D' || c == 'f' || c == 'F')
687                         {
688                             // Trailing qualifier. Just skip it. Everything is a D
689                         }
690                         else
691                         {
692                             i--; // pushback delimiter
693                         }
694                     }
695                     break;
696                     
697                     // Finishing work on exponential portion of a float
698                 case 8:
699                     if (Character.isDigit(c))
700                     {
701                         tokenBuf.append(c);
702                     }
703                     else
704                     {
705                         // Hit delimeter.
706                         token = Selector.DOUBLE;
707                         try
708                         {
709                             value = Double.valueOf(tokenBuf.toString());
710                         }
711                         catch (NumberFormatException   e)
712                         {
713                             throw new SelectorFormatException(
714                                     "Invalid numeric constant: " + e.getMessage(),
715                                     selector, i);
716                         }
717                         state = 0;
718                         if (c == 'd' || c == 'D' || c == 'f' || c == 'F')
719                         {
720                             // Trailing qualifier. Just skip it. Everything is a D
721                         }
722                         else
723                         {
724                             i--; // pushback delimiter
725                         }
726                     }
727                     break;
728                     
729                     // Working on a string literal
730                 case 9:
731                     if (c == '\'')
732                     {
733                         state = 10;
734                     }
735                     else
736                     {
737                         tokenBuf.append(c);
738                     }
739                     break;
740                     
741                     // Is this the end of a string? Or an escaped single quote
742                 case 10:
743                     if (c == '\'')
744                     {
745                         // Escaped single quote. Put it in token and continue
746                         state = 9;
747                         tokenBuf.append(c);
748                     }
749                     else
750                     {
751                         // Hit delimeter.
752                         token = Selector.STRING;
753                         value = tokenBuf.toString();
754                         state = 0;
755                         i--; // pushback delimiter
756                     }
757                     break;
758                     
759                     // Working on an identifier
760                 case 11:
761                     if (Character.isJavaIdentifierPart(c))
762                     {
763                         tokenBuf.append(c);
764                     }
765                     else
766                     {
767                         value = tokenBuf.toString();
768                         // OK, we either have an identifier, or a keyword.
769                         // this method handles figuring that out.
770                         token = identifierToKeyWord((String  )value);
771                         state = 0;
772                         i--; // pushback delimiter
773                     }
774                     break;
775                 default:
776                     // This should never happen.
777                     throw new SelectorFormatException(
778                             "Selector tokenizer in bad state: " + state +
779                             " tokenBuf=" + tokenBuf + " char=" + c,
780                             selector, i);
781             }
782             
783             // We detect if the Selector uses message properties
784             // (as opposed to just JMS fields).
785             if (token == Selector.IDENTIFIER)
786             {
787                 usesProperties = true;
788             }
789             else if (token == Selector.JMS_FIELD)
790             {
791                 usesFields = true;
792             }
793             
794             if (state == 0 && token == Selector.INVALID)
795             {
796                 // This should never happen.
797                 throw new SelectorFormatException(
798                         "Unknown token: " + token +
799                         " tokenBuf=" + tokenBuf,
800                         selector, i);
801             }
802             
803             if (state == 0 && token != Selector.WHITESPACE)
804             {
805                 buf.add(SelectorToken.getInstance(token, value));
806                 lastToken = token;
807                 radix = 10;
808             }
809         }
810         
811         if (state == 9)
812         {
813             // Missing closing quote
814             throw new SelectorFormatException(
815                     "Missing closing quote", selector, i);
816         }
817         else if (state != 0)
818         {
819             throw new SelectorFormatException(
820                     "Invalid Expression", selector, i);
821         }
822         
823         return buf;
824     }
825     
826     // Check if s is a keyword, JMS field, or generic identifier
827     private int identifierToKeyWord(String   s)
828     {
829         Integer   n = (Integer  )keywords.get(s.toUpperCase());
830         if (n != null)
831         {
832             return n.intValue();
833         }
834         else if (s.startsWith("JMS"))
835         {
836             if(headers.contains(s))
837                 return JMS_FIELD;
838             else
839                 return IDENTIFIER;
840         }
841         else
842         {
843             return IDENTIFIER;
844         }
845     }
846     
847     private boolean isHexDigit(char c)
848     {
849         return (Character.isDigit(c) ||
850                 c == 'a' || c == 'A' ||
851                 c == 'b' || c == 'B' ||
852                 c == 'c' || c == 'C' ||
853                 c == 'd' || c == 'D' ||
854                 c == 'e' || c == 'E' ||
855                 c == 'f' || c == 'F');
856     }
857     
858     /**
859      * Aggregate primatives into compound tokens (if any).
860      * This performs the following conversions:
861      *  NOT BETWEEN => NOT_BETWEEN
862      *  NOT IN      => NOT_IN
863      *  NOT LIKE    => NOT_LIKE
864      *  IS NULL     => IS_NULL
865      *  IS NOT NULL => IS_NOT_NULL
866      */
867     private LinkedList   aggregate(LinkedList   in)
868     throws SelectorFormatException
869     {
870         LinkedList  <SelectorToken> out = new LinkedList  <SelectorToken>();
871         
872         SelectorToken token0;
873         SelectorToken token1;
874         SelectorToken token2;
875         int len = in.size();
876         
877         for (int i = 0; i < len; i++)
878         {
879             token0 = (SelectorToken)in.get(i);
880             token1 = null;
881             token2 = null;
882             
883             if (i + 1 < len)
884             {
885                 token1 = (SelectorToken)in.get(i + 1);
886             }
887             
888             if (i + 2 < len)
889             {
890                 token2 = (SelectorToken)in.get(i + 2);
891             }
892             
893             switch (token0.getToken())
894             {
895                 case Selector.NOT:
896                     if (token1 == null)
897                     {
898                         // NOT
899                         out.add(token0);
900                     }
901                     else if (token1.getToken() == Selector.BETWEEN)
902                     {
903                         // NOT BETWEEN
904                         out.add(SelectorToken.getInstance(Selector.NOT_BETWEEN,
905                                 (String  )token0.getValue() + " " +
906                                 (String  )token1.getValue() ));
907                         // Skip BETWEEN
908                         i++;
909                     }
910                     else if (token1.getToken() == Selector.IN)
911                     {
912                         // NOT IN
913                         out.add(SelectorToken.getInstance(Selector.NOT_IN,
914                                 (String  )token0.getValue() + " " +
915                                 (String  )token1.getValue() ));
916                         // Skip IN
917                         i++;
918                     }
919                     else if (token1.getToken() == Selector.LIKE)
920                     {
921                         // NOT LIKE
922                         out.add(SelectorToken.getInstance(Selector.NOT_LIKE,
923                                 (String  )token0.getValue() + " " +
924                                 (String  )token1.getValue() ));
925                         // Skip LIKE
926                         i++;
927                     }
928                     else
929                     {
930                         // NOT
931                         out.add(token0);
932                     }
933                     break;
934                     
935                 case Selector.IS:
936                     if (token1 == null)
937                     {
938                         // just IS
939                         out.add(token0);
940                     }
941                     else if (token1.getToken() == Selector.NULL)
942                     {
943                         // IS NULL
944                         out.add(SelectorToken.getInstance(Selector.IS_NULL,
945                                 (String  )token0.getValue() + " " +
946                                 (String  )token1.getValue()));
947                         // Skip NULL
948                         i++;
949                     }
950                     else if (token1.getToken() == Selector.NOT)
951                     {
952                         // IS NOT
953                         if (token2 == null)
954                         {
955                             // just IS NOT
956                             out.add(SelectorToken.getInstance(Selector.IS_NOT,
957                                     (String  )token0.getValue() + " " +
958                                     (String  )token1.getValue()));
959                             // Skip NOT
960                             i++;
961                         }
962                         else if (token2.getToken() == Selector.NULL)
963                         {
964                             // IS NOT NULL
965                             out.add(SelectorToken.getInstance(Selector.IS_NOT_NULL,
966                                     (String  )token0.getValue() + " " +
967                                     (String  )token1.getValue() + " " +
968                                     (String  )token2.getValue()));
969                             // Skip NOT NULL
970                             i++;
971                             i++;
972                         }
973                         else
974                         {
975                             // just IS NOT
976                             out.add(SelectorToken.getInstance(Selector.IS_NOT,
977                                     (String  )token0.getValue() + " " +
978                                     (String  )token1.getValue()));
979                             // Skip NOT
980                             i++;
981                         }
982                     }
983                     else
984                     {
985                         // Just IS
986                         out.add(token0);
987                     }
988                     break;
989                 default:
990                     // Simple token
991                     out.add(token0);
992                     break;
993             }
994         }
995         
996         return out;
997     }
998     
999     /**
1000     * Prepare list for conversion to RPN.
1001     * This step prepares some of the more funky operations into
1002     * a format that can be more easily evaluated using a simple RPN
1003     * expression evaluator.
1004     * It performs the following:
1005     *
1006     * Replaces the AND in the BETWEEN and NOT_BETWEEN constructs with
1007     * a comma. The comma ensures we correctly convert the arithmetic
1008     * expressions in the BETWEEN ranges to RPN. This is especially true
1009     * when you take into account unary minus (ie BETWEEN - 1 and 5).
1010     * Then BETWEEN is just treated as an operator that requires 3 operands
1011     * and the COMMA is ignmored.
1012     *
1013     * Converts the list construct in the IN and NOT_IN operations into
1014     * a single token (operand) that has a HashMap for it's value.
1015     *
1016     * Detects the ESCAPE keyword and converts the LIKE regular expression
1017     * string into a simple object that continas the string and the
1018     * escape character, so when we go to evaluate it we can do the
1019     * right thing based on the RE package we use.
1020     */
1021    private LinkedList   prepare(LinkedList   in)
1022    throws SelectorFormatException
1023    {
1024        LinkedList  <SelectorToken> out = new LinkedList  <SelectorToken>();
1025        
1026        SelectorToken token0;
1027        SelectorToken token1;
1028        SelectorToken token2;
1029        int len = in.size();
1030        
1031        for (int i = 0; i < len; i++)
1032        {
1033            token0 = (SelectorToken)in.get(i);
1034            
1035            switch (token0.getToken())
1036            {
1037                
1038                case Selector.BETWEEN:
1039                case Selector.NOT_BETWEEN:
1040                    out.add(token0);
1041                    i++;
1042                    // OKAY we saw a BETWEEN. Scan forward until we hit an AND
1043                    // and convert it to a COMMA
1044                    while (i < len)
1045                    {
1046                        token0 = (SelectorToken)in.get(i);
1047                        if (token0.getToken() == Selector.AND)
1048                        {
1049                            out.add(SelectorToken.getInstance(Selector.COMMA, ","));
1050                            break;
1051                        }
1052                        out.add(token0);
1053                        i++;
1054                    }
1055                    break;
1056                    
1057                case Selector.IN:
1058                case Selector.NOT_IN:
1059                    out.add(token0);
1060                    i++;
1061                    token0 = (SelectorToken)in.get(i);
1062                    if (token0.getToken() != Selector.LEFT_PAREN)
1063                    {
1064                        throw new SelectorFormatException(
1065                                "Missing ( in IN statement", selector);
1066                    }
1067                    // Skip open paren
1068                    i++;
1069                    // OK convert list of strings into a HashSet
1070                    HashSet  <Object  > set = new HashSet  <Object  >();
1071                    while (i < len)
1072                    {
1073                        token0 = (SelectorToken)in.get(i);
1074                        
1075                        if (token0.getToken() == Selector.RIGHT_PAREN)
1076                        {
1077                            // skip close paren and terminate
1078                            break;
1079                        }
1080                        
1081                        if (token0.getToken() == Selector.COMMA)
1082                        {
1083                            // skip commas
1084                            i++;
1085                            continue;
1086                        }
1087                        
1088                        if (token0.getToken() != Selector.STRING)
1089                        {
1090                            throw new SelectorFormatException(
1091                                    "IN requires string literal: " +
1092                                    token0.getValue(), selector);
1093                        }
1094                        
1095                        // Put string in HashMap
1096                        set.add(token0.getValue());
1097                        i++;
1098                    }
1099                    
1100                    // Put list token with HashSet as value. This now becomes
1101                    // the right operand for IN and NOT_IN
1102                    out.add(SelectorToken.getInstance(Selector.LIST, set));
1103                    break;
1104                    
1105                    
1106                case Selector.LIKE:
1107                case Selector.NOT_LIKE:
1108                    out.add(token0);
1109                    i++;
1110                    // String literal should be next token
1111                    token0 = (SelectorToken)in.get(i);
1112                    if (token0.getToken() != Selector.STRING)
1113                    {
1114                        throw new SelectorFormatException(
1115                                "LIKE requires string literal: " +
1116                                token0.getValue(), selector);
1117                    }
1118                    
1119                    // String literal is the regular expression
1120                    String   re = (String  )token0.getValue();
1121                    String   escape = null;
1122                    i++;
1123                    if (i < len)
1124                    {
1125                        token0 = (SelectorToken)in.get(i);
1126                        if (token0.getToken() == Selector.ESCAPE)
1127                        {
1128                            // Get escape string
1129                            i++;
1130                            token0 = (SelectorToken)in.get(i);
1131                            if (token0.getToken() != Selector.STRING)
1132                            {
1133                                throw new SelectorFormatException(
1134                                        "ESCAPE requires string literal: " +
1135                                        token0.getValue(), selector);
1136                            }
1137                            else
1138                            {
1139                                escape = (String  )token0.getValue();
1140                            }
1141                        }
1142                        else
1143                        {
1144                            i--; // push back token since it wasn't ESCAPE
1145                        }
1146                    }
1147                    out.add(SelectorToken.getInstance(Selector.RE,
1148                            new RegularExpression(re, escape)));
1149                    break;
1150                    
1151                default:
1152                    // Simple token
1153                    out.add(token0);
1154                    break;
1155            }
1156        }
1157        
1158        return out;
1159    }
1160    
1161    /**
1162     * Validate expression
1163     * This does a simple, final syntax check before conversion to RPN.
1164     * It detects invalid expressions such as "= red 'color'"
1165     */
1166    private void validate(LinkedList   in)
1167    throws SelectorFormatException
1168    {
1169        
1170        SelectorToken token;
1171        int len = in.size();
1172        int prevToken = STARTING;
1173        
1174        for (int i = 0; i < len; i++)
1175        {
1176            token = (SelectorToken)in.get(i);
1177            
1178            // If the current token is an operand, then the previous
1179            // token must be an operator (or STARTING)
1180            if (!isOperator(token))
1181            {
1182                if (prevToken != STARTING &&
1183                        !isOperator(prevToken))
1184                {
1185                    throw new SelectorFormatException(
1186                            "Missing operator", selector);
1187                }
1188            }
1189            
1190            prevToken = token.getToken();
1191        }
1192        
1193        return;
1194    }
1195    
1196    /**
1197     * Convert the token stream into Reverse Polish Notation (aka RPN
1198     * or postfix notation). This helps detect syntax errors and
1199     * prepares the expression for evaluation. Here is the procedure
1200     * for converting infix to postfix:
1201     *
1202     * Scan infix expression from left to right.
1203     * A. When an operand is encountered move it immediately to the
1204     *    RPN expression.
1205     * B. When an operator is encountered:
1206     *    1. First pop operators from the stack and place them into the
1207     *       RPN expression until either the stack is empty or the precedence
1208     *       level of the top operator in the stack is LESS than the
1209     *       precedence of the operator encountered in the scan.
1210     *    2. Then push the operator encountered onto the stack
1211     * C. When a left paren is encountered push it onto the stack
1212     *    (it creates a "sub-stack").
1213     * D. When unstacking operators stop when a left paren comes to the top
1214     *    of the stack.
1215     * E. When a right paren is encountered when scanning the expression unstack
1216     *    operators until a matching left paren is found in the stack.
1217     *    Pop left paren and disgard. Disgard right paren.
1218     * F. When the entire expression has been scanned pop any remaining
1219     *    operators from the stack and place into the RPN expression.
1220     *
1221     * The following is done to support evaluation short circuit:
1222     *
1223     * After you have pushed an AND (OR) operator onto the stack, insert the
1224     * AND_MARKER (OR_MARKER) into the RPN expression.
1225     */
1226    private Object  [] convertToRPN(LinkedList   in)
1227    throws SelectorFormatException
1228    {
1229        Stack  <SelectorToken> stack = new Stack  <SelectorToken>();
1230        
1231        // For this final pass we convert to a fixed size array to
1232        // make final evaluation faster. We make the array larger to
1233        // handle markers if we have any.
1234        Object  [] out = new Object  [(int)(in.size() * 1.5)];
1235        int i = 0;
1236        
1237        Iterator   iter = in.iterator();
1238        
1239        while (iter.hasNext())
1240        {
1241            SelectorToken token = (SelectorToken)iter.next();
1242            
1243            if (!isOperator(token))
1244            {
1245                // Operand. Move directly to RPN
1246                out[i++] = token;
1247                continue;
1248            }
1249            
1250            if (token.getToken() == LEFT_PAREN)
1251            {
1252                // Push ( immediately on stack
1253                stack.push(token);
1254                continue;
1255            }
1256            
1257            SelectorToken t = null;
1258            if (token.getToken() == RIGHT_PAREN)
1259            {
1260                // Pop operators until we encounter a left paren
1261                do
1262                {
1263                    if (stack.empty())
1264                    {
1265                        throw new SelectorFormatException(
1266                                "Missing (", selector);
1267                    }
1268                    
1269                    t = (SelectorToken)stack.pop();
1270                    if (t.getToken() != LEFT_PAREN)
1271                    {
1272                        out[i++] = t;
1273                    }
1274                } while (t.getToken() != LEFT_PAREN);
1275                continue;
1276            }
1277            
1278            // Operator is not a paren. Copy operators off of stack
1279            // until we hit one with a lower priority than the one
1280            // from the scanned expression.
1281            while (!stack.empty())
1282            {
1283                t = (SelectorToken)stack.peek();
1284                if (t.getToken() == LEFT_PAREN)
1285                {
1286                    break;
1287                }
1288                if (getPrecedence(t) < getPrecedence(token))
1289                {
1290                    // Stop if precedence of top operator is less than
1291                    // operator from expression scan.
1292                    break;
1293                }
1294                // Copy higher precedence operators to RPN expression
1295                out[i++] = (SelectorToken)stack.pop();
1296            }
1297            
1298            // Push operator from scanned expression onto stack
1299            stack.push(token);
1300            
1301            if (shortCircuit)
1302            {
1303                // Markers are used to short circuit expression evaluation
1304                // If we just pushed an AND or OR onto the stack, put the
1305                // corresponding marker into the expression
1306                if (token.getToken() == Selector.AND)
1307                {
1308                    out[i++] = SelectorToken.getInstance(Selector.AND_MARKER);
1309                }
1310                else if (token.getToken() == Selector.OR)
1311                {
1312                    out[i++] = SelectorToken.getInstance(Selector.OR_MARKER);
1313                }
1314            }
1315        }
1316        
1317        // Expression has been scanned. Pop all remaining operators
1318        // off of stack and put in expression.
1319        while (!stack.empty())
1320        {
1321            out[i] = (SelectorToken)stack.pop();
1322            if ( ((SelectorToken)out[i]).getToken() == LEFT_PAREN )
1323            {
1324                throw new SelectorFormatException(
1325                        "Missing )", selector);
1326            }
1327            i++;
1328        }
1329        
1330        return out;
1331    }
1332    
1333    /**
1334     * Evaluate the selector using the passed properties and message fields.
1335     * compile() must have been called before calling match().
1336     *
1337     * @param  properties   HashMap containing message properties. These
1338     *                      should be String/Object pairs.
1339     *                      If usesProperties() returns 'false' then message
1340     *                      properties are not needed to evaluate the expression
1341     *                      and this parameter may be null.
1342     * @param   fields      HashMap containg JMS Message fields. These
1343     *                      should be String/Object pairs.
1344     *                      If usesFields() returns 'false' then JMS fields
1345     *                      are not needed to evaluate the expression
1346     *                      and this parameter may be null.
1347     *
1348     * @return  true if expression evaluates to true, else false.
1349     *
1350     * @throws  SelectorFormatException if the selector syntax is invalid
1351     */
1352    public synchronized boolean match(Map   properties, Map   fields)
1353        throws SelectorFormatException
1354    {
1355        
1356        /*
1357         * This method is synchronized primarily because of the runtime
1358         * stack. If the stack was local then we wouldn't need to synchronize,
1359         * but we'd be creating a new stack on every match() call.
1360         */
1361        
1362        /*
1363         * You evaluate an RPN using a stack. It goes like this:
1364         * A. Scan RPN expression from left to right
1365         * B. When you encounter an operand push it onto the stack.
1366         * C. When you encounter an operator pop off as many operands
1367         *    as you need (in our case 1, 2 or 3), and apply operator
1368         *    to the operands.
1369         * D. Push result onto the stack
1370         * E. When scan is complete the final result is on top of the stack
1371         *
1372         * The following is performed when supporting evaluation short circuit:
1373         *
1374         * If an AND_MARKER is encountered during scanning:
1375         *   If the top of the evaluation stack is FALSE then scan the
1376         *     RPN expression until the AND operator is encountered. Skip the
1377         *     AND operator. If during this scan additional AND_MARKERS are
1378         *     encountered then continue scanning expression until you have
1379         *     skipped as man AND operators as AND_MARKERS encountered.
1380         *     Then continue evaluation.
1381         *   Else skip the AND_MARKER and continue evaluation.
1382         *
1383         * If an OR_MARKER is encountered during scanning:
1384         *   If the top of the evaluation stack is TRUE then scan the
1385         *     RPN expression until the OR operator is encountered. Skip the
1386         *     OR operator. If during this scan additional OR_MARKERS are
1387         *     encountered then continue scanning expression until you have
1388         *     skipped as man OR operators as OR_MARKERS encountered.
1389         *     Then continue evaluation.
1390         *   Else skip the OR_MARKER and continue evaluation.
1391         */
1392        
1393        stack.clear();
1394        SelectorToken   token, operand1, operand2, operand3;
1395        
1396        int markers = 0;
1397        
1398        try
1399        {
1400            
1401            for (int i = 0; i < compiledSelector.length; i++)
1402            {
1403                token = (SelectorToken)compiledSelector[i];
1404                
1405                if (token == null)
1406                {
1407                    // RPN may be shorter than the original since we
1408                    // remove parens.
1409                    break;
1410                }
1411                
1412                if (shortCircuit)
1413                {
1414                    
1415                    // Short circuit boolean expressions
1416                    if (token.getToken() == Selector.AND_MARKER)
1417                    {
1418                        // We hit an AND_MARKER.
1419                        int t = ((SelectorToken)stack.peek()).getToken();
1420                        if (t == Selector.FALSE)
1421                        {
1422                            // Top of eval stack is FALSE. Short circuit by scanning
1423                            // until we hit an AND operator. If we see other AND_MARKERS
1424                            // we must skip as many operators as markers.
1425                            markers = 1;
1426                            while (markers > 0)
1427                            {
1428                                token = (SelectorToken)compiledSelector[++i];
1429                                if (token.getToken() == Selector.AND_MARKER)
1430                                {
1431                                    markers++;
1432                                }
1433                                else if (token.getToken() == Selector.AND)
1434                                {
1435                                    markers--;
1436                                }
1437                                else
1438                                {
1439                                }
1440                            }
1441                            // Completed short circuit. Continue evaluation
1442                            continue;
1443                        }
1444                        else
1445                        {
1446                            // Not a short circuit. Skip marker and continue
1447                            continue;
1448                        }
1449                    }
1450                    else if (token.getToken() == Selector.OR_MARKER)
1451                    {
1452                        // We hit an OR_MARKER.
1453                        int t = ((SelectorToken)stack.peek()).getToken();
1454                        if (t == Selector.TRUE)
1455                        {
1456                            // Top of eval stack is TRUE. Short circuit by scanning
1457                            // until we hit an OR operator. If we see other OR_MARKERS
1458                            // we must skip as many operators as markers.
1459                            markers = 1;
1460                            while (markers > 0)
1461                            {
1462                                token = (SelectorToken)compiledSelector[++i];
1463                                if (token.getToken() == Selector.OR_MARKER)
1464                                {
1465                                    markers++;
1466                                }
1467                                else if (token.getToken() == Selector.OR)
1468                                {
1469                                    markers--;
1470                                }
1471                                else
1472                                {
1473                                }
1474                            }
1475                            // Completed short circuit. Continue evaluation
1476                            continue;
1477                        }
1478                        else
1479                        {
1480                            // Not a short circuit. Skip marker and continue
1481                            continue;
1482                        }
1483                    }
1484                    
1485                } // if shortCircuit
1486                
1487                
1488                // Push operands onto stack
1489                if (!isOperator(token))
1490                {
1491                    if (token.getToken() == IDENTIFIER)
1492                    {
1493                        // Expand identifier
1494                        Object   value;
1495                        if (properties == null)
1496                        {
1497                            value = null;
1498                        }
1499                        else
1500                        {
1501                            value = properties.get((String  )token.getValue());
1502                        }
1503                        if (value == null)
1504                        {
1505                            stack.push(SelectorToken.getInstance(UNKNOWN, null));
1506                        }
1507                        else
1508                        {
1509                            stack.push(propertyToToken(value));
1510                        }
1511                    }
1512                    else if (token.getToken() == JMS_FIELD)
1513                    {
1514                        // Expand identifier
1515                        Object   value;
1516                        if (fields == null)
1517                        {
1518                            value = null;
1519                        }
1520                        else
1521                        {
1522                            value = fields.get((String  )token.getValue());
1523                        }
1524                        if (value == null)
1525                        {
1526                            stack.push(SelectorToken.getInstance(UNKNOWN, null));
1527                        }
1528                        else
1529                        {
1530                            stack.push(propertyToToken(value));
1531                        }
1532                    }
1533                    else
1534                    {
1535                        // A literal operand
1536                        stack.push(token);
1537                    }
1538                    continue;
1539                }
1540                
1541                if (token.getToken() == COMMA)
1542                {
1543                    // Comma's are no-ops. They were there to ensure conversion
1544                    // from infix to RPN went correctly for BETWEEN ranges.
1545                    continue;
1546                }
1547                
1548                // Handle operator. We know we'll need at least one operand
1549                // so get it now.
1550                operand1 = (SelectorToken)stack.pop();
1551                
1552                // Process operator
1553                switch (token.getToken())
1554                {
1555                    
1556                    // For OR, AND, and NOT we have to handle UNKNOWN.
1557                    // See Section 3.8.1.2 of the JMS 1.1 spec
1558                    case OR:
1559                        operand2 = (SelectorToken)stack.pop();
1560                        if (operand1.getToken() == TRUE ||
1561                                operand2.getToken() == TRUE)
1562                        {
1563                            stack.push(SelectorToken.getInstance(TRUE));
1564                        }
1565                        else if (operand1.getToken() == FALSE &&
1566                                operand2.getToken() == FALSE)
1567                        {
1568                            stack.push(SelectorToken.getInstance(FALSE));
1569                        }
1570                        else
1571                        {
1572                            stack.push(SelectorToken.getInstance(UNKNOWN));
1573                        }
1574                        break;
1575                    case AND:
1576                        operand2 = (SelectorToken)stack.pop();
1577                        if (operand1.getToken() == TRUE &&
1578                                operand2.getToken() == TRUE)
1579                        {
1580                            stack.push(SelectorToken.getInstance(TRUE));
1581                        }
1582                        else  if (operand1.getToken() == FALSE ||
1583                                operand2.getToken() == FALSE)
1584                        {
1585                            stack.push(SelectorToken.getInstance(FALSE));
1586                        }
1587                        else
1588                        {
1589                            stack.push(SelectorToken.getInstance(UNKNOWN));
1590                        }
1591                        break;
1592                    case NOT:
1593                        if (operand1.getToken() == TRUE)
1594                        {
1595                            stack.push(SelectorToken.getInstance(FALSE));
1596                        }
1597                        else if (operand1.getToken() == FALSE)
1598                        {
1599                            stack.push(SelectorToken.getInstance(TRUE));
1600                        }
1601                        else
1602                        {
1603                            stack.push(SelectorToken.getInstance(UNKNOWN));
1604                        }
1605                        break;
1606                    case EQUALS:
1607                        operand2 = (SelectorToken)stack.pop();
1608                        
1609                        if (isNumeric(operand1) || isNumeric(operand2))
1610                        {
1611                            stack.push(doNumericOperation(
1612                                    token, operand2, operand1));
1613                        }
1614                        else if (operand1.equals(operand2))
1615                        {
1616                            stack.push(SelectorToken.getInstance(TRUE));
1617                        }
1618                        else
1619                        {
1620                            stack.push(SelectorToken.getInstance(FALSE));
1621                        }
1622                        break;
1623                    case NOT_EQUALS:
1624                        operand2 = (SelectorToken)stack.pop();
1625                        
1626                        if (isNumeric(operand1) || isNumeric(operand2))
1627                        {
1628                            stack.push(doNumericOperation(
1629                                    token, operand2, operand1));
1630                        }
1631                        else if (operand1.equals(operand2))
1632                        {
1633                            stack.push(SelectorToken.getInstance(FALSE));
1634                        }
1635                        else
1636                        {
1637                            stack.push(SelectorToken.getInstance(TRUE));
1638                        }
1639                        break;
1640                        
1641                    case LT:
1642                    case LTE:
1643                    case GT:
1644                    case GTE:
1645                        operand2 = (SelectorToken)stack.pop();
1646                        
1647                        // operand2 is first. It is actually the first
1648                        // operation. They are reversed on the stack
1649                        stack.push(doNumericOperation(
1650                                token, operand2, operand1));
1651                        break;
1652                        
1653                    case PLUS:
1654                    case MINUS:
1655                    case MULTIPLY:
1656                    case DIVIDE:
1657                        operand2 = (SelectorToken)stack.pop();
1658                        stack.push(doNumericOperation(
1659                                token, operand2, operand1));
1660                        break;
1661                        
1662                    case UNARY_MINUS:
1663                        stack.push(doNumericOperation(token, operand1, null));
1664                        break;
1665                        
1666                    case UNARY_PLUS:
1667                        stack.push(doNumericOperation(token, operand1, null));
1668                        break;
1669                        
1670                    case BETWEEN:
1671                    case NOT_BETWEEN:
1672                        // Operand 1 is the second range value
1673                        SelectorToken max = operand1;
1674                        
1675                        // Operand 2 is the first range value
1676                        SelectorToken min = (SelectorToken)stack.pop();
1677                        
1678                        // Operand 3 is the operand on the left side of BETWEEN
1679                        SelectorToken operand = (SelectorToken)stack.pop();
1680                        
1681                        boolean between = false;
1682                        
1683                        // The operands may be floats or longs. We use
1684                        // doNumericOperation to handle this for us
1685                        if (doNumericOperation(SelectorToken.getInstance(GTE),
1686                                operand, min).getToken() == TRUE &&
1687                                doNumericOperation(SelectorToken.getInstance(LTE),
1688                                operand, max).getToken() == TRUE)
1689                        {
1690                            between = true;
1691                        }
1692                        
1693                        if (token.getToken() == BETWEEN)
1694                        {
1695                            if (between)
1696                            {
1697                                stack.push(SelectorToken.getInstance(TRUE));
1698                            }
1699                            else
1700                            {
1701                                stack.push(SelectorToken.getInstance(FALSE));
1702                            }
1703                        }
1704                        else
1705                        {
1706                            if (between)
1707                            {
1708                                stack.push(SelectorToken.getInstance(FALSE));
1709                            }
1710                            else
1711                            {
1712                                stack.push(SelectorToken.getInstance(TRUE));
1713                            }
1714                        }
1715                        break;
1716                        
1717                    case IN:
1718                    case NOT_IN:
1719                        
1720                        // operand2 is the identifier
1721                        operand2 = (SelectorToken)stack.pop();
1722                        
1723                        if (! (operand2.getValue() instanceof String  ))
1724                        {
1725                            throw new SelectorFormatException(
1726                                    "IN requires string operand: " +
1727                                    operand2.getValue(), selector);
1728                        }
1729                        
1730                        // operand1 is the string list
1731                        HashSet   set = (HashSet  )operand1.getValue();
1732                        
1733                        if (operand2.getToken() == UNKNOWN)
1734                        {
1735                            // If operand is unknow, result is unknown.
1736                            stack.push(SelectorToken.getInstance(FALSE));
1737                        }
1738                        else if (set.contains((String  )operand2.getValue()))
1739                        {
1740                            if (token.getToken() == IN)
1741                            {
1742                                stack.push(SelectorToken.getInstance(TRUE));
1743                            }
1744                            else
1745                            {
1746                                stack.push(SelectorToken.getInstance(FALSE));
1747                            }
1748                        }
1749                        else
1750                        {
1751                            if (token.getToken() == IN)
1752                            {
1753                                stack.push(SelectorToken.getInstance(FALSE));
1754                            }
1755                            else
1756                            {
1757                                stack.push(SelectorToken.getInstance(TRUE));
1758                            }
1759                        }
1760                        break;
1761                        
1762                    case LIKE:
1763                    case NOT_LIKE:
1764                        // operand2 is the identifier
1765                        operand2 = (SelectorToken)stack.pop();
1766                        
1767                        if (! (operand2.getValue() instanceof String  ))
1768                        {
1769                            throw new SelectorFormatException(
1770                                    "LIKE requires string operand: " +
1771                                    operand2.getValue(), selector);
1772                        }
1773                        
1774                        // operand1 is the RE
1775                        RegularExpression re =
1776                                (RegularExpression)operand1.getValue();
1777                        
1778                        if (operand2.getToken() == UNKNOWN)
1779                        {
1780                            // If operand is unknow, result is unknown.
1781                            stack.push(SelectorToken.getInstance(FALSE));
1782                        }
1783                        else if (re.match((String  )operand2.getValue()))
1784                        {
1785                            if (token.getToken() == LIKE)
1786                            {
1787                                stack.push(SelectorToken.getInstance(TRUE));
1788                            }
1789                            else
1790                            {
1791                                stack.push(SelectorToken.getInstance(FALSE));
1792                            }
1793                        }
1794                        else
1795                        {
1796                            if (token.getToken() == LIKE)
1797                            {
1798                                stack.push(SelectorToken.getInstance(FALSE));
1799                            }
1800                            else
1801                            {
1802                                stack.push(SelectorToken.getInstance(TRUE));
1803                            }
1804                        }
1805                        break;
1806                        
1807                    case IS_NULL:
1808                        if (operand1.getToken() == UNKNOWN)
1809                        {
1810                            stack.push(SelectorToken.getInstance(TRUE));
1811                        }
1812                        else
1813                        {
1814                            stack.push(SelectorToken.getInstance(FALSE));
1815                        }
1816                        break;
1817                    case IS_NOT_NULL:
1818                        if (operand1.getToken() != UNKNOWN)
1819                        {
1820                            stack.push(SelectorToken.getInstance(TRUE));
1821                        }
1822                        else
1823                        {
1824                            stack.push(SelectorToken.getInstance(FALSE));
1825                        }
1826                        break;
1827                    default:
1828                        throw new SelectorFormatException(
1829                                "Unknown operator: " + token, selector);
1830                }
1831            }
1832            
1833            
1834            // All done!
1835            // The top of the stack better hold a boolean!
1836            token = (SelectorToken)stack.pop();
1837            
1838        }
1839        catch (java.util.EmptyStackException   e)
1840        {
1841            throw new SelectorFormatException("Missing operand", selector);
1842        }
1843        
1844        if (!stack.empty())
1845        {
1846            throw new SelectorFormatException(
1847                    "Missing operator", selector);
1848        }
1849        else if (token.getToken() == TRUE)
1850        {
1851            return true;
1852        }
1853        else if (token.getToken() == FALSE)
1854        {
1855            return false;
1856        }
1857        else if (token.getToken() == UNKNOWN)
1858        {
1859            return false;
1860        }
1861        else
1862        {
1863            throw new SelectorFormatException(
1864                    "Non-boolean expression", selector);
1865        }
1866    }
1867    
1868    private SelectorToken propertyToToken(Object   value)
1869    {
1870        if (value instanceof String  )
1871        {
1872            return SelectorToken.getInstance(STRING, value);
1873        }
1874        else if (value instanceof Boolean  )
1875        {
1876            boolean b = ((Boolean  )value).booleanValue();
1877            if (b)
1878            {
1879                return SelectorToken.getInstance(TRUE);
1880            }
1881            else
1882            {
1883                return SelectorToken.getInstance(FALSE);
1884            }
1885        }
1886        else if (value instanceof Double  )
1887        {
1888            return SelectorToken.getInstance(DOUBLE, value);
1889        }
1890        else if (value instanceof Float  )
1891        {
1892            double d = ((Float  )value).floatValue();
1893            return SelectorToken.getInstance(DOUBLE, new Double  (d));
1894        }
1895        else if (value instanceof Long  )
1896        {
1897            return SelectorToken.getInstance(LONG, value);
1898        }
1899        else if (value instanceof Integer  )
1900        {
1901            long l = ((Integer  )value).intValue();
1902            return SelectorToken.getInstance(LONG, new Long  (l));
1903        }
1904        else if (value instanceof Short  )
1905        {
1906            long l = ((Short  )value).shortValue();
1907            return SelectorToken.getInstance(LONG, new Long  (l));
1908        }
1909        else if (value instanceof Byte  )
1910        {
1911            long l = ((Byte  )value).byteValue();
1912            return SelectorToken.getInstance(LONG, new Long  (l));
1913        }
1914        
1915        return null;
1916    }
1917    
1918    private SelectorToken convertStringToNumber(String   s)
1919    throws SelectorFormatException
1920    {
1921        
1922        try
1923        {
1924            Long   l = Long.valueOf(s);
1925            return SelectorToken.getInstance(LONG, l);
1926        }
1927        catch (NumberFormatException   e)
1928        {
1929            try
1930            {
1931                // Hmmm...maybe it's a double
1932                Double   d = Double.valueOf(s);
1933                return SelectorToken.getInstance(DOUBLE, d);
1934            }
1935            catch (NumberFormatException   e2)
1936            {
1937                throw new SelectorFormatException(
1938                        "Cannot convert string to number '" + s + "'", selector);
1939            }
1940        }
1941    }
1942    
1943    /**
1944     * Perform a numeric operation. God this is lame. There must
1945     * be a better way, but it's late and I'm not thinking well.
1946     *
1947     * The operands are either Long or Double.
1948     */
1949    private SelectorToken doNumericOperation(
1950            SelectorToken t, SelectorToken op1, SelectorToken op2)
1951            throws SelectorFormatException
1952    {
1953        
1954        boolean b = false;
1955        boolean is1L = false;
1956        boolean is2L = false;
1957        long    val1L = 0, val2L = 0;
1958        double  val1D = 0, val2D = 0;
1959        
1960        
1961        if ((!isNumeric(op1) && op1.getToken() != UNKNOWN))
1962        {
1963            if (convertTypes && op1.getToken() == STRING)
1964            {
1965                op1 = convertStringToNumber((String  )op1.getValue());
1966            }
1967            else
1968            {
1969                throw new SelectorFormatException(
1970                        "Non-numeric argument '" + op1.getValue() +
1971                        "'", selector);
1972            }
1973        }
1974        
1975        if (op2 != null && (!isNumeric(op2) && op2.getToken() != UNKNOWN))
1976        {
1977            if (convertTypes && op2.getToken() == STRING)
1978            {
1979                op2 = convertStringToNumber((String  )op2.getValue());
1980            }
1981            else
1982            {
1983                throw new SelectorFormatException(
1984                        "Non-numeric argument '" + op2.getValue() +
1985                        "'", selector);
1986            }
1987        }
1988        
1989        
1990        if (op1.getToken() == UNKNOWN ||
1991                (op2 != null && op2.getToken() == UNKNOWN))
1992        {
1993            // Operation with a UNKNOWN argument is always UNKNOWN
1994            return SelectorToken.getInstance(UNKNOWN);
1995        }
1996        
1997        
1998        if (op1.getValue() instanceof Long  )
1999        {
2000            is1L = true;
2001            val1L = ((Long  )op1.getValue()).longValue();
2002            val1D = ((Long  )op1.getValue()).doubleValue();
2003        }
2004        else
2005        {
2006            is1L = false;
2007            val1L = ((Double  )op1.getValue()).longValue();
2008            val1D = ((Double  )op1.getValue()).doubleValue();
2009        }
2010        
2011        if (op2 != null)
2012        {
2013            if (op2.getValue() instanceof Long  )
2014            {
2015                is2L = true;
2016                val2L = ((Long  )op2.getValue()).longValue();
2017                val2D = ((Long  )op2.getValue()).doubleValue();
2018            }
2019            else
2020            {
2021                is2L = false;
2022                val2L = ((Double  )op2.getValue()).longValue();
2023                val2D = ((Double  )op2.getValue()).doubleValue();
2024            }
2025        }
2026        
2027        switch (t.getToken())
2028        {
2029            case EQUALS:
2030            case NOT_EQUALS:
2031                if (is1L && is2L)
2032                {
2033                    b = val1L == val2L;
2034                }
2035                else if (is1L)
2036                {
2037                    b = val1L == val2D;
2038                }
2039                else if (is2L)
2040                {
2041                    b = val1D == val2L;
2042                }
2043                else
2044                {
2045                    b = val1D == val2D;
2046                }
2047                if (t.getToken() == EQUALS)
2048                {
2049                    return SelectorToken.getInstance(b ? TRUE: FALSE);
2050                }
2051                else
2052                {
2053                    return SelectorToken.getInstance(b ? FALSE: TRUE);
2054                }
2055                
2056            case LT:
2057                if (is1L && is2L)
2058                {
2059                    b = val1L < val2L;
2060                }
2061                else if (is1L)
2062                {
2063                    b = val1L < val2D;
2064                }
2065                else if (is2L)
2066                {
2067                    b = val1D < val2L;
2068                }
2069                else
2070                {
2071                    b = val1D < val2D;
2072                }
2073                return SelectorToken.getInstance(b ? TRUE: FALSE);
2074            case LTE:
2075                if (is1L && is2L)
2076                {
2077                    b = val1L <= val2L;
2078                }
2079                else if (is1L)
2080                {
2081                    b = val1L <= val2D;
2082                }
2083                else if (is2L)
2084                {
2085                    b = val1D <= val2L;
2086                }
2087                else
2088                {
2089                    b = val1D <= val2D;
2090                }
2091                return SelectorToken.getInstance(b ? TRUE: FALSE);
2092            case GT:
2093                if (is1L && is2L)
2094                {
2095                    b = val1L > val2L;
2096                }
2097                else if (is1L)
2098                {
2099                    b = val1L > val2D;
2100                }
2101                else if (is2L)
2102                {
2103                    b = val1D > val2L;
2104                }
2105                else
2106                {
2107                    b = val1D > val2D;
2108                }
2109                return SelectorToken.getInstance(b ? TRUE: FALSE);
2110            case GTE:
2111                if (is1L && is2L)
2112                {
2113                    b = val1L >= val2L;
2114                }
2115                else if (is1L)
2116                {
2117                    b = val1L >= val2D;
2118                }
2119                else if (is2L)
2120                {
2121                    b = val1D >= val2L;
2122                }
2123                else
2124                {
2125                    b = val1D >= val2D;
2126                }
2127                return SelectorToken.getInstance(b ? TRUE: FALSE);
2128            case PLUS:
2129                if (is1L && is2L)
2130                {
2131                    long v = val1L + val2L;
2132                    return SelectorToken.getInstance(LONG, new Long  (v));
2133                }
2134                else
2135                {
2136                    double d = val1D + val2D;
2137                    return SelectorToken.getInstance(DOUBLE, new Double  (d));
2138                }
2139            case UNARY_PLUS:
2140                // Unary plus is a no-op
2141                return(op1);
2142                
2143            case MINUS:
2144                if (is1L && is2L)
2145                {
2146                    long v = val1L - val2L;
2147                    return SelectorToken.getInstance(LONG, new Long  (v));
2148                }
2149                else
2150                {
2151                    double d = val1D - val2D;
2152                    return SelectorToken.getInstance(DOUBLE, new Double  (d));
2153                }
2154            case UNARY_MINUS:
2155                if (is1L)
2156                {
2157                    long v = - val1L;
2158                    return SelectorToken.getInstance(LONG, new Long  (v));
2159                }
2160                else
2161                {
2162                    double d = - val1D;
2163                    return SelectorToken.getInstance(DOUBLE, new Double  (d));
2164                }
2165            case MULTIPLY:
2166                if (is1L && is2L)
2167                {
2168                    long v = val1L * val2L;
2169                    return SelectorToken.getInstance(LONG, new Long  (v));
2170                }
2171                else
2172                {
2173                    double d = val1D * val2D;
2174                    return SelectorToken.getInstance(DOUBLE, new Double  (d));
2175                }
2176            case DIVIDE:
2177                if (is1L && is2L)
2178                {
2179                    long v = val1L / val2L;
2180                    return SelectorToken.getInstance(LONG, new Long  (v));
2181                }
2182                else
2183                {
2184                    double d = val1D / val2D;
2185                    return SelectorToken.getInstance(DOUBLE, new Double  (d));
2186                }
2187            default:
2188                throw new SelectorFormatException(
2189                        "Unknown numeric operation: " + t, selector);
2190        }
2191        
2192    }
2193    
2194    private static boolean isNumeric(SelectorToken t)
2195    {
2196        int tok = t.getToken();
2197        return ((tok == DOUBLE) || (tok == LONG));
2198    }
2199    
2200    private static boolean isOperator(SelectorToken t)
2201    {
2202        return (t.getToken() < 100);
2203    }
2204    
2205    private static boolean isOperator(int t)
2206    {
2207        return (t < 100);
2208    }
2209    
2210    // Return a number representing the precedene of an operator:
2211    //
2212    private static int getPrecedence(SelectorToken t)
2213    {
2214        
2215        switch (t.getToken())
2216        {
2217            
2218            
2219            case OR:
2220                return 10;
2221                
2222            case AND:
2223                return 11;
2224                
2225            case NOT:
2226                return 12;
2227                
2228            case EQUALS:
2229            case NOT_EQUALS:
2230                return 20;
2231                
2232            case LT:
2233            case LTE:
2234            case GT:
2235            case GTE:
2236                return 21;
2237                
2238            case IN:
2239            case NOT_IN:
2240            case LIKE:
2241            case NOT_LIKE:
2242            case IS_NULL:
2243            case IS_NOT_NULL:
2244            case BETWEEN:
2245            case NOT_BETWEEN:
2246                return 30;
2247                
2248            case PLUS:
2249            case MINUS:
2250                return 40;
2251                
2252            case MULTIPLY:
2253            case DIVIDE:
2254                return 41;
2255                
2256            case COMMA:
2257                return 42;
2258                
2259            case UNARY_PLUS:
2260            case UNARY_MINUS:
2261                return 43;
2262                
2263                
2264            case LEFT_PAREN:
2265            case RIGHT_PAREN:
2266                return 50;
2267                
2268                
2269            default:
2270                return 1;
2271        }
2272    }
2273    
2274    /**
2275     * Two Selector instances are equal if they are the same instance
2276     * or if the selector strings match.
2277     */
2278    public boolean equals(Object   o)
2279    {
2280        
2281        // Since we cache Selectors it should be the case that Selectors
2282        // with the same selector string will be the same instance.
2283        if (this == o) return true;
2284        
2285        if (!(o instanceof Selector))
2286        {
2287            return false;
2288        }
2289        
2290        Selector obj = (Selector)o;
2291        return (this.selector.equals(obj.selector));
2292    }
2293    
2294    public int hashCode()
2295    {
2296        /* Return the hashCode for the Selector string */
2297        return selector.hashCode();
2298    }
2299    
2300    public String   toString()
2301    {
2302        return selector;
2303    }
2304    
2305    /**
2306     * Check if the Selector uses properties.
2307     *
2308     * @return  true if the selector expression uses properties
2309     *          false if the selector does not use properties (ie
2310     *          it only uses JMS header fields).
2311     */
2312    public boolean usesProperties()
2313    {
2314        return usesProperties;
2315    }
2316    
2317    /**
2318     * Check if the Selector uses JMS Header Fiedls.
2319     *
2320     * @return  true if the selector expression uses JMS fields.
2321     *          false if the selector does not use JMS fields (ie
2322     *          it only uses JMS properties).
2323     */
2324    public boolean usesFields()
2325    {
2326        return usesFields;
2327    }
2328    
2329    private static void dumpTokens(LinkedList   l)
2330    {
2331        
2332        Iterator   iter = l.iterator();
2333        
2334        while (iter.hasNext())
2335        {
2336            SelectorToken token = (SelectorToken)iter.next();
2337            System.out.print(token.toString());
2338        }
2339        System.out.println();
2340    }
2341    
2342    public String   toDebugString()
2343    {
2344        StringBuffer   sb = new StringBuffer  ();
2345        for (int i = 0; i < compiledSelector.length; i++)
2346        {
2347            if (compiledSelector[i] != null)
2348            {
2349                sb.append(compiledSelector[i].toString());
2350            }
2351        }
2352        return sb.toString() + " cachesize=" + selectorCache.size() ;
2353    }
2354}
2355
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags