View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.server.core.normalization;
21  
22  
23  import java.util.ArrayList;
24  import java.util.List;
25  
26  import javax.naming.InvalidNameException;
27  import javax.naming.NamingException;
28  
29  import org.apache.directory.server.schema.registries.Registries;
30  import org.apache.directory.shared.ldap.entry.Value;
31  import org.apache.directory.shared.ldap.entry.client.ClientBinaryValue;
32  import org.apache.directory.shared.ldap.entry.client.ClientStringValue;
33  import org.apache.directory.shared.ldap.filter.AndNode;
34  import org.apache.directory.shared.ldap.filter.BranchNode;
35  import org.apache.directory.shared.ldap.filter.ExprNode;
36  import org.apache.directory.shared.ldap.filter.ExtensibleNode;
37  import org.apache.directory.shared.ldap.filter.FilterVisitor;
38  import org.apache.directory.shared.ldap.filter.LeafNode;
39  import org.apache.directory.shared.ldap.filter.NotNode;
40  import org.apache.directory.shared.ldap.filter.PresenceNode;
41  import org.apache.directory.shared.ldap.filter.SimpleNode;
42  import org.apache.directory.shared.ldap.filter.SubstringNode;
43  import org.apache.directory.shared.ldap.name.NameComponentNormalizer;
44  import org.apache.directory.shared.ldap.schema.AttributeType;
45  import org.apache.directory.shared.ldap.util.ByteBuffer;
46  import org.apache.directory.shared.ldap.util.StringTools;
47  
48  import org.slf4j.Logger;
49  import org.slf4j.LoggerFactory;
50  
51  
52  /**
53   * A filter visitor which normalizes leaf node values as it visits them.  It also removes
54   * leaf nodes from branches whose attributeType is undefined.  It obviously cannot remove
55   * a leaf node from a filter which is only a leaf node.  Checks to see if a filter is a
56   * leaf node with undefined attributeTypes should be done outside this visitor.
57   *
58   * Since this visitor may remove filter nodes it may produce negative results on filters,
59   * like NOT branch nodes without a child or AND and OR nodes with one or less children.  This
60   * might make some partition implementations choke.  To avoid this problem we clean up branch
61   * nodes that don't make sense.  For example all BranchNodes without children are just
62   * removed.  An AND and OR BranchNode with a single child is replaced with it's child for
63   * all but the topmost branchnode which we cannot replace.  So again the top most branch
64   * node must be inspected by code outside of this visitor.
65   *
66   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
67   * @version $Rev: 675520 $
68   */
69  public class NormalizingVisitor implements FilterVisitor
70  {
71      /** logger used by this class */
72      private static final Logger log = LoggerFactory.getLogger( NormalizingVisitor.class );
73  
74      /** the name component normalizer used by this visitor */
75      private final NameComponentNormalizer ncn;
76  
77      /** the global registries used to resolve OIDs for attributeType ids */
78      private final Registries registries;
79  
80  
81      /**
82       * Chars which need to be escaped in a filter
83       * '\0' | '(' | ')' | '*' | '\'
84       */
85      private static final boolean[] FILTER_CHAR =
86          { 
87              true,  false, false, false, false, false, false, false, // 00 -> 07 NULL
88              false, false, false, false, false, false, false, false, // 08 -> 0F
89              false, false, false, false, false, false, false, false, // 10 -> 17
90              false, false, false, false, false, false, false, false, // 18 -> 1F
91              false, false, false, false, false, false, false, false, // 20 -> 27
92              true,  true,  true,  false, false, false, false, false, // 28 -> 2F '(', ')', '*'
93              false, false, false, false, false, false, false, false, // 30 -> 37
94              false, false, false, false, false, false, false, false, // 38 -> 3F 
95              false, false, false, false, false, false, false, false, // 40 -> 47
96              false, false, false, false, false, false, false, false, // 48 -> 4F
97              false, false, false, false, false, false, false, false, // 50 -> 57
98              false, false, false, false, true,  false, false, false, // 58 -> 5F '\'
99              false, false, false, false, false, false, false, false, // 60 -> 67
100             false, false, false, false, false, false, false, false, // 68 -> 6F
101             false, false, false, false, false, false, false, false, // 70 -> 77
102             false, false, false, false, false, false, false, false  // 78 -> 7F
103         };
104     
105     /**
106      * Check if the given char is a filter escaped char
107      * &lt;filterEscapedChars&gt; ::= '\0' | '(' | ')' | '*' | '\'
108      *
109      * @param c the char we want to test
110      * @return true if the char is a pair char only
111      */
112     public static boolean isFilterChar( char c )
113     {
114         return ( ( ( c | 0x7F ) == 0x7F ) && FILTER_CHAR[c & 0x7f] );
115     }
116 
117     /**
118      * Decodes sequences of escaped hex within an attribute's value into 
119      * a UTF-8 String.  The hex is decoded inline and the complete decoded
120      * String is returned.
121      * 
122      * @param str the string containing hex escapes
123      * @return the decoded string
124      */
125     private static final String decodeEscapedHex( String str ) throws InvalidNameException
126     {
127         // create buffer and add everything before start of scan
128         StringBuffer buf = new StringBuffer();
129         ByteBuffer bb = new ByteBuffer();
130         boolean escaped = false;
131         
132         // start scanning until we find an escaped series of bytes
133         for ( int ii = 0; ii < str.length(); ii++ )
134         {
135             char c = str.charAt( ii );
136             
137             if ( c == '\\' )
138             {
139                 // we have the start of a hex escape sequence
140                 if ( StringTools.isHex( str, ii+1 ) && StringTools.isHex ( str, ii+2 ) )
141                 {
142                     bb.clear();
143                     int advancedBy = StringTools.collectEscapedHexBytes( bb, str, ii );
144                     ii+=advancedBy-1;
145                     buf.append( StringTools.utf8ToString( bb.buffer(), bb.position() ) );
146                     escaped = false;
147                     continue;
148                 }
149                 else if ( !escaped )
150                 {
151                     // It may be an escaped char ( '\0', '(', ')', '*', '\' )
152                     escaped = true;
153                     continue;
154                 }
155             }
156 
157             
158             if ( escaped )
159             {
160                 if ( isFilterChar( c ) )
161                 {
162                     // It is an escaped char ( '\0', '(', ')', '*', '\' )
163                     // Stores it into the buffer without the '\'
164                     escaped = false;
165                     buf.append( c );
166                     continue;
167                 }
168                 else
169                 {
170                     throw new InvalidNameException( "The value must contain valid escaped characters." );
171                 }
172             }
173             else
174             {
175                 buf.append( str.charAt( ii ) );
176             }
177         }
178 
179         if ( escaped )
180         {
181             // We should not have a '\' at the end of the string
182             throw new InvalidNameException( "The value must not ends with a '\\'." );
183         }
184 
185         return buf.toString();
186     }
187 
188 
189     /**
190      * Un-escape the escaped chars in the value
191      */
192     private void unescapeValue( Value<?> value )
193     {
194         if ( !value.isBinary() )
195         {
196             String valStr = (String)value.getNormalizedValue();
197             
198             if ( StringTools.isEmpty( valStr ) )
199             {
200                 return;
201             }
202             
203             try
204             {
205                 String newStr= decodeEscapedHex( valStr );
206                 ((ClientStringValue)value).set( newStr );
207                 return;
208             }
209             catch ( InvalidNameException ine )
210             {
211                 value.set( null );
212                 return;
213             }
214         }
215     }
216 
217 
218     /**
219      * 
220      * Creates a new instance of NormalizingVisitor.
221      *
222      * @param ncn The name component normalizer to use
223      * @param registries The global registries
224      */
225     public NormalizingVisitor( NameComponentNormalizer ncn, Registries registries )
226     {
227         this.ncn = ncn;
228         this.registries = registries;
229     }
230 
231 
232     /**
233      * A private method used to normalize a value
234      * 
235      * @param attribute The attribute's ID
236      * @param value The value to normalize
237      * @return the normalized value
238      */
239     private Value<?> normalizeValue( String attribute, Value<?> value )
240     {
241         try
242         {
243             Value<?> normalized = null;
244 
245             AttributeType attributeType = registries.getAttributeTypeRegistry().lookup( attribute );
246 
247             if ( attributeType.getSyntax().isHumanReadable() )
248             {
249                 if ( value.isBinary() )
250                 {
251                     normalized = new ClientStringValue( ( String ) ncn.normalizeByName( attribute, StringTools
252                         .utf8ToString( ( byte[] ) value.get() ) ) );
253                     
254                     unescapeValue( normalized );
255                 }
256                 else
257                 {
258                     normalized = new ClientStringValue( ( String ) ncn.normalizeByName( attribute, ( String ) value
259                         .get() ) );
260                     
261                     unescapeValue( normalized );
262                 }
263             }
264             else
265             {
266                 if ( value.isBinary() )
267                 {
268                     normalized = new ClientBinaryValue( ( byte[] ) ncn.normalizeByName( attribute, ( byte[] ) value
269                         .get() ) );
270                 }
271                 else
272                 {
273                     normalized = new ClientBinaryValue( ( byte[] ) ncn.normalizeByName( attribute, ( String ) value
274                         .get() ) );
275 
276                 }
277             }
278 
279             return normalized;
280         }
281         catch ( NamingException ne )
282         {
283             log.warn( "Failed to normalize filter value: {}", ne.getMessage(), ne );
284             return null;
285         }
286 
287     }
288 
289 
290     /**
291      * Visit a PresenceNode. If the attribute exists, the node is returned, otherwise
292      * null is returned.
293      * 
294      * @param node the node to visit
295      * @return The visited node
296      */
297     private ExprNode visitPresenceNode( PresenceNode node )
298     {
299         try
300         {
301             node.setAttribute( registries.getOidRegistry().getOid( node.getAttribute() ) );
302             return node;
303         }
304         catch ( NamingException ne )
305         {
306             log.warn( "Failed to normalize filter node attribute: {}, error: {}", node.getAttribute(), ne.getMessage() );
307             return null;
308         }
309     }
310 
311 
312     /**
313      * Visit a SimpleNode. If the attribute exists, the node is returned, otherwise
314      * null is returned. SimpleNodes are :
315      *  - ApproximateNode
316      *  - EqualityNode
317      *  - GreaterEqNode
318      *  - LesserEqNode
319      *  
320      * @param node the node to visit
321      * @return the visited node
322      */
323     private ExprNode visitSimpleNode( SimpleNode node )
324     {
325         // still need this check here in case the top level is a leaf node
326         // with an undefined attributeType for its attribute
327         if ( !ncn.isDefined( node.getAttribute() ) )
328         {
329             return null;
330         }
331 
332         Value<?> normalized = normalizeValue( node.getAttribute(), node.getValue() );
333 
334         if ( normalized == null )
335         {
336             return null;
337         }
338 
339         try
340         {
341             node.setAttribute( registries.getOidRegistry().getOid( node.getAttribute() ) );
342             node.setValue( normalized );
343             return node;
344         }
345         catch ( NamingException ne )
346         {
347             log.warn( "Failed to normalize filter node attribute: {}, error: {}", node.getAttribute(), ne.getMessage() );
348             return null;
349         }
350     }
351 
352 
353     /**
354      * Visit a SubstringNode. If the attribute exists, the node is returned, otherwise
355      * null is returned. 
356      * 
357      * Normalizing substring value is pretty complex. It's not currently implemented...
358      * 
359      * @param node the node to visit
360      * @return the visited node
361      */
362     private ExprNode visitSubstringNode( SubstringNode node )
363     {
364         // still need this check here in case the top level is a leaf node
365         // with an undefined attributeType for its attribute
366         if ( !ncn.isDefined( node.getAttribute() ) )
367         {
368             return null;
369         }
370 
371         Value<?> normInitial = null;
372 
373         if ( node.getInitial() != null )
374         {
375             normInitial = normalizeValue( node.getAttribute(), new ClientStringValue( node.getInitial() ) );
376 
377             if ( normInitial == null )
378             {
379                 return null;
380             }
381         }
382 
383         List<String> normAnys = null;
384 
385         if ( ( node.getAny() != null ) && ( node.getAny().size() != 0 ) )
386         {
387             normAnys = new ArrayList<String>( node.getAny().size() );
388 
389             for ( String any : node.getAny() )
390             {
391                 Value<?> normAny = normalizeValue( node.getAttribute(), new ClientStringValue( any ) );
392 
393                 if ( normAny != null )
394                 {
395                     normAnys.add( ( String ) normAny.get() );
396                 }
397             }
398 
399             if ( normAnys.size() == 0 )
400             {
401                 return null;
402             }
403         }
404 
405         Value<?> normFinal = null;
406 
407         if ( node.getFinal() != null )
408         {
409             normFinal = normalizeValue( node.getAttribute(), new ClientStringValue( node.getFinal() ) );
410 
411             if ( normFinal == null )
412             {
413                 return null;
414             }
415         }
416 
417         try
418         {
419             node.setAttribute( registries.getOidRegistry().getOid( node.getAttribute() ) );
420 
421             if ( normInitial != null )
422             {
423                 node.setInitial( ( String ) normInitial.get() );
424             }
425             else
426             {
427                 node.setInitial( null );
428             }
429 
430             node.setAny( normAnys );
431 
432             if ( normFinal != null )
433             {
434                 node.setFinal( ( String ) normFinal.get() );
435             }
436             else
437             {
438                 node.setFinal( null );
439             }
440 
441             return node;
442         }
443         catch ( NamingException ne )
444         {
445             log.warn( "Failed to normalize filter node attribute: {}, error: {}", node.getAttribute(), ne.getMessage() );
446             return null;
447         }
448     }
449 
450 
451     /**
452      * Visit a ExtensibleNode. If the attribute exists, the node is returned, otherwise
453      * null is returned. 
454      * 
455      * TODO implement the logic for ExtensibleNode
456      * 
457      * @param node the node to visit
458      * @return the visited node
459      */
460     private ExprNode visitExtensibleNode( ExtensibleNode node )
461     {
462         try
463         {
464             node.setAttribute( registries.getOidRegistry().getOid( node.getAttribute() ) );
465             return node;
466         }
467         catch ( NamingException ne )
468         {
469             log.warn( "Failed to normalize filter node attribute: {}, error: {}", node.getAttribute(), ne.getMessage() );
470             return null;
471         }
472     }
473 
474 
475     /**
476      * Visit a BranchNode. BranchNodes are :
477      *  - AndNode
478      *  - NotNode
479      *  - OrNode
480      *  
481      * @param node the node to visit
482      * @return the visited node
483      */
484     private ExprNode visitBranchNode( BranchNode node )
485     {
486         // Two differente cases :
487         // - AND or OR
488         // - NOT
489 
490         if ( node instanceof NotNode )
491         {
492             // Manage the NOT
493             ExprNode child = node.getFirstChild();
494 
495             ExprNode result = ( ExprNode ) visit( child );
496 
497             if ( result == null )
498             {
499                 return result;
500             }
501             else if ( result instanceof BranchNode )
502             {
503                 node.setChildren( ( ( BranchNode ) result ).getChildren() );
504                 return node;
505             }
506             else if ( result instanceof LeafNode )
507             {
508                 List<ExprNode> newChildren = new ArrayList<ExprNode>( 1 );
509                 newChildren.add( result );
510                 node.setChildren( newChildren );
511                 return node;
512             }
513         }
514         else
515         {
516             // Manage AND and OR nodes.
517             BranchNode branchNode = node;
518             List<ExprNode> children = node.getChildren();
519 
520             // For AND and OR, we may have more than one children.
521             // We may have to remove some of them, so let's create
522             // a new handler to store the correct nodes.
523             List<ExprNode> newChildren = new ArrayList<ExprNode>( children.size() );
524 
525             // Now, iterate through all the children
526             for ( int i = 0; i < children.size(); i++ )
527             {
528                 ExprNode child = children.get( i );
529 
530                 ExprNode result = ( ExprNode ) visit( child );
531 
532                 if ( result != null )
533                 {
534                     // As the node is correct, add it to the children 
535                     // list.
536                     newChildren.add( result );
537                 }
538             }
539 
540             if ( ( branchNode instanceof AndNode ) && ( newChildren.size() != children.size() ) )
541             {
542                 return null;
543             }
544 
545             if ( newChildren.size() == 0 )
546             {
547                 // No more children, return null
548                 return null;
549             }
550             else if ( newChildren.size() == 1 )
551             {
552                 // As we only have one child, return it
553                 // to the caller.
554                 return newChildren.get( 0 );
555             }
556             else
557             {
558                 branchNode.setChildren( newChildren );
559             }
560         }
561 
562         return node;
563     }
564 
565 
566     /**
567      * Visit the tree, normalizing the leaves and recusrsively visit the branches.
568      * 
569      * Here are the leaves we are visiting :
570      * - PresenceNode ( attr =* )
571      * - ExtensibleNode ( ? )
572      * - SubStringNode ( attr = *X*Y* )
573      * - ApproximateNode ( attr ~= value )
574      * - EqualityNode ( attr = value )
575      * - GreaterEqNode ( attr >= value )
576      * - LessEqNode ( attr <= value )
577      * 
578      * The PresencNode is managed differently from other nodes, as it just check
579      * for the attribute, not the value.
580      * 
581      * @param node the node to visit
582      * @return the visited node
583      */
584     public Object visit( ExprNode node )
585     {
586         // -------------------------------------------------------------------
587         // Handle PresenceNodes
588         // -------------------------------------------------------------------
589 
590         if ( node instanceof PresenceNode )
591         {
592             return visitPresenceNode( ( PresenceNode ) node );
593         }
594 
595         // -------------------------------------------------------------------
596         // Handle BranchNodes (AndNode, NotNode and OrNode)
597         // -------------------------------------------------------------------
598 
599         else if ( node instanceof BranchNode )
600         {
601             return visitBranchNode( ( BranchNode ) node );
602         }
603 
604         // -------------------------------------------------------------------
605         // Handle SimpleNodes (ApproximateNode, EqualityNode, GreaterEqNode,
606         // and LesserEqNode) 
607         // -------------------------------------------------------------------
608 
609         else if ( node instanceof SimpleNode )
610         {
611             return visitSimpleNode( ( SimpleNode ) node );
612         }
613         else if ( node instanceof ExtensibleNode )
614         {
615             return visitExtensibleNode( ( ExtensibleNode ) node );
616         }
617         else if ( node instanceof SubstringNode )
618         {
619             return visitSubstringNode( ( SubstringNode ) node );
620         }
621         else
622         {
623             return null;
624         }
625     }
626 
627 
628     public boolean canVisit( ExprNode node )
629     {
630         return true;
631     }
632 
633 
634     public boolean isPrefix()
635     {
636         return false;
637     }
638 
639 
640     public List<ExprNode> getOrder( BranchNode node, List<ExprNode> children )
641     {
642         return children;
643     }
644 }