/*

 * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package com.sun.jndi.ldap;

import javax.naming.NamingException;

import javax.naming.directory.InvalidSearchFilterException;

import java.io.IOException;

/**

 * LDAP (RFC-1960) and LDAPv3 (RFC-2254) search filters.

 *

 * @author Xuelei Fan

 * @author Vincent Ryan

 * @author Jagane Sundar

 * @author Rosanna Lee

 */

final class Filter {

    /**

     * First convert filter string into byte[].

     * For LDAP v3, the conversion uses Unicode -> UTF8

     * For LDAP v2, the conversion uses Unicode -> ISO 8859 (Latin-1)

     *

     * Then parse the byte[] as a filter, converting \hh to

     * a single byte, and encoding the resulting filter

     * into the supplied BER buffer

     */

    static void encodeFilterString(BerEncoder ber, String filterStr,

        boolean isLdapv3) throws IOException, NamingException {

            throw new InvalidSearchFilterException("Empty filter");

        }

        byte[] filter;

        int filterLen;

        if (isLdapv3) {

            filter = filterStr.getBytes("UTF8");

        } else {

            filter = filterStr.getBytes("8859_1");

        }

        filterLen = filter.length;

        if (dbg) {

            dbgIndent = 0;

            System.err.println("String filter: " + filterStr);

            System.err.println("size: " + filterLen);

            dprint("original: ", filter, 0, filterLen);

        }

        encodeFilter(ber, filter, 0, filterLen);

    }

    private static void encodeFilter(BerEncoder ber, byte[] filter,

        int filterStart, int filterEnd) throws IOException, NamingException {

        if (dbg) {

            dprint("encFilter: ",  filter, filterStart, filterEnd);

            dbgIndent++;

        }

        if ((filterEnd - filterStart) <= 0) {

            throw new InvalidSearchFilterException("Empty filter");

        }

        int nextOffset;

        int parens, balance;

        boolean escape;

        parens = 0;

        int filtOffset[] = new int[1];

        for (filtOffset[0] = filterStart; filtOffset[0] < filterEnd;) {

            switch (filter[filtOffset[0]]) {

            case '(':

                filtOffset[0]++;

                parens++;

                switch (filter[filtOffset[0]]) {

                case '&':

                    encodeComplexFilter(ber, filter,

                        LDAP_FILTER_AND, filtOffset, filterEnd);

                    // filtOffset[0] has pointed to char after right paren

                    parens--;

                    break;

                case '|':

                    encodeComplexFilter(ber, filter,

                        LDAP_FILTER_OR, filtOffset, filterEnd);

                    // filtOffset[0] has pointed to char after right paren

                    parens--;

                    break;

                case '!':

                    encodeComplexFilter(ber, filter,

                        LDAP_FILTER_NOT, filtOffset, filterEnd);

                    // filtOffset[0] has pointed to char after right paren

                    parens--;

                    break;

                default:

                    balance = 1;

                    escape = false;

                    nextOffset = filtOffset[0];

                    while (nextOffset < filterEnd && balance > 0) {

                        if (!escape) {

                            if (filter[nextOffset] == '(')

                                balance++;

                            else if (filter[nextOffset] == ')')

                                balance--;

                        }

                        if (filter[nextOffset] == '\\' && !escape)

                            escape = true;

                        else

                            escape = false;

                        if (balance > 0)

                            nextOffset++;

                    }

                    if (balance != 0)

                        throw new InvalidSearchFilterException(

                                  "Unbalanced parenthesis");

                    encodeSimpleFilter(ber, filter, filtOffset[0], nextOffset);

                    // points to the char after right paren.

                    filtOffset[0] = nextOffset + 1;

                    parens--;

                    break;

                }

                break;

            case ')':

                //

                // End of sequence

                //

                ber.endSeq();

                filtOffset[0]++;

                parens--;

                break;

            case ' ':

                filtOffset[0]++;

                break;

            default:    // assume simple type=value filter

                encodeSimpleFilter(ber, filter, filtOffset[0], filterEnd);

                filtOffset[0] = filterEnd; // force break from outer

                break;

            }

            if (parens < 0) {

                throw new InvalidSearchFilterException(

                                                "Unbalanced parenthesis");

            }

        }

        if (parens != 0) {

            throw new InvalidSearchFilterException("Unbalanced parenthesis");

        }

        if (dbg) {

            dbgIndent--;

        }

    }

    /**

     * convert character 'c' that represents a hexadecimal digit to an integer.

     * if 'c' is not a hexadecimal digit [0-9A-Fa-f], -1 is returned.

     * otherwise the converted value is returned.

     */

    private static int hexchar2int( byte c ) {

        if ( c >= '0' && c <= '9' ) {

            return( c - '0' );

        }

        if ( c >= 'A' && c <= 'F' ) {

            return( c - 'A' + 10 );

        }

        if ( c >= 'a' && c <= 'f' ) {

            return( c - 'a' + 10 );

        }

        return( -1 );

    }

    // called by the LdapClient.compare method

    static byte[] unescapeFilterValue(byte[] orig, int start, int end)

        throws NamingException {

        boolean escape = false, escStart = false;

        int ival;

        byte ch;

        if (dbg) {

            dprint("unescape: " , orig, start, end);

        }

        int len = end - start;

        byte tbuf[] = new byte[len];

        int j = 0;

        for (int i = start; i < end; i++) {

            ch = orig[i];

            if (escape) {

                // Try LDAP V3 escape (\xx)

                if ((ival = hexchar2int(ch)) < 0) {

                    /**

                     * If there is no hex char following a '\' when

                     * parsing a LDAP v3 filter (illegal by v3 way)

                     * we fallback to the way we unescape in v2.

                     */

                    if (escStart) {

                        // V2: \* \( \)

                        escape = false;

                        tbuf[j++] = ch;

                    } else {

                        // escaping already started but we can't find 2nd hex

                        throw new InvalidSearchFilterException("invalid escape sequence: " + orig);

                    }

                } else {

                    if (escStart) {

                        tbuf[j] = (byte)(ival<<4);

                        escStart = false;

                    } else {

                        tbuf[j++] |= (byte)ival;

                        escape = false;

                    }

                }

            } else if (ch != '\\') {

                tbuf[j++] = ch;

                escape = false;

            } else {

                escStart = escape = true;

            }

        }

        byte[] answer = new byte[j];

        System.arraycopy(tbuf, 0, answer, 0, j);

        if (dbg) {

            Ber.dumpBER(System.err, "", answer, 0, j);

        }

        return answer;

    }

    private static int indexOf(byte[] str, char ch, int start, int end) {

        for (int i = start; i < end; i++) {

            if (str[i] == ch)

                return i;

        }

        return -1;

    }

    private static int indexOf(byte[] str, String target, int start, int end) {

        int where = indexOf(str, target.charAt(0), start, end);

        if (where >= 0) {

            for (int i = 1; i < target.length(); i++) {

                if (str[where+i] != target.charAt(i)) {

                    return -1;

                }

            }

        }

        return where;

    }

    private static int findUnescaped(byte[] str, char ch, int start, int end) {

        while (start < end) {

            int where = indexOf(str, ch, start, end);

            /*

             * Count the immediate preceding '\' to find out if

             * this is an escaped '*'. This is a made-up way for

             * parsing an escaped '*' in v2. This is how the other leading

             * SDK vendors interpret v2.

             * For v3 we fallback to the way we parse "\*" in v2.

             * It's not legal in v3 to use "\*" to escape '*'; the right

             * way is to use "\2a" instead.

             */

            int backSlashPos;

            int backSlashCnt = 0;

            for (backSlashPos = where - 1;

                    ((backSlashPos >= start) && (str[backSlashPos] == '\\'));

                    backSlashPos--, backSlashCnt++);

            // if at start of string, or not there at all, or if not escaped

            if (where == start || where == -1 || ((backSlashCnt % 2) == 0))

                return where;

            // start search after escaped star

            start = where + 1;

        }

        return -1;

    }

    private static void encodeSimpleFilter(BerEncoder ber, byte[] filter,

        int filtStart, int filtEnd) throws IOException, NamingException {

        if (dbg) {

            dprint("encSimpleFilter: ", filter, filtStart, filtEnd);

            dbgIndent++;

        }

        String type, value;

        int valueStart, valueEnd, typeStart, typeEnd;

        int eq;

        if ((eq = indexOf(filter, '=', filtStart, filtEnd)) == -1) {

            throw new InvalidSearchFilterException("Missing 'equals'");

        }

        valueStart = eq + 1;        // value starts after equal sign

        valueEnd = filtEnd;

        typeStart = filtStart;      // beginning of string

        int ftype;

        switch (filter[eq - 1]) {

        case '<':

            ftype = LDAP_FILTER_LE;

            typeEnd = eq - 1;

            break;

        case '>':

            ftype = LDAP_FILTER_GE;

            typeEnd = eq - 1;

            break;

        case '~':

            ftype = LDAP_FILTER_APPROX;

            typeEnd = eq - 1;

            break;

        case ':':

            ftype = LDAP_FILTER_EXT;

            typeEnd = eq - 1;

            break;

        default:

            typeEnd = eq;

            //initializing ftype to make the compiler happy

            ftype = 0x00;

            break;

        }

        if (dbg) {

            System.err.println("type: " + typeStart + ", " + typeEnd);

            System.err.println("value: " + valueStart + ", " + valueEnd);

        }

        // check validity of type

        //

        // RFC4512 defines the type as the following ABNF:

        //     attr = attributedescription

        //     attributedescription = attributetype options

        //     attributetype = oid

        //     oid = descr / numericoid

        //     descr = keystring

        //     keystring = leadkeychar *keychar

        //     leadkeychar = ALPHA

        //     keychar = ALPHA / DIGIT / HYPHEN

        //     numericoid = number 1*( DOT number )

        //     number  = DIGIT / ( LDIGIT 1*DIGIT )

        //     options = *( SEMI option )

        //     option = 1*keychar

        //

        // And RFC4515 defines the extensible type as the following ABNF:

        //     attr [dnattrs] [matchingrule] / [dnattrs] matchingrule

        int optionsStart = -1;

        int extensibleStart = -1;

        if ((filter[typeStart] >= '0' && filter[typeStart] <= '9') ||

            (filter[typeStart] >= 'A' && filter[typeStart] <= 'Z') ||

            (filter[typeStart] >= 'a' && filter[typeStart] <= 'z')) {

            boolean isNumericOid =

                filter[typeStart] >= '0' && filter[typeStart] <= '9';

            for (int i = typeStart + 1; i < typeEnd; i++) {

                // ';' is an indicator of attribute options

                if (filter[i] == ';') {

                    if (isNumericOid && filter[i - 1] == '.') {

                        throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                    }

                    // attribute options

                    optionsStart = i;

                    break;

                }

                // ':' is an indicator of extensible rules

                if (filter[i] == ':' && ftype == LDAP_FILTER_EXT) {

                    if (isNumericOid && filter[i - 1] == '.') {

                        throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                    }

                    // extensible matching

                    extensibleStart = i;

                    break;

                }

                if (isNumericOid) {

                    // numeric object identifier

                    if ((filter[i] == '.' && filter[i - 1] == '.') ||

                        (filter[i] != '.' &&

                            !(filter[i] >= '0' && filter[i] <= '9'))) {

                        throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                    }

                } else {

                    // descriptor

                    // The underscore ("_") character is not allowed by

                    // the LDAP specification. We allow it here to

                    // tolerate the incorrect use in practice.

                    if (filter[i] != '-' && filter[i] != '_' &&

                        !(filter[i] >= '0' && filter[i] <= '9') &&

                        !(filter[i] >= 'A' && filter[i] <= 'Z') &&

                        !(filter[i] >= 'a' && filter[i] <= 'z')) {

                        throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                    }

                }

            }

        } else if (ftype == LDAP_FILTER_EXT && filter[typeStart] == ':') {

            // extensible matching

            extensibleStart = typeStart;

        } else {

            throw new InvalidSearchFilterException(

                                    "invalid attribute description");

        }

        // check attribute options

        if (optionsStart > 0) {

            for (int i = optionsStart + 1; i < typeEnd; i++) {

                if (filter[i] == ';') {

                    if (filter[i - 1] == ';') {

                        throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                    }

                    continue;

                }

                // ':' is an indicator of extensible rules

                if (filter[i] == ':' && ftype == LDAP_FILTER_EXT) {

                    if (filter[i - 1] == ';') {

                        throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                    }

                    // extensible matching

                    extensibleStart = i;

                    break;

                }

                // The underscore ("_") character is not allowed by

                // the LDAP specification. We allow it here to

                // tolerate the incorrect use in practice.

                if (filter[i] != '-' && filter[i] != '_' &&

                        !(filter[i] >= '0' && filter[i] <= '9') &&

                        !(filter[i] >= 'A' && filter[i] <= 'Z') &&

                        !(filter[i] >= 'a' && filter[i] <= 'z')) {

                    throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                }

            }

        }

        // check extensible matching

        if (extensibleStart > 0) {

            boolean isMatchingRule = false;

            for (int i = extensibleStart + 1; i < typeEnd; i++) {

                if (filter[i] == ':') {

                    throw new InvalidSearchFilterException(

                                    "invalid attribute description");

                } else if ((filter[i] >= '0' && filter[i] <= '9') ||

                           (filter[i] >= 'A' && filter[i] <= 'Z') ||

                           (filter[i] >= 'a' && filter[i] <= 'z')) {

                    boolean isNumericOid = filter[i] >= '0' && filter[i] <= '9';

                    i++;

                    for (int j = i; j < typeEnd; j++, i++) {

                        // allows no more than two extensible rules

                        if (filter[j] == ':') {

                            if (isMatchingRule) {

                                throw new InvalidSearchFilterException(

                                            "invalid attribute description");

                            }

                            if (isNumericOid && filter[j - 1] == '.') {

                                throw new InvalidSearchFilterException(

                                            "invalid attribute description");

                            }

                            isMatchingRule = true;

                            break;

                        }

                        if (isNumericOid) {