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}