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