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<StringFilter> 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 = 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<? extends Attribute> e = attrs.getAll();
445 e.hasMore(); ) {
446 attr = e.next();
447 if (attr.size() == 0 || (attr.size() == 1 && attr.get() == null)) {
448 // only checking presence of attribute
449 answer += "(" + attr.getID() + "=" + "*)";
450 } else {
451 for (NamingEnumeration<?> ve = attr.getAll();
452 ve.hasMore();
453 ) {
454 String val = getEncodedStringRep(ve.next());
455 if (val != null) {
456 answer += "(" + attr.getID() + "=" + val + ")";
457 }
458 }
459 }
460 }
461
462 answer += ")";
463 //System.out.println("filter: " + answer);
464 return answer;
465 }
466
467 // Writes the hex representation of a byte to a StringBuffer.
468 private static void hexDigit(StringBuffer buf, byte x) {
469 char c;
470
471 c = (char) ((x >> 4) & 0xf);
472 if (c > 9)
473 c = (char) ((c-10) + 'A');
474 else
475 c = (char)(c + '0');
476
477 buf.append(c);
478 c = (char) (x & 0xf);
479 if (c > 9)
480 c = (char)((c-10) + 'A');
481 else
482 c = (char)(c + '0');
483 buf.append(c);
484 }
485
486
487 /**
488 * Returns the string representation of an object (such as an attr value).
489 * If obj is a byte array, encode each item as \xx, where xx is hex encoding
490 * of the byte value.
491 * Else, if obj is not a String, use its string representation (toString()).
492 * Special characters in obj (or its string representation) are then
493 * encoded appropriately according to RFC 2254.
494 * * \2a
495 * ( \28
496 * ) \29
497 * \ \5c
498 * NUL \00
499 */
500 private static String getEncodedStringRep(Object obj) throws NamingException {
501 String str;
502 if (obj == null)
503 return null;
504
505 if (obj instanceof byte[]) {
506 // binary data must be encoded as \hh where hh is a hex char
507 byte[] bytes = (byte[])obj;
508 StringBuffer b1 = new StringBuffer(bytes.length*3);
509 for (int i = 0; i < bytes.length; i++) {
510 b1.append('\\');
511 hexDigit(b1, bytes[i]);
512 }
513 return b1.toString();
514 }
515 if (!(obj instanceof String)) {
516 str = obj.toString();
517 } else {
518 str = (String)obj;
519 }
520 int len = str.length();
521 StringBuffer buf = new StringBuffer(len);
522 char ch;
523 for (int i = 0; i < len; i++) {
524 switch (ch=str.charAt(i)) {
525 case '*':
526 buf.append("\\2a");
527 break;
528 case '(':
529 buf.append("\\28");
530 break;
531 case ')':
532 buf.append("\\29");
533 break;
534 case '\\':
535 buf.append("\\5c");
536 break;
537 case 0:
538 buf.append("\\00");
539 break;
540 default:
541 buf.append(ch);
542 }
543 }
544 return buf.toString();
545 }
546
547
548 /**
549 * Finds the first occurrence of <tt>ch</tt> in <tt>val</tt> starting
550 * from position <tt>start</tt>. It doesn't count if <tt>ch</tt>
551 * has been escaped by a backslash (\)
552 */
553 public static int findUnescaped(char ch, String val, int start) {
554 int len = val.length();
555
556 while (start < len) {
557 int where = val.indexOf(ch, start);
558 // if at start of string, or not there at all, or if not escaped
559 if (where == start || where == -1 || val.charAt(where-1) != '\\')
560 return where;
561
562 // start search after escaped star
563 start = where + 1;
564 }
565 return -1;
566 }
567
568 /**
569 * Formats the expression <tt>expr</tt> using arguments from the array
570 * <tt>args</tt>.
571 *
572 * <code>{i}</code> specifies the <code>i</code>'th element from
573 * the array <code>args</code> is to be substituted for the
574 * string "<code>{i}</code>".
575 *
576 * To escape '{' or '}' (or any other character), use '\'.
577 *
578 * Uses getEncodedStringRep() to do encoding.
579 */
580
581 public static String format(String expr, Object[] args)
582 throws NamingException {
583
584 int param;
585 int where = 0, start = 0;
586 StringBuffer answer = new StringBuffer(expr.length());
587
588 while ((where = findUnescaped('{', expr, start)) >= 0) {
589 int pstart = where + 1; // skip '{'
590 int pend = expr.indexOf('}', pstart);
591
592 if (pend < 0) {
593 throw new InvalidSearchFilterException("unbalanced {: " + expr);
594 }
595
596 // at this point, pend should be pointing at '}'
597 try {
598 param = Integer.parseInt(expr.substring(pstart, pend));
599 } catch (NumberFormatException e) {
600 throw new InvalidSearchFilterException(
601 "integer expected inside {}: " + expr);
602 }
603
604 if (param >= args.length) {
605 throw new InvalidSearchFilterException(
606 "number exceeds argument list: " + param);
607 }
608
609 answer.append(expr.substring(start, where)).append(getEncodedStringRep(args[param]));
610 start = pend + 1; // skip '}'
611 }
612
613 if (start < expr.length())
614 answer.append(expr.substring(start));
615
616 return answer.toString();
617 }
618
619 /*
620 * returns an Attributes instance containing only attributeIDs given in
621 * "attributeIDs" whose values come from the given DSContext.
622 */
623 public static Attributes selectAttributes(Attributes originals,
624 String[] attrIDs) throws NamingException {
625
626 if (attrIDs == null)
627 return originals;
628
629 Attributes result = new BasicAttributes();
630
631 for(int i=0; i<attrIDs.length; i++) {
632 Attribute attr = originals.get(attrIDs[i]);
633 if(attr != null) {
634 result.put(attr);
635 }
636 }
637
638 return result;
639 }
640
641 /* For testing filter
642 public static void main(String[] args) {
643
644 Attributes attrs = new BasicAttributes(LdapClient.caseIgnore);
645 attrs.put("cn", "Rosanna Lee");
646 attrs.put("sn", "Lee");
647 attrs.put("fn", "Rosanna");
648 attrs.put("id", "10414");
649 attrs.put("machine", "jurassic");
650
651
652 try {
653 System.out.println(format(attrs));
654
655 String expr = "(&(Age = {0})(Account Balance <= {1}))";
656 Object[] fargs = new Object[2];
657 // fill in the parameters
658 fargs[0] = new Integer(65);
659 fargs[1] = new Float(5000);
660
661 System.out.println(format(expr, fargs));
662
663
664 System.out.println(format("bin={0}",
665 new Object[] {new byte[] {0, 1, 2, 3, 4, 5}}));
666
667 System.out.println(format("bin=\\{anything}", null));
668
669 } catch (NamingException e) {
670 e.printStackTrace();
671 }
672 }
673 */
674
675 }