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; 024import java.util.Comparator; 025import java.util.List; 026import java.util.Set; 027import java.util.TreeSet; 028 029import org.apache.directory.api.ldap.model.schema.SchemaManager; 030 031 032/** 033 * Visitor which traverses a filter tree while normalizing the branch node 034 * order. Filter expressions can change the order of expressions in branch nodes 035 * without effecting the logical meaning of the expression. This visitor orders 036 * the children of expression tree branch nodes consistantly. It is really 037 * useful for comparing expression trees which may be altered for performance or 038 * altered because of codec idiosyncracies: for example the SNACC4J codec uses a 039 * hashmap to store expressions in a sequence which rearranges the order of 040 * children based on object hashcodes. We need this visitor to remove such 041 * inconsitancies in order hence normalizing the branch node's child order. 042 * 043 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 044 */ 045public class BranchNormalizedVisitor implements FilterVisitor 046{ 047 @Override 048 public Object visit( ExprNode node ) 049 { 050 if ( !( node instanceof BranchNode ) ) 051 { 052 return null; 053 } 054 055 BranchNode branch = ( BranchNode ) node; 056 057 Comparator<ExprNode> nodeComparator = new NodeComparator(); 058 059 Set<ExprNode> set = new TreeSet<>( nodeComparator ); 060 061 List<ExprNode> children = branch.getChildren(); 062 063 for ( ExprNode child : branch.getChildren() ) 064 { 065 if ( !child.isLeaf() ) 066 { 067 ExprNode newChild = ( ExprNode ) visit( child ); 068 069 if ( newChild != null ) 070 { 071 set.add( newChild ); 072 } 073 } 074 else 075 { 076 set.add( child ); 077 } 078 } 079 080 children.clear(); 081 082 children.addAll( set ); 083 084 return branch; 085 } 086 087 088 /** 089 * {@inheritDoc} 090 */ 091 @Override 092 public boolean canVisit( ExprNode node ) 093 { 094 return node instanceof BranchNode; 095 } 096 097 098 /** 099 * {@inheritDoc} 100 */ 101 @Override 102 public boolean isPrefix() 103 { 104 return false; 105 } 106 107 108 /** 109 * {@inheritDoc} 110 */ 111 @Override 112 public List<ExprNode> getOrder( BranchNode node, List<ExprNode> children ) 113 { 114 return children; 115 } 116 117 118 /** 119 * Normalizes a filter expression to a canonical representation while 120 * retaining logical meaning of the expression. 121 * 122 * @param schemaManager The SchemaManager 123 * @param filter the filter to normalize 124 * @return the normalized version of the filter 125 * @throws java.text.ParseException if the filter is malformed 126 */ 127 public static String getNormalizedFilter( SchemaManager schemaManager, String filter ) throws ParseException 128 { 129 ExprNode originalNode = FilterParser.parse( schemaManager, filter ); 130 131 return getNormalizedFilter( originalNode ); 132 } 133 134 135 /** 136 * Normalizes a filter expression to a canonical representation while 137 * retaining logical meaning of the expression. 138 * 139 * @param filter 140 * the filter to normalize 141 * @return the normalized String version of the filter 142 */ 143 public static String getNormalizedFilter( ExprNode filter ) 144 { 145 BranchNormalizedVisitor visitor = new BranchNormalizedVisitor(); 146 147 ExprNode result = ( ExprNode ) visitor.visit( filter ); 148 149 return result.toString().trim(); 150 } 151 152 153 static class NodeComparator implements Comparator<ExprNode> 154 { 155 @Override 156 public int compare( ExprNode o1, ExprNode o2 ) 157 { 158 String s1 = o1.toString(); 159 String s2 = o2.toString(); 160 161 return s1.compareTo( s2 ); 162 } 163 } 164}