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