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";
51 Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
55 switch ( f->f_choice ) {
56 case SLAPD_FILTER_COMPUTED:
57 switch( f->f_result ) {
58 case SLAPD_COMPARE_UNDEFINED:
59 /* This technically is not the same as FALSE, but it
60 * certainly will produce no matches.
63 case LDAP_COMPARE_FALSE:
66 case LDAP_COMPARE_TRUE:
67 result = idl_allids( op->o_bd );
72 case SLAPD_FILTER_DN_ONE:
73 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
75 /* an error is treated as an empty list */
76 if ( dn2idl( op->o_bd, f->f_dn, DN_ONE_PREFIX, &result ) != 0
83 #ifdef SLAPD_FILTER_DN_CHILDREN
84 case SLAPD_FILTER_DN_CHILDREN:
87 case SLAPD_FILTER_DN_SUBTREE:
88 Debug( LDAP_DEBUG_FILTER,
89 "\tDN %s\n", sub, 0, 0 );
91 /* an error is treated as an empty list */
92 if ( dn2idl( op->o_bd, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
99 case LDAP_FILTER_PRESENT:
100 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
102 result = presence_candidates( op, f->f_desc );
105 case LDAP_FILTER_EQUALITY:
106 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
108 result = equality_candidates( op, f->f_ava );
111 case LDAP_FILTER_APPROX:
112 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
114 result = approx_candidates( op, f->f_ava );
117 case LDAP_FILTER_SUBSTRINGS:
118 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
120 result = substring_candidates( op, f->f_sub );
124 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
126 result = presence_candidates( op, f->f_ava->aa_desc );
130 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
132 result = presence_candidates( op, f->f_ava->aa_desc );
135 case LDAP_FILTER_AND:
136 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
138 result = list_candidates( op, f->f_and, LDAP_FILTER_AND );
142 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
144 result = list_candidates( op, f->f_or, LDAP_FILTER_OR );
147 case LDAP_FILTER_NOT:
148 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
151 * As candidates lists may contain entries which do
152 * not match the assertion, negation of the inner candidate
153 * list could result in matching entries be excluded from
154 * the returned candidate list.
156 result = idl_allids( op->o_bd );
159 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN\n", 0, 0, 0 );
160 /* unknown filters must not return NULL, to allow
161 * extended filter processing to be done later.
163 result = idl_allids( op->o_bd );
167 Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
168 result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
176 AttributeDescription *desc
184 struct berval prefix = {0, NULL};
186 Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
188 idl = idl_allids( op->o_bd );
190 if( desc == slap_schema.si_ad_objectClass ) {
194 rc = index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
195 &dbname, &mask, &prefix );
197 if( rc != LDAP_SUCCESS ) {
198 Debug( LDAP_DEBUG_TRACE,
199 "<= presence_candidates: index_param returned=%d\n",
205 if( dbname == NULL ) {
207 Debug( LDAP_DEBUG_TRACE,
208 "<= presense_candidates: not indexed\n",
214 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
217 Debug( LDAP_DEBUG_ANY,
218 "<= presense_candidates db open failed (%s%s)\n",
219 dbname, LDBM_SUFFIX, 0 );
224 if( prefix.bv_val != NULL ) {
228 rc = key_read( op->o_bd, db, &prefix, &idl );
230 if( rc != LDAP_SUCCESS ) {
231 Debug( LDAP_DEBUG_TRACE,
232 "<= presense_candidates key read failed (%d)\n",
236 } else if( idl == NULL ) {
237 Debug( LDAP_DEBUG_TRACE,
238 "<= presense_candidates NULL\n",
244 ldbm_cache_close( op->o_bd, db );
246 Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
247 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
255 AttributeAssertion *ava
264 struct berval prefix = {0, NULL};
265 struct berval *keys = NULL;
268 Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
271 idl = idl_allids( op->o_bd );
273 rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
274 &dbname, &mask, &prefix );
276 if( rc != LDAP_SUCCESS ) {
277 Debug( LDAP_DEBUG_TRACE,
278 "<= equality_candidates: index_param returned=%d\n",
284 if( dbname == NULL ) {
286 Debug( LDAP_DEBUG_TRACE,
287 "<= equality_candidates: not indexed\n",
293 mr = ava->aa_desc->ad_type->sat_equality;
298 if( !mr->smr_filter ) {
302 rc = (mr->smr_filter)(
303 LDAP_FILTER_EQUALITY,
305 ava->aa_desc->ad_type->sat_syntax,
309 &keys, op->o_tmpmemctx );
311 if( rc != LDAP_SUCCESS ) {
312 Debug( LDAP_DEBUG_TRACE,
313 "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
314 dbname, LDBM_SUFFIX, rc );
320 Debug( LDAP_DEBUG_TRACE,
321 "<= equality_candidates: no keys (%s%s)\n",
322 dbname, LDBM_SUFFIX, 0 );
327 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
330 Debug( LDAP_DEBUG_ANY,
331 "<= equality_candidates db open failed (%s%s)\n",
332 dbname, LDBM_SUFFIX, 0 );
337 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
341 rc = key_read( op->o_bd, db, &keys[i], &tmp );
343 if( rc != LDAP_SUCCESS ) {
346 Debug( LDAP_DEBUG_TRACE,
347 "<= equality_candidates key read failed (%d)\n",
356 Debug( LDAP_DEBUG_TRACE,
357 "<= equality_candidates NULL\n",
364 idl = idl_intersection( op->o_bd, idl, tmp );
368 if( idl == NULL ) break;
371 ber_bvarray_free_x( keys, op->o_tmpmemctx );
373 ldbm_cache_close( op->o_bd, db );
376 Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
377 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
385 AttributeAssertion *ava
394 struct berval prefix = {0, NULL};
395 struct berval *keys = NULL;
398 Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
401 idl = idl_allids( op->o_bd );
403 rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
404 &dbname, &mask, &prefix );
406 if( rc != LDAP_SUCCESS ) {
407 Debug( LDAP_DEBUG_TRACE,
408 "<= approx_candidates: index_param returned=%d\n",
414 if( dbname == NULL ) {
416 Debug( LDAP_DEBUG_ANY,
417 "<= approx_candidates: not indexed\n",
423 mr = ava->aa_desc->ad_type->sat_approx;
425 /* no approx matching rule, try equality matching rule */
426 mr = ava->aa_desc->ad_type->sat_equality;
433 if( !mr->smr_filter ) {
437 rc = (mr->smr_filter)(
440 ava->aa_desc->ad_type->sat_syntax,
444 &keys, op->o_tmpmemctx );
446 if( rc != LDAP_SUCCESS ) {
447 Debug( LDAP_DEBUG_TRACE,
448 "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
449 dbname, LDBM_SUFFIX, rc );
455 Debug( LDAP_DEBUG_TRACE,
456 "<= approx_candidates: no keys (%s%s)\n",
457 dbname, LDBM_SUFFIX, 0 );
462 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
465 Debug( LDAP_DEBUG_ANY,
466 "<= approx_candidates db open failed (%s%s)\n",
467 dbname, LDBM_SUFFIX, 0 );
472 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
476 rc = key_read( op->o_bd, db, &keys[i], &tmp );
478 if( rc != LDAP_SUCCESS ) {
481 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
490 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
497 idl = idl_intersection( op->o_bd, idl, tmp );
501 if( idl == NULL ) break;
504 ber_bvarray_free_x( keys, op->o_tmpmemctx );
506 ldbm_cache_close( op->o_bd, db );
508 Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
509 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
521 ID_BLOCK *idl, *tmp, *tmp2;
524 Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
528 for ( f = flist; f != NULL; f = f->f_next ) {
529 if ( (tmp = filter_candidates( op, f )) == NULL &&
530 ftype == LDAP_FILTER_AND ) {
531 Debug( LDAP_DEBUG_TRACE,
532 "<= list_candidates NULL\n", 0, 0, 0 );
541 } else if ( ftype == LDAP_FILTER_AND ) {
542 idl = idl_intersection( op->o_bd, idl, tmp );
546 idl = idl_union( op->o_bd, idl, tmp );
552 Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
553 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
559 substring_candidates(
561 SubstringsAssertion *sub
570 struct berval prefix = {0, NULL};
571 struct berval *keys = NULL;
574 Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
577 idl = idl_allids( op->o_bd );
579 rc = index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
580 &dbname, &mask, &prefix );
582 if( rc != LDAP_SUCCESS ) {
583 Debug( LDAP_DEBUG_TRACE,
584 "<= substrings_candidates: index_param returned=%d\n",
590 if( dbname == NULL ) {
592 Debug( LDAP_DEBUG_ANY,
593 "<= substrings_candidates: not indexed\n",
599 mr = sub->sa_desc->ad_type->sat_substr;
605 if( !mr->smr_filter ) {
609 rc = (mr->smr_filter)(
610 LDAP_FILTER_SUBSTRINGS,
612 sub->sa_desc->ad_type->sat_syntax,
616 &keys, op->o_tmpmemctx );
618 if( rc != LDAP_SUCCESS ) {
619 Debug( LDAP_DEBUG_TRACE,
620 "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
621 dbname, LDBM_SUFFIX, rc );
627 Debug( LDAP_DEBUG_TRACE,
628 "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
629 mask, dbname, LDBM_SUFFIX );
634 db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
637 Debug( LDAP_DEBUG_ANY,
638 "<= substrings_candidates db open failed (%s%s)\n",
639 dbname, LDBM_SUFFIX, 0 );
644 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
648 rc = key_read( op->o_bd, db, &keys[i], &tmp );
650 if( rc != LDAP_SUCCESS ) {
653 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
662 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
669 idl = idl_intersection( op->o_bd, idl, tmp );
673 if( idl == NULL ) break;
676 ber_bvarray_free_x( keys, op->o_tmpmemctx );
678 ldbm_cache_close( op->o_bd, db );
680 Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
681 idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );