Java > Open Source Codes > org > ungoverned > oscar > ldap > Parser


1 /*
2  * Oscar - An implementation of the OSGi framework.
3  * Copyright (c) 2004, Richard S. Hall
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in
14  * the documentation and/or other materials provided with the
15  * distribution.
16  * * Neither the name of the ungoverned.org nor the names of its
17  * contributors may be used to endorse or promote products derived
18  * from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  *
32  * Contact: Richard S. Hall (heavy@ungoverned.org)
33  * Contributor(s):
34  * Dennis Heimbigner
35  * Humberto Cervantes
36  *
37 **/
38 package org.ungoverned.oscar.ldap;
39
40 import java.io.IOException ;
41 import java.io.PrintStream ;
42 import java.math.BigDecimal ;
43 import java.math.BigInteger ;
44 import java.util.*;
45 import java.util.List ;
46 import java.util.ArrayList ;
47 import java.util.Stack ;
48
49 public class Parser
50 {
51     //
52 // Parser contants.
53 //
54
55     // End of file.
56 public static final int EOF = -1;
57
58     // Special characters in parse
59 public static final char LPAREN = '(';
60     public static final char RPAREN = ')';
61     public static final char STAR = '*';
62
63     // Define the list of legal leading and trailing
64 // characters in an attribute name.
65 public static final String ATTRIBUTECHARS0 =
66         ".abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";
67     // Define the list of legal internal characters in an attribute name.
68 public static final String ATTRIBUTECHARS1 =
69         ".abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_ ";
70
71     // Define an enum for substring procedure
72 public static final int SIMPLE = 0;
73     public static final int PRESENT = 1;
74     public static final int SUBSTRING = 2;
75
76     // different from =|>|<|~
77 public static final int NOOP = 0;
78
79     // Comparison operators.
80 public static final int EQUAL = 0;
81     public static final int GREATER_EQUAL = 1;
82     public static final int LESS_EQUAL = 2;
83     public static final int APPROX = 3;
84
85     // Criteria in % to accept something as approximate.
86 public static final int APPROX_CRITERIA = 10;
87
88     // Flag indicating presense of BigInteger/Decimal.
89 private static boolean m_hasBigNumbers = false;
90
91     static
92     {
93         try
94         {
95             Class.forName("java.math.BigDecimal");
96             m_hasBigNumbers = true;
97         }
98         catch (Exception ex)
99         {
100             // Ignore.
101 }
102     }
103     //
104 // Instance variables.
105 //
106
107     private LdapLexer lexer = null;
108     private List program;
109
110     public Parser()
111     {
112         reset();
113     }
114
115     public Parser(LdapLexer l)
116     {
117         reset(l);
118     }
119
120     public void reset()
121     {
122         lexer = null;
123         if (program == null)
124         {
125             program = new ArrayList ();
126         }
127         program.clear();
128     }
129
130     public void reset(LdapLexer l)
131     {
132         reset();
133         lexer = l;
134     }
135
136     public Object [] getProgram()
137     {
138         return program.toArray(new Object [program.size()]);
139     }
140
141     // Define the recursive descent procedures
142
143     /*
144     <start>::= <filter> <EOF>
145     */
146     public boolean start() throws ParseException, IOException
147     {
148         boolean ok = filter();
149         if (!ok)
150         {
151             return ok;
152         }
153         int ch = lexer.get();
154         if (ch != EOF)
155         {
156             throw new ParseException(
157                 "expected <EOF>; found '" + ((char) ch) + "'");
158         }
159         return ok;
160     }
161
162     /*
163     <filter> ::= '(' <filtercomp> ')'
164      */
165     boolean filter() throws ParseException, IOException
166     {
167         debug("filter");
168         if (lexer.peeknw() != LPAREN)
169         {
170             return false;
171         }
172         lexer.get();
173         if (!filtercomp())
174         {
175             throw new ParseException("expected filtercomp");
176         }
177         if (lexer.getnw() != RPAREN)
178         {
179             throw new ParseException("expected )");
180         }
181         return true;
182     }
183
184     /*
185     <filtercomp> ::= <and> | <or> | <not> | <item>
186     <and> ::= '&' <filterlist>
187     <or> ::= '|' <filterlist>
188     <not> ::= '!' <filter>
189     */
190     boolean filtercomp() throws ParseException, IOException
191     {
192         debug("filtercomp");
193         int c = lexer.peeknw();
194         switch (c)
195         {
196             case '&' :
197             case '|' :
198                 lexer.get();
199                 int cnt = filterlist();
200                 if (cnt == 0)
201                 {
202                     return false;
203                 }
204                 // Code: [And|Or](cnt)
205 program.add(
206                     c == '&'
207                         ? (Operator) new AndOperator(cnt)
208                         : (Operator) new OrOperator(cnt));
209                 return true;
210             case '!' :
211                 lexer.get();
212                 if (!filter())
213                 {
214                     return false;
215                 }
216                 // Code: Not()
217 program.add(new NotOperator());
218                 return true;
219             case EOF :
220                 return false;
221             default :
222                 // check for key
223 if (ATTRIBUTECHARS0.indexOf(c) <= 0)
224                 {
225                     return false;
226                 }
227                 boolean b = item();
228                 return b;
229         }
230     }
231
232     /*
233     <filterlist> ::= <filter> | <filter> <filterlist>
234     */
235     int filterlist() throws ParseException, IOException
236     {
237         debug("filterlist");
238         int cnt = 0;
239         if (filter())
240         {
241             do
242             {
243                 cnt++;
244             }
245             while (filter());
246         }
247         return (cnt);
248     }
249
250     /*
251     <item> ::= <simple> | <present> | <substring>
252     <simple> ::= <attr> <filtertype> <value>
253     <filtertype> ::= <equal> | <approx> | <greater> | <less>
254     <present> ::= <attr> '=*'
255     <substring> ::= <attr> '=' <initial> <any> <final>
256     */
257     boolean item() throws ParseException, IOException
258     {
259         debug("item");
260
261         StringBuffer attr = new StringBuffer ();
262         if (!attribute(attr))
263         {
264             return false;
265         }
266
267         lexer.skipwhitespace(); // assume allowable before equal operator
268 // note: I treat the =* case as = followed by a special substring
269 int op = equalop();
270         if (op == NOOP)
271         {
272             String oplist = "=|~=|>=|<=";
273             throw new ParseException("expected " + oplist);
274         }
275         ArrayList pieces = new ArrayList ();
276         int kind = substring(pieces);
277         // Get some of the illegal cases out of the way
278 if (op != '=' && kind != SIMPLE)
279         {
280             // We assume that only the = operator can work
281 // with right sides containing stars. If not correct
282 // then this code must change.
283 throw new ParseException("expected value|substring|*");
284         }
285
286         switch (kind)
287         {
288             case SIMPLE :
289                 // Code: Push(attr); Constant(pieces.get(0)); <operator>();
290 program.add(new PushOperator(attr.toString()));
291                 program.add(new ConstOperator(pieces.get(0)));
292                 switch (op)
293                 {
294                     case '<' :
295                         program.add(new LessEqualOperator());
296                         break;
297                     case '>' :
298                         program.add(new GreaterEqualOperator());
299                         break;
300                     case '~' :
301                         program.add(new ApproxOperator());
302                         break;
303                     case '=' :
304                     default :
305                         program.add(new EqualOperator());
306                 }
307                 break;
308             case PRESENT :
309                 // Code: Present(attr);
310 program.add(new PresentOperator(attr.toString()));
311                 break;
312             case SUBSTRING :
313                 generateSubStringCode(attr.toString(), pieces);
314                 break;
315             default :
316                 throw new ParseException("expected value|substring|*");
317         }
318         return true;
319     }
320
321     // Generating code for substring right side is mildly
322 // complicated.
323
324     void generateSubStringCode(String attr, ArrayList pieces)
325     {
326         // Code: Push(attr)
327 program.add(new PushOperator(attr.toString()));
328
329         // Convert the pieces arraylist to a String[]
330 String [] list =
331             (String []) pieces.toArray(new String [pieces.size()]);
332
333         // Code: SubString(list)
334 program.add(new SubStringOperator(list));
335     }
336
337     /*
338     <attr> is a string representing an attributte,
339     or key, in the properties
340     objects of the registered services. Attribute names are not case
341     sensitive; that is cn and CN both refer to the same attribute.
342     Attribute names may have embedded spaces, but not leading or
343     trailing spaces.
344     */
345     boolean attribute(StringBuffer buf) throws ParseException, IOException
346     {
347         debug("attribute");
348         lexer.skipwhitespace();
349         buf.setLength(0);
350         int c = lexer.peek(); // need to make sure there
351 // is at least one KEYCHAR
352 if (c == EOF)
353         {
354             return false;
355         }
356         if (ATTRIBUTECHARS0.indexOf(c) < 0)
357         {
358             return false;
359         }
360
361         do
362         {
363             buf.append((char) lexer.get());
364         }
365         while (ATTRIBUTECHARS1.indexOf(lexer.peek()) >= 0);
366
367         // The above may have accumulated trailing blanks that must be removed
368 int i = buf.length() - 1;
369         while (i > 0 && buf.charAt(i) == ' ')
370         {
371             i--;
372         }
373         buf.setLength(i + 1);
374         return true;
375     }
376
377     /*
378        <equal> ::= '='
379        <approx> ::= '~='
380        <greater> ::= '>='
381        <less> ::= '<='
382        <present> ::= <attr> '=*'
383     */
384     int equalop() throws ParseException, IOException
385     {
386         debug("equalop");
387         lexer.skipwhitespace();
388         int op = lexer.peek();
389         switch (op)
390         {
391             case '=' :
392                 lexer.get();
393                 break;
394             case '~' :
395             case '<' :
396             case '>' :
397                 // skip main operator char
398 int c = lexer.get();
399                 // make sure that the next char is '='
400 c = lexer.get();
401                 if (c != '=')
402                 {
403                     throw new ParseException("expected ~=|>=|<=");
404                 }
405                 break;
406             default :
407                 op = NOOP;
408         }
409         return op;
410     }
411
412     /*
413     <substring> ::= <attr> '=' <initial> <any> <final>
414     <initial> ::= NULL | <value>
415     <any> ::= '*' <starval>
416     <starval> ::= NULL | <value> '*' <starval>
417     <final> ::= NULL | <value>
418     <value> ::= ...
419     */
420     /*
421     This procedure handles all cases on right side of an item
422     */
423     int substring(ArrayList pieces) throws ParseException, IOException
424     {
425         debug("substring");
426
427         pieces.clear();
428         StringBuffer ss = new StringBuffer ();
429         // int kind = SIMPLE; // assume until proven otherwise
430 boolean wasStar = false; // indicates last piece was a star
431 boolean leftstar = false; // track if the initial piece is a star
432 boolean rightstar = false; // track if the final piece is a star
433
434         // We assume (sub)strings can contain leading and trailing blanks
435 loop: for (;;)
436         {
437             int c = lexer.peek();
438             switch (c)
439             {
440                 case RPAREN :
441                     if (wasStar)
442                     {
443                         // insert last piece as "" to handle trailing star
444 rightstar = true;
445                     }
446                     else
447                     {
448                         pieces.add(ss.toString());
449                         // accumulate the last piece
450 // note that in the case of
451 // (cn=); this might be
452 // the string "" (!=null)
453 }
454                     ss.setLength(0);
455                     break loop;
456                 case '\\' :
457                     wasStar = false;
458                     lexer.get();
459                     c = lexer.get();
460                     if (c != EOF)
461                     {
462                         throw new ParseException("unexpected EOF");
463                     }
464                     ss.append((char) c);
465                     break;
466                 case EOF :
467                     if (pieces.size() > 0)
468                     {
469                         throw new ParseException("expected ')'");
470                     }
471                     else
472                     {
473                         throw new ParseException("expected value|substring");
474                     }
475                 case '*' :
476                     if (wasStar)
477                     {
478                         // encountered two successive stars;
479 // I assume this is illegal
480 throw new ParseException("unexpected '**'");
481                     }
482                     lexer.get();
483                     if (ss.length() > 0)
484                     {
485                         pieces.add(ss.toString()); // accumulate the pieces
486 // between '*' occurrences
487 }
488                     ss.setLength(0);
489                     // if this is a leading star, then track it
490 if (pieces.size() == 0)
491                     {
492                         leftstar = true;
493                     }
494                     ss.setLength(0);
495                     wasStar = true;
496                     break;
497                 default :
498                     wasStar = false;
499                     ss.append((char) lexer.get());
500             }
501         }
502         if (pieces.size() == 0)
503         {
504             return PRESENT;
505         }
506         if (leftstar || rightstar || pieces.size() > 1)
507         {
508             // insert leading and/or trailing "" to anchor ends
509 if (rightstar)
510             {
511                 pieces.add("");
512             }
513             if (leftstar)
514             {
515                 pieces.add(0, "");
516             }
517             return SUBSTRING;
518         }
519         // assert !leftstar && !rightstar && pieces.size == 1
520 return SIMPLE;
521     }
522
523     // Debug stuff
524
525     static boolean debug = false;
526
527     PrintStream dbgout = null;
528
529     public void setDebug(PrintStream out)
530     {
531         debug = true;
532         dbgout = out;
533     }
534
535     void debug(String proc)
536     {
537         if (!debug || dbgout == null)
538         {
539             return;
540         }
541         dbgout.println("parsing " + proc + ":" + lexer.charno());
542         dbgout.flush();
543     }
544
545     // Exclusive inner classes
546
547     private static class AndOperator extends Operator
548     {
549         private int operandCount;
550
551         public AndOperator(int opcnt)
552         {
553             operandCount = opcnt;
554         }
555
556         public void execute(Stack operands, Mapper mapper)
557             throws EvaluationException
558         {
559             // Determine result using short-circuit evaluation.
560 boolean result = true;
561             for (int i = 0; i < operandCount; i++)
562             {
563                 if (operands.empty())
564                 {
565                     fewOperands("AND");
566                 }
567
568                 // For short-circuited evaluation, once the AND
569 // becomes false, we can ignore the remaining
570 // expressions, but we must still pop them off.
571 if (!result)
572                 {
573                     operands.pop();
574                 }
575                 else
576                 {
577                     result = ((Boolean ) operands.pop()).booleanValue();
578                 }
579             }
580             operands.push(new Boolean (result));
581         }
582
583         public String toString()
584         {
585             return "&(" + operandCount + ")";
586         }
587
588         public void buildTree(Stack operands)
589         {
590             children = new Operator[operandCount];
591             // need to preserve stack order
592 for (int i = 0; i < operandCount; i++)
593             {
594                 children[(operandCount - 1) - i] =
595                     (Operator) operands.pop();
596             }
597             operands.push(this);
598         }
599
600         public void toStringInfix(StringBuffer b)
601         {
602             b.append("(&");
603             for (int i = 0; i < children.length; i++)
604             {
605                 Operator o = (Operator) children[i];
606                 o.toStringInfix(b);
607             }
608             b.append(")");
609         }
610     }
611
612     private static class OrOperator extends Operator
613     {
614         private int operandCount;
615
616         public OrOperator(int opcnt)
617         {
618             operandCount = opcnt;
619         }
620
621         public void execute(Stack operands, Mapper mapper)
622             throws EvaluationException
623         {
624             // Determine result using short-circuit evaluation.
625 boolean result = false;
626             for (int i = 0; i < operandCount; i++)
627             {
628                 if (operands.empty())
629                 {
630                     fewOperands("OR");
631                 }
632
633                 // For short-circuited evaluation, once the OR
634 // becomes true, we can ignore the remaining
635 // expressions, but we must still pop them off.
636 if (result)
637                 {
638                     operands.pop();
639                 }
640                 else
641                 {
642                     result = ((Boolean ) operands.pop()).booleanValue();
643                 }
644             }
645             operands.push(new Boolean (result));
646         }
647
648         public String toString()
649         {
650             return "|(" + operandCount + ")";
651         }
652
653         public void buildTree(Stack operands)
654         {
655             children = new Operator[operandCount];
656             // need to preserve stack order
657 for (int i = 0; i < operandCount; i++)
658             {
659                 children[(operandCount - 1) - i] =
660                     (Operator) operands.pop();
661             }
662             operands.push(this);
663         }
664
665         public void toStringInfix(StringBuffer b)
666         {
667             b.append("(|");
668             for (int i = 0; i < children.length; i++)
669             {
670                 Operator o = (Operator) children[i];
671                 o.toStringInfix(b);
672             }
673             b.append(")");
674         }
675     }
676
677     private static class NotOperator extends Operator
678     {
679         public NotOperator()
680         {
681         }
682
683         public void execute(Stack operands, Mapper mapper)
684             throws EvaluationException
685         {
686             if (operands.empty())
687             {
688                 fewOperands("NOT");
689             }
690             boolean result = !((Boolean ) operands.pop()).booleanValue();
691             operands.push(new Boolean (result));
692         }
693
694         public String toString()
695         {
696             return "!()";
697         }
698
699         public void buildTree(Stack operands)
700         {
701             children = new Operator[1];
702             children[0] = (Operator) operands.pop();
703             operands.push(this);
704         }
705
706         public void toStringInfix(StringBuffer b)
707         {
708             b.append("(!");
709             for (int i = 0; i < children.length; i++)
710             {
711                 Operator o = (Operator) children[i];
712                 o.toStringInfix(b);
713             }
714             b.append(")");
715         }
716     }
717
718     private static class EqualOperator extends Operator
719     {
720         public EqualOperator()
721         {
722         }
723
724         public void execute(Stack operands, Mapper mapper)
725             throws EvaluationException
726         {
727             if (operands.empty())
728             {
729                 fewOperands("=");
730             }
731
732             // We cheat and use the knowledge that top (right) operand
733 // will always be a string because of the way code was generated
734 String rhs = (String ) operands.pop();
735             if (operands.empty())
736             {
737                 fewOperands("=");
738             }
739
740             Object lhs = operands.pop();
741
742             operands.push(new Boolean (compare(lhs, rhs, EQUAL)));
743         }
744
745         public String toString()
746         {
747             return "=()";
748         }
749
750         public void buildTree(Stack operands)
751         {
752             children = new Operator[2];
753             // need to preserve stack order
754 for (int i = 0; i < 2; i++)
755             {
756                 Operator o = (Operator) operands.pop();
757                 children[1 - i] = o;
758             }
759             operands.push(this);
760         }
761
762         public void toStringInfix(StringBuffer b)
763         {
764             b.append("(");
765             for (int i = 0; i < children.length; i++)
766             {
767                 Operator o = (Operator) children[i];
768                 if (i > 0)
769                 {
770                     b.append("=");
771                 }
772                 o.toStringInfix(b);
773             }
774             b.append(")");
775         }
776     }
777
778     private static class GreaterEqualOperator extends Operator
779     {
780         public GreaterEqualOperator()
781         {
782         }
783
784         public void execute(Stack operands, Mapper mapper)
785             throws EvaluationException
786         {
787             if (operands.empty())
788             {
789                 fewOperands(">=");
790             }
791             // We cheat and use the knowledge that top (right) operand
792 // will always be a string because of the way code was generated
793 String rhs = (String ) operands.pop();
794             if (operands.empty())
795             {
796                 fewOperands(">=");
797             }
798             Object lhs = operands.pop();
799
800             operands.push(new Boolean (compare(lhs, rhs, GREATER_EQUAL)));
801         }
802
803         public String toString()
804         {
805             return ">=()";
806         }
807
808         public void buildTree(Stack operands)
809         {
810             children = new Operator[2];
811             // need to preserve stack order
812 for (int i = 0; i < 2; i++)
813             {
814                 children[1 - i] = (Operator) operands.pop();
815             }
816             operands.push(this);
817         }
818
819         public void toStringInfix(StringBuffer b)
820         {
821             b.append("(");
822             for (int i = 0; i < children.length; i++)
823             {
824                 Operator o = (Operator) children[i];
825                 if (i > 0)
826                 {
827                     b.append(">=");
828                 }
829                 o.toStringInfix(b);
830             }
831             b.append(")");
832         }
833     }
834
835     private static class LessEqualOperator extends Operator
836     {
837         public LessEqualOperator()
838         {
839         }
840
841         public void execute(Stack operands, Mapper mapper)
842             throws EvaluationException
843         {
844             if (operands.empty())
845             {
846                 fewOperands("<=");
847             }
848             // We cheat and use the knowledge that top (right) operand
849 // will always be a string because of the way code was generated
850 String rhs = (String ) operands.pop();
851             if (operands.empty())
852             {
853                 fewOperands("<=");
854             }
855             Object lhs = (Object ) operands.pop();
856             operands.push(new Boolean (compare(lhs, rhs, LESS_EQUAL)));
857         }
858
859         public String toString()
860         {
861             return "<=()";
862         }
863
864         public void buildTree(Stack operands)
865         {
866             children = new Operator[2];
867             // need to preserve stack order
868 for (int i = 0; i < 2; i++)
869             {
870                 children[1 - i] = (Operator) operands.pop();
871             }
872             operands.push(this);
873         }
874
875         public void toStringInfix(StringBuffer b)
876         {
877             b.append("(");
878             for (int i = 0; i < children.length; i++)
879             {
880                 Operator o = (Operator) children[i];
881                 if (i > 0)
882                 {
883                     b.append("<=");
884                 }
885                 o.toStringInfix(b);
886             }
887             b.append(")");
888         }
889     }
890
891     private static class ApproxOperator extends Operator
892     {
893         public ApproxOperator()
894         {
895         }
896
897         public void execute(Stack operands, Mapper mapper)
898             throws EvaluationException
899         {
900             if (operands.empty())
901             {
902                 fewOperands("~=");
903             }
904             // We cheat and use the knowledge that top (right) operand
905 // will always be a string because of the way code was generated
906 String rhs = (String ) operands.pop();
907             if (operands.empty())
908             {
909                 fewOperands("~=");
910             }
911             Object lhs = operands.pop();
912             operands.push(new Boolean (compare(lhs, rhs, APPROX)));
913         }
914
915         public String toString()
916         {
917             return "~=()";
918         }
919
920         public void buildTree(Stack operands)
921         {
922             children = new Operator[2];
923             // need to preserve stack order
924 for (int i = 0; i < 2; i++)
925             {
926                 children[1 - i] = (Operator) operands.pop();
927             }
928             operands.push(this);
929         }
930
931         public void toStringInfix(StringBuffer b)
932         {
933             b.append("(");
934             for (int i = 0; i < children.length; i++)
935             {
936                 Operator o = (Operator) children[i];
937                 if (i > 0)
938                 {
939                     b.append("~=");
940                 }
941                 o.toStringInfix(b);
942             }
943             b.append(")");
944         }
945     }
946
947     private static class PresentOperator extends Operator
948     {
949         String attribute;
950
951         public PresentOperator(String attribute)
952         {
953             this.attribute = attribute;
954         }
955
956         public void execute(Stack operands, Mapper mapper)
957             throws EvaluationException
958         {
959             Object value = mapper.lookup(attribute);
960             operands.push(new Boolean (value != null));
961         }
962
963         public String toString()
964         {
965             return attribute + "=*";
966         }
967
968         public void buildTree(Stack operands)
969         {
970             operands.push(this);
971         }
972
973         public void toStringInfix(StringBuffer b)
974         {
975             b.append("(");
976             b.append(attribute + "=*");
977             b.append(")");
978         }
979     }
980
981     private static class PushOperator extends Operator
982     {
983         String attribute;
984
985         public PushOperator(String attribute)
986         {
987             this.attribute = attribute;
988         }
989
990         public void execute(Stack operands, Mapper mapper)
991             throws EvaluationException
992         {
993             // find and push the value of a given attribute
994 Object value = mapper.lookup(attribute);
995             if (value == null)
996             {
997                 throw new AttributeNotFoundException(
998                     "attribute " + attribute + " not found");
999             }
1000            operands.push(value);
1001        }
1002
1003        public String toString()
1004        {
1005            return "push(" + attribute + ")";
1006        }
1007
1008        public String toStringInfix()
1009        {
1010            return attribute;
1011        }
1012
1013        public void buildTree(Stack operands)
1014        {
1015            operands.push(this);
1016        }
1017
1018        public void toStringInfix(StringBuffer b)
1019        {
1020            b.append(attribute);
1021        }
1022    }
1023
1024    private static class ConstOperator extends Operator
1025    {
1026        Object val;
1027
1028        public ConstOperator(Object val)
1029        {
1030            this.val = val;
1031        }
1032
1033        public void execute(Stack operands, Mapper mapper)
1034            throws EvaluationException
1035        {
1036            operands.push(val);
1037        }
1038
1039        public String toString()
1040        {
1041            return "const(" + val + ")";
1042        }
1043
1044        public String toStringInfix()
1045        {
1046            return val.toString();
1047        }
1048
1049        public void buildTree(Stack operands)
1050        {
1051            operands.push(this);
1052        }
1053
1054        public void toStringInfix(StringBuffer b)
1055        {
1056            b.append(val.toString());
1057        }
1058    }
1059
1060    private static class SubStringOperator extends Operator
1061        implements OperatorConstants
1062    {
1063        String [] pieces;
1064
1065        public SubStringOperator(String [] pieces)
1066        {
1067            this.pieces = pieces;
1068        }
1069
1070        public void execute(Stack operands, Mapper mapper)
1071            throws EvaluationException
1072        {
1073            if (operands.empty())
1074            {
1075                fewOperands("SUBSTRING");
1076            }
1077
1078            Object op = operands.pop();
1079
1080            // The operand can either be a string or an array of strings.
1081 if (op instanceof String )
1082            {
1083                operands.push(check((String ) op));
1084            }
1085            else if (op instanceof String [])
1086            {
1087                // If one element of the array matches, then push true.
1088 String [] ops = (String []) op;
1089                boolean result = false;
1090                for (int i = 0; !result && (i < ops.length); i++)
1091                {
1092                    if (check(ops[i]) == Boolean.TRUE)
1093                    {
1094                        result = true;
1095                    }
1096                }
1097
1098                operands.push((result) ? Boolean.TRUE : Boolean.FALSE);
1099            }
1100            else
1101            {
1102                unsupportedType("SUBSTRING", op.getClass());
1103            }
1104        }
1105
1106        private Boolean check(String s)
1107        {
1108            // Walk the pieces to match the string
1109 // There are implicit stars between each piece,
1110 // and the first and last pieces might be "" to anchor the match.
1111 // assert (pieces.length > 1)
1112 // minimal case is <string>*<string>
1113
1114            Boolean result = Boolean.FALSE;
1115            int len = pieces.length;
1116
1117            loop : for (int i = 0; i < len; i++)
1118            {
1119                String piece = (String ) pieces[i];
1120                int index = 0;
1121                if (i == len - 1)
1122                {
1123                    // this is the last piece
1124 if (s.endsWith(piece))
1125                    {
1126                        result = Boolean.TRUE;
1127                    }
1128                    else
1129                    {
1130                        result = Boolean.FALSE;
1131                    }
1132                    break loop;
1133                }
1134                // initial non-star; assert index == 0
1135 else if (i == 0)
1136                {
1137                    if (!s.startsWith(piece))
1138                    {
1139                        result = Boolean.FALSE;
1140                        break loop;
1141                    }
1142                }
1143                // assert i > 0 && i < len-1
1144 else
1145                {
1146                    // Sure wish stringbuffer supported e.g. indexOf
1147 index = s.indexOf(piece, index);
1148                    if (index < 0)
1149                    {
1150                        result = Boolean.FALSE;
1151                        break loop;
1152                    }
1153                }
1154                // start beyond the matching piece
1155 index += piece.length();
1156            }
1157
1158            return result;
1159        }
1160
1161        public String toString()
1162        {
1163            StringBuffer b = new StringBuffer ();
1164            b.append("substring(");
1165            for (int i = 0; i < pieces.length; i++)
1166            {
1167                String piece = pieces[i];
1168                if (i > 0)
1169                {
1170                    b.append("*");
1171                }
1172                b.append(escape(piece));
1173            }
1174            b.append(")");
1175            return b.toString();
1176        }
1177
1178        public String escape(String s)
1179        {
1180            int len = s.length();
1181            StringBuffer buf = new StringBuffer (len);
1182            for (int i = 0; i < len; i++)
1183            {
1184                char c = s.charAt(i);
1185                if (c == ')' || c == '*')
1186                    buf.append('\\');
1187                buf.append(c);
1188            }
1189            return buf.toString();
1190        }
1191
1192        public void buildTree(Stack operands)
1193        {
1194            children = new Operator[1];
1195            children[0] = (Operator) operands.pop();
1196            operands.push(this);
1197        }
1198
1199        public void toStringInfix(StringBuffer b)
1200        {
1201            b.append("(");
1202            children[0].toStringInfix(b); // dump attribute
1203 b.append("=");
1204            for (int i = 0; i < pieces.length; i++)
1205            {
1206                String piece = (String ) pieces[i];
1207                if (i > 0)
1208                {
1209                    b.append("*");
1210                }
1211                b.append(piece);
1212            }
1213            b.append(")");
1214        }
1215    }
1216
1217    // Utility classes and Interfaces
1218
1219    private interface OperatorConstants
1220    {
1221        static final int SSINIT = 0;
1222        static final int SSFINAL = 1;
1223        static final int SSMIDDLE = 2;
1224        static final int SSANY = 3;
1225    }
1226
1227    /**
1228     * Compare two operands in an expression with respect
1229     * to the following operators =, <=, >= and ~=
1230     *
1231     * Example: value=100
1232     *
1233     * @param lhs an object that implements comparable or an array of
1234     * objects that implement comparable.
1235     * @param rhs a string representing the right operand.
1236     * @param operator an integer that represents the operator.
1237     * @return <tt>true</tt> or <tt>false</tt> according to the evaluation.
1238     * @throws EvaluationException if it is not possible to do the comparison.
1239    **/
1240    public static boolean compare(Object lhs, String rhs, int operator)
1241        throws EvaluationException
1242    {
1243        // Determine class of LHS.
1244 Class lhsClass = null;
1245
1246        // If LHS is an array, then call compare() on each element
1247 // of the array until a match is found.
1248 if (lhs.getClass().isArray())
1249        {
1250            // First, if this is an array of primitives, then convert
1251 // the entire array to an array of the associated
1252 // primitive wrapper class instances.
1253 if (lhs.getClass().getComponentType().isPrimitive())
1254            {
1255                lhs = convertPrimitiveArray(lhs);
1256            }
1257
1258            // Now call compare on each element of array.
1259 Object [] array = (Object []) lhs;
1260            for (int i = 0; i < array.length; i++)
1261            {
1262                if (compare(array[i], rhs, operator))
1263                {
1264                    return true;
1265                }
1266            }
1267        }
1268        // If LHS is a vector, then call compare() on each element
1269 // of the vector until a match is found.
1270 else if (lhs instanceof Vector)
1271        {
1272            for (Enumeration e = ((Vector) lhs).elements(); e.hasMoreElements();)
1273            {
1274                if (compare(e.nextElement(), rhs, operator))
1275                {
1276                    return true;
1277                }
1278            }
1279        }
1280        else
1281        {
1282            // Get the class of LHS.
1283 lhsClass = lhs.getClass();
1284
1285            // At this point we are expecting the LHS to be a comparable,
1286 // but Boolean is a special case since it is the only primitive
1287 // wrapper class that does not implement comparable; deal with
1288 // Boolean separately.
1289 if (lhsClass == Boolean .class)
1290            {
1291                return compareBoolean(lhs, rhs, operator);
1292            }
1293        
1294            // If LHS is not a Boolean, then verify it is a comparable
1295 // and perform comparison.
1296 if (!(Comparable .class.isAssignableFrom(lhsClass)))
1297            {
1298                String opName = null;
1299                switch (operator)
1300                {
1301                    case EQUAL :
1302                        opName = "=";
1303                    case GREATER_EQUAL :
1304                        opName = ">=";
1305                    case LESS_EQUAL :
1306                        opName = "<=";
1307                    case APPROX:
1308                        opName = "~=";
1309                    default:
1310                        opName = "UNKNOWN OP";
1311                }
1312
1313                unsupportedType(opName, lhsClass);
1314            }
1315
1316            // We will try to create a comparable object from the
1317 // RHS string.
1318 Comparable rhsComparable = null;
1319            try
1320            {
1321                // We are expecting to be able to construct a comparable
1322 // instance from the RHS string by passing it into the
1323 // constructor of the corresponing comparable class. The
1324 // Character class is a special case, since its constructor
1325 // does not take a string, so handle it separately.
1326 if (lhsClass == Character .class)
1327                {
1328                    rhsComparable = new Character (rhs.charAt(0));
1329                }
1330                else
1331                {
1332                    rhsComparable = (Comparable ) lhsClass
1333                        .getConstructor(new Class [] { String .class })
1334                            .newInstance(new Object [] { rhs });
1335                }
1336            }
1337            catch (Exception ex)
1338            {
1339                String msg = (ex.getCause() == null)
1340                    ? ex.toString() : ex.getCause().toString();
1341                throw new EvaluationException(
1342                    "Could not instantiate class "
1343                        + lhsClass.getName()
1344                        + " with constructor String parameter "
1345                        + rhs + " " + msg);
1346            }
1347
1348            Comparable lhsComparable = (Comparable ) lhs;
1349
1350            switch (operator)
1351            {
1352                case EQUAL :
1353                    return (lhsComparable.compareTo(rhsComparable) == 0);
1354                case GREATER_EQUAL :
1355                    return (lhsComparable.compareTo(rhsComparable) >= 0);
1356                case LESS_EQUAL :
1357                    return (lhsComparable.compareTo(rhsComparable) <= 0);
1358                case APPROX:
1359                    return compareToApprox(lhsComparable, rhsComparable);
1360                default:
1361                    throw new EvaluationException("Unknown comparison operator..."
1362                        + operator);
1363            }
1364        }
1365
1366        return false;
1367    }
1368
1369    /**
1370     * This is an ugly utility method to convert an array of primitives
1371     * to an array of primitive wrapper objects. This method simplifies
1372     * processing LDAP filters since the special case of primitive arrays
1373     * can be ignored.
1374     * @param array
1375     * @return
1376    **/
1377    private static Object [] convertPrimitiveArray(Object array)
1378    {
1379        Class clazz = array.getClass().getComponentType();
1380
1381        if (clazz == Boolean.TYPE)
1382        {
1383            boolean[] src = (boolean[]) array;
1384            array = new Boolean [src.length];
1385            for (int i = 0; i < src.length; i++)
1386            {
1387                ((Object []) array)[i] = new Boolean (src[i]);
1388            }
1389        }
1390        else if (clazz == Character.TYPE)
1391        {
1392            char[] src = (char[]) array;
1393            array = new Character [src.length];
1394            for (int i = 0; i < src.length; i++)
1395            {
1396                ((Object []) array)[i] = new Character (src[i]);
1397            }
1398        }
1399        else if (clazz == Byte.TYPE)
1400        {
1401            byte[] src = (byte[]) array;
1402            array = new Byte [src.length];
1403            for (int i = 0; i < src.length; i++)
1404            {
1405                ((Object []) array)[i] = new Byte (src[i]);
1406            }
1407        }
1408        else if (clazz == Short.TYPE)
1409        {
1410            byte[] src = (byte[]) array;
1411            array = new Byte [src.length];
1412            for (int i = 0; i < src.length; i++)
1413            {
1414                ((Object []) array)[i] = new Byte (src[i]);
1415            }
1416        }
1417        else if (clazz == Integer.TYPE)
1418        {
1419            int[] src = (int[]) array;
1420            array = new Integer [src.length];
1421            for (int i = 0; i < src.length; i++)
1422            {
1423                ((Object []) array)[i] = new Integer (src[i]);
1424            }
1425        }
1426        else if (clazz == Long.TYPE)
1427        {
1428            long[] src = (long[]) array;
1429            array = new Long [src.length];
1430            for (int i = 0; i < src.length; i++)
1431            {
1432                ((Object []) array)[i] = new Long (src[i]);
1433            }
1434        }
1435        else if (clazz == Float.TYPE)
1436        {
1437            float[] src = (float[]) array;
1438            array = new Float [src.length];
1439            for (int i = 0; i < src.length; i++)
1440            {
1441                ((Object []) array)[i] = new Float (src[i]);
1442            }
1443        }
1444        else if (clazz == Double.TYPE)
1445        {
1446            double[] src = (double[]) array;
1447            array = new Double [src.length];
1448            for (int i = 0; i < src.length; i++)
1449            {
1450                ((Object []) array)[i] = new Double (src[i]);
1451            }
1452        }
1453
1454        return (Object []) array;
1455    }
1456
1457    private static boolean compareBoolean(Object lhs, String rhs, int operator)
1458        throws EvaluationException
1459    {
1460        Boolean rhsBoolean = new Boolean (rhs);
1461        if (lhs.getClass().isArray())
1462        {
1463            Object [] objs = (Object []) lhs;
1464            for (int i = 0; i < objs.length; i++)
1465            {
1466                switch (operator)
1467                {
1468                    case EQUAL :
1469                    case GREATER_EQUAL :
1470                    case LESS_EQUAL :
1471                    case APPROX:
1472                        if (objs[i].equals(rhsBoolean))
1473                        {
1474                            return true;
1475                        }
1476                        break;
1477                    default:
1478                        throw new EvaluationException(
1479                            "Unknown comparison operator: " + operator);
1480                }
1481            }
1482            return false;
1483        }
1484        else
1485        {
1486            switch (operator)
1487            {
1488                case EQUAL :
1489                case GREATER_EQUAL :
1490                case LESS_EQUAL :
1491                case APPROX:
1492                    return (lhs.equals(rhsBoolean));
1493                default:
1494                    throw new EvaluationException("Unknown comparison operator..."
1495                        + operator);
1496            }
1497        }
1498    }
1499
1500    /**
1501     * Test if two objects are approximate. The two objects that are passed must
1502     * have the same type.
1503     *
1504     * Approximate for numerical values involves a difference of less than APPROX_CRITERIA
1505     * Approximate for string values is calculated by using the Levenshtein distance
1506     * between strings. Less than APPROX_CRITERIA of difference is considered as approximate.
1507     *
1508     * Supported types only include the following subclasses of Number:
1509     * - Byte
1510     * - Double
1511     * - Float
1512     * - Int
1513     * - Long
1514     * - Short
1515     * - BigInteger
1516     * - BigDecimal
1517     * As subclasses of Number must provide methods to convert the represented numeric value
1518     * to byte, double, float, int, long, and short. (see API)
1519     *
1520     * @param obj1
1521     * @param obj2
1522     * @return true if they are approximate
1523     * @throws EvaluationException if it the two objects cannot be approximated
1524    **/
1525    private static boolean compareToApprox(Object obj1, Object obj2) throws EvaluationException
1526    {
1527        if (obj1 instanceof Byte )
1528        {
1529            byte value1 = ((Byte )obj1).byteValue();
1530            byte value2 = ((Byte )obj2).byteValue();
1531            return (value2 >= (value1-((Math.abs(value1)*(byte)APPROX_CRITERIA)/(byte)100))
1532                && value2 <= (value1+((Math.abs(value1)*(byte)APPROX_CRITERIA)/(byte)100)));
1533        }
1534        else if (obj1 instanceof Character )
1535        {
1536            char value1 = ((Character )obj1).charValue();
1537            char value2 = ((Character )obj2).charValue();
1538            return (value2 >= (value1-((Math.abs(value1)*(char)APPROX_CRITERIA)/(char)100))
1539                && value2 <= (value1+((Math.abs(value1)*(char)APPROX_CRITERIA)/(char)100)));
1540        }
1541        else if (obj1 instanceof Double )
1542        {
1543            double value1 = ((Double )obj1).doubleValue();
1544            double value2 = ((Double )obj2).doubleValue();
1545            return (value2 >= (value1-((Math.abs(value1)*(double)APPROX_CRITERIA)/(double)100))
1546                && value2 <= (value1+((Math.abs(value1)*(double)APPROX_CRITERIA)/(double)100)));
1547        }
1548        else if (obj1 instanceof Float )
1549        {
1550            float value1 = ((Float )obj1).floatValue();
1551            float value2 = ((Float )obj2).floatValue();
1552            return (value2 >= (value1-((Math.abs(value1)*(float)APPROX_CRITERIA)/(float)100))
1553                && value2 <= (value1+((Math.abs(value1)*(float)APPROX_CRITERIA)/(float)100)));
1554        }
1555        else if (obj1 instanceof Integer )
1556        {
1557            int value1 = ((Integer )obj1).intValue();
1558            int value2 = ((Integer )obj2).intValue();
1559            return (value2 >= (value1-((Math.abs(value1)*(int)APPROX_CRITERIA)/(int)100))
1560                && value2 <= (value1+((Math.abs(value1)*(int)APPROX_CRITERIA)/(int)100)));
1561        }
1562        else if (obj1 instanceof Long )
1563        {
1564            long value1 = ((Long )obj1).longValue();
1565            long value2 = ((Long )obj2).longValue();
1566            return (value2 >= (value1-((Math.abs(value1)*(long)APPROX_CRITERIA)/(long)100))
1567                && value2 <= (value1+((Math.abs(value1)*(long)APPROX_CRITERIA)/(long)100)));
1568        }
1569        else if (obj1 instanceof Short )
1570        {
1571            short value1 = ((Short )obj1).shortValue();
1572            short value2 = ((Short )obj2).shortValue();
1573            return (value2 >= (value1-((Math.abs(value1)*(short)APPROX_CRITERIA)/(short)100))
1574                && value2 <= (value1+((Math.abs(value1)*(short)APPROX_CRITERIA)/(short)100)));
1575        }
1576        else if (obj1 instanceof String )
1577        {
1578            int distance = getDistance(obj1.toString(),obj2.toString());
1579            int size = ((String )obj1).length();
1580            return (distance <= ((size*APPROX_CRITERIA)/100));
1581        }
1582        else if (m_hasBigNumbers && (obj1 instanceof BigInteger ))
1583        {
1584            BigInteger value1 = (BigInteger )obj1;
1585            BigInteger value2 = (BigInteger )obj2;
1586            BigInteger delta = value1.abs().multiply(
1587                BigInteger.valueOf(APPROX_CRITERIA)
1588                    .divide(BigInteger.valueOf(100)));
1589            BigInteger low = value1.subtract(delta);
1590            BigInteger high = value1.add(delta);
1591            return (value2.compareTo(low) >= 0) && (value2.compareTo(high) <= 0);
1592        }
1593        else if (m_hasBigNumbers && (obj1 instanceof BigDecimal ))
1594        {
1595            BigDecimal value1 = (BigDecimal )obj1;
1596            BigDecimal value2 = (BigDecimal )obj2;
1597            BigDecimal delta = value1.abs().multiply(
1598                BigDecimal.valueOf(APPROX_CRITERIA)
1599                    .divide(BigDecimal.valueOf(100), BigDecimal.ROUND_HALF_DOWN));
1600            BigDecimal low = value1.subtract(delta);
1601            BigDecimal high = value1.add(delta);
1602            return (value2.compareTo(low) >= 0) && (value2.compareTo(high) <= 0);
1603        }
1604        throw new EvaluationException(
1605            "Approximate operator not supported for type "
1606            + obj1.getClass().getName());
1607    }
1608
1609    /**
1610     * Calculate the Levenshtein distance (LD) between two strings.
1611     * The Levenshteing distance is a measure of the similarity between
1612     * two strings, which we will refer to as the source string (s) and
1613     * the target string (t). The distance is the number of deletions,
1614     * insertions, or substitutions required to transform s into t.
1615     *
1616     * Algorithm from: http://www.merriampark.com/ld.htm
1617     *
1618     * @param s the first string
1619     * @param t the second string
1620     * @return
1621     */
1622    private static int getDistance(String s, String t)
1623    {
1624        int d[][]; // matrix
1625 int n; // length of s
1626 int m; // length of t
1627 int i; // iterates through s
1628 int j; // iterates through t
1629 char s_i; // ith character of s
1630 char t_j; // jth character of t
1631 int cost; // cost
1632
1633        // Step 1
1634 n = s.length();
1635        m = t.length();
1636        if (n == 0)
1637        {
1638            return m;
1639        }
1640        if (m == 0)
1641        {
1642            return n;
1643        }
1644        d = new int[n + 1][m + 1];
1645
1646        // Step 2
1647 for (i = 0; i <= n; i++)
1648        {
1649            d[i][0] = i;
1650        }
1651
1652        for (j = 0; j <= m; j++)
1653        {
1654            d[0][j] = j;
1655        }
1656
1657        // Step 3
1658 for (i = 1; i <= n; i++)
1659        {
1660            s_i = s.charAt(i - 1);
1661            // Step 4
1662 for (j = 1; j <= m; j++)
1663            {
1664                t_j = t.charAt(j - 1);
1665                // Step 5
1666 if (s_i == t_j)
1667                {
1668                    cost = 0;
1669                }
1670                else
1671                {
1672                    cost = 1;
1673                }
1674                // Step 6
1675 d[i][j] =
1676                    Minimum(
1677                        d[i - 1][j] + 1,
1678                        d[i][j - 1] + 1,
1679                        d[i - 1][j - 1] + cost);
1680            }
1681        }
1682        // Step 7
1683 return d[n][m];
1684    }
1685
1686    /**
1687     * Calculate the minimum between three values
1688     *
1689     * @param a
1690     * @param b
1691     * @param c
1692     * @return
1693     */
1694    private static int Minimum(int a, int b, int c)
1695    {
1696        int mi;
1697        mi = a;
1698        if (b < mi)
1699        {
1700            mi = b;
1701        }
1702        if (c < mi)
1703        {
1704            mi = c;
1705        }
1706        return mi;
1707    }
1708
1709    private static void fewOperands(String op) throws EvaluationException
1710    {
1711        throw new EvaluationException(op + ": too few operands");
1712    }
1713
1714    private static void unsupportedType(String opStr, Class clazz)
1715        throws EvaluationException
1716    {
1717        throw new EvaluationException(
1718            opStr + ": unsupported type " + clazz.getName(), clazz);
1719    }
1720}
1721

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags