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 = {0};
218 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
219 "presence_candidates: enter\n" ));
221 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
224 idl = idl_allids( be );
226 if( desc == slap_schema.si_ad_objectClass ) {
230 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
231 &dbname, &mask, &prefix );
233 if( rc != LDAP_SUCCESS ) {
235 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
236 "presence_candidates: index_param returned %d\n",
239 Debug( LDAP_DEBUG_TRACE,
240 "<= presence_candidates: index_param returned=%d\n",
247 if( dbname == NULL ) {
250 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
251 "presence_candidates: not indexed\n" ));
253 Debug( LDAP_DEBUG_TRACE,
254 "<= presense_candidates: not indexed\n",
261 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
265 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
266 "presence_candidates: db open failed (%s%s)\n",
267 dbname, LDBM_SUFFIX ));
269 Debug( LDAP_DEBUG_ANY,
270 "<= presense_candidates db open failed (%s%s)\n",
271 dbname, LDBM_SUFFIX, 0 );
277 if( prefix.bv_val != NULL ) {
281 rc = key_read( be, db, &prefix, &idl );
283 if( rc != LDAP_SUCCESS ) {
285 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
286 "presence_candidates: key read failed (%d)\n", rc ));
288 Debug( LDAP_DEBUG_TRACE,
289 "<= presense_candidates key read failed (%d)\n",
294 } else if( idl == NULL ) {
296 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
297 "presence_candidates: NULL\n" ));
299 Debug( LDAP_DEBUG_TRACE,
300 "<= presense_candidates NULL\n",
307 ldbm_cache_close( be, db );
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 = {0};
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",
377 mr = ava->aa_desc->ad_type->sat_equality;
382 if( !mr->smr_filter ) {
386 rc = (mr->smr_filter)(
387 LDAP_FILTER_EQUALITY,
389 ava->aa_desc->ad_type->sat_syntax,
395 if( rc != LDAP_SUCCESS ) {
397 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
398 "equality_candidates: (%s%s) MR filter failed (%d\n",
399 dbname, LDBM_SUFFIX, rc ));
401 Debug( LDAP_DEBUG_TRACE,
402 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
403 dbname, LDBM_SUFFIX, rc );
411 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
412 "equality_candidates: no keys (%s%s)\n",
413 dbname, LDBM_SUFFIX ));
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", LDAP_LEVEL_ERR,
428 "equality_candidates: db open failed (%s%s)\n",
429 dbname, LDBM_SUFFIX ));
431 Debug( LDAP_DEBUG_ANY,
432 "<= equality_candidates db open failed (%s%s)\n",
433 dbname, LDBM_SUFFIX, 0 );
439 for ( i= 0; keys[i] != NULL; i++ ) {
443 rc = key_read( be, db, keys[i], &tmp );
445 if( rc != LDAP_SUCCESS ) {
449 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
450 "equality_candidates: key read failed (%d)\n", rc ));
452 Debug( LDAP_DEBUG_TRACE,
453 "<= equality_candidates key read failed (%d)\n",
464 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
465 "equality_candidates NULL\n" ));
467 Debug( LDAP_DEBUG_TRACE,
468 "<= equality_candidates NULL\n",
476 idl = idl_intersection( be, idl, tmp );
480 if( idl == NULL ) break;
483 ber_bvecfree( keys );
485 ldbm_cache_close( be, db );
489 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
490 "equality_candidates: return %ld\n",
491 idl ? ID_BLOCK_NIDS(idl) : 0 ));
493 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
494 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
503 AttributeAssertion *ava
512 struct berval prefix = {0};
513 struct berval **keys = NULL;
517 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
518 "approx_candidates: enter\n" ));
520 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
524 idl = idl_allids( be );
526 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
527 &dbname, &mask, &prefix );
529 if( rc != LDAP_SUCCESS ) {
531 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
532 "approx_candidates: index_param returned %d\n", rc ));
534 Debug( LDAP_DEBUG_TRACE,
535 "<= approx_candidates: index_param returned=%d\n",
542 if( dbname == NULL ) {
545 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
546 "approx_candidates: not indexed\n" ));
548 Debug( LDAP_DEBUG_ANY,
549 "<= approx_candidates: not indexed\n",
556 mr = ava->aa_desc->ad_type->sat_approx;
558 /* no approx matching rule, try equality matching rule */
559 mr = ava->aa_desc->ad_type->sat_equality;
566 if( !mr->smr_filter ) {
570 rc = (mr->smr_filter)(
573 ava->aa_desc->ad_type->sat_syntax,
579 if( rc != LDAP_SUCCESS ) {
581 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
582 "approx_candidates: (%s%s) MR filter failed (%d)\n",
583 dbname, LDBM_SUFFIX, rc ));
585 Debug( LDAP_DEBUG_TRACE,
586 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
587 dbname, LDBM_SUFFIX, rc );
595 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
596 "approx_candidates: no keys (%s%s)\n",
597 dbname, LDBM_SUFFIX ));
599 Debug( LDAP_DEBUG_TRACE,
600 "<= approx_candidates: no keys (%s%s)\n",
601 dbname, LDBM_SUFFIX, 0 );
607 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
611 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
612 "approx_candidates db open failed (%s%s)\n",
613 dbname, LDBM_SUFFIX ));
615 Debug( LDAP_DEBUG_ANY,
616 "<= approx_candidates db open failed (%s%s)\n",
617 dbname, LDBM_SUFFIX, 0 );
623 for ( i= 0; keys[i] != NULL; i++ ) {
627 rc = key_read( be, db, keys[i], &tmp );
629 if( rc != LDAP_SUCCESS ) {
633 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
634 "approx_candidates: key read failed (%d)\n", rc ));
636 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
647 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
648 "approx_candidates: NULL\n" ));
650 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
658 idl = idl_intersection( be, idl, tmp );
662 if( idl == NULL ) break;
665 ber_bvecfree( keys );
667 ldbm_cache_close( be, db );
670 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
671 "approx_candidates: return %ld\n",
672 idl ? ID_BLOCK_NIDS(idl) : 0 ));
674 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
675 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
688 ID_BLOCK *idl, *tmp, *tmp2;
692 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
693 "list_candidates: 0x%x\n", ftype ));
695 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
700 for ( f = flist; f != NULL; f = f->f_next ) {
701 if ( (tmp = filter_candidates( be, f )) == NULL &&
702 ftype == LDAP_FILTER_AND ) {
704 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
705 "list_candidates: NULL\n" ));
707 Debug( LDAP_DEBUG_TRACE,
708 "<= list_candidates NULL\n", 0, 0, 0 );
718 } else if ( ftype == LDAP_FILTER_AND ) {
719 idl = idl_intersection( be, idl, tmp );
723 idl = idl_union( be, idl, tmp );
730 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
731 "list_candidates: return %ld\n",
732 idl ? ID_BLOCK_NIDS(idl) : 0 ));
734 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
735 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
742 substring_candidates(
744 SubstringsAssertion *sub
753 struct berval prefix = {0};
754 struct berval **keys = NULL;
758 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
759 "substrings_candidates: enter\n" ));
761 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
765 idl = idl_allids( be );
767 rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
768 &dbname, &mask, &prefix );
770 if( rc != LDAP_SUCCESS ) {
772 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
773 "substrings_candidates: index_param returned %d\n", rc ));
775 Debug( LDAP_DEBUG_TRACE,
776 "<= substrings_candidates: index_param returned=%d\n",
783 if( dbname == NULL ) {
786 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
787 "substrings_candidates: not indexed\n" ));
789 Debug( LDAP_DEBUG_ANY,
790 "<= substrings_candidates: not indexed\n",
797 mr = sub->sa_desc->ad_type->sat_substr;
803 if( !mr->smr_filter ) {
807 rc = (mr->smr_filter)(
808 LDAP_FILTER_SUBSTRINGS,
810 sub->sa_desc->ad_type->sat_syntax,
816 if( rc != LDAP_SUCCESS ) {
818 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
819 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
820 dbname, LDBM_SUFFIX, rc ));
822 Debug( LDAP_DEBUG_TRACE,
823 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
824 dbname, LDBM_SUFFIX, rc );
832 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
833 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
834 mask, dbname, LDBM_SUFFIX ));
836 Debug( LDAP_DEBUG_TRACE,
837 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
838 mask, dbname, LDBM_SUFFIX );
844 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
848 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
849 "substrings_candidates: db open failed (%s%s)\n",
850 dbname, LDBM_SUFFIX ));
852 Debug( LDAP_DEBUG_ANY,
853 "<= substrings_candidates db open failed (%s%s)\n",
854 dbname, LDBM_SUFFIX, 0 );
860 for ( i= 0; keys[i] != NULL; i++ ) {
864 rc = key_read( be, db, keys[i], &tmp );
866 if( rc != LDAP_SUCCESS ) {
870 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
871 "substrings_candidates: key read failed (%d)\n",
874 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
885 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
886 "substrings_candidates: NULL\n" ));
888 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
896 idl = idl_intersection( be, idl, tmp );
900 if( idl == NULL ) break;
903 ber_bvecfree( keys );
905 ldbm_cache_close( be, db );
908 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
909 "substrings_candidates: return %ld\n",
910 idl ? ID_BLOCK_NIDS(idl) : 0 ));
912 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
913 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );