git.sur5r.net Git - openldap/blob - libraries/libldap/filter.c

   1 /* $OpenLDAP$ */
   2 /*
   3  * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
   4  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   5  */
   6 /*  Portions
   7  *  Copyright (c) 1990 Regents of the University of Michigan.
   8  *  All rights reserved.
   9  *
  10  *  search.c
  11  */
  12
  13 #include "portable.h"
  14
  15 #include <stdio.h>
  16
  17 #include <ac/stdlib.h>
  18
  19 #include <ac/socket.h>
  20 #include <ac/string.h>
  21 #include <ac/time.h>
  22
  23 #include "ldap-int.h"
  24
  25 static char *put_complex_filter LDAP_P((
  26         BerElement *ber,
  27         char *str,
  28         ber_tag_t tag,
  29         int not ));
  30
  31 static int put_simple_filter LDAP_P((
  32         BerElement *ber,
  33         char *str ));
  34
  35 static int put_substring_filter LDAP_P((
  36         BerElement *ber,
  37         char *type,
  38         char *str ));
  39
  40 static int put_filter_list LDAP_P((
  41         BerElement *ber,
  42         char *str,
  43         ber_tag_t tag ));
  44
  45 static int ldap_is_oid ( const char *str )
  46 {
  47         int i;
  48
  49         if( LDAP_ALPHA( str[0] )) {
  50                 for( i=1; str[i]; i++ ) {
  51                         if( !LDAP_LDH( str[i] )) {
  52                                 return 0;
  53                         }
  54                 }
  55                 return 1;
  56
  57         } else if LDAP_DIGIT( str[0] ) {
  58                 int dot=0;
  59                 for( i=1; str[i]; i++ ) {
  60                         if( LDAP_DIGIT( str[i] )) {
  61                                 dot=0;
  62
  63                         } else if ( str[i] == '.' ) {
  64                                 if( dot ) return 0;
  65                                 if( ++dot > 1 ) return 0;
  66
  67                         } else {
  68                                 return 0;
  69                         }
  70                 }
  71                 return !dot;
  72         }
  73
  74         return 0;
  75 }
  76
  77 static int ldap_is_desc ( const char *str )
  78 {
  79         int i;
  80
  81         if( LDAP_ALPHA( str[0] )) {
  82                 for( i=1; str[i]; i++ ) {
  83                         if( str[i] == ';' ) {
  84                                 str = &str[i+1];
  85                                 goto options;
  86                         }
  87
  88                         if( !LDAP_LDH( str[i] )) {
  89                                 return 0;
  90                         }
  91                 }
  92                 return 1;
  93
  94         } else if LDAP_DIGIT( str[0] ) {
  95                 int dot=0;
  96                 for( i=1; str[i]; i++ ) {
  97                         if( str[i] == ';' ) {
  98                                 if( dot ) return 0;
  99                                 str = &str[i+1];
 100                                 goto options;
 101                         }
 102
 103                         if( LDAP_DIGIT( str[i] )) {
 104                                 dot=0;
 105
 106                         } else if ( str[i] == '.' ) {
 107                                 if( dot ) return 0;
 108                                 if( ++dot > 1 ) return 0;
 109
 110                         } else {
 111                                 return 0;
 112                         }
 113                 }
 114                 return !dot;
 115         }
 116
 117         return 0;
 118
 119 options:
 120         if( !LDAP_LDH( str[0] )) {
 121                 return 0;
 122         }
 123         for( i=1; str[i]; i++ ) {
 124                 if( str[i] == ';' ) {
 125                         str = &str[i+1];
 126                         goto options;
 127                 }
 128                 if( !LDAP_LDH( str[i] )) {
 129                         return 0;
 130                 }
 131         }
 132         return 1;
 133 }
 134
 135 static char *
 136 find_right_paren( char *s )
 137 {
 138         int     balance, escape;
 139
 140         balance = 1;
 141         escape = 0;
 142         while ( *s && balance ) {
 143                 if ( !escape ) {
 144                         if ( *s == '(' ) {
 145                                 balance++;
 146                         } else if ( *s == ')' ) {
 147                                 balance--;
 148                         }
 149                 }
 150
 151                 escape = ( *s == '\\' && !escape );
 152
 153                 if ( balance ) s++;
 154         }
 155
 156         return *s ? s : NULL;
 157 }
 158
 159 static int hex2value( int c )
 160 {
 161         if( c >= '0' && c <= '9' ) {
 162                 return c - '0';
 163         }
 164
 165         if( c >= 'A' && c <= 'F' ) {
 166                 return c + (10 - (int) 'A');
 167         }
 168
 169         if( c >= 'a' && c <= 'f' ) {
 170                 return c + (10 - (int) 'a');
 171         }
 172
 173         return -1;
 174 }
 175
 176 char *
 177 ldap_pvt_find_wildcard( const char *s )
 178 {
 179         for( ; *s; s++ ) {
 180                 switch( *s ) {
 181                 case '*':       /* found wildcard */
 182                         return (char *) s;
 183
 184                 case '(':
 185                 case ')':
 186                         return NULL;
 187
 188                 case '\\':
 189                         if( s[1] == '\0' ) return NULL;
 190
 191                         if( LDAP_HEX( s[1] ) && LDAP_HEX( s[2] ) ) {
 192                                 s+=2;
 193
 194                         } else switch( s[1] ) {
 195                         default:
 196                                 return NULL;
 197
 198                         /* allow RFC 1960 escapes */
 199                         case '*':
 200                         case '(':
 201                         case ')':
 202                         case '\\':
 203                                 s++;
 204                         }
 205                 }
 206         }
 207
 208         return (char *) s;
 209 }
 210
 211 /* unescape filter value */
 212 /* support both LDAP v2 and v3 escapes */
 213 /* output can include nul characters! */
 214 ber_slen_t
 215 ldap_pvt_filter_value_unescape( char *fval )
 216 {
 217         ber_slen_t r, v;
 218         int v1, v2;
 219
 220         for( r=v=0; fval[v] != '\0'; v++ ) {
 221                 switch( fval[v] ) {
 222                 case '(':
 223                 case ')':
 224                         return -1;
 225
 226                 case '\\':
 227                         /* escape */
 228                         v++;
 229
 230                         if ( fval[v] == '\0' ) {
 231                                 /* escape at end of string */
 232                                 return -1;
 233                         }
 234
 235                         if (( v1 = hex2value( fval[v] )) >= 0 ) {
 236                                 /* LDAPv3 escape */
 237                                 if (( v2 = hex2value( fval[v+1] )) < 0 ) {
 238                                         /* must be two digit code */
 239                                         return -1;
 240                                 }
 241
 242                                 fval[r++] = v1 * 16 + v2;
 243                                 v++;
 244
 245                         } else {
 246                                 /* LDAPv2 escape */
 247                                 switch( fval[v] ) {
 248                                 case '(':
 249                                 case ')':
 250                                 case '*':
 251                                 case '\\':
 252                                         fval[r++] = fval[v];
 253                                         break;
 254                                 default:
 255                                         /* illegal escape */
 256                                         return -1;
 257                                 }
 258                         }
 259                         break;
 260
 261                 default:
 262                         fval[r++] = fval[v];
 263                 }
 264         }
 265
 266         fval[r] = '\0';
 267         return r;
 268 }
 269
 270 static char *
 271 put_complex_filter( BerElement *ber, char *str, ber_tag_t tag, int not )
 272 {
 273         char    *next;
 274
 275         /*
 276          * We have (x(filter)...) with str sitting on
 277          * the x.  We have to find the paren matching
 278          * the one before the x and put the intervening
 279          * filters by calling put_filter_list().
 280          */
 281
 282         /* put explicit tag */
 283         if ( ber_printf( ber, "t{" /*"}"*/, tag ) == -1 ) {
 284                 return NULL;
 285         }
 286
 287         str++;
 288         if ( (next = find_right_paren( str )) == NULL ) {
 289                 return NULL;
 290         }
 291
 292         *next = '\0';
 293         if ( put_filter_list( ber, str, tag ) == -1 ) {
 294                 return NULL;
 295         }
 296
 297         /* close the '(' */
 298         *next++ = ')';
 299
 300         /* flush explicit tagged thang */
 301         if ( ber_printf( ber, /*"{"*/ "N}" ) == -1 ) {
 302                 return NULL;
 303         }
 304
 305         return next;
 306 }
 307
 308 int
 309 ldap_int_put_filter( BerElement *ber, const char *str_in )
 310 {
 311         int rc;
 312         char    *freeme;
 313         char    *str;
 314         char    *next;
 315         int     parens, balance, escape;
 316
 317         /*
 318          * A Filter looks like this:
 319          *      Filter ::= CHOICE {
 320          *              and             [0]     SET OF Filter,
 321          *              or              [1]     SET OF Filter,
 322          *              not             [2]     Filter,
 323          *              equalityMatch   [3]     AttributeValueAssertion,
 324          *              substrings      [4]     SubstringFilter,
 325          *              greaterOrEqual  [5]     AttributeValueAssertion,
 326          *              lessOrEqual     [6]     AttributeValueAssertion,
 327          *              present         [7]     AttributeType,
 328          *              approxMatch     [8]     AttributeValueAssertion,
 329          *                              extensibleMatch [9]             MatchingRuleAssertion -- LDAPv3
 330          *      }
 331          *
 332          *      SubstringFilter ::= SEQUENCE {
 333          *              type               AttributeType,
 334          *              SEQUENCE OF CHOICE {
 335          *                      initial          [0] IA5String,
 336          *                      any              [1] IA5String,
 337          *                      final            [2] IA5String
 338          *              }
 339          *      }
 340          *
 341          *              MatchingRuleAssertion ::= SEQUENCE {    -- LDAPv3
 342          *                      matchingRule    [1] MatchingRuleId OPTIONAL,
 343          *                      type            [2] AttributeDescription OPTIONAL,
 344          *                      matchValue      [3] AssertionValue,
 345          *                      dnAttributes    [4] BOOLEAN DEFAULT FALSE }
 346          *
 347          * Note: tags in a choice are always explicit
 348          */
 349
 350         Debug( LDAP_DEBUG_TRACE, "put_filter: \"%s\"\n", str_in, 0, 0 );
 351
 352         freeme = LDAP_STRDUP( str_in );
 353         if( freeme == NULL ) return LDAP_NO_MEMORY;
 354         str = freeme;
 355
 356         parens = 0;
 357         while ( *str ) {
 358                 switch ( *str ) {
 359                 case '(': /*')'*/
 360                         str++;
 361                         parens++;
 362
 363                         /* skip spaces */
 364                         while( LDAP_SPACE( *str ) ) str++;
 365
 366                         switch ( *str ) {
 367                         case '&':
 368                                 Debug( LDAP_DEBUG_TRACE, "put_filter: AND\n",
 369                                     0, 0, 0 );
 370
 371                                 str = put_complex_filter( ber, str,
 372                                     LDAP_FILTER_AND, 0 );
 373                                 if( str == NULL ) {
 374                                         rc = -1;
 375                                         goto done;
 376                                 }
 377
 378                                 parens--;
 379                                 break;
 380
 381                         case '|':
 382                                 Debug( LDAP_DEBUG_TRACE, "put_filter: OR\n",
 383                                     0, 0, 0 );
 384
 385                                 str = put_complex_filter( ber, str,
 386                                     LDAP_FILTER_OR, 0 );
 387                                 if( str == NULL ) {
 388                                         rc = -1;
 389                                         goto done;
 390                                 }
 391
 392                                 parens--;
 393                                 break;
 394
 395                         case '!':
 396                                 Debug( LDAP_DEBUG_TRACE, "put_filter: NOT\n",
 397                                     0, 0, 0 );
 398
 399                                 str = put_complex_filter( ber, str,
 400                                     LDAP_FILTER_NOT, 0 );
 401                                 if( str == NULL ) {
 402                                         rc = -1;
 403                                         goto done;
 404                                 }
 405
 406                                 parens--;
 407                                 break;
 408
 409                         default:
 410                                 Debug( LDAP_DEBUG_TRACE, "put_filter: simple\n",
 411                                     0, 0, 0 );
 412
 413                                 balance = 1;
 414                                 escape = 0;
 415                                 next = str;
 416
 417                                 while ( *next && balance ) {
 418                                         if ( escape == 0 ) {
 419                                                 if ( *next == '(' ) {
 420                                                         balance++;
 421                                                 } else if ( *next == ')' ) {
 422                                                         balance--;
 423                                                 }
 424                                         }
 425
 426                                         if ( *next == '\\' && ! escape ) {
 427                                                 escape = 1;
 428                                         } else {
 429                                                 escape = 0;
 430                                         }
 431
 432                                         if ( balance ) next++;
 433                                 }
 434
 435                                 if ( balance != 0 ) {
 436                                         rc = -1;
 437                                         goto done;
 438                                 }
 439
 440                                 *next = '\0';
 441
 442                                 if ( put_simple_filter( ber, str ) == -1 ) {
 443                                         rc = -1;
 444                                         goto done;
 445                                 }
 446
 447                                 *next++ = /*'('*/ ')';
 448
 449                                 str = next;
 450                                 parens--;
 451                                 break;
 452                         }
 453                         break;
 454
 455                 case /*'('*/ ')':
 456                         Debug( LDAP_DEBUG_TRACE, "put_filter: end\n",
 457                                 0, 0, 0 );
 458                         if ( ber_printf( ber, /*"["*/ "]" ) == -1 ) {
 459                                 rc = -1;
 460                                 goto done;
 461                         }
 462                         str++;
 463                         parens--;
 464                         break;
 465
 466                 case ' ':
 467                         str++;
 468                         break;
 469
 470                 default:        /* assume it's a simple type=value filter */
 471                         Debug( LDAP_DEBUG_TRACE, "put_filter: default\n",
 472                                 0, 0, 0 );
 473                         next = strchr( str, '\0' );
 474                         if ( put_simple_filter( ber, str ) == -1 ) {
 475                                 rc = -1;
 476                                 goto done;
 477                         }
 478                         str = next;
 479                         break;
 480                 }
 481         }
 482
 483         rc = parens ? -1 : 0;
 484
 485 done:
 486         LDAP_FREE( freeme );
 487         return rc;
 488 }
 489
 490 /*
 491  * Put a list of filters like this "(filter1)(filter2)..."
 492  */
 493
 494 static int
 495 put_filter_list( BerElement *ber, char *str, ber_tag_t tag )
 496 {
 497         char    *next = NULL;
 498         char    save;
 499
 500         Debug( LDAP_DEBUG_TRACE, "put_filter_list \"%s\"\n",
 501                 str, 0, 0 );
 502
 503         while ( *str ) {
 504                 while ( *str && LDAP_SPACE( (unsigned char) *str ) ) {
 505                         str++;
 506                 }
 507                 if ( *str == '\0' ) break;
 508
 509                 if ( (next = find_right_paren( str + 1 )) == NULL ) {
 510                         return -1;
 511                 }
 512                 save = *++next;
 513
 514                 /* now we have "(filter)" with str pointing to it */
 515                 *next = '\0';
 516                 if ( ldap_int_put_filter( ber, str ) == -1 ) return -1;
 517                 *next = save;
 518                 str = next;
 519
 520                 if( tag == LDAP_FILTER_NOT ) break;
 521         }
 522
 523         if( tag == LDAP_FILTER_NOT && ( next == NULL || *str )) {
 524                 return -1;
 525         }
 526
 527         return 0;
 528 }
 529
 530 static int
 531 put_simple_filter(
 532         BerElement *ber,
 533         char *str )
 534 {
 535         char            *s;
 536         char            *value;
 537         ber_tag_t       ftype;
 538         int             rc = -1;
 539
 540         Debug( LDAP_DEBUG_TRACE, "put_simple_filter: \"%s\"\n",
 541                 str, 0, 0 );
 542
 543         str = LDAP_STRDUP( str );
 544         if( str == NULL ) return -1;
 545
 546         if ( (s = strchr( str, '=' )) == NULL ) {
 547                 goto done;
 548         }
 549
 550         value = s + 1;
 551         *s-- = '\0';
 552
 553         switch ( *s ) {
 554         case '<':
 555                 ftype = LDAP_FILTER_LE;
 556                 *s = '\0';
 557                 break;
 558
 559         case '>':
 560                 ftype = LDAP_FILTER_GE;
 561                 *s = '\0';
 562                 break;
 563
 564         case '~':
 565                 ftype = LDAP_FILTER_APPROX;
 566                 *s = '\0';
 567                 break;
 568
 569         case ':':
 570                 /* RFC2254 extensible filters are off the form:
 571                  *              type [:dn] [:rule] := value
 572                  * or   [:dn]:rule := value
 573                  */
 574                 ftype = LDAP_FILTER_EXT;
 575                 *s = '\0';
 576
 577                 {
 578                         char *dn = strchr( str, ':' );
 579                         char *rule = NULL;
 580
 581                         if( dn != NULL ) {
 582                                 *dn++ = '\0';
 583                                 rule = strchr( dn, ':' );
 584
 585                                 if( rule == NULL ) {
 586                                         /* one colon */
 587                                         if ( strcmp(dn, "dn") == 0 ) {
 588                                                 /* must have attribute */
 589                                                 if( !ldap_is_desc( str ) ) {
 590                                                         goto done;
 591                                                 }
 592
 593                                                 rule = "";
 594
 595                                         } else {
 596                                           rule = dn;
 597                                           dn = NULL;
 598                                         }
 599
 600                                 } else {
 601                                         /* two colons */
 602                                         *rule++ = '\0';
 603
 604                                         if ( strcmp(dn, "dn") != 0 ) {
 605                                                 /* must have "dn" */
 606                                                 goto done;
 607                                         }
 608                                 }
 609
 610                         }
 611
 612                         if ( *str == '\0' && ( !rule || *rule == '\0' ) ) {
 613                                 /* must have either type or rule */
 614                                 goto done;
 615                         }
 616
 617                         if ( *str != '\0' && !ldap_is_desc( str ) ) {
 618                                 goto done;
 619                         }
 620
 621                         if ( rule && *rule != '\0' && !ldap_is_oid( rule ) ) {
 622                                 goto done;
 623                         }
 624
 625                         rc = ber_printf( ber, "t{" /*"}"*/, ftype );
 626
 627                         if( rc != -1 && rule && *rule != '\0' ) {
 628                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_OID, rule );
 629                         }
 630
 631                         if( rc != -1 && *str != '\0' ) {
 632                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_TYPE, str );
 633                         }
 634
 635                         if( rc != -1 ) {
 636                                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 637
 638                                 if( len >= 0 ) {
 639                                         rc = ber_printf( ber, "to",
 640                                                 LDAP_FILTER_EXT_VALUE, value, len );
 641                                 } else {
 642                                         rc = -1;
 643                                 }
 644                         }
 645
 646                         if( rc != -1 && dn ) {
 647                                 rc = ber_printf( ber, "tb",
 648                                         LDAP_FILTER_EXT_DNATTRS, (ber_int_t) 1 );
 649                         }
 650
 651                         if( rc != -1 ) {
 652                                 rc = ber_printf( ber, /*"{"*/ "N}" );
 653                         }
 654                 }
 655                 goto done;
 656
 657         default:
 658                 if( !ldap_is_desc( str ) ) {
 659                         goto done;
 660
 661                 } else {
 662                         char *nextstar = ldap_pvt_find_wildcard( value );
 663
 664                         if ( nextstar == NULL ) {
 665                                 goto done;
 666
 667                         } else if ( *nextstar == '\0' ) {
 668                                 ftype = LDAP_FILTER_EQUALITY;
 669
 670                         } else if ( strcmp( value, "*" ) == 0 ) {
 671                                 ftype = LDAP_FILTER_PRESENT;
 672
 673                         } else {
 674                                 rc = put_substring_filter( ber, str, value );
 675                                 goto done;
 676                         }
 677                 } break;
 678         }
 679
 680         if( !ldap_is_desc( str ) ) goto done;
 681
 682         if ( ftype == LDAP_FILTER_PRESENT ) {
 683                 rc = ber_printf( ber, "ts", ftype, str );
 684
 685         } else {
 686                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 687
 688                 if( len >= 0 ) {
 689                         rc = ber_printf( ber, "t{soN}",
 690                                 ftype, str, value, len );
 691                 }
 692         }
 693
 694 done:
 695         if( rc != -1 ) rc = 0;
 696         LDAP_FREE( str );
 697         return rc;
 698 }
 699
 700 static int
 701 put_substring_filter( BerElement *ber, char *type, char *val )
 702 {
 703         char *nextstar;
 704         int gotstar = 0;
 705         ber_tag_t       ftype = LDAP_FILTER_SUBSTRINGS;
 706
 707         Debug( LDAP_DEBUG_TRACE, "put_substring_filter \"%s=%s\"\n",
 708                 type, val, 0 );
 709
 710         if ( ber_printf( ber, "t{s{" /*"}}"*/, ftype, type ) == -1 ) {
 711                 return -1;
 712         }
 713
 714         for( ; *val; val=nextstar ) {
 715                 nextstar = ldap_pvt_find_wildcard( val );
 716
 717                 if ( nextstar == NULL ) {
 718                         return -1;
 719                 }
 720
 721                 if ( *nextstar == '\0' ) {
 722                         ftype = LDAP_SUBSTRING_FINAL;
 723                 } else if ( gotstar++ == 0 ) {
 724                         ftype = LDAP_SUBSTRING_INITIAL;
 725                 } else {
 726                         ftype = LDAP_SUBSTRING_ANY;
 727                 }
 728
 729                 *nextstar++ = '\0';
 730
 731                 if ( *val != '\0' || ftype == LDAP_SUBSTRING_ANY ) {
 732                         ber_slen_t len = ldap_pvt_filter_value_unescape( val );
 733
 734                         if ( len < 0  ) {
 735                                 return -1;
 736                         }
 737
 738                         if ( ber_printf( ber, "to", ftype, val, len ) == -1 ) {
 739                                 return -1;
 740                         }
 741                 }
 742         }
 743
 744         if ( ber_printf( ber, /*"{{"*/ "N}N}" ) == -1 ) {
 745                 return -1;
 746         }
 747
 748         return 0;
 749 }