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 /** 048 * {@inheritDoc} 049 */ 050 @Override 051 public Object visit( ExprNode node ) 052 { 053 if ( !( node instanceof BranchNode ) ) 054 { 055 return null; 056 } 057 058 BranchNode branch = ( BranchNode ) node; 059 060 Comparator<ExprNode> nodeComparator = new NodeComparator(); 061 062 Set<ExprNode> set = new TreeSet<>( nodeComparator ); 063 064 List<ExprNode> children = branch.getChildren(); 065 066 for ( ExprNode child : branch.getChildren() ) 067 { 068 if ( !child.isLeaf() ) 069 { 070 ExprNode newChild = ( ExprNode ) visit( child ); 071 072 if ( newChild != null ) 073 { 074 set.add( newChild ); 075 } 076 } 077 else 078 { 079 set.add( child ); 080 } 081 } 082 083 children.clear(); 084 085 children.addAll( set ); 086 087 return branch; 088 } 089 090 091 /** 092 * {@inheritDoc} 093 */ 094 @Override 095 public boolean canVisit( ExprNode node ) 096 { 097 return node instanceof BranchNode; 098 } 099 100 101 /** 102 * {@inheritDoc} 103 */ 104 @Override 105 public boolean isPrefix() 106 { 107 return false; 108 } 109 110 111 /** 112 * {@inheritDoc} 113 */ 114 @Override 115 public List<ExprNode> getOrder( BranchNode node, List<ExprNode> children ) 116 { 117 return children; 118 } 119 120 121 /** 122 * Normalizes a filter expression to a canonical representation while 123 * retaining logical meaning of the expression. 124 * 125 * @param schemaManager The SchemaManager 126 * @param filter the filter to normalize 127 * @return the normalized version of the filter 128 * @throws java.text.ParseException if the filter is malformed 129 */ 130 public static String getNormalizedFilter( SchemaManager schemaManager, String filter ) throws ParseException 131 { 132 ExprNode originalNode = FilterParser.parse( schemaManager, filter ); 133 134 return getNormalizedFilter( originalNode ); 135 } 136 137 138 /** 139 * Normalizes a filter expression to a canonical representation while 140 * retaining logical meaning of the expression. 141 * 142 * @param filter the filter to normalize 143 * @return the normalized String version of the filter 144 */ 145 public static String getNormalizedFilter( ExprNode filter ) 146 { 147 BranchNormalizedVisitor visitor = new BranchNormalizedVisitor(); 148 149 ExprNode result = ( ExprNode ) visitor.visit( filter ); 150 151 return result.toString().trim(); 152 } 153 154 static class NodeComparator implements Comparator<ExprNode> 155 { 156 @Override 157 public int compare( ExprNode o1, ExprNode o2 ) 158 { 159 StringBuilder buf = new StringBuilder(); 160 161 buf.setLength( 0 ); 162 163 String s1; 164 165 buf.append( o1.toString() ); 166 167 s1 = buf.toString(); 168 169 buf.setLength( 0 ); 170 171 String s2; 172 173 buf.append( o2.toString() ); 174 175 s2 = buf.toString(); 176 177 return s1.compareTo( s2 ); 178 } 179 } 180}