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