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         str++;
 279         if ( (next = find_right_paren( str )) == NULL )
 280                 return( NULL );
 281
 282         *next = '\0';
 283         if ( put_filter_list( ber, str, tag ) == -1 )
 284                 return( NULL );
 285
 286         /* close the '(' */
 287         *next++ = ')';
 288
 289         /* flush explicit tagged thang */
 290         if ( ber_printf( ber, /*"{"*/ "N}" ) == -1 )
 291                 return( NULL );
 292
 293         return( next );
 294 }
 295
 296 int
 297 ldap_int_put_filter( BerElement *ber, char *str )
 298 {
 299         char    *next;
 300         int     parens, balance, escape;
 301
 302         /*
 303          * A Filter looks like this:
 304          *      Filter ::= CHOICE {
 305          *              and             [0]     SET OF Filter,
 306          *              or              [1]     SET OF Filter,
 307          *              not             [2]     Filter,
 308          *              equalityMatch   [3]     AttributeValueAssertion,
 309          *              substrings      [4]     SubstringFilter,
 310          *              greaterOrEqual  [5]     AttributeValueAssertion,
 311          *              lessOrEqual     [6]     AttributeValueAssertion,
 312          *              present         [7]     AttributeType,
 313          *              approxMatch     [8]     AttributeValueAssertion,
 314          *                              extensibleMatch [9]             MatchingRuleAssertion -- LDAPv3
 315          *      }
 316          *
 317          *      SubstringFilter ::= SEQUENCE {
 318          *              type               AttributeType,
 319          *              SEQUENCE OF CHOICE {
 320          *                      initial          [0] IA5String,
 321          *                      any              [1] IA5String,
 322          *                      final            [2] IA5String
 323          *              }
 324          *      }
 325          *
 326          *              MatchingRuleAssertion ::= SEQUENCE {    -- LDAPv3
 327          *                      matchingRule    [1] MatchingRuleId OPTIONAL,
 328          *                      type            [2] AttributeDescription OPTIONAL,
 329          *                      matchValue      [3] AssertionValue,
 330          *                      dnAttributes    [4] BOOLEAN DEFAULT FALSE }
 331          *
 332          * Note: tags in a choice are always explicit
 333          */
 334
 335         Debug( LDAP_DEBUG_TRACE, "put_filter: \"%s\"\n", str, 0, 0 );
 336
 337         parens = 0;
 338         while ( *str ) {
 339                 switch ( *str ) {
 340                 case '(': /*')'*/
 341                         str++;
 342                         parens++;
 343
 344                         /* skip spaces */
 345                         while( LDAP_SPACE( *str ) ) str++;
 346
 347                         switch ( *str ) {
 348                         case '&':
 349                                 Debug( LDAP_DEBUG_TRACE, "put_filter: AND\n",
 350                                     0, 0, 0 );
 351
 352                                 str = put_complex_filter( ber, str,
 353                                     LDAP_FILTER_AND, 0 );
 354                                 if( str == NULL ) return( -1 );
 355
 356                                 parens--;
 357                                 break;
 358
 359                         case '|':
 360                                 Debug( LDAP_DEBUG_TRACE, "put_filter: OR\n",
 361                                     0, 0, 0 );
 362
 363                                 str = put_complex_filter( ber, str,
 364                                     LDAP_FILTER_OR, 0 );
 365                                 if( str == NULL ) return( -1 );
 366
 367                                 parens--;
 368                                 break;
 369
 370                         case '!':
 371                                 Debug( LDAP_DEBUG_TRACE, "put_filter: NOT\n",
 372                                     0, 0, 0 );
 373
 374                                 str = put_complex_filter( ber, str,
 375                                     LDAP_FILTER_NOT, 0 );
 376                                 if( str == NULL ) return( -1 );
 377
 378                                 parens--;
 379                                 break;
 380
 381                         default:
 382                                 Debug( LDAP_DEBUG_TRACE, "put_filter: simple\n",
 383                                     0, 0, 0 );
 384
 385                                 balance = 1;
 386                                 escape = 0;
 387                                 next = str;
 388                                 while ( *next && balance ) {
 389                                         if ( escape == 0 ) {
 390                                                 if ( *next == '(' )
 391                                                         balance++;
 392                                                 else if ( *next == ')' )
 393                                                         balance--;
 394                                         }
 395                                         if ( *next == '\\' && ! escape )
 396                                                 escape = 1;
 397                                         else
 398                                                 escape = 0;
 399                                         if ( balance )
 400                                                 next++;
 401                                 }
 402                                 if ( balance != 0 )
 403                                         return( -1 );
 404
 405                                 *next = '\0';
 406                                 if ( put_simple_filter( ber, str ) == -1 ) {
 407                                         return( -1 );
 408                                 }
 409                                 *next++ = ')';
 410                                 str = next;
 411                                 parens--;
 412                                 break;
 413                         }
 414                         break;
 415
 416                 case /*'('*/ ')':
 417                         Debug( LDAP_DEBUG_TRACE, "put_filter: end\n",
 418                                 0, 0, 0 );
 419                         if ( ber_printf( ber, /*"["*/ "]" ) == -1 )
 420                                 return( -1 );
 421                         str++;
 422                         parens--;
 423                         break;
 424
 425                 case ' ':
 426                         str++;
 427                         break;
 428
 429                 default:        /* assume it's a simple type=value filter */
 430                         Debug( LDAP_DEBUG_TRACE, "put_filter: default\n",
 431                                 0, 0, 0 );
 432                         next = strchr( str, '\0' );
 433                         if ( put_simple_filter( ber, str ) == -1 ) {
 434                                 return( -1 );
 435                         }
 436                         str = next;
 437                         break;
 438                 }
 439         }
 440
 441         return( parens ? -1 : 0 );
 442 }
 443
 444 /*
 445  * Put a list of filters like this "(filter1)(filter2)..."
 446  */
 447
 448 static int
 449 put_filter_list( BerElement *ber, char *str, ber_tag_t tag )
 450 {
 451         char    *next = NULL;
 452         char    save;
 453
 454         Debug( LDAP_DEBUG_TRACE, "put_filter_list \"%s\"\n",
 455                 str, 0, 0 );
 456
 457         while ( *str ) {
 458                 while ( *str && LDAP_SPACE( (unsigned char) *str ) ) {
 459                         str++;
 460                 }
 461                 if ( *str == '\0' ) break;
 462
 463                 if ( (next = find_right_paren( str + 1 )) == NULL ) {
 464                         return( -1 );
 465                 }
 466                 save = *++next;
 467
 468                 /* now we have "(filter)" with str pointing to it */
 469                 *next = '\0';
 470                 if ( ldap_int_put_filter( ber, str ) == -1 ) return -1;
 471                 *next = save;
 472                 str = next;
 473
 474                 if( tag == LDAP_FILTER_NOT ) break;
 475         }
 476
 477         if( tag == LDAP_FILTER_NOT && ( next == NULL || *str )) {
 478                 return -1;
 479         }
 480
 481         return 0;
 482 }
 483
 484 static int
 485 put_simple_filter(
 486         BerElement *ber,
 487         char *str )
 488 {
 489         char            *s;
 490         char            *value;
 491         ber_tag_t       ftype;
 492         int             rc = -1;
 493
 494         Debug( LDAP_DEBUG_TRACE, "put_simple_filter: \"%s\"\n",
 495                 str, 0, 0 );
 496
 497         str = LDAP_STRDUP( str );
 498         if( str == NULL ) return -1;
 499
 500         if ( (s = strchr( str, '=' )) == NULL ) {
 501                 goto done;
 502         }
 503
 504         value = s + 1;
 505         *s-- = '\0';
 506
 507         switch ( *s ) {
 508         case '<':
 509                 ftype = LDAP_FILTER_LE;
 510                 *s = '\0';
 511                 break;
 512
 513         case '>':
 514                 ftype = LDAP_FILTER_GE;
 515                 *s = '\0';
 516                 break;
 517
 518         case '~':
 519                 ftype = LDAP_FILTER_APPROX;
 520                 *s = '\0';
 521                 break;
 522
 523         case ':':
 524                 /* RFC2254 extensible filters are off the form:
 525                  *              type [:dn] [:rule] := value
 526                  * or   [:dn]:rule := value
 527                  */
 528                 ftype = LDAP_FILTER_EXT;
 529                 *s = '\0';
 530
 531                 {
 532                         char *dn = strchr( str, ':' );
 533                         char *rule = NULL;
 534
 535                         if( dn != NULL ) {
 536                                 *dn++ = '\0';
 537                                 rule = strchr( dn, ':' );
 538
 539                                 if( rule == NULL ) {
 540                                         /* one colon */
 541                                         if ( strcmp(dn, "dn") == 0 ) {
 542                                                 /* must have attribute */
 543                                                 if( !ldap_is_desc( str ) ) {
 544                                                         goto done;
 545                                                 }
 546
 547                                                 rule = "";
 548
 549                                         } else {
 550                                           rule = dn;
 551                                           dn = NULL;
 552                                         }
 553
 554                                 } else {
 555                                         /* two colons */
 556                                         *rule++ = '\0';
 557
 558                                         if ( strcmp(dn, "dn") != 0 ) {
 559                                                 /* must have "dn" */
 560                                                 goto done;
 561                                         }
 562                                 }
 563
 564                         }
 565
 566                         if ( *str == '\0' && ( !rule || *rule == '\0' ) ) {
 567                                 /* must have either type or rule */
 568                                 goto done;
 569                         }
 570
 571                         if ( *str != '\0' && !ldap_is_desc( str ) ) {
 572                                 goto done;
 573                         }
 574
 575                         if ( rule && *rule != '\0' && !ldap_is_oid( rule ) ) {
 576                                 goto done;
 577                         }
 578
 579                         rc = ber_printf( ber, "t{" /*"}"*/, ftype );
 580
 581                         if( rc != -1 && rule && *rule != '\0' ) {
 582                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_OID, rule );
 583                         }
 584                         if( rc != -1 && *str != '\0' ) {
 585                                 rc = ber_printf( ber, "ts", LDAP_FILTER_EXT_TYPE, str );
 586                         }
 587                         if( rc != -1 ) {
 588                                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 589
 590                                 if( len >= 0 ) {
 591                                         rc = ber_printf( ber, "to",
 592                                                 LDAP_FILTER_EXT_VALUE, value, len );
 593                                 } else {
 594                                         rc = -1;
 595                                 }
 596                         }
 597                         if( rc != -1 && dn ) {
 598                                 rc = ber_printf( ber, "tb",
 599                                         LDAP_FILTER_EXT_DNATTRS, (ber_int_t) 1 );
 600                         }
 601                         if( rc != -1 ) {
 602                                 rc = ber_printf( ber, /*"{"*/ "N}" );
 603                         }
 604                 }
 605                 goto done;
 606
 607         default:
 608                 {
 609                         char *nextstar = ldap_pvt_find_wildcard( value );
 610                         if ( nextstar == NULL ) {
 611                                 goto done;
 612                         } else if ( *nextstar == '\0' ) {
 613                                 ftype = LDAP_FILTER_EQUALITY;
 614                         } else if ( strcmp( value, "*" ) == 0 ) {
 615                                 ftype = LDAP_FILTER_PRESENT;
 616                         } else {
 617                                 rc = put_substring_filter( ber, str, value );
 618                                 goto done;
 619                         }
 620                 } break;
 621         }
 622
 623         if( !ldap_is_desc( str ) ) goto done;
 624
 625         if ( ftype == LDAP_FILTER_PRESENT ) {
 626                 rc = ber_printf( ber, "ts", ftype, str );
 627
 628         } else {
 629                 ber_slen_t len = ldap_pvt_filter_value_unescape( value );
 630
 631                 if( len >= 0 ) {
 632                         rc = ber_printf( ber, "t{soN}",
 633                                 ftype, str, value, len );
 634                 }
 635         }
 636
 637 done:
 638         if( rc != -1 ) rc = 0;
 639         LDAP_FREE( str );
 640         return rc;
 641 }
 642
 643 static int
 644 put_substring_filter( BerElement *ber, char *type, char *val )
 645 {
 646         char *nextstar;
 647         int gotstar = 0;
 648         ber_tag_t       ftype = LDAP_FILTER_SUBSTRINGS;
 649
 650         Debug( LDAP_DEBUG_TRACE, "put_substring_filter \"%s=%s\"\n",
 651                 type, val, 0 );
 652
 653         if ( ber_printf( ber, "t{s{" /*"}}"*/, ftype, type ) == -1 )
 654                 return( -1 );
 655
 656         for( ; *val; val=nextstar ) {
 657                 nextstar = ldap_pvt_find_wildcard( val );
 658
 659                 if ( nextstar == NULL ) {
 660                         return -1;
 661                 }
 662
 663                 if ( *nextstar == '\0' ) {
 664                         ftype = LDAP_SUBSTRING_FINAL;
 665                 } else if ( gotstar++ == 0 ) {
 666                         ftype = LDAP_SUBSTRING_INITIAL;
 667                 } else {
 668                         ftype = LDAP_SUBSTRING_ANY;
 669                 }
 670
 671                 *nextstar++ = '\0';
 672
 673                 if ( *val != '\0' || ftype == LDAP_SUBSTRING_ANY ) {
 674                         ber_slen_t len = ldap_pvt_filter_value_unescape( val );
 675
 676                         if ( len < 0  ) {
 677                                 return -1;
 678                         }
 679
 680                         if ( ber_printf( ber, "to", ftype, val, len ) == -1 ) {
 681                                 return -1;
 682                         }
 683                 }
 684         }
 685
 686         if ( ber_printf( ber, /*"{{"*/ "N}N}" ) == -1 )
 687                 return -1;
 688
 689         return 0;
 690 }