git.sur5r.net Git - openldap/blob - servers/slapd/back-mdb/filterindex.c

   1 /* filterindex.c - generate the list of candidate entries from a filter */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2015 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  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>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20 #include <ac/string.h>
  21
  22 #include "back-mdb.h"
  23 #include "idl.h"
  24 #ifdef LDAP_COMP_MATCH
  25 #include <component.h>
  26 #endif
  27
  28 static int presence_candidates(
  29         Operation *op,
  30         MDB_txn *rtxn,
  31         AttributeDescription *desc,
  32         ID *ids );
  33
  34 static int equality_candidates(
  35         Operation *op,
  36         MDB_txn *rtxn,
  37         AttributeAssertion *ava,
  38         ID *ids,
  39         ID *tmp );
  40 static int inequality_candidates(
  41         Operation *op,
  42         MDB_txn *rtxn,
  43         AttributeAssertion *ava,
  44         ID *ids,
  45         ID *tmp,
  46         int gtorlt );
  47 static int approx_candidates(
  48         Operation *op,
  49         MDB_txn *rtxn,
  50         AttributeAssertion *ava,
  51         ID *ids,
  52         ID *tmp );
  53 static int substring_candidates(
  54         Operation *op,
  55         MDB_txn *rtxn,
  56         SubstringsAssertion *sub,
  57         ID *ids,
  58         ID *tmp );
  59
  60 static int list_candidates(
  61         Operation *op,
  62         MDB_txn *rtxn,
  63         Filter *flist,
  64         int ftype,
  65         ID *ids,
  66         ID *tmp,
  67         ID *stack );
  68
  69 static int
  70 ext_candidates(
  71         Operation *op,
  72                 MDB_txn *rtxn,
  73         MatchingRuleAssertion *mra,
  74         ID *ids,
  75         ID *tmp,
  76         ID *stack);
  77
  78 #ifdef LDAP_COMP_MATCH
  79 static int
  80 comp_candidates (
  81         Operation *op,
  82         MDB_txn *rtxn,
  83         MatchingRuleAssertion *mra,
  84         ComponentFilter *f,
  85         ID *ids,
  86         ID *tmp,
  87         ID *stack);
  88
  89 static int
  90 ava_comp_candidates (
  91                 Operation *op,
  92                 MDB_txn *rtxn,
  93                 AttributeAssertion *ava,
  94                 AttributeAliasing *aa,
  95                 ID *ids,
  96                 ID *tmp,
  97                 ID *stack);
  98 #endif
  99
 100 int
 101 mdb_filter_candidates(
 102         Operation *op,
 103         MDB_txn *rtxn,
 104         Filter  *f,
 105         ID *ids,
 106         ID *tmp,
 107         ID *stack )
 108 {
 109         int rc = 0;
 110 #ifdef LDAP_COMP_MATCH
 111         AttributeAliasing *aa;
 112 #endif
 113         Debug( LDAP_DEBUG_FILTER, "=> mdb_filter_candidates\n", 0, 0, 0 );
 114
 115         if ( f->f_choice & SLAPD_FILTER_UNDEFINED ) {
 116                 MDB_IDL_ZERO( ids );
 117                 goto out;
 118         }
 119
 120         switch ( f->f_choice ) {
 121         case SLAPD_FILTER_COMPUTED:
 122                 switch( f->f_result ) {
 123                 case SLAPD_COMPARE_UNDEFINED:
 124                 /* This technically is not the same as FALSE, but it
 125                  * certainly will produce no matches.
 126                  */
 127                 /* FALL THRU */
 128                 case LDAP_COMPARE_FALSE:
 129                         MDB_IDL_ZERO( ids );
 130                         break;
 131                 case LDAP_COMPARE_TRUE:
 132                         MDB_IDL_ALL( ids );
 133                         break;
 134                 case LDAP_SUCCESS:
 135                         /* this is a pre-computed scope, leave it alone */
 136                         break;
 137                 }
 138                 break;
 139         case LDAP_FILTER_PRESENT:
 140                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
 141                 rc = presence_candidates( op, rtxn, f->f_desc, ids );
 142                 break;
 143
 144         case LDAP_FILTER_EQUALITY:
 145                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
 146 #ifdef LDAP_COMP_MATCH
 147                 if ( is_aliased_attribute && ( aa = is_aliased_attribute ( f->f_ava->aa_desc ) ) ) {
 148                         rc = ava_comp_candidates ( op, rtxn, f->f_ava, aa, ids, tmp, stack );
 149                 }
 150                 else
 151 #endif
 152                 {
 153                         rc = equality_candidates( op, rtxn, f->f_ava, ids, tmp );
 154                 }
 155                 break;
 156
 157         case LDAP_FILTER_APPROX:
 158                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
 159                 rc = approx_candidates( op, rtxn, f->f_ava, ids, tmp );
 160                 break;
 161
 162         case LDAP_FILTER_SUBSTRINGS:
 163                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
 164                 rc = substring_candidates( op, rtxn, f->f_sub, ids, tmp );
 165                 break;
 166
 167         case LDAP_FILTER_GE:
 168                 /* if no GE index, use pres */
 169                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
 170                 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
 171                         ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
 172                         rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_GE );
 173                 else
 174                         rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
 175                 break;
 176
 177         case LDAP_FILTER_LE:
 178                 /* if no LE index, use pres */
 179                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
 180                 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
 181                         ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
 182                         rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_LE );
 183                 else
 184                         rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
 185                 break;
 186
 187         case LDAP_FILTER_NOT:
 188                 /* no indexing to support NOT filters */
 189                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 190                 MDB_IDL_ALL( ids );
 191                 break;
 192
 193         case LDAP_FILTER_AND:
 194                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 195                 rc = list_candidates( op, rtxn,
 196                         f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
 197                 break;
 198
 199         case LDAP_FILTER_OR:
 200                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 201                 rc = list_candidates( op, rtxn,
 202                         f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
 203                 break;
 204         case LDAP_FILTER_EXT:
 205                 Debug( LDAP_DEBUG_FILTER, "\tEXT\n", 0, 0, 0 );
 206                 rc = ext_candidates( op, rtxn, f->f_mra, ids, tmp, stack );
 207                 break;
 208         default:
 209                 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
 210                         (unsigned long) f->f_choice, 0, 0 );
 211                 /* Must not return NULL, otherwise extended filters break */
 212                 MDB_IDL_ALL( ids );
 213         }
 214         if ( ids[2] == NOID && MDB_IDL_IS_RANGE( ids )) {
 215                 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 216                 ID last;
 217
 218                 if ( mdb->mi_nextid ) {
 219                         last = mdb->mi_nextid;
 220                 } else {
 221                         MDB_cursor *mc;
 222                         MDB_val key;
 223
 224                         last = 0;
 225                         rc = mdb_cursor_open( rtxn, mdb->mi_id2entry, &mc );
 226                         if ( !rc ) {
 227                                 rc = mdb_cursor_get( mc, &key, NULL, MDB_LAST );
 228                                 if ( !rc )
 229                                         memcpy( &last, key.mv_data, sizeof( last ));
 230                                 mdb_cursor_close( mc );
 231                         }
 232                 }
 233                 if ( last ) {
 234                         ids[2] = last;
 235                 } else {
 236                         MDB_IDL_ZERO( ids );
 237                 }
 238         }
 239
 240 out:
 241         Debug( LDAP_DEBUG_FILTER,
 242                 "<= mdb_filter_candidates: id=%ld first=%ld last=%ld\n",
 243                 (long) ids[0],
 244                 (long) MDB_IDL_FIRST( ids ),
 245                 (long) MDB_IDL_LAST( ids ) );
 246
 247         return rc;
 248 }
 249
 250 #ifdef LDAP_COMP_MATCH
 251 static int
 252 comp_list_candidates(
 253         Operation *op,
 254         MDB_txn *rtxn,
 255         MatchingRuleAssertion* mra,
 256         ComponentFilter *flist,
 257         int     ftype,
 258         ID *ids,
 259         ID *tmp,
 260         ID *save )
 261 {
 262         int rc = 0;
 263         ComponentFilter *f;
 264
 265         Debug( LDAP_DEBUG_FILTER, "=> comp_list_candidates 0x%x\n", ftype, 0, 0 );
 266         for ( f = flist; f != NULL; f = f->cf_next ) {
 267                 /* ignore precomputed scopes */
 268                 if ( f->cf_choice == SLAPD_FILTER_COMPUTED &&
 269                      f->cf_result == LDAP_SUCCESS ) {
 270                         continue;
 271                 }
 272                 MDB_IDL_ZERO( save );
 273                 rc = comp_candidates( op, rtxn, mra, f, save, tmp, save+MDB_IDL_UM_SIZE );
 274
 275                 if ( rc != 0 ) {
 276                         if ( ftype == LDAP_COMP_FILTER_AND ) {
 277                                 rc = 0;
 278                                 continue;
 279                         }
 280                         break;
 281                 }
 282
 283                 if ( ftype == LDAP_COMP_FILTER_AND ) {
 284                         if ( f == flist ) {
 285                                 MDB_IDL_CPY( ids, save );
 286                         } else {
 287                                 mdb_idl_intersection( ids, save );
 288                         }
 289                         if( MDB_IDL_IS_ZERO( ids ) )
 290                                 break;
 291                 } else {
 292                         if ( f == flist ) {
 293                                 MDB_IDL_CPY( ids, save );
 294                         } else {
 295                                 mdb_idl_union( ids, save );
 296                         }
 297                 }
 298         }
 299
 300         if( rc == LDAP_SUCCESS ) {
 301                 Debug( LDAP_DEBUG_FILTER,
 302                         "<= comp_list_candidates: id=%ld first=%ld last=%ld\n",
 303                         (long) ids[0],
 304                         (long) MDB_IDL_FIRST(ids),
 305                         (long) MDB_IDL_LAST(ids) );
 306
 307         } else {
 308                 Debug( LDAP_DEBUG_FILTER,
 309                         "<= comp_list_candidates: undefined rc=%d\n",
 310                         rc, 0, 0 );
 311         }
 312
 313         return rc;
 314 }
 315
 316 static int
 317 comp_equality_candidates (
 318         Operation *op,
 319         MDB_txn *rtxn,
 320         MatchingRuleAssertion *mra,
 321         ComponentAssertion *ca,
 322         ID *ids,
 323         ID *tmp,
 324         ID *stack)
 325 {
 326         MDB_dbi   dbi;
 327         int i;
 328         int rc;
 329         slap_mask_t mask;
 330         struct berval prefix = {0, NULL};
 331         struct berval *keys = NULL;
 332         MatchingRule *mr = mra->ma_rule;
 333         Syntax *sat_syntax;
 334         ComponentReference* cr_list, *cr;
 335         AttrInfo *ai;
 336
 337         MDB_IDL_ALL( ids );
 338
 339         if ( !ca->ca_comp_ref )
 340                 return 0;
 341
 342         ai = mdb_attr_mask( op->o_bd->be_private, mra->ma_desc );
 343         if( ai ) {
 344                 cr_list = ai->ai_cr;
 345         }
 346         else {
 347                 return 0;
 348         }
 349         /* find a component reference to be indexed */
 350         sat_syntax = ca->ca_ma_rule->smr_syntax;
 351         for ( cr = cr_list ; cr ; cr = cr->cr_next ) {
 352                 if ( cr->cr_string.bv_len == ca->ca_comp_ref->cr_string.bv_len &&
 353                         strncmp( cr->cr_string.bv_val, ca->ca_comp_ref->cr_string.bv_val,cr->cr_string.bv_len ) == 0 )
 354                         break;
 355         }
 356
 357         if ( !cr )
 358                 return 0;
 359
 360         rc = mdb_index_param( op->o_bd, mra->ma_desc, LDAP_FILTER_EQUALITY,
 361                         &dbi, &mask, &prefix );
 362
 363         if( rc != LDAP_SUCCESS ) {
 364                 return 0;
 365         }
 366
 367         if( !mr ) {
 368                 return 0;
 369         }
 370
 371         if( !mr->smr_filter ) {
 372                 return 0;
 373         }
 374
 375         rc = (ca->ca_ma_rule->smr_filter)(
 376                                 LDAP_FILTER_EQUALITY,
 377                                 cr->cr_indexmask,
 378                                 sat_syntax,
 379                                 ca->ca_ma_rule,
 380                                 &prefix,
 381                                 &ca->ca_ma_value,
 382                                 &keys, op->o_tmpmemctx );
 383
 384         if( rc != LDAP_SUCCESS ) {
 385                 return 0;
 386         }
 387
 388         if( keys == NULL ) {
 389                 return 0;
 390         }
 391         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 392                 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
 393
 394                 if( rc == MDB_NOTFOUND ) {
 395                         MDB_IDL_ZERO( ids );
 396                         rc = 0;
 397                         break;
 398                 } else if( rc != LDAP_SUCCESS ) {
 399                         break;
 400                 }
 401
 402                 if( MDB_IDL_IS_ZERO( tmp ) ) {
 403                         MDB_IDL_ZERO( ids );
 404                         break;
 405                 }
 406
 407                 if ( i == 0 ) {
 408                         MDB_IDL_CPY( ids, tmp );
 409                 } else {
 410                         mdb_idl_intersection( ids, tmp );
 411                 }
 412
 413                 if( MDB_IDL_IS_ZERO( ids ) )
 414                         break;
 415         }
 416         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 417
 418         Debug( LDAP_DEBUG_TRACE,
 419                         "<= comp_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 420                         (long) ids[0],
 421                         (long) MDB_IDL_FIRST(ids),
 422                         (long) MDB_IDL_LAST(ids) );
 423         return( rc );
 424 }
 425
 426 static int
 427 ava_comp_candidates (
 428         Operation *op,
 429         MDB_txn *rtxn,
 430         AttributeAssertion *ava,
 431         AttributeAliasing *aa,
 432         ID *ids,
 433         ID *tmp,
 434         ID *stack )
 435 {
 436         MatchingRuleAssertion mra;
 437
 438         mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
 439         if ( !mra.ma_rule ) {
 440                 MDB_IDL_ALL( ids );
 441                 return 0;
 442         }
 443         mra.ma_desc = aa->aa_aliased_ad;
 444         mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
 445
 446         return comp_candidates ( op, rtxn, &mra, ava->aa_cf, ids, tmp, stack );
 447 }
 448
 449 static int
 450 comp_candidates (
 451         Operation *op,
 452         MDB_txn *rtxn,
 453         MatchingRuleAssertion *mra,
 454         ComponentFilter *f,
 455         ID *ids,
 456         ID *tmp,
 457         ID *stack)
 458 {
 459         int     rc;
 460
 461         if ( !f ) return LDAP_PROTOCOL_ERROR;
 462
 463         Debug( LDAP_DEBUG_FILTER, "comp_candidates\n", 0, 0, 0 );
 464         switch ( f->cf_choice ) {
 465         case SLAPD_FILTER_COMPUTED:
 466                 rc = f->cf_result;
 467                 break;
 468         case LDAP_COMP_FILTER_AND:
 469                 rc = comp_list_candidates( op, rtxn, mra, f->cf_and, LDAP_COMP_FILTER_AND, ids, tmp, stack );
 470                 break;
 471         case LDAP_COMP_FILTER_OR:
 472                 rc = comp_list_candidates( op, rtxn, mra, f->cf_or, LDAP_COMP_FILTER_OR, ids, tmp, stack );
 473                 break;
 474         case LDAP_COMP_FILTER_NOT:
 475                 /* No component indexing supported for NOT filter */
 476                 Debug( LDAP_DEBUG_FILTER, "\tComponent NOT\n", 0, 0, 0 );
 477                 MDB_IDL_ALL( ids );
 478                 rc = LDAP_PROTOCOL_ERROR;
 479                 break;
 480         case LDAP_COMP_FILTER_ITEM:
 481                 rc = comp_equality_candidates( op, rtxn, mra, f->cf_ca, ids, tmp, stack );
 482                 break;
 483         default:
 484                 MDB_IDL_ALL( ids );
 485                 rc = LDAP_PROTOCOL_ERROR;
 486         }
 487
 488         return( rc );
 489 }
 490 #endif
 491
 492 static int
 493 ext_candidates(
 494         Operation *op,
 495                 MDB_txn *rtxn,
 496         MatchingRuleAssertion *mra,
 497         ID *ids,
 498         ID *tmp,
 499         ID *stack)
 500 {
 501 #ifdef LDAP_COMP_MATCH
 502         /*
 503          * Currently Only Component Indexing for componentFilterMatch is supported
 504          * Indexing for an extensible filter is not supported yet
 505          */
 506         if ( mra->ma_cf ) {
 507                 return comp_candidates ( op, rtxn, mra, mra->ma_cf, ids, tmp, stack);
 508         }
 509 #endif
 510         if ( mra->ma_desc == slap_schema.si_ad_entryDN ) {
 511                 int rc;
 512                 ID id;
 513
 514                 MDB_IDL_ZERO( ids );
 515                 if ( mra->ma_rule == slap_schema.si_mr_distinguishedNameMatch ) {
 516 base:
 517                         rc = mdb_dn2id( op, rtxn, NULL, &mra->ma_value, &id, NULL, NULL, NULL );
 518                         if ( rc == MDB_SUCCESS ) {
 519                                 mdb_idl_insert( ids, id );
 520                         }
 521                         return 0;
 522                 } else if ( mra->ma_rule && mra->ma_rule->smr_match ==
 523                         dnRelativeMatch && dnIsSuffix( &mra->ma_value,
 524                                 op->o_bd->be_nsuffix )) {
 525                         int scope;
 526                         if ( mra->ma_rule == slap_schema.si_mr_dnSuperiorMatch ) {
 527                                 mdb_dn2sups( op, rtxn, &mra->ma_value, ids );
 528                                 return 0;
 529                         }
 530                         if ( mra->ma_rule == slap_schema.si_mr_dnSubtreeMatch )
 531                                 scope = LDAP_SCOPE_SUBTREE;
 532                         else if ( mra->ma_rule == slap_schema.si_mr_dnOneLevelMatch )
 533                                 scope = LDAP_SCOPE_ONELEVEL;
 534                         else if ( mra->ma_rule == slap_schema.si_mr_dnSubordinateMatch )
 535                                 scope = LDAP_SCOPE_SUBORDINATE;
 536                         else
 537                                 goto base;      /* scope = LDAP_SCOPE_BASE; */
 538 #if 0
 539                         if ( scope > LDAP_SCOPE_BASE ) {
 540                                 ei = NULL;
 541                                 rc = mdb_cache_find_ndn( op, rtxn, &mra->ma_value, &ei );
 542                                 if ( ei )
 543                                         mdb_cache_entryinfo_unlock( ei );
 544                                 if ( rc == LDAP_SUCCESS ) {
 545                                         int sc = op->ors_scope;
 546                                         op->ors_scope = scope;
 547                                         rc = mdb_dn2idl( op, rtxn, &mra->ma_value, ei, ids,
 548                                                 stack );
 549                                         op->ors_scope = sc;
 550                                 }
 551                                 return 0;
 552                         }
 553 #endif
 554                 }
 555         }
 556
 557         MDB_IDL_ALL( ids );
 558         return 0;
 559 }
 560
 561 static int
 562 list_candidates(
 563         Operation *op,
 564         MDB_txn *rtxn,
 565         Filter  *flist,
 566         int             ftype,
 567         ID *ids,
 568         ID *tmp,
 569         ID *save )
 570 {
 571         int rc = 0;
 572         Filter  *f;
 573
 574         Debug( LDAP_DEBUG_FILTER, "=> mdb_list_candidates 0x%x\n", ftype, 0, 0 );
 575         for ( f = flist; f != NULL; f = f->f_next ) {
 576                 /* ignore precomputed scopes */
 577                 if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
 578                      f->f_result == LDAP_SUCCESS ) {
 579                         continue;
 580                 }
 581                 MDB_IDL_ZERO( save );
 582                 rc = mdb_filter_candidates( op, rtxn, f, save, tmp,
 583                         save+MDB_IDL_UM_SIZE );
 584
 585                 if ( rc != 0 ) {
 586                         if ( ftype == LDAP_FILTER_AND ) {
 587                                 rc = 0;
 588                                 continue;
 589                         }
 590                         break;
 591                 }
 592
 593
 594                 if ( ftype == LDAP_FILTER_AND ) {
 595                         if ( f == flist ) {
 596                                 MDB_IDL_CPY( ids, save );
 597                         } else {
 598                                 mdb_idl_intersection( ids, save );
 599                         }
 600                         if( MDB_IDL_IS_ZERO( ids ) )
 601                                 break;
 602                 } else {
 603                         if ( f == flist ) {
 604                                 MDB_IDL_CPY( ids, save );
 605                         } else {
 606                                 mdb_idl_union( ids, save );
 607                         }
 608                 }
 609         }
 610
 611         if( rc == LDAP_SUCCESS ) {
 612                 Debug( LDAP_DEBUG_FILTER,
 613                         "<= mdb_list_candidates: id=%ld first=%ld last=%ld\n",
 614                         (long) ids[0],
 615                         (long) MDB_IDL_FIRST(ids),
 616                         (long) MDB_IDL_LAST(ids) );
 617
 618         } else {
 619                 Debug( LDAP_DEBUG_FILTER,
 620                         "<= mdb_list_candidates: undefined rc=%d\n",
 621                         rc, 0, 0 );
 622         }
 623
 624         return rc;
 625 }
 626
 627 static int
 628 presence_candidates(
 629         Operation *op,
 630         MDB_txn *rtxn,
 631         AttributeDescription *desc,
 632         ID *ids )
 633 {
 634         MDB_dbi dbi;
 635         int rc;
 636         slap_mask_t mask;
 637         struct berval prefix = {0, NULL};
 638
 639         Debug( LDAP_DEBUG_TRACE, "=> mdb_presence_candidates (%s)\n",
 640                         desc->ad_cname.bv_val, 0, 0 );
 641
 642         MDB_IDL_ALL( ids );
 643
 644         if( desc == slap_schema.si_ad_objectClass ) {
 645                 return 0;
 646         }
 647
 648         rc = mdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 649                 &dbi, &mask, &prefix );
 650
 651         if( rc == LDAP_INAPPROPRIATE_MATCHING ) {
 652                 /* not indexed */
 653                 Debug( LDAP_DEBUG_TRACE,
 654                         "<= mdb_presence_candidates: (%s) not indexed\n",
 655                         desc->ad_cname.bv_val, 0, 0 );
 656                 return 0;
 657         }
 658
 659         if( rc != LDAP_SUCCESS ) {
 660                 Debug( LDAP_DEBUG_TRACE,
 661                         "<= mdb_presence_candidates: (%s) index_param "
 662                         "returned=%d\n",
 663                         desc->ad_cname.bv_val, rc, 0 );
 664                 return 0;
 665         }
 666
 667         if( prefix.bv_val == NULL ) {
 668                 Debug( LDAP_DEBUG_TRACE,
 669                         "<= mdb_presence_candidates: (%s) no prefix\n",
 670                         desc->ad_cname.bv_val, 0, 0 );
 671                 return -1;
 672         }
 673
 674         rc = mdb_key_read( op->o_bd, rtxn, dbi, &prefix, ids, NULL, 0 );
 675
 676         if( rc == MDB_NOTFOUND ) {
 677                 MDB_IDL_ZERO( ids );
 678                 rc = 0;
 679         } else if( rc != LDAP_SUCCESS ) {
 680                 Debug( LDAP_DEBUG_TRACE,
 681                         "<= mdb_presense_candidates: (%s) "
 682                         "key read failed (%d)\n",
 683                         desc->ad_cname.bv_val, rc, 0 );
 684                 goto done;
 685         }
 686
 687         Debug(LDAP_DEBUG_TRACE,
 688                 "<= mdb_presence_candidates: id=%ld first=%ld last=%ld\n",
 689                 (long) ids[0],
 690                 (long) MDB_IDL_FIRST(ids),
 691                 (long) MDB_IDL_LAST(ids) );
 692
 693 done:
 694         return rc;
 695 }
 696
 697 static int
 698 equality_candidates(
 699         Operation *op,
 700         MDB_txn *rtxn,
 701         AttributeAssertion *ava,
 702         ID *ids,
 703         ID *tmp )
 704 {
 705         MDB_dbi dbi;
 706         int i;
 707         int rc;
 708         slap_mask_t mask;
 709         struct berval prefix = {0, NULL};
 710         struct berval *keys = NULL;
 711         MatchingRule *mr;
 712
 713         Debug( LDAP_DEBUG_TRACE, "=> mdb_equality_candidates (%s)\n",
 714                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 715
 716         if ( ava->aa_desc == slap_schema.si_ad_entryDN ) {
 717                 ID id;
 718                 rc = mdb_dn2id( op, rtxn, NULL, &ava->aa_value, &id, NULL, NULL, NULL );
 719                 if ( rc == LDAP_SUCCESS ) {
 720                         /* exactly one ID can match */
 721                         ids[0] = 1;
 722                         ids[1] = id;
 723                 }
 724                 if ( rc == MDB_NOTFOUND ) {
 725                         MDB_IDL_ZERO( ids );
 726                         rc = 0;
 727                 }
 728                 return rc;
 729         }
 730
 731         MDB_IDL_ALL( ids );
 732
 733         rc = mdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 734                 &dbi, &mask, &prefix );
 735
 736         if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
 737                 Debug( LDAP_DEBUG_ANY,
 738                         "<= mdb_equality_candidates: (%s) not indexed\n",
 739                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 740                 return 0;
 741         }
 742
 743         if( rc != LDAP_SUCCESS ) {
 744                 Debug( LDAP_DEBUG_ANY,
 745                         "<= mdb_equality_candidates: (%s) "
 746                         "index_param failed (%d)\n",
 747                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 748                 return 0;
 749         }
 750
 751         mr = ava->aa_desc->ad_type->sat_equality;
 752         if( !mr ) {
 753                 return 0;
 754         }
 755
 756         if( !mr->smr_filter ) {
 757                 return 0;
 758         }
 759
 760         rc = (mr->smr_filter)(
 761                 LDAP_FILTER_EQUALITY,
 762                 mask,
 763                 ava->aa_desc->ad_type->sat_syntax,
 764                 mr,
 765                 &prefix,
 766                 &ava->aa_value,
 767                 &keys, op->o_tmpmemctx );
 768
 769         if( rc != LDAP_SUCCESS ) {
 770                 Debug( LDAP_DEBUG_TRACE,
 771                         "<= mdb_equality_candidates: (%s, %s) "
 772                         "MR filter failed (%d)\n",
 773                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 774                 return 0;
 775         }
 776
 777         if( keys == NULL ) {
 778                 Debug( LDAP_DEBUG_TRACE,
 779                         "<= mdb_equality_candidates: (%s) no keys\n",
 780                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 781                 return 0;
 782         }
 783
 784         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 785                 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
 786
 787                 if( rc == MDB_NOTFOUND ) {
 788                         MDB_IDL_ZERO( ids );
 789                         rc = 0;
 790                         break;
 791                 } else if( rc != LDAP_SUCCESS ) {
 792                         Debug( LDAP_DEBUG_TRACE,
 793                                 "<= mdb_equality_candidates: (%s) "
 794                                 "key read failed (%d)\n",
 795                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 796                         break;
 797                 }
 798
 799                 if( MDB_IDL_IS_ZERO( tmp ) ) {
 800                         Debug( LDAP_DEBUG_TRACE,
 801                                 "<= mdb_equality_candidates: (%s) NULL\n",
 802                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 803                         MDB_IDL_ZERO( ids );
 804                         break;
 805                 }
 806
 807                 if ( i == 0 ) {
 808                         MDB_IDL_CPY( ids, tmp );
 809                 } else {
 810                         mdb_idl_intersection( ids, tmp );
 811                 }
 812
 813                 if( MDB_IDL_IS_ZERO( ids ) )
 814                         break;
 815         }
 816
 817         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 818
 819         Debug( LDAP_DEBUG_TRACE,
 820                 "<= mdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
 821                 (long) ids[0],
 822                 (long) MDB_IDL_FIRST(ids),
 823                 (long) MDB_IDL_LAST(ids) );
 824         return( rc );
 825 }
 826
 827
 828 static int
 829 approx_candidates(
 830         Operation *op,
 831         MDB_txn *rtxn,
 832         AttributeAssertion *ava,
 833         ID *ids,
 834         ID *tmp )
 835 {
 836         MDB_dbi dbi;
 837         int i;
 838         int rc;
 839         slap_mask_t mask;
 840         struct berval prefix = {0, NULL};
 841         struct berval *keys = NULL;
 842         MatchingRule *mr;
 843
 844         Debug( LDAP_DEBUG_TRACE, "=> mdb_approx_candidates (%s)\n",
 845                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 846
 847         MDB_IDL_ALL( ids );
 848
 849         rc = mdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 850                 &dbi, &mask, &prefix );
 851
 852         if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
 853                 Debug( LDAP_DEBUG_ANY,
 854                         "<= mdb_approx_candidates: (%s) not indexed\n",
 855                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
 856                 return 0;
 857         }
 858
 859         if( rc != LDAP_SUCCESS ) {
 860                 Debug( LDAP_DEBUG_ANY,
 861                         "<= mdb_approx_candidates: (%s) "
 862                         "index_param failed (%d)\n",
 863                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
 864                 return 0;
 865         }
 866
 867         mr = ava->aa_desc->ad_type->sat_approx;
 868         if( !mr ) {
 869                 /* no approx matching rule, try equality matching rule */
 870                 mr = ava->aa_desc->ad_type->sat_equality;
 871         }
 872
 873         if( !mr ) {
 874                 return 0;
 875         }
 876
 877         if( !mr->smr_filter ) {
 878                 return 0;
 879         }
 880
 881         rc = (mr->smr_filter)(
 882                 LDAP_FILTER_APPROX,
 883                 mask,
 884                 ava->aa_desc->ad_type->sat_syntax,
 885                 mr,
 886                 &prefix,
 887                 &ava->aa_value,
 888                 &keys, op->o_tmpmemctx );
 889
 890         if( rc != LDAP_SUCCESS ) {
 891                 Debug( LDAP_DEBUG_TRACE,
 892                         "<= mdb_approx_candidates: (%s, %s) "
 893                         "MR filter failed (%d)\n",
 894                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
 895                 return 0;
 896         }
 897
 898         if( keys == NULL ) {
 899                 Debug( LDAP_DEBUG_TRACE,
 900                         "<= mdb_approx_candidates: (%s) no keys (%s)\n",
 901                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, 0 );
 902                 return 0;
 903         }
 904
 905         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 906                 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
 907
 908                 if( rc == MDB_NOTFOUND ) {
 909                         MDB_IDL_ZERO( ids );
 910                         rc = 0;
 911                         break;
 912                 } else if( rc != LDAP_SUCCESS ) {
 913                         Debug( LDAP_DEBUG_TRACE,
 914                                 "<= mdb_approx_candidates: (%s) "
 915                                 "key read failed (%d)\n",
 916                                 ava->aa_desc->ad_cname.bv_val, rc, 0 );
 917                         break;
 918                 }
 919
 920                 if( MDB_IDL_IS_ZERO( tmp ) ) {
 921                         Debug( LDAP_DEBUG_TRACE,
 922                                 "<= mdb_approx_candidates: (%s) NULL\n",
 923                                 ava->aa_desc->ad_cname.bv_val, 0, 0 );
 924                         MDB_IDL_ZERO( ids );
 925                         break;
 926                 }
 927
 928                 if ( i == 0 ) {
 929                         MDB_IDL_CPY( ids, tmp );
 930                 } else {
 931                         mdb_idl_intersection( ids, tmp );
 932                 }
 933
 934                 if( MDB_IDL_IS_ZERO( ids ) )
 935                         break;
 936         }
 937
 938         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 939
 940         Debug( LDAP_DEBUG_TRACE, "<= mdb_approx_candidates %ld, first=%ld, last=%ld\n",
 941                 (long) ids[0],
 942                 (long) MDB_IDL_FIRST(ids),
 943                 (long) MDB_IDL_LAST(ids) );
 944         return( rc );
 945 }
 946
 947 static int
 948 substring_candidates(
 949         Operation *op,
 950         MDB_txn *rtxn,
 951         SubstringsAssertion     *sub,
 952         ID *ids,
 953         ID *tmp )
 954 {
 955         MDB_dbi dbi;
 956         int i;
 957         int rc;
 958         slap_mask_t mask;
 959         struct berval prefix = {0, NULL};
 960         struct berval *keys = NULL;
 961         MatchingRule *mr;
 962
 963         Debug( LDAP_DEBUG_TRACE, "=> mdb_substring_candidates (%s)\n",
 964                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 965
 966         MDB_IDL_ALL( ids );
 967
 968         rc = mdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 969                 &dbi, &mask, &prefix );
 970
 971         if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
 972                 Debug( LDAP_DEBUG_ANY,
 973                         "<= mdb_substring_candidates: (%s) not indexed\n",
 974                         sub->sa_desc->ad_cname.bv_val, 0, 0 );
 975                 return 0;
 976         }
 977
 978         if( rc != LDAP_SUCCESS ) {
 979                 Debug( LDAP_DEBUG_ANY,
 980                         "<= mdb_substring_candidates: (%s) "
 981                         "index_param failed (%d)\n",
 982                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
 983                 return 0;
 984         }
 985
 986         mr = sub->sa_desc->ad_type->sat_substr;
 987
 988         if( !mr ) {
 989                 return 0;
 990         }
 991
 992         if( !mr->smr_filter ) {
 993                 return 0;
 994         }
 995
 996         rc = (mr->smr_filter)(
 997                 LDAP_FILTER_SUBSTRINGS,
 998                 mask,
 999                 sub->sa_desc->ad_type->sat_syntax,
1000                 mr,
1001                 &prefix,
1002                 sub,
1003                 &keys, op->o_tmpmemctx );
1004
1005         if( rc != LDAP_SUCCESS ) {
1006                 Debug( LDAP_DEBUG_TRACE,
1007                         "<= mdb_substring_candidates: (%s) "
1008                         "MR filter failed (%d)\n",
1009                         sub->sa_desc->ad_cname.bv_val, rc, 0 );
1010                 return 0;
1011         }
1012
1013         if( keys == NULL ) {
1014                 Debug( LDAP_DEBUG_TRACE,
1015                         "<= mdb_substring_candidates: (0x%04lx) no keys (%s)\n",
1016                         mask, sub->sa_desc->ad_cname.bv_val, 0 );
1017                 return 0;
1018         }
1019
1020         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
1021                 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
1022
1023                 if( rc == MDB_NOTFOUND ) {
1024                         MDB_IDL_ZERO( ids );
1025                         rc = 0;
1026                         break;
1027                 } else if( rc != LDAP_SUCCESS ) {
1028                         Debug( LDAP_DEBUG_TRACE,
1029                                 "<= mdb_substring_candidates: (%s) "
1030                                 "key read failed (%d)\n",
1031                                 sub->sa_desc->ad_cname.bv_val, rc, 0 );
1032                         break;
1033                 }
1034
1035                 if( MDB_IDL_IS_ZERO( tmp ) ) {
1036                         Debug( LDAP_DEBUG_TRACE,
1037                                 "<= mdb_substring_candidates: (%s) NULL\n",
1038                                 sub->sa_desc->ad_cname.bv_val, 0, 0 );
1039                         MDB_IDL_ZERO( ids );
1040                         break;
1041                 }
1042
1043                 if ( i == 0 ) {
1044                         MDB_IDL_CPY( ids, tmp );
1045                 } else {
1046                         mdb_idl_intersection( ids, tmp );
1047                 }
1048
1049                 if( MDB_IDL_IS_ZERO( ids ) )
1050                         break;
1051         }
1052
1053         ber_bvarray_free_x( keys, op->o_tmpmemctx );
1054
1055         Debug( LDAP_DEBUG_TRACE, "<= mdb_substring_candidates: %ld, first=%ld, last=%ld\n",
1056                 (long) ids[0],
1057                 (long) MDB_IDL_FIRST(ids),
1058                 (long) MDB_IDL_LAST(ids) );
1059         return( rc );
1060 }
1061
1062 static int
1063 inequality_candidates(
1064         Operation *op,
1065         MDB_txn *rtxn,
1066         AttributeAssertion *ava,
1067         ID *ids,
1068         ID *tmp,
1069         int gtorlt )
1070 {
1071         MDB_dbi dbi;
1072         int rc;
1073         slap_mask_t mask;
1074         struct berval prefix = {0, NULL};
1075         struct berval *keys = NULL;
1076         MatchingRule *mr;
1077         MDB_cursor *cursor = NULL;
1078
1079         Debug( LDAP_DEBUG_TRACE, "=> mdb_inequality_candidates (%s)\n",
1080                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
1081
1082         MDB_IDL_ALL( ids );
1083
1084         rc = mdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
1085                 &dbi, &mask, &prefix );
1086
1087         if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
1088                 Debug( LDAP_DEBUG_ANY,
1089                         "<= mdb_inequality_candidates: (%s) not indexed\n",
1090                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
1091                 return 0;
1092         }
1093
1094         if( rc != LDAP_SUCCESS ) {
1095                 Debug( LDAP_DEBUG_ANY,
1096                         "<= mdb_inequality_candidates: (%s) "
1097                         "index_param failed (%d)\n",
1098                         ava->aa_desc->ad_cname.bv_val, rc, 0 );
1099                 return 0;
1100         }
1101
1102         mr = ava->aa_desc->ad_type->sat_equality;
1103         if( !mr ) {
1104                 return 0;
1105         }
1106
1107         if( !mr->smr_filter ) {
1108                 return 0;
1109         }
1110
1111         rc = (mr->smr_filter)(
1112                 LDAP_FILTER_EQUALITY,
1113                 mask,
1114                 ava->aa_desc->ad_type->sat_syntax,
1115                 mr,
1116                 &prefix,
1117                 &ava->aa_value,
1118                 &keys, op->o_tmpmemctx );
1119
1120         if( rc != LDAP_SUCCESS ) {
1121                 Debug( LDAP_DEBUG_TRACE,
1122                         "<= mdb_inequality_candidates: (%s, %s) "
1123                         "MR filter failed (%d)\n",
1124                         prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
1125                 return 0;
1126         }
1127
1128         if( keys == NULL ) {
1129                 Debug( LDAP_DEBUG_TRACE,
1130                         "<= mdb_inequality_candidates: (%s) no keys\n",
1131                         ava->aa_desc->ad_cname.bv_val, 0, 0 );
1132                 return 0;
1133         }
1134
1135         MDB_IDL_ZERO( ids );
1136         while(1) {
1137                 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[0], tmp, &cursor, gtorlt );
1138
1139                 if( rc == MDB_NOTFOUND ) {
1140                         rc = 0;
1141                         break;
1142                 } else if( rc != LDAP_SUCCESS ) {
1143                         Debug( LDAP_DEBUG_TRACE,
1144                                "<= mdb_inequality_candidates: (%s) "
1145                                "key read failed (%d)\n",
1146                                ava->aa_desc->ad_cname.bv_val, rc, 0 );
1147                         break;
1148                 }
1149
1150                 if( MDB_IDL_IS_ZERO( tmp ) ) {
1151                         Debug( LDAP_DEBUG_TRACE,
1152                                "<= mdb_inequality_candidates: (%s) NULL\n",
1153                                ava->aa_desc->ad_cname.bv_val, 0, 0 );
1154                         break;
1155                 }
1156
1157                 mdb_idl_union( ids, tmp );
1158
1159                 if( op->ors_limit && op->ors_limit->lms_s_unchecked != -1 &&
1160                         MDB_IDL_N( ids ) >= (unsigned) op->ors_limit->lms_s_unchecked ) {
1161                         mdb_cursor_close( cursor );
1162                         break;
1163                 }
1164         }
1165         ber_bvarray_free_x( keys, op->o_tmpmemctx );
1166
1167         Debug( LDAP_DEBUG_TRACE,
1168                 "<= mdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
1169                 (long) ids[0],
1170                 (long) MDB_IDL_FIRST(ids),
1171                 (long) MDB_IDL_LAST(ids) );
1172         return( rc );
1173 }