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