1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
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
184 if ( node.getChild().isLeaf() )
185 {
186 LeafNode child = ( LeafNode ) node.getChild();
187 idx = db.getUserIndex( child.getAttribute() );
188 childEnumeration = idx.listIndices();
189 }
190
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
203
204
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
227
228
229
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
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
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
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 }