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    }