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