1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 *
19 */
20 package org.apache.directory.server.xdbm.search.impl;
21
22
23 import org.apache.directory.shared.ldap.filter.ScopeNode;
24 import org.apache.directory.shared.ldap.filter.SearchScope;
25 import org.apache.directory.server.xdbm.IndexEntry;
26 import org.apache.directory.server.xdbm.Store;
27 import org.apache.directory.server.xdbm.search.Evaluator;
28
29
30 /**
31 * Evaluates ScopeNode assertions with subtree scope on candidates using an
32 * entry database.
33 *
34 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
35 * @version $Rev: 689396 $
36 */
37 public class SubtreeScopeEvaluator<E> implements Evaluator<ScopeNode,E>
38 {
39 /** The ScopeNode containing initial search scope constraints */
40 private final ScopeNode node;
41
42 /** The entry identifier of the scope base */
43 private final Long baseId;
44
45 /**
46 * Whether or not to accept all candidates. If this evaluator's baseId is
47 * set to the context entry's id, then obviously all candidates will be
48 * subordinate to this root ancestor or in subtree scope. This check is
49 * done on initialization and used there after. One reason we need do
50 * this is because the subtree scope index (sub level index) does not map
51 * the values for the context entry id to it's subordinates since it would
52 * have to include all entries. This is a waste of space and lookup time
53 * since we know all entries will be subordinates in this case.
54 */
55 private final boolean baseIsContextEntry;
56
57 /** True if the scope requires alias dereferencing while searching */
58 private final boolean dereferencing;
59
60 /** The entry database/store */
61 private final Store<E> db;
62
63
64 /**
65 * Creates a subtree scope node evaluator for search expressions.
66 *
67 * @param node the scope node
68 * @param db the database used to evaluate scope node
69 * @throws Exception on db access failure
70 */
71 public SubtreeScopeEvaluator( Store<E> db, ScopeNode node ) throws Exception
72 {
73 this.db = db;
74 this.node = node;
75
76 if ( node.getScope() != SearchScope.SUBTREE )
77 {
78 throw new IllegalStateException( "ScopeNode is not of subtree scope." );
79 }
80
81 baseId = db.getEntryId( node.getBaseDn() );
82 baseIsContextEntry = getContextEntryId() == baseId;
83 dereferencing = node.getDerefAliases().isDerefInSearching() ||
84 node.getDerefAliases().isDerefAlways();
85 }
86
87
88 private Long contextEntryId;
89
90
91 private Long getContextEntryId()
92 {
93 if ( contextEntryId == null )
94 {
95 try
96 {
97 this.contextEntryId = db.getEntryId( db.getSuffix().getNormName() );
98 }
99 catch ( Exception e )
100 {
101 // might not have been created
102 // might not have been created
103 }
104 }
105
106 if ( contextEntryId == null )
107 {
108 return 1L;
109 }
110
111 return contextEntryId;
112 }
113
114
115 /**
116 * Asserts whether or not a candidate has one level scope while taking
117 * alias dereferencing into account.
118 *
119 * @param candidate the entry tested to see if it is in subtree scope
120 * @return true if the candidate is within one level scope whether or not
121 * alias dereferencing is enabled.
122 * @throws Exception if the index lookups fail.
123 * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry)
124 */
125 public boolean evaluate( IndexEntry<?,E> candidate ) throws Exception
126 {
127 /*
128 * This condition catches situations where the candidate is equal to
129 * the base entry and when the base entry is the context entry. Note
130 * we do not store a mapping in the subtree index of the context entry
131 * to all it's subordinates since that would be the entire set of
132 * entries in the db.
133 */
134 if ( baseIsContextEntry || baseId.longValue() == candidate.getId().longValue() )
135 {
136 return true;
137 }
138
139 boolean isDescendant = db.getSubLevelIndex().forward( baseId, candidate.getId() );
140
141 /*
142 * The candidate id could be any entry in the db. If search
143 * dereferencing is not enabled then we return the results of the
144 * descendant test.
145 */
146 if ( ! isDereferencing() )
147 {
148 return isDescendant;
149 }
150
151 /*
152 * From here down alias dereferencing is enabled. We determine if the
153 * candidate id is an alias, if so we reject it since aliases should
154 * not be returned.
155 */
156 if ( null != db.getAliasIndex().reverseLookup( candidate.getId() ) )
157 {
158 return false;
159 }
160
161 /*
162 * The candidate is NOT an alias at this point. So if it is a
163 * descendant we just return true since it is in normal subtree scope.
164 */
165 if ( isDescendant )
166 {
167 return true;
168 }
169
170 /*
171 * At this point the candidate is not a descendant and it is not an
172 * alias. We need to check if the candidate is in extended subtree
173 * scope by performing a lookup on the subtree alias index. This index
174 * stores a tuple mapping the baseId to the ids of objects brought
175 * into subtree scope of the base by an alias:
176 *
177 * ( baseId, aliasedObjId )
178 *
179 * If the candidate id is an object brought into subtree scope then
180 * the lookup returns true accepting the candidate. Otherwise the
181 * candidate is rejected with a false return because it is not in scope.
182 */
183 return db.getSubAliasIndex().forward( baseId, candidate.getId() );
184 }
185
186
187 /**
188 * Asserts whether or not a candidate has one level scope while taking
189 * alias dereferencing into account.
190 *
191 * @param id the id of the entry tested to see if it is in subtree scope
192 * @return true if the candidate is within one level scope whether or not
193 * alias dereferencing is enabled.
194 * @throws Exception if the index lookups fail.
195 * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry)
196 */
197 public boolean evaluate( Long id ) throws Exception
198 {
199 boolean isDescendant = db.getSubLevelIndex().forward( baseId, id );
200
201 /*
202 * The candidate id could be any entry in the db. If search
203 * dereferencing is not enabled then we return the results of the
204 * descendant test.
205 */
206 if ( ! isDereferencing() )
207 {
208 return isDescendant;
209 }
210
211 /*
212 * From here down alias dereferencing is enabled. We determine if the
213 * candidate id is an alias, if so we reject it since aliases should
214 * not be returned.
215 */
216 if ( null != db.getAliasIndex().reverseLookup( id ) )
217 {
218 return false;
219 }
220
221 /*
222 * The candidate is NOT an alias at this point. So if it is a
223 * descendant we just return true since it is in normal subtree scope.
224 */
225 if ( isDescendant )
226 {
227 return true;
228 }
229
230 /*
231 * At this point the candidate is not a descendant and it is not an
232 * alias. We need to check if the candidate is in extended subtree
233 * scope by performing a lookup on the subtree alias index. This index
234 * stores a tuple mapping the baseId to the ids of objects brought
235 * into subtree scope of the base by an alias:
236 *
237 * ( baseId, aliasedObjId )
238 *
239 * If the candidate id is an object brought into subtree scope then
240 * the lookup returns true accepting the candidate. Otherwise the
241 * candidate is rejected with a false return because it is not in scope.
242 */
243 return db.getSubAliasIndex().forward( baseId, id );
244 }
245
246
247 /**
248 * Asserts whether or not a candidate has one level scope while taking
249 * alias dereferencing into account.
250 *
251 * @param candidate the entry tested to see if it is in subtree scope
252 * @return true if the candidate is within one level scope whether or not
253 * alias dereferencing is enabled.
254 * @throws Exception if the index lookups fail.
255 * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry)
256 */
257 public boolean evaluate( E candidate ) throws Exception
258 {
259 throw new UnsupportedOperationException( "This is too inefficient without getId() on ServerEntry" );
260 }
261
262
263 public ScopeNode getExpression()
264 {
265 return node;
266 }
267
268
269 public Long getBaseId()
270 {
271 return baseId;
272 }
273
274
275 public boolean isDereferencing()
276 {
277 return dereferencing;
278 }
279 }