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_int_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         Debug( LDAP_DEBUG_TRACE, "put_filter: \"%s\"\n", str_in, 0, 0 );
 352
 353         freeme = LDAP_STRDUP( str_in );
 354         if( freeme == NULL ) return LDAP_NO_MEMORY;
 355         str = freeme;
 356
 357         parens = 0;
 358         while ( *str ) {
 359                 switch ( *str ) {
 360                 case '(': /*')'*/
 361                         str++;
 362                         parens++;
 363
 364                         /* skip spaces */
 365                         while( LDAP_SPACE( *str ) ) str++;
 366
 367                         switch ( *str ) {
 368                         case '&':
 369                                 Debug( LDAP_DEBUG_TRACE, "put_filter: AND\n",
 370                                     0, 0, 0 );
 371
 372                                 str = put_complex_filter( ber, str,
 373                                     LDAP_FILTER_AND, 0 );
 374                                 if( str == NULL ) {
 375                                         rc = -1;
 376                                         goto done;
 377                                 }
 378
 379                                 parens--;
 380                                 break;
 381
 382                         case '|':
 383                                 Debug( LDAP_DEBUG_TRACE, "put_filter: OR\n",
 384                                     0, 0, 0 );
 385
 386                                 str = put_complex_filter( ber, str,
 387                                     LDAP_FILTER_OR, 0 );
 388                                 if( str == NULL ) {
 389                                         rc = -1;
 390                                         goto done;
 391                                 }
 392
 393                                 parens--;
 394                                 break;
 395
 396                         case '!':
 397                                 Debug( LDAP_DEBUG_TRACE, "put_filter: NOT\n",
 398                                     0, 0, 0 );
 399
 400                                 str = put_complex_filter( ber, str,
 401                                     LDAP_FILTER_NOT, 0 );
 402                                 if( str == NULL ) {
 403                                         rc = -1;
 404                                         goto done;
 405                                 }
 406
 407                                 parens--;
 408                                 break;
 409
 410                         default:
 411                                 Debug( LDAP_DEBUG_TRACE, "put_filter: simple\n",
 412                                     0, 0, 0 );
 413
 414                                 balance = 1;
 415                                 escape = 0;
 416                                 next = str;
 417
 418                                 while ( *next && balance ) {
 419                                         if ( escape == 0 ) {
 420                                                 if ( *next == '(' ) {
 421                                                         balance++;
 422                                                 } else if ( *next == ')' ) {
 423                                                         balance--;
 424                                                 }
 425                                         }
 426
 427                                         if ( *next == '\\' && ! escape ) {
 428                                                 escape = 1;
 429                                         } else {
 430                                                 escape = 0;
 431                                         }
 432
 433                                         if ( balance ) next++;
 434                                 }
 435
 436                                 if ( balance != 0 ) {
 437                                         rc = -1;
 438                                         goto done;
 439                                 }
 440
 441                                 *next = '\0';
 442
 443                                 if ( put_simple_filter( ber, str ) == -1 ) {
 444                                         rc = -1;
 445                                         goto done;
 446                                 }
 447
 448                                 *next++ = /*'('*/ ')';
 449
 450                                 str = next;
 451                                 parens--;
 452                                 break;
 453                         }
 454                         break;
 455
 456                 case /*'('*/ ')':
 457                         Debug( LDAP_DEBUG_TRACE, "put_filter: end\n",
 458                                 0, 0, 0 );
 459                         if ( ber_printf( ber, /*"["*/ "]" ) == -1 ) {
 460                                 rc = -1;
 461                                 goto done;
 462                         }
 463                         str++;
 464                         parens--;
 465                         break;
 466
 467                 case ' ':
 468                         str++;
 469                         break;
 470
 471                 default:        /* assume it's a simple type=value filter */
 472                         Debug( LDAP_DEBUG_TRACE, "put_filter: default\n",
 473                                 0, 0, 0 );
 474                         next = strchr( str, '\0' );
 475                         if ( put_simple_filter( ber, str ) == -1 ) {
 476                                 rc = -1;
 477                                 goto done;
 478                         }
 479                         str = next;
 480                         break;
 481                 }
 482         }
 483
 484         rc = parens ? -1 : 0;
 485
 486 done:
 487         LDAP_FREE( freeme );
 488         return rc;
 489 }
 490
 491 /*
 492  * Put a list of filters like this "(filter1)(filter2)..."
 493  */
 494
 495 static int
 496 put_filter_list( BerElement *ber, char *str, ber_tag_t tag )
 497 {
 498         char    *next = NULL;
 499         char    save;
 500
 501         Debug( LDAP_DEBUG_TRACE, "put_filter_list \"%s\"\n",
 502                 str, 0, 0 );
 503
 504         while ( *str ) {
 505                 while ( *str && LDAP_SPACE( (unsigned char) *str ) ) {
 506                         str++;
 507                 }
 508                 if ( *str == '\0' ) break;
 509
 510                 if ( (next = find_right_paren( str + 1 )) == NULL ) {
 511                         return -1;
 512                 }
 513                 save = *++next;
 514
 515                 /* now we have "(filter)" with str pointing to it */
 516                 *next = '\0';
 517                 if ( ldap_int_put_filter( ber, str ) == -1 ) return -1;
 518                 *next = save;
 519                 str = next;
 520
 521                 if( tag == LDAP_FILTER_NOT ) break;
 522         }
 523
 524         if( tag == LDAP_FILTER_NOT && ( next == NULL || *str )) {
 525                 return -1;
 526         }
 527
 528         return 0;
 529 }
 530
 531 static int
 532 put_simple_filter(
 533         BerElement *ber,
 534         char *str )
 535 {
 536         char            *s;
 537         char            *value;
 538         ber_tag_t       ftype;
 539         int             rc = -1;
 540
 541         Debug( LDAP_DEBUG_TRACE, "put_simple_filter: \"%s\"\n",
 542                 str, 0, 0 );
 543
 544         str = LDAP_STRDUP( str );
 545         if( str == NULL ) return -1;
 546
 547         if ( (s = strchr( str, '=' )) == NULL ) {
 548                 goto done;
 549         }
 550
 551         value = s + 1;
 552         *s-- = '\0';
 553
 554         switch ( *s ) {
 555         case '<':
 556                 ftype = LDAP_FILTER_LE;
 557                 *s = '\0';
 558                 break;
 559
 560         case '>':
 561                 ftype = LDAP_FILTER_GE;
 562                 *s = '\0';
 563                 break;
 564
 565         case '~':
 566                 ftype = LDAP_FILTER_APPROX;
 567                 *s = '\0';
 568                 break;
 569
 570         case ':':
 571                 /* RFC2254 extensible filters are off the form:
 572                  *              type [:dn] [:rule] := value
 573                  * or   [:dn]:rule := value
 574                  */
 575                 ftype = LDAP_FILTER_EXT;
 576                 *s = '\0';
 577
 578                 {
 579                         char *dn = strchr( str, ':' );
 580                         char *rule = NULL;
 581
 582                         if( dn != NULL ) {
 583                                 *dn++ = '\0';
 584                                 rule = strchr( dn, ':' );
 585
 586                                 if( rule == NULL ) {
 587                                         /* one colon */
 588                                         if ( strcmp(dn, "dn") == 0 ) {
 589                                                 /* must have attribute */
 590                                                 if( !ldap_is_desc( str ) ) {
 591                                                         goto done;
 592                                                 }
 593
 594                                                 rule = "";
 595
 596                                         } else {
 597                                           rule = dn;
 598                                           dn = NULL;
 599                                         }
 600
 601                                 } else {
 602                                         /* two colons */
 603                                         *rule++ = '\0';
 604
 605                                         if ( strcmp(dn, "dn") != 0 ) {
 606                                                 /* must have "dn" */
 607                                                 goto done;
 608                                         }
 609                                 }
 610
 611                         }
 612
 613                         if ( *str == '\0' && ( !rule || *rule == '\0' ) ) {
 614                                 /* must have either type or rule */
 615                                 goto done;
 616                         }
 617
 618                         if ( *str != '\0' && !ldap_is_desc( str ) ) {
 619                                 goto done;
 620                         }
 621
 622                         if ( rule && *rule != '\0' && !ldap_is_oid( rule ) ) {
 623                                 goto done;
 624                         }
 625
 626                         rc = ber_printf( ber, "t{" /*"}"*/, ftype );
 627
 628                         if( rc != -1 && rule && *rule != '\0' ) {
 629                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_OID, rule );
 630                         }
 631
 632                         if( rc != -1 && *str != '\0' ) {
 633                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_TYPE, str );
 634                         }
 635
 636                         if( rc != -1 ) {
 637                                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 638
 639                                 if( len >= 0 ) {
 640                                         rc = ber_printf( ber, "to",
 641                                                 LDAP_FILTER_EXT_VALUE, value, len );
 642                                 } else {
 643                                         rc = -1;
 644                                 }
 645                         }
 646
 647                         if( rc != -1 && dn ) {
 648                                 rc = ber_printf( ber, "tb",
 649                                         LDAP_FILTER_EXT_DNATTRS, (ber_int_t) 1 );
 650                         }
 651
 652                         if( rc != -1 ) {
 653                                 rc = ber_printf( ber, /*"{"*/ "N}" );
 654                         }
 655                 }
 656                 goto done;
 657
 658         default:
 659                 if( !ldap_is_desc( str ) ) {
 660                         goto done;
 661
 662                 } else {
 663                         char *nextstar = ldap_pvt_find_wildcard( value );
 664
 665                         if ( nextstar == NULL ) {
 666                                 goto done;
 667
 668                         } else if ( *nextstar == '\0' ) {
 669                                 ftype = LDAP_FILTER_EQUALITY;
 670
 671                         } else if ( strcmp( value, "*" ) == 0 ) {
 672                                 ftype = LDAP_FILTER_PRESENT;
 673
 674                         } else {
 675                                 rc = put_substring_filter( ber, str, value );
 676                                 goto done;
 677                         }
 678                 } break;
 679         }
 680
 681         if( !ldap_is_desc( str ) ) goto done;
 682
 683         if ( ftype == LDAP_FILTER_PRESENT ) {
 684                 rc = ber_printf( ber, "ts", ftype, str );
 685
 686         } else {
 687                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 688
 689                 if( len >= 0 ) {
 690                         rc = ber_printf( ber, "t{soN}",
 691                                 ftype, str, value, len );
 692                 }
 693         }
 694
 695 done:
 696         if( rc != -1 ) rc = 0;
 697         LDAP_FREE( str );
 698         return rc;
 699 }
 700
 701 static int
 702 put_substring_filter( BerElement *ber, char *type, char *val )
 703 {
 704         char *nextstar;
 705         int gotstar = 0;
 706         ber_tag_t       ftype = LDAP_FILTER_SUBSTRINGS;
 707
 708         Debug( LDAP_DEBUG_TRACE, "put_substring_filter \"%s=%s\"\n",
 709                 type, val, 0 );
 710
 711         if ( ber_printf( ber, "t{s{" /*"}}"*/, ftype, type ) == -1 ) {
 712                 return -1;
 713         }
 714
 715         for( ; *val; val=nextstar ) {
 716                 nextstar = ldap_pvt_find_wildcard( val );
 717
 718                 if ( nextstar == NULL ) {
 719                         return -1;
 720                 }
 721
 722                 if ( *nextstar == '\0' ) {
 723                         ftype = LDAP_SUBSTRING_FINAL;
 724                 } else {
 725                         *nextstar++ = '\0';
 726                         if ( gotstar++ == 0 ) {
 727                                 ftype = LDAP_SUBSTRING_INITIAL;
 728                         } else {
 729                                 ftype = LDAP_SUBSTRING_ANY;
 730                         }
 731                 }
 732
 733                 if ( *val != '\0' || ftype == LDAP_SUBSTRING_ANY ) {
 734                         ber_slen_t len = ldap_pvt_filter_value_unescape( val );
 735
 736                         if ( len < 0  ) {
 737                                 return -1;
 738                         }
 739
 740                         if ( ber_printf( ber, "to", ftype, val, len ) == -1 ) {
 741                                 return -1;
 742                         }
 743                 }
 744         }
 745
 746         if ( ber_printf( ber, /*"{{"*/ "N}N}" ) == -1 ) {
 747                 return -1;
 748         }
 749
 750         return 0;
 751 }