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 rc = index_param( be, desc, LDAP_FILTER_PRESENT,
227 &dbname, &mask, &prefix );
229 if( rc != LDAP_SUCCESS ) {
231 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
232 "presence_candidates: index_param returned %d\n",
235 Debug( LDAP_DEBUG_TRACE,
236 "<= presence_candidates: index_param returned=%d\n",
243 if( dbname == NULL ) {
246 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
247 "presence_candidates: not indexed\n" ));
249 Debug( LDAP_DEBUG_TRACE,
250 "<= presense_candidates: not indexed\n",
257 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
261 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
262 "presence_candidates: db open failed (%s%s)\n",
263 dbname, LDBM_SUFFIX ));
265 Debug( LDAP_DEBUG_ANY,
266 "<= presense_candidates db open failed (%s%s)\n",
267 dbname, LDBM_SUFFIX, 0 );
273 if( prefix.bv_val != NULL ) {
277 rc = key_read( be, db, &prefix, &idl );
279 if( rc != LDAP_SUCCESS ) {
281 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
282 "presence_candidates: key read failed (%d)\n", rc ));
284 Debug( LDAP_DEBUG_TRACE,
285 "<= presense_candidates key read failed (%d)\n",
290 } else if( idl == NULL ) {
292 LDAP_LOG(( "filter", LDAP_LEVEL_DETAIL1,
293 "presence_candidates: NULL\n" ));
295 Debug( LDAP_DEBUG_TRACE,
296 "<= presense_candidates NULL\n",
303 ldbm_cache_close( be, db );
306 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
307 "presence_candidates: return %ld\n",
308 idl ? ID_BLOCK_NIDS(idl) : 0 ));
310 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
311 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
320 AttributeAssertion *ava
329 struct berval prefix = {0};
330 struct berval **keys = NULL;
334 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
335 "equality_candidates: enter\n" ));
337 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
341 idl = idl_allids( be );
343 rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
344 &dbname, &mask, &prefix );
346 if( rc != LDAP_SUCCESS ) {
348 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
349 "equality_candidates: index_param returned %d\n", rc ));
351 Debug( LDAP_DEBUG_TRACE,
352 "<= equality_candidates: index_param returned=%d\n",
359 if( dbname == NULL ) {
362 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
363 "equality_candidates: not indexed\n" ));
365 Debug( LDAP_DEBUG_TRACE,
366 "<= equality_candidates: not indexed\n",
373 mr = ava->aa_desc->ad_type->sat_equality;
378 if( !mr->smr_filter ) {
382 rc = (mr->smr_filter)(
383 LDAP_FILTER_EQUALITY,
385 ava->aa_desc->ad_type->sat_syntax,
391 if( rc != LDAP_SUCCESS ) {
393 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
394 "equality_candidates: (%s%s) MR filter failed (%d\n",
395 dbname, LDBM_SUFFIX, rc ));
397 Debug( LDAP_DEBUG_TRACE,
398 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
399 dbname, LDBM_SUFFIX, rc );
407 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
408 "equality_candidates: no keys (%s%s)\n",
409 dbname, LDBM_SUFFIX ));
411 Debug( LDAP_DEBUG_TRACE,
412 "<= equality_candidates: no keys (%s%s)\n",
413 dbname, LDBM_SUFFIX, 0 );
419 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
423 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
424 "equality_candidates: db open failed (%s%s)\n",
425 dbname, LDBM_SUFFIX ));
427 Debug( LDAP_DEBUG_ANY,
428 "<= equality_candidates db open failed (%s%s)\n",
429 dbname, LDBM_SUFFIX, 0 );
435 for ( i= 0; keys[i] != NULL; i++ ) {
439 rc = key_read( be, db, keys[i], &tmp );
441 if( rc != LDAP_SUCCESS ) {
445 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
446 "equality_candidates: key read failed (%d)\n", rc ));
448 Debug( LDAP_DEBUG_TRACE,
449 "<= equality_candidates key read failed (%d)\n",
460 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
461 "equality_candidates NULL\n" ));
463 Debug( LDAP_DEBUG_TRACE,
464 "<= equality_candidates NULL\n",
472 idl = idl_intersection( be, idl, tmp );
476 if( idl == NULL ) break;
479 ber_bvecfree( keys );
481 ldbm_cache_close( be, db );
485 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
486 "equality_candidates: return %ld\n",
487 idl ? ID_BLOCK_NIDS(idl) : 0 ));
489 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
490 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
499 AttributeAssertion *ava
508 struct berval prefix = {0};
509 struct berval **keys = NULL;
513 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
514 "approx_candidates: enter\n" ));
516 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
520 idl = idl_allids( be );
522 rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
523 &dbname, &mask, &prefix );
525 if( rc != LDAP_SUCCESS ) {
527 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
528 "approx_candidates: index_param returned %d\n", rc ));
530 Debug( LDAP_DEBUG_TRACE,
531 "<= approx_candidates: index_param returned=%d\n",
538 if( dbname == NULL ) {
541 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
542 "approx_candidates: not indexed\n" ));
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", LDAP_LEVEL_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", LDAP_LEVEL_INFO,
592 "approx_candidates: no keys (%s%s)\n",
593 dbname, LDBM_SUFFIX ));
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", LDAP_LEVEL_ERR,
608 "approx_candidates db open failed (%s%s)\n",
609 dbname, LDBM_SUFFIX ));
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] != NULL; i++ ) {
623 rc = key_read( be, db, keys[i], &tmp );
625 if( rc != LDAP_SUCCESS ) {
629 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
630 "approx_candidates: key read failed (%d)\n", rc ));
632 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
643 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
644 "approx_candidates: NULL\n" ));
646 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
654 idl = idl_intersection( be, idl, tmp );
658 if( idl == NULL ) break;
661 ber_bvecfree( keys );
663 ldbm_cache_close( be, db );
666 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
667 "approx_candidates: return %ld\n",
668 idl ? ID_BLOCK_NIDS(idl) : 0 ));
670 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
671 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
684 ID_BLOCK *idl, *tmp, *tmp2;
688 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
689 "list_candidates: 0x%x\n", ftype ));
691 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
696 for ( f = flist; f != NULL; f = f->f_next ) {
697 if ( (tmp = filter_candidates( be, f )) == NULL &&
698 ftype == LDAP_FILTER_AND ) {
700 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
701 "list_candidates: NULL\n" ));
703 Debug( LDAP_DEBUG_TRACE,
704 "<= list_candidates NULL\n", 0, 0, 0 );
714 } else if ( ftype == LDAP_FILTER_AND ) {
715 idl = idl_intersection( be, idl, tmp );
719 idl = idl_union( be, idl, tmp );
726 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
727 "list_candidates: return %ld\n",
728 idl ? ID_BLOCK_NIDS(idl) : 0 ));
730 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
731 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
738 substring_candidates(
740 SubstringsAssertion *sub
749 struct berval prefix = {0};
750 struct berval **keys = NULL;
754 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
755 "substrings_candidates: enter\n" ));
757 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
761 idl = idl_allids( be );
763 rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
764 &dbname, &mask, &prefix );
766 if( rc != LDAP_SUCCESS ) {
768 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
769 "substrings_candidates: index_param returned %d\n", rc ));
771 Debug( LDAP_DEBUG_TRACE,
772 "<= substrings_candidates: index_param returned=%d\n",
779 if( dbname == NULL ) {
782 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
783 "substrings_candidates: not indexed\n" ));
785 Debug( LDAP_DEBUG_ANY,
786 "<= substrings_candidates: not indexed\n",
793 mr = sub->sa_desc->ad_type->sat_substr;
799 if( !mr->smr_filter ) {
803 rc = (mr->smr_filter)(
804 LDAP_FILTER_SUBSTRINGS,
806 sub->sa_desc->ad_type->sat_syntax,
812 if( rc != LDAP_SUCCESS ) {
814 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
815 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
816 dbname, LDBM_SUFFIX, rc ));
818 Debug( LDAP_DEBUG_TRACE,
819 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
820 dbname, LDBM_SUFFIX, rc );
828 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
829 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
830 mask, dbname, LDBM_SUFFIX ));
832 Debug( LDAP_DEBUG_TRACE,
833 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
834 mask, dbname, LDBM_SUFFIX );
840 db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
844 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
845 "substrings_candidates: db open failed (%s%s)\n",
846 dbname, LDBM_SUFFIX ));
848 Debug( LDAP_DEBUG_ANY,
849 "<= substrings_candidates db open failed (%s%s)\n",
850 dbname, LDBM_SUFFIX, 0 );
856 for ( i= 0; keys[i] != NULL; i++ ) {
860 rc = key_read( be, db, keys[i], &tmp );
862 if( rc != LDAP_SUCCESS ) {
866 LDAP_LOG(( "filter", LDAP_LEVEL_ERR,
867 "substrings_candidates: key read failed (%d)\n",
870 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
881 LDAP_LOG(( "filter", LDAP_LEVEL_INFO,
882 "substrings_candidates: NULL\n" ));
884 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
892 idl = idl_intersection( be, idl, tmp );
896 if( idl == NULL ) break;
899 ber_bvecfree( keys );
901 ldbm_cache_close( be, db );
904 LDAP_LOG(( "filter", LDAP_LEVEL_ENTRY,
905 "substrings_candidates: return %ld\n",
906 idl ? ID_BLOCK_NIDS(idl) : 0 ));
908 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
909 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );