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}