View Javadoc

1   /*
2    *   Copyright 2004 The Apache Software Foundation
3    *
4    *   Licensed under the Apache License, Version 2.0 (the "License");
5    *   you may not use this file except in compliance with the License.
6    *   You may obtain a copy of the License at
7    *
8    *       http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *   Unless required by applicable law or agreed to in writing, software
11   *   distributed under the License is distributed on an "AS IS" BASIS,
12   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *   See the License for the specific language governing permissions and
14   *   limitations under the License.
15   *
16   */
17  package org.apache.ldap.server.partition.impl.btree;
18  
19  
20  import java.math.BigInteger;
21  import java.util.ArrayList;
22  
23  import javax.naming.NamingEnumeration;
24  import javax.naming.NamingException;
25  
26  import org.apache.ldap.common.NotImplementedException;
27  import org.apache.ldap.common.filter.AssertionNode;
28  import org.apache.ldap.common.filter.BranchNode;
29  import org.apache.ldap.common.filter.ExprNode;
30  import org.apache.ldap.common.filter.LeafNode;
31  import org.apache.ldap.common.filter.PresenceNode;
32  import org.apache.ldap.common.filter.ScopeNode;
33  import org.apache.ldap.common.filter.SimpleNode;
34  import org.apache.ldap.server.schema.AttributeTypeRegistry;
35  
36  
37  /***
38   * Enumerates over candidates that satisfy a filter expression.
39   * 
40   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
41   * @version $Rev: 264732 $
42   */
43  public class ExpressionEnumerator implements Enumerator
44  {
45      /*** The database used by this enumerator */
46      private BTreeContextPartition db = null;
47      /*** Enumerator flyweight for evaulating filter scope assertions */
48      private ScopeEnumerator scopeEnumerator;
49      /*** Enumerator flyweight for evaulating filter substring assertions */
50      private SubstringEnumerator substringEnumerator;
51      /*** Evaluator dependency on a ExpressionEvaluator */
52      private ExpressionEvaluator evaluator;
53  
54  
55      /***
56       * Creates an expression tree enumerator.
57       *
58       * @param db database used by this enumerator
59       * @param evaluator
60       */
61      public ExpressionEnumerator( BTreeContextPartition db,
62                                   AttributeTypeRegistry attributeTypeRegistry,
63                                   ExpressionEvaluator evaluator )
64      {
65          this.db = db;
66          this.evaluator = evaluator;
67  
68          LeafEvaluator leafEvaluator = evaluator.getLeafEvaluator();
69          scopeEnumerator = new ScopeEnumerator( db, leafEvaluator.getScopeEvaluator() );
70          substringEnumerator = new SubstringEnumerator( db, attributeTypeRegistry,
71                  leafEvaluator.getSubstringEvaluator() );
72      }
73  
74  
75      /***
76       * Creates an enumeration to enumerate through the set of candidates 
77       * satisfying a filter expression.
78       * 
79       * @param node a filter expression root
80       * @return an enumeration over the 
81       * @throws NamingException if database access fails
82       */
83      public NamingEnumeration enumerate( ExprNode node ) throws NamingException
84      {
85          NamingEnumeration list = null;
86  
87          if ( node instanceof ScopeNode )
88          {
89              list = scopeEnumerator.enumerate( node );
90          }
91          else if ( node instanceof AssertionNode )
92          {
93              throw new IllegalArgumentException( "Cannot produce enumeration " 
94                  + "on an AssertionNode" );
95          }
96          else if ( node.isLeaf() ) 
97          {
98              LeafNode leaf = ( LeafNode ) node;
99  
100             switch( leaf.getAssertionType() )
101             {
102             case( LeafNode.APPROXIMATE ):
103                 list = enumEquality( ( SimpleNode ) node );
104                 break;
105             case( LeafNode.EQUALITY ):
106                 list = enumEquality( ( SimpleNode ) node );
107                 break;
108             case( LeafNode.EXTENSIBLE ):
109                 // N O T   I M P L E M E N T E D   Y E T !
110                 throw new NotImplementedException();
111             case( LeafNode.GREATEREQ ):
112                 list = enumGreater( ( SimpleNode ) node, true );
113                 break;
114             case( LeafNode.LESSEQ ):
115                 list = enumGreater( ( SimpleNode ) node, false );
116                 break;
117             case( LeafNode.PRESENCE ):
118                 list = enumPresence( ( PresenceNode ) node );
119                 break;
120             case( LeafNode.SUBSTRING ):
121                 list = substringEnumerator.enumerate( leaf );
122                 break;
123             default:
124                 throw new IllegalArgumentException( "Unknown leaf assertion" );
125             }
126         } 
127         else 
128         {
129             BranchNode branch = ( BranchNode ) node;
130             
131             switch( branch.getOperator() )
132             {
133             case( BranchNode.AND ):
134                 list = enumConj( branch );
135                 break;
136             case( BranchNode.NOT ):
137                 list = enumNeg( branch );
138                 break;
139             case( BranchNode.OR ):
140                 list = enumDisj( branch );
141                 break;
142             default:
143                 throw new IllegalArgumentException( 
144                     "Unknown branch logical operator" );
145             }
146         }
147 
148         return list;
149     }
150 
151 
152     /***
153      * Creates an enumeration over a disjunction expression branch node.
154      *
155      * @param node the disjunction expression branch node
156      */
157     private NamingEnumeration enumDisj( BranchNode node ) throws NamingException
158     {
159         ArrayList children = node.getChildren();
160         NamingEnumeration[] childEnumerations = new NamingEnumeration [children.size()];
161 
162         // Recursively create NamingEnumerations for each child expression node
163         for ( int ii = 0; ii < childEnumerations.length; ii++ )
164         {
165             childEnumerations[ii] = enumerate( ( ExprNode ) children.get( ii ) );
166         }
167 
168         return new DisjunctionEnumeration( childEnumerations );
169     }
170 
171 
172     /***
173      * Creates an enumeration over a negation expression branch node.
174      *
175      * @param node a negation expression branch node
176      */
177     private NamingEnumeration enumNeg( final BranchNode node ) throws NamingException
178     {
179         Index idx = null;
180         NamingEnumeration childEnumeration = null;
181         NamingEnumeration enumeration = null;
182 
183         // Iterates over entire set of index values
184         if ( node.getChild().isLeaf() )
185         {
186             LeafNode child = ( LeafNode ) node.getChild();
187             idx = db.getUserIndex( child.getAttribute() );
188             childEnumeration = idx.listIndices();
189         }
190         // Iterates over the entire set of entries
191         else
192         {
193             idx = db.getNdnIndex();
194             childEnumeration = idx.listIndices();
195         }
196 
197 
198         IndexAssertion assertion = new IndexAssertion()
199         {
200             public boolean assertCandidate( IndexRecord rec ) throws NamingException
201             {
202                 // NOTICE THE ! HERE
203                 // The candidate is valid if it does not pass assertion. A
204                 // candidate that passes assertion is therefore invalid.
205                 return ! evaluator.evaluate( node.getChild(), rec );
206             }
207         };
208 
209         enumeration = new IndexAssertionEnumeration( childEnumeration, assertion, true );
210         return enumeration;
211     }
212 
213 
214     /***
215      * Creates an enumeration over a conjunction expression branch node.
216      *
217      * @param node a conjunction expression branch node
218      */
219     private NamingEnumeration enumConj( final BranchNode node ) throws NamingException
220     {
221         int minIndex = 0;
222         int minValue = Integer.MAX_VALUE;
223         int value = Integer.MAX_VALUE;
224 
225         /*
226          * We scan the child nodes of a branch node searching for the child
227          * expression node with the smallest scan count.  This is the child
228          * we will use for iteration by creating a NamingEnumeration over its
229          * expression.
230          */
231         final ArrayList children = node.getChildren();
232         for ( int ii = 0; ii < children.size(); ii++ )
233         {
234             ExprNode child = ( ExprNode ) children.get( ii );
235             value = ( ( BigInteger ) child.get( "count" ) ).intValue();
236             minValue = Math.min( minValue, value );
237 
238             if ( minValue == value )
239             {
240                 minIndex = ii;
241             }
242         }
243 
244         // Once found we build the child enumeration & the wrapping enum
245         final ExprNode minChild = ( ExprNode ) children.get( minIndex );
246         IndexAssertion assertion = new IndexAssertion()
247         {
248             public boolean assertCandidate( IndexRecord rec ) throws NamingException
249             {
250                 for ( int ii = 0; ii < children.size(); ii++ )
251                 {
252                     ExprNode child = ( ExprNode ) children.get( ii );
253 
254                     // Skip the child (with min scan count) chosen for enum
255                     if ( child == minChild )
256                     {
257                         continue;
258                     }
259                     else if ( ! evaluator.evaluate( child, rec ) )
260                     {
261                         return false;
262                     }
263                 }
264 
265                 return true;
266             }
267         };
268 
269         // Do recursive call to build child enumeration then wrap and return
270         NamingEnumeration underlying = enumerate( minChild );
271         IndexAssertionEnumeration iae;
272         iae = new IndexAssertionEnumeration( underlying, assertion );
273         return iae;
274     }
275 
276 
277     /***
278      * Returns an enumeration over candidates that satisfy a presence attribute 
279      * value assertion.
280      * 
281      * @param node the presence AVA node
282      * @return an enumeration over the index records matching the AVA
283      * @throws NamingException if there is a failure while accessing the db
284      */
285     private NamingEnumeration enumPresence( final PresenceNode node ) 
286         throws NamingException
287     {
288         if ( db.hasUserIndexOn( node.getAttribute() ) )
289         {
290             Index idx = db.getExistanceIndex();
291             return idx.listIndices( node.getAttribute() );
292         }
293         
294         return nonIndexedScan( node );
295     }
296     
297 
298     /***
299      * Returns an enumeration over candidates that satisfy a simple greater than
300      * or less than or equal to attribute value assertion.
301      * 
302      * @param node the AVA node
303      * @param isGreater true if >= false if <= is used
304      * @return an enumeration over the index records matching the AVA
305      * @throws NamingException if there is a failure while accessing the db
306      */
307     private NamingEnumeration enumGreater( final SimpleNode node, 
308         final boolean isGreater ) throws NamingException
309     {
310         if ( db.hasUserIndexOn( node.getAttribute() ) )
311         {
312             Index idx = db.getUserIndex( node.getAttribute() );
313             
314             if ( isGreater )
315             {
316                 return idx.listIndices( node.getValue(), true );
317             }
318             else 
319             {
320                 return idx.listIndices( node.getValue(), false );
321             }
322         }
323 
324         return nonIndexedScan( node );
325     }
326     
327     
328     /***
329      * Returns an enumeration over candidates that satisfy a simple equality 
330      * attribute value assertion.
331      * 
332      * @param node the equality AVA node
333      * @return an enumeration over the index records matching the AVA
334      * @throws NamingException if there is a failure while accessing the db
335      */
336     private NamingEnumeration enumEquality( final SimpleNode node )
337         throws NamingException
338     {
339         if ( db.hasUserIndexOn( node.getAttribute() ) )
340         {
341             Index idx = db.getUserIndex( node.getAttribute() );
342             return idx.listIndices( node.getValue() );
343         }
344 
345         return nonIndexedScan( node );
346     }
347     
348     
349     /***
350      * Creates a scan over all entries in the database with an assertion to test
351      * for the correct evaluation of a filter expression on a LeafNode.
352      * 
353      * @param node the leaf node to produce a scan over
354      * @return the enumeration over all perspective candidates satisfying expr
355      * @throws NamingException if db access failures result
356      */
357     private NamingEnumeration nonIndexedScan( final LeafNode node )
358         throws NamingException
359     {
360         NamingEnumeration underlying = db.getNdnIndex().listIndices();
361         IndexAssertion assertion = new IndexAssertion()
362         {
363             public boolean assertCandidate( IndexRecord record ) 
364                 throws NamingException
365             {
366                 return evaluator.getLeafEvaluator().evaluate( node, record );
367             }
368         };
369         
370         return new IndexAssertionEnumeration( underlying, assertion );
371     }
372 }