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 * <filterEscapedChars> ::= '\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 }