git.sur5r.net Git - openldap/blob - servers/slapd/back-ldbm/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 1998-2005 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
  21 #include <ac/socket.h>
  22 #include <ac/string.h>
  23
  24 #include "slap.h"
  25 #include "back-ldbm.h"
  26
  27 static ID_BLOCK *presence_candidates(
  28         Operation *op,
  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(
  35         Operation *op,
  36         SubstringsAssertion *sub );
  37 static ID_BLOCK *list_candidates(
  38         Operation *op,
  39         Filter *flist,
  40         int ftype );
  41
  42 ID_BLOCK *
  43 filter_candidates(
  44     Operation   *op,
  45     Filter      *f
  46 )
  47 {
  48         char *sub = "SUBTREE";
  49         ID_BLOCK        *result;
  50
  51         Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
  52
  53
  54         result = NULL;
  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.
  61                  */
  62                 /* FALLTHRU */
  63                 case LDAP_COMPARE_FALSE:
  64                         result = NULL;
  65                         break;
  66                 case LDAP_COMPARE_TRUE:
  67                         result = idl_allids( op->o_bd );
  68                         break;
  69                 }
  70                 break;
  71
  72         case SLAPD_FILTER_DN_ONE:
  73                 Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
  74
  75                 /* an error is treated as an empty list */
  76                 if ( dn2idl( op->o_bd, f->f_dn, DN_ONE_PREFIX, &result ) != 0
  77                                 && result != NULL ) {
  78                         idl_free( result );
  79                         result = NULL;
  80                 }
  81                 break;
  82
  83 #ifdef SLAPD_FILTER_DN_CHILDREN
  84         case SLAPD_FILTER_DN_CHILDREN:
  85                 sub = "CHILDREN";
  86 #endif
  87         case SLAPD_FILTER_DN_SUBTREE:
  88                 Debug( LDAP_DEBUG_FILTER,
  89                         "\tDN %s\n", sub, 0, 0 );
  90
  91                 /* an error is treated as an empty list */
  92                 if ( dn2idl( op->o_bd, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
  93                                 && result != NULL ) {
  94                         idl_free( result );
  95                         result = NULL;
  96                 }
  97                 break;
  98
  99         case LDAP_FILTER_PRESENT:
 100                 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
 101
 102                 result = presence_candidates( op, f->f_desc );
 103                 break;
 104
 105         case LDAP_FILTER_EQUALITY:
 106                 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
 107
 108                 result = equality_candidates( op, f->f_ava );
 109                 break;
 110
 111         case LDAP_FILTER_APPROX:
 112                 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
 113
 114                 result = approx_candidates( op, f->f_ava );
 115                 break;
 116
 117         case LDAP_FILTER_SUBSTRINGS:
 118                 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
 119
 120                 result = substring_candidates( op, f->f_sub );
 121                 break;
 122
 123         case LDAP_FILTER_GE:
 124                 Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
 125
 126                 result = presence_candidates( op, f->f_ava->aa_desc );
 127                 break;
 128
 129         case LDAP_FILTER_LE:
 130                 Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
 131
 132                 result = presence_candidates( op, f->f_ava->aa_desc );
 133                 break;
 134
 135         case LDAP_FILTER_AND:
 136                 Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
 137
 138                 result = list_candidates( op, f->f_and, LDAP_FILTER_AND );
 139                 break;
 140
 141         case LDAP_FILTER_OR:
 142                 Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
 143
 144                 result = list_candidates( op, f->f_or, LDAP_FILTER_OR );
 145                 break;
 146
 147         case LDAP_FILTER_NOT:
 148                 Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
 149
 150                 /*
 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.
 155                  */
 156                 result = idl_allids( op->o_bd );
 157                 break;
 158         default:
 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.
 162                  */
 163                 result = idl_allids( op->o_bd );
 164                 break;
 165         }
 166
 167         Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
 168             result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
 169
 170         return( result );
 171 }
 172
 173 static ID_BLOCK *
 174 presence_candidates(
 175     Operation *op,
 176         AttributeDescription *desc
 177 )
 178 {
 179         ID_BLOCK        *idl;
 180         DBCache *db;
 181         int rc;
 182         char *dbname;
 183         slap_mask_t mask;
 184         struct berval prefix = {0, NULL};
 185
 186         Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
 187
 188         idl = idl_allids( op->o_bd );
 189
 190         if( desc == slap_schema.si_ad_objectClass ) {
 191                 return idl;
 192         }
 193
 194         rc = index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
 195                 &dbname, &mask, &prefix );
 196
 197         if( rc != LDAP_SUCCESS ) {
 198                 Debug( LDAP_DEBUG_TRACE,
 199                     "<= presence_candidates: index_param returned=%d\n",
 200                         rc, 0, 0 );
 201
 202                 return idl;
 203         }
 204
 205         if( dbname == NULL ) {
 206                 /* not indexed */
 207                 Debug( LDAP_DEBUG_TRACE,
 208                     "<= presense_candidates: not indexed\n",
 209                         0, 0, 0 );
 210
 211                 return idl;
 212         }
 213
 214         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 215
 216         if ( db == NULL ) {
 217                 Debug( LDAP_DEBUG_ANY,
 218                     "<= presense_candidates db open failed (%s%s)\n",
 219                         dbname, LDBM_SUFFIX, 0 );
 220
 221                 return idl;
 222         }
 223
 224         if( prefix.bv_val != NULL ) {
 225                 idl_free( idl );
 226                 idl = NULL;
 227
 228                 rc = key_read( op->o_bd, db, &prefix, &idl );
 229
 230                 if( rc != LDAP_SUCCESS ) {
 231                         Debug( LDAP_DEBUG_TRACE,
 232                                 "<= presense_candidates key read failed (%d)\n",
 233                             rc, 0, 0 );
 234
 235
 236                 } else if( idl == NULL ) {
 237                         Debug( LDAP_DEBUG_TRACE,
 238                                 "<= presense_candidates NULL\n",
 239                             0, 0, 0 );
 240
 241                 }
 242         }
 243
 244         ldbm_cache_close( op->o_bd, db );
 245
 246         Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
 247             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 248
 249         return( idl );
 250 }
 251
 252 static ID_BLOCK *
 253 equality_candidates(
 254     Operation *op,
 255         AttributeAssertion *ava
 256 )
 257 {
 258         ID_BLOCK        *idl;
 259         DBCache *db;
 260         int i;
 261         int rc;
 262         char *dbname;
 263         slap_mask_t mask;
 264         struct berval prefix = {0, NULL};
 265         struct berval *keys = NULL;
 266         MatchingRule *mr;
 267
 268         Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
 269
 270
 271         idl = idl_allids( op->o_bd );
 272
 273         rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
 274                 &dbname, &mask, &prefix );
 275
 276         if( rc != LDAP_SUCCESS ) {
 277                 Debug( LDAP_DEBUG_TRACE,
 278                     "<= equality_candidates: index_param returned=%d\n",
 279                         rc, 0, 0 );
 280
 281                 return idl;
 282         }
 283
 284         if( dbname == NULL ) {
 285                 /* not indexed */
 286                 Debug( LDAP_DEBUG_TRACE,
 287                     "<= equality_candidates: not indexed\n",
 288                         0, 0, 0 );
 289
 290                 return idl;
 291         }
 292
 293         mr = ava->aa_desc->ad_type->sat_equality;
 294         if( !mr ) {
 295                 return idl;
 296         }
 297
 298         if( !mr->smr_filter ) {
 299                 return idl;
 300         }
 301
 302         rc = (mr->smr_filter)(
 303                 LDAP_FILTER_EQUALITY,
 304                 mask,
 305                 ava->aa_desc->ad_type->sat_syntax,
 306                 mr,
 307                 &prefix,
 308                 &ava->aa_value,
 309                 &keys, op->o_tmpmemctx );
 310
 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 );
 315
 316                 return idl;
 317         }
 318
 319         if( keys == NULL ) {
 320                 Debug( LDAP_DEBUG_TRACE,
 321                     "<= equality_candidates: no keys (%s%s)\n",
 322                         dbname, LDBM_SUFFIX, 0 );
 323
 324                 return idl;
 325         }
 326
 327         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 328
 329         if ( db == NULL ) {
 330                 Debug( LDAP_DEBUG_ANY,
 331                     "<= equality_candidates db open failed (%s%s)\n",
 332                         dbname, LDBM_SUFFIX, 0 );
 333
 334                 return idl;
 335         }
 336
 337         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 338                 ID_BLOCK *save;
 339                 ID_BLOCK *tmp;
 340
 341                 rc = key_read( op->o_bd, db, &keys[i], &tmp );
 342
 343                 if( rc != LDAP_SUCCESS ) {
 344                         idl_free( idl );
 345                         idl = NULL;
 346                         Debug( LDAP_DEBUG_TRACE,
 347                                 "<= equality_candidates key read failed (%d)\n",
 348                             rc, 0, 0 );
 349
 350                         break;
 351                 }
 352
 353                 if( tmp == NULL ) {
 354                         idl_free( idl );
 355                         idl = NULL;
 356                         Debug( LDAP_DEBUG_TRACE,
 357                                 "<= equality_candidates NULL\n",
 358                             0, 0, 0 );
 359
 360                         break;
 361                 }
 362
 363                 save = idl;
 364                 idl = idl_intersection( op->o_bd, idl, tmp );
 365                 idl_free( save );
 366                 idl_free( tmp );
 367
 368                 if( idl == NULL ) break;
 369         }
 370
 371         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 372
 373         ldbm_cache_close( op->o_bd, db );
 374
 375
 376         Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
 377             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 378
 379         return( idl );
 380 }
 381
 382 static ID_BLOCK *
 383 approx_candidates(
 384     Operation *op,
 385         AttributeAssertion *ava
 386 )
 387 {
 388         ID_BLOCK *idl;
 389         DBCache *db;
 390         int i;
 391         int rc;
 392         char *dbname;
 393         slap_mask_t mask;
 394         struct berval prefix = {0, NULL};
 395         struct berval *keys = NULL;
 396         MatchingRule *mr;
 397
 398         Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
 399
 400
 401         idl = idl_allids( op->o_bd );
 402
 403         rc = index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
 404                 &dbname, &mask, &prefix );
 405
 406         if( rc != LDAP_SUCCESS ) {
 407                 Debug( LDAP_DEBUG_TRACE,
 408                     "<= approx_candidates: index_param returned=%d\n",
 409                         rc, 0, 0 );
 410
 411                 return idl;
 412         }
 413
 414         if( dbname == NULL ) {
 415                 /* not indexed */
 416                 Debug( LDAP_DEBUG_ANY,
 417                     "<= approx_candidates: not indexed\n",
 418                         0, 0, 0 );
 419
 420                 return idl;
 421         }
 422
 423         mr = ava->aa_desc->ad_type->sat_approx;
 424         if( !mr ) {
 425                 /* no approx matching rule, try equality matching rule */
 426                 mr = ava->aa_desc->ad_type->sat_equality;
 427         }
 428
 429         if( !mr ) {
 430                 return idl;
 431         }
 432
 433         if( !mr->smr_filter ) {
 434                 return idl;
 435         }
 436
 437         rc = (mr->smr_filter)(
 438                 LDAP_FILTER_APPROX,
 439                 mask,
 440                 ava->aa_desc->ad_type->sat_syntax,
 441                 mr,
 442                 &prefix,
 443                 &ava->aa_value,
 444                 &keys, op->o_tmpmemctx );
 445
 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 );
 450
 451                 return idl;
 452         }
 453
 454         if( keys == NULL ) {
 455                 Debug( LDAP_DEBUG_TRACE,
 456                     "<= approx_candidates: no keys (%s%s)\n",
 457                         dbname, LDBM_SUFFIX, 0 );
 458
 459                 return idl;
 460         }
 461
 462         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 463
 464         if ( db == NULL ) {
 465                 Debug( LDAP_DEBUG_ANY,
 466                     "<= approx_candidates db open failed (%s%s)\n",
 467                         dbname, LDBM_SUFFIX, 0 );
 468
 469                 return idl;
 470         }
 471
 472         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 473                 ID_BLOCK *save;
 474                 ID_BLOCK *tmp;
 475
 476                 rc = key_read( op->o_bd, db, &keys[i], &tmp );
 477
 478                 if( rc != LDAP_SUCCESS ) {
 479                         idl_free( idl );
 480                         idl = NULL;
 481                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
 482                             rc, 0, 0 );
 483
 484                         break;
 485                 }
 486
 487                 if( tmp == NULL ) {
 488                         idl_free( idl );
 489                         idl = NULL;
 490                         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
 491                             0, 0, 0 );
 492
 493                         break;
 494                 }
 495
 496                 save = idl;
 497                 idl = idl_intersection( op->o_bd, idl, tmp );
 498                 idl_free( save );
 499                 idl_free( tmp );
 500
 501                 if( idl == NULL ) break;
 502         }
 503
 504         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 505
 506         ldbm_cache_close( op->o_bd, db );
 507
 508         Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
 509             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 510
 511         return( idl );
 512 }
 513
 514 static ID_BLOCK *
 515 list_candidates(
 516     Operation *op,
 517     Filter      *flist,
 518     int         ftype
 519 )
 520 {
 521         ID_BLOCK        *idl, *tmp, *tmp2;
 522         Filter  *f;
 523
 524         Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
 525
 526
 527         idl = NULL;
 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 );
 533
 534                         idl_free( idl );
 535                         return( NULL );
 536                 }
 537
 538                 tmp2 = idl;
 539                 if ( idl == NULL ) {
 540                         idl = tmp;
 541                 } else if ( ftype == LDAP_FILTER_AND ) {
 542                         idl = idl_intersection( op->o_bd, idl, tmp );
 543                         idl_free( tmp );
 544                         idl_free( tmp2 );
 545                 } else {
 546                         idl = idl_union( op->o_bd, idl, tmp );
 547                         idl_free( tmp );
 548                         idl_free( tmp2 );
 549                 }
 550         }
 551
 552         Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
 553             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 554
 555         return( idl );
 556 }
 557
 558 static ID_BLOCK *
 559 substring_candidates(
 560     Operation *op,
 561     SubstringsAssertion *sub
 562 )
 563 {
 564         ID_BLOCK *idl;
 565         DBCache *db;
 566         int i;
 567         int rc;
 568         char *dbname;
 569         slap_mask_t mask;
 570         struct berval prefix = {0, NULL};
 571         struct berval *keys = NULL;
 572         MatchingRule *mr;
 573
 574         Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
 575
 576
 577         idl = idl_allids( op->o_bd );
 578
 579         rc = index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
 580                 &dbname, &mask, &prefix );
 581
 582         if( rc != LDAP_SUCCESS ) {
 583                 Debug( LDAP_DEBUG_TRACE,
 584                     "<= substrings_candidates: index_param returned=%d\n",
 585                         rc, 0, 0 );
 586
 587                 return idl;
 588         }
 589
 590         if( dbname == NULL ) {
 591                 /* not indexed */
 592                 Debug( LDAP_DEBUG_ANY,
 593                     "<= substrings_candidates: not indexed\n",
 594                         0, 0, 0 );
 595
 596                 return idl;
 597         }
 598
 599         mr = sub->sa_desc->ad_type->sat_substr;
 600
 601         if( !mr ) {
 602                 return idl;
 603         }
 604
 605         if( !mr->smr_filter ) {
 606                 return idl;
 607         }
 608
 609         rc = (mr->smr_filter)(
 610                 LDAP_FILTER_SUBSTRINGS,
 611                 mask,
 612                 sub->sa_desc->ad_type->sat_syntax,
 613                 mr,
 614                 &prefix,
 615                 sub,
 616                 &keys, op->o_tmpmemctx );
 617
 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 );
 622
 623                 return idl;
 624         }
 625
 626         if( keys == NULL ) {
 627                 Debug( LDAP_DEBUG_TRACE,
 628                     "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
 629                         mask, dbname, LDBM_SUFFIX );
 630
 631                 return idl;
 632         }
 633
 634         db = ldbm_cache_open( op->o_bd, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
 635
 636         if ( db == NULL ) {
 637                 Debug( LDAP_DEBUG_ANY,
 638                     "<= substrings_candidates db open failed (%s%s)\n",
 639                         dbname, LDBM_SUFFIX, 0 );
 640
 641                 return idl;
 642         }
 643
 644         for ( i= 0; keys[i].bv_val != NULL; i++ ) {
 645                 ID_BLOCK *save;
 646                 ID_BLOCK *tmp;
 647
 648                 rc = key_read( op->o_bd, db, &keys[i], &tmp );
 649
 650                 if( rc != LDAP_SUCCESS ) {
 651                         idl_free( idl );
 652                         idl = NULL;
 653                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
 654                             rc, 0, 0 );
 655
 656                         break;
 657                 }
 658
 659                 if( tmp == NULL ) {
 660                         idl_free( idl );
 661                         idl = NULL;
 662                         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
 663                             0, 0, 0 );
 664
 665                         break;
 666                 }
 667
 668                 save = idl;
 669                 idl = idl_intersection( op->o_bd, idl, tmp );
 670                 idl_free( save );
 671                 idl_free( tmp );
 672
 673                 if( idl == NULL ) break;
 674         }
 675
 676         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 677
 678         ldbm_cache_close( op->o_bd, db );
 679
 680         Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
 681             idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
 682
 683         return( idl );
 684 }