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 }