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