directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1389184 [9/13] - in /directory/apacheds/trunk: core-annotations/src/main/java/org/apache/directory/server/core/factory/ core-api/src/main/java/org/apache/directory/server/core/api/ core-api/src/main/java/org/apache/directory/server/core/ap...
Date Mon, 24 Sep 2012 02:17:20 GMT
Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/ApproximateEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/ApproximateEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/ApproximateEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/ApproximateEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,200 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.Iterator;
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.shared.ldap.model.entry.Attribute;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.entry.Value;
+import org.apache.directory.shared.ldap.model.filter.ApproximateNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.MatchingRule;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+
+
+/**
+ * An Evaluator which determines if candidates are matched by ApproximateNode
+ * assertions.  Same as equality for now.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class ApproximateEvaluator<T> extends LeafEvaluator<T>
+{
+    /**
+     * Creates a new ApproximateEvaluator
+     * @param node The ApproximateNode
+     * @param db The Store
+     * @param schemaManager The SchemaManager
+     * @throws Exception If the creation failed
+     */
+    public ApproximateEvaluator( ApproximateNode<T> node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        super( node, db, schemaManager );
+
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            idx = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+            normalizer = null;
+            ldapComparator = null;
+        }
+        else
+        {
+            idx = null;
+
+            MatchingRule mr = attributeType.getEquality();
+
+            if ( mr == null )
+            {
+                throw new IllegalStateException( I18n.err( I18n.ERR_709, node ) );
+            }
+
+            normalizer = mr.getNormalizer();
+            ldapComparator = mr.getLdapComparator();
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public ApproximateNode<T> getExpression()
+    {
+        return ( ApproximateNode<T> ) node;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute does not exist just return false
+        if ( ( attr != null ) && evaluate( attr ) )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( attr != null && evaluate( attr ) )
+                {
+                    return true;
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        return evaluate( entry );
+    }
+
+
+    // TODO - determine if comparator and index entry should have the Value
+    // wrapper or the raw normalized value
+    private boolean evaluate( Attribute attribute ) throws Exception
+    {
+        /*
+         * Cycle through the attribute values testing normalized version
+         * obtained from using the ordering or equality matching rule's
+         * normalizer.  The test uses the comparator obtained from the
+         * appropriate matching rule to perform the check.
+         */
+
+        for ( Value<?> value : attribute )
+        {
+            if ( ldapComparator.compare( value.getNormValue(), node.getValue().getNormValue() ) == 0 )
+            {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "ApproximateEvaluator : " ).append( super.toString() ).append( "\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/EqualityEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/EqualityEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/EqualityEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/EqualityEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,240 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.Comparator;
+import java.util.Iterator;
+
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.shared.ldap.model.entry.Attribute;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.entry.Value;
+import org.apache.directory.shared.ldap.model.filter.EqualityNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.MatchingRule;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+import org.apache.directory.shared.ldap.model.schema.comparators.ByteArrayComparator;
+import org.apache.directory.shared.ldap.model.schema.comparators.StringComparator;
+import org.apache.directory.shared.ldap.model.schema.normalizers.NoOpNormalizer;
+import org.apache.directory.shared.util.Strings;
+
+
+/**
+ * An Evaluator which determines if candidates are matched by GreaterEqNode
+ * assertions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class EqualityEvaluator<T> extends LeafEvaluator<T>
+{
+    /** The default byte[] comparator if no comparator has been defined */
+    private static final Comparator<byte[]> BINARY_COMPARATOR = new ByteArrayComparator( null );
+
+    /** The default String comparator if no comparator has been defined */
+    private static final Comparator<String> STRING_COMPARATOR = new StringComparator( null );
+
+
+    @SuppressWarnings("unchecked")
+    public EqualityEvaluator( EqualityNode<T> node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        super( node, db, schemaManager );
+
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            idx = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+        }
+
+        MatchingRule mr = attributeType.getEquality();
+
+        if ( mr == null )
+        {
+            normalizer = new NoOpNormalizer( attributeType.getOid() );
+            ldapComparator = null;
+        }
+        else
+        {
+            normalizer = mr.getNormalizer();
+            ldapComparator = mr.getLdapComparator();
+        }
+    }
+
+
+    public EqualityNode<T> getExpression()
+    {
+        return ( EqualityNode<T> ) node;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        return evaluate( entry );
+    }
+
+
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute does not exist just return false
+        if ( ( attr != null ) && evaluate( attr ) )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( ( attr != null ) && evaluate( attr ) )
+                {
+                    return true;
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    // TODO - determine if comparator and index entry should have the Value
+    // wrapper or the raw normalized value
+    private boolean evaluate( Attribute attribute ) throws Exception
+    {
+        /*
+         * Cycle through the attribute values testing normalized version
+         * obtained from using the ordering or equality matching rule's
+         * normalizer.  The test uses the comparator obtained from the
+         * appropriate matching rule to perform the check.
+         */
+        for ( Value<?> value : attribute )
+        {
+            //noinspection unchecked
+            if ( value.isHumanReadable() )
+            {
+                // Deal with a String value
+                String serverValue = ( ( Value<String> ) value ).getNormValue();
+                String nodeValue = null;
+
+                if ( node.getValue().isHumanReadable() )
+                {
+                    nodeValue = ( ( Value<String> ) node.getValue() ).getNormValue();
+                }
+                else
+                {
+                    nodeValue = Strings.utf8ToString( ( ( Value<byte[]> ) node.getValue() ).getNormValue() );
+                }
+
+                if ( ldapComparator != null )
+                {
+                    if ( ldapComparator.compare( serverValue, nodeValue ) == 0 )
+                    {
+                        return true;
+                    }
+                }
+                else
+                {
+                    if ( STRING_COMPARATOR.compare( serverValue, nodeValue ) == 0 )
+                    {
+                        return true;
+                    }
+                }
+            }
+            else
+            {
+                // Deal with a binary value
+                byte[] serverValue = ( ( Value<byte[]> ) value ).getNormValue();
+                byte[] nodeValue = ( ( Value<byte[]> ) node.getValue() ).getNormValue();
+
+                if ( ldapComparator != null )
+                {
+                    if ( ldapComparator.compare( ( Object ) serverValue, ( Object ) nodeValue ) == 0 )
+                    {
+                        return true;
+                    }
+                }
+                else
+                {
+                    if ( BINARY_COMPARATOR.compare( serverValue, nodeValue ) == 0 )
+                    {
+                        return true;
+                    }
+                }
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "EqualityEvaluator : " ).append( super.toString() ).append( '\n' );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/GreaterEqEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/GreaterEqEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/GreaterEqEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/GreaterEqEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,248 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.Iterator;
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.shared.ldap.model.entry.Attribute;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.entry.Value;
+import org.apache.directory.shared.ldap.model.filter.GreaterEqNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.MatchingRule;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+
+
+/**
+ * An Evaluator which determines if candidates are matched by GreaterEqNode
+ * assertions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class GreaterEqEvaluator<T> extends LeafEvaluator<T>
+{
+    @SuppressWarnings("unchecked")
+    public GreaterEqEvaluator( GreaterEqNode<T> node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        super( node, db, schemaManager );
+
+        if ( db.hasIndexOn( node.getAttributeType() ) )
+        {
+            idx = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+        }
+        else
+        {
+            idx = null;
+        }
+
+        /*
+         * We prefer matching using the Normalizer and Comparator pair from
+         * the ordering matchingRule if one is available.  It may very well
+         * not be.  If so then we resort to using the Normalizer and
+         * Comparator from the equality matchingRule as a last resort.
+         */
+        MatchingRule mr = attributeType.getOrdering();
+
+        if ( mr == null )
+        {
+            mr = attributeType.getEquality();
+        }
+
+        if ( mr == null )
+        {
+            throw new IllegalStateException( I18n.err( I18n.ERR_715, node ) );
+        }
+
+        normalizer = mr.getNormalizer();
+        ldapComparator = mr.getLdapComparator();
+    }
+
+
+    public GreaterEqNode getExpression()
+    {
+        return ( GreaterEqNode ) node;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        if ( idx != null && idx.isDupsEnabled() )
+        {
+            return idx.reverseGreaterOrEq( indexEntry.getId(), node.getValue().getValue() );
+        }
+
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        /*
+         * The code below could have been replaced by a call to
+         * evaluate( Entry ) but it was not because we wanted to make
+         * sure the call to evaluate with the attribute was made using a
+         * non-null IndexEntry parameter.  This is to make sure the call to
+         * evaluate with the attribute will set the value on the IndexEntry.
+         */
+
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute exists and has a greater than or equal value return true
+        //noinspection unchecked
+        if ( attr != null && evaluate( ( IndexEntry<Object, String> ) indexEntry, attr ) )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                //noinspection unchecked
+                if ( attr != null && evaluate( ( IndexEntry<Object, String> ) indexEntry, attr ) )
+                {
+                    return true;
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute exists and has a greater than or equal value return true
+        if ( ( attr != null ) && evaluate( null, attr ) )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( ( attr != null ) && evaluate( null, attr ) )
+                {
+                    return true;
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    // TODO - determine if comaparator and index entry should have the Value
+    // wrapper or the raw normalized value 
+    private boolean evaluate( IndexEntry<Object, String> indexEntry, Attribute attribute )
+        throws Exception
+    {
+        /*
+         * Cycle through the attribute values testing normalized version
+         * obtained from using the ordering or equality matching rule's
+         * normalizer.  The test uses the comparator obtained from the
+         * appropriate matching rule to perform the check.
+         */
+        for ( Value value : attribute )
+        {
+            //noinspection unchecked
+            if ( ldapComparator.compare( value.getNormValue(), node.getValue().getNormValue() ) >= 0 )
+            {
+                if ( indexEntry != null )
+                {
+                    indexEntry.setKey( value.getNormValue() );
+                }
+
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "GreaterEqEvaluator : " ).append( super.toString() ).append( "\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LeafEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LeafEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LeafEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LeafEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,114 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.SimpleNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.LdapComparator;
+import org.apache.directory.shared.ldap.model.schema.Normalizer;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+
+
+/**
+ * An abstract evaluator to store the common fileds for the Simple node evaluators
+ * (ApproximateEvaluator, EqualityEvaluator, GreaterEqEvluator and LessEqEvluator)
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public abstract class LeafEvaluator<T> implements Evaluator<SimpleNode<T>>
+{
+    /** The ExprNode to evaluate */
+    protected final SimpleNode<T> node;
+
+    /** The backend */
+    protected final Store db;
+
+    /** The SchemaManager instance */
+    protected final SchemaManager schemaManager;
+
+    /** The AttributeType we will use for the evaluation */
+    protected final AttributeType attributeType;
+
+    /** The associated normalizer */
+    protected Normalizer normalizer;
+
+    /** The associated comparator */
+    protected LdapComparator<? super Object> ldapComparator;
+
+    /** The index to use if any */
+    protected Index<T, Entry, String> idx;
+
+
+    @SuppressWarnings("unchecked")
+    public LeafEvaluator( SimpleNode<T> node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        this.db = db;
+        this.node = node;
+        this.schemaManager = schemaManager;
+        this.attributeType = node.getAttributeType();
+    }
+
+
+    /**
+     * @return The AttributeType
+     */
+    public AttributeType getAttributeType()
+    {
+        return attributeType;
+    }
+
+
+    /**
+     * @return The Normalizer associated with the AttributeType
+     */
+    public Normalizer getNormalizer()
+    {
+        return normalizer;
+    }
+
+
+    /**
+     * @return The LdapComparator associated with the AttributeType
+     */
+    public LdapComparator<? super Object> getComparator()
+    {
+        return ldapComparator;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( node );
+
+        return sb.toString();
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LessEqEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LessEqEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LessEqEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/LessEqEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,239 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.Iterator;
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.shared.ldap.model.entry.Attribute;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.entry.Value;
+import org.apache.directory.shared.ldap.model.filter.LessEqNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.MatchingRule;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+
+
+/**
+ * An Evaluator which determines if candidates are matched by LessEqNode
+ * assertions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class LessEqEvaluator<T> extends LeafEvaluator<T>
+{
+    @SuppressWarnings("unchecked")
+    public LessEqEvaluator( LessEqNode<T> node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        super( node, db, schemaManager );
+
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            idx = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+        }
+        else
+        {
+            idx = null;
+        }
+
+        /*
+         * We prefer matching using the Normalizer and Comparator pair from
+         * the ordering matchingRule if one is available.  It may very well
+         * not be.  If so then we resort to using the Normalizer and
+         * Comparator from the equality matchingRule as a last resort.
+         */
+        MatchingRule mr = attributeType.getOrdering();
+
+        if ( mr == null )
+        {
+            mr = attributeType.getEquality();
+        }
+
+        if ( mr == null )
+        {
+            throw new IllegalStateException( I18n.err( I18n.ERR_717, node ) );
+        }
+
+        normalizer = mr.getNormalizer();
+        ldapComparator = mr.getLdapComparator();
+    }
+
+
+    public LessEqNode<T> getExpression()
+    {
+        return ( LessEqNode<T> ) node;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        if ( null == entry )
+        {
+            return false;
+        }
+
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute does not exist just return false
+        //noinspection unchecked
+        if ( attr != null && evaluate( ( IndexEntry<Object, String> ) indexEntry, attr ) )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                //noinspection unchecked
+                if ( attr != null && evaluate( ( IndexEntry<Object, String> ) indexEntry, attr ) )
+                {
+                    return true;
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute does not exist just return false
+        if ( ( attr != null ) && evaluate( null, attr ) )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( attr != null && evaluate( null, attr ) )
+                {
+                    return true;
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    // TODO - determine if comaparator and index entry should have the Value
+    // wrapper or the raw normalized value
+    private boolean evaluate( IndexEntry<Object, String> indexEntry, Attribute attribute )
+        throws Exception
+    {
+        /*
+         * Cycle through the attribute values testing normalized version
+         * obtained from using the ordering or equality matching rule's
+         * normalizer.  The test uses the comparator obtained from the
+         * appropriate matching rule to perform the check.
+         */
+        for ( Value<?> value : attribute )
+        {
+            //noinspection unchecked
+            if ( ldapComparator.compare( value.getNormValue(), node.getValue().getNormValue() ) <= 0 )
+            {
+                if ( indexEntry != null )
+                {
+                    indexEntry.setKey( value.getNormValue() );
+                }
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "LessEqEvaluator : " ).append( super.toString() ).append( "\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/NotEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/NotEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/NotEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/NotEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,91 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
+import org.apache.directory.shared.ldap.model.filter.NotNode;
+
+
+/**
+ * An Evaluator for logical negation (NOT) expressions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class NotEvaluator implements Evaluator<NotNode>
+{
+    /** The ExprNode to evaluate */
+    private final NotNode node;
+
+    /** The Evaluator to use for the inner Node */
+    private final Evaluator<? extends ExprNode> childEvaluator;
+
+
+    public NotEvaluator( NotNode node, Evaluator<? extends ExprNode> childEvaluator )
+    {
+        this.node = node;
+        this.childEvaluator = childEvaluator;
+    }
+
+
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        return !childEvaluator.evaluate( entry );
+    }
+
+
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        return !childEvaluator.evaluate( indexEntry );
+    }
+
+
+    public NotNode getExpression()
+    {
+        return node;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "NotEvaluator : " ).append( node ).append( '\n' );
+
+        sb.append( childEvaluator.toString( tabs + "  " ) );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OneLevelScopeEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OneLevelScopeEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OneLevelScopeEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OneLevelScopeEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,195 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.ParentIdAndRdn;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.ScopeNode;
+import org.apache.directory.shared.ldap.model.message.SearchScope;
+
+
+/**
+ * Evaluates one level scope assertions on candidates using an entry database.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class OneLevelScopeEvaluator<E> implements Evaluator<ScopeNode>
+{
+    /** The ScopeNode containing initial search scope constraints */
+    private final ScopeNode node;
+
+    /** The entry identifier of the scope base */
+    private final String baseId;
+
+    /** True if the scope requires alias dereferencing while searching */
+    private final boolean dereferencing;
+
+    /** the entry db storing entries */
+    private final Store db;
+
+
+    /**
+     * Creates a one level scope node Evaluator for search expressions.
+     *
+     * @param node the scope node
+     * @param db the database used to evaluate scope node
+     * @throws Exception on db access failure
+     */
+    public OneLevelScopeEvaluator( Store db, ScopeNode node ) throws Exception
+    {
+        this.node = node;
+
+        if ( node.getScope() != SearchScope.ONELEVEL )
+        {
+            throw new IllegalStateException( I18n.err( I18n.ERR_720 ) );
+        }
+
+        this.db = db;
+        baseId = node.getBaseId();
+        dereferencing = node.getDerefAliases().isDerefInSearching() || node.getDerefAliases().isDerefAlways();
+    }
+
+
+    /**
+     * Asserts whether or not a candidate has one level scope while taking
+     * alias dereferencing into account.
+     *
+     * TODO - terribly inefficient - would benefit from exposing the id of an
+     * entry within the Entry
+     *
+     * {@inheritDoc}
+     */
+    public boolean evaluate( Entry candidate ) throws Exception
+    {
+        throw new UnsupportedOperationException( I18n.err( I18n.ERR_721 ) );
+    }
+
+
+    /**
+     * Asserts whether or not a candidate has one level scope while taking
+     * alias dereferencing into account.
+     *
+     * @param candidate the candidate to assert
+     * @return true if the candidate is within one level scope
+     * @throws Exception if db lookups fail
+     * @see org.apache.directory.server.xdbm.search.Evaluator#evaluate(IndexEntry)
+     */
+    public boolean evaluate( IndexEntry<?, String> candidate ) throws Exception
+    {
+        ParentIdAndRdn parent = db.getRdnIndex().reverseLookup( candidate.getId() );
+        boolean isChild = parent.getParentId().equals( baseId );
+
+        /*
+         * The candidate id could be any entry in the db.  If search
+         * dereferencing is not enabled then we return the results of the child
+         * test.
+         */
+        if ( !dereferencing )
+        {
+            return isChild;
+        }
+
+        /*
+         * From here down alias dereferencing is enabled.  We determine if the
+         * candidate id is an alias, if so we reject it since aliases should
+         * not be returned.
+         */
+        if ( null != db.getAliasIndex().reverseLookup( candidate.getId() ) )
+        {
+            return false;
+        }
+
+        /*
+         * The candidate is NOT an alias at this point.  So if it is a child we
+         * just return true since it is in normal one level scope.
+         */
+        if ( isChild )
+        {
+            return true;
+        }
+
+        /*
+         * At this point the candidate is not a child and it is not an alias.
+         * We need to check if the candidate is in extended one level scope by
+         * performing a lookup on the one level alias index.  This index stores
+         * a tuple mapping the baseId to the id of objects brought into the
+         * one level scope of the base by an alias: ( baseId, aliasedObjId )
+         * If the candidate id is an object brought into one level scope then
+         * the lookup returns true accepting the candidate.  Otherwise the
+         * candidate is rejected with a false return because it is not in scope.
+         */
+        return db.getOneAliasIndex().forward( baseId, candidate.getId() );
+    }
+
+
+    public ScopeNode getExpression()
+    {
+        return node;
+    }
+
+
+    /**
+     * Gets the id of the search base associated with the ScopeNode expression.
+     *
+     * @return identifier of the search base
+     */
+    public String getBaseId()
+    {
+        return baseId;
+    }
+
+
+    /**
+     * Gets whether or not dereferencing is enabled for this evaluator.
+     *
+     * @return true if dereferencing is enabled, false otherwise
+     */
+    public boolean isDereferencing()
+    {
+        return dereferencing;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "OneLevelScopEvaluator : " ).append( node ).append( "\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OrEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OrEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OrEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/OrEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,155 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.server.xdbm.search.impl.ScanCountComparator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
+import org.apache.directory.shared.ldap.model.filter.OrNode;
+
+
+/**
+ * An Evaluator for logical disjunction (OR) expressions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class OrEvaluator implements Evaluator<OrNode>
+{
+    /** The list of evaluators associated with each of the children */
+    private final List<Evaluator<? extends ExprNode>> evaluators;
+
+    /** The OrNode */
+    private final OrNode node;
+
+
+    public OrEvaluator( OrNode node, List<Evaluator<? extends ExprNode>> evaluators )
+    {
+        this.node = node;
+        this.evaluators = optimize( evaluators );
+    }
+
+
+    /**
+     * Takes a set of Evaluators and copies then sorts them in a new list with
+     * decreasing scan counts on their expression nodes.  This is done to have
+     * the Evaluators with the greatest scan counts which have the highest
+     * probability of accepting a candidate first.  That will increase the
+     * chance of shorting the checks on evaluators early so extra lookups and
+     * comparisons are avoided.
+     *
+     * @param unoptimized the unoptimized list of Evaluators
+     * @return optimized Evaluator list with decreasing scan count ordering
+     */
+    private List<Evaluator<? extends ExprNode>> optimize(
+        List<Evaluator<? extends ExprNode>> unoptimized )
+    {
+        List<Evaluator<? extends ExprNode>> optimized = new ArrayList<Evaluator<? extends ExprNode>>(
+            unoptimized.size() );
+        optimized.addAll( unoptimized );
+
+        Collections.sort( optimized, new ScanCountComparator() );
+
+        return optimized;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        for ( Evaluator<?> evaluator : evaluators )
+        {
+            if ( evaluator.evaluate( indexEntry ) )
+            {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        for ( Evaluator<?> evaluator : evaluators )
+        {
+            if ( evaluator.evaluate( entry ) )
+            {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    public OrNode getExpression()
+    {
+        return node;
+    }
+
+
+    /**
+     * Dumps the evaluators
+     */
+    private String dumpEvaluators( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        for ( Evaluator<? extends ExprNode> evaluator : evaluators )
+        {
+            sb.append( evaluator.toString( tabs + "  " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "OrEvaluator : " ).append( node ).append( "\n" );
+
+        if ( ( evaluators != null ) && ( evaluators.size() > 0 ) )
+        {
+            sb.append( dumpEvaluators( tabs ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PassThroughEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PassThroughEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PassThroughEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PassThroughEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,116 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.UndefinedNode;
+
+
+/**
+ * An Evaluator that always validate all the submitted values
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class PassThroughEvaluator implements Evaluator<UndefinedNode>
+{
+    /** The backend */
+    private final Store db;
+
+
+    /**
+     * Create a new instance of the PassThroughEvaluator
+     * @throws Exception
+     */
+    public PassThroughEvaluator( Store db )
+    {
+        this.db = db;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        return true;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        return true;
+    }
+
+
+    /**
+     * Gets the expression used by this expression Evaluator.
+     *
+     * @return the AST for the expression
+     */
+    public UndefinedNode getExpression()
+    {
+        return null;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "PassthroughEvaluator\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PresenceEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PresenceEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PresenceEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/PresenceEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,186 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.Iterator;
+
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.constants.SchemaConstants;
+import org.apache.directory.shared.ldap.model.entry.Attribute;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.PresenceNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+
+
+/**
+ * An Evaluator which determines if candidates are matched by GreaterEqNode
+ * assertions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class PresenceEvaluator implements Evaluator<PresenceNode>
+{
+    /** The ExprNode to evaluate */
+    private final PresenceNode node;
+
+    /** The backend */
+    private final Store db;
+
+    /** The AttributeType we will use for the evaluation */
+    private final AttributeType attributeType;
+
+    /** The SchemaManager instance */
+    private final SchemaManager schemaManager;
+
+    /** The index to use if any */
+    private final Index<String, Entry, String> idx;
+
+
+    public PresenceEvaluator( PresenceNode node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        this.db = db;
+        this.node = node;
+        this.schemaManager = schemaManager;
+        this.attributeType = node.getAttributeType();
+
+        if ( db.hasUserIndexOn( attributeType ) )
+        {
+            idx = db.getPresenceIndex();
+        }
+        else
+        {
+            idx = null;
+        }
+    }
+
+
+    public PresenceNode getExpression()
+    {
+        return node;
+    }
+
+
+    public AttributeType getAttributeType()
+    {
+        return attributeType;
+    }
+
+
+    // TODO - determine if comparator and index entry should have the Value
+    // wrapper or the raw normalized value
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        return evaluate( entry );
+    }
+
+
+    // TODO - determine if comaparator and index entry should have the Value
+    // wrapper or the raw normalized value
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        if ( db.hasSystemIndexOn( attributeType )
+            || ( attributeType.getOid().equals( SchemaConstants.ENTRY_UUID_AT_OID ) ) )
+        {
+            // we don't maintain a presence index for objectClass, entryUUID and entryCSN
+            // however as every entry has such an attribute this evaluator always evaluates to true
+            return true;
+        }
+
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute exists just return true
+        if ( attr != null )
+        {
+            return true;
+        }
+
+        // If we do not have the attribute, loop through the sub classes of
+        // the attributeType.  Perhaps the entry has an attribute value of a
+        // subtype (descendant) that will produce a match
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            do
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( attr != null )
+                {
+                    return true;
+                }
+            }
+            while ( descendants.hasNext() );
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "PresenceEvaluator : " ).append( node ).append( "\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubstringEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubstringEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubstringEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubstringEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,353 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ * 
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ * 
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import java.util.Iterator;
+import java.util.regex.Pattern;
+
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.entry.Attribute;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.entry.Value;
+import org.apache.directory.shared.ldap.model.filter.SubstringNode;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.MatchingRule;
+import org.apache.directory.shared.ldap.model.schema.Normalizer;
+import org.apache.directory.shared.ldap.model.schema.SchemaManager;
+import org.apache.directory.shared.ldap.model.schema.normalizers.NoOpNormalizer;
+
+
+/**
+ * Evaluates substring filter assertions on an entry.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class SubstringEvaluator implements Evaluator<SubstringNode>
+{
+    /** Database used while evaluating candidates */
+    private final Store db;
+
+    /** Reference to the SchemaManager */
+    private final SchemaManager schemaManager;
+
+    /** The Substring expression */
+    private final SubstringNode node;
+
+    /** The regular expression generated for the SubstringNode pattern */
+    private final Pattern regex;
+
+    /** The AttributeType we will use for the evaluation */
+    private final AttributeType attributeType;
+
+    /** The associated normalizer */
+    private final Normalizer normalizer;
+
+    /** The index to use if any */
+    private final Index<String, Entry, String> idx;
+
+
+    /**
+     * Creates a new SubstringEvaluator for substring expressions.
+     *
+     * @param node the substring expression node
+     * @param db the database this evaluator uses
+     * @param schemaManager the schema manager
+     * @throws Exception if there are failures accessing resources and the db
+     */
+    @SuppressWarnings("unchecked")
+    public SubstringEvaluator( SubstringNode node, Store db, SchemaManager schemaManager )
+        throws Exception
+    {
+        this.db = db;
+        this.node = node;
+        this.schemaManager = schemaManager;
+        this.attributeType = node.getAttributeType();
+
+        MatchingRule rule = attributeType.getSubstring();
+
+        if ( rule == null )
+        {
+            rule = attributeType.getEquality();
+        }
+
+        if ( rule != null )
+        {
+            normalizer = rule.getNormalizer();
+        }
+        else
+        {
+            normalizer = new NoOpNormalizer( attributeType.getSyntaxOid() );
+        }
+
+        // compile the regular expression to search for a matching attribute
+        // if the attributeType is humanReadable
+        if ( attributeType.getSyntax().isHumanReadable() )
+        {
+            regex = node.getRegex( normalizer );
+        }
+        else
+        {
+            regex = null;
+        }
+
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            idx = ( Index<String, Entry, String> ) db.getIndex( attributeType );
+        }
+        else
+        {
+            idx = null;
+        }
+    }
+
+
+    @SuppressWarnings("unchecked")
+    public boolean evaluate( IndexEntry<?, String> indexEntryQM ) throws Exception
+    {
+        IndexEntry<String, String> indexEntry = ( IndexEntry<String, String> ) indexEntryQM;
+
+        Entry entry = indexEntry.getEntry();
+
+        // resuscitate the entry if it has not been and set entry in IndexEntry
+        if ( null == entry )
+        {
+            entry = db.lookup( indexEntry.getId() );
+
+            if ( null == entry )
+            {
+                // The entry is not anymore present : get out
+                return false;
+            }
+
+            indexEntry.setEntry( entry );
+        }
+
+        /*
+         * Don't make a call here to evaluateWithoutIndex( Entry ) for
+         * code reuse since we do want to set the value on the indexEntry on
+         * matches.
+         */
+
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute exists and the pattern matches return true
+        if ( attr != null )
+        {
+            /*
+             * Cycle through the attribute values testing normalized version
+             * obtained from using the substring matching rule's normalizer.
+             * The test uses the comparator obtained from the appropriate
+             * substring matching rule.
+             */
+            if ( attr.isHumanReadable() )
+            {
+                for ( Value<?> value : attr )
+                {
+                    String strValue = ( String ) value.getNormValue();
+
+                    // Once match is found cleanup and return true
+                    if ( regex.matcher( strValue ).matches() )
+                    {
+                        // before returning we set the normalized value
+                        indexEntry.setKey( strValue );
+                        return true;
+                    }
+                }
+            }
+            else
+            {
+                // Slightly more complex. We won't be able to use a regex to check
+                // the value.
+                for ( Value<?> value : attr )
+                {
+                    byte[] byteValue = ( byte[] ) value.getNormValue();
+
+                    // Once match is found cleanup and return true
+                    // @TODO : implement this check.
+                    /*
+                    if ( check( byteValue ) )
+                    {
+                        // before returning we set the normalized value
+                        indexEntry.setKey( byteValue );
+                        return true;
+                    }
+                    */
+                }
+            }
+
+            // Fall through as we didn't find any matching value for this attribute.
+            // We will have to check in the potential descendant, if any.
+        }
+
+        // If we do not have the attribute, loop through the descendant
+        // May be the node Attribute has descendant ?
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( null != attr )
+                {
+
+                    /*
+                     * Cycle through the attribute values testing normalized version
+                     * obtained from using the substring matching rule's normalizer.
+                     * The test uses the comparator obtained from the appropriate
+                     * substring matching rule.
+                     */
+                    for ( Value<?> value : attr )
+                    {
+                        String strValue = ( String ) value.getNormValue();
+
+                        // Once match is found cleanup and return true
+                        if ( regex.matcher( strValue ).matches() )
+                        {
+                            // before returning we set the normalized value
+                            indexEntry.setKey( strValue );
+                            return true;
+                        }
+                    }
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        // get the attribute
+        Attribute attr = entry.get( attributeType );
+
+        // if the attribute exists and the pattern matches return true
+        if ( attr != null )
+        {
+            /*
+             * Cycle through the attribute values testing normalized version
+             * obtained from using the substring matching rule's normalizer.
+             * The test uses the comparator obtained from the appropriate
+             * substring matching rule.
+             */
+            for ( Value<?> value : attr )
+            {
+                String strValue = ( String ) value.getNormValue();
+
+                // Once match is found cleanup and return true
+                if ( regex.matcher( strValue ).matches() )
+                {
+                    return true;
+                }
+            }
+
+            // Fall through as we didn't find any matching value for this attribute.
+            // We will have to check in the potential descendant, if any.
+        }
+
+        // If we do not have the attribute, loop through the descendant
+        // May be the node Attribute has descendant ?
+        if ( schemaManager.getAttributeTypeRegistry().hasDescendants( attributeType ) )
+        {
+            // TODO check to see if descendant handling is necessary for the
+            // index so we can match properly even when for example a name
+            // attribute is used instead of more specific commonName
+            Iterator<AttributeType> descendants = schemaManager.getAttributeTypeRegistry().descendants( attributeType );
+
+            while ( descendants.hasNext() )
+            {
+                AttributeType descendant = descendants.next();
+
+                attr = entry.get( descendant );
+
+                if ( null != attr )
+                {
+
+                    /*
+                     * Cycle through the attribute values testing normalized version
+                     * obtained from using the substring matching rule's normalizer.
+                     * The test uses the comparator obtained from the appropriate
+                     * substring matching rule.
+                     */
+                    for ( Value<?> value : attr )
+                    {
+                        String strValue = ( String ) value.getNormValue();
+
+                        // Once match is found cleanup and return true
+                        if ( regex.matcher( strValue ).matches() )
+                        {
+                            return true;
+                        }
+                    }
+                }
+            }
+        }
+
+        // we fell through so a match was not found - assertion was false.
+        return false;
+    }
+
+
+    public Pattern getPattern()
+    {
+        return regex;
+    }
+
+
+    public SubstringNode getExpression()
+    {
+        return node;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "SubstringEvaluator : " ).append( node ).append( "\n" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubtreeScopeEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubtreeScopeEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubtreeScopeEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/SubtreeScopeEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,273 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *  
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License. 
+ *  
+ */
+package org.apache.directory.server.xdbm.search.evaluator;
+
+
+import org.apache.directory.server.core.api.partition.Partition;
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.ParentIdAndRdn;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.ScopeNode;
+import org.apache.directory.shared.ldap.model.message.SearchScope;
+
+
+/**
+ * Evaluates ScopeNode assertions with subtree scope on candidates using an
+ * entry database.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class SubtreeScopeEvaluator implements Evaluator<ScopeNode>
+{
+    /** The ScopeNode containing initial search scope constraints */
+    private final ScopeNode node;
+
+    /** The entry identifier of the scope base */
+    private final String baseId;
+
+    /** 
+     * Whether or not to accept all candidates.  If this evaluator's baseId is
+     * set to the context entry's id, then obviously all candidates will be 
+     * subordinate to this root ancestor or in subtree scope.  This check is 
+     * done on  initialization and used there after.  One reason we need do 
+     * this is because the subtree scope index (sub level index) does not map 
+     * the values for the context entry id to it's subordinates since it would 
+     * have to include all entries.  This is a waste of space and lookup time
+     * since we know all entries will be subordinates in this case.
+     */
+    private final boolean baseIsContextEntry;
+
+    /** True if the scope requires alias dereferencing while searching */
+    private final boolean dereferencing;
+
+    /** The entry database/store */
+    private final Store db;
+
+
+    /**
+     * Creates a subtree scope node evaluator for search expressions.
+     *
+     * @param node the scope node
+     * @param db the database used to evaluate scope node
+     * @throws Exception on db access failure
+     */
+    public SubtreeScopeEvaluator( Store db, ScopeNode node ) throws Exception
+    {
+        this.db = db;
+        this.node = node;
+
+        if ( node.getScope() != SearchScope.SUBTREE )
+        {
+            throw new IllegalStateException( I18n.err( I18n.ERR_727 ) );
+        }
+
+        baseId = node.getBaseId();
+        baseIsContextEntry = getContextEntryId() == baseId;
+        dereferencing = node.getDerefAliases().isDerefInSearching() || node.getDerefAliases().isDerefAlways();
+    }
+
+    private String contextEntryId;
+
+
+    // This will suppress PMD.EmptyCatchBlock warnings in this method
+    @SuppressWarnings("PMD.EmptyCatchBlock")
+    private String getContextEntryId() throws Exception
+    {
+        if ( contextEntryId == null )
+        {
+            try
+            {
+                this.contextEntryId = db.getEntryId( ( ( Partition ) db ).getSuffixDn() );
+            }
+            catch ( Exception e )
+            {
+                // might not have been created
+            }
+        }
+
+        if ( contextEntryId == null )
+        {
+            return Partition.DEFAULT_ID;
+        }
+
+        return contextEntryId;
+    }
+
+
+    /**
+     * Tells if a candidate is a descendant of the base ID. We have to fetch all 
+     * the parentIdAndRdn up to the baseId. If we terminate on the context entry without 
+     * having found the baseId, then the candidate is not a descendant.
+     */
+    private boolean isDescendant( String candidateId ) throws Exception
+    {
+        String tmp = candidateId;
+
+        while ( true )
+        {
+            ParentIdAndRdn parentIdAndRdn = db.getRdnIndex().reverseLookup( tmp );
+
+            if ( parentIdAndRdn == null )
+            {
+                return false;
+            }
+
+            tmp = parentIdAndRdn.getParentId();
+
+            if ( tmp.equals( Partition.ROOT_ID ) )
+            {
+                return false;
+            }
+
+            if ( tmp.equals( baseId ) )
+            {
+                return true;
+            }
+        }
+    }
+
+
+    /**
+     * Asserts whether or not a candidate has sub level scope while taking
+     * alias dereferencing into account.
+     *
+     * @param candidate the entry tested to see if it is in subtree scope
+     * @return true if the candidate is within one level scope whether or not
+     * alias dereferencing is enabled.
+     * @throws Exception if the index lookups fail.
+     * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry)
+     */
+    public boolean evaluate( IndexEntry<?, String> candidate ) throws Exception
+    {
+        String id = candidate.getId();
+
+        /*
+         * This condition catches situations where the candidate is equal to 
+         * the base entry and when the base entry is the context entry.  Note
+         * we do not store a mapping in the subtree index of the context entry
+         * to all it's subordinates since that would be the entire set of 
+         * entries in the db.
+         */
+        boolean isDescendant = baseIsContextEntry || baseId.equals( id ) || isDescendant( id );
+
+        /*
+         * The candidate id could be any entry in the db.  If search
+         * dereferencing is not enabled then we return the results of the
+         * descendant test.
+         */
+        if ( !isDereferencing() )
+        {
+            return isDescendant;
+        }
+
+        /*
+         * From here down alias dereferencing is enabled.  We determine if the
+         * candidate id is an alias, if so we reject it since aliases should
+         * not be returned.
+         */
+        if ( null != db.getAliasIndex().reverseLookup( id ) )
+        {
+            return false;
+        }
+
+        /*
+         * The candidate is NOT an alias at this point.  So if it is a
+         * descendant we just return true since it is in normal subtree scope.
+         */
+        if ( isDescendant )
+        {
+            return true;
+        }
+
+        /*
+         * At this point the candidate is not a descendant and it is not an
+         * alias.  We need to check if the candidate is in extended subtree
+         * scope by performing a lookup on the subtree alias index.  This index
+         * stores a tuple mapping the baseId to the ids of objects brought
+         * into subtree scope of the base by an alias:
+         *
+         * ( baseId, aliasedObjId )
+         *
+         * If the candidate id is an object brought into subtree scope then
+         * the lookup returns true accepting the candidate.  Otherwise the
+         * candidate is rejected with a false return because it is not in scope.
+         */
+        return db.getSubAliasIndex().forward( baseId, id );
+    }
+
+
+    /**
+     * Asserts whether or not a candidate has sub level scope while taking
+     * alias dereferencing into account.
+     *
+     * @param candidate the entry tested to see if it is in subtree scope
+     * @return true if the candidate is within one level scope whether or not
+     * alias dereferencing is enabled.
+     * @throws Exception if the index lookups fail.
+     * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry)
+     */
+    public boolean evaluate( Entry candidate ) throws Exception
+    {
+        throw new UnsupportedOperationException( I18n.err( I18n.ERR_721 ) );
+    }
+
+
+    public ScopeNode getExpression()
+    {
+        return node;
+    }
+
+
+    public String getBaseId()
+    {
+        return baseId;
+    }
+
+
+    public boolean isDereferencing()
+    {
+        return dereferencing;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "SubstreeScopeEvaluator : " ).append( node ).append( '\n' );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}



Mime
View raw message