View Javadoc
1   /*
2    * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  package com.sun.jndi.toolkit.dir;
26  
27  import javax.naming.*;
28  import javax.naming.directory.*;
29  import java.util.Enumeration;
30  import java.util.StringTokenizer;
31  import java.util.Vector;
32  import java.util.Locale;
33  
34  /**
35    * A class for parsing LDAP search filters (defined in RFC 1960, 2254)
36    *
37    * @author Jon Ruiz
38    * @author Rosanna Lee
39    */
40  public class SearchFilter implements AttrFilter {
41  
42      interface StringFilter extends AttrFilter {
43          public void parse() throws InvalidSearchFilterException;
44      }
45  
46      // %%% "filter" and "pos" are not declared "private" due to bug 4064984.
47      String                      filter;
48      int                         pos;
49      private StringFilter        rootFilter;
50  
51      protected static final boolean debug = false;
52  
53      protected static final char         BEGIN_FILTER_TOKEN = '(';
54      protected static final char         END_FILTER_TOKEN = ')';
55      protected static final char         AND_TOKEN = '&';
56      protected static final char         OR_TOKEN = '|';
57      protected static final char         NOT_TOKEN = '!';
58      protected static final char         EQUAL_TOKEN = '=';
59      protected static final char         APPROX_TOKEN = '~';
60      protected static final char         LESS_TOKEN = '<';
61      protected static final char         GREATER_TOKEN = '>';
62      protected static final char         EXTEND_TOKEN = ':';
63      protected static final char         WILDCARD_TOKEN = '*';
64  
65      public SearchFilter(String filter) throws InvalidSearchFilterException {
66          this.filter = filter;
67          pos = 0;
68          normalizeFilter();
69          rootFilter = this.createNextFilter();
70      }
71  
72      // Returns true if targetAttrs passes the filter
73      public boolean check(Attributes targetAttrs) throws NamingException {
74          if (targetAttrs == null)
75              return false;
76  
77          return rootFilter.check(targetAttrs);
78      }
79  
80      /*
81       * Utility routines used by member classes
82       */
83  
84      // does some pre-processing on the string to make it look exactly lik
85      // what the parser expects. This only needs to be called once.
86      protected void normalizeFilter() {
87          skipWhiteSpace(); // get rid of any leading whitespaces
88  
89          // Sometimes, search filters don't have "(" and ")" - add them
90          if(getCurrentChar() != BEGIN_FILTER_TOKEN) {
91              filter = BEGIN_FILTER_TOKEN + filter + END_FILTER_TOKEN;
92          }
93          // this would be a good place to strip whitespace if desired
94  
95          if(debug) {System.out.println("SearchFilter: normalized filter:" +
96                                        filter);}
97      }
98  
99      private void skipWhiteSpace() {
100         while (Character.isWhitespace(getCurrentChar())) {
101             consumeChar();
102         }
103     }
104 
105     protected StringFilter createNextFilter()
106         throws InvalidSearchFilterException {
107         StringFilter filter;
108 
109         skipWhiteSpace();
110 
111         try {
112             // make sure every filter starts with "("
113             if(getCurrentChar() != BEGIN_FILTER_TOKEN) {
114                 throw new InvalidSearchFilterException("expected \"" +
115                                                        BEGIN_FILTER_TOKEN +
116                                                        "\" at position " +
117                                                        pos);
118             }
119 
120             // skip past the "("
121             this.consumeChar();
122 
123             skipWhiteSpace();
124 
125             // use the next character to determine the type of filter
126             switch(getCurrentChar()) {
127             case AND_TOKEN:
128                 if (debug) {System.out.println("SearchFilter: creating AND");}
129                 filter = new CompoundFilter(true);
130                 filter.parse();
131                 break;
132             case OR_TOKEN:
133                 if (debug) {System.out.println("SearchFilter: creating OR");}
134                 filter = new CompoundFilter(false);
135                 filter.parse();
136                 break;
137             case NOT_TOKEN:
138                 if (debug) {System.out.println("SearchFilter: creating OR");}
139                 filter = new NotFilter();
140                 filter.parse();
141                 break;
142             default:
143                 if (debug) {System.out.println("SearchFilter: creating SIMPLE");}
144                 filter = new AtomicFilter();
145                 filter.parse();
146                 break;
147             }
148 
149             skipWhiteSpace();
150 
151             // make sure every filter ends with ")"
152             if(getCurrentChar() != END_FILTER_TOKEN) {
153                 throw new InvalidSearchFilterException("expected \"" +
154                                                        END_FILTER_TOKEN +
155                                                        "\" at position " +
156                                                        pos);
157             }
158 
159             // skip past the ")"
160             this.consumeChar();
161         } catch (InvalidSearchFilterException e) {
162             if (debug) {System.out.println("rethrowing e");}
163             throw e; // just rethrow these
164 
165         // catch all - any uncaught exception while parsing will end up here
166         } catch  (Exception e) {
167             if(debug) {System.out.println(e.getMessage());e.printStackTrace();}
168             throw new InvalidSearchFilterException("Unable to parse " +
169                     "character " + pos + " in \""+
170                     this.filter + "\"");
171         }
172 
173         return filter;
174     }
175 
176     protected char getCurrentChar() {
177         return filter.charAt(pos);
178     }
179 
180     protected char relCharAt(int i) {
181         return filter.charAt(pos + i);
182     }
183 
184     protected void consumeChar() {
185         pos++;
186     }
187 
188     protected void consumeChars(int i) {
189         pos += i;
190     }
191 
192     protected int relIndexOf(int ch) {
193         return filter.indexOf(ch, pos) - pos;
194     }
195 
196     protected String relSubstring(int beginIndex, int endIndex){
197         if(debug){System.out.println("relSubString: " + beginIndex +
198                                      " " + endIndex);}
199         return filter.substring(beginIndex+pos, endIndex+pos);
200     }
201 
202 
203    /**
204      * A class for dealing with compound filters ("and" & "or" filters).
205      */
206     final class CompoundFilter implements StringFilter {
207         private Vector<StringFilter>  subFilters;
208         private boolean polarity;
209 
210         CompoundFilter(boolean polarity) {
211             subFilters = new Vector<>();
212             this.polarity = polarity;
213         }
214 
215         public void parse() throws InvalidSearchFilterException {
216             SearchFilter.this.consumeChar(); // consume the "&"
217             while(SearchFilter.this.getCurrentChar() != END_FILTER_TOKEN) {
218                 if (debug) {System.out.println("CompoundFilter: adding");}
219                 StringFilter filter = SearchFilter.this.createNextFilter();
220                 subFilters.addElement(filter);
221                 skipWhiteSpace();
222             }
223         }
224 
225         public boolean check(Attributes targetAttrs) throws NamingException {
226             for(int i = 0; i<subFilters.size(); i++) {
227                 StringFilter filter = subFilters.elementAt(i);
228                 if(filter.check(targetAttrs) != this.polarity) {
229                     return !polarity;
230                 }
231             }
232             return polarity;
233         }
234     } /* CompoundFilter */
235 
236    /**
237      * A class for dealing with NOT filters
238      */
239     final class NotFilter implements StringFilter {
240         private StringFilter    filter;
241 
242         public void parse() throws InvalidSearchFilterException {
243             SearchFilter.this.consumeChar(); // consume the "!"
244             filter = SearchFilter.this.createNextFilter();
245         }
246 
247         public boolean check(Attributes targetAttrs) throws NamingException {
248             return !filter.check(targetAttrs);
249         }
250     } /* notFilter */
251 
252     // note: declared here since member classes can't have static variables
253     static final int EQUAL_MATCH = 1;
254     static final int APPROX_MATCH = 2;
255     static final int GREATER_MATCH = 3;
256     static final int LESS_MATCH = 4;
257 
258     /**
259      * A class for dealing wtih atomic filters
260      */
261     final class AtomicFilter implements StringFilter {
262         private String attrID;
263         private String value;
264         private int    matchType;
265 
266         public void parse() throws InvalidSearchFilterException {
267 
268             skipWhiteSpace();
269 
270             try {
271                 // find the end
272                 int endPos = SearchFilter.this.relIndexOf(END_FILTER_TOKEN);
273 
274                 //determine the match type
275                 int i = SearchFilter.this.relIndexOf(EQUAL_TOKEN);
276                 if(debug) {System.out.println("AtomicFilter: = at " + i);}
277                 int qualifier = SearchFilter.this.relCharAt(i-1);
278                 switch(qualifier) {
279                 case APPROX_TOKEN:
280                     if (debug) {System.out.println("Atomic: APPROX found");}
281                     matchType = APPROX_MATCH;
282                     attrID = SearchFilter.this.relSubstring(0, i-1);
283                     value = SearchFilter.this.relSubstring(i+1, endPos);
284                     break;
285 
286                 case GREATER_TOKEN:
287                     if (debug) {System.out.println("Atomic: GREATER found");}
288                     matchType = GREATER_MATCH;
289                     attrID = SearchFilter.this.relSubstring(0, i-1);
290                     value = SearchFilter.this.relSubstring(i+1, endPos);
291                     break;
292 
293                 case LESS_TOKEN:
294                     if (debug) {System.out.println("Atomic: LESS found");}
295                     matchType = LESS_MATCH;
296                     attrID = SearchFilter.this.relSubstring(0, i-1);
297                     value = SearchFilter.this.relSubstring(i+1, endPos);
298                     break;
299 
300                 case EXTEND_TOKEN:
301                     if(debug) {System.out.println("Atomic: EXTEND found");}
302                     throw new OperationNotSupportedException("Extensible match not supported");
303 
304                 default:
305                     if (debug) {System.out.println("Atomic: EQUAL found");}
306                     matchType = EQUAL_MATCH;
307                     attrID = SearchFilter.this.relSubstring(0,i);
308                     value = SearchFilter.this.relSubstring(i+1, endPos);
309                     break;
310                 }
311 
312                 attrID = attrID.trim();
313                 value = value.trim();
314 
315                 //update our position
316                 SearchFilter.this.consumeChars(endPos);
317 
318             } catch (Exception e) {
319                 if (debug) {System.out.println(e.getMessage());
320                             e.printStackTrace();}
321                 InvalidSearchFilterException sfe =
322                     new InvalidSearchFilterException("Unable to parse " +
323                     "character " + SearchFilter.this.pos + " in \""+
324                     SearchFilter.this.filter + "\"");
325                 sfe.setRootCause(e);
326                 throw(sfe);
327             }
328 
329             if(debug) {System.out.println("AtomicFilter: " + attrID + "=" +
330                                           value);}
331         }
332 
333         public boolean check(Attributes targetAttrs) {
334             Enumeration<?> candidates;
335 
336             try {
337                 Attribute attr = targetAttrs.get(attrID);
338                 if(attr == null) {
339                     return false;
340                 }
341                 candidates = attr.getAll();
342             } catch (NamingException ne) {
343                 if (debug) {System.out.println("AtomicFilter: should never " +
344                                                "here");}
345                 return false;
346             }
347 
348             while(candidates.hasMoreElements()) {
349                 String val = candidates.nextElement().toString();
350                 if (debug) {System.out.println("Atomic: comparing: " + val);}
351                 switch(matchType) {
352                 case APPROX_MATCH:
353                 case EQUAL_MATCH:
354                     if(substringMatch(this.value, val)) {
355                     if (debug) {System.out.println("Atomic: EQUAL match");}
356                         return true;
357                     }
358                     break;
359                 case GREATER_MATCH:
360                     if (debug) {System.out.println("Atomic: GREATER match");}
361                     if(val.compareTo(this.value) >= 0) {
362                         return true;
363                     }
364                     break;
365                 case LESS_MATCH:
366                     if (debug) {System.out.println("Atomic: LESS match");}
367                     if(val.compareTo(this.value) <= 0) {
368                         return true;
369                     }
370                     break;
371                 default:
372                     if (debug) {System.out.println("AtomicFilter: unkown " +
373                                                    "matchType");}
374                 }
375             }
376             return false;
377         }
378 
379         // used for substring comparisons (where proto has "*" wildcards
380         private boolean substringMatch(String proto, String value) {
381             // simple case 1: "*" means attribute presence is being tested
382             if(proto.equals(new Character(WILDCARD_TOKEN).toString())) {
383                 if(debug) {System.out.println("simple presence assertion");}
384                 return true;
385             }
386 
387             // simple case 2: if there are no wildcards, call String.equals()
388             if(proto.indexOf(WILDCARD_TOKEN) == -1) {
389                 return proto.equalsIgnoreCase(value);
390             }
391 
392             if(debug) {System.out.println("doing substring comparison");}
393             // do the work: make sure all the substrings are present
394             int currentPos = 0;
395             StringTokenizer subStrs = new StringTokenizer(proto, "*", false);
396 
397             // do we need to begin with the first token?
398             if(proto.charAt(0) != WILDCARD_TOKEN &&
399                     !value.toLowerCase(Locale.ENGLISH).startsWith(
400                         subStrs.nextToken().toLowerCase(Locale.ENGLISH))) {
401                 if(debug) {
402                     System.out.println("faild initial test");
403                 }
404                 return false;
405             }
406 
407             while(subStrs.hasMoreTokens()) {
408                 String currentStr = subStrs.nextToken();
409                 if (debug) {System.out.println("looking for \"" +
410                                                currentStr +"\"");}
411                 currentPos = value.toLowerCase(Locale.ENGLISH).indexOf(
412                        currentStr.toLowerCase(Locale.ENGLISH), currentPos);
413 
414                 if(currentPos == -1) {
415                     return false;
416                 }
417                 currentPos += currentStr.length();
418             }
419 
420             // do we need to end with the last token?
421             if(proto.charAt(proto.length() - 1) != WILDCARD_TOKEN &&
422                currentPos != value.length() ) {
423                 if(debug) {System.out.println("faild final test");}
424                 return false;
425             }
426 
427             return true;
428         }
429 
430     } /* AtomicFilter */
431 
432     // ----- static methods for producing string filters given attribute set
433     // ----- or object array
434 
435 
436     /**
437       * Creates an LDAP filter as a conjuction of the attributes supplied.
438       */
439     public static String format(Attributes attrs) throws NamingException {
440         if (attrs == null || attrs.size() == 0) {
441             return "objectClass=*";
442         }
443 
444         String answer;
445         answer = "(& ";
446         Attribute attr;
447         for (NamingEnumeration<? extends Attribute> e = attrs.getAll();
448              e.hasMore(); ) {
449             attr = e.next();
450             if (attr.size() == 0 || (attr.size() == 1 && attr.get() == null)) {
451                 // only checking presence of attribute
452                 answer += "(" + attr.getID() + "=" + "*)";
453             } else {
454                 for (NamingEnumeration<?> ve = attr.getAll();
455                      ve.hasMore(); ) {
456                     String val = getEncodedStringRep(ve.next());
457                     if (val != null) {
458                         answer += "(" + attr.getID() + "=" + val + ")";
459                     }
460                 }
461             }
462         }
463 
464         answer += ")";
465         //System.out.println("filter: " + answer);
466         return answer;
467     }
468 
469     // Writes the hex representation of a byte to a StringBuffer.
470     private static void hexDigit(StringBuffer buf, byte x) {
471         char c;
472 
473         c = (char) ((x >> 4) & 0xf);
474         if (c > 9)
475             c = (char) ((c-10) + 'A');
476         else
477             c = (char)(c + '0');
478 
479         buf.append(c);
480         c = (char) (x & 0xf);
481         if (c > 9)
482             c = (char)((c-10) + 'A');
483         else
484             c = (char)(c + '0');
485         buf.append(c);
486     }
487 
488 
489     /**
490       * Returns the string representation of an object (such as an attr value).
491       * If obj is a byte array, encode each item as \xx, where xx is hex encoding
492       * of the byte value.
493       * Else, if obj is not a String, use its string representation (toString()).
494       * Special characters in obj (or its string representation) are then
495       * encoded appropriately according to RFC 2254.
496       *         *       \2a
497       *         (       \28
498       *         )       \29
499       *         \       \5c
500       *         NUL     \00
501       */
502     private static String getEncodedStringRep(Object obj) throws NamingException {
503         String str;
504         if (obj == null)
505             return null;
506 
507         if (obj instanceof byte[]) {
508             // binary data must be encoded as \hh where hh is a hex char
509             byte[] bytes = (byte[])obj;
510             StringBuffer b1 = new StringBuffer(bytes.length*3);
511             for (int i = 0; i < bytes.length; i++) {
512                 b1.append('\\');
513                 hexDigit(b1, bytes[i]);
514             }
515             return b1.toString();
516         }
517         if (!(obj instanceof String)) {
518             str = obj.toString();
519         } else {
520             str = (String)obj;
521         }
522         int len = str.length();
523         StringBuffer buf = new StringBuffer(len);
524         char ch;
525         for (int i = 0; i < len; i++) {
526             switch (ch=str.charAt(i)) {
527             case '*':
528                 buf.append("\\2a");
529                 break;
530             case '(':
531                 buf.append("\\28");
532                 break;
533             case ')':
534                 buf.append("\\29");
535                 break;
536             case '\\':
537                 buf.append("\\5c");
538                 break;
539             case 0:
540                 buf.append("\\00");
541                 break;
542             default:
543                 buf.append(ch);
544             }
545         }
546         return buf.toString();
547     }
548 
549 
550     /**
551       * Finds the first occurrence of <tt>ch</tt> in <tt>val</tt> starting
552       * from position <tt>start</tt>. It doesn't count if <tt>ch</tt>
553       * has been escaped by a backslash (\)
554       */
555     public static int findUnescaped(char ch, String val, int start) {
556         int len = val.length();
557 
558         while (start < len) {
559             int where = val.indexOf(ch, start);
560             // if at start of string, or not there at all, or if not escaped
561             if (where == start || where == -1 || val.charAt(where-1) != '\\')
562                 return where;
563 
564             // start search after escaped star
565             start = where + 1;
566         }
567         return -1;
568     }
569 
570     /**
571      * Formats the expression <tt>expr</tt> using arguments from the array
572      * <tt>args</tt>.
573      *
574      * <code>{i}</code> specifies the <code>i</code>'th element from
575      * the array <code>args</code> is to be substituted for the
576      * string "<code>{i}</code>".
577      *
578      * To escape '{' or '}' (or any other character), use '\'.
579      *
580      * Uses getEncodedStringRep() to do encoding.
581      */
582 
583     public static String format(String expr, Object[] args)
584         throws NamingException {
585 
586          int param;
587          int where = 0, start = 0;
588          StringBuffer answer = new StringBuffer(expr.length());
589 
590          while ((where = findUnescaped('{', expr, start)) >= 0) {
591              int pstart = where + 1; // skip '{'
592              int pend = expr.indexOf('}', pstart);
593 
594              if (pend < 0) {
595                  throw new InvalidSearchFilterException("unbalanced {: " + expr);
596              }
597 
598              // at this point, pend should be pointing at '}'
599              try {
600                  param = Integer.parseInt(expr.substring(pstart, pend));
601              } catch (NumberFormatException e) {
602                  throw new InvalidSearchFilterException(
603                      "integer expected inside {}: " + expr);
604              }
605 
606              if (param >= args.length) {
607                  throw new InvalidSearchFilterException(
608                      "number exceeds argument list: " + param);
609              }
610 
611              answer.append(expr.substring(start, where)).append(getEncodedStringRep(args[param]));
612              start = pend + 1; // skip '}'
613          }
614 
615          if (start < expr.length())
616              answer.append(expr.substring(start));
617 
618         return answer.toString();
619     }
620 
621     /*
622      * returns an Attributes instance containing only attributeIDs given in
623      * "attributeIDs" whose values come from the given DSContext.
624      */
625     public static Attributes selectAttributes(Attributes originals,
626         String[] attrIDs) throws NamingException {
627 
628         if (attrIDs == null)
629             return originals;
630 
631         Attributes result = new BasicAttributes();
632 
633         for(int i=0; i<attrIDs.length; i++) {
634             Attribute attr = originals.get(attrIDs[i]);
635             if(attr != null) {
636                 result.put(attr);
637             }
638         }
639 
640         return result;
641     }
642 
643 /*  For testing filter
644     public static void main(String[] args) {
645 
646         Attributes attrs = new BasicAttributes(LdapClient.caseIgnore);
647         attrs.put("cn", "Rosanna Lee");
648         attrs.put("sn", "Lee");
649         attrs.put("fn", "Rosanna");
650         attrs.put("id", "10414");
651         attrs.put("machine", "jurassic");
652 
653 
654         try {
655             System.out.println(format(attrs));
656 
657             String  expr = "(&(Age = {0})(Account Balance <= {1}))";
658             Object[] fargs = new Object[2];
659             // fill in the parameters
660             fargs[0] = new Integer(65);
661             fargs[1] = new Float(5000);
662 
663             System.out.println(format(expr, fargs));
664 
665 
666             System.out.println(format("bin={0}",
667                 new Object[] {new byte[] {0, 1, 2, 3, 4, 5}}));
668 
669             System.out.println(format("bin=\\{anything}", null));
670 
671         } catch (NamingException e) {
672             e.printStackTrace();
673         }
674     }
675 */
676 
677 }