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