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