source/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, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: ldb expression parsing
  29  *
  30  *  Description: parse LDAP-like search expressions
  31  *
  32  *  Author: Andrew Tridgell
  33  */
  34
  35 /*
  36   TODO:
  37       - add RFC2254 binary string handling
  38       - possibly add ~=, <= and >= handling
  39       - expand the test suite
  40       - add better parse error handling
  41
  42 */
  43
  44 #include "includes.h"
  45 #include "ldb/include/includes.h"
  46 #include "system/locale.h"
  47
  48 struct ldb_val ldb_binary_decode(void *mem_ctx, const char *str);
  49
  50 /*
  51 a filter is defined by:
  52                <filter> ::= '(' <filtercomp> ')'
  53                <filtercomp> ::= <and> | <or> | <not> | <simple>
  54                <and> ::= '&' <filterlist>
  55                <or> ::= '|' <filterlist>
  56                <not> ::= '!' <filter>
  57                <filterlist> ::= <filter> | <filter> <filterlist>
  58                <simple> ::= <attributetype> <filtertype> <attributevalue>
  59                <filtertype> ::= '=' | '~=' | '<=' | '>='
  60 */
  61
  62 /*
  63    decode a RFC2254 binary string representation of a buffer.
  64    Used in LDAP filters.
  65 */
  66 struct ldb_val ldb_binary_decode(void *mem_ctx, const char *str)
  67 {
  68         int i, j;
  69         struct ldb_val ret;
  70         int slen = str?strlen(str):0;
  71
  72         ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
  73         ret.length = 0;
  74         if (ret.data == NULL) return ret;
  75
  76         for (i=j=0;i<slen;i++) {
  77                 if (str[i] == '\\') {
  78                         unsigned c;
  79                         if (sscanf(&str[i+1], "%02X", &c) != 1) {
  80                                 talloc_free(ret.data);
  81                                 memset(&ret, 0, sizeof(ret));
  82                                 return ret;
  83                         }
  84                         ((uint8_t *)ret.data)[j++] = c;
  85                         i += 2;
  86                 } else {
  87                         ((uint8_t *)ret.data)[j++] = str[i];
  88                 }
  89         }
  90         ret.length = j;
  91         ((uint8_t *)ret.data)[j] = 0;
  92
  93         return ret;
  94 }
  95
  96
  97 /*
  98    encode a blob as a RFC2254 binary string, escaping any
  99    non-printable or '\' characters
 100 */
 101 char *ldb_binary_encode(void *mem_ctx, struct ldb_val val)
 102 {
 103         int i;
 104         char *ret;
 105         int len = val.length;
 106         unsigned char *buf = val.data;
 107
 108         for (i=0;i<val.length;i++) {
 109                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 110                         len += 2;
 111                 }
 112         }
 113         ret = talloc_array(mem_ctx, char, len+1);
 114         if (ret == NULL) return NULL;
 115
 116         len = 0;
 117         for (i=0;i<val.length;i++) {
 118                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 119                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 120                         len += 3;
 121                 } else {
 122                         ret[len++] = buf[i];
 123                 }
 124         }
 125
 126         ret[len] = 0;
 127
 128         return ret;
 129 }
 130
 131 /*
 132    encode a string as a RFC2254 binary string, escaping any
 133    non-printable or '\' characters.  This routine is suitable for use
 134    in escaping user data in ldap filters.
 135 */
 136 char *ldb_binary_encode_string(void *mem_ctx, const char *string)
 137 {
 138         struct ldb_val val;
 139         val.data = discard_const_p(uint8_t, string);
 140         val.length = strlen(string);
 141         return ldb_binary_encode(mem_ctx, val);
 142 }
 143
 144 /* find the first matching wildcard */
 145 static char *ldb_parse_find_wildcard(char *value)
 146 {
 147         while (*value) {
 148                 value = strpbrk(value, "\\*");
 149                 if (value == NULL) return NULL;
 150
 151                 if (value[0] == '\\') {
 152                         if (value[1] == '\0') return NULL;
 153                         value += 2;
 154                         continue;
 155                 }
 156
 157                 if (value[0] == '*') return value;
 158         }
 159
 160         return NULL;
 161 }
 162
 163 /* return a NULL terminated list of binary strings representing the value
 164    chunks separated by wildcards that makes the value portion of the filter
 165 */
 166 static struct ldb_val **ldb_wildcard_decode(void *mem_ctx, const char *string)
 167 {
 168         struct ldb_val **ret = NULL;
 169         int val = 0;
 170         char *wc, *str;
 171
 172         wc = talloc_strdup(mem_ctx, string);
 173         if (wc == NULL) return NULL;
 174
 175         while (wc && *wc) {
 176                 str = wc;
 177                 wc = ldb_parse_find_wildcard(str);
 178                 if (wc && *wc) {
 179                         if (wc == str) {
 180                                 wc++;
 181                                 continue;
 182                         }
 183                         *wc = 0;
 184                         wc++;
 185                 }
 186
 187                 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
 188                 if (ret == NULL) return NULL;
 189
 190                 ret[val] = talloc(mem_ctx, struct ldb_val);
 191                 if (ret[val] == NULL) return NULL;
 192
 193                 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
 194                 if ((ret[val])->data == NULL) return NULL;
 195
 196                 val++;
 197         }
 198
 199         if (ret != NULL) {
 200                 ret[val] = NULL;
 201         }
 202
 203         return ret;
 204 }
 205
 206 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
 207
 208
 209 /*
 210   parse an extended match
 211
 212   possible forms:
 213         (attr:oid:=value)
 214         (attr:dn:oid:=value)
 215         (attr:dn:=value)
 216         (:dn:oid:=value)
 217
 218   the ':dn' part sets the dnAttributes boolean if present
 219   the oid sets the rule_id string
 220
 221 */
 222 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 223                                                  char *attr, char *value)
 224 {
 225         char *p1, *p2;
 226
 227         ret->operation = LDB_OP_EXTENDED;
 228         ret->u.extended.value = ldb_binary_decode(ret, value);
 229         if (ret->u.extended.value.data == NULL) goto failed;
 230
 231         p1 = strchr(attr, ':');
 232         if (p1 == NULL) goto failed;
 233         p2 = strchr(p1+1, ':');
 234
 235         *p1 = 0;
 236         if (p2) *p2 = 0;
 237
 238         ret->u.extended.attr = attr;
 239         if (strcmp(p1+1, "dn") == 0) {
 240                 ret->u.extended.dnAttributes = 1;
 241                 if (p2) {
 242                         ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 243                         if (ret->u.extended.rule_id == NULL) goto failed;
 244                 } else {
 245                         ret->u.extended.rule_id = NULL;
 246                 }
 247         } else {
 248                 ret->u.extended.dnAttributes = 0;
 249                 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 250                 if (ret->u.extended.rule_id == NULL) goto failed;
 251         }
 252
 253         return ret;
 254
 255 failed:
 256         talloc_free(ret);
 257         return NULL;
 258 }
 259
 260 static enum ldb_parse_op ldb_parse_filtertype(void *mem_ctx, char **type, char **value, const char **s)
 261 {
 262         enum ldb_parse_op filter = 0;
 263         char *name, *val, *k;
 264         const char *p = *s;
 265         const char *t, *t1;
 266
 267         /* retrieve attributetype name */
 268         t = p;
 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         /* retieve 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 }