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