001/*
002 *  Licensed to the Apache Software Foundation (ASF) under one
003 *  or more contributor license agreements.  See the NOTICE file
004 *  distributed with this work for additional information
005 *  regarding copyright ownership.  The ASF licenses this file
006 *  to you under the Apache License, Version 2.0 (the
007 *  "License"); you may not use this file except in compliance
008 *  with the License.  You may obtain a copy of the License at
009 *
010 *    http://www.apache.org/licenses/LICENSE-2.0
011 *
012 *  Unless required by applicable law or agreed to in writing,
013 *  software distributed under the License is distributed on an
014 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 *  KIND, either express or implied.  See the License for the
016 *  specific language governing permissions and limitations
017 *  under the License.
018 *
019 */
020package org.apache.directory.api.ldap.model.filter;
021
022
023import java.text.ParseException;
024
025import org.apache.directory.api.i18n.I18n;
026import org.apache.directory.api.ldap.model.entry.AttributeUtils;
027import org.apache.directory.api.ldap.model.entry.BinaryValue;
028import org.apache.directory.api.ldap.model.entry.StringValue;
029import org.apache.directory.api.ldap.model.entry.Value;
030import org.apache.directory.api.ldap.model.exception.LdapException;
031import org.apache.directory.api.ldap.model.schema.AttributeType;
032import org.apache.directory.api.ldap.model.schema.SchemaManager;
033import org.apache.directory.api.util.Chars;
034import org.apache.directory.api.util.Hex;
035import org.apache.directory.api.util.Position;
036import org.apache.directory.api.util.Strings;
037import org.apache.directory.api.util.Unicode;
038
039
040/**
041 * This class parse a Ldap filter. The grammar is given in RFC 4515
042 *
043 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
044 */
045public final class FilterParser
046{
047    private FilterParser()
048    {
049    }
050
051
052    /**
053     * Parse an extensible
054     *
055     * extensible     = ( attr [":dn"] [':' oid] ":=" assertionvalue )
056     *                  / ( [":dn"] ':' oid ":=" assertionvalue )
057     * matchingrule   = ":" oid
058     */
059    private static ExprNode parseExtensible( SchemaManager schemaManager, String attribute, byte[] filter,
060        Position pos, boolean relaxed ) throws LdapException, ParseException
061    {
062        ExtensibleNode node;
063
064        if ( schemaManager != null )
065        {
066            AttributeType attributeType = schemaManager.getAttributeType( attribute );
067
068            if ( attributeType != null )
069            {
070                node = new ExtensibleNode( attributeType );
071            }
072            else
073            {
074                return UndefinedNode.UNDEFINED_NODE;
075            }
076        }
077        else
078        {
079            node = new ExtensibleNode( attribute );
080        }
081
082        if ( attribute != null )
083        {
084            // First check if we have a ":dn"
085            if ( Strings.areEquals( filter, pos.start, "dn" ) >= 0 )
086            {
087                // Set the dnAttributes flag and move forward in the string
088                node.setDnAttributes( true );
089                pos.start += 2;
090            }
091            else
092            {
093                // Push back the ':'
094                pos.start--;
095            }
096
097            // Do we have a MatchingRule ?
098            if ( Strings.byteAt( filter, pos.start ) == ':' )
099            {
100                pos.start++;
101
102                if ( Strings.byteAt( filter, pos.start ) == '=' )
103                {
104                    pos.start++;
105
106                    // Get the assertionValue
107                    node.setValue( parseAssertionValue( schemaManager, filter, pos ) );
108
109                    return node;
110                }
111                else
112                {
113                    String matchingRuleId = AttributeUtils.parseAttribute( filter, pos, false, relaxed );
114
115                    node.setMatchingRuleId( matchingRuleId );
116
117                    if ( Strings.areEquals( filter, pos.start, ":=" ) >= 0 )
118                    {
119                        pos.start += 2;
120
121                        // Get the assertionValue
122                        node.setValue( parseAssertionValue( schemaManager, filter, pos ) );
123
124                        return node;
125                    }
126                    else
127                    {
128                        throw new ParseException( I18n.err( I18n.ERR_04146 ), pos.start );
129                    }
130                }
131            }
132            else
133            {
134                throw new ParseException( I18n.err( I18n.ERR_04147 ), pos.start );
135            }
136        }
137        else
138        {
139            // No attribute
140            boolean oidRequested = false;
141
142            // First check if we have a ":dn"
143            if ( Strings.areEquals( filter, pos.start, ":dn" ) >= 0 )
144            {
145                // Set the dnAttributes flag and move forward in the string
146                node.setDnAttributes( true );
147                pos.start += 3;
148            }
149            else
150            {
151                oidRequested = true;
152            }
153
154            // Do we have a MatchingRule ?
155            if ( Strings.byteAt( filter, pos.start ) == ':' )
156            {
157                pos.start++;
158
159                if ( Strings.byteAt( filter, pos.start ) == '=' )
160                {
161                    if ( oidRequested )
162                    {
163                        throw new ParseException( I18n.err( I18n.ERR_04148 ), pos.start );
164                    }
165
166                    pos.start++;
167
168                    // Get the assertionValue
169                    node.setValue( parseAssertionValue( schemaManager, null, filter, pos ) );
170
171                    return node;
172                }
173                else
174                {
175                    String matchingRuleId = AttributeUtils.parseAttribute( filter, pos, false, relaxed );
176
177                    node.setMatchingRuleId( matchingRuleId );
178
179                    if ( Strings.areEquals( filter, pos.start, ":=" ) >= 0 )
180                    {
181                        pos.start += 2;
182
183                        // Get the assertionValue
184                        node.setValue( parseAssertionValue( schemaManager, null, filter, pos ) );
185
186                        return node;
187                    }
188                    else
189                    {
190                        throw new ParseException( I18n.err( I18n.ERR_04146 ), pos.start );
191                    }
192                }
193            }
194            else
195            {
196                throw new ParseException( I18n.err( I18n.ERR_04147 ), pos.start );
197            }
198        }
199    }
200
201
202    /**
203     * An assertion value :
204     * assertionvalue = valueencoding
205     * valueencoding  = 0*(normal / escaped)
206     * normal         = UTF1SUBSET / UTFMB
207     * escaped        = '\' HEX HEX
208     * HEX            = '0'-'9' / 'A'-'F' / 'a'-'f'
209     * UTF1SUBSET     = %x01-27 / %x2B-5B / %x5D-7F (Everything but '\0', '*', '(', ')' and '\')
210     * UTFMB          = UTF2 / UTF3 / UTF4
211     * UTF0           = %x80-BF
212     * UTF2           = %xC2-DF UTF0
213     * UTF3           = %xE0 %xA0-BF UTF0 / %xE1-EC UTF0 UTF0 / %xED %x80-9F UTF0 / %xEE-EF UTF0 UTF0
214     * UTF4           = %xF0 %x90-BF UTF0 UTF0 / %xF1-F3 UTF0 UTF0 UTF0 / %xF4 %x80-8F UTF0 UTF0
215     *
216     * With the specific constraints (RFC 4515):
217     *    "The <valueencoding> rule ensures that the entire filter string is a"
218     *    "valid UTF-8 string and provides that the octets that represent the"
219     *    "ASCII characters "*" (ASCII 0x2a), "(" (ASCII 0x28), ")" (ASCII"
220     *    "0x29), "\" (ASCII 0x5c), and NUL (ASCII 0x00) are represented as a"
221     *    "backslash "\" (ASCII 0x5c) followed by the two hexadecimal digits"
222     *    "representing the value of the encoded octet."
223     *
224     * The incoming String is already transformed from UTF-8 to unicode, so we must assume that the
225     * grammar we have to check is the following :
226     *
227     * assertionvalue = valueencoding
228     * valueencoding  = 0*(normal / escaped)
229     * normal         = unicodeSubset
230     * escaped        = '\' HEX HEX
231     * HEX            = '0'-'9' / 'A'-'F' / 'a'-'f'
232     * unicodeSubset     = %x01-27 / %x2B-5B / %x5D-FFFF
233     * @throws LdapInvalidAttributeValueException 
234     */
235    private static Value<?> parseAssertionValue( SchemaManager schemaManager, String attribute, byte[] filter,
236        Position pos ) throws ParseException
237    {
238        byte b = Strings.byteAt( filter, pos.start );
239
240        // Create a buffer big enough to contain the value once converted
241        byte[] value = new byte[filter.length - pos.start];
242        int current = 0;
243
244        do
245        {
246            if ( Unicode.isUnicodeSubset( b ) )
247            {
248                value[current++] = b;
249                pos.start++;
250            }
251            else if ( Strings.isCharASCII( filter, pos.start, '\\' ) )
252            {
253                // Maybe an escaped
254                pos.start++;
255
256                // First hex
257                if ( Chars.isHex( filter, pos.start ) )
258                {
259                    pos.start++;
260                }
261                else
262                {
263                    throw new ParseException( I18n.err( I18n.ERR_04149 ), pos.start );
264                }
265
266                // second hex
267                if ( Chars.isHex( filter, pos.start ) )
268                {
269                    value[current++] = Hex.getHexValue( filter[pos.start - 1], filter[pos.start] );
270                    pos.start++;
271                }
272                else
273                {
274                    throw new ParseException( I18n.err( I18n.ERR_04149 ), pos.start );
275                }
276            }
277            else
278            {
279                // not a valid char, so let's get out
280                break;
281            }
282
283            b = Strings.byteAt( filter, pos.start );
284        }
285        while ( b != '\0' );
286
287        if ( current != 0 )
288        {
289            byte[] result = new byte[current];
290            System.arraycopy( value, 0, result, 0, current );
291
292            if ( schemaManager != null )
293            {
294                AttributeType attributeType = schemaManager.getAttributeType( attribute );
295
296                if ( attributeType == null )
297                {
298                    return new BinaryValue( result );
299                }
300
301                if ( attributeType.getSyntax().isHumanReadable() )
302                {
303                    return new StringValue( Strings.utf8ToString( result ) );
304                }
305                else
306                {
307                    return new BinaryValue( result );
308                }
309            }
310            else
311            {
312                return new BinaryValue( result );
313            }
314        }
315        else
316        {
317            if ( schemaManager != null )
318            {
319                AttributeType attributeType = schemaManager.getAttributeType( attribute );
320
321                if ( attributeType.getEquality().getSyntax().isHumanReadable() )
322                {
323                    return new StringValue( ( String ) null );
324                }
325                else
326                {
327                    return new BinaryValue( null );
328                }
329            }
330            else
331            {
332                return new BinaryValue( ( byte[] ) null );
333            }
334        }
335    }
336
337
338    /**
339     * An assertion value :
340     * assertionvalue = valueencoding
341     * valueencoding  = 0*(normal / escaped)
342     * normal         = UTF1SUBSET / UTFMB
343     * escaped        = '\' HEX HEX
344     * HEX            = '0'-'9' / 'A'-'F' / 'a'-'f'
345     * UTF1SUBSET     = %x01-27 / %x2B-5B / %x5D-7F (Everything but '\0', '*', '(', ')' and '\')
346     * UTFMB          = UTF2 / UTF3 / UTF4
347     * UTF0           = %x80-BF
348     * UTF2           = %xC2-DF UTF0
349     * UTF3           = %xE0 %xA0-BF UTF0 / %xE1-EC UTF0 UTF0 / %xED %x80-9F UTF0 / %xEE-EF UTF0 UTF0
350     * UTF4           = %xF0 %x90-BF UTF0 UTF0 / %xF1-F3 UTF0 UTF0 UTF0 / %xF4 %x80-8F UTF0 UTF0
351     *
352     * With the specific constraints (RFC 4515):
353     *    "The <valueencoding> rule ensures that the entire filter string is a"
354     *    "valid UTF-8 string and provides that the octets that represent the"
355     *    "ASCII characters "*" (ASCII 0x2a), "(" (ASCII 0x28), ")" (ASCII"
356     *    "0x29), "\" (ASCII 0x5c), and NUL (ASCII 0x00) are represented as a"
357     *    "backslash "\" (ASCII 0x5c) followed by the two hexadecimal digits"
358     *    "representing the value of the encoded octet."
359     *
360     * The incoming String is already transformed from UTF-8 to unicode, so we must assume that the
361     * grammar we have to check is the following :
362     *
363     * assertionvalue = valueencoding
364     * valueencoding  = 0*(normal / escaped)
365     * normal         = unicodeSubset
366     * escaped        = '\' HEX HEX
367     * HEX            = '0'-'9' / 'A'-'F' / 'a'-'f'
368     * unicodeSubset     = %x01-27 / %x2B-5B / %x5D-FFFF
369     */
370    private static Value<?> parseAssertionValue( SchemaManager schemaManager, byte[] filter, Position pos )
371        throws ParseException
372    {
373        byte b = Strings.byteAt( filter, pos.start );
374
375        // Create a buffer big enough to contain the value once converted
376        byte[] value = new byte[filter.length - pos.start];
377        int current = 0;
378
379        do
380        {
381            if ( Unicode.isUnicodeSubset( b ) )
382            {
383                value[current++] = b;
384                pos.start++;
385            }
386            else if ( Strings.isCharASCII( filter, pos.start, '\\' ) )
387            {
388                // Maybe an escaped
389                pos.start++;
390
391                // First hex
392                if ( Chars.isHex( filter, pos.start ) )
393                {
394                    pos.start++;
395                }
396                else
397                {
398                    throw new ParseException( I18n.err( I18n.ERR_04149 ), pos.start );
399                }
400
401                // second hex
402                if ( Chars.isHex( filter, pos.start ) )
403                {
404                    value[current++] = Hex.getHexValue( filter[pos.start - 1], filter[pos.start] );
405                    pos.start++;
406                }
407                else
408                {
409                    throw new ParseException( I18n.err( I18n.ERR_04149 ), pos.start );
410                }
411            }
412            else
413            {
414                // not a valid char, so let's get out
415                break;
416            }
417
418            b = Strings.byteAt( filter, pos.start );
419        }
420        while ( b != '\0' );
421
422        if ( current != 0 )
423        {
424            byte[] result = new byte[current];
425            System.arraycopy( value, 0, result, 0, current );
426
427            return new BinaryValue( result );
428        }
429        else
430        {
431            return new BinaryValue( null );
432        }
433    }
434
435
436    /**
437     * Parse a substring
438     */
439    private static ExprNode parseSubstring( SchemaManager schemaManager, String attribute, Value<?> initial,
440        byte[] filter, Position pos )
441        throws ParseException, LdapException
442    {
443        if ( Strings.isCharASCII( filter, pos.start, '*' ) )
444        {
445            // We have found a '*' : this is a substring
446            SubstringNode node;
447
448            if ( schemaManager != null )
449            {
450                AttributeType attributeType = schemaManager.lookupAttributeTypeRegistry( attribute );
451
452                if ( attributeType != null )
453                {
454                    node = new SubstringNode( schemaManager.lookupAttributeTypeRegistry( attribute ) );
455                }
456                else
457                {
458                    return null;
459                }
460            }
461            else
462            {
463                node = new SubstringNode( attribute );
464            }
465
466            if ( ( initial != null ) && !initial.isNull() )
467            {
468                // We have a substring starting with a value : val*...
469                // Set the initial value. It must be a String
470                String initialStr = initial.getString();
471                node.setInitial( initialStr );
472            }
473
474            pos.start++;
475
476            //
477            while ( true )
478            {
479                Value<?> assertionValue = parseAssertionValue( schemaManager, attribute, filter, pos );
480
481                // Is there anything else but a ')' after the value ?
482                if ( Strings.isCharASCII( filter, pos.start, ')' ) )
483                {
484                    // Nope : as we have had [initial] '*' (any '*' ) *,
485                    // this is the final
486                    if ( !assertionValue.isNull() )
487                    {
488                        String finalStr = assertionValue.getString();
489                        node.setFinal( finalStr );
490                    }
491
492                    return node;
493                }
494                else if ( Strings.isCharASCII( filter, pos.start, '*' ) )
495                {
496                    // We have a '*' : it's an any
497                    // If the value is empty, that means we have more than
498                    // one consecutive '*' : do nothing in this case.
499                    if ( !assertionValue.isNull() )
500                    {
501                        String anyStr = assertionValue.getString();
502                        node.addAny( anyStr );
503                    }
504
505                    pos.start++;
506                }
507                else
508                {
509                    // This is an error
510                    throw new ParseException( I18n.err( I18n.ERR_04150 ), pos.start );
511                }
512            }
513        }
514        else
515        {
516            // This is an error
517            throw new ParseException( I18n.err( I18n.ERR_04150 ), pos.start );
518        }
519    }
520
521
522    /**
523     * Here is the grammar to parse :
524     *
525     * simple    ::= '=' assertionValue
526     * present   ::= '=' '*'
527     * substring ::= '=' [initial] any [final]
528     * initial   ::= assertionValue
529     * any       ::= '*' ( assertionValue '*')*
530     *
531     * As we can see, there is an ambiguity in the grammar : attr=* can be
532     * seen as a present or as a substring. As stated in the RFC :
533     *
534     * "Note that although both the <substring> and <present> productions in"
535     * "the grammar above can produce the "attr=*" construct, this construct"
536     * "is used only to denote a presence filter." (RFC 4515, 3)
537     *
538     * We have also to consider the difference between a substring and the
539     * equality node : this last node does not contain a '*'
540     *
541     * @param attributeType
542     * @param filter
543     * @param pos
544     * @return
545     */
546    @SuppressWarnings(
547        { "rawtypes", "unchecked" })
548    private static ExprNode parsePresenceEqOrSubstring( SchemaManager schemaManager, String attribute, byte[] filter,
549        Position pos )
550        throws ParseException, LdapException
551    {
552        if ( Strings.isCharASCII( filter, pos.start, '*' ) )
553        {
554            // To be a present node, the next char should be a ')'
555            pos.start++;
556
557            if ( Strings.isCharASCII( filter, pos.start, ')' ) )
558            {
559                // This is a present node
560                if ( schemaManager != null )
561                {
562                    AttributeType attributeType = schemaManager.getAttributeType( attribute );
563
564                    if ( attributeType != null )
565                    {
566                        return new PresenceNode( attributeType );
567                    }
568                    else
569                    {
570                        return null;
571                    }
572                }
573                else
574                {
575                    return new PresenceNode( attribute );
576                }
577            }
578            else
579            {
580                // Definitively a substring with no initial or an error
581                // Push back the '*' on the string
582                pos.start--;
583                
584                return parseSubstring( schemaManager, attribute, null, filter, pos );
585            }
586        }
587        else if ( Strings.isCharASCII( filter, pos.start, ')' ) )
588        {
589            // An empty equality Node
590            if ( schemaManager != null )
591            {
592                AttributeType attributeType = schemaManager.getAttributeType( attribute );
593
594                if ( attributeType != null )
595                {
596                    return new EqualityNode( attributeType, new BinaryValue( ( byte[] ) null ) );
597                }
598
599                else
600                {
601                    return null;
602                }
603            }
604            else
605            {
606                return new EqualityNode( attribute, new BinaryValue( ( byte[] ) null ) );
607            }
608        }
609        else
610        {
611            // A substring or an equality node
612            Value<?> value = parseAssertionValue( schemaManager, attribute, filter, pos );
613
614            // Is there anything else but a ')' after the value ?
615            if ( Strings.isCharASCII( filter, pos.start, ')' ) )
616            {
617                // This is an equality node
618                if ( schemaManager != null )
619                {
620                    AttributeType attributeType = schemaManager.getAttributeType( attribute );
621
622                    if ( attributeType != null )
623                    {
624                        return new EqualityNode( attributeType, value );
625                    }
626                    else
627                    {
628                        return null;
629                    }
630                }
631                else
632                {
633                    return new EqualityNode( attribute, value );
634                }
635            }
636
637            return parseSubstring( schemaManager, attribute, value, filter, pos );
638        }
639    }
640
641
642    /**
643     * Parse the following grammar :
644     * item           = simple / present / substring / extensible
645     * simple         = attr WSP* filtertype assertionvalue
646     * filtertype     = '=' / '~=' / '>=' / '<='
647     * present        = attr WSP* '=' '*'
648     * substring      = attr WSP* '=' [initial] any [final]
649     * extensible     = ( attr [":dn"] [':' oid] ":=" assertionvalue )
650     *                  / ( [":dn"] ':' oid ":=" assertionvalue )
651     * matchingrule   = ":" oid
652     *
653     * An item starts with an attribute or a colon.
654     */
655    @SuppressWarnings(
656        { "rawtypes", "unchecked" })
657    private static ExprNode parseItem( SchemaManager schemaManager, byte[] filter, Position pos, byte b,
658        boolean relaxed ) throws ParseException, LdapException
659    {
660        String attribute;
661
662        if ( b == '\0' )
663        {
664            throw new ParseException( I18n.err( I18n.ERR_04151 ), pos.start );
665        }
666
667        if ( b == ':' )
668        {
669            // If we have a colon, then the item is an extensible one
670            return parseExtensible( schemaManager, null, filter, pos, relaxed );
671        }
672        else
673        {
674            // We must have an attribute
675            attribute = AttributeUtils.parseAttribute( filter, pos, true, relaxed );
676            
677            // Skip spaces
678            skipWhiteSpaces( filter, pos );
679
680            // Now, we may have a present, substring, simple or an extensible
681            byte currentByte = Strings.byteAt( filter, pos.start );
682
683            switch ( currentByte )
684            {
685                case '=':
686                    // It can be a presence, an equal or a substring
687                    pos.start++;
688                    
689                    return parsePresenceEqOrSubstring( schemaManager, attribute, filter, pos );
690
691                case '~':
692                    // Approximate node
693                    pos.start++;
694
695                    // Check that we have a '='
696                    if ( !Strings.isCharASCII( filter, pos.start, '=' ) )
697                    {
698                        throw new ParseException( I18n.err( I18n.ERR_04152 ), pos.start );
699                    }
700
701                    pos.start++;
702                    
703                    // Parse the value and create the node
704                    if ( schemaManager == null )
705                    {
706                        return new ApproximateNode( attribute, parseAssertionValue( schemaManager, attribute, filter,
707                            pos ) );
708                    }
709                    else
710                    {
711                        AttributeType attributeType = schemaManager.getAttributeType( attribute );
712
713                        if ( attributeType != null )
714                        {
715                            return new ApproximateNode( attributeType, parseAssertionValue( schemaManager, attribute,
716                                filter, pos ) );
717                        }
718                        else
719                        {
720                            return UndefinedNode.UNDEFINED_NODE;
721                        }
722                    }
723
724                case '>':
725                    // Greater or equal node
726                    pos.start++;
727
728                    // Check that we have a '='
729                    if ( !Strings.isCharASCII( filter, pos.start, '=' ) )
730                    {
731                        throw new ParseException( I18n.err( I18n.ERR_04152 ), pos.start );
732                    }
733
734                    pos.start++;
735
736                    // Parse the value and create the node
737                    if ( schemaManager == null )
738                    {
739                        return new GreaterEqNode( attribute,
740                            parseAssertionValue( schemaManager, attribute, filter, pos ) );
741                    }
742                    else
743                    {
744                        AttributeType attributeType = schemaManager.getAttributeType( attribute );
745
746                        if ( attributeType != null )
747                        {
748                            return new GreaterEqNode( attributeType, parseAssertionValue( schemaManager, attribute,
749                                filter, pos ) );
750                        }
751                        else
752                        {
753                            return UndefinedNode.UNDEFINED_NODE;
754                        }
755                    }
756
757                case '<':
758                    // Less or equal node
759                    pos.start++;
760
761                    // Check that we have a '='
762                    if ( !Strings.isCharASCII( filter, pos.start, '=' ) )
763                    {
764                        throw new ParseException( I18n.err( I18n.ERR_04152 ), pos.start );
765                    }
766
767                    pos.start++;
768
769                    // Parse the value and create the node
770                    if ( schemaManager == null )
771                    {
772                        return new LessEqNode( attribute, parseAssertionValue( schemaManager, attribute, filter, pos ) );
773                    }
774                    else
775                    {
776                        AttributeType attributeType = schemaManager.getAttributeType( attribute );
777
778                        if ( attributeType != null )
779                        {
780                            return new LessEqNode( attributeType, parseAssertionValue( schemaManager, attribute,
781                                filter, pos ) );
782                        }
783                        else
784                        {
785                            return UndefinedNode.UNDEFINED_NODE;
786                        }
787                    }
788
789                case ':':
790                    // An extensible node
791                    pos.start++;
792                    return parseExtensible( schemaManager, attribute, filter, pos, relaxed );
793
794                default:
795                    // This is an error
796                    throw new ParseException( I18n.err( I18n.ERR_04153 ), pos.start );
797            }
798        }
799    }
800
801
802    /**
803     * Parse AND, OR and NOT nodes :
804     *
805     * and            = '&' filterlist
806     * or             = '|' filterlist
807     * not            = '!' filter
808     * filterlist     = 1*filter
809     *
810     * @return
811     */
812    private static ExprNode parseBranchNode( SchemaManager schemaManager, ExprNode node, byte[] filter, Position pos,
813        boolean relaxed ) throws ParseException, LdapException
814    {
815        BranchNode branchNode = ( BranchNode ) node;
816        int nbChildren = 0;
817
818        // We must have at least one filter
819        ExprNode child = parseFilterInternal( schemaManager, filter, pos, relaxed );
820
821        if ( child != UndefinedNode.UNDEFINED_NODE )
822        {
823            // Add the child to the node children
824            branchNode.addNode( child );
825
826            if ( branchNode instanceof NotNode )
827            {
828                return node;
829            }
830
831            nbChildren++;
832        }
833        else if ( node instanceof AndNode )
834        {
835            return UndefinedNode.UNDEFINED_NODE;
836        }
837
838        // Now, iterate recusively though all the remaining filters, if any
839        while ( ( child = parseFilterInternal( schemaManager, filter, pos, relaxed ) ) != UndefinedNode.UNDEFINED_NODE )
840        {
841            // Add the child to the node children if not null
842            if ( child != null )
843            {
844                branchNode.addNode( child );
845                nbChildren++;
846            }
847            else if ( node instanceof AndNode )
848            {
849                return UndefinedNode.UNDEFINED_NODE;
850            }
851        }
852
853        if ( nbChildren > 0 )
854        {
855            return node;
856        }
857        else
858        {
859            return UndefinedNode.UNDEFINED_NODE;
860        }
861    }
862
863
864    /**
865     * filtercomp     = and / or / not / item
866     * and            = '&' WSP* filterlist
867     * or             = '|' WSP* filterlist
868     * not            = '!' WSP* filter
869     * item           = simple / present / substring / extensible
870     * simple         = attr WSP* filtertype WSP* assertionvalue
871     * present        = attr WSP* EQUALS ASTERISK
872     * substring      = attr WSP* EQUALS WSP* [initial] any [final]
873     * extensible     = ( attr [dnattrs]
874     *                    [matchingrule] COLON EQUALS assertionvalue )
875     *                    / ( [dnattrs]
876     *                         matchingrule COLON EQUALS assertionvalue )
877     */
878    private static ExprNode parseFilterComp( SchemaManager schemaManager, byte[] filter, Position pos,
879        boolean relaxed ) throws ParseException, LdapException
880    {
881        ExprNode node;
882
883        if ( pos.start == pos.length )
884        {
885            throw new ParseException( I18n.err( I18n.ERR_04154 ), pos.start );
886        }
887
888        byte c = Strings.byteAt( filter, pos.start );
889
890        switch ( c )
891        {
892            case '&':
893                // This is a AND node
894                pos.start++;
895                
896                // Skip spaces
897                skipWhiteSpaces( filter, pos );
898
899                node = new AndNode();
900                node = parseBranchNode( schemaManager, node, filter, pos, relaxed );
901                break;
902
903            case '|':
904                // This is an OR node
905                pos.start++;
906                
907                // Skip spaces
908                skipWhiteSpaces( filter, pos );
909
910                node = new OrNode();
911                node = parseBranchNode( schemaManager, node, filter, pos, relaxed );
912                break;
913
914            case '!':
915                // This is a NOT node
916                pos.start++;
917                
918                // Skip spaces
919                skipWhiteSpaces( filter, pos );
920
921                node = new NotNode();
922                node = parseBranchNode( schemaManager, node, filter, pos, relaxed );
923                break;
924
925            default:
926                // This is an item
927                node = parseItem( schemaManager, filter, pos, c, relaxed );
928                break;
929
930        }
931
932        return node;
933    }
934    
935    
936    /**
937     * Skip teh white spaces (0x20, 0x09, 0x0a and 0x0d)
938     * @param filter
939     * @param pos
940     */
941    private static void skipWhiteSpaces( byte[] filter, Position pos )
942    {
943        while ( Strings.isCharASCII( filter, pos.start, ' ' )
944                || Strings.isCharASCII( filter, pos.start, '\t' )
945                || Strings.isCharASCII( filter, pos.start, '\n' ) )
946        {
947            pos.start++;
948        }
949    }
950
951
952    /**
953     * Parse the grammar rule :
954     * filter ::= WSP* '(' WSP* filterComp WSP* ')' WSP*
955     */
956    private static ExprNode parseFilterInternal( SchemaManager schemaManager, byte[] filter, Position pos,
957        boolean relaxed ) throws ParseException, LdapException
958    {
959        // Skip spaces
960        skipWhiteSpaces( filter, pos );
961        
962        // Check for the left '('
963        if ( !Strings.isCharASCII( filter, pos.start, '(' ) )
964        {
965            // No more node, get out
966            if ( ( pos.start == 0 ) && ( pos.length != 0 ) )
967            {
968                throw new ParseException( I18n.err( I18n.ERR_04155 ), 0 );
969            }
970            else
971            {
972                return UndefinedNode.UNDEFINED_NODE;
973            }
974        }
975
976        pos.start++;
977
978        // Skip spaces
979        skipWhiteSpaces( filter, pos );
980        
981        // parse the filter component
982        ExprNode node = parseFilterComp( schemaManager, filter, pos, relaxed );
983
984        if ( node == UndefinedNode.UNDEFINED_NODE )
985        {
986            return UndefinedNode.UNDEFINED_NODE;
987        }
988
989        // Skip spaces
990        skipWhiteSpaces( filter, pos );
991        
992        // Check that we have a right ')'
993        if ( !Strings.isCharASCII( filter, pos.start, ')' ) )
994        {
995            throw new ParseException( I18n.err( I18n.ERR_04157 ), pos.start );
996        }
997
998        pos.start++;
999
1000        // Skip spaces
1001        skipWhiteSpaces( filter, pos );
1002        
1003        return node;
1004    }
1005
1006
1007    /**
1008     * Parses a search filter from it's string representation to an expression node object.
1009     * 
1010     * @param filter the search filter in it's string representation
1011     * @return the expression node object
1012     * @throws ParseException If the filter is invalid
1013     */
1014    public static ExprNode parse( String filter ) throws ParseException
1015    {
1016        return parse( null, Strings.getBytesUtf8( filter ), false );
1017    }
1018
1019
1020    /**
1021     * @see FilterParser#parse(String)
1022     * 
1023     * @param filter the search filter in it's string representation
1024     * @return the expression node object
1025     * @throws ParseException If the filter is invalid
1026     */
1027    public static ExprNode parse( byte[] filter ) throws ParseException
1028    {
1029        return parse( null, filter, false );
1030    }
1031
1032
1033    /**
1034     * @see FilterParser#parse(String)
1035     * 
1036     * @param schemaManager The SchemaManager
1037     * @param filter the search filter in it's string representation
1038     * @return the expression node object
1039     * @throws ParseException If the filter is invalid
1040     */
1041    public static ExprNode parse( SchemaManager schemaManager, String filter ) throws ParseException
1042    {
1043        return parse( schemaManager, Strings.getBytesUtf8( filter ), false );
1044    }
1045
1046
1047    /**
1048     * @see FilterParser#parse(String)
1049     * 
1050     * @param schemaManager The SchemaManager
1051     * @param filter the search filter in it's string representation
1052     * @return the expression node object
1053     * @throws ParseException If the filter is invalid
1054     */
1055    public static ExprNode parse( SchemaManager schemaManager, byte[] filter ) throws ParseException
1056    {
1057        return parse( schemaManager, filter, false );
1058    }
1059
1060
1061    private static ExprNode parse( SchemaManager schemaManager, byte[] filter, boolean relaxed )
1062        throws ParseException
1063    {
1064        // The filter must not be null. This is a defensive test
1065        if ( Strings.isEmpty( filter ) )
1066        {
1067            throw new ParseException( I18n.err( I18n.ERR_04158 ), 0 );
1068        }
1069
1070        Position pos = new Position();
1071        pos.start = 0;
1072        pos.end = 0;
1073        pos.length = filter.length;
1074
1075        try
1076        {
1077            ExprNode node = parseFilterInternal( schemaManager, filter, pos, relaxed );
1078            
1079            if ( node == UndefinedNode.UNDEFINED_NODE )
1080            {
1081                return null;
1082            }
1083            else
1084            {
1085                return node;
1086            }
1087        }
1088        catch ( LdapException le )
1089        {
1090            throw new ParseException( le.getMessage(), pos.start );
1091        }
1092    }
1093
1094
1095    /**
1096     * @see FilterParser#parse(String)
1097     * 
1098     * @param schemaManager The SchemaManager
1099     * @param filter the search filter in it's string representation
1100     * @param pos The position in the filter
1101     * @return the expression node object
1102     * @throws ParseException If the filter is invalid
1103     */
1104    public static ExprNode parse( SchemaManager schemaManager, String filter, Position pos ) throws ParseException
1105    {
1106        // The filter must not be null. This is a defensive test
1107        if ( Strings.isEmpty( filter ) )
1108        {
1109            throw new ParseException( I18n.err( I18n.ERR_04158 ), 0 );
1110        }
1111
1112        pos.start = 0;
1113        pos.end = 0;
1114        pos.length = filter.length();
1115
1116        try
1117        {
1118            return parseFilterInternal( schemaManager, Strings.getBytesUtf8( filter ), pos, false );
1119        }
1120        catch ( LdapException le )
1121        {
1122            throw new ParseException( le.getMessage(), pos.start );
1123        }
1124    }
1125
1126
1127    /**
1128     * Parses a search filter from it's string representation to an expression node object.
1129     * 
1130     * In <code>relaxed</code> mode the filter may violate RFC 4515, e.g. the underscore in attribute names is allowed.
1131     * 
1132     * @param filter the search filter in it's string representation
1133     * @param relaxed <code>true</code> to parse the filter in relaxed mode
1134     * @return the expression node object
1135     * @throws ParseException If the filter is invalid
1136     */
1137    public static ExprNode parse( String filter, boolean relaxed ) throws ParseException
1138    {
1139        return parse( null, Strings.getBytesUtf8( filter ), relaxed );
1140    }
1141}