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