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