001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.xdbm.search.impl; 021 022 023 import org.apache.directory.shared.ldap.filter.ScopeNode; 024 import org.apache.directory.shared.ldap.filter.SearchScope; 025 import org.apache.directory.server.i18n.I18n; 026 import org.apache.directory.server.xdbm.IndexEntry; 027 import org.apache.directory.server.xdbm.Store; 028 import org.apache.directory.server.xdbm.search.Evaluator; 029 030 031 /** 032 * Evaluates ScopeNode assertions with subtree scope on candidates using an 033 * entry database. 034 * 035 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 036 * @version $Rev: 917312 $ 037 */ 038 public class SubtreeScopeEvaluator<E, ID> implements Evaluator<ScopeNode, E, ID> 039 { 040 /** The ScopeNode containing initial search scope constraints */ 041 private final ScopeNode node; 042 043 /** The entry identifier of the scope base */ 044 private final ID baseId; 045 046 /** 047 * Whether or not to accept all candidates. If this evaluator's baseId is 048 * set to the context entry's id, then obviously all candidates will be 049 * subordinate to this root ancestor or in subtree scope. This check is 050 * done on initialization and used there after. One reason we need do 051 * this is because the subtree scope index (sub level index) does not map 052 * the values for the context entry id to it's subordinates since it would 053 * have to include all entries. This is a waste of space and lookup time 054 * since we know all entries will be subordinates in this case. 055 */ 056 private final boolean baseIsContextEntry; 057 058 /** True if the scope requires alias dereferencing while searching */ 059 private final boolean dereferencing; 060 061 /** The entry database/store */ 062 private final Store<E, ID> db; 063 064 065 /** 066 * Creates a subtree scope node evaluator for search expressions. 067 * 068 * @param node the scope node 069 * @param db the database used to evaluate scope node 070 * @throws Exception on db access failure 071 */ 072 public SubtreeScopeEvaluator( Store<E, ID> db, ScopeNode node ) throws Exception 073 { 074 this.db = db; 075 this.node = node; 076 077 if ( node.getScope() != SearchScope.SUBTREE ) 078 { 079 throw new IllegalStateException( I18n.err( I18n.ERR_727 ) ); 080 } 081 082 baseId = db.getEntryId( node.getBaseDn() ); 083 baseIsContextEntry = getContextEntryId() == baseId; 084 dereferencing = node.getDerefAliases().isDerefInSearching() || node.getDerefAliases().isDerefAlways(); 085 } 086 087 private ID contextEntryId; 088 089 090 private ID getContextEntryId() throws Exception 091 { 092 if ( contextEntryId == null ) 093 { 094 try 095 { 096 this.contextEntryId = db.getEntryId( db.getSuffix().getNormName() ); 097 } 098 catch ( Exception e ) 099 { 100 // might not have been created 101 // might not have been created 102 } 103 } 104 105 if ( contextEntryId == null ) 106 { 107 return db.getDefaultId(); 108 } 109 110 return contextEntryId; 111 } 112 113 114 /** 115 * Asserts whether or not a candidate has one level scope while taking 116 * alias dereferencing into account. 117 * 118 * @param candidate the entry tested to see if it is in subtree scope 119 * @return true if the candidate is within one level scope whether or not 120 * alias dereferencing is enabled. 121 * @throws Exception if the index lookups fail. 122 * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry) 123 */ 124 public boolean evaluate( IndexEntry<?, E, ID> candidate ) throws Exception 125 { 126 /* 127 * This condition catches situations where the candidate is equal to 128 * the base entry and when the base entry is the context entry. Note 129 * we do not store a mapping in the subtree index of the context entry 130 * to all it's subordinates since that would be the entire set of 131 * entries in the db. 132 */ 133 if ( baseIsContextEntry || baseId.equals( candidate.getId() ) ) 134 { 135 return true; 136 } 137 138 boolean isDescendant = db.getSubLevelIndex().forward( baseId, candidate.getId() ); 139 140 /* 141 * The candidate id could be any entry in the db. If search 142 * dereferencing is not enabled then we return the results of the 143 * descendant test. 144 */ 145 if ( !isDereferencing() ) 146 { 147 return isDescendant; 148 } 149 150 /* 151 * From here down alias dereferencing is enabled. We determine if the 152 * candidate id is an alias, if so we reject it since aliases should 153 * not be returned. 154 */ 155 if ( null != db.getAliasIndex().reverseLookup( candidate.getId() ) ) 156 { 157 return false; 158 } 159 160 /* 161 * The candidate is NOT an alias at this point. So if it is a 162 * descendant we just return true since it is in normal subtree scope. 163 */ 164 if ( isDescendant ) 165 { 166 return true; 167 } 168 169 /* 170 * At this point the candidate is not a descendant and it is not an 171 * alias. We need to check if the candidate is in extended subtree 172 * scope by performing a lookup on the subtree alias index. This index 173 * stores a tuple mapping the baseId to the ids of objects brought 174 * into subtree scope of the base by an alias: 175 * 176 * ( baseId, aliasedObjId ) 177 * 178 * If the candidate id is an object brought into subtree scope then 179 * the lookup returns true accepting the candidate. Otherwise the 180 * candidate is rejected with a false return because it is not in scope. 181 */ 182 return db.getSubAliasIndex().forward( baseId, candidate.getId() ); 183 } 184 185 186 /** 187 * Asserts whether or not a candidate has one level scope while taking 188 * alias dereferencing into account. 189 * 190 * @param id the id of the entry tested to see if it is in subtree scope 191 * @return true if the candidate is within one level scope whether or not 192 * alias dereferencing is enabled. 193 * @throws Exception if the index lookups fail. 194 * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry) 195 */ 196 public boolean evaluateId( ID id ) throws Exception 197 { 198 boolean isDescendant = db.getSubLevelIndex().forward( baseId, id ); 199 200 /* 201 * The candidate id could be any entry in the db. If search 202 * dereferencing is not enabled then we return the results of the 203 * descendant test. 204 */ 205 if ( !isDereferencing() ) 206 { 207 return isDescendant; 208 } 209 210 /* 211 * From here down alias dereferencing is enabled. We determine if the 212 * candidate id is an alias, if so we reject it since aliases should 213 * not be returned. 214 */ 215 if ( null != db.getAliasIndex().reverseLookup( id ) ) 216 { 217 return false; 218 } 219 220 /* 221 * The candidate is NOT an alias at this point. So if it is a 222 * descendant we just return true since it is in normal subtree scope. 223 */ 224 if ( isDescendant ) 225 { 226 return true; 227 } 228 229 /* 230 * At this point the candidate is not a descendant and it is not an 231 * alias. We need to check if the candidate is in extended subtree 232 * scope by performing a lookup on the subtree alias index. This index 233 * stores a tuple mapping the baseId to the ids of objects brought 234 * into subtree scope of the base by an alias: 235 * 236 * ( baseId, aliasedObjId ) 237 * 238 * If the candidate id is an object brought into subtree scope then 239 * the lookup returns true accepting the candidate. Otherwise the 240 * candidate is rejected with a false return because it is not in scope. 241 */ 242 return db.getSubAliasIndex().forward( baseId, id ); 243 } 244 245 246 /** 247 * Asserts whether or not a candidate has one level scope while taking 248 * alias dereferencing into account. 249 * 250 * @param candidate the entry tested to see if it is in subtree scope 251 * @return true if the candidate is within one level scope whether or not 252 * alias dereferencing is enabled. 253 * @throws Exception if the index lookups fail. 254 * @see Evaluator#evaluate(org.apache.directory.server.xdbm.IndexEntry) 255 */ 256 public boolean evaluateEntry( E candidate ) throws Exception 257 { 258 throw new UnsupportedOperationException( I18n.err( I18n.ERR_721 ) ); 259 } 260 261 262 public ScopeNode getExpression() 263 { 264 return node; 265 } 266 267 268 public ID getBaseId() 269 { 270 return baseId; 271 } 272 273 274 public boolean isDereferencing() 275 { 276 return dereferencing; 277 } 278 }