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