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