View Javadoc

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 }