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     */
020    package org.apache.directory.server.core.normalization;
021    
022    
023    import java.util.ArrayList;
024    import java.util.List;
025    
026    import org.apache.directory.shared.ldap.entry.StringValue;
027    import org.apache.directory.shared.ldap.entry.Value;
028    import org.apache.directory.shared.ldap.exception.LdapException;
029    import org.apache.directory.shared.ldap.filter.AndNode;
030    import org.apache.directory.shared.ldap.filter.BranchNode;
031    import org.apache.directory.shared.ldap.filter.ExprNode;
032    import org.apache.directory.shared.ldap.filter.ExtensibleNode;
033    import org.apache.directory.shared.ldap.filter.FilterVisitor;
034    import org.apache.directory.shared.ldap.filter.LeafNode;
035    import org.apache.directory.shared.ldap.filter.NotNode;
036    import org.apache.directory.shared.ldap.filter.PresenceNode;
037    import org.apache.directory.shared.ldap.filter.SimpleNode;
038    import org.apache.directory.shared.ldap.filter.SubstringNode;
039    import org.apache.directory.shared.ldap.name.NameComponentNormalizer;
040    import org.apache.directory.shared.ldap.schema.AttributeType;
041    import org.apache.directory.shared.ldap.schema.SchemaManager;
042    import org.slf4j.Logger;
043    import org.slf4j.LoggerFactory;
044    
045    
046    /**
047     * A filter visitor which normalizes leaf node values as it visits them.  It also removes
048     * leaf nodes from branches whose attributeType is undefined.  It obviously cannot remove
049     * a leaf node from a filter which is only a leaf node.  Checks to see if a filter is a
050     * leaf node with undefined attributeTypes should be done outside this visitor.
051     *
052     * Since this visitor may remove filter nodes it may produce negative results on filters,
053     * like NOT branch nodes without a child or AND and OR nodes with one or less children.  This
054     * might make some partition implementations choke.  To avoid this problem we clean up branch
055     * nodes that don't make sense.  For example all BranchNodes without children are just
056     * removed.  An AND and OR BranchNode with a single child is replaced with it's child for
057     * all but the topmost branch node which we cannot replace.  So again the top most branch
058     * node must be inspected by code outside of this visitor.
059     *
060     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
061     * @version $Rev: 928945 $
062     */
063    public class FilterNormalizingVisitor implements FilterVisitor
064    {
065        /** logger used by this class */
066        private static final Logger log = LoggerFactory.getLogger( FilterNormalizingVisitor.class );
067    
068        /** the name component normalizer used by this visitor */
069        private final NameComponentNormalizer ncn;
070    
071        /** the global registries used to resolve OIDs for attributeType ids */
072        private final SchemaManager schemaManager;
073        
074    
075        /**
076         * Chars which need to be escaped in a filter
077         * '\0' | '(' | ')' | '*' | '\'
078         */
079        private static final boolean[] FILTER_CHAR =
080            { 
081                true,  false, false, false, false, false, false, false, // 00 -> 07 NULL
082                false, false, false, false, false, false, false, false, // 08 -> 0F
083                false, false, false, false, false, false, false, false, // 10 -> 17
084                false, false, false, false, false, false, false, false, // 18 -> 1F
085                false, false, false, false, false, false, false, false, // 20 -> 27
086                true,  true,  true,  false, false, false, false, false, // 28 -> 2F '(', ')', '*'
087                false, false, false, false, false, false, false, false, // 30 -> 37
088                false, false, false, false, false, false, false, false, // 38 -> 3F 
089                false, false, false, false, false, false, false, false, // 40 -> 47
090                false, false, false, false, false, false, false, false, // 48 -> 4F
091                false, false, false, false, false, false, false, false, // 50 -> 57
092                false, false, false, false, true,  false, false, false, // 58 -> 5F '\'
093                false, false, false, false, false, false, false, false, // 60 -> 67
094                false, false, false, false, false, false, false, false, // 68 -> 6F
095                false, false, false, false, false, false, false, false, // 70 -> 77
096                false, false, false, false, false, false, false, false  // 78 -> 7F
097            };
098        
099        /**
100         * Check if the given char is a filter escaped char
101         * &lt;filterEscapedChars&gt; ::= '\0' | '(' | ')' | '*' | '\'
102         *
103         * @param c the char we want to test
104         * @return true if the char is a pair char only
105         */
106        public static boolean isFilterChar( char c )
107        {
108            return ( ( ( c | 0x7F ) == 0x7F ) && FILTER_CHAR[c & 0x7f] );
109        }
110    
111    
112        /**
113         * 
114         * Creates a new instance of NormalizingVisitor.
115         *
116         * @param ncn The name component normalizer to use
117         * @param registries The global registries
118         */
119        public FilterNormalizingVisitor( NameComponentNormalizer ncn, SchemaManager schemaManager )
120        {
121            this.ncn = ncn;
122            this.schemaManager = schemaManager;
123        }
124    
125    
126        /**
127         * A private method used to normalize a value. At this point, the value
128         * is a Value<byte[]>, we have to translate it to a Value<String> if its
129         * AttributeType is H-R. Then we have to normalize the value accordingly
130         * to the AttributeType Normalizer.
131         * 
132         * @param attribute The attribute's ID
133         * @param value The value to normalize
134         * @return the normalized value
135         */
136        private Value<?> normalizeValue( String attribute, Value<?> value )
137        {
138            try
139            {
140                Value<?> normalized = null;
141    
142                AttributeType attributeType = schemaManager.lookupAttributeTypeRegistry( attribute );
143    
144                if ( attributeType.getSyntax().isHumanReadable() )
145                {
146                    normalized = new StringValue( 
147                        (String) ncn.normalizeByName( attribute, value.getString() ) );
148                }
149                else
150                {
151                    normalized = (Value<?>)ncn.normalizeByName( attribute, value.getBytes() );
152                }
153    
154                return normalized;
155            }
156            catch ( LdapException ne )
157            {
158                log.warn( "Failed to normalize filter value: {}", ne.getLocalizedMessage(), ne );
159                return null;
160            }
161        }
162    
163    
164        /**
165         * Visit a PresenceNode. If the attribute exists, the node is returned, otherwise
166         * null is returned.
167         * 
168         * @param node the node to visit
169         * @return The visited node
170         */
171        private ExprNode visitPresenceNode( PresenceNode node ) throws LdapException
172        {
173            node.setAttribute( schemaManager.getAttributeTypeRegistry().getOidByName( node.getAttribute() ) );
174            return node;
175        }
176    
177    
178        /**
179         * Visit a SimpleNode. If the attribute exists, the node is returned, otherwise
180         * null is returned. SimpleNodes are :
181         *  - ApproximateNode
182         *  - EqualityNode
183         *  - GreaterEqNode
184         *  - LesserEqNode
185         *  
186         * @param node the node to visit
187         * @return the visited node
188         */
189        private ExprNode visitSimpleNode( SimpleNode node ) throws LdapException
190        {
191            // still need this check here in case the top level is a leaf node
192            // with an undefined attributeType for its attribute
193            if ( !ncn.isDefined( node.getAttribute() ) )
194            {
195                return null;
196            }
197    
198            Value<?> normalized = normalizeValue( node.getAttribute(), node.getValue() );
199    
200            if ( normalized == null )
201            {
202                return null;
203            }
204    
205            node.setAttribute( schemaManager.getAttributeTypeRegistry().getOidByName( node.getAttribute() ) );
206            node.setValue( normalized );
207            
208            return node;
209        }
210    
211    
212        /**
213         * Visit a SubstringNode. If the attribute exists, the node is returned, otherwise
214         * null is returned. 
215         * 
216         * Normalizing substring value is pretty complex. It's not currently implemented...
217         * 
218         * @param node the node to visit
219         * @return the visited node
220         */
221        private ExprNode visitSubstringNode( SubstringNode node ) throws LdapException
222        {
223            // still need this check here in case the top level is a leaf node
224            // with an undefined attributeType for its attribute
225            if ( !ncn.isDefined( node.getAttribute() ) )
226            {
227                return null;
228            }
229    
230            Value<?> normInitial = null;
231    
232            if ( node.getInitial() != null )
233            {
234                normInitial = normalizeValue( node.getAttribute(), new StringValue( node.getInitial() ) );
235    
236                if ( normInitial == null )
237                {
238                    return null;
239                }
240            }
241    
242            List<String> normAnys = null;
243    
244            if ( ( node.getAny() != null ) && ( node.getAny().size() != 0 ) )
245            {
246                normAnys = new ArrayList<String>( node.getAny().size() );
247    
248                for ( String any : node.getAny() )
249                {
250                    Value<?> normAny = normalizeValue( node.getAttribute(), new StringValue( any ) );
251    
252                    if ( normAny != null )
253                    {
254                        normAnys.add( normAny.getString() );
255                    }
256                }
257    
258                if ( normAnys.size() == 0 )
259                {
260                    return null;
261                }
262            }
263    
264            Value<?> normFinal = null;
265    
266            if ( node.getFinal() != null )
267            {
268                normFinal = normalizeValue( node.getAttribute(), new StringValue( node.getFinal() ) );
269    
270                if ( normFinal == null )
271                {
272                    return null;
273                }
274            }
275    
276            node.setAttribute( schemaManager.getAttributeTypeRegistry().getOidByName( node.getAttribute() ) );
277    
278            if ( normInitial != null )
279            {
280                node.setInitial( normInitial.getString() );
281            }
282            else
283            {
284                node.setInitial( null );
285            }
286    
287            node.setAny( normAnys );
288    
289            if ( normFinal != null )
290            {
291                node.setFinal( normFinal.getString() );
292            }
293            else
294            {
295                node.setFinal( null );
296            }
297    
298            return node;
299        }
300    
301    
302        /**
303         * Visit a ExtensibleNode. If the attribute exists, the node is returned, otherwise
304         * null is returned. 
305         * 
306         * TODO implement the logic for ExtensibleNode
307         * 
308         * @param node the node to visit
309         * @return the visited node
310         */
311        private ExprNode visitExtensibleNode( ExtensibleNode node ) throws LdapException
312        {
313            node.setAttribute( schemaManager.getAttributeTypeRegistry().getOidByName( node.getAttribute() ) );
314    
315            return node;
316        }
317    
318    
319        /**
320         * Visit a BranchNode. BranchNodes are :
321         *  - AndNode
322         *  - NotNode
323         *  - OrNode
324         *  
325         * @param node the node to visit
326         * @return the visited node
327         */
328        private ExprNode visitBranchNode( BranchNode node )
329        {
330            // Two differente cases :
331            // - AND or OR
332            // - NOT
333    
334            if ( node instanceof NotNode )
335            {
336                // Manage the NOT
337                ExprNode child = node.getFirstChild();
338    
339                ExprNode result = ( ExprNode ) visit( child );
340    
341                if ( result == null )
342                {
343                    return null;
344                }
345                else if ( result instanceof BranchNode )
346                {
347                    List<ExprNode> newChildren = new ArrayList<ExprNode>( 1 );
348                    newChildren.add( result );
349                    node.setChildren( newChildren );
350                    return node;
351                }
352                else if ( result instanceof LeafNode )
353                {
354                    List<ExprNode> newChildren = new ArrayList<ExprNode>( 1 );
355                    newChildren.add( result );
356                    node.setChildren( newChildren );
357                    return node;
358                }
359            }
360            else
361            {
362                // Manage AND and OR nodes.
363                BranchNode branchNode = node;
364                List<ExprNode> children = node.getChildren();
365    
366                // For AND and OR, we may have more than one children.
367                // We may have to remove some of them, so let's create
368                // a new handler to store the correct nodes.
369                List<ExprNode> newChildren = new ArrayList<ExprNode>( children.size() );
370    
371                // Now, iterate through all the children
372                for ( int i = 0; i < children.size(); i++ )
373                {
374                    ExprNode child = children.get( i );
375    
376                    ExprNode result = ( ExprNode ) visit( child );
377    
378                    if ( result != null )
379                    {
380                        // As the node is correct, add it to the children 
381                        // list.
382                        newChildren.add( result );
383                    }
384                }
385    
386                if ( ( branchNode instanceof AndNode ) && ( newChildren.size() != children.size() ) )
387                {
388                    return null;
389                }
390    
391                if ( newChildren.size() == 0 )
392                {
393                    // No more children, return null
394                    return null;
395                }
396                else if ( newChildren.size() == 1 )
397                {
398                    // As we only have one child, return it
399                    // to the caller.
400                    return newChildren.get( 0 );
401                }
402                else
403                {
404                    branchNode.setChildren( newChildren );
405                }
406            }
407    
408            return node;
409        }
410    
411    
412        /**
413         * Visit the tree, normalizing the leaves and recusrsively visit the branches.
414         * 
415         * Here are the leaves we are visiting :
416         * - PresenceNode ( attr =* )
417         * - ExtensibleNode ( ? )
418         * - SubStringNode ( attr = *X*Y* )
419         * - ApproximateNode ( attr ~= value )
420         * - EqualityNode ( attr = value )
421         * - GreaterEqNode ( attr >= value )
422         * - LessEqNode ( attr <= value )
423         * 
424         * The PresencNode is managed differently from other nodes, as it just check
425         * for the attribute, not the value.
426         * 
427         * @param node the node to visit
428         * @return the visited node
429         */
430        public Object visit( ExprNode node ) 
431        {
432            try
433            {
434                    // -------------------------------------------------------------------
435                    // Handle PresenceNodes
436                    // -------------------------------------------------------------------
437            
438                    if ( node instanceof PresenceNode )
439                    {
440                        return visitPresenceNode( ( PresenceNode ) node );
441                    }
442            
443                    // -------------------------------------------------------------------
444                    // Handle BranchNodes (AndNode, NotNode and OrNode)
445                    // -------------------------------------------------------------------
446            
447                    else if ( node instanceof BranchNode )
448                    {
449                        return visitBranchNode( ( BranchNode ) node );
450                    }
451            
452                    // -------------------------------------------------------------------
453                    // Handle SimpleNodes (ApproximateNode, EqualityNode, GreaterEqNode,
454                    // and LesserEqNode) 
455                    // -------------------------------------------------------------------
456            
457                    else if ( node instanceof SimpleNode )
458                    {
459                        return visitSimpleNode( ( SimpleNode ) node );
460                    }
461                    else if ( node instanceof ExtensibleNode )
462                    {
463                        return visitExtensibleNode( ( ExtensibleNode ) node );
464                    }
465                    else if ( node instanceof SubstringNode )
466                    {
467                        return visitSubstringNode( ( SubstringNode ) node );
468                    }
469                    else
470                    {
471                        return null;
472                    }
473            }
474            catch( LdapException e )
475            {
476                    throw new RuntimeException( e );
477            }
478        }
479    
480    
481        public boolean canVisit( ExprNode node )
482        {
483            return true;
484        }
485    
486    
487        public boolean isPrefix()
488        {
489            return false;
490        }
491    
492    
493        public List<ExprNode> getOrder( BranchNode node, List<ExprNode> children )
494        {
495            return children;
496        }
497    }