1 /* filterindex.c - generate the list of candidate entries from a filter */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 1998-2004 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
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>.
21 #include <ac/socket.h>
22 #include <ac/string.h>
25 #include "back-ldbm.h"
27 static ID_BLOCK *presence_candidates(
29 AttributeDescription *desc );
30 static ID_BLOCK *equality_candidates(
31 Operation *op, AttributeAssertion *ava );
32 static ID_BLOCK *approx_candidates(
33 Operation *op, AttributeAssertion *ava );
34 static ID_BLOCK *substring_candidates(
36 SubstringsAssertion *sub );
37 static ID_BLOCK *list_candidates(
48 char *sub = "SUBTREE";
52 LDAP_LOG( FILTER, ENTRY, "filter_candidates: enter\n", 0, 0, 0 );
54 Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
59 switch ( f->f_choice ) {
60 case SLAPD_FILTER_COMPUTED:
61 switch( f->f_result ) {
62 case SLAPD_COMPARE_UNDEFINED:
63 /* This technically is not the same as FALSE, but it
64 * certainly will produce no matches.
67 case LDAP_COMPARE_FALSE:
70 case LDAP_COMPARE_TRUE:
71 result = idl_allids( op->o_bd );
76 case SLAPD_FILTER_DN_ONE:
78 LDAP_LOG( FILTER, DETAIL1,
79 "filter_candidates: DN ONE (%s)\n", f->f_dn, 0, 0 );
81 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
84 /* an error is treated as an empty list */
85 if ( dn2idl( op->o_bd, f->f_dn, DN_ONE_PREFIX, &result ) != 0
92 #ifdef SLAPD_FILTER_DN_CHILDREN
93 case SLAPD_FILTER_DN_CHILDREN:
96 case SLAPD_FILTER_DN_SUBTREE:
98 LDAP_LOG( FILTER, DETAIL1,
99 "filter_candidates: DN %s (%s)\n", sub, f->f_dn, 0 );
101 Debug( LDAP_DEBUG_FILTER,
102 "\tDN %s\n", sub, 0, 0 );
105 /* an error is treated as an empty list */
106 if ( dn2idl( op->o_bd, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
107 && result != NULL ) {
113 case LDAP_FILTER_PRESENT:
115 LDAP_LOG( FILTER, DETAIL1,
116 "filter_candidates: Present (%s)\n",
117 f->f_desc->ad_cname.bv_val, 0, 0 );
119 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
122 result = presence_candidates( op, f->f_desc );
125 case LDAP_FILTER_EQUALITY:
127 LDAP_LOG( FILTER, DETAIL1,
128 "filter_candidates: EQUALITY (%s),(%s)\n",
129 f->f_ava->aa_desc->ad_cname.bv_val,
130 f->f_ava->aa_value.bv_val, 0 );
132 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
135 result = equality_candidates( op, f->f_ava );
138 case LDAP_FILTER_APPROX:
140 LDAP_LOG( FILTER, DETAIL1,
141 "filter_candidates: APPROX (%s), (%s)\n",
142 f->f_ava->aa_desc->ad_cname.bv_val,
143 f->f_ava->aa_value.bv_val, 0 );
145 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
148 result = approx_candidates( op, f->f_ava );
151 case LDAP_FILTER_SUBSTRINGS:
153 LDAP_LOG( FILTER, DETAIL1,
154 "filter_candidates: SUBSTRINGS\n", 0, 0, 0 );
156 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
159 result = substring_candidates( op, f->f_sub );
164 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: GE\n", 0, 0, 0 );
166 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
169 result = presence_candidates( op, f->f_ava->aa_desc );
174 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: LE\n", 0, 0, 0 );
176 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
179 result = presence_candidates( op, f->f_ava->aa_desc );
182 case LDAP_FILTER_AND:
184 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: AND\n", 0, 0, 0 );
186 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
189 result = list_candidates( op, f->f_and, LDAP_FILTER_AND );
194 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: OR\n", 0, 0, 0 );
196 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
199 result = list_candidates( op, f->f_or, LDAP_FILTER_OR );
202 case LDAP_FILTER_NOT:
204 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: NOT\n", 0, 0, 0 );
206 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
210 * As candidates lists may contain entries which do
211 * not match the assertion, negation of the inner candidate
212 * list could result in matching entries be excluded from
213 * the returned candidate list.
215 result = idl_allids( op->o_bd );
219 LDAP_LOG( FILTER, DETAIL1, "filter_candidates: UNKNOWN\n", 0, 0, 0 );
221 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN\n", 0, 0, 0 );
223 /* unknown filters must not return NULL, to allow
224 * extended filter processing to be done later.
226 result = idl_allids( op->o_bd );
231 LDAP_LOG( FILTER, ENTRY,
232 "filter_candidates: return %ld\n",
233 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
235 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
236 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
245 AttributeDescription *desc
253 struct berval prefix = {0, NULL};
256 LDAP_LOG( FILTER, ENTRY, "presence_candidates: enter\n", 0, 0, 0 );
258 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
261 idl = idl_allids( op->o_bd );
263 if( desc == slap_schema.si_ad_objectClass ) {
267 rc = index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
268 &dbname, &mask, &prefix );
270 if( rc != LDAP_SUCCESS ) {
272 LDAP_LOG( FILTER, INFO,
273 "presence_candidates: index_param returned %d\n", rc, 0, 0 );
275 Debug( LDAP_DEBUG_TRACE,
276 "<= presence_candidates: index_param returned=%d\n",
283 if( dbname == NULL ) {
286 LDAP_LOG( FILTER, INFO, "presence_candidates: not indexed\n", 0, 0, 0 );
288 Debug( LDAP_DEBUG_TRACE,
289 "<= presense_candidates: not indexed\n",
296 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
300 LDAP_LOG( FILTER, INFO,
301 "presence_candidates: db open failed (%s%s)\n",
302 dbname, LDBM_SUFFIX, 0 );
304 Debug( LDAP_DEBUG_ANY,
305 "<= presense_candidates db open failed (%s%s)\n",
306 dbname, LDBM_SUFFIX, 0 );
312 if( prefix.bv_val != NULL ) {
316 rc = key_read( op->o_bd, db, &prefix, &idl );
318 if( rc != LDAP_SUCCESS ) {
320 LDAP_LOG( FILTER, ERR,
321 "presence_candidates: key read failed (%d)\n", rc, 0, 0 );
323 Debug( LDAP_DEBUG_TRACE,
324 "<= presense_candidates key read failed (%d)\n",
329 } else if( idl == NULL ) {
331 LDAP_LOG( FILTER, DETAIL1, "presence_candidates: NULL\n", 0, 0, 0 );
333 Debug( LDAP_DEBUG_TRACE,
334 "<= presense_candidates NULL\n",
341 ldbm_cache_close( op->o_bd, db );
344 LDAP_LOG( FILTER, ENTRY,
345 "presence_candidates: return %ld\n",
346 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
348 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
349 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
358 AttributeAssertion *ava
367 struct berval prefix = {0, NULL};
368 struct berval *keys = NULL;
372 LDAP_LOG( FILTER, ENTRY, "equality_candidates: enter\n", 0, 0, 0 );
374 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
378 idl = idl_allids( op->o_bd );
380 rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
381 &dbname, &mask, &prefix );
383 if( rc != LDAP_SUCCESS ) {
385 LDAP_LOG( FILTER, ERR,
386 "equality_candidates: index_param returned %d\n", rc, 0, 0 );
388 Debug( LDAP_DEBUG_TRACE,
389 "<= equality_candidates: index_param returned=%d\n",
396 if( dbname == NULL ) {
399 LDAP_LOG( FILTER, ERR, "equality_candidates: not indexed\n", 0, 0, 0 );
401 Debug( LDAP_DEBUG_TRACE,
402 "<= equality_candidates: not indexed\n",
409 mr = ava->aa_desc->ad_type->sat_equality;
414 if( !mr->smr_filter ) {
418 rc = (mr->smr_filter)(
419 LDAP_FILTER_EQUALITY,
421 ava->aa_desc->ad_type->sat_syntax,
425 &keys, op->o_tmpmemctx );
427 if( rc != LDAP_SUCCESS ) {
429 LDAP_LOG( FILTER, ERR,
430 "equality_candidates: (%s%s) MR filter failed (%d\n",
431 dbname, LDBM_SUFFIX, rc );
433 Debug( LDAP_DEBUG_TRACE,
434 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
435 dbname, LDBM_SUFFIX, rc );
443 LDAP_LOG( FILTER, ERR,
444 "equality_candidates: no keys (%s%s)\n", dbname, LDBM_SUFFIX, 0 );
446 Debug( LDAP_DEBUG_TRACE,
447 "<= equality_candidates: no keys (%s%s)\n",
448 dbname, LDBM_SUFFIX, 0 );
454 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
458 LDAP_LOG( FILTER, ERR, "equality_candidates: db open failed (%s%s)\n",
459 dbname, LDBM_SUFFIX, 0 );
461 Debug( LDAP_DEBUG_ANY,
462 "<= equality_candidates db open failed (%s%s)\n",
463 dbname, LDBM_SUFFIX, 0 );
469 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
473 rc = key_read( op->o_bd, db, &keys[i], &tmp );
475 if( rc != LDAP_SUCCESS ) {
479 LDAP_LOG( FILTER, ERR,
480 "equality_candidates: key read failed (%d)\n", rc, 0, 0 );
482 Debug( LDAP_DEBUG_TRACE,
483 "<= equality_candidates key read failed (%d)\n",
494 LDAP_LOG( FILTER, INFO, "equality_candidates NULL\n", 0, 0, 0 );
496 Debug( LDAP_DEBUG_TRACE,
497 "<= equality_candidates NULL\n",
505 idl = idl_intersection( op->o_bd, idl, tmp );
509 if( idl == NULL ) break;
512 ber_bvarray_free_x( keys, op->o_tmpmemctx );
514 ldbm_cache_close( op->o_bd, db );
518 LDAP_LOG( FILTER, ENTRY,
519 "equality_candidates: return %ld\n",
520 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
522 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
523 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
532 AttributeAssertion *ava
541 struct berval prefix = {0, NULL};
542 struct berval *keys = NULL;
546 LDAP_LOG( FILTER, ENTRY, "approx_candidates: enter\n", 0, 0, 0 );
548 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
552 idl = idl_allids( op->o_bd );
554 rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
555 &dbname, &mask, &prefix );
557 if( rc != LDAP_SUCCESS ) {
559 LDAP_LOG( FILTER, ERR,
560 "approx_candidates: index_param returned %d\n", rc, 0, 0 );
562 Debug( LDAP_DEBUG_TRACE,
563 "<= approx_candidates: index_param returned=%d\n",
570 if( dbname == NULL ) {
573 LDAP_LOG( FILTER, ERR, "approx_candidates: not indexed\n", 0, 0, 0 );
575 Debug( LDAP_DEBUG_ANY,
576 "<= approx_candidates: not indexed\n",
583 mr = ava->aa_desc->ad_type->sat_approx;
585 /* no approx matching rule, try equality matching rule */
586 mr = ava->aa_desc->ad_type->sat_equality;
593 if( !mr->smr_filter ) {
597 rc = (mr->smr_filter)(
600 ava->aa_desc->ad_type->sat_syntax,
604 &keys, op->o_tmpmemctx );
606 if( rc != LDAP_SUCCESS ) {
608 LDAP_LOG( FILTER, ERR,
609 "approx_candidates: (%s%s) MR filter failed (%d)\n",
610 dbname, LDBM_SUFFIX, rc );
612 Debug( LDAP_DEBUG_TRACE,
613 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
614 dbname, LDBM_SUFFIX, rc );
622 LDAP_LOG( FILTER, INFO,
623 "approx_candidates: no keys (%s%s)\n",
624 dbname, LDBM_SUFFIX, 0 );
626 Debug( LDAP_DEBUG_TRACE,
627 "<= approx_candidates: no keys (%s%s)\n",
628 dbname, LDBM_SUFFIX, 0 );
634 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
638 LDAP_LOG( FILTER, ERR,
639 "approx_candidates db open failed (%s%s)\n",
640 dbname, LDBM_SUFFIX, 0 );
642 Debug( LDAP_DEBUG_ANY,
643 "<= approx_candidates db open failed (%s%s)\n",
644 dbname, LDBM_SUFFIX, 0 );
650 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
654 rc = key_read( op->o_bd, db, &keys[i], &tmp );
656 if( rc != LDAP_SUCCESS ) {
660 LDAP_LOG( FILTER, ERR,
661 "approx_candidates: key read failed (%d)\n", rc, 0, 0 );
663 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
674 LDAP_LOG( FILTER, INFO, "approx_candidates: NULL\n", 0, 0, 0 );
676 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
684 idl = idl_intersection( op->o_bd, idl, tmp );
688 if( idl == NULL ) break;
691 ber_bvarray_free_x( keys, op->o_tmpmemctx );
693 ldbm_cache_close( op->o_bd, db );
696 LDAP_LOG( FILTER, ENTRY,
697 "approx_candidates: return %ld\n",
698 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
700 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
701 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
714 ID_BLOCK *idl, *tmp, *tmp2;
718 LDAP_LOG( FILTER, ENTRY, "list_candidates: 0x%x\n", ftype, 0, 0 );
720 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
725 for ( f = flist; f != NULL; f = f->f_next ) {
726 if ( (tmp = filter_candidates( op, f )) == NULL &&
727 ftype == LDAP_FILTER_AND ) {
729 LDAP_LOG( FILTER, INFO, "list_candidates: NULL\n", 0, 0, 0 );
731 Debug( LDAP_DEBUG_TRACE,
732 "<= list_candidates NULL\n", 0, 0, 0 );
742 } else if ( ftype == LDAP_FILTER_AND ) {
743 idl = idl_intersection( op->o_bd, idl, tmp );
747 idl = idl_union( op->o_bd, idl, tmp );
754 LDAP_LOG( FILTER, ENTRY, "list_candidates: return %ld\n",
755 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
757 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
758 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
765 substring_candidates(
767 SubstringsAssertion *sub
776 struct berval prefix = {0, NULL};
777 struct berval *keys = NULL;
781 LDAP_LOG( FILTER, ENTRY, "substrings_candidates: enter\n", 0, 0, 0 );
783 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
787 idl = idl_allids( op->o_bd );
789 rc = index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
790 &dbname, &mask, &prefix );
792 if( rc != LDAP_SUCCESS ) {
794 LDAP_LOG( FILTER, ERR,
795 "substrings_candidates: index_param returned %d\n", rc, 0, 0 );
797 Debug( LDAP_DEBUG_TRACE,
798 "<= substrings_candidates: index_param returned=%d\n",
805 if( dbname == NULL ) {
808 LDAP_LOG( FILTER, ERR, "substrings_candidates: not indexed\n", 0, 0, 0);
810 Debug( LDAP_DEBUG_ANY,
811 "<= substrings_candidates: not indexed\n",
818 mr = sub->sa_desc->ad_type->sat_substr;
824 if( !mr->smr_filter ) {
828 rc = (mr->smr_filter)(
829 LDAP_FILTER_SUBSTRINGS,
831 sub->sa_desc->ad_type->sat_syntax,
835 &keys, op->o_tmpmemctx );
837 if( rc != LDAP_SUCCESS ) {
839 LDAP_LOG( FILTER, ERR,
840 "substrings_candidates: (%s%s) MR filter failed (%d)\n",
841 dbname, LDBM_SUFFIX, rc );
843 Debug( LDAP_DEBUG_TRACE,
844 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
845 dbname, LDBM_SUFFIX, rc );
853 LDAP_LOG( FILTER, ERR,
854 "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
855 mask, dbname, LDBM_SUFFIX );
857 Debug( LDAP_DEBUG_TRACE,
858 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
859 mask, dbname, LDBM_SUFFIX );
865 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
869 LDAP_LOG( FILTER, ERR,
870 "substrings_candidates: db open failed (%s%s)\n",
871 dbname, LDBM_SUFFIX, 0 );
873 Debug( LDAP_DEBUG_ANY,
874 "<= substrings_candidates db open failed (%s%s)\n",
875 dbname, LDBM_SUFFIX, 0 );
881 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
885 rc = key_read( op->o_bd, db, &keys[i], &tmp );
887 if( rc != LDAP_SUCCESS ) {
891 LDAP_LOG( FILTER, ERR,
892 "substrings_candidates: key read failed (%d)\n", rc, 0, 0 );
894 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
905 LDAP_LOG( FILTER, INFO, "substrings_candidates: NULL\n", 0, 0, 0 );
907 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
915 idl = idl_intersection( op->o_bd, idl, tmp );
919 if( idl == NULL ) break;
922 ber_bvarray_free_x( keys, op->o_tmpmemctx );
924 ldbm_cache_close( op->o_bd, db );
927 LDAP_LOG( FILTER, ENTRY,
928 "substrings_candidates: return %ld\n",
929 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
931 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
932 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );