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