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 
  26 package com.sun.jndi.ldap;
  27 
  28 import javax.naming.NamingException;
  29 import javax.naming.directory.InvalidSearchFilterException;
  30 
  31 import java.io.IOException;
  32 
  33 /**
  34  * LDAP (RFC-1960) and LDAPv3 (RFC-2254) search filters.
  35  *
  36  * @author Xuelei Fan
  37  * @author Vincent Ryan
  38  * @author Jagane Sundar
  39  * @author Rosanna Lee
  40  */
  41 
  42 final class Filter {
  43 
  44     /**
  45      * First convert filter string into byte[].
  46      * For LDAP v3, the conversion uses Unicode -> UTF8
  47      * For LDAP v2, the conversion uses Unicode -> ISO 8859 (Latin-1)
  48      *
  49      * Then parse the byte[] as a filter, converting \hh to
  50      * a single byte, and encoding the resulting filter
  51      * into the supplied BER buffer
  52      */
  53     static void encodeFilterString(BerEncoder ber, String filterStr,
  54         boolean isLdapv3) throws IOException, NamingException {
  55 
  56         if ((filterStr == null) || (filterStr.equals(""))) {
  57             throw new InvalidSearchFilterException("Empty filter");
  58         }
  59         byte[] filter;
  60         int filterLen;
  61         if (isLdapv3) {
  62             filter = filterStr.getBytes("UTF8");
  63         } else {
  64             filter = filterStr.getBytes("8859_1");
  65         }
  66         filterLen = filter.length;
  67         if (dbg) {
  68             dbgIndent = 0;
  69             System.err.println("String filter: " + filterStr);
  70             System.err.println("size: " + filterLen);
  71             dprint("original: ", filter, 0, filterLen);
  72         }
  73 
  74         encodeFilter(ber, filter, 0, filterLen);
  75     }
  76 
  77     private static void encodeFilter(BerEncoder ber, byte[] filter,
  78         int filterStart, int filterEnd) throws IOException, NamingException {
  79 
  80         if (dbg) {
  81             dprint("encFilter: ",  filter, filterStart, filterEnd);
  82             dbgIndent++;
  83         }
  84 
  85         if ((filterEnd - filterStart) <= 0) {
  86             throw new InvalidSearchFilterException("Empty filter");
  87         }
  88 
  89         int nextOffset;
  90         int parens, balance;
  91         boolean escape;
  92 
  93         parens = 0;
  94 
  95         int filtOffset[] = new int[1];
  96 
  97         for (filtOffset[0] = filterStart; filtOffset[0] < filterEnd;) {
  98             switch (filter[filtOffset[0]]) {
  99             case '(':
 100                 filtOffset[0]++;
 101                 parens++;
 102                 switch (filter[filtOffset[0]]) {
 103                 case '&':
 104                     encodeComplexFilter(ber, filter,
 105                         LDAP_FILTER_AND, filtOffset, filterEnd);
 106                     // filtOffset[0] has pointed to char after right paren
 107                     parens--;
 108                     break;
 109 
 110                 case '|':
 111                     encodeComplexFilter(ber, filter,
 112                         LDAP_FILTER_OR, filtOffset, filterEnd);
 113                     // filtOffset[0] has pointed to char after right paren
 114                     parens--;
 115                     break;
 116 
 117                 case '!':
 118                     encodeComplexFilter(ber, filter,
 119                         LDAP_FILTER_NOT, filtOffset, filterEnd);
 120                     // filtOffset[0] has pointed to char after right paren
 121                     parens--;
 122                     break;
 123 
 124                 default:
 125                     balance = 1;
 126                     escape = false;
 127                     nextOffset = filtOffset[0];
 128                     while (nextOffset < filterEnd && balance > 0) {
 129                         if (!escape) {
 130                             if (filter[nextOffset] == '(')
 131                                 balance++;
 132                             else if (filter[nextOffset] == ')')
 133                                 balance--;
 134                         }
 135                         if (filter[nextOffset] == '\\' && !escape)
 136                             escape = true;
 137                         else
 138                             escape = false;
 139                         if (balance > 0)
 140                             nextOffset++;
 141                     }
 142                     if (balance != 0)
 143                         throw new InvalidSearchFilterException(
 144                                   "Unbalanced parenthesis");
 145 
 146                     encodeSimpleFilter(ber, filter, filtOffset[0], nextOffset);
 147 
 148                     // points to the char after right paren.
 149                     filtOffset[0] = nextOffset + 1;
 150 
 151                     parens--;
 152                     break;
 153 
 154                 }
 155                 break;
 156 
 157             case ')':
 158                 //
 159                 // End of sequence
 160                 //
 161                 ber.endSeq();
 162                 filtOffset[0]++;
 163                 parens--;
 164                 break;
 165 
 166             case ' ':
 167                 filtOffset[0]++;
 168                 break;
 169 
 170             default:    // assume simple type=value filter
 171                 encodeSimpleFilter(ber, filter, filtOffset[0], filterEnd);
 172                 filtOffset[0] = filterEnd; // force break from outer
 173                 break;
 174             }
 175 
 176             if (parens < 0) {
 177                 throw new InvalidSearchFilterException(
 178                                                 "Unbalanced parenthesis");
 179             }
 180         }
 181 
 182         if (parens != 0) {
 183             throw new InvalidSearchFilterException("Unbalanced parenthesis");
 184         }
 185 
 186         if (dbg) {
 187             dbgIndent--;
 188         }
 189 
 190     }
 191 
 192     /**
 193      * convert character 'c' that represents a hexadecimal digit to an integer.
 194      * if 'c' is not a hexadecimal digit [0-9A-Fa-f], -1 is returned.
 195      * otherwise the converted value is returned.
 196      */
 197     private static int hexchar2int( byte c ) {
 198         if ( c >= '0' && c <= '9' ) {
 199             return( c - '0' );
 200         }
 201         if ( c >= 'A' && c <= 'F' ) {
 202             return( c - 'A' + 10 );
 203         }
 204         if ( c >= 'a' && c <= 'f' ) {
 205             return( c - 'a' + 10 );
 206         }
 207         return( -1 );
 208     }
 209 
 210     // called by the LdapClient.compare method
 211     static byte[] unescapeFilterValue(byte[] orig, int start, int end)
 212         throws NamingException {
 213         boolean escape = false, escStart = false;
 214         int ival;
 215         byte ch;
 216 
 217         if (dbg) {
 218             dprint("unescape: " , orig, start, end);
 219         }
 220 
 221         int len = end - start;
 222         byte tbuf[] = new byte[len];
 223         int j = 0;
 224         for (int i = start; i < end; i++) {
 225             ch = orig[i];
 226             if (escape) {
 227                 // Try LDAP V3 escape (\xx)
 228                 if ((ival = hexchar2int(ch)) < 0) {
 229 
 230                     /**
 231                      * If there is no hex char following a '\' when
 232                      * parsing a LDAP v3 filter (illegal by v3 way)
 233                      * we fallback to the way we unescape in v2.
 234                      */
 235                     if (escStart) {
 236                         // V2: \* \( \)
 237                         escape = false;
 238                         tbuf[j++] = ch;
 239                     } else {
 240                         // escaping already started but we can't find 2nd hex
 241                         throw new InvalidSearchFilterException("invalid escape sequence: " + orig);
 242                     }
 243                 } else {
 244                     if (escStart) {
 245                         tbuf[j] = (byte)(ival<<4);
 246                         escStart = false;
 247                     } else {
 248                         tbuf[j++] |= (byte)ival;
 249                         escape = false;
 250                     }
 251                 }
 252             } else if (ch != '\\') {
 253                 tbuf[j++] = ch;
 254                 escape = false;
 255             } else {
 256                 escStart = escape = true;
 257             }
 258         }
 259         byte[] answer = new byte[j];
 260         System.arraycopy(tbuf, 0, answer, 0, j);
 261         if (dbg) {
 262             Ber.dumpBER(System.err, "", answer, 0, j);
 263         }
 264         return answer;
 265     }
 266 
 267     private static int indexOf(byte[] str, char ch, int start, int end) {
 268         for (int i = start; i < end; i++) {
 269             if (str[i] == ch)
 270                 return i;
 271         }
 272         return -1;
 273     }
 274 
 275     private static int indexOf(byte[] str, String target, int start, int end) {
 276         int where = indexOf(str, target.charAt(0), start, end);
 277         if (where >= 0) {
 278             for (int i = 1; i < target.length(); i++) {
 279                 if (str[where+i] != target.charAt(i)) {
 280                     return -1;
 281                 }
 282             }
 283         }
 284         return where;
 285     }
 286 
 287     private static int findUnescaped(byte[] str, char ch, int start, int end) {
 288         while (start < end) {
 289             int where = indexOf(str, ch, start, end);
 290 
 291             /*
 292              * Count the immediate preceding '\' to find out if
 293              * this is an escaped '*'. This is a made-up way for
 294              * parsing an escaped '*' in v2. This is how the other leading
 295              * SDK vendors interpret v2.
 296              * For v3 we fallback to the way we parse "\*" in v2.
 297              * It's not legal in v3 to use "\*" to escape '*'; the right
 298              * way is to use "\2a" instead.
 299              */
 300             int backSlashPos;
 301             int backSlashCnt = 0;
 302             for (backSlashPos = where - 1;
 303                     ((backSlashPos >= start) && (str[backSlashPos] == '\\'));
 304                     backSlashPos--, backSlashCnt++);
 305 
 306             // if at start of string, or not there at all, or if not escaped
 307             if (where == start || where == -1 || ((backSlashCnt % 2) == 0))
 308                 return where;
 309 
 310             // start search after escaped star
 311             start = where + 1;
 312         }
 313         return -1;
 314     }
 315 
 316 
 317     private static void encodeSimpleFilter(BerEncoder ber, byte[] filter,
 318         int filtStart, int filtEnd) throws IOException, NamingException {
 319 
 320         if (dbg) {
 321             dprint("encSimpleFilter: ", filter, filtStart, filtEnd);
 322             dbgIndent++;
 323         }
 324 
 325         String type, value;
 326         int valueStart, valueEnd, typeStart, typeEnd;
 327 
 328         int eq;
 329         if ((eq = indexOf(filter, '=', filtStart, filtEnd)) == -1) {
 330             throw new InvalidSearchFilterException("Missing 'equals'");
 331         }
 332 
 333 
 334         valueStart = eq + 1;        // value starts after equal sign
 335         valueEnd = filtEnd;
 336         typeStart = filtStart;      // beginning of string
 337 
 338         int ftype;
 339 
 340         switch (filter[eq - 1]) {
 341         case '<':
 342             ftype = LDAP_FILTER_LE;
 343             typeEnd = eq - 1;
 344             break;
 345         case '>':
 346             ftype = LDAP_FILTER_GE;
 347             typeEnd = eq - 1;
 348             break;
 349         case '~':
 350             ftype = LDAP_FILTER_APPROX;
 351             typeEnd = eq - 1;
 352             break;
 353         case ':':
 354             ftype = LDAP_FILTER_EXT;
 355             typeEnd = eq - 1;
 356             break;
 357         default:
 358             typeEnd = eq;
 359             //initializing ftype to make the compiler happy
 360             ftype = 0x00;
 361             break;
 362         }
 363 
 364         if (dbg) {
 365             System.err.println("type: " + typeStart + ", " + typeEnd);
 366             System.err.println("value: " + valueStart + ", " + valueEnd);
 367         }
 368 
 369         // check validity of type
 370         //
 371         // RFC4512 defines the type as the following ABNF:
 372         //     attr = attributedescription
 373         //     attributedescription = attributetype options
 374         //     attributetype = oid
 375         //     oid = descr / numericoid
 376         //     descr = keystring
 377         //     keystring = leadkeychar *keychar
 378         //     leadkeychar = ALPHA
 379         //     keychar = ALPHA / DIGIT / HYPHEN
 380         //     numericoid = number 1*( DOT number )
 381         //     number  = DIGIT / ( LDIGIT 1*DIGIT )
 382         //     options = *( SEMI option )
 383         //     option = 1*keychar
 384         //
 385         // And RFC4515 defines the extensible type as the following ABNF:
 386         //     attr [dnattrs] [matchingrule] / [dnattrs] matchingrule
 387         int optionsStart = -1;
 388         int extensibleStart = -1;
 389         if ((filter[typeStart] >= '0' && filter[typeStart] <= '9') ||
 390             (filter[typeStart] >= 'A' && filter[typeStart] <= 'Z') ||
 391             (filter[typeStart] >= 'a' && filter[typeStart] <= 'z')) {
 392 
 393             boolean isNumericOid =
 394                 filter[typeStart] >= '0' && filter[typeStart] <= '9';
 395             for (int i = typeStart + 1; i < typeEnd; i++) {
 396                 // ';' is an indicator of attribute options
 397                 if (filter[i] == ';') {
 398                     if (isNumericOid && filter[i - 1] == '.') {
 399                         throw new InvalidSearchFilterException(
 400                                     "invalid attribute description");
 401                     }
 402 
 403                     // attribute options
 404                     optionsStart = i;
 405                     break;
 406                 }
 407 
 408                 // ':' is an indicator of extensible rules
 409                 if (filter[i] == ':' && ftype == LDAP_FILTER_EXT) {
 410                     if (isNumericOid && filter[i - 1] == '.') {
 411                         throw new InvalidSearchFilterException(
 412                                     "invalid attribute description");
 413                     }
 414 
 415                     // extensible matching
 416                     extensibleStart = i;
 417                     break;
 418                 }
 419 
 420                 if (isNumericOid) {
 421                     // numeric object identifier
 422                     if ((filter[i] == '.' && filter[i - 1] == '.') ||
 423                         (filter[i] != '.' &&
 424                             !(filter[i] >= '0' && filter[i] <= '9'))) {
 425                         throw new InvalidSearchFilterException(
 426                                     "invalid attribute description");
 427                     }
 428                 } else {
 429                     // descriptor
 430                     // The underscore ("_") character is not allowed by
 431                     // the LDAP specification. We allow it here to
 432                     // tolerate the incorrect use in practice.
 433                     if (filter[i] != '-' && filter[i] != '_' &&
 434                         !(filter[i] >= '0' && filter[i] <= '9') &&
 435                         !(filter[i] >= 'A' && filter[i] <= 'Z') &&
 436                         !(filter[i] >= 'a' && filter[i] <= 'z')) {
 437                         throw new InvalidSearchFilterException(
 438                                     "invalid attribute description");
 439                     }
 440                 }
 441             }
 442         } else if (ftype == LDAP_FILTER_EXT && filter[typeStart] == ':') {
 443             // extensible matching
 444             extensibleStart = typeStart;
 445         } else {
 446             throw new InvalidSearchFilterException(
 447                                     "invalid attribute description");
 448         }
 449 
 450         // check attribute options
 451         if (optionsStart > 0) {
 452             for (int i = optionsStart + 1; i < typeEnd; i++) {
 453                 if (filter[i] == ';') {
 454                     if (filter[i - 1] == ';') {
 455                         throw new InvalidSearchFilterException(
 456                                     "invalid attribute description");
 457                     }
 458                     continue;
 459                 }
 460 
 461                 // ':' is an indicator of extensible rules
 462                 if (filter[i] == ':' && ftype == LDAP_FILTER_EXT) {
 463                     if (filter[i - 1] == ';') {
 464                         throw new InvalidSearchFilterException(
 465                                     "invalid attribute description");
 466                     }
 467 
 468                     // extensible matching
 469                     extensibleStart = i;
 470                     break;
 471                 }
 472 
 473                 // The underscore ("_") character is not allowed by
 474                 // the LDAP specification. We allow it here to
 475                 // tolerate the incorrect use in practice.
 476                 if (filter[i] != '-' && filter[i] != '_' &&
 477                         !(filter[i] >= '0' && filter[i] <= '9') &&
 478                         !(filter[i] >= 'A' && filter[i] <= 'Z') &&
 479                         !(filter[i] >= 'a' && filter[i] <= 'z')) {
 480                     throw new InvalidSearchFilterException(
 481                                     "invalid attribute description");
 482                 }
 483             }
 484         }
 485 
 486         // check extensible matching
 487         if (extensibleStart > 0) {
 488             boolean isMatchingRule = false;
 489             for (int i = extensibleStart + 1; i < typeEnd; i++) {
 490                 if (filter[i] == ':') {
 491                     throw new InvalidSearchFilterException(
 492                                     "invalid attribute description");
 493                 } else if ((filter[i] >= '0' && filter[i] <= '9') ||
 494                            (filter[i] >= 'A' && filter[i] <= 'Z') ||
 495                            (filter[i] >= 'a' && filter[i] <= 'z')) {
 496                     boolean isNumericOid = filter[i] >= '0' && filter[i] <= '9';
 497                     i++;
 498                     for (int j = i; j < typeEnd; j++, i++) {
 499                         // allows no more than two extensible rules
 500                         if (filter[j] == ':') {
 501                             if (isMatchingRule) {
 502                                 throw new InvalidSearchFilterException(
 503                                             "invalid attribute description");
 504                             }
 505                             if (isNumericOid && filter[j - 1] == '.') {
 506                                 throw new InvalidSearchFilterException(
 507                                             "invalid attribute description");
 508                             }
 509 
 510                             isMatchingRule = true;
 511                             break;
 512                         }
 513 
 514                         if (isNumericOid) {
 515                             // numeric object identifier
 516                             if ((filter[j] == '.' && filter[j - 1] == '.') ||
 517                                 (filter[j] != '.' &&
 518                                     !(filter[j] >= '0' && filter[j] <= '9'))) {
 519                                 throw new InvalidSearchFilterException(
 520                                             "invalid attribute description");
 521                             }
 522                         } else {
 523                             // descriptor
 524                             // The underscore ("_") character is not allowed by
 525                             // the LDAP specification. We allow it here to
 526                             // tolerate the incorrect use in practice.
 527                             if (filter[j] != '-' && filter[j] != '_' &&
 528                                 !(filter[j] >= '0' && filter[j] <= '9') &&
 529                                 !(filter[j] >= 'A' && filter[j] <= 'Z') &&
 530                                 !(filter[j] >= 'a' && filter[j] <= 'z')) {
 531                                 throw new InvalidSearchFilterException(
 532                                             "invalid attribute description");
 533                             }
 534                         }
 535                     }
 536                 } else {
 537                     throw new InvalidSearchFilterException(
 538                                     "invalid attribute description");
 539                 }
 540             }
 541         }
 542 
 543         // ensure the latest byte is not isolated
 544         if (filter[typeEnd - 1] == '.' || filter[typeEnd - 1] == ';' ||
 545                                           filter[typeEnd - 1] == ':') {
 546             throw new InvalidSearchFilterException(
 547                 "invalid attribute description");
 548         }
 549 
 550         if (typeEnd == eq) { // filter type is of "equal"
 551             if (findUnescaped(filter, '*', valueStart, valueEnd) == -1) {
 552                 ftype = LDAP_FILTER_EQUALITY;
 553             } else if (filter[valueStart] == '*' &&
 554                             valueStart == (valueEnd - 1)) {
 555                 ftype = LDAP_FILTER_PRESENT;
 556             } else {
 557                 encodeSubstringFilter(ber, filter,
 558                     typeStart, typeEnd, valueStart, valueEnd);
 559                 return;
 560             }
 561         }
 562 
 563         if (ftype == LDAP_FILTER_PRESENT) {
 564             ber.encodeOctetString(filter, ftype, typeStart, typeEnd-typeStart);
 565         } else if (ftype == LDAP_FILTER_EXT) {
 566             encodeExtensibleMatch(ber, filter,
 567                 typeStart, typeEnd, valueStart, valueEnd);
 568         } else {
 569             ber.beginSeq(ftype);
 570                 ber.encodeOctetString(filter, Ber.ASN_OCTET_STR,
 571                     typeStart, typeEnd - typeStart);
 572                 ber.encodeOctetString(
 573                     unescapeFilterValue(filter, valueStart, valueEnd),
 574                     Ber.ASN_OCTET_STR);
 575             ber.endSeq();
 576         }
 577 
 578         if (dbg) {
 579             dbgIndent--;
 580         }
 581     }
 582 
 583     private static void encodeSubstringFilter(BerEncoder ber, byte[] filter,
 584         int typeStart, int typeEnd, int valueStart, int valueEnd)
 585         throws IOException, NamingException {
 586 
 587         if (dbg) {
 588             dprint("encSubstringFilter: type ", filter, typeStart, typeEnd);
 589             dprint(", val : ", filter, valueStart, valueEnd);
 590             dbgIndent++;
 591         }
 592 
 593         ber.beginSeq(LDAP_FILTER_SUBSTRINGS);
 594             ber.encodeOctetString(filter, Ber.ASN_OCTET_STR,
 595                     typeStart, typeEnd-typeStart);
 596             ber.beginSeq(LdapClient.LBER_SEQUENCE);
 597                 int index;
 598                 int previndex = valueStart;
 599                 while ((index = findUnescaped(filter, '*', previndex, valueEnd)) != -1) {
 600                     if (previndex == valueStart) {
 601                       if (previndex < index) {
 602                           if (dbg)
 603                               System.err.println(
 604                                   "initial: " + previndex + "," + index);
 605                         ber.encodeOctetString(
 606                             unescapeFilterValue(filter, previndex, index),
 607                             LDAP_SUBSTRING_INITIAL);
 608                       }
 609                     } else {
 610                       if (previndex < index) {
 611                           if (dbg)
 612                               System.err.println("any: " + previndex + "," + index);
 613                         ber.encodeOctetString(
 614                             unescapeFilterValue(filter, previndex, index),
 615                             LDAP_SUBSTRING_ANY);
 616                       }
 617                     }
 618                     previndex = index + 1;
 619                 }
 620                 if (previndex < valueEnd) {
 621                     if (dbg)
 622                         System.err.println("final: " + previndex + "," + valueEnd);
 623                   ber.encodeOctetString(
 624                       unescapeFilterValue(filter, previndex, valueEnd),
 625                       LDAP_SUBSTRING_FINAL);
 626                 }
 627             ber.endSeq();
 628         ber.endSeq();
 629 
 630         if (dbg) {
 631             dbgIndent--;
 632         }
 633     }
 634 
 635     // The complex filter types look like:
 636     //     "&(type=val)(type=val)"
 637     //     "|(type=val)(type=val)"
 638     //     "!(type=val)"
 639     //
 640     // The filtOffset[0] pointing to the '&', '|', or '!'.
 641     //
 642     private static void encodeComplexFilter(BerEncoder ber, byte[] filter,
 643         int filterType, int filtOffset[], int filtEnd)
 644         throws IOException, NamingException {
 645 
 646         if (dbg) {
 647             dprint("encComplexFilter: ", filter, filtOffset[0], filtEnd);
 648             dprint(", type: " + Integer.toString(filterType, 16));
 649             dbgIndent++;
 650         }
 651 
 652         filtOffset[0]++;
 653 
 654         ber.beginSeq(filterType);
 655 
 656             int[] parens = findRightParen(filter, filtOffset, filtEnd);
 657             encodeFilterList(ber, filter, filterType, parens[0], parens[1]);
 658 
 659         ber.endSeq();
 660 
 661         if (dbg) {
 662             dbgIndent--;
 663         }
 664 
 665     }
 666 
 667     //
 668     // filter at filtOffset[0] - 1 points to a (. Find ) that matches it
 669     // and return substring between the parens. Adjust filtOffset[0] to
 670     // point to char after right paren
 671     //
 672     private static int[] findRightParen(byte[] filter, int filtOffset[], int end)
 673     throws IOException, NamingException {
 674 
 675         int balance = 1;
 676         boolean escape = false;
 677         int nextOffset = filtOffset[0];
 678 
 679         while (nextOffset < end && balance > 0) {
 680             if (!escape) {
 681                 if (filter[nextOffset] == '(')
 682                     balance++;
 683                 else if (filter[nextOffset] == ')')
 684                     balance--;
 685             }
 686             if (filter[nextOffset] == '\\' && !escape)
 687                 escape = true;
 688             else
 689                 escape = false;
 690             if (balance > 0)
 691                 nextOffset++;
 692         }
 693         if (balance != 0) {
 694             throw new InvalidSearchFilterException("Unbalanced parenthesis");
 695         }
 696 
 697         // String tmp = filter.substring(filtOffset[0], nextOffset);
 698 
 699         int[] tmp = new int[] {filtOffset[0], nextOffset};
 700 
 701         filtOffset[0] = nextOffset + 1;
 702 
 703         return tmp;
 704 
 705     }
 706 
 707     //
 708     // Encode filter list of type "(filter1)(filter2)..."
 709     //
 710     private static void encodeFilterList(BerEncoder ber, byte[] filter,
 711         int filterType, int start, int end) throws IOException, NamingException {
 712 
 713         if (dbg) {
 714             dprint("encFilterList: ", filter, start, end);
 715             dbgIndent++;
 716         }
 717 
 718         int filtOffset[] = new int[1];
 719         int listNumber = 0;
 720         for (filtOffset[0] = start; filtOffset[0] < end; filtOffset[0]++) {
 721             if (Character.isSpaceChar((char)filter[filtOffset[0]]))
 722                 continue;
 723 
 724             if ((filterType == LDAP_FILTER_NOT) && (listNumber > 0)) {
 725                 throw new InvalidSearchFilterException(
 726                     "Filter (!) cannot be followed by more than one filters");
 727             }
 728 
 729             if (filter[filtOffset[0]] == '(') {
 730                 continue;
 731             }
 732 
 733             int[] parens = findRightParen(filter, filtOffset, end);
 734 
 735             // add enclosing parens
 736             int len = parens[1]-parens[0];
 737             byte[] newfilter = new byte[len+2];
 738             System.arraycopy(filter, parens[0], newfilter, 1, len);
 739             newfilter[0] = (byte)'(';
 740             newfilter[len+1] = (byte)')';
 741             encodeFilter(ber, newfilter, 0, newfilter.length);
 742 
 743             listNumber++;
 744         }
 745 
 746         if (dbg) {
 747             dbgIndent--;
 748         }
 749 
 750     }
 751 
 752     //
 753     // Encode extensible match
 754     //
 755     private static void encodeExtensibleMatch(BerEncoder ber, byte[] filter,
 756         int matchStart, int matchEnd, int valueStart, int valueEnd)
 757         throws IOException, NamingException {
 758 
 759         boolean matchDN = false;
 760         int colon;
 761         int colon2;
 762         int i;
 763 
 764         ber.beginSeq(LDAP_FILTER_EXT);
 765 
 766             // test for colon separator
 767             if ((colon = indexOf(filter, ':', matchStart, matchEnd)) >= 0) {
 768 
 769                 // test for match DN
 770                 if ((i = indexOf(filter, ":dn", colon, matchEnd)) >= 0) {
 771                     matchDN = true;
 772                 }
 773 
 774                 // test for matching rule
 775                 if (((colon2 = indexOf(filter, ':', colon + 1, matchEnd)) >= 0)
 776                     || (i == -1)) {
 777 
 778                     if (i == colon) {
 779                         ber.encodeOctetString(filter, LDAP_FILTER_EXT_RULE,
 780                             colon2 + 1, matchEnd - (colon2 + 1));
 781 
 782                     } else if ((i == colon2) && (i >= 0)) {
 783                         ber.encodeOctetString(filter, LDAP_FILTER_EXT_RULE,
 784                             colon + 1, colon2 - (colon + 1));
 785 
 786                     } else {
 787                         ber.encodeOctetString(filter, LDAP_FILTER_EXT_RULE,
 788                             colon + 1, matchEnd - (colon + 1));
 789                     }
 790                 }
 791 
 792                 // test for attribute type
 793                 if (colon > matchStart) {
 794                     ber.encodeOctetString(filter,
 795                         LDAP_FILTER_EXT_TYPE, matchStart, colon - matchStart);
 796                 }
 797             } else {
 798                 ber.encodeOctetString(filter, LDAP_FILTER_EXT_TYPE, matchStart,
 799                     matchEnd - matchStart);
 800             }
 801 
 802             ber.encodeOctetString(
 803                 unescapeFilterValue(filter, valueStart, valueEnd),
 804                 LDAP_FILTER_EXT_VAL);
 805 
 806             /*
 807              * This element is defined in RFC-2251 with an ASN.1 DEFAULT tag.
 808              * However, for Active Directory interoperability it is transmitted
 809              * even when FALSE.
 810              */
 811             ber.encodeBoolean(matchDN, LDAP_FILTER_EXT_DN);
 812 
 813         ber.endSeq();
 814     }
 815 
 816     ////////////////////////////////////////////////////////////////////////////
 817     //
 818     // some debug print code that does indenting. Useful for debugging
 819     // the filter generation code
 820     //
 821     ////////////////////////////////////////////////////////////////////////////
 822 
 823     private static final boolean dbg = false;
 824     private static int dbgIndent = 0;
 825 
 826     private static void dprint(String msg) {
 827         dprint(msg, new byte[0], 0, 0);
 828     }
 829 
 830     private static void dprint(String msg, byte[] str) {
 831         dprint(msg, str, 0, str.length);
 832     }
 833 
 834     private static void dprint(String msg, byte[] str, int start, int end) {
 835         String dstr = "  ";
 836         int i = dbgIndent;
 837         while (i-- > 0) {
 838             dstr += "  ";
 839         }
 840         dstr += msg;
 841 
 842         System.err.print(dstr);
 843         for (int j = start; j < end; j++) {
 844             System.err.print((char)str[j]);
 845         }
 846         System.err.println();
 847     }
 848 
 849     /////////////// Constants used for encoding filter //////////////
 850 
 851     static final int LDAP_FILTER_AND = 0xa0;
 852     static final int LDAP_FILTER_OR = 0xa1;
 853     static final int LDAP_FILTER_NOT = 0xa2;
 854     static final int LDAP_FILTER_EQUALITY = 0xa3;
 855     static final int LDAP_FILTER_SUBSTRINGS = 0xa4;
 856     static final int LDAP_FILTER_GE = 0xa5;
 857     static final int LDAP_FILTER_LE = 0xa6;
 858     static final int LDAP_FILTER_PRESENT = 0x87;
 859     static final int LDAP_FILTER_APPROX = 0xa8;
 860     static final int LDAP_FILTER_EXT = 0xa9;            // LDAPv3
 861 
 862     static final int LDAP_FILTER_EXT_RULE = 0x81;       // LDAPv3
 863     static final int LDAP_FILTER_EXT_TYPE = 0x82;       // LDAPv3
 864     static final int LDAP_FILTER_EXT_VAL = 0x83;        // LDAPv3
 865     static final int LDAP_FILTER_EXT_DN = 0x84;         // LDAPv3
 866 
 867     static final int LDAP_SUBSTRING_INITIAL = 0x80;
 868     static final int LDAP_SUBSTRING_ANY = 0x81;
 869     static final int LDAP_SUBSTRING_FINAL = 0x82;
 870 }