/*
 *  Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *  
 *    http://www.apache.org/licenses/LICENSE-2.0
 *  
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License. 
 *  
 */
package org.apache.directory.shared.ldap.filter;


import java.text.ParseException;

import org.apache.directory.shared.ldap.entry.Value;
import org.apache.directory.shared.ldap.entry.client.ClientBinaryValue;
import org.apache.directory.shared.ldap.util.AttributeUtils;
import org.apache.directory.shared.ldap.util.Position;
import org.apache.directory.shared.ldap.util.StringTools;


/**
 * This class parse a Ldap filter. The grammar is given in RFC 4515
 *
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 * @version $Rev$, $Date$
 */
public class FilterParser
{
    /**
     * Creates a filter parser implementation.
     */
    public FilterParser()
    {
    }


    /**
     * Parse an extensible
     * 
     * extensible     = ( attr [":dn"] [':' oid] ":=" assertionvalue )
     *                  / ( [":dn"] ':' oid ":=" assertionvalue )
     * matchingrule   = ":" oid
     */
    private static ExprNode parseExtensible( String attr, String filter, Position pos ) throws ParseException
    {
        ExtensibleNode node = new ExtensibleNode( attr );

        if ( attr != null )
        {
            // First check if we have a ":dn"
            if ( StringTools.areEquals( filter, pos.start, "dn" ) )
            {
                // Set the dnAttributes flag and move forward in the string
                node.setDnAttributes( true );
                pos.start += 2;
            }
            else
            {
                // Push back the ':' 
                pos.start--;
            }

            // Do we have a MatchingRule ?
            if ( StringTools.charAt( filter, pos.start ) == ':' )
            {
                pos.start++;
                int start = pos.start;

                if ( StringTools.charAt( filter, pos.start ) == '=' )
                {
                    pos.start++;

                    // Get the assertionValue
                    node.setValue( parseAssertionValue( filter, pos, true ) );

                    return node;
                }
                else
                {
                    AttributeUtils.parseAttribute( filter, pos, false );

                    node.setMatchingRuleId( filter.substring( start, pos.start ) );

                    if ( StringTools.areEquals( filter, pos.start, ":=" ) )
                    {
                        pos.start += 2;

                        // Get the assertionValue
                        node.setValue( parseAssertionValue( filter, pos, true ) );

                        return node;
                    }
                    else
                    {
                        throw new ParseException( "AssertionValue expected", pos.start );
                    }
                }
            }
            else
            {
                throw new ParseException( "Expected MatchingRule or assertionValue", pos.start );
            }
        }
        else
        {
            boolean oidRequested = false;

            // First check if we have a ":dn"
            if ( StringTools.areEquals( filter, pos.start, ":dn" ) )
            {
                // Set the dnAttributes flag and move forward in the string
                node.setDnAttributes( true );
                pos.start += 3;
            }
            else
            {
                oidRequested = true;
            }

            // Do we have a MatchingRule ?
            if ( StringTools.charAt( filter, pos.start ) == ':' )
            {
                pos.start++;
                int start = pos.start;

                if ( StringTools.charAt( filter, pos.start ) == '=' )
                {
                    if ( oidRequested )
                    {
                        throw new ParseException( "MatchingRule expected", pos.start );
                    }

                    pos.start++;

                    // Get the assertionValue
                    node.setValue( parseAssertionValue( filter, pos, true ) );

                    return node;
                }
                else
                {
                    AttributeUtils.parseAttribute( filter, pos, false );

                    node.setMatchingRuleId( filter.substring( start, pos.start ) );

                    if ( StringTools.areEquals( filter, pos.start, ":=" ) )
                    {
                        pos.start += 2;

                        // Get the assertionValue
                        node.setValue( parseAssertionValue( filter, pos, true ) );

                        return node;
                    }
                    else
                    {
                        throw new ParseException( "AssertionValue expected", pos.start );
                    }
                }
            }
            else
            {
                throw new ParseException( "Expected MatchingRule or assertionValue", pos.start );
            }
        }
    }


    /**
     * An assertion value : 
     * assertionvalue = valueencoding
     * valueencoding  = 0*(normal / escaped)
     * normal         = UTF1SUBSET / UTFMB
     * escaped        = '\' HEX HEX
     * HEX            = '0'-'9' / 'A'-'F' / 'a'-'f'
     * UTF1SUBSET     = %x01-27 / %x2B-5B / %x5D-7F (Everything but '\0', '*', '(', ')' and '\')
     * UTFMB          = UTF2 / UTF3 / UTF4
     * UTF0           = %x80-BF
     * UTF2           = %xC2-DF UTF0
     * UTF3           = %xE0 %xA0-BF UTF0 / %xE1-EC UTF0 UTF0 / %xED %x80-9F UTF0 / %xEE-EF UTF0 UTF0
     * UTF4           = %xF0 %x90-BF UTF0 UTF0 / %xF1-F3 UTF0 UTF0 UTF0 / %xF4 %x80-8F UTF0 UTF0
     * 
     * With the specific constraints (RFC 4515):
     *    "The <valueencoding> rule ensures that the entire filter string is a"
     *    "valid UTF-8 string and provides that the octets that represent the"
     *    "ASCII characters "*" (ASCII 0x2a), "(" (ASCII 0x28), ")" (ASCII"
     *    "0x29), "\" (ASCII 0x5c), and NUL (ASCII 0x00) are represented as a"
     *    "backslash "\" (ASCII 0x5c) followed by the two hexadecimal digits"
     *    "representing the value of the encoded octet."

     * 
     * The incomming String is already transformed from UTF-8 to unicode, so we must assume that the 
     * grammar we have to check is the following :
     * 
     * assertionvalue = valueencoding
     * valueencoding  = 0*(normal / escaped)
     * normal         = unicodeSubset
     * escaped        = '\' HEX HEX
     * HEX            = '0'-'9' / 'A'-'F' / 'a'-'f'
     * unicodeSubset     = %x01-27 / %x2B-5B / %x5D-FFFF
     */
    private static Value<?> parseAssertionValue( String filter, Position pos, boolean preserveEscapedChars ) throws ParseException
    {
        int start = pos.start;
        char c = StringTools.charAt( filter, pos.start );
        
        // Create a buffer big enough to contain the value once converted
        byte[] value = new byte[ filter.length() - pos.start];
        int current = 0;

        do
        {
            if ( StringTools.isUnicodeSubset( c ) )
            {
                value[current++] = (byte)c;
                pos.start++;
            }
            else if ( StringTools.isCharASCII( filter, pos.start, '\\' ) )
            {
                // Maybe an escaped 
                pos.start++;

                // First hex
                if ( StringTools.isHex( filter, pos.start ) )
                {
                    pos.start++;
                }
                else
                {
                    throw new ParseException( "Not a valid escaped value", pos.start );
                }

                // second hex
                if ( StringTools.isHex( filter, pos.start ) )
                {
                    value[current++] = StringTools.getHexValue( filter.charAt( pos.start - 1 ), filter.charAt( pos.start ) );
                    pos.start++;
                }
                else
                {
                    throw new ParseException( "Not a valid escaped value", pos.start );
                }
            }
            else
            {
                // not a valid char, so let's get out
                break;
            }
        }
        while ( ( c = StringTools.charAt( filter, pos.start ) ) != '\0' );

        if ( current != 0 )
        {
            byte[] result = new byte[ current ];
            System.arraycopy( value, 0, result, 0, current );
            
            return new ClientBinaryValue( result );
        }
        else
        {
            return new ClientBinaryValue();
        }
    }


    private static Value<?> parseAssertionValue( String filter, Position pos ) throws ParseException
    {
        return parseAssertionValue( filter, pos, false );
    }


    /**
     * Parse a substring
     */
    private static ExprNode parseSubstring( String attr, Value<?> initial, String filter, Position pos )
        throws ParseException
    {
        if ( StringTools.isCharASCII( filter, pos.start, '*' ) )
        {
            // We have found a '*' : this is a substring
            SubstringNode node = new SubstringNode( attr );

            if ( initial != null && !initial.isNull() )
            {
                // We have a substring starting with a value : val*...
                // Set the initial value. It must be a String
                String initialStr = initial.getString();
                node.setInitial( initialStr );
            }

            pos.start++;

            // 
            while ( true )
            {
                Value<?> assertionValue = parseAssertionValue( filter, pos );

                // Is there anything else but a ')' after the value ?
                if ( StringTools.isCharASCII( filter, pos.start, ')' ) )
                {
                    // Nope : as we have had [initial] '*' (any '*' ) *,
                    // this is the final
                    if ( !assertionValue.isNull() )
                    {
                        String finalStr = assertionValue.getString();
                        node.setFinal( finalStr );
                    }

                    return node;
                }
                else if ( StringTools.isCharASCII( filter, pos.start, '*' ) )
                {
                    // We have a '*' : it's an any
                    // If the value is empty, that means we have more than 
                    // one consecutive '*' : do nothing in this case.
                    if ( !assertionValue.isNull() )
                    {
                        String anyStr = assertionValue.getString();
                        node.addAny( anyStr );
                    }

                    pos.start++;
                }
                else
                {
                    // This is an error
                    throw new ParseException( "Bad substring", pos.start );
                }
            }
        }
        else
        {
            // This is an error
            throw new ParseException( "Bad substring", pos.start );
        }
    }


    /**
     * Here is the grammar to parse :
     * 
     * simple    ::= '=' assertionValue
     * present   ::= '=' '*'
     * substring ::= '=' [initial] any [final]
     * initial   ::= assertionValue
     * any       ::= '*' ( assertionValue '*')*
     * 
     * As we can see, there is an ambiguity in the grammar : attr=* can be
     * seen as a present or as a substring. As stated in the RFC :
     * 
     * "Note that although both the <substring> and <present> productions in"
     * "the grammar above can produce the "attr=*" construct, this construct"
     * "is used only to denote a presence filter." (RFC 4515, 3)
     * 
     * We have also to consider the difference between a substring and the
     * equality node : this last node does not contain a '*'
     *
     * @param attr
     * @param filter
     * @param pos
     * @return
     */
    private static ExprNode parsePresenceEqOrSubstring( String attr, String filter, Position pos )
        throws ParseException
    {
        if ( StringTools.isCharASCII( filter, pos.start, '*' ) )
        {
            // To be a present node, the next char should be a ')'
            pos.start++;

            if ( StringTools.isCharASCII( filter, pos.start, ')' ) )
            {
                // This is a present node
                return new PresenceNode( attr );
            }
            else
            {
                // Definitively a substring with no initial or an error
                // Push back the '*' on the string
                pos.start--;
                return parseSubstring( attr, null, filter, pos );
            }
        }
        else if ( StringTools.isCharASCII( filter, pos.start, ')' ) )
        {
            // An empty equality Node
            return new EqualityNode( attr, new ClientBinaryValue() );
        }
        else
        {
            // A substring or an equality node
            Value<?> value = parseAssertionValue( filter, pos );

            // Is there anything else but a ')' after the value ?
            if ( StringTools.isCharASCII( filter, pos.start, ')' ) )
            {
                // This is an equality node
                return new EqualityNode( attr, value );
            }

            return parseSubstring( attr, value, filter, pos );
        }
    }


    /**
     * Parse the following grammar :
     * item           = simple / present / substring / extensible
     * simple         = attr filtertype assertionvalue
     * filtertype     = '=' / '~=' / '>=' / '<='
     * present        = attr '=' '*'
     * substring      = attr '=' [initial] any [final]
     * extensible     = ( attr [":dn"] [':' oid] ":=" assertionvalue )
     *                  / ( [":dn"] ':' oid ":=" assertionvalue )
     * matchingrule   = ":" oid
     *                  
     * An item starts with an attribute or a colon.
     */
    private static ExprNode parseItem( String filter, Position pos, char c ) throws ParseException
    {
        LeafNode node = null;
        String attr = null;

        if ( c == '\0' )
        {
            throw new ParseException( "Bad char", pos.start );
        }

        if ( c == ':' )
        {
            // If we have a colon, then the item is an extensible one
            return parseExtensible( null, filter, pos );
        }
        else
        {
            // We must have an attribute
            attr = AttributeUtils.parseAttribute( filter, pos, true );

            // Now, we may have a present, substring, simple or an extensible
            c = StringTools.charAt( filter, pos.start );

            switch ( c )
            {
                case '=':
                    // It can be a presence, an equal or a substring
                    pos.start++;
                    return parsePresenceEqOrSubstring( attr, filter, pos );

                case '~':
                    // Approximate node
                    pos.start++;

                    // Check that we have a '='
                    if ( !StringTools.isCharASCII( filter, pos.start, '=' ) )
                    {
                        throw new ParseException( "Expecting a '=' ", pos.start );
                    }

                    pos.start++;

                    // Parse the value and create the node
                    node = new ApproximateNode( attr, parseAssertionValue( filter, pos ) );
                    return node;

                case '>':
                    // Greater or equal node
                    pos.start++;

                    // Check that we have a '='
                    if ( !StringTools.isCharASCII( filter, pos.start, '=' ) )
                    {
                        throw new ParseException( "Expecting a '=' ", pos.start );
                    }

                    pos.start++;

                    // Parse the value and create the node
                    node = new GreaterEqNode( attr, parseAssertionValue( filter, pos ) );
                    return node;

                case '<':
                    // Less or equal node
                    pos.start++;

                    // Check that we have a '='
                    if ( !StringTools.isCharASCII( filter, pos.start, '=' ) )
                    {
                        throw new ParseException( "Expecting a '=' ", pos.start );
                    }

                    pos.start++;

                    // Parse the value and create the node
                    node = new LessEqNode( attr, parseAssertionValue( filter, pos ) );
                    return node;

                case ':':
                    // An extensible node
                    pos.start++;
                    return parseExtensible( attr, filter, pos );

                default:
                    // This is an error
                    throw new ParseException( "An item is expected", pos.start );
            }
        }
    }


    /**
     * Parse AND, OR and NOT nodes :
     * 
     * and            = '&' filterlist
     * or             = '|' filterlist
     * not            = '!' filter
     * filterlist     = 1*filter
     * 
     * @return
     */
    private static ExprNode parseBranchNode( ExprNode node, String filter, Position pos ) throws ParseException
    {
        BranchNode bNode = ( BranchNode ) node;

        // We must have at least one filter
        ExprNode child = parseFilterInternal( filter, pos );

        // Add the child to the node children
        bNode.addNode( child );

        // Now, iterate recusively though all the remaining filters, if any
        while ( ( child = parseFilterInternal( filter, pos ) ) != null )
        {
            // Add the child to the node children
            bNode.addNode( child );
        }

        return node;
    }


    /**
     * filtercomp     = and / or / not / item
     * and            = '&' filterlist
     * or             = '|' filterlist
     * not            = '!' filter
     * item           = simple / present / substring / extensible
     * simple         = attr filtertype assertionvalue
     * present        = attr EQUALS ASTERISK
     * substring      = attr EQUALS [initial] any [final]
     * extensible     = ( attr [dnattrs]
     *                    [matchingrule] COLON EQUALS assertionvalue )
     *                    / ( [dnattrs]
     *                         matchingrule COLON EQUALS assertionvalue )
     */
    private static ExprNode parseFilterComp( String filter, Position pos ) throws ParseException
    {
        ExprNode node = null;

        if ( pos.start == pos.length )
        {
            throw new ParseException( "Empty filterComp", pos.start );
        }

        char c = StringTools.charAt( filter, pos.start );

        switch ( c )
        {
            case '&':
                // This is a AND node
                pos.start++;
                node = new AndNode();
                parseBranchNode( node, filter, pos );
                break;

            case '|':
                // This is an OR node
                pos.start++;
                node = new OrNode();
                parseBranchNode( node, filter, pos );
                break;

            case '!':
                // This is a NOT node
                pos.start++;
                node = new NotNode();
                parseBranchNode( node, filter, pos );
                break;

            default:
                // This is an item
                node = parseItem( filter, pos, c );
                break;

        }

        return node;
    }


    /**
     * Pasre the grammar rule :
     * filter ::= '(' filterComp ')'
     */
    private static ExprNode parseFilterInternal( String filter, Position pos ) throws ParseException
    {
        // Check for the left '('
        if ( !StringTools.isCharASCII( filter, pos.start, '(' ) )
        {
            // No more node, get out
            if ( ( pos.start == 0 ) && ( pos.length != 0 ) )
            {
                throw new ParseException( "No '(' at the begining of the filter", 0 );
            }
            else
            {
                return null;
            }
        }

        pos.start++;

        // parse the filter component
        ExprNode node = parseFilterComp( filter, pos );

        if ( node == null )
        {
            throw new ParseException( "Bad filter", pos.start );
        }

        // Check that we have a right ')'
        if ( !StringTools.isCharASCII( filter, pos.start, ')' ) )
        {
            throw new ParseException( "The filter has no right parenthese", pos.start );
        }

        pos.start++;

        return node;
    }


    /**
     * @see FilterParser#parse(String)
     */
    public static ExprNode parse( String filter ) throws ParseException
    {
        // The filter must not be null. This is a defensive test
        if ( StringTools.isEmpty( filter ) )
        {
            throw new ParseException( "Empty filter", 0 );
        }

        Position pos = new Position();
        pos.start = 0;
        pos.end = 0;
        pos.length = filter.length();

        return parseFilterInternal( filter, pos );
    }


    public void setFilterParserMonitor( FilterParserMonitor monitor )
    {
    }
}