1/* filterindex.c - generate the list of candidate entries from a filter */
2/* $OpenLDAP$ */
3/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2000-2011 The OpenLDAP Foundation.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
10 * Public License.
11 *
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
15 */
16
17#include "portable.h"
18
19#include <stdio.h>
20#include <ac/string.h>
21
22#include "back-bdb.h"
23#include "idl.h"
24#ifdef LDAP_COMP_MATCH
25#include <component.h>
26#endif
27
28static int presence_candidates(
29	Operation *op,
30	DB_TXN *rtxn,
31	AttributeDescription *desc,
32	ID *ids );
33
34static int equality_candidates(
35	Operation *op,
36	DB_TXN *rtxn,
37	AttributeAssertion *ava,
38	ID *ids,
39	ID *tmp );
40static int inequality_candidates(
41	Operation *op,
42	DB_TXN *rtxn,
43	AttributeAssertion *ava,
44	ID *ids,
45	ID *tmp,
46	int gtorlt );
47static int approx_candidates(
48	Operation *op,
49	DB_TXN *rtxn,
50	AttributeAssertion *ava,
51	ID *ids,
52	ID *tmp );
53static int substring_candidates(
54	Operation *op,
55	DB_TXN *rtxn,
56	SubstringsAssertion *sub,
57	ID *ids,
58	ID *tmp );
59
60static int list_candidates(
61	Operation *op,
62	DB_TXN *rtxn,
63	Filter *flist,
64	int ftype,
65	ID *ids,
66	ID *tmp,
67	ID *stack );
68
69static int
70ext_candidates(
71        Operation *op,
72		DB_TXN *rtxn,
73        MatchingRuleAssertion *mra,
74        ID *ids,
75        ID *tmp,
76        ID *stack);
77
78#ifdef LDAP_COMP_MATCH
79static int
80comp_candidates (
81	Operation *op,
82	DB_TXN *rtxn,
83	MatchingRuleAssertion *mra,
84	ComponentFilter *f,
85	ID *ids,
86	ID *tmp,
87	ID *stack);
88
89static int
90ava_comp_candidates (
91		Operation *op,
92		DB_TXN *rtxn,
93		AttributeAssertion *ava,
94		AttributeAliasing *aa,
95		ID *ids,
96		ID *tmp,
97		ID *stack);
98#endif
99
100int
101bdb_filter_candidates(
102	Operation *op,
103	DB_TXN *rtxn,
104	Filter	*f,
105	ID *ids,
106	ID *tmp,
107	ID *stack )
108{
109	int rc = 0;
110#ifdef LDAP_COMP_MATCH
111	AttributeAliasing *aa;
112#endif
113	Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 );
114
115	if ( f->f_choice & SLAPD_FILTER_UNDEFINED ) {
116		BDB_IDL_ZERO( ids );
117		goto out;
118	}
119
120	switch ( f->f_choice ) {
121	case SLAPD_FILTER_COMPUTED:
122		switch( f->f_result ) {
123		case SLAPD_COMPARE_UNDEFINED:
124		/* This technically is not the same as FALSE, but it
125		 * certainly will produce no matches.
126		 */
127		/* FALL THRU */
128		case LDAP_COMPARE_FALSE:
129			BDB_IDL_ZERO( ids );
130			break;
131		case LDAP_COMPARE_TRUE: {
132			struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
133			BDB_IDL_ALL( bdb, ids );
134			} break;
135		case LDAP_SUCCESS:
136			/* this is a pre-computed scope, leave it alone */
137			break;
138		}
139		break;
140	case LDAP_FILTER_PRESENT:
141		Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
142		rc = presence_candidates( op, rtxn, f->f_desc, ids );
143		break;
144
145	case LDAP_FILTER_EQUALITY:
146		Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
147#ifdef LDAP_COMP_MATCH
148		if ( is_aliased_attribute && ( aa = is_aliased_attribute ( f->f_ava->aa_desc ) ) ) {
149			rc = ava_comp_candidates ( op, rtxn, f->f_ava, aa, ids, tmp, stack );
150		}
151		else
152#endif
153		{
154			rc = equality_candidates( op, rtxn, f->f_ava, ids, tmp );
155		}
156		break;
157
158	case LDAP_FILTER_APPROX:
159		Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
160		rc = approx_candidates( op, rtxn, f->f_ava, ids, tmp );
161		break;
162
163	case LDAP_FILTER_SUBSTRINGS:
164		Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
165		rc = substring_candidates( op, rtxn, f->f_sub, ids, tmp );
166		break;
167
168	case LDAP_FILTER_GE:
169		/* if no GE index, use pres */
170		Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
171		if( f->f_ava->aa_desc->ad_type->sat_ordering &&
172			( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
173			rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_GE );
174		else
175			rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
176		break;
177
178	case LDAP_FILTER_LE:
179		/* if no LE index, use pres */
180		Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
181		if( f->f_ava->aa_desc->ad_type->sat_ordering &&
182			( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
183			rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_LE );
184		else
185			rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
186		break;
187
188	case LDAP_FILTER_NOT:
189		/* no indexing to support NOT filters */
190		Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
191		{ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
192		BDB_IDL_ALL( bdb, ids );
193		}
194		break;
195
196	case LDAP_FILTER_AND:
197		Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
198		rc = list_candidates( op, rtxn,
199			f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
200		break;
201
202	case LDAP_FILTER_OR:
203		Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
204		rc = list_candidates( op, rtxn,
205			f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
206		break;
207	case LDAP_FILTER_EXT:
208                Debug( LDAP_DEBUG_FILTER, "\tEXT\n", 0, 0, 0 );
209                rc = ext_candidates( op, rtxn, f->f_mra, ids, tmp, stack );
210                break;
211	default:
212		Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
213			(unsigned long) f->f_choice, 0, 0 );
214		/* Must not return NULL, otherwise extended filters break */
215		{ struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
216		BDB_IDL_ALL( bdb, ids );
217		}
218	}
219
220out:
221	Debug( LDAP_DEBUG_FILTER,
222		"<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n",
223		(long) ids[0],
224		(long) BDB_IDL_FIRST( ids ),
225		(long) BDB_IDL_LAST( ids ) );
226
227	return rc;
228}
229
230#ifdef LDAP_COMP_MATCH
231static int
232comp_list_candidates(
233	Operation *op,
234	DB_TXN *rtxn,
235	MatchingRuleAssertion* mra,
236	ComponentFilter	*flist,
237	int	ftype,
238	ID *ids,
239	ID *tmp,
240	ID *save )
241{
242	int rc = 0;
243	ComponentFilter	*f;
244
245	Debug( LDAP_DEBUG_FILTER, "=> comp_list_candidates 0x%x\n", ftype, 0, 0 );
246	for ( f = flist; f != NULL; f = f->cf_next ) {
247		/* ignore precomputed scopes */
248		if ( f->cf_choice == SLAPD_FILTER_COMPUTED &&
249		     f->cf_result == LDAP_SUCCESS ) {
250			continue;
251		}
252		BDB_IDL_ZERO( save );
253		rc = comp_candidates( op, rtxn, mra, f, save, tmp, save+BDB_IDL_UM_SIZE );
254
255		if ( rc != 0 ) {
256			if ( ftype == LDAP_COMP_FILTER_AND ) {
257				rc = 0;
258				continue;
259			}
260			break;
261		}
262
263		if ( ftype == LDAP_COMP_FILTER_AND ) {
264			if ( f == flist ) {
265				BDB_IDL_CPY( ids, save );
266			} else {
267				bdb_idl_intersection( ids, save );
268			}
269			if( BDB_IDL_IS_ZERO( ids ) )
270				break;
271		} else {
272			if ( f == flist ) {
273				BDB_IDL_CPY( ids, save );
274			} else {
275				bdb_idl_union( ids, save );
276			}
277		}
278	}
279
280	if( rc == LDAP_SUCCESS ) {
281		Debug( LDAP_DEBUG_FILTER,
282			"<= comp_list_candidates: id=%ld first=%ld last=%ld\n",
283			(long) ids[0],
284			(long) BDB_IDL_FIRST(ids),
285			(long) BDB_IDL_LAST(ids) );
286
287	} else {
288		Debug( LDAP_DEBUG_FILTER,
289			"<= comp_list_candidates: undefined rc=%d\n",
290			rc, 0, 0 );
291	}
292
293	return rc;
294}
295
296static int
297comp_equality_candidates (
298        Operation *op,
299	DB_TXN *rtxn,
300        MatchingRuleAssertion *mra,
301	ComponentAssertion *ca,
302        ID *ids,
303        ID *tmp,
304        ID *stack)
305{
306       struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
307        DB      *db;
308        int i;
309        int rc;
310        slap_mask_t mask;
311        struct berval prefix = {0, NULL};
312        struct berval *keys = NULL;
313        MatchingRule *mr = mra->ma_rule;
314        Syntax *sat_syntax;
315	ComponentReference* cr_list, *cr;
316	AttrInfo *ai;
317
318        BDB_IDL_ALL( bdb, ids );
319
320	if ( !ca->ca_comp_ref )
321		return 0;
322
323	ai = bdb_attr_mask( op->o_bd->be_private, mra->ma_desc );
324	if( ai ) {
325		cr_list = ai->ai_cr;
326	}
327	else {
328		return 0;
329	}
330	/* find a component reference to be indexed */
331	sat_syntax = ca->ca_ma_rule->smr_syntax;
332	for ( cr = cr_list ; cr ; cr = cr->cr_next ) {
333		if ( cr->cr_string.bv_len == ca->ca_comp_ref->cr_string.bv_len &&
334			strncmp( cr->cr_string.bv_val, ca->ca_comp_ref->cr_string.bv_val,cr->cr_string.bv_len ) == 0 )
335			break;
336	}
337
338	if ( !cr )
339		return 0;
340
341        rc = bdb_index_param( op->o_bd, mra->ma_desc, LDAP_FILTER_EQUALITY,
342                &db, &mask, &prefix );
343
344        if( rc != LDAP_SUCCESS ) {
345                return 0;
346        }
347
348        if( !mr ) {
349                return 0;
350        }
351
352        if( !mr->smr_filter ) {
353                return 0;
354        }
355
356	rc = (ca->ca_ma_rule->smr_filter)(
357                LDAP_FILTER_EQUALITY,
358                cr->cr_indexmask,
359                sat_syntax,
360                ca->ca_ma_rule,
361                &prefix,
362                &ca->ca_ma_value,
363                &keys, op->o_tmpmemctx );
364
365        if( rc != LDAP_SUCCESS ) {
366                return 0;
367        }
368
369        if( keys == NULL ) {
370                return 0;
371        }
372        for ( i= 0; keys[i].bv_val != NULL; i++ ) {
373                rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
374
375                if( rc == DB_NOTFOUND ) {
376                        BDB_IDL_ZERO( ids );
377                        rc = 0;
378                        break;
379                } else if( rc != LDAP_SUCCESS ) {
380                        break;
381                }
382
383                if( BDB_IDL_IS_ZERO( tmp ) ) {
384                        BDB_IDL_ZERO( ids );
385                        break;
386                }
387
388                if ( i == 0 ) {
389                        BDB_IDL_CPY( ids, tmp );
390                } else {
391                        bdb_idl_intersection( ids, tmp );
392                }
393
394                if( BDB_IDL_IS_ZERO( ids ) )
395                        break;
396        }
397        ber_bvarray_free_x( keys, op->o_tmpmemctx );
398
399        Debug( LDAP_DEBUG_TRACE,
400                "<= comp_equality_candidates: id=%ld, first=%ld, last=%ld\n",
401                (long) ids[0],
402                (long) BDB_IDL_FIRST(ids),
403                (long) BDB_IDL_LAST(ids) );
404        return( rc );
405}
406
407static int
408ava_comp_candidates (
409	Operation *op,
410	DB_TXN *rtxn,
411	AttributeAssertion *ava,
412	AttributeAliasing *aa,
413	ID *ids,
414	ID *tmp,
415	ID *stack )
416{
417	MatchingRuleAssertion mra;
418
419	mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
420	if ( !mra.ma_rule ) {
421		struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
422		BDB_IDL_ALL( bdb, ids );
423		return 0;
424	}
425	mra.ma_desc = aa->aa_aliased_ad;
426	mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
427
428	return comp_candidates ( op, rtxn, &mra, ava->aa_cf, ids, tmp, stack );
429}
430
431static int
432comp_candidates (
433	Operation *op,
434	DB_TXN *rtxn,
435	MatchingRuleAssertion *mra,
436	ComponentFilter *f,
437	ID *ids,
438	ID *tmp,
439	ID *stack)
440{
441	int	rc;
442
443	if ( !f ) return LDAP_PROTOCOL_ERROR;
444
445	Debug( LDAP_DEBUG_FILTER, "comp_candidates\n", 0, 0, 0 );
446	switch ( f->cf_choice ) {
447	case SLAPD_FILTER_COMPUTED:
448		rc = f->cf_result;
449		break;
450	case LDAP_COMP_FILTER_AND:
451		rc = comp_list_candidates( op, rtxn, mra, f->cf_and, LDAP_COMP_FILTER_AND, ids, tmp, stack );
452		break;
453	case LDAP_COMP_FILTER_OR:
454		rc = comp_list_candidates( op, rtxn, mra, f->cf_or, LDAP_COMP_FILTER_OR, ids, tmp, stack );
455		break;
456	case LDAP_COMP_FILTER_NOT:
457		/* No component indexing supported for NOT filter */
458		Debug( LDAP_DEBUG_FILTER, "\tComponent NOT\n", 0, 0, 0 );
459		{
460			struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
461			BDB_IDL_ALL( bdb, ids );
462		}
463		rc = LDAP_PROTOCOL_ERROR;
464		break;
465	case LDAP_COMP_FILTER_ITEM:
466		rc = comp_equality_candidates( op, rtxn, mra, f->cf_ca, ids, tmp, stack );
467		break;
468	default:
469		{
470			struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
471			BDB_IDL_ALL( bdb, ids );
472		}
473		rc = LDAP_PROTOCOL_ERROR;
474	}
475
476	return( rc );
477}
478#endif
479
480static int
481ext_candidates(
482        Operation *op,
483		DB_TXN *rtxn,
484        MatchingRuleAssertion *mra,
485        ID *ids,
486        ID *tmp,
487        ID *stack)
488{
489	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
490
491#ifdef LDAP_COMP_MATCH
492	/*
493	 * Currently Only Component Indexing for componentFilterMatch is supported
494	 * Indexing for an extensible filter is not supported yet
495	 */
496	if ( mra->ma_cf ) {
497		return comp_candidates ( op, rtxn, mra, mra->ma_cf, ids, tmp, stack);
498	}
499#endif
500	if ( mra->ma_desc == slap_schema.si_ad_entryDN ) {
501		int rc;
502		EntryInfo *ei;
503
504		BDB_IDL_ZERO( ids );
505		if ( mra->ma_rule == slap_schema.si_mr_distinguishedNameMatch ) {
506			ei = NULL;
507			rc = bdb_cache_find_ndn( op, rtxn, &mra->ma_value, &ei );
508			if ( rc == LDAP_SUCCESS )
509				bdb_idl_insert( ids, ei->bei_id );
510			if ( ei )
511				bdb_cache_entryinfo_unlock( ei );
512			return 0;
513		} else if ( mra->ma_rule && mra->ma_rule->smr_match ==
514			dnRelativeMatch && dnIsSuffix( &mra->ma_value,
515				op->o_bd->be_nsuffix )) {
516			int scope;
517			if ( mra->ma_rule == slap_schema.si_mr_dnSuperiorMatch ) {
518				struct berval pdn;
519				ei = NULL;
520				dnParent( &mra->ma_value, &pdn );
521				bdb_cache_find_ndn( op, rtxn, &pdn, &ei );
522				if ( ei ) {
523					bdb_cache_entryinfo_unlock( ei );
524					while ( ei && ei->bei_id ) {
525						bdb_idl_insert( ids, ei->bei_id );
526						ei = ei->bei_parent;
527					}
528				}
529				return 0;
530			}
531			if ( mra->ma_rule == slap_schema.si_mr_dnSubtreeMatch )
532				scope = LDAP_SCOPE_SUBTREE;
533			else if ( mra->ma_rule == slap_schema.si_mr_dnOneLevelMatch )
534				scope = LDAP_SCOPE_ONELEVEL;
535			else if ( mra->ma_rule == slap_schema.si_mr_dnSubordinateMatch )
536				scope = LDAP_SCOPE_SUBORDINATE;
537			else
538				scope = LDAP_SCOPE_BASE;
539			if ( scope > LDAP_SCOPE_BASE ) {
540				ei = NULL;
541				rc = bdb_cache_find_ndn( op, rtxn, &mra->ma_value, &ei );
542				if ( ei )
543					bdb_cache_entryinfo_unlock( ei );
544				if ( rc == LDAP_SUCCESS ) {
545					int sc = op->ors_scope;
546					op->ors_scope = scope;
547					rc = bdb_dn2idl( op, rtxn, &mra->ma_value, ei, ids,
548						stack );
549					op->ors_scope = sc;
550				}
551				return 0;
552			}
553		}
554	}
555
556	BDB_IDL_ALL( bdb, ids );
557	return 0;
558}
559
560static int
561list_candidates(
562	Operation *op,
563	DB_TXN *rtxn,
564	Filter	*flist,
565	int		ftype,
566	ID *ids,
567	ID *tmp,
568	ID *save )
569{
570	int rc = 0;
571	Filter	*f;
572
573	Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 );
574	for ( f = flist; f != NULL; f = f->f_next ) {
575		/* ignore precomputed scopes */
576		if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
577		     f->f_result == LDAP_SUCCESS ) {
578			continue;
579		}
580		BDB_IDL_ZERO( save );
581		rc = bdb_filter_candidates( op, rtxn, f, save, tmp,
582			save+BDB_IDL_UM_SIZE );
583
584		if ( rc != 0 ) {
585			if ( rc == DB_LOCK_DEADLOCK )
586				return rc;
587
588			if ( ftype == LDAP_FILTER_AND ) {
589				rc = 0;
590				continue;
591			}
592			break;
593		}
594
595
596		if ( ftype == LDAP_FILTER_AND ) {
597			if ( f == flist ) {
598				BDB_IDL_CPY( ids, save );
599			} else {
600				bdb_idl_intersection( ids, save );
601			}
602			if( BDB_IDL_IS_ZERO( ids ) )
603				break;
604		} else {
605			if ( f == flist ) {
606				BDB_IDL_CPY( ids, save );
607			} else {
608				bdb_idl_union( ids, save );
609			}
610		}
611	}
612
613	if( rc == LDAP_SUCCESS ) {
614		Debug( LDAP_DEBUG_FILTER,
615			"<= bdb_list_candidates: id=%ld first=%ld last=%ld\n",
616			(long) ids[0],
617			(long) BDB_IDL_FIRST(ids),
618			(long) BDB_IDL_LAST(ids) );
619
620	} else {
621		Debug( LDAP_DEBUG_FILTER,
622			"<= bdb_list_candidates: undefined rc=%d\n",
623			rc, 0, 0 );
624	}
625
626	return rc;
627}
628
629static int
630presence_candidates(
631	Operation *op,
632	DB_TXN *rtxn,
633	AttributeDescription *desc,
634	ID *ids )
635{
636	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
637	DB *db;
638	int rc;
639	slap_mask_t mask;
640	struct berval prefix = {0, NULL};
641
642	Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates (%s)\n",
643			desc->ad_cname.bv_val, 0, 0 );
644
645	BDB_IDL_ALL( bdb, ids );
646
647	if( desc == slap_schema.si_ad_objectClass ) {
648		return 0;
649	}
650
651	rc = bdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
652		&db, &mask, &prefix );
653
654	if( rc == LDAP_INAPPROPRIATE_MATCHING ) {
655		/* not indexed */
656		Debug( LDAP_DEBUG_TRACE,
657			"<= bdb_presence_candidates: (%s) not indexed\n",
658			desc->ad_cname.bv_val, 0, 0 );
659		return 0;
660	}
661
662	if( rc != LDAP_SUCCESS ) {
663		Debug( LDAP_DEBUG_TRACE,
664			"<= bdb_presence_candidates: (%s) index_param "
665			"returned=%d\n",
666			desc->ad_cname.bv_val, rc, 0 );
667		return 0;
668	}
669
670	if( prefix.bv_val == NULL ) {
671		Debug( LDAP_DEBUG_TRACE,
672			"<= bdb_presence_candidates: (%s) no prefix\n",
673			desc->ad_cname.bv_val, 0, 0 );
674		return -1;
675	}
676
677	rc = bdb_key_read( op->o_bd, db, rtxn, &prefix, ids, NULL, 0 );
678
679	if( rc == DB_NOTFOUND ) {
680		BDB_IDL_ZERO( ids );
681		rc = 0;
682	} else if( rc != LDAP_SUCCESS ) {
683		Debug( LDAP_DEBUG_TRACE,
684			"<= bdb_presense_candidates: (%s) "
685			"key read failed (%d)\n",
686			desc->ad_cname.bv_val, rc, 0 );
687		goto done;
688	}
689
690	Debug(LDAP_DEBUG_TRACE,
691		"<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n",
692		(long) ids[0],
693		(long) BDB_IDL_FIRST(ids),
694		(long) BDB_IDL_LAST(ids) );
695
696done:
697	return rc;
698}
699
700static int
701equality_candidates(
702	Operation *op,
703	DB_TXN *rtxn,
704	AttributeAssertion *ava,
705	ID *ids,
706	ID *tmp )
707{
708	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
709	DB	*db;
710	int i;
711	int rc;
712	slap_mask_t mask;
713	struct berval prefix = {0, NULL};
714	struct berval *keys = NULL;
715	MatchingRule *mr;
716
717	Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates (%s)\n",
718			ava->aa_desc->ad_cname.bv_val, 0, 0 );
719
720	if ( ava->aa_desc == slap_schema.si_ad_entryDN ) {
721		EntryInfo *ei = NULL;
722		rc = bdb_cache_find_ndn( op, rtxn, &ava->aa_value, &ei );
723		if ( rc == LDAP_SUCCESS ) {
724			/* exactly one ID can match */
725			ids[0] = 1;
726			ids[1] = ei->bei_id;
727		}
728		if ( ei ) {
729			bdb_cache_entryinfo_unlock( ei );
730		}
731		return rc;
732	}
733
734	BDB_IDL_ALL( bdb, ids );
735
736	rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
737		&db, &mask, &prefix );
738
739	if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
740		Debug( LDAP_DEBUG_ANY,
741			"<= bdb_equality_candidates: (%s) not indexed\n",
742			ava->aa_desc->ad_cname.bv_val, 0, 0 );
743		return 0;
744	}
745
746	if( rc != LDAP_SUCCESS ) {
747		Debug( LDAP_DEBUG_ANY,
748			"<= bdb_equality_candidates: (%s) "
749			"index_param failed (%d)\n",
750			ava->aa_desc->ad_cname.bv_val, rc, 0 );
751		return 0;
752	}
753
754	mr = ava->aa_desc->ad_type->sat_equality;
755	if( !mr ) {
756		return 0;
757	}
758
759	if( !mr->smr_filter ) {
760		return 0;
761	}
762
763	rc = (mr->smr_filter)(
764		LDAP_FILTER_EQUALITY,
765		mask,
766		ava->aa_desc->ad_type->sat_syntax,
767		mr,
768		&prefix,
769		&ava->aa_value,
770		&keys, op->o_tmpmemctx );
771
772	if( rc != LDAP_SUCCESS ) {
773		Debug( LDAP_DEBUG_TRACE,
774			"<= bdb_equality_candidates: (%s, %s) "
775			"MR filter failed (%d)\n",
776			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
777		return 0;
778	}
779
780	if( keys == NULL ) {
781		Debug( LDAP_DEBUG_TRACE,
782			"<= bdb_equality_candidates: (%s) no keys\n",
783			ava->aa_desc->ad_cname.bv_val, 0, 0 );
784		return 0;
785	}
786
787	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
788		rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
789
790		if( rc == DB_NOTFOUND ) {
791			BDB_IDL_ZERO( ids );
792			rc = 0;
793			break;
794		} else if( rc != LDAP_SUCCESS ) {
795			Debug( LDAP_DEBUG_TRACE,
796				"<= bdb_equality_candidates: (%s) "
797				"key read failed (%d)\n",
798				ava->aa_desc->ad_cname.bv_val, rc, 0 );
799			break;
800		}
801
802		if( BDB_IDL_IS_ZERO( tmp ) ) {
803			Debug( LDAP_DEBUG_TRACE,
804				"<= bdb_equality_candidates: (%s) NULL\n",
805				ava->aa_desc->ad_cname.bv_val, 0, 0 );
806			BDB_IDL_ZERO( ids );
807			break;
808		}
809
810		if ( i == 0 ) {
811			BDB_IDL_CPY( ids, tmp );
812		} else {
813			bdb_idl_intersection( ids, tmp );
814		}
815
816		if( BDB_IDL_IS_ZERO( ids ) )
817			break;
818	}
819
820	ber_bvarray_free_x( keys, op->o_tmpmemctx );
821
822	Debug( LDAP_DEBUG_TRACE,
823		"<= bdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
824		(long) ids[0],
825		(long) BDB_IDL_FIRST(ids),
826		(long) BDB_IDL_LAST(ids) );
827	return( rc );
828}
829
830
831static int
832approx_candidates(
833	Operation *op,
834	DB_TXN *rtxn,
835	AttributeAssertion *ava,
836	ID *ids,
837	ID *tmp )
838{
839	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
840	DB	*db;
841	int i;
842	int rc;
843	slap_mask_t mask;
844	struct berval prefix = {0, NULL};
845	struct berval *keys = NULL;
846	MatchingRule *mr;
847
848	Debug( LDAP_DEBUG_TRACE, "=> bdb_approx_candidates (%s)\n",
849			ava->aa_desc->ad_cname.bv_val, 0, 0 );
850
851	BDB_IDL_ALL( bdb, ids );
852
853	rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
854		&db, &mask, &prefix );
855
856	if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
857		Debug( LDAP_DEBUG_ANY,
858			"<= bdb_approx_candidates: (%s) not indexed\n",
859			ava->aa_desc->ad_cname.bv_val, 0, 0 );
860		return 0;
861	}
862
863	if( rc != LDAP_SUCCESS ) {
864		Debug( LDAP_DEBUG_ANY,
865			"<= bdb_approx_candidates: (%s) "
866			"index_param failed (%d)\n",
867			ava->aa_desc->ad_cname.bv_val, rc, 0 );
868		return 0;
869	}
870
871	mr = ava->aa_desc->ad_type->sat_approx;
872	if( !mr ) {
873		/* no approx matching rule, try equality matching rule */
874		mr = ava->aa_desc->ad_type->sat_equality;
875	}
876
877	if( !mr ) {
878		return 0;
879	}
880
881	if( !mr->smr_filter ) {
882		return 0;
883	}
884
885	rc = (mr->smr_filter)(
886		LDAP_FILTER_APPROX,
887		mask,
888		ava->aa_desc->ad_type->sat_syntax,
889		mr,
890		&prefix,
891		&ava->aa_value,
892		&keys, op->o_tmpmemctx );
893
894	if( rc != LDAP_SUCCESS ) {
895		Debug( LDAP_DEBUG_TRACE,
896			"<= bdb_approx_candidates: (%s, %s) "
897			"MR filter failed (%d)\n",
898			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
899		return 0;
900	}
901
902	if( keys == NULL ) {
903		Debug( LDAP_DEBUG_TRACE,
904			"<= bdb_approx_candidates: (%s) no keys (%s)\n",
905			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
906		return 0;
907	}
908
909	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
910		rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
911
912		if( rc == DB_NOTFOUND ) {
913			BDB_IDL_ZERO( ids );
914			rc = 0;
915			break;
916		} else if( rc != LDAP_SUCCESS ) {
917			Debug( LDAP_DEBUG_TRACE,
918				"<= bdb_approx_candidates: (%s) "
919				"key read failed (%d)\n",
920				ava->aa_desc->ad_cname.bv_val, rc, 0 );
921			break;
922		}
923
924		if( BDB_IDL_IS_ZERO( tmp ) ) {
925			Debug( LDAP_DEBUG_TRACE,
926				"<= bdb_approx_candidates: (%s) NULL\n",
927				ava->aa_desc->ad_cname.bv_val, 0, 0 );
928			BDB_IDL_ZERO( ids );
929			break;
930		}
931
932		if ( i == 0 ) {
933			BDB_IDL_CPY( ids, tmp );
934		} else {
935			bdb_idl_intersection( ids, tmp );
936		}
937
938		if( BDB_IDL_IS_ZERO( ids ) )
939			break;
940	}
941
942	ber_bvarray_free_x( keys, op->o_tmpmemctx );
943
944	Debug( LDAP_DEBUG_TRACE, "<= bdb_approx_candidates %ld, first=%ld, last=%ld\n",
945		(long) ids[0],
946		(long) BDB_IDL_FIRST(ids),
947		(long) BDB_IDL_LAST(ids) );
948	return( rc );
949}
950
951static int
952substring_candidates(
953	Operation *op,
954	DB_TXN *rtxn,
955	SubstringsAssertion	*sub,
956	ID *ids,
957	ID *tmp )
958{
959	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
960	DB	*db;
961	int i;
962	int rc;
963	slap_mask_t mask;
964	struct berval prefix = {0, NULL};
965	struct berval *keys = NULL;
966	MatchingRule *mr;
967
968	Debug( LDAP_DEBUG_TRACE, "=> bdb_substring_candidates (%s)\n",
969			sub->sa_desc->ad_cname.bv_val, 0, 0 );
970
971	BDB_IDL_ALL( bdb, ids );
972
973	rc = bdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
974		&db, &mask, &prefix );
975
976	if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
977		Debug( LDAP_DEBUG_ANY,
978			"<= bdb_substring_candidates: (%s) not indexed\n",
979			sub->sa_desc->ad_cname.bv_val, 0, 0 );
980		return 0;
981	}
982
983	if( rc != LDAP_SUCCESS ) {
984		Debug( LDAP_DEBUG_ANY,
985			"<= bdb_substring_candidates: (%s) "
986			"index_param failed (%d)\n",
987			sub->sa_desc->ad_cname.bv_val, rc, 0 );
988		return 0;
989	}
990
991	mr = sub->sa_desc->ad_type->sat_substr;
992
993	if( !mr ) {
994		return 0;
995	}
996
997	if( !mr->smr_filter ) {
998		return 0;
999	}
1000
1001	rc = (mr->smr_filter)(
1002		LDAP_FILTER_SUBSTRINGS,
1003		mask,
1004		sub->sa_desc->ad_type->sat_syntax,
1005		mr,
1006		&prefix,
1007		sub,
1008		&keys, op->o_tmpmemctx );
1009
1010	if( rc != LDAP_SUCCESS ) {
1011		Debug( LDAP_DEBUG_TRACE,
1012			"<= bdb_substring_candidates: (%s) "
1013			"MR filter failed (%d)\n",
1014			sub->sa_desc->ad_cname.bv_val, rc, 0 );
1015		return 0;
1016	}
1017
1018	if( keys == NULL ) {
1019		Debug( LDAP_DEBUG_TRACE,
1020			"<= bdb_substring_candidates: (0x%04lx) no keys (%s)\n",
1021			mask, sub->sa_desc->ad_cname.bv_val, 0 );
1022		return 0;
1023	}
1024
1025	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
1026		rc = bdb_key_read( op->o_bd, db, rtxn, &keys[i], tmp, NULL, 0 );
1027
1028		if( rc == DB_NOTFOUND ) {
1029			BDB_IDL_ZERO( ids );
1030			rc = 0;
1031			break;
1032		} else if( rc != LDAP_SUCCESS ) {
1033			Debug( LDAP_DEBUG_TRACE,
1034				"<= bdb_substring_candidates: (%s) "
1035				"key read failed (%d)\n",
1036				sub->sa_desc->ad_cname.bv_val, rc, 0 );
1037			break;
1038		}
1039
1040		if( BDB_IDL_IS_ZERO( tmp ) ) {
1041			Debug( LDAP_DEBUG_TRACE,
1042				"<= bdb_substring_candidates: (%s) NULL\n",
1043				sub->sa_desc->ad_cname.bv_val, 0, 0 );
1044			BDB_IDL_ZERO( ids );
1045			break;
1046		}
1047
1048		if ( i == 0 ) {
1049			BDB_IDL_CPY( ids, tmp );
1050		} else {
1051			bdb_idl_intersection( ids, tmp );
1052		}
1053
1054		if( BDB_IDL_IS_ZERO( ids ) )
1055			break;
1056	}
1057
1058	ber_bvarray_free_x( keys, op->o_tmpmemctx );
1059
1060	Debug( LDAP_DEBUG_TRACE, "<= bdb_substring_candidates: %ld, first=%ld, last=%ld\n",
1061		(long) ids[0],
1062		(long) BDB_IDL_FIRST(ids),
1063		(long) BDB_IDL_LAST(ids) );
1064	return( rc );
1065}
1066
1067static int
1068inequality_candidates(
1069	Operation *op,
1070	DB_TXN *rtxn,
1071	AttributeAssertion *ava,
1072	ID *ids,
1073	ID *tmp,
1074	int gtorlt )
1075{
1076	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
1077	DB	*db;
1078	int rc;
1079	slap_mask_t mask;
1080	struct berval prefix = {0, NULL};
1081	struct berval *keys = NULL;
1082	MatchingRule *mr;
1083	DBC * cursor = NULL;
1084
1085	Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n",
1086			ava->aa_desc->ad_cname.bv_val, 0, 0 );
1087
1088	BDB_IDL_ALL( bdb, ids );
1089
1090	rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
1091		&db, &mask, &prefix );
1092
1093	if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
1094		Debug( LDAP_DEBUG_ANY,
1095			"<= bdb_inequality_candidates: (%s) not indexed\n",
1096			ava->aa_desc->ad_cname.bv_val, 0, 0 );
1097		return 0;
1098	}
1099
1100	if( rc != LDAP_SUCCESS ) {
1101		Debug( LDAP_DEBUG_ANY,
1102			"<= bdb_inequality_candidates: (%s) "
1103			"index_param failed (%d)\n",
1104			ava->aa_desc->ad_cname.bv_val, rc, 0 );
1105		return 0;
1106	}
1107
1108	mr = ava->aa_desc->ad_type->sat_equality;
1109	if( !mr ) {
1110		return 0;
1111	}
1112
1113	if( !mr->smr_filter ) {
1114		return 0;
1115	}
1116
1117	rc = (mr->smr_filter)(
1118		LDAP_FILTER_EQUALITY,
1119		mask,
1120		ava->aa_desc->ad_type->sat_syntax,
1121		mr,
1122		&prefix,
1123		&ava->aa_value,
1124		&keys, op->o_tmpmemctx );
1125
1126	if( rc != LDAP_SUCCESS ) {
1127		Debug( LDAP_DEBUG_TRACE,
1128			"<= bdb_inequality_candidates: (%s, %s) "
1129			"MR filter failed (%d)\n",
1130			prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
1131		return 0;
1132	}
1133
1134	if( keys == NULL ) {
1135		Debug( LDAP_DEBUG_TRACE,
1136			"<= bdb_inequality_candidates: (%s) no keys\n",
1137			ava->aa_desc->ad_cname.bv_val, 0, 0 );
1138		return 0;
1139	}
1140
1141	BDB_IDL_ZERO( ids );
1142	while(1) {
1143		rc = bdb_key_read( op->o_bd, db, rtxn, &keys[0], tmp, &cursor, gtorlt );
1144
1145		if( rc == DB_NOTFOUND ) {
1146			rc = 0;
1147			break;
1148		} else if( rc != LDAP_SUCCESS ) {
1149			Debug( LDAP_DEBUG_TRACE,
1150			       "<= bdb_inequality_candidates: (%s) "
1151			       "key read failed (%d)\n",
1152			       ava->aa_desc->ad_cname.bv_val, rc, 0 );
1153			break;
1154		}
1155
1156		if( BDB_IDL_IS_ZERO( tmp ) ) {
1157			Debug( LDAP_DEBUG_TRACE,
1158			       "<= bdb_inequality_candidates: (%s) NULL\n",
1159			       ava->aa_desc->ad_cname.bv_val, 0, 0 );
1160			break;
1161		}
1162
1163		bdb_idl_union( ids, tmp );
1164
1165		if( op->ors_limit && op->ors_limit->lms_s_unchecked != -1 &&
1166			BDB_IDL_N( ids ) >= (unsigned) op->ors_limit->lms_s_unchecked ) {
1167			cursor->c_close( cursor );
1168			break;
1169		}
1170	}
1171	ber_bvarray_free_x( keys, op->o_tmpmemctx );
1172
1173	Debug( LDAP_DEBUG_TRACE,
1174		"<= bdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
1175		(long) ids[0],
1176		(long) BDB_IDL_FIRST(ids),
1177		(long) BDB_IDL_LAST(ids) );
1178	return( rc );
1179}
1180