lib/ldb/common/ldb_parse.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Tridgell  2004
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 3 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb expression parsing
  28  *
  29  *  Description: parse LDAP-like search expressions
  30  *
  31  *  Author: Andrew Tridgell
  32  */
  33
  34 /*
  35   TODO:
  36       - add RFC2254 binary string handling
  37       - possibly add ~=, <= and >= handling
  38       - expand the test suite
  39       - add better parse error handling
  40
  41 */
  42
  43 #include "ldb_private.h"
  44 #include "system/locale.h"
  45
  46 static int ldb_parse_hex2char(const char *x)
  47 {
  48         if (isxdigit(x[0]) && isxdigit(x[1])) {
  49                 const char h1 = x[0], h2 = x[1];
  50                 int c = 0;
  51
  52                 if (h1 >= 'a') c = h1 - (int)'a' + 10;
  53                 else if (h1 >= 'A') c = h1 - (int)'A' + 10;
  54                 else if (h1 >= '0') c = h1 - (int)'0';
  55                 c = c << 4;
  56                 if (h2 >= 'a') c += h2 - (int)'a' + 10;
  57                 else if (h2 >= 'A') c += h2 - (int)'A' + 10;
  58                 else if (h2 >= '0') c += h2 - (int)'0';
  59
  60                 return c;
  61         }
  62
  63         return -1;
  64 }
  65
  66 /*
  67 a filter is defined by:
  68                <filter> ::= '(' <filtercomp> ')'
  69                <filtercomp> ::= <and> | <or> | <not> | <simple>
  70                <and> ::= '&' <filterlist>
  71                <or> ::= '|' <filterlist>
  72                <not> ::= '!' <filter>
  73                <filterlist> ::= <filter> | <filter> <filterlist>
  74                <simple> ::= <attributetype> <filtertype> <attributevalue>
  75                <filtertype> ::= '=' | '~=' | '<=' | '>='
  76 */
  77
  78 /*
  79    decode a RFC2254 binary string representation of a buffer.
  80    Used in LDAP filters.
  81 */
  82 struct ldb_val ldb_binary_decode(TALLOC_CTX *mem_ctx, const char *str)
  83 {
  84         size_t i, j;
  85         struct ldb_val ret;
  86         size_t slen = str?strlen(str):0;
  87
  88         ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
  89         ret.length = 0;
  90         if (ret.data == NULL) return ret;
  91
  92         for (i=j=0;i<slen;i++) {
  93                 if (str[i] == '\\') {
  94                         int c;
  95
  96                         c = ldb_parse_hex2char(&str[i+1]);
  97                         if (c == -1) {
  98                                 talloc_free(ret.data);
  99                                 memset(&ret, 0, sizeof(ret));
 100                                 return ret;
 101                         }
 102                         ((uint8_t *)ret.data)[j++] = c;
 103                         i += 2;
 104                 } else {
 105                         ((uint8_t *)ret.data)[j++] = str[i];
 106                 }
 107         }
 108         ret.length = j;
 109         ((uint8_t *)ret.data)[j] = 0;
 110
 111         return ret;
 112 }
 113
 114
 115 /*
 116    encode a blob as a RFC2254 binary string, escaping any
 117    non-printable or '\' characters
 118 */
 119 char *ldb_binary_encode(TALLOC_CTX *mem_ctx, struct ldb_val val)
 120 {
 121         size_t i;
 122         char *ret;
 123         size_t len = val.length;
 124         unsigned char *buf = val.data;
 125
 126         for (i=0;i<val.length;i++) {
 127                 unsigned int cval = buf[i];
 128                 if (cval < 0x20 || cval > 0x7E || strchr(" *()\\&|!\"", buf[i])) {
 129                         len += 2;
 130                 }
 131         }
 132         ret = talloc_array(mem_ctx, char, len+1);
 133         if (ret == NULL) return NULL;
 134
 135         len = 0;
 136         for (i=0;i<val.length;i++) {
 137                 unsigned int cval = buf[i];
 138                 if (cval < 0x20 || cval > 0x7E || strchr(" *()\\&|!\"", buf[i])) {
 139                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 140                         len += 3;
 141                 } else {
 142                         ret[len++] = buf[i];
 143                 }
 144         }
 145
 146         ret[len] = 0;
 147
 148         return ret;
 149 }
 150
 151 /*
 152    encode a string as a RFC2254 binary string, escaping any
 153    non-printable or '\' characters.  This routine is suitable for use
 154    in escaping user data in ldap filters.
 155 */
 156 char *ldb_binary_encode_string(TALLOC_CTX *mem_ctx, const char *string)
 157 {
 158         struct ldb_val val;
 159         if (string == NULL) {
 160                 return NULL;
 161         }
 162         val.data = discard_const_p(uint8_t, string);
 163         val.length = strlen(string);
 164         return ldb_binary_encode(mem_ctx, val);
 165 }
 166
 167 /* find the first matching wildcard */
 168 static char *ldb_parse_find_wildcard(char *value)
 169 {
 170         while (*value) {
 171                 value = strpbrk(value, "\\*");
 172                 if (value == NULL) return NULL;
 173
 174                 if (value[0] == '\\') {
 175                         if (value[1] == '\0') return NULL;
 176                         value += 2;
 177                         continue;
 178                 }
 179
 180                 if (value[0] == '*') return value;
 181         }
 182
 183         return NULL;
 184 }
 185
 186 /* return a NULL terminated list of binary strings representing the value
 187    chunks separated by wildcards that makes the value portion of the filter
 188 */
 189 static struct ldb_val **ldb_wildcard_decode(TALLOC_CTX *mem_ctx, const char *string)
 190 {
 191         struct ldb_val **ret = NULL;
 192         unsigned int val = 0;
 193         char *wc, *str;
 194
 195         wc = talloc_strdup(mem_ctx, string);
 196         if (wc == NULL) return NULL;
 197
 198         while (wc && *wc) {
 199                 str = wc;
 200                 wc = ldb_parse_find_wildcard(str);
 201                 if (wc && *wc) {
 202                         if (wc == str) {
 203                                 wc++;
 204                                 continue;
 205                         }
 206                         *wc = 0;
 207                         wc++;
 208                 }
 209
 210                 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
 211                 if (ret == NULL) return NULL;
 212
 213                 ret[val] = talloc(mem_ctx, struct ldb_val);
 214                 if (ret[val] == NULL) return NULL;
 215
 216                 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
 217                 if ((ret[val])->data == NULL) return NULL;
 218
 219                 val++;
 220         }
 221
 222         if (ret != NULL) {
 223                 ret[val] = NULL;
 224         }
 225
 226         return ret;
 227 }
 228
 229 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *mem_ctx, const char **s);
 230
 231
 232 /*
 233   parse an extended match
 234
 235   possible forms:
 236         (attr:oid:=value)
 237         (attr:dn:oid:=value)
 238         (attr:dn:=value)
 239         (:dn:oid:=value)
 240
 241   the ':dn' part sets the dnAttributes boolean if present
 242   the oid sets the rule_id string
 243
 244 */
 245 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 246                                                  char *attr, char *value)
 247 {
 248         char *p1, *p2;
 249
 250         ret->operation = LDB_OP_EXTENDED;
 251         ret->u.extended.value = ldb_binary_decode(ret, value);
 252         if (ret->u.extended.value.data == NULL) goto failed;
 253
 254         p1 = strchr(attr, ':');
 255         if (p1 == NULL) goto failed;
 256         p2 = strchr(p1+1, ':');
 257
 258         *p1 = 0;
 259         if (p2) *p2 = 0;
 260
 261         ret->u.extended.attr = attr;
 262         if (strcmp(p1+1, "dn") == 0) {
 263                 ret->u.extended.dnAttributes = 1;
 264                 if (p2) {
 265                         ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 266                         if (ret->u.extended.rule_id == NULL) goto failed;
 267                 } else {
 268                         ret->u.extended.rule_id = NULL;
 269                 }
 270         } else {
 271                 ret->u.extended.dnAttributes = 0;
 272                 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 273                 if (ret->u.extended.rule_id == NULL) goto failed;
 274         }
 275
 276         return ret;
 277
 278 failed:
 279         talloc_free(ret);
 280         return NULL;
 281 }
 282
 283 static enum ldb_parse_op ldb_parse_filtertype(TALLOC_CTX *mem_ctx, char **type, char **value, const char **s)
 284 {
 285         enum ldb_parse_op filter = 0;
 286         char *name, *val, *k;
 287         const char *p = *s;
 288         const char *t, *t1;
 289
 290         /* retrieve attributetype name */
 291         t = p;
 292
 293         if (*p == '@') { /* for internal attributes the first char can be @ */
 294                 p++;
 295         }
 296
 297         while ((isascii(*p) && isalnum((unsigned char)*p)) || (*p == '-') || (*p == '.')) {
 298                 /* attribute names can only be alphanums */
 299                 p++;
 300         }
 301
 302         if (*p == ':') { /* but extended searches have : and . chars too */
 303                 p = strstr(p, ":=");
 304                 if (p == NULL) { /* malformed attribute name */
 305                         return 0;
 306                 }
 307         }
 308
 309         t1 = p;
 310
 311         while (isspace((unsigned char)*p)) p++;
 312
 313         if (!strchr("=<>~:", *p)) {
 314                 return 0;
 315         }
 316
 317         /* save name */
 318         name = (char *)talloc_memdup(mem_ctx, t, t1 - t + 1);
 319         if (name == NULL) return 0;
 320         name[t1 - t] = '\0';
 321
 322         /* retrieve filtertype */
 323
 324         if (*p == '=') {
 325                 filter = LDB_OP_EQUALITY;
 326         } else if (*(p + 1) == '=') {
 327                 switch (*p) {
 328                 case '<':
 329                         filter = LDB_OP_LESS;
 330                         p++;
 331                         break;
 332                 case '>':
 333                         filter = LDB_OP_GREATER;
 334                         p++;
 335                         break;
 336                 case '~':
 337                         filter = LDB_OP_APPROX;
 338                         p++;
 339                         break;
 340                 case ':':
 341                         filter = LDB_OP_EXTENDED;
 342                         p++;
 343                         break;
 344                 }
 345         }
 346         if (!filter) {
 347                 talloc_free(name);
 348                 return 0;
 349         }
 350         p++;
 351
 352         while (isspace((unsigned char)*p)) p++;
 353
 354         /* retrieve value */
 355         t = p;
 356
 357         while (*p && ((*p != ')') || ((*p == ')') && (*(p - 1) == '\\')))) p++;
 358
 359         val = (char *)talloc_memdup(mem_ctx, t, p - t + 1);
 360         if (val == NULL) {
 361                 talloc_free(name);
 362                 return 0;
 363         }
 364         val[p - t] = '\0';
 365
 366         k = &(val[p - t]);
 367
 368         /* remove trailing spaces from value */
 369         while ((k > val) && (isspace((unsigned char)*(k - 1)))) k--;
 370         *k = '\0';
 371
 372         *type = name;
 373         *value = val;
 374         *s = p;
 375         return filter;
 376 }
 377
 378 /*
 379   <simple> ::= <attributetype> <filtertype> <attributevalue>
 380 */
 381 static struct ldb_parse_tree *ldb_parse_simple(TALLOC_CTX *mem_ctx, const char **s)
 382 {
 383         char *attr, *value;
 384         struct ldb_parse_tree *ret;
 385         enum ldb_parse_op filtertype;
 386
 387         ret = talloc(mem_ctx, struct ldb_parse_tree);
 388         if (!ret) {
 389                 errno = ENOMEM;
 390                 return NULL;
 391         }
 392
 393         filtertype = ldb_parse_filtertype(ret, &attr, &value, s);
 394         if (!filtertype) {
 395                 talloc_free(ret);
 396                 return NULL;
 397         }
 398
 399         switch (filtertype) {
 400
 401                 case LDB_OP_PRESENT:
 402                         ret->operation = LDB_OP_PRESENT;
 403                         ret->u.present.attr = attr;
 404                         break;
 405
 406                 case LDB_OP_EQUALITY:
 407
 408                         if (strcmp(value, "*") == 0) {
 409                                 ret->operation = LDB_OP_PRESENT;
 410                                 ret->u.present.attr = attr;
 411                                 break;
 412                         }
 413
 414                         if (ldb_parse_find_wildcard(value) != NULL) {
 415                                 ret->operation = LDB_OP_SUBSTRING;
 416                                 ret->u.substring.attr = attr;
 417                                 ret->u.substring.start_with_wildcard = 0;
 418                                 ret->u.substring.end_with_wildcard = 0;
 419                                 ret->u.substring.chunks = ldb_wildcard_decode(ret, value);
 420                                 if (ret->u.substring.chunks == NULL){
 421                                         talloc_free(ret);
 422                                         return NULL;
 423                                 }
 424                                 if (value[0] == '*')
 425                                         ret->u.substring.start_with_wildcard = 1;
 426                                 if (value[strlen(value) - 1] == '*')
 427                                         ret->u.substring.end_with_wildcard = 1;
 428                                 talloc_free(value);
 429
 430                                 break;
 431                         }
 432
 433                         ret->operation = LDB_OP_EQUALITY;
 434                         ret->u.equality.attr = attr;
 435                         ret->u.equality.value = ldb_binary_decode(ret, value);
 436                         if (ret->u.equality.value.data == NULL) {
 437                                 talloc_free(ret);
 438                                 return NULL;
 439                         }
 440                         talloc_free(value);
 441                         break;
 442
 443                 case LDB_OP_GREATER:
 444                         ret->operation = LDB_OP_GREATER;
 445                         ret->u.comparison.attr = attr;
 446                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 447                         if (ret->u.comparison.value.data == NULL) {
 448                                 talloc_free(ret);
 449                                 return NULL;
 450                         }
 451                         talloc_free(value);
 452                         break;
 453
 454                 case LDB_OP_LESS:
 455                         ret->operation = LDB_OP_LESS;
 456                         ret->u.comparison.attr = attr;
 457                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 458                         if (ret->u.comparison.value.data == NULL) {
 459                                 talloc_free(ret);
 460                                 return NULL;
 461                         }
 462                         talloc_free(value);
 463                         break;
 464
 465                 case LDB_OP_APPROX:
 466                         ret->operation = LDB_OP_APPROX;
 467                         ret->u.comparison.attr = attr;
 468                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 469                         if (ret->u.comparison.value.data == NULL) {
 470                                 talloc_free(ret);
 471                                 return NULL;
 472                         }
 473                         talloc_free(value);
 474                         break;
 475
 476                 case LDB_OP_EXTENDED:
 477
 478                         ret = ldb_parse_extended(ret, attr, value);
 479                         break;
 480
 481                 default:
 482                         talloc_free(ret);
 483                         return NULL;
 484         }
 485
 486         return ret;
 487 }
 488
 489
 490 /*
 491   parse a filterlist
 492   <and> ::= '&' <filterlist>
 493   <or> ::= '|' <filterlist>
 494   <filterlist> ::= <filter> | <filter> <filterlist>
 495 */
 496 static struct ldb_parse_tree *ldb_parse_filterlist(TALLOC_CTX *mem_ctx, const char **s)
 497 {
 498         struct ldb_parse_tree *ret, *next;
 499         enum ldb_parse_op op;
 500         const char *p = *s;
 501
 502         switch (*p) {
 503                 case '&':
 504                         op = LDB_OP_AND;
 505                         break;
 506                 case '|':
 507                         op = LDB_OP_OR;
 508                         break;
 509                 default:
 510                         return NULL;
 511         }
 512         p++;
 513
 514         while (isspace((unsigned char)*p)) p++;
 515
 516         ret = talloc(mem_ctx, struct ldb_parse_tree);
 517         if (!ret) {
 518                 errno = ENOMEM;
 519                 return NULL;
 520         }
 521
 522         ret->operation = op;
 523         ret->u.list.num_elements = 1;
 524         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 525         if (!ret->u.list.elements) {
 526                 errno = ENOMEM;
 527                 talloc_free(ret);
 528                 return NULL;
 529         }
 530
 531         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &p);
 532         if (!ret->u.list.elements[0]) {
 533                 talloc_free(ret);
 534                 return NULL;
 535         }
 536
 537         while (isspace((unsigned char)*p)) p++;
 538
 539         while (*p) {
 540                 struct ldb_parse_tree **e;
 541                 if (*p == ')') {
 542                         break;
 543                 }
 544
 545                 next = ldb_parse_filter(ret->u.list.elements, &p);
 546                 if (next == NULL) {
 547                         /* an invalid filter element */
 548                         talloc_free(ret);
 549                         return NULL;
 550                 }
 551                 e = talloc_realloc(ret, ret->u.list.elements,
 552                                      struct ldb_parse_tree *,
 553                                      ret->u.list.num_elements + 1);
 554                 if (!e) {
 555                         errno = ENOMEM;
 556                         talloc_free(ret);
 557                         return NULL;
 558                 }
 559                 ret->u.list.elements = e;
 560                 ret->u.list.elements[ret->u.list.num_elements] = next;
 561                 ret->u.list.num_elements++;
 562                 while (isspace((unsigned char)*p)) p++;
 563         }
 564
 565         *s = p;
 566
 567         return ret;
 568 }
 569
 570
 571 /*
 572   <not> ::= '!' <filter>
 573 */
 574 static struct ldb_parse_tree *ldb_parse_not(TALLOC_CTX *mem_ctx, const char **s)
 575 {
 576         struct ldb_parse_tree *ret;
 577         const char *p = *s;
 578
 579         if (*p != '!') {
 580                 return NULL;
 581         }
 582         p++;
 583
 584         ret = talloc(mem_ctx, struct ldb_parse_tree);
 585         if (!ret) {
 586                 errno = ENOMEM;
 587                 return NULL;
 588         }
 589
 590         ret->operation = LDB_OP_NOT;
 591         ret->u.isnot.child = ldb_parse_filter(ret, &p);
 592         if (!ret->u.isnot.child) {
 593                 talloc_free(ret);
 594                 return NULL;
 595         }
 596
 597         *s = p;
 598
 599         return ret;
 600 }
 601
 602 /*
 603   parse a filtercomp
 604   <filtercomp> ::= <and> | <or> | <not> | <simple>
 605 */
 606 static struct ldb_parse_tree *ldb_parse_filtercomp(TALLOC_CTX *mem_ctx, const char **s)
 607 {
 608         struct ldb_parse_tree *ret;
 609         const char *p = *s;
 610
 611         while (isspace((unsigned char)*p)) p++;
 612
 613         switch (*p) {
 614         case '&':
 615                 ret = ldb_parse_filterlist(mem_ctx, &p);
 616                 break;
 617
 618         case '|':
 619                 ret = ldb_parse_filterlist(mem_ctx, &p);
 620                 break;
 621
 622         case '!':
 623                 ret = ldb_parse_not(mem_ctx, &p);
 624                 break;
 625
 626         case '(':
 627         case ')':
 628                 return NULL;
 629
 630         default:
 631                 ret = ldb_parse_simple(mem_ctx, &p);
 632
 633         }
 634
 635         *s = p;
 636         return ret;
 637 }
 638
 639
 640 /*
 641   <filter> ::= '(' <filtercomp> ')'
 642 */
 643 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *mem_ctx, const char **s)
 644 {
 645         struct ldb_parse_tree *ret;
 646         const char *p = *s;
 647
 648         if (*p != '(') {
 649                 return NULL;
 650         }
 651         p++;
 652
 653         ret = ldb_parse_filtercomp(mem_ctx, &p);
 654
 655         if (*p != ')') {
 656                 return NULL;
 657         }
 658         p++;
 659
 660         while (isspace((unsigned char)*p)) {
 661                 p++;
 662         }
 663
 664         *s = p;
 665
 666         return ret;
 667 }
 668
 669
 670 /*
 671   main parser entry point. Takes a search string and returns a parse tree
 672
 673   expression ::= <simple> | <filter>
 674 */
 675 struct ldb_parse_tree *ldb_parse_tree(TALLOC_CTX *mem_ctx, const char *s)
 676 {
 677         if (s == NULL || *s == 0) {
 678                 s = "(|(objectClass=*)(distinguishedName=*))";
 679         }
 680
 681         while (isspace((unsigned char)*s)) s++;
 682
 683         if (*s == '(') {
 684                 return ldb_parse_filter(mem_ctx, &s);
 685         }
 686
 687         return ldb_parse_simple(mem_ctx, &s);
 688 }
 689
 690
 691 /*
 692   construct a ldap parse filter given a parse tree
 693 */
 694 char *ldb_filter_from_tree(TALLOC_CTX *mem_ctx, const struct ldb_parse_tree *tree)
 695 {
 696         char *s, *s2, *ret;
 697         unsigned int i;
 698
 699         if (tree == NULL) {
 700                 return NULL;
 701         }
 702
 703         switch (tree->operation) {
 704         case LDB_OP_AND:
 705         case LDB_OP_OR:
 706                 ret = talloc_asprintf(mem_ctx, "(%c", tree->operation==LDB_OP_AND?'&':'|');
 707                 if (ret == NULL) return NULL;
 708                 for (i=0;i<tree->u.list.num_elements;i++) {
 709                         s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
 710                         if (s == NULL) {
 711                                 talloc_free(ret);
 712                                 return NULL;
 713                         }
 714                         s2 = talloc_asprintf_append(ret, "%s", s);
 715                         talloc_free(s);
 716                         if (s2 == NULL) {
 717                                 talloc_free(ret);
 718                                 return NULL;
 719                         }
 720                         ret = s2;
 721                 }
 722                 s = talloc_asprintf_append(ret, ")");
 723                 if (s == NULL) {
 724                         talloc_free(ret);
 725                         return NULL;
 726                 }
 727                 return s;
 728         case LDB_OP_NOT:
 729                 s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
 730                 if (s == NULL) return NULL;
 731
 732                 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 733                 talloc_free(s);
 734                 return ret;
 735         case LDB_OP_EQUALITY:
 736                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 737                 if (s == NULL) return NULL;
 738                 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
 739                                       tree->u.equality.attr, s);
 740                 talloc_free(s);
 741                 return ret;
 742         case LDB_OP_SUBSTRING:
 743                 ret = talloc_asprintf(mem_ctx, "(%s=%s", tree->u.substring.attr,
 744                                       tree->u.substring.start_with_wildcard?"*":"");
 745                 if (ret == NULL) return NULL;
 746                 for (i = 0; tree->u.substring.chunks[i]; i++) {
 747                         s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
 748                         if (s2 == NULL) {
 749                                 talloc_free(ret);
 750                                 return NULL;
 751                         }
 752                         if (tree->u.substring.chunks[i+1] ||
 753                             tree->u.substring.end_with_wildcard) {
 754                                 s = talloc_asprintf_append(ret, "%s*", s2);
 755                         } else {
 756                                 s = talloc_asprintf_append(ret, "%s", s2);
 757                         }
 758                         if (s == NULL) {
 759                                 talloc_free(ret);
 760                                 return NULL;
 761                         }
 762                         ret = s;
 763                 }
 764                 s = talloc_asprintf_append(ret, ")");
 765                 if (s == NULL) {
 766                         talloc_free(ret);
 767                         return NULL;
 768                 }
 769                 ret = s;
 770                 return ret;
 771         case LDB_OP_GREATER:
 772                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 773                 if (s == NULL) return NULL;
 774                 ret = talloc_asprintf(mem_ctx, "(%s>=%s)",
 775                                       tree->u.equality.attr, s);
 776                 talloc_free(s);
 777                 return ret;
 778         case LDB_OP_LESS:
 779                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 780                 if (s == NULL) return NULL;
 781                 ret = talloc_asprintf(mem_ctx, "(%s<=%s)",
 782                                       tree->u.equality.attr, s);
 783                 talloc_free(s);
 784                 return ret;
 785         case LDB_OP_PRESENT:
 786                 ret = talloc_asprintf(mem_ctx, "(%s=*)", tree->u.present.attr);
 787                 return ret;
 788         case LDB_OP_APPROX:
 789                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 790                 if (s == NULL) return NULL;
 791                 ret = talloc_asprintf(mem_ctx, "(%s~=%s)",
 792                                       tree->u.equality.attr, s);
 793                 talloc_free(s);
 794                 return ret;
 795         case LDB_OP_EXTENDED:
 796                 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
 797                 if (s == NULL) return NULL;
 798                 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
 799                                       tree->u.extended.attr?tree->u.extended.attr:"",
 800                                       tree->u.extended.dnAttributes?":dn":"",
 801                                       tree->u.extended.rule_id?":":"",
 802                                       tree->u.extended.rule_id?tree->u.extended.rule_id:"",
 803                                       s);
 804                 talloc_free(s);
 805                 return ret;
 806         }
 807
 808         return NULL;
 809 }
 810
 811
 812 /*
 813   walk a parse tree, calling the provided callback on each node
 814 */
 815 int ldb_parse_tree_walk(struct ldb_parse_tree *tree,
 816                         int (*callback)(struct ldb_parse_tree *tree, void *),
 817                         void *private_context)
 818 {
 819         unsigned int i;
 820         int ret;
 821
 822         ret = callback(tree, private_context);
 823         if (ret != LDB_SUCCESS) {
 824                 return ret;
 825         }
 826
 827         switch (tree->operation) {
 828         case LDB_OP_AND:
 829         case LDB_OP_OR:
 830                 for (i=0;i<tree->u.list.num_elements;i++) {
 831                         ret = ldb_parse_tree_walk(tree->u.list.elements[i], callback, private_context);
 832                         if (ret != LDB_SUCCESS) {
 833                                 return ret;
 834                         }
 835                 }
 836                 break;
 837         case LDB_OP_NOT:
 838                 ret = ldb_parse_tree_walk(tree->u.isnot.child, callback, private_context);
 839                 if (ret != LDB_SUCCESS) {
 840                         return ret;
 841                 }
 842                 break;
 843         case LDB_OP_EQUALITY:
 844         case LDB_OP_GREATER:
 845         case LDB_OP_LESS:
 846         case LDB_OP_APPROX:
 847         case LDB_OP_SUBSTRING:
 848         case LDB_OP_PRESENT:
 849         case LDB_OP_EXTENDED:
 850                 break;
 851         }
 852         return LDB_SUCCESS;
 853 }
 854
 855 struct parse_tree_attr_replace_ctx {
 856         const char *attr;
 857         const char *replace;
 858 };
 859
 860 /*
 861   callback for ldb_parse_tree_attr_replace()
 862  */
 863 static int parse_tree_attr_replace(struct ldb_parse_tree *tree, void *private_context)
 864 {
 865         struct parse_tree_attr_replace_ctx *ctx = private_context;
 866         switch (tree->operation) {
 867         case LDB_OP_EQUALITY:
 868         case LDB_OP_GREATER:
 869         case LDB_OP_LESS:
 870         case LDB_OP_APPROX:
 871                 if (ldb_attr_cmp(tree->u.equality.attr, ctx->attr) == 0) {
 872                         tree->u.equality.attr = ctx->replace;
 873                 }
 874                 break;
 875         case LDB_OP_SUBSTRING:
 876                 if (ldb_attr_cmp(tree->u.substring.attr, ctx->attr) == 0) {
 877                         tree->u.substring.attr = ctx->replace;
 878                 }
 879                 break;
 880         case LDB_OP_PRESENT:
 881                 if (ldb_attr_cmp(tree->u.present.attr, ctx->attr) == 0) {
 882                         tree->u.present.attr = ctx->replace;
 883                 }
 884                 break;
 885         case LDB_OP_EXTENDED:
 886                 if (tree->u.extended.attr &&
 887                     ldb_attr_cmp(tree->u.extended.attr, ctx->attr) == 0) {
 888                         tree->u.extended.attr = ctx->replace;
 889                 }
 890                 break;
 891         default:
 892                 break;
 893         }
 894         return LDB_SUCCESS;
 895 }
 896
 897 /*
 898   replace any occurrences of an attribute name in the parse tree with a
 899   new name
 900 */
 901 void ldb_parse_tree_attr_replace(struct ldb_parse_tree *tree,
 902                                  const char *attr,
 903                                  const char *replace)
 904 {
 905         struct parse_tree_attr_replace_ctx ctx;
 906
 907         ctx.attr    = attr;
 908         ctx.replace = replace;
 909
 910         ldb_parse_tree_walk(tree, parse_tree_attr_replace, &ctx);
 911 }
 912
 913 /*
 914   shallow copy a tree - copying only the elements array so that the caller
 915   can safely add new elements without changing the message
 916 */
 917 struct ldb_parse_tree *ldb_parse_tree_copy_shallow(TALLOC_CTX *mem_ctx,
 918                                                    const struct ldb_parse_tree *ot)
 919 {
 920         unsigned int i;
 921         struct ldb_parse_tree *nt;
 922
 923         nt = talloc(mem_ctx, struct ldb_parse_tree);
 924         if (!nt) {
 925                 return NULL;
 926         }
 927
 928         *nt = *ot;
 929
 930         switch (ot->operation) {
 931         case LDB_OP_AND:
 932         case LDB_OP_OR:
 933                 nt->u.list.elements = talloc_array(nt, struct ldb_parse_tree *,
 934                                                    ot->u.list.num_elements);
 935                 if (!nt->u.list.elements) {
 936                         talloc_free(nt);
 937                         return NULL;
 938                 }
 939
 940                 for (i=0;i<ot->u.list.num_elements;i++) {
 941                         nt->u.list.elements[i] =
 942                                 ldb_parse_tree_copy_shallow(nt->u.list.elements,
 943                                                 ot->u.list.elements[i]);
 944                         if (!nt->u.list.elements[i]) {
 945                                 talloc_free(nt);
 946                                 return NULL;
 947                         }
 948                 }
 949                 break;
 950         case LDB_OP_NOT:
 951                 nt->u.isnot.child = ldb_parse_tree_copy_shallow(nt,
 952                                                         ot->u.isnot.child);
 953                 if (!nt->u.isnot.child) {
 954                         talloc_free(nt);
 955                         return NULL;
 956                 }
 957                 break;
 958         case LDB_OP_EQUALITY:
 959         case LDB_OP_GREATER:
 960         case LDB_OP_LESS:
 961         case LDB_OP_APPROX:
 962         case LDB_OP_SUBSTRING:
 963         case LDB_OP_PRESENT:
 964         case LDB_OP_EXTENDED:
 965                 break;
 966         }
 967
 968         return nt;
 969 }