1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
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
177 if ( node.getChild().isLeaf() )
178 {
179 LeafNode child = ( LeafNode ) node.getChild();
180 idx = db.getUserIndex( child.getAttribute() );
181 childEnumeration = idx.listIndices();
182 }
183
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
196
197
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
220
221
222
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
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
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
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 }