1 /* filterindex.c - generate the list of candidate entries from a filter */
4 * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved.
5 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
12 #include <ac/socket.h>
13 #include <ac/string.h>
16 #include "back-ldbm.h"
18 static ID_BLOCK *presence_candidates(
20 AttributeDescription *desc );
21 static ID_BLOCK *equality_candidates(
22 Backend *be, AttributeAssertion *ava );
23 static ID_BLOCK *approx_candidates(
24 Backend *be, AttributeAssertion *ava );
25 static ID_BLOCK *substring_candidates(
27 SubstringsAssertion *sub );
28 static ID_BLOCK *list_candidates(
42 LDAP_LOG( FILTER, ENTRY, "filter_candidates: enter\n", 0, 0, 0 );
44 Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
49 switch ( f->f_choice ) {
50 case SLAPD_FILTER_DN_ONE:
52 LDAP_LOG( FILTER, DETAIL1,
53 "filter_candidates: DN ONE (%s)\n", f->f_dn, 0, 0 );
55 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
58 /* an error is treated as an empty list */
59 if ( dn2idl( be, f->f_dn, DN_ONE_PREFIX, &result ) != 0
66 case SLAPD_FILTER_DN_SUBTREE:
68 LDAP_LOG( FILTER, DETAIL1,
69 "filter_candidates: DN SUBTREE (%s)\n", f->f_dn, 0, 0 );
71 Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
74 /* an error is treated as an empty list */
75 if ( dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
82 case LDAP_FILTER_PRESENT:
84 LDAP_LOG( FILTER, DETAIL1,
85 "filter_candidates: Present (%s)\n",
86 f->f_desc->ad_cname.bv_val, 0, 0 );
88 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
91 result = presence_candidates( be, f->f_desc );
94 case LDAP_FILTER_EQUALITY:
96 LDAP_LOG( FILTER, DETAIL1,
97 "filter_candidates: EQUALITY (%s),(%s)\n",
98 f->f_ava->aa_desc->ad_cname.bv_val,
99 f->f_ava->aa_value.bv_val, 0 );
101 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
104 result = equality_candidates( be, f->f_ava );
107 case LDAP_FILTER_APPROX:
109 LDAP_LOG( FILTER, DETAIL1,
110 "filter_candidates: APPROX (%s), (%s)\n",
111 f->f_ava->aa_desc->ad_cname.bv_val,
112 f->f_ava->aa_value.bv_val, 0 );
114 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
117 result = approx_candidates( be, f->f_ava );
120 case LDAP_FILTER_SUBSTRINGS:
122 LDAP_LOG( FILTER, DETAIL1,
123 "filter_candidates: SUBSTRINGS\n", 0, 0, 0 );
125 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
128 result = substring_candidates( be, f->f_sub );
133 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: GE\n", 0, 0, 0 );
135 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
138 result = presence_candidates( be, f->f_ava->aa_desc );
143 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: LE\n", 0, 0, 0 );
145 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
148 result = presence_candidates( be, f->f_ava->aa_desc );
151 case LDAP_FILTER_AND:
153 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: AND\n", 0, 0, 0 );
155 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
158 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
163 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: OR\n", 0, 0, 0 );
165 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
168 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
171 case LDAP_FILTER_NOT:
173 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: NOT\n", 0, 0, 0 );
175 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
179 * As candidates lists may contain entries which do
180 * not match the assertion, negation of the inner candidate
181 * list could result in matching entries be excluded from
182 * the returned candidate list.
184 result = idl_allids( be );
188 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: UNKNOWN\n", 0, 0, 0 );
190 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN\n", 0, 0, 0 );
192 /* unknown filters must not return NULL, to allow
193 * extended filter processing to be done later.
195 result = idl_allids( be );
200 LDAP_LOG( FILTER, ENTRY,
201 "filter_candidates: return %ld\n",
202 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
204 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
205 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
214 AttributeDescription *desc
222 struct berval prefix = {0};
225 LDAP_LOG( FILTER, ENTRY, "presence_candidates: enter\n", 0, 0, 0 );
227 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
230 idl = idl_allids( be );
232 if( desc == slap_schema.si_ad_objectClass ) {
236 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
237 &dbname, &mask, &prefix );
239 if( rc != LDAP_SUCCESS ) {
241 LDAP_LOG( FILTER, INFO,
242 "presence_candidates: index_param returned %d\n", rc, 0, 0 );
244 Debug( LDAP_DEBUG_TRACE,
245 "<= presence_candidates: index_param returned=%d\n",
252 if( dbname == NULL ) {
255 LDAP_LOG( FILTER, INFO, "presence_candidates: not indexed\n", 0, 0, 0 );
257 Debug( LDAP_DEBUG_TRACE,
258 "<= presense_candidates: not indexed\n",
265 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
269 LDAP_LOG( FILTER, INFO,
270 "presence_candidates: db open failed (%s%s)\n",
271 dbname, LDBM_SUFFIX, 0 );
273 Debug( LDAP_DEBUG_ANY,
274 "<= presense_candidates db open failed (%s%s)\n",
275 dbname, LDBM_SUFFIX, 0 );
281 if( prefix.bv_val != NULL ) {
285 rc = key_read( be, db, &prefix, &idl );
287 if( rc != LDAP_SUCCESS ) {
289 LDAP_LOG( FILTER, ERR,
290 "presence_candidates: key read failed (%d)\n", rc, 0, 0 );
292 Debug( LDAP_DEBUG_TRACE,
293 "<= presense_candidates key read failed (%d)\n",
298 } else if( idl == NULL ) {
300 LDAP_LOG( FILTER, DETAIL1, "presence_candidates: NULL\n", 0, 0, 0 );
302 Debug( LDAP_DEBUG_TRACE,
303 "<= presense_candidates NULL\n",
310 ldbm_cache_close( be, db );
313 LDAP_LOG( FILTER, ENTRY,
314 "presence_candidates: return %ld\n",
315 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
317 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
318 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
327 AttributeAssertion *ava
336 struct berval prefix = {0};
337 struct berval *keys = NULL;
341 LDAP_LOG( FILTER, ENTRY, "equality_candidates: enter\n", 0, 0, 0 );
343 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
347 idl = idl_allids( be );
349 rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
350 &dbname, &mask, &prefix );
352 if( rc != LDAP_SUCCESS ) {
354 LDAP_LOG( FILTER, ERR,
355 "equality_candidates: index_param returned %d\n", rc, 0, 0 );
357 Debug( LDAP_DEBUG_TRACE,
358 "<= equality_candidates: index_param returned=%d\n",
365 if( dbname == NULL ) {
368 LDAP_LOG( FILTER, ERR, "equality_candidates: not indexed\n", 0, 0, 0 );
370 Debug( LDAP_DEBUG_TRACE,
371 "<= equality_candidates: not indexed\n",
378 mr = ava->aa_desc->ad_type->sat_equality;
383 if( !mr->smr_filter ) {
387 rc = (mr->smr_filter)(
388 LDAP_FILTER_EQUALITY,
390 ava->aa_desc->ad_type->sat_syntax,
396 if( rc != LDAP_SUCCESS ) {
398 LDAP_LOG( FILTER, ERR,
399 "equality_candidates: (%s%s) MR filter failed (%d\n",
400 dbname, LDBM_SUFFIX, rc );
402 Debug( LDAP_DEBUG_TRACE,
403 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
404 dbname, LDBM_SUFFIX, rc );
412 LDAP_LOG( FILTER, ERR,
413 "equality_candidates: no keys (%s%s)\n", dbname, LDBM_SUFFIX, 0 );
415 Debug( LDAP_DEBUG_TRACE,
416 "<= equality_candidates: no keys (%s%s)\n",
417 dbname, LDBM_SUFFIX, 0 );
423 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
427 LDAP_LOG( FILTER, ERR, "equality_candidates: db open failed (%s%s)\n",
428 dbname, LDBM_SUFFIX, 0 );
430 Debug( LDAP_DEBUG_ANY,
431 "<= equality_candidates db open failed (%s%s)\n",
432 dbname, LDBM_SUFFIX, 0 );
438 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
442 rc = key_read( be, db, &keys[i], &tmp );
444 if( rc != LDAP_SUCCESS ) {
448 LDAP_LOG( FILTER, ERR,
449 "equality_candidates: key read failed (%d)\n", rc, 0, 0 );
451 Debug( LDAP_DEBUG_TRACE,
452 "<= equality_candidates key read failed (%d)\n",
463 LDAP_LOG( FILTER, INFO, "equality_candidates NULL\n", 0, 0, 0 );
465 Debug( LDAP_DEBUG_TRACE,
466 "<= equality_candidates NULL\n",
474 idl = idl_intersection( be, idl, tmp );
478 if( idl == NULL ) break;
481 ber_bvarray_free( keys );
483 ldbm_cache_close( be, db );
487 LDAP_LOG( FILTER, ENTRY,
488 "equality_candidates: return %ld\n",
489 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
491 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
492 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
501 AttributeAssertion *ava
510 struct berval prefix = {0};
511 struct berval *keys = NULL;
515 LDAP_LOG( FILTER, ENTRY, "approx_candidates: enter\n", 0, 0, 0 );
517 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
521 idl = idl_allids( be );
523 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
524 &dbname, &mask, &prefix );
526 if( rc != LDAP_SUCCESS ) {
528 LDAP_LOG( FILTER, ERR,
529 "approx_candidates: index_param returned %d\n", rc, 0, 0 );
531 Debug( LDAP_DEBUG_TRACE,
532 "<= approx_candidates: index_param returned=%d\n",
539 if( dbname == NULL ) {
542 LDAP_LOG( FILTER, ERR, "approx_candidates: not indexed\n", 0, 0, 0 );
544 Debug( LDAP_DEBUG_ANY,
545 "<= approx_candidates: not indexed\n",
552 mr = ava->aa_desc->ad_type->sat_approx;
554 /* no approx matching rule, try equality matching rule */
555 mr = ava->aa_desc->ad_type->sat_equality;
562 if( !mr->smr_filter ) {
566 rc = (mr->smr_filter)(
569 ava->aa_desc->ad_type->sat_syntax,
575 if( rc != LDAP_SUCCESS ) {
577 LDAP_LOG( FILTER, ERR,
578 "approx_candidates: (%s%s) MR filter failed (%d)\n",
579 dbname, LDBM_SUFFIX, rc );
581 Debug( LDAP_DEBUG_TRACE,
582 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
583 dbname, LDBM_SUFFIX, rc );
591 LDAP_LOG( FILTER, INFO,
592 "approx_candidates: no keys (%s%s)\n",
593 dbname, LDBM_SUFFIX, 0 );
595 Debug( LDAP_DEBUG_TRACE,
596 "<= approx_candidates: no keys (%s%s)\n",
597 dbname, LDBM_SUFFIX, 0 );
603 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
607 LDAP_LOG( FILTER, ERR,
608 "approx_candidates db open failed (%s%s)\n",
609 dbname, LDBM_SUFFIX, 0 );
611 Debug( LDAP_DEBUG_ANY,
612 "<= approx_candidates db open failed (%s%s)\n",
613 dbname, LDBM_SUFFIX, 0 );
619 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
623 rc = key_read( be, db, &keys[i], &tmp );
625 if( rc != LDAP_SUCCESS ) {
629 LDAP_LOG( FILTER, ERR,
630 "approx_candidates: key read failed (%d)\n", rc, 0, 0 );
632 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
643 LDAP_LOG( FILTER, INFO, "approx_candidates: NULL\n", 0, 0, 0 );
645 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
653 idl = idl_intersection( be, idl, tmp );
657 if( idl == NULL ) break;
660 ber_bvarray_free( keys );
662 ldbm_cache_close( be, db );
665 LDAP_LOG( FILTER, ENTRY,
666 "approx_candidates: return %ld\n",
667 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
669 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
670 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
683 ID_BLOCK *idl, *tmp, *tmp2;
687 LDAP_LOG( FILTER, ENTRY, "list_candidates: 0x%x\n", ftype, 0, 0 );
689 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
694 for ( f = flist; f != NULL; f = f->f_next ) {
695 if ( (tmp = filter_candidates( be, f )) == NULL &&
696 ftype == LDAP_FILTER_AND ) {
698 LDAP_LOG( FILTER, INFO, "list_candidates: NULL\n", 0, 0, 0 );
700 Debug( LDAP_DEBUG_TRACE,
701 "<= list_candidates NULL\n", 0, 0, 0 );
711 } else if ( ftype == LDAP_FILTER_AND ) {
712 idl = idl_intersection( be, idl, tmp );
716 idl = idl_union( be, idl, tmp );
723 LDAP_LOG( FILTER, ENTRY, "list_candidates: return %ld\n",
724 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
726 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
727 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
734 substring_candidates(
736 SubstringsAssertion *sub
745 struct berval prefix = {0};
746 struct berval *keys = NULL;
750 LDAP_LOG( FILTER, ENTRY, "substrings_candidates: enter\n", 0, 0, 0 );
752 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
756 idl = idl_allids( be );
758 rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
759 &dbname, &mask, &prefix );
761 if( rc != LDAP_SUCCESS ) {
763 LDAP_LOG( FILTER, ERR,
764 "substrings_candidates: index_param returned %d\n", rc, 0, 0 );
766 Debug( LDAP_DEBUG_TRACE,
767 "<= substrings_candidates: index_param returned=%d\n",
774 if( dbname == NULL ) {
777 LDAP_LOG( FILTER, ERR, "substrings_candidates: not indexed\n", 0, 0, 0);
779 Debug( LDAP_DEBUG_ANY,
780 "<= substrings_candidates: not indexed\n",
787 mr = sub->sa_desc->ad_type->sat_substr;
793 if( !mr->smr_filter ) {
797 rc = (mr->smr_filter)(
798 LDAP_FILTER_SUBSTRINGS,
800 sub->sa_desc->ad_type->sat_syntax,
806 if( rc != LDAP_SUCCESS ) {
808 LDAP_LOG( FILTER, ERR,
809 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
810 dbname, LDBM_SUFFIX, rc );
812 Debug( LDAP_DEBUG_TRACE,
813 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
814 dbname, LDBM_SUFFIX, rc );
822 LDAP_LOG( FILTER, ERR,
823 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
824 mask, dbname, LDBM_SUFFIX );
826 Debug( LDAP_DEBUG_TRACE,
827 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
828 mask, dbname, LDBM_SUFFIX );
834 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
838 LDAP_LOG( FILTER, ERR,
839 "substrings_candidates: db open failed (%s%s)\n",
840 dbname, LDBM_SUFFIX, 0 );
842 Debug( LDAP_DEBUG_ANY,
843 "<= substrings_candidates db open failed (%s%s)\n",
844 dbname, LDBM_SUFFIX, 0 );
850 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
854 rc = key_read( be, db, &keys[i], &tmp );
856 if( rc != LDAP_SUCCESS ) {
860 LDAP_LOG( FILTER, ERR,
861 "substrings_candidates: key read failed (%d)\n", rc, 0, 0 );
863 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
874 LDAP_LOG( FILTER, INFO, "substrings_candidates: NULL\n", 0, 0, 0 );
876 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
884 idl = idl_intersection( be, idl, tmp );
888 if( idl == NULL ) break;
891 ber_bvarray_free( keys );
893 ldbm_cache_close( be, db );
896 LDAP_LOG( FILTER, ENTRY,
897 "substrings_candidates: return %ld\n",
898 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
900 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
901 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );