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