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 }