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

   1 /* $OpenLDAP$ */
   2 /*
   3  * Copyright 1998-2002 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                 case '*':
 225                         return -1;
 226
 227                 case '\\':
 228                         /* escape */
 229                         v++;
 230
 231                         if ( fval[v] == '\0' ) {
 232                                 /* escape at end of string */
 233                                 return -1;
 234                         }
 235
 236                         if (( v1 = hex2value( fval[v] )) >= 0 ) {
 237                                 /* LDAPv3 escape */
 238                                 if (( v2 = hex2value( fval[v+1] )) < 0 ) {
 239                                         /* must be two digit code */
 240                                         return -1;
 241                                 }
 242
 243                                 fval[r++] = v1 * 16 + v2;
 244                                 v++;
 245
 246                         } else {
 247                                 /* LDAPv2 escape */
 248                                 switch( fval[v] ) {
 249                                 case '(':
 250                                 case ')':
 251                                 case '*':
 252                                 case '\\':
 253                                         fval[r++] = fval[v];
 254                                         break;
 255                                 default:
 256                                         /* illegal escape */
 257                                         return -1;
 258                                 }
 259                         }
 260                         break;
 261
 262                 default:
 263                         fval[r++] = fval[v];
 264                 }
 265         }
 266
 267         fval[r] = '\0';
 268         return r;
 269 }
 270
 271 static char *
 272 put_complex_filter( BerElement *ber, char *str, ber_tag_t tag, int not )
 273 {
 274         char    *next;
 275
 276         /*
 277          * We have (x(filter)...) with str sitting on
 278          * the x.  We have to find the paren matching
 279          * the one before the x and put the intervening
 280          * filters by calling put_filter_list().
 281          */
 282
 283         /* put explicit tag */
 284         if ( ber_printf( ber, "t{" /*"}"*/, tag ) == -1 ) {
 285                 return NULL;
 286         }
 287
 288         str++;
 289         if ( (next = find_right_paren( str )) == NULL ) {
 290                 return NULL;
 291         }
 292
 293         *next = '\0';
 294         if ( put_filter_list( ber, str, tag ) == -1 ) {
 295                 return NULL;
 296         }
 297
 298         /* close the '(' */
 299         *next++ = ')';
 300
 301         /* flush explicit tagged thang */
 302         if ( ber_printf( ber, /*"{"*/ "N}" ) == -1 ) {
 303                 return NULL;
 304         }
 305
 306         return next;
 307 }
 308
 309 int
 310 ldap_pvt_put_filter( BerElement *ber, const char *str_in )
 311 {
 312         int rc;
 313         char    *freeme;
 314         char    *str;
 315         char    *next;
 316         int     parens, balance, escape;
 317
 318         /*
 319          * A Filter looks like this:
 320          *      Filter ::= CHOICE {
 321          *              and             [0]     SET OF Filter,
 322          *              or              [1]     SET OF Filter,
 323          *              not             [2]     Filter,
 324          *              equalityMatch   [3]     AttributeValueAssertion,
 325          *              substrings      [4]     SubstringFilter,
 326          *              greaterOrEqual  [5]     AttributeValueAssertion,
 327          *              lessOrEqual     [6]     AttributeValueAssertion,
 328          *              present         [7]     AttributeType,
 329          *              approxMatch     [8]     AttributeValueAssertion,
 330          *                              extensibleMatch [9]             MatchingRuleAssertion -- LDAPv3
 331          *      }
 332          *
 333          *      SubstringFilter ::= SEQUENCE {
 334          *              type               AttributeType,
 335          *              SEQUENCE OF CHOICE {
 336          *                      initial          [0] IA5String,
 337          *                      any              [1] IA5String,
 338          *                      final            [2] IA5String
 339          *              }
 340          *      }
 341          *
 342          *              MatchingRuleAssertion ::= SEQUENCE {    -- LDAPv3
 343          *                      matchingRule    [1] MatchingRuleId OPTIONAL,
 344          *                      type            [2] AttributeDescription OPTIONAL,
 345          *                      matchValue      [3] AssertionValue,
 346          *                      dnAttributes    [4] BOOLEAN DEFAULT FALSE }
 347          *
 348          * Note: tags in a choice are always explicit
 349          */
 350
 351 #ifdef NEW_LOGGING
 352         LDAP_LOG (( "filter", LDAP_LEVEL_ARGS, "ldap_pvt_put_filter: \"%s\"\n",
 353                 str_in ));
 354 #else
 355         Debug( LDAP_DEBUG_TRACE, "put_filter: \"%s\"\n", str_in, 0, 0 );
 356 #endif
 357
 358         freeme = LDAP_STRDUP( str_in );
 359         if( freeme == NULL ) return LDAP_NO_MEMORY;
 360         str = freeme;
 361
 362         parens = 0;
 363         while ( *str ) {
 364                 switch ( *str ) {
 365                 case '(': /*')'*/
 366                         str++;
 367                         parens++;
 368
 369                         /* skip spaces */
 370                         while( LDAP_SPACE( *str ) ) str++;
 371
 372                         switch ( *str ) {
 373                         case '&':
 374 #ifdef NEW_LOGGING
 375                                 LDAP_LOG (( "filter", LDAP_LEVEL_DETAIL1,
 376                                         "ldap_pvt_put_filter: AND\n" ));
 377 #else
 378                                 Debug( LDAP_DEBUG_TRACE, "put_filter: AND\n",
 379                                     0, 0, 0 );
 380 #endif
 381
 382                                 str = put_complex_filter( ber, str,
 383                                     LDAP_FILTER_AND, 0 );
 384                                 if( str == NULL ) {
 385                                         rc = -1;
 386                                         goto done;
 387                                 }
 388
 389                                 parens--;
 390                                 break;
 391
 392                         case '|':
 393 #ifdef NEW_LOGGING
 394                                 LDAP_LOG (( "filter", LDAP_LEVEL_DETAIL1,
 395                                         "ldap_pvt_put_filter: OR\n" ));
 396 #else
 397                                 Debug( LDAP_DEBUG_TRACE, "put_filter: OR\n",
 398                                     0, 0, 0 );
 399 #endif
 400
 401                                 str = put_complex_filter( ber, str,
 402                                     LDAP_FILTER_OR, 0 );
 403                                 if( str == NULL ) {
 404                                         rc = -1;
 405                                         goto done;
 406                                 }
 407
 408                                 parens--;
 409                                 break;
 410
 411                         case '!':
 412 #ifdef NEW_LOGGING
 413                                 LDAP_LOG (( "filter", LDAP_LEVEL_DETAIL1,
 414                                         "ldap_pvt_put_filter: NOT\n" ));
 415 #else
 416                                 Debug( LDAP_DEBUG_TRACE, "put_filter: NOT\n",
 417                                     0, 0, 0 );
 418 #endif
 419
 420                                 str = put_complex_filter( ber, str,
 421                                     LDAP_FILTER_NOT, 0 );
 422                                 if( str == NULL ) {
 423                                         rc = -1;
 424                                         goto done;
 425                                 }
 426
 427                                 parens--;
 428                                 break;
 429
 430                         default:
 431 #ifdef NEW_LOGGING
 432                                 LDAP_LOG (( "filter", LDAP_LEVEL_DETAIL1,
 433                                         "ldap_pvt_put_filter: simple\n" ));
 434 #else
 435                                 Debug( LDAP_DEBUG_TRACE, "put_filter: simple\n",
 436                                     0, 0, 0 );
 437 #endif
 438
 439                                 balance = 1;
 440                                 escape = 0;
 441                                 next = str;
 442
 443                                 while ( *next && balance ) {
 444                                         if ( escape == 0 ) {
 445                                                 if ( *next == '(' ) {
 446                                                         balance++;
 447                                                 } else if ( *next == ')' ) {
 448                                                         balance--;
 449                                                 }
 450                                         }
 451
 452                                         if ( *next == '\\' && ! escape ) {
 453                                                 escape = 1;
 454                                         } else {
 455                                                 escape = 0;
 456                                         }
 457
 458                                         if ( balance ) next++;
 459                                 }
 460
 461                                 if ( balance != 0 ) {
 462                                         rc = -1;
 463                                         goto done;
 464                                 }
 465
 466                                 *next = '\0';
 467
 468                                 if ( put_simple_filter( ber, str ) == -1 ) {
 469                                         rc = -1;
 470                                         goto done;
 471                                 }
 472
 473                                 *next++ = /*'('*/ ')';
 474
 475                                 str = next;
 476                                 parens--;
 477                                 break;
 478                         }
 479                         break;
 480
 481                 case /*'('*/ ')':
 482 #ifdef NEW_LOGGING
 483                         LDAP_LOG (( "filter", LDAP_LEVEL_DETAIL1,
 484                                 "ldap_pvt_put_filter: end\n" ));
 485 #else
 486                         Debug( LDAP_DEBUG_TRACE, "put_filter: end\n",
 487                                 0, 0, 0 );
 488 #endif
 489                         if ( ber_printf( ber, /*"["*/ "]" ) == -1 ) {
 490                                 rc = -1;
 491                                 goto done;
 492                         }
 493                         str++;
 494                         parens--;
 495                         break;
 496
 497                 case ' ':
 498                         str++;
 499                         break;
 500
 501                 default:        /* assume it's a simple type=value filter */
 502 #ifdef NEW_LOGGING
 503                         LDAP_LOG (( "filter", LDAP_LEVEL_DETAIL1,
 504                                 "ldap_pvt_put_filter: default\n" ));
 505 #else
 506                         Debug( LDAP_DEBUG_TRACE, "put_filter: default\n",
 507                                 0, 0, 0 );
 508 #endif
 509                         next = strchr( str, '\0' );
 510                         if ( put_simple_filter( ber, str ) == -1 ) {
 511                                 rc = -1;
 512                                 goto done;
 513                         }
 514                         str = next;
 515                         break;
 516                 }
 517         }
 518
 519         rc = parens ? -1 : 0;
 520
 521 done:
 522         LDAP_FREE( freeme );
 523         return rc;
 524 }
 525
 526 /*
 527  * Put a list of filters like this "(filter1)(filter2)..."
 528  */
 529
 530 static int
 531 put_filter_list( BerElement *ber, char *str, ber_tag_t tag )
 532 {
 533         char    *next = NULL;
 534         char    save;
 535
 536 #ifdef NEW_LOGGING
 537         LDAP_LOG (( "filter", LDAP_LEVEL_ARGS,
 538                                 "put_filter_list \"%s\"\n", str ));
 539 #else
 540         Debug( LDAP_DEBUG_TRACE, "put_filter_list \"%s\"\n",
 541                 str, 0, 0 );
 542 #endif
 543
 544         while ( *str ) {
 545                 while ( *str && LDAP_SPACE( (unsigned char) *str ) ) {
 546                         str++;
 547                 }
 548                 if ( *str == '\0' ) break;
 549
 550                 if ( (next = find_right_paren( str + 1 )) == NULL ) {
 551                         return -1;
 552                 }
 553                 save = *++next;
 554
 555                 /* now we have "(filter)" with str pointing to it */
 556                 *next = '\0';
 557                 if ( ldap_pvt_put_filter( ber, str ) == -1 ) return -1;
 558                 *next = save;
 559                 str = next;
 560
 561                 if( tag == LDAP_FILTER_NOT ) break;
 562         }
 563
 564         if( tag == LDAP_FILTER_NOT && ( next == NULL || *str )) {
 565                 return -1;
 566         }
 567
 568         return 0;
 569 }
 570
 571 static int
 572 put_simple_filter(
 573         BerElement *ber,
 574         char *str )
 575 {
 576         char            *s;
 577         char            *value;
 578         ber_tag_t       ftype;
 579         int             rc = -1;
 580
 581 #ifdef NEW_LOGGING
 582         LDAP_LOG (( "filter", LDAP_LEVEL_ARGS,
 583                                 "put_simple_filter: \"%s\"\n", str ));
 584 #else
 585         Debug( LDAP_DEBUG_TRACE, "put_simple_filter: \"%s\"\n",
 586                 str, 0, 0 );
 587 #endif
 588
 589         str = LDAP_STRDUP( str );
 590         if( str == NULL ) return -1;
 591
 592         if ( (s = strchr( str, '=' )) == NULL ) {
 593                 goto done;
 594         }
 595
 596         value = s + 1;
 597         *s-- = '\0';
 598
 599         switch ( *s ) {
 600         case '<':
 601                 ftype = LDAP_FILTER_LE;
 602                 *s = '\0';
 603                 break;
 604
 605         case '>':
 606                 ftype = LDAP_FILTER_GE;
 607                 *s = '\0';
 608                 break;
 609
 610         case '~':
 611                 ftype = LDAP_FILTER_APPROX;
 612                 *s = '\0';
 613                 break;
 614
 615         case ':':
 616                 /* RFC2254 extensible filters are off the form:
 617                  *              type [:dn] [:rule] := value
 618                  * or   [:dn]:rule := value
 619                  */
 620                 ftype = LDAP_FILTER_EXT;
 621                 *s = '\0';
 622
 623                 {
 624                         char *dn = strchr( str, ':' );
 625                         char *rule = NULL;
 626
 627                         if( dn != NULL ) {
 628                                 *dn++ = '\0';
 629                                 rule = strchr( dn, ':' );
 630
 631                                 if( rule == NULL ) {
 632                                         /* one colon */
 633                                         if ( strcmp(dn, "dn") == 0 ) {
 634                                                 /* must have attribute */
 635                                                 if( !ldap_is_desc( str ) ) {
 636                                                         goto done;
 637                                                 }
 638
 639                                                 rule = "";
 640
 641                                         } else {
 642                                           rule = dn;
 643                                           dn = NULL;
 644                                         }
 645
 646                                 } else {
 647                                         /* two colons */
 648                                         *rule++ = '\0';
 649
 650                                         if ( strcmp(dn, "dn") != 0 ) {
 651                                                 /* must have "dn" */
 652                                                 goto done;
 653                                         }
 654                                 }
 655
 656                         }
 657
 658                         if ( *str == '\0' && ( !rule || *rule == '\0' ) ) {
 659                                 /* must have either type or rule */
 660                                 goto done;
 661                         }
 662
 663                         if ( *str != '\0' && !ldap_is_desc( str ) ) {
 664                                 goto done;
 665                         }
 666
 667                         if ( rule && *rule != '\0' && !ldap_is_oid( rule ) ) {
 668                                 goto done;
 669                         }
 670
 671                         rc = ber_printf( ber, "t{" /*"}"*/, ftype );
 672
 673                         if( rc != -1 && rule && *rule != '\0' ) {
 674                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_OID, rule );
 675                         }
 676
 677                         if( rc != -1 && *str != '\0' ) {
 678                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_TYPE, str );
 679                         }
 680
 681                         if( rc != -1 ) {
 682                                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 683
 684                                 if( len >= 0 ) {
 685                                         rc = ber_printf( ber, "to",
 686                                                 LDAP_FILTER_EXT_VALUE, value, len );
 687                                 } else {
 688                                         rc = -1;
 689                                 }
 690                         }
 691
 692                         if( rc != -1 && dn ) {
 693                                 rc = ber_printf( ber, "tb",
 694                                         LDAP_FILTER_EXT_DNATTRS, (ber_int_t) 1 );
 695                         }
 696
 697                         if( rc != -1 ) {
 698                                 rc = ber_printf( ber, /*"{"*/ "N}" );
 699                         }
 700                 }
 701                 goto done;
 702
 703         default:
 704                 if( !ldap_is_desc( str ) ) {
 705                         goto done;
 706
 707                 } else {
 708                         char *nextstar = ldap_pvt_find_wildcard( value );
 709
 710                         if ( nextstar == NULL ) {
 711                                 goto done;
 712
 713                         } else if ( *nextstar == '\0' ) {
 714                                 ftype = LDAP_FILTER_EQUALITY;
 715
 716                         } else if ( strcmp( value, "*" ) == 0 ) {
 717                                 ftype = LDAP_FILTER_PRESENT;
 718
 719                         } else {
 720                                 rc = put_substring_filter( ber, str, value );
 721                                 goto done;
 722                         }
 723                 } break;
 724         }
 725
 726         if( !ldap_is_desc( str ) ) goto done;
 727
 728         if ( ftype == LDAP_FILTER_PRESENT ) {
 729                 rc = ber_printf( ber, "ts", ftype, str );
 730
 731         } else {
 732                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 733
 734                 if( len >= 0 ) {
 735                         rc = ber_printf( ber, "t{soN}",
 736                                 ftype, str, value, len );
 737                 }
 738         }
 739
 740 done:
 741         if( rc != -1 ) rc = 0;
 742         LDAP_FREE( str );
 743         return rc;
 744 }
 745
 746 static int
 747 put_substring_filter( BerElement *ber, char *type, char *val )
 748 {
 749         char *nextstar;
 750         int gotstar = 0;
 751         ber_tag_t       ftype = LDAP_FILTER_SUBSTRINGS;
 752
 753 #ifdef NEW_LOGGING
 754         LDAP_LOG (( "filter", LDAP_LEVEL_ARGS,
 755                                 "put_substring_filter \"%s=%s\"\n", type, val ));
 756 #else
 757         Debug( LDAP_DEBUG_TRACE, "put_substring_filter \"%s=%s\"\n",
 758                 type, val, 0 );
 759 #endif
 760
 761         if ( ber_printf( ber, "t{s{" /*"}}"*/, ftype, type ) == -1 ) {
 762                 return -1;
 763         }
 764
 765         for( ; *val; val=nextstar ) {
 766                 nextstar = ldap_pvt_find_wildcard( val );
 767
 768                 if ( nextstar == NULL ) {
 769                         return -1;
 770                 }
 771
 772                 if ( *nextstar == '\0' ) {
 773                         ftype = LDAP_SUBSTRING_FINAL;
 774                 } else {
 775                         *nextstar++ = '\0';
 776                         if ( gotstar++ == 0 ) {
 777                                 ftype = LDAP_SUBSTRING_INITIAL;
 778                         } else {
 779                                 ftype = LDAP_SUBSTRING_ANY;
 780                         }
 781                 }
 782
 783                 if ( *val != '\0' || ftype == LDAP_SUBSTRING_ANY ) {
 784                         ber_slen_t len = ldap_pvt_filter_value_unescape( val );
 785
 786                         if ( len < 0  ) {
 787                                 return -1;
 788                         }
 789
 790                         if ( ber_printf( ber, "to", ftype, val, len ) == -1 ) {
 791                                 return -1;
 792                         }
 793                 }
 794         }
 795
 796         if ( ber_printf( ber, /*"{{"*/ "N}N}" ) == -1 ) {
 797                 return -1;
 798         }
 799
 800         return 0;
 801 }