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 /*
  47  * Maximum depth of the filter parse tree, the value chosen is small enough to
  48  * avoid triggering ASAN stack overflow checks. But large enough to be useful.
  49  *
  50  * On Windows clients the maximum number of levels of recursion allowed is 100.
  51  * In the LDAP server, Windows restricts clients to 512 nested
  52  * (eg) OR statements.
  53  */
  54 #define LDB_MAX_PARSE_TREE_DEPTH 128
  55
  56 /*
  57 a filter is defined by:
  58                <filter> ::= '(' <filtercomp> ')'
  59                <filtercomp> ::= <and> | <or> | <not> | <simple>
  60                <and> ::= '&' <filterlist>
  61                <or> ::= '|' <filterlist>
  62                <not> ::= '!' <filter>
  63                <filterlist> ::= <filter> | <filter> <filterlist>
  64                <simple> ::= <attributetype> <filtertype> <attributevalue>
  65                <filtertype> ::= '=' | '~=' | '<=' | '>='
  66 */
  67
  68 /*
  69    decode a RFC2254 binary string representation of a buffer.
  70    Used in LDAP filters.
  71 */
  72 struct ldb_val ldb_binary_decode(TALLOC_CTX *mem_ctx, const char *str)
  73 {
  74         size_t i, j;
  75         struct ldb_val ret;
  76         size_t slen = str?strlen(str):0;
  77
  78         ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
  79         ret.length = 0;
  80         if (ret.data == NULL) return ret;
  81
  82         for (i=j=0;i<slen;i++) {
  83                 if (str[i] == '\\') {
  84                         uint8_t c;
  85                         bool ok;
  86
  87                         ok = hex_byte(&str[i+1], &c);
  88                         if (!ok) {
  89                                 talloc_free(ret.data);
  90                                 memset(&ret, 0, sizeof(ret));
  91                                 return ret;
  92                         }
  93                         ((uint8_t *)ret.data)[j++] = c;
  94                         i += 2;
  95                 } else {
  96                         ((uint8_t *)ret.data)[j++] = str[i];
  97                 }
  98         }
  99         ret.length = j;
 100         ((uint8_t *)ret.data)[j] = 0;
 101
 102         return ret;
 103 }
 104
 105 static bool need_encode(unsigned char cval)
 106 {
 107         if (cval < 0x20 || cval > 0x7E || strchr(" *()\\&|!\"", cval)) {
 108                 return true;
 109         }
 110         return false;
 111 }
 112
 113 /*
 114    encode a blob as a RFC2254 binary string, escaping any
 115    non-printable or '\' characters
 116 */
 117 char *ldb_binary_encode(TALLOC_CTX *mem_ctx, struct ldb_val val)
 118 {
 119         size_t i;
 120         char *ret;
 121         size_t len = val.length;
 122         unsigned char *buf = val.data;
 123
 124         for (i=0;i<val.length;i++) {
 125                 if (need_encode(buf[i])) {
 126                         len += 2;
 127                 }
 128         }
 129         ret = talloc_array(mem_ctx, char, len+1);
 130         if (ret == NULL) return NULL;
 131
 132         len = 0;
 133         for (i=0;i<val.length;i++) {
 134                 if (need_encode(buf[i])) {
 135                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 136                         len += 3;
 137                 } else {
 138                         ret[len++] = buf[i];
 139                 }
 140         }
 141
 142         ret[len] = 0;
 143
 144         return ret;
 145 }
 146
 147 /*
 148    encode a string as a RFC2254 binary string, escaping any
 149    non-printable or '\' characters.  This routine is suitable for use
 150    in escaping user data in ldap filters.
 151 */
 152 char *ldb_binary_encode_string(TALLOC_CTX *mem_ctx, const char *string)
 153 {
 154         struct ldb_val val;
 155         if (string == NULL) {
 156                 return NULL;
 157         }
 158         val.data = discard_const_p(uint8_t, string);
 159         val.length = strlen(string);
 160         return ldb_binary_encode(mem_ctx, val);
 161 }
 162
 163 /* find the first matching wildcard */
 164 static char *ldb_parse_find_wildcard(char *value)
 165 {
 166         while (*value) {
 167                 value = strpbrk(value, "\\*");
 168                 if (value == NULL) return NULL;
 169
 170                 if (value[0] == '\\') {
 171                         if (value[1] == '\0') return NULL;
 172                         value += 2;
 173                         continue;
 174                 }
 175
 176                 if (value[0] == '*') return value;
 177         }
 178
 179         return NULL;
 180 }
 181
 182 /* return a NULL terminated list of binary strings representing the value
 183    chunks separated by wildcards that makes the value portion of the filter
 184 */
 185 static struct ldb_val **ldb_wildcard_decode(TALLOC_CTX *mem_ctx, const char *string)
 186 {
 187         struct ldb_val **ret = NULL;
 188         unsigned int val = 0;
 189         char *wc, *str;
 190
 191         wc = talloc_strdup(mem_ctx, string);
 192         if (wc == NULL) return NULL;
 193
 194         while (wc && *wc) {
 195                 str = wc;
 196                 wc = ldb_parse_find_wildcard(str);
 197                 if (wc && *wc) {
 198                         if (wc == str) {
 199                                 wc++;
 200                                 continue;
 201                         }
 202                         *wc = 0;
 203                         wc++;
 204                 }
 205
 206                 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
 207                 if (ret == NULL) return NULL;
 208
 209                 ret[val] = talloc(mem_ctx, struct ldb_val);
 210                 if (ret[val] == NULL) return NULL;
 211
 212                 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
 213                 if ((ret[val])->data == NULL) return NULL;
 214
 215                 val++;
 216         }
 217
 218         if (ret != NULL) {
 219                 ret[val] = NULL;
 220         }
 221
 222         return ret;
 223 }
 224
 225 static struct ldb_parse_tree *ldb_parse_filter(
 226         TALLOC_CTX *mem_ctx,
 227         const char **s,
 228         unsigned depth,
 229         unsigned max_depth);
 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 != '\0' && *(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_zero(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(
 497         TALLOC_CTX *mem_ctx,
 498         const char **s,
 499         unsigned depth,
 500         unsigned max_depth)
 501 {
 502         struct ldb_parse_tree *ret, *next;
 503         enum ldb_parse_op op;
 504         const char *p = *s;
 505
 506         switch (*p) {
 507                 case '&':
 508                         op = LDB_OP_AND;
 509                         break;
 510                 case '|':
 511                         op = LDB_OP_OR;
 512                         break;
 513                 default:
 514                         return NULL;
 515         }
 516         p++;
 517
 518         while (isspace((unsigned char)*p)) p++;
 519
 520         ret = talloc(mem_ctx, struct ldb_parse_tree);
 521         if (!ret) {
 522                 errno = ENOMEM;
 523                 return NULL;
 524         }
 525
 526         ret->operation = op;
 527         ret->u.list.num_elements = 1;
 528         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 529         if (!ret->u.list.elements) {
 530                 errno = ENOMEM;
 531                 talloc_free(ret);
 532                 return NULL;
 533         }
 534
 535         ret->u.list.elements[0] =
 536                 ldb_parse_filter(ret->u.list.elements, &p, depth, max_depth);
 537         if (!ret->u.list.elements[0]) {
 538                 talloc_free(ret);
 539                 return NULL;
 540         }
 541
 542         while (isspace((unsigned char)*p)) p++;
 543
 544         while (*p) {
 545                 struct ldb_parse_tree **e;
 546                 if (*p == ')') {
 547                         break;
 548                 }
 549
 550                 next = ldb_parse_filter(
 551                         ret->u.list.elements, &p, depth, max_depth);
 552                 if (next == NULL) {
 553                         /* an invalid filter element */
 554                         talloc_free(ret);
 555                         return NULL;
 556                 }
 557                 e = talloc_realloc(ret, ret->u.list.elements,
 558                                      struct ldb_parse_tree *,
 559                                      ret->u.list.num_elements + 1);
 560                 if (!e) {
 561                         errno = ENOMEM;
 562                         talloc_free(ret);
 563                         return NULL;
 564                 }
 565                 ret->u.list.elements = e;
 566                 ret->u.list.elements[ret->u.list.num_elements] = next;
 567                 ret->u.list.num_elements++;
 568                 while (isspace((unsigned char)*p)) p++;
 569         }
 570
 571         *s = p;
 572
 573         return ret;
 574 }
 575
 576
 577 /*
 578   <not> ::= '!' <filter>
 579 */
 580 static struct ldb_parse_tree *ldb_parse_not(
 581         TALLOC_CTX *mem_ctx,
 582         const char **s,
 583         unsigned depth,
 584         unsigned max_depth)
 585 {
 586         struct ldb_parse_tree *ret;
 587         const char *p = *s;
 588
 589         if (*p != '!') {
 590                 return NULL;
 591         }
 592         p++;
 593
 594         ret = talloc(mem_ctx, struct ldb_parse_tree);
 595         if (!ret) {
 596                 errno = ENOMEM;
 597                 return NULL;
 598         }
 599
 600         ret->operation = LDB_OP_NOT;
 601         ret->u.isnot.child = ldb_parse_filter(ret, &p, depth, max_depth);
 602         if (!ret->u.isnot.child) {
 603                 talloc_free(ret);
 604                 return NULL;
 605         }
 606
 607         *s = p;
 608
 609         return ret;
 610 }
 611
 612 /*
 613   parse a filtercomp
 614   <filtercomp> ::= <and> | <or> | <not> | <simple>
 615 */
 616 static struct ldb_parse_tree *ldb_parse_filtercomp(
 617         TALLOC_CTX *mem_ctx,
 618         const char **s,
 619         unsigned depth,
 620         unsigned max_depth)
 621 {
 622         struct ldb_parse_tree *ret;
 623         const char *p = *s;
 624
 625         while (isspace((unsigned char)*p)) p++;
 626
 627         switch (*p) {
 628         case '&':
 629                 ret = ldb_parse_filterlist(mem_ctx, &p, depth, max_depth);
 630                 break;
 631
 632         case '|':
 633                 ret = ldb_parse_filterlist(mem_ctx, &p, depth, max_depth);
 634                 break;
 635
 636         case '!':
 637                 ret = ldb_parse_not(mem_ctx, &p, depth, max_depth);
 638                 break;
 639
 640         case '(':
 641         case ')':
 642                 return NULL;
 643
 644         default:
 645                 ret = ldb_parse_simple(mem_ctx, &p);
 646
 647         }
 648
 649         *s = p;
 650         return ret;
 651 }
 652
 653 /*
 654   <filter> ::= '(' <filtercomp> ')'
 655 */
 656 static struct ldb_parse_tree *ldb_parse_filter(
 657         TALLOC_CTX *mem_ctx,
 658         const char **s,
 659         unsigned depth,
 660         unsigned max_depth)
 661 {
 662         struct ldb_parse_tree *ret;
 663         const char *p = *s;
 664
 665         /*
 666          * Check the depth of the parse tree, and reject the input if
 667          * max_depth exceeded. This avoids stack overflow
 668          * issues.
 669          */
 670         if (depth > max_depth) {
 671                 return NULL;
 672         }
 673         depth++;
 674
 675         if (*p != '(') {
 676                 return NULL;
 677         }
 678         p++;
 679
 680         ret = ldb_parse_filtercomp(mem_ctx, &p, depth, max_depth);
 681
 682         if (*p != ')') {
 683                 return NULL;
 684         }
 685         p++;
 686
 687         while (isspace((unsigned char)*p)) {
 688                 p++;
 689         }
 690
 691         *s = p;
 692
 693         return ret;
 694 }
 695
 696
 697 /*
 698   main parser entry point. Takes a search string and returns a parse tree
 699
 700   expression ::= <simple> | <filter>
 701 */
 702 struct ldb_parse_tree *ldb_parse_tree(TALLOC_CTX *mem_ctx, const char *s)
 703 {
 704         unsigned depth = 0;
 705
 706         while (s && isspace((unsigned char)*s)) s++;
 707
 708         if (s == NULL || *s == 0) {
 709                 s = "(|(objectClass=*)(distinguishedName=*))";
 710         }
 711
 712         if (*s == '(') {
 713                 return ldb_parse_filter(
 714                         mem_ctx, &s, depth, LDB_MAX_PARSE_TREE_DEPTH);
 715         }
 716
 717         return ldb_parse_simple(mem_ctx, &s);
 718 }
 719
 720
 721 /*
 722   construct a ldap parse filter given a parse tree
 723 */
 724 char *ldb_filter_from_tree(TALLOC_CTX *mem_ctx, const struct ldb_parse_tree *tree)
 725 {
 726         char *s, *s2, *ret;
 727         unsigned int i;
 728
 729         if (tree == NULL) {
 730                 return NULL;
 731         }
 732
 733         switch (tree->operation) {
 734         case LDB_OP_AND:
 735         case LDB_OP_OR:
 736                 ret = talloc_asprintf(mem_ctx, "(%c", tree->operation==LDB_OP_AND?'&':'|');
 737                 if (ret == NULL) return NULL;
 738                 for (i=0;i<tree->u.list.num_elements;i++) {
 739                         s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
 740                         if (s == NULL) {
 741                                 talloc_free(ret);
 742                                 return NULL;
 743                         }
 744                         s2 = talloc_asprintf_append(ret, "%s", s);
 745                         talloc_free(s);
 746                         if (s2 == NULL) {
 747                                 talloc_free(ret);
 748                                 return NULL;
 749                         }
 750                         ret = s2;
 751                 }
 752                 s = talloc_asprintf_append(ret, ")");
 753                 if (s == NULL) {
 754                         talloc_free(ret);
 755                         return NULL;
 756                 }
 757                 return s;
 758         case LDB_OP_NOT:
 759                 s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
 760                 if (s == NULL) return NULL;
 761
 762                 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 763                 talloc_free(s);
 764                 return ret;
 765         case LDB_OP_EQUALITY:
 766                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 767                 if (s == NULL) return NULL;
 768                 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
 769                                       tree->u.equality.attr, s);
 770                 talloc_free(s);
 771                 return ret;
 772         case LDB_OP_SUBSTRING:
 773                 ret = talloc_asprintf(mem_ctx, "(%s=%s", tree->u.substring.attr,
 774                                       tree->u.substring.start_with_wildcard?"*":"");
 775                 if (ret == NULL) return NULL;
 776                 for (i = 0; tree->u.substring.chunks && tree->u.substring.chunks[i]; i++) {
 777                         s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
 778                         if (s2 == NULL) {
 779                                 talloc_free(ret);
 780                                 return NULL;
 781                         }
 782                         if (tree->u.substring.chunks[i+1] ||
 783                             tree->u.substring.end_with_wildcard) {
 784                                 s = talloc_asprintf_append(ret, "%s*", s2);
 785                         } else {
 786                                 s = talloc_asprintf_append(ret, "%s", s2);
 787                         }
 788                         if (s == NULL) {
 789                                 talloc_free(ret);
 790                                 return NULL;
 791                         }
 792                         ret = s;
 793                 }
 794                 s = talloc_asprintf_append(ret, ")");
 795                 if (s == NULL) {
 796                         talloc_free(ret);
 797                         return NULL;
 798                 }
 799                 ret = s;
 800                 return ret;
 801         case LDB_OP_GREATER:
 802                 s = ldb_binary_encode(mem_ctx, tree->u.comparison.value);
 803                 if (s == NULL) return NULL;
 804                 ret = talloc_asprintf(mem_ctx, "(%s>=%s)",
 805                                       tree->u.comparison.attr, s);
 806                 talloc_free(s);
 807                 return ret;
 808         case LDB_OP_LESS:
 809                 s = ldb_binary_encode(mem_ctx, tree->u.comparison.value);
 810                 if (s == NULL) return NULL;
 811                 ret = talloc_asprintf(mem_ctx, "(%s<=%s)",
 812                                       tree->u.comparison.attr, s);
 813                 talloc_free(s);
 814                 return ret;
 815         case LDB_OP_PRESENT:
 816                 ret = talloc_asprintf(mem_ctx, "(%s=*)", tree->u.present.attr);
 817                 return ret;
 818         case LDB_OP_APPROX:
 819                 s = ldb_binary_encode(mem_ctx, tree->u.comparison.value);
 820                 if (s == NULL) return NULL;
 821                 ret = talloc_asprintf(mem_ctx, "(%s~=%s)",
 822                                       tree->u.comparison.attr, s);
 823                 talloc_free(s);
 824                 return ret;
 825         case LDB_OP_EXTENDED:
 826                 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
 827                 if (s == NULL) return NULL;
 828                 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
 829                                       tree->u.extended.attr?tree->u.extended.attr:"",
 830                                       tree->u.extended.dnAttributes?":dn":"",
 831                                       tree->u.extended.rule_id?":":"",
 832                                       tree->u.extended.rule_id?tree->u.extended.rule_id:"",
 833                                       s);
 834                 talloc_free(s);
 835                 return ret;
 836         }
 837
 838         return NULL;
 839 }
 840
 841
 842 /*
 843   walk a parse tree, calling the provided callback on each node
 844 */
 845 int ldb_parse_tree_walk(struct ldb_parse_tree *tree,
 846                         int (*callback)(struct ldb_parse_tree *tree, void *),
 847                         void *private_context)
 848 {
 849         unsigned int i;
 850         int ret;
 851
 852         ret = callback(tree, private_context);
 853         if (ret != LDB_SUCCESS) {
 854                 return ret;
 855         }
 856
 857         switch (tree->operation) {
 858         case LDB_OP_AND:
 859         case LDB_OP_OR:
 860                 for (i=0;i<tree->u.list.num_elements;i++) {
 861                         ret = ldb_parse_tree_walk(tree->u.list.elements[i], callback, private_context);
 862                         if (ret != LDB_SUCCESS) {
 863                                 return ret;
 864                         }
 865                 }
 866                 break;
 867         case LDB_OP_NOT:
 868                 ret = ldb_parse_tree_walk(tree->u.isnot.child, callback, private_context);
 869                 if (ret != LDB_SUCCESS) {
 870                         return ret;
 871                 }
 872                 break;
 873         case LDB_OP_EQUALITY:
 874         case LDB_OP_GREATER:
 875         case LDB_OP_LESS:
 876         case LDB_OP_APPROX:
 877         case LDB_OP_SUBSTRING:
 878         case LDB_OP_PRESENT:
 879         case LDB_OP_EXTENDED:
 880                 break;
 881         }
 882         return LDB_SUCCESS;
 883 }
 884
 885 struct parse_tree_attr_replace_ctx {
 886         const char *attr;
 887         const char *replace;
 888 };
 889
 890 /*
 891   callback for ldb_parse_tree_attr_replace()
 892  */
 893 static int parse_tree_attr_replace(struct ldb_parse_tree *tree, void *private_context)
 894 {
 895         struct parse_tree_attr_replace_ctx *ctx = private_context;
 896         switch (tree->operation) {
 897         case LDB_OP_EQUALITY:
 898                 if (ldb_attr_cmp(tree->u.equality.attr, ctx->attr) == 0) {
 899                         tree->u.equality.attr = ctx->replace;
 900                 }
 901                 break;
 902         case LDB_OP_GREATER:
 903         case LDB_OP_LESS:
 904         case LDB_OP_APPROX:
 905                 if (ldb_attr_cmp(tree->u.comparison.attr, ctx->attr) == 0) {
 906                         tree->u.comparison.attr = ctx->replace;
 907                 }
 908                 break;
 909         case LDB_OP_SUBSTRING:
 910                 if (ldb_attr_cmp(tree->u.substring.attr, ctx->attr) == 0) {
 911                         tree->u.substring.attr = ctx->replace;
 912                 }
 913                 break;
 914         case LDB_OP_PRESENT:
 915                 if (ldb_attr_cmp(tree->u.present.attr, ctx->attr) == 0) {
 916                         tree->u.present.attr = ctx->replace;
 917                 }
 918                 break;
 919         case LDB_OP_EXTENDED:
 920                 if (tree->u.extended.attr &&
 921                     ldb_attr_cmp(tree->u.extended.attr, ctx->attr) == 0) {
 922                         tree->u.extended.attr = ctx->replace;
 923                 }
 924                 break;
 925         default:
 926                 break;
 927         }
 928         return LDB_SUCCESS;
 929 }
 930
 931 /*
 932   replace any occurrences of an attribute name in the parse tree with a
 933   new name
 934 */
 935 void ldb_parse_tree_attr_replace(struct ldb_parse_tree *tree,
 936                                  const char *attr,
 937                                  const char *replace)
 938 {
 939         struct parse_tree_attr_replace_ctx ctx;
 940
 941         ctx.attr    = attr;
 942         ctx.replace = replace;
 943
 944         ldb_parse_tree_walk(tree, parse_tree_attr_replace, &ctx);
 945 }
 946
 947 /*
 948   shallow copy a tree - copying only the elements array so that the caller
 949   can safely add new elements without changing the message
 950 */
 951 struct ldb_parse_tree *ldb_parse_tree_copy_shallow(TALLOC_CTX *mem_ctx,
 952                                                    const struct ldb_parse_tree *ot)
 953 {
 954         unsigned int i;
 955         struct ldb_parse_tree *nt;
 956
 957         nt = talloc(mem_ctx, struct ldb_parse_tree);
 958         if (!nt) {
 959                 return NULL;
 960         }
 961
 962         *nt = *ot;
 963
 964         switch (ot->operation) {
 965         case LDB_OP_AND:
 966         case LDB_OP_OR:
 967                 nt->u.list.elements = talloc_array(nt, struct ldb_parse_tree *,
 968                                                    ot->u.list.num_elements);
 969                 if (!nt->u.list.elements) {
 970                         talloc_free(nt);
 971                         return NULL;
 972                 }
 973
 974                 for (i=0;i<ot->u.list.num_elements;i++) {
 975                         nt->u.list.elements[i] =
 976                                 ldb_parse_tree_copy_shallow(nt->u.list.elements,
 977                                                 ot->u.list.elements[i]);
 978                         if (!nt->u.list.elements[i]) {
 979                                 talloc_free(nt);
 980                                 return NULL;
 981                         }
 982                 }
 983                 break;
 984         case LDB_OP_NOT:
 985                 nt->u.isnot.child = ldb_parse_tree_copy_shallow(nt,
 986                                                         ot->u.isnot.child);
 987                 if (!nt->u.isnot.child) {
 988                         talloc_free(nt);
 989                         return NULL;
 990                 }
 991                 break;
 992         case LDB_OP_EQUALITY:
 993         case LDB_OP_GREATER:
 994         case LDB_OP_LESS:
 995         case LDB_OP_APPROX:
 996         case LDB_OP_SUBSTRING:
 997         case LDB_OP_PRESENT:
 998         case LDB_OP_EXTENDED:
 999                 break;
1000         }
1001
1002         return nt;
1003 }
1004
1005 /* Get the attribute (if any) associated with the top node of a parse tree. */
1006 const char *ldb_parse_tree_get_attr(const struct ldb_parse_tree *tree)
1007 {
1008         switch (tree->operation) {
1009         case LDB_OP_AND:
1010         case LDB_OP_OR:
1011         case LDB_OP_NOT:
1012                 return NULL;
1013         case LDB_OP_EQUALITY:
1014                 return tree->u.equality.attr;
1015         case LDB_OP_SUBSTRING:
1016                 return tree->u.substring.attr;
1017         case LDB_OP_GREATER:
1018         case LDB_OP_LESS:
1019         case LDB_OP_APPROX:
1020                 return tree->u.comparison.attr;
1021         case LDB_OP_PRESENT:
1022                 return tree->u.present.attr;
1023         case LDB_OP_EXTENDED:
1024                 return tree->u.extended.attr;
1025         }
1026
1027         return NULL;
1028 }