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    }