1 /* filterindex.c - generate the list of candidate entries from a filter */
4 * Copyright 1998-2000 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", LDAP_LEVEL_ENTRY, "filter_candidates: enter\n"));
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", LDAP_LEVEL_DETAIL1,
53 "filter_candidates: DN ONE (%s)\n", f->f_dn ));
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", LDAP_LEVEL_DETAIL1,
69 "filter_candidates: DN SUBTREE (%s)\n", f->f_dn ));
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", LDAP_LEVEL_DETAIL1,
85 "filter_candidates: Present (%s)\n", f->f_desc->ad_cname.bv_val ));
87 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
90 result = presence_candidates( be, f->f_desc );
93 case LDAP_FILTER_EQUALITY:
95 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
96 "filter_candidates: EQUALITY (%s),(%s)\n",
97 f->f_ava->aa_desc->ad_cname.bv_val,
98 f->f_ava->aa_value->bv_val ));
100 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
103 result = equality_candidates( be, f->f_ava );
106 case LDAP_FILTER_APPROX:
108 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
109 "filter_candidates: APPROX (%s), (%s)\n",
110 f->f_ava->aa_desc->ad_cname.bv_val,
111 f->f_ava->aa_value->bv_val ));
113 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
116 result = approx_candidates( be, f->f_ava );
119 case LDAP_FILTER_SUBSTRINGS:
121 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
122 "filter_candidates: SUBSTRINGS\n"));
124 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
127 result = substring_candidates( be, f->f_sub );
132 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
133 "filter_candidates: GE\n"));
135 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
138 result = presence_candidates( be, f->f_desc );
143 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
144 "filter_candidates: LE\n" ));
146 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
149 result = presence_candidates( be, f->f_desc );
152 case LDAP_FILTER_AND:
154 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
155 "filter_candidates: AND\n" ));
157 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
160 result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
165 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
166 "filter_candidates: OR\n" ));
168 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
171 result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
174 case LDAP_FILTER_NOT:
176 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
177 "filter_candidates: NOT\n" ));
179 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
183 * As candidates lists may contain entries which do
184 * not match the assertion, negation of the inner candidate
185 * list could result in matching entries be excluded from
186 * the returned candidate list.
188 result = idl_allids( be );
193 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
194 "filter_candidates: return %ld\n",
195 result ? ID_BLOCK_NIDS(result) : 0 ));
197 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
198 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
207 AttributeDescription *desc
215 struct berval *prefix;
218 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
219 "presence_candidates: enter\n" ));
221 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
225 idl = idl_allids( be );
227 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
228 &dbname, &mask, &prefix );
230 if( rc != LDAP_SUCCESS ) {
232 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
233 "presence_candidates: index_param returned %d\n",
236 Debug( LDAP_DEBUG_TRACE,
237 "<= presence_candidates: index_param returned=%d\n",
244 if( dbname == NULL ) {
247 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
248 "presence_candidates: not indexed\n" ));
250 Debug( LDAP_DEBUG_TRACE,
251 "<= presense_candidates: not indexed\n",
255 ber_bvfree( prefix );
259 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
263 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
264 "presence_candidates: db open failed (%s%s)\n",
265 dbname, LDBM_SUFFIX ));
267 Debug( LDAP_DEBUG_ANY,
268 "<= presense_candidates db open failed (%s%s)\n",
269 dbname, LDBM_SUFFIX, 0 );
272 ber_bvfree( prefix );
276 if( prefix != NULL ) {
280 rc = key_read( be, db, prefix, &idl );
282 if( rc != LDAP_SUCCESS ) {
284 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
285 "presence_candidates: key read failed (%d)\n", rc ));
287 Debug( LDAP_DEBUG_TRACE,
288 "<= presense_candidates key read failed (%d)\n",
293 } else if( idl == NULL ) {
295 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
296 "presence_candidates: NULL\n" ));
298 Debug( LDAP_DEBUG_TRACE,
299 "<= presense_candidates NULL\n",
306 ldbm_cache_close( be, db );
307 ber_bvfree( prefix );
310 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
311 "presence_candidates: return %ld\n",
312 idl ? ID_BLOCK_NIDS(idl) : 0 ));
314 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
315 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
324 AttributeAssertion *ava
333 struct berval *prefix;
334 struct berval **keys = NULL;
338 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
339 "equality_candidates: enter\n" ));
341 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
345 idl = idl_allids( be );
347 rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
348 &dbname, &mask, &prefix );
350 if( rc != LDAP_SUCCESS ) {
352 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
353 "equality_candidates: index_param returned %d\n", rc ));
355 Debug( LDAP_DEBUG_TRACE,
356 "<= equality_candidates: index_param returned=%d\n",
363 if( dbname == NULL ) {
366 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
367 "equality_candidates: not indexed\n" ));
369 Debug( LDAP_DEBUG_TRACE,
370 "<= equality_candidates: not indexed\n",
374 ber_bvfree( prefix );
378 mr = ava->aa_desc->ad_type->sat_equality;
380 ber_bvfree( prefix );
384 if( !mr->smr_filter ) {
385 ber_bvfree( prefix );
389 rc = (mr->smr_filter)(
390 LDAP_FILTER_EQUALITY,
392 ava->aa_desc->ad_type->sat_syntax,
398 ber_bvfree( prefix );
400 if( rc != LDAP_SUCCESS ) {
402 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
403 "equality_candidates: (%s%s) MR filter failed (%d\n",
404 dbname, LDBM_SUFFIX, rc ));
406 Debug( LDAP_DEBUG_TRACE,
407 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
408 dbname, LDBM_SUFFIX, rc );
416 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
417 "equality_candidates: no keys (%s%s)\n",
418 dbname, LDBM_SUFFIX ));
420 Debug( LDAP_DEBUG_TRACE,
421 "<= equality_candidates: no keys (%s%s)\n",
422 dbname, LDBM_SUFFIX, 0 );
428 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
432 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
433 "equality_candidates: db open failed (%s%s)\n",
434 dbname, LDBM_SUFFIX ));
436 Debug( LDAP_DEBUG_ANY,
437 "<= equality_candidates db open failed (%s%s)\n",
438 dbname, LDBM_SUFFIX, 0 );
444 for ( i= 0; keys[i] != NULL; i++ ) {
448 rc = key_read( be, db, keys[i], &tmp );
450 if( rc != LDAP_SUCCESS ) {
454 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
455 "equality_candidates: key read failed (%d)\n", rc ));
457 Debug( LDAP_DEBUG_TRACE,
458 "<= equality_candidates key read failed (%d)\n",
469 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
470 "equality_candidates NULL\n" ));
472 Debug( LDAP_DEBUG_TRACE,
473 "<= equality_candidates NULL\n",
481 idl = idl_intersection( be, idl, tmp );
485 if( idl == NULL ) break;
488 ber_bvecfree( keys );
490 ldbm_cache_close( be, db );
494 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
495 "equality_candidates: return %ld\n",
496 idl ? ID_BLOCK_NIDS(idl) : 0 ));
498 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
499 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
508 AttributeAssertion *ava
517 struct berval *prefix;
518 struct berval **keys = NULL;
522 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
523 "approx_candidates: enter\n" ));
525 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
529 idl = idl_allids( be );
531 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
532 &dbname, &mask, &prefix );
534 if( rc != LDAP_SUCCESS ) {
536 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
537 "approx_candidates: index_param returned %d\n", rc ));
539 Debug( LDAP_DEBUG_TRACE,
540 "<= approx_candidates: index_param returned=%d\n",
547 if( dbname == NULL ) {
550 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
551 "approx_candidates: not indexed\n" ));
553 Debug( LDAP_DEBUG_ANY,
554 "<= approx_candidates: not indexed\n",
558 ber_bvfree( prefix );
562 mr = ava->aa_desc->ad_type->sat_approx;
564 /* no approx matching rule, try equality matching rule */
565 mr = ava->aa_desc->ad_type->sat_equality;
569 ber_bvfree( prefix );
573 if( !mr->smr_filter ) {
574 ber_bvfree( prefix );
578 rc = (mr->smr_filter)(
581 ava->aa_desc->ad_type->sat_syntax,
587 ber_bvfree( prefix );
589 if( rc != LDAP_SUCCESS ) {
591 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
592 "approx_candidates: (%s%s) MR filter failed (%d)\n",
593 dbname, LDBM_SUFFIX, rc ));
595 Debug( LDAP_DEBUG_TRACE,
596 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
597 dbname, LDBM_SUFFIX, rc );
605 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
606 "approx_candidates: no keys (%s%s)\n",
607 dbname, LDBM_SUFFIX ));
609 Debug( LDAP_DEBUG_TRACE,
610 "<= approx_candidates: no keys (%s%s)\n",
611 dbname, LDBM_SUFFIX, 0 );
617 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
621 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
622 "approx_candidates db open failed (%s%s)\n",
623 dbname, LDBM_SUFFIX ));
625 Debug( LDAP_DEBUG_ANY,
626 "<= approx_candidates db open failed (%s%s)\n",
627 dbname, LDBM_SUFFIX, 0 );
633 for ( i= 0; keys[i] != NULL; i++ ) {
637 rc = key_read( be, db, keys[i], &tmp );
639 if( rc != LDAP_SUCCESS ) {
643 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
644 "approx_candidates: key read failed (%d)\n", rc ));
646 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
657 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
658 "approx_candidates: NULL\n" ));
660 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
668 idl = idl_intersection( be, idl, tmp );
672 if( idl == NULL ) break;
675 ber_bvecfree( keys );
677 ldbm_cache_close( be, db );
680 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
681 "approx_candidates: return %ld\n",
682 idl ? ID_BLOCK_NIDS(idl) : 0 ));
684 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
685 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
698 ID_BLOCK *idl, *tmp, *tmp2;
702 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
703 "list_candidates: 0x%x\n", ftype ));
705 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
710 for ( f = flist; f != NULL; f = f->f_next ) {
711 if ( (tmp = filter_candidates( be, f )) == NULL &&
712 ftype == LDAP_FILTER_AND ) {
714 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
715 "list_candidates: NULL\n" ));
717 Debug( LDAP_DEBUG_TRACE,
718 "<= list_candidates NULL\n", 0, 0, 0 );
728 } else if ( ftype == LDAP_FILTER_AND ) {
729 idl = idl_intersection( be, idl, tmp );
733 idl = idl_union( be, idl, tmp );
740 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
741 "list_candidates: return %ld\n",
742 idl ? ID_BLOCK_NIDS(idl) : 0 ));
744 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
745 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
752 substring_candidates(
754 SubstringsAssertion *sub
763 struct berval *prefix;
764 struct berval **keys = NULL;
768 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
769 "substrings_candidates: enter\n" ));
771 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
775 idl = idl_allids( be );
777 rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
778 &dbname, &mask, &prefix );
780 if( rc != LDAP_SUCCESS ) {
782 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
783 "substrings_candidates: index_param returned %d\n", rc ));
785 Debug( LDAP_DEBUG_TRACE,
786 "<= substrings_candidates: index_param returned=%d\n",
793 if( dbname == NULL ) {
796 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
797 "substrings_candidates: not indexed\n" ));
799 Debug( LDAP_DEBUG_ANY,
800 "<= substrings_candidates: not indexed\n",
804 ber_bvfree( prefix );
808 mr = sub->sa_desc->ad_type->sat_substr;
811 ber_bvfree( prefix );
815 if( !mr->smr_filter ) {
816 ber_bvfree( prefix );
820 rc = (mr->smr_filter)(
821 LDAP_FILTER_SUBSTRINGS,
823 sub->sa_desc->ad_type->sat_syntax,
829 ber_bvfree( prefix );
831 if( rc != LDAP_SUCCESS ) {
833 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
834 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
835 dbname, LDBM_SUFFIX, rc ));
837 Debug( LDAP_DEBUG_TRACE,
838 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
839 dbname, LDBM_SUFFIX, rc );
847 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
848 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
849 mask, dbname, LDBM_SUFFIX ));
851 Debug( LDAP_DEBUG_TRACE,
852 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
853 mask, dbname, LDBM_SUFFIX );
859 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
863 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
864 "substrings_candidates: db open failed (%s%s)\n",
865 dbname, LDBM_SUFFIX ));
867 Debug( LDAP_DEBUG_ANY,
868 "<= substrings_candidates db open failed (%s%s)\n",
869 dbname, LDBM_SUFFIX, 0 );
875 for ( i= 0; keys[i] != NULL; i++ ) {
879 rc = key_read( be, db, keys[i], &tmp );
881 if( rc != LDAP_SUCCESS ) {
885 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
886 "substrings_candidates: key read failed (%d)\n",
889 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
900 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
901 "substrings_candidates: NULL\n" ));
903 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
911 idl = idl_intersection( be, idl, tmp );
915 if( idl == NULL ) break;
918 ber_bvecfree( keys );
920 ldbm_cache_close( be, db );
923 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
924 "substrings_candidates: return %ld\n",
925 idl ? ID_BLOCK_NIDS(idl) : 0 ));
927 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
928 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );