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 with 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: unknown " +
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(Character.toString(WILDCARD_TOKEN))) {
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 conjunction 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 StringBuilder sb = new StringBuilder(len);
524 char ch;
525 for (int i = 0; i < len; i++) {
526 switch (ch=str.charAt(i)) {
527 case '*':
528 sb.append("\\2a");
529 break;
530 case '(':
531 sb.append("\\28");
532 break;
533 case ')':
534 sb.append("\\29");
535 break;
536 case '\\':
537 sb.append("\\5c");
538 break;
539 case 0:
540 sb.append("\\00");
541 break;
542 default:
543 sb.append(ch);
544 }
545 }
546 return sb.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 StringBuilder answer = new StringBuilder(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 }