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