lib/ldb/common/ldb_parse.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Tridgell  2004
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 3 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb expression parsing
  28  *
  29  *  Description: parse LDAP-like search expressions
  30  *
  31  *  Author: Andrew Tridgell
  32  */
  33
  34 /*
  35   TODO:
  36       - add RFC2254 binary string handling
  37       - possibly add ~=, <= and >= handling
  38       - expand the test suite
  39       - add better parse error handling
  40
  41 */
  42
  43 #include "ldb_private.h"
  44 #include "system/locale.h"
  45
  46 static int ldb_parse_hex2char(const char *x)
  47 {
  48         if (isxdigit(x[0]) && isxdigit(x[1])) {
  49                 const char h1 = x[0], h2 = x[1];
  50                 int c = 0;
  51
  52                 if (h1 >= 'a') c = h1 - (int)'a' + 10;
  53                 else if (h1 >= 'A') c = h1 - (int)'A' + 10;
  54                 else if (h1 >= '0') c = h1 - (int)'0';
  55                 c = c << 4;
  56                 if (h2 >= 'a') c += h2 - (int)'a' + 10;
  57                 else if (h2 >= 'A') c += h2 - (int)'A' + 10;
  58                 else if (h2 >= '0') c += h2 - (int)'0';
  59
  60                 return c;
  61         }
  62
  63         return -1;
  64 }
  65
  66 /*
  67 a filter is defined by:
  68                <filter> ::= '(' <filtercomp> ')'
  69                <filtercomp> ::= <and> | <or> | <not> | <simple>
  70                <and> ::= '&' <filterlist>
  71                <or> ::= '|' <filterlist>
  72                <not> ::= '!' <filter>
  73                <filterlist> ::= <filter> | <filter> <filterlist>
  74                <simple> ::= <attributetype> <filtertype> <attributevalue>
  75                <filtertype> ::= '=' | '~=' | '<=' | '>='
  76 */
  77
  78 /*
  79    decode a RFC2254 binary string representation of a buffer.
  80    Used in LDAP filters.
  81 */
  82 struct ldb_val ldb_binary_decode(TALLOC_CTX *mem_ctx, const char *str)
  83 {
  84         size_t i, j;
  85         struct ldb_val ret;
  86         size_t slen = str?strlen(str):0;
  87
  88         ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
  89         ret.length = 0;
  90         if (ret.data == NULL) return ret;
  91
  92         for (i=j=0;i<slen;i++) {
  93                 if (str[i] == '\\') {
  94                         int c;
  95
  96                         c = ldb_parse_hex2char(&str[i+1]);
  97                         if (c == -1) {
  98                                 talloc_free(ret.data);
  99                                 memset(&ret, 0, sizeof(ret));
 100                                 return ret;
 101                         }
 102                         ((uint8_t *)ret.data)[j++] = c;
 103                         i += 2;
 104                 } else {
 105                         ((uint8_t *)ret.data)[j++] = str[i];
 106                 }
 107         }
 108         ret.length = j;
 109         ((uint8_t *)ret.data)[j] = 0;
 110
 111         return ret;
 112 }
 113
 114
 115 /*
 116    encode a blob as a RFC2254 binary string, escaping any
 117    non-printable or '\' characters
 118 */
 119 char *ldb_binary_encode(TALLOC_CTX *mem_ctx, struct ldb_val val)
 120 {
 121         size_t i;
 122         char *ret;
 123         size_t len = val.length;
 124         unsigned char *buf = val.data;
 125
 126         for (i=0;i<val.length;i++) {
 127                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 128                         len += 2;
 129                 }
 130         }
 131         ret = talloc_array(mem_ctx, char, len+1);
 132         if (ret == NULL) return NULL;
 133
 134         len = 0;
 135         for (i=0;i<val.length;i++) {
 136                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 137                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 138                         len += 3;
 139                 } else {
 140                         ret[len++] = buf[i];
 141                 }
 142         }
 143
 144         ret[len] = 0;
 145
 146         return ret;
 147 }
 148
 149 /*
 150    encode a string as a RFC2254 binary string, escaping any
 151    non-printable or '\' characters.  This routine is suitable for use
 152    in escaping user data in ldap filters.
 153 */
 154 char *ldb_binary_encode_string(TALLOC_CTX *mem_ctx, const char *string)
 155 {
 156         struct ldb_val val;
 157         if (string == NULL) {
 158                 return NULL;
 159         }
 160         val.data = discard_const_p(uint8_t, string);
 161         val.length = strlen(string);
 162         return ldb_binary_encode(mem_ctx, val);
 163 }
 164
 165 /* find the first matching wildcard */
 166 static char *ldb_parse_find_wildcard(char *value)
 167 {
 168         while (*value) {
 169                 value = strpbrk(value, "\\*");
 170                 if (value == NULL) return NULL;
 171
 172                 if (value[0] == '\\') {
 173                         if (value[1] == '\0') return NULL;
 174                         value += 2;
 175                         continue;
 176                 }
 177
 178                 if (value[0] == '*') return value;
 179         }
 180
 181         return NULL;
 182 }
 183
 184 /* return a NULL terminated list of binary strings representing the value
 185    chunks separated by wildcards that makes the value portion of the filter
 186 */
 187 static struct ldb_val **ldb_wildcard_decode(TALLOC_CTX *mem_ctx, const char *string)
 188 {
 189         struct ldb_val **ret = NULL;
 190         unsigned int val = 0;
 191         char *wc, *str;
 192
 193         wc = talloc_strdup(mem_ctx, string);
 194         if (wc == NULL) return NULL;
 195
 196         while (wc && *wc) {
 197                 str = wc;
 198                 wc = ldb_parse_find_wildcard(str);
 199                 if (wc && *wc) {
 200                         if (wc == str) {
 201                                 wc++;
 202                                 continue;
 203                         }
 204                         *wc = 0;
 205                         wc++;
 206                 }
 207
 208                 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
 209                 if (ret == NULL) return NULL;
 210
 211                 ret[val] = talloc(mem_ctx, struct ldb_val);
 212                 if (ret[val] == NULL) return NULL;
 213
 214                 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
 215                 if ((ret[val])->data == NULL) return NULL;
 216
 217                 val++;
 218         }
 219
 220         if (ret != NULL) {
 221                 ret[val] = NULL;
 222         }
 223
 224         return ret;
 225 }
 226
 227 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *mem_ctx, const char **s);
 228
 229
 230 /*
 231   parse an extended match
 232
 233   possible forms:
 234         (attr:oid:=value)
 235         (attr:dn:oid:=value)
 236         (attr:dn:=value)
 237         (:dn:oid:=value)
 238
 239   the ':dn' part sets the dnAttributes boolean if present
 240   the oid sets the rule_id string
 241
 242 */
 243 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 244                                                  char *attr, char *value)
 245 {
 246         char *p1, *p2;
 247
 248         ret->operation = LDB_OP_EXTENDED;
 249         ret->u.extended.value = ldb_binary_decode(ret, value);
 250         if (ret->u.extended.value.data == NULL) goto failed;
 251
 252         p1 = strchr(attr, ':');
 253         if (p1 == NULL) goto failed;
 254         p2 = strchr(p1+1, ':');
 255
 256         *p1 = 0;
 257         if (p2) *p2 = 0;
 258
 259         ret->u.extended.attr = attr;
 260         if (strcmp(p1+1, "dn") == 0) {
 261                 ret->u.extended.dnAttributes = 1;
 262                 if (p2) {
 263                         ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 264                         if (ret->u.extended.rule_id == NULL) goto failed;
 265                 } else {
 266                         ret->u.extended.rule_id = NULL;
 267                 }
 268         } else {
 269                 ret->u.extended.dnAttributes = 0;
 270                 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 271                 if (ret->u.extended.rule_id == NULL) goto failed;
 272         }
 273
 274         return ret;
 275
 276 failed:
 277         talloc_free(ret);
 278         return NULL;
 279 }
 280
 281 static enum ldb_parse_op ldb_parse_filtertype(TALLOC_CTX *mem_ctx, char **type, char **value, const char **s)
 282 {
 283         enum ldb_parse_op filter = 0;
 284         char *name, *val, *k;
 285         const char *p = *s;
 286         const char *t, *t1;
 287
 288         /* retrieve attributetype name */
 289         t = p;
 290
 291         if (*p == '@') { /* for internal attributes the first char can be @ */
 292                 p++;
 293         }
 294
 295         while ((isascii(*p) && isalnum((unsigned char)*p)) || (*p == '-') || (*p == '.')) {
 296                 /* attribute names can only be alphanums */
 297                 p++;
 298         }
 299
 300         if (*p == ':') { /* but extended searches have : and . chars too */
 301                 p = strstr(p, ":=");
 302                 if (p == NULL) { /* malformed attribute name */
 303                         return 0;
 304                 }
 305         }
 306
 307         t1 = p;
 308
 309         while (isspace((unsigned char)*p)) p++;
 310
 311         if (!strchr("=<>~:", *p)) {
 312                 return 0;
 313         }
 314
 315         /* save name */
 316         name = (char *)talloc_memdup(mem_ctx, t, t1 - t + 1);
 317         if (name == NULL) return 0;
 318         name[t1 - t] = '\0';
 319
 320         /* retrieve filtertype */
 321
 322         if (*p == '=') {
 323                 filter = LDB_OP_EQUALITY;
 324         } else if (*(p + 1) == '=') {
 325                 switch (*p) {
 326                 case '<':
 327                         filter = LDB_OP_LESS;
 328                         p++;
 329                         break;
 330                 case '>':
 331                         filter = LDB_OP_GREATER;
 332                         p++;
 333                         break;
 334                 case '~':
 335                         filter = LDB_OP_APPROX;
 336                         p++;
 337                         break;
 338                 case ':':
 339                         filter = LDB_OP_EXTENDED;
 340                         p++;
 341                         break;
 342                 }
 343         }
 344         if (!filter) {
 345                 talloc_free(name);
 346                 return filter;
 347         }
 348         p++;
 349
 350         while (isspace((unsigned char)*p)) p++;
 351
 352         /* retrieve value */
 353         t = p;
 354
 355         while (*p && ((*p != ')') || ((*p == ')') && (*(p - 1) == '\\')))) p++;
 356
 357         val = (char *)talloc_memdup(mem_ctx, t, p - t + 1);
 358         if (val == NULL) {
 359                 talloc_free(name);
 360                 return 0;
 361         }
 362         val[p - t] = '\0';
 363
 364         k = &(val[p - t]);
 365
 366         /* remove trailing spaces from value */
 367         while ((k > val) && (isspace((unsigned char)*(k - 1)))) k--;
 368         *k = '\0';
 369
 370         *type = name;
 371         *value = val;
 372         *s = p;
 373         return filter;
 374 }
 375
 376 /*
 377   <simple> ::= <attributetype> <filtertype> <attributevalue>
 378 */
 379 static struct ldb_parse_tree *ldb_parse_simple(TALLOC_CTX *mem_ctx, const char **s)
 380 {
 381         char *attr, *value;
 382         struct ldb_parse_tree *ret;
 383         enum ldb_parse_op filtertype;
 384
 385         ret = talloc(mem_ctx, struct ldb_parse_tree);
 386         if (!ret) {
 387                 errno = ENOMEM;
 388                 return NULL;
 389         }
 390
 391         filtertype = ldb_parse_filtertype(ret, &attr, &value, s);
 392         if (!filtertype) {
 393                 talloc_free(ret);
 394                 return NULL;
 395         }
 396
 397         switch (filtertype) {
 398
 399                 case LDB_OP_PRESENT:
 400                         ret->operation = LDB_OP_PRESENT;
 401                         ret->u.present.attr = attr;
 402                         break;
 403
 404                 case LDB_OP_EQUALITY:
 405
 406                         if (strcmp(value, "*") == 0) {
 407                                 ret->operation = LDB_OP_PRESENT;
 408                                 ret->u.present.attr = attr;
 409                                 break;
 410                         }
 411
 412                         if (ldb_parse_find_wildcard(value) != NULL) {
 413                                 ret->operation = LDB_OP_SUBSTRING;
 414                                 ret->u.substring.attr = attr;
 415                                 ret->u.substring.start_with_wildcard = 0;
 416                                 ret->u.substring.end_with_wildcard = 0;
 417                                 ret->u.substring.chunks = ldb_wildcard_decode(ret, value);
 418                                 if (ret->u.substring.chunks == NULL){
 419                                         talloc_free(ret);
 420                                         return NULL;
 421                                 }
 422                                 if (value[0] == '*')
 423                                         ret->u.substring.start_with_wildcard = 1;
 424                                 if (value[strlen(value) - 1] == '*')
 425                                         ret->u.substring.end_with_wildcard = 1;
 426                                 talloc_free(value);
 427
 428                                 break;
 429                         }
 430
 431                         ret->operation = LDB_OP_EQUALITY;
 432                         ret->u.equality.attr = attr;
 433                         ret->u.equality.value = ldb_binary_decode(ret, value);
 434                         if (ret->u.equality.value.data == NULL) {
 435                                 talloc_free(ret);
 436                                 return NULL;
 437                         }
 438                         talloc_free(value);
 439                         break;
 440
 441                 case LDB_OP_GREATER:
 442                         ret->operation = LDB_OP_GREATER;
 443                         ret->u.comparison.attr = attr;
 444                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 445                         if (ret->u.comparison.value.data == NULL) {
 446                                 talloc_free(ret);
 447                                 return NULL;
 448                         }
 449                         talloc_free(value);
 450                         break;
 451
 452                 case LDB_OP_LESS:
 453                         ret->operation = LDB_OP_LESS;
 454                         ret->u.comparison.attr = attr;
 455                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 456                         if (ret->u.comparison.value.data == NULL) {
 457                                 talloc_free(ret);
 458                                 return NULL;
 459                         }
 460                         talloc_free(value);
 461                         break;
 462
 463                 case LDB_OP_APPROX:
 464                         ret->operation = LDB_OP_APPROX;
 465                         ret->u.comparison.attr = attr;
 466                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 467                         if (ret->u.comparison.value.data == NULL) {
 468                                 talloc_free(ret);
 469                                 return NULL;
 470                         }
 471                         talloc_free(value);
 472                         break;
 473
 474                 case LDB_OP_EXTENDED:
 475
 476                         ret = ldb_parse_extended(ret, attr, value);
 477                         break;
 478
 479                 default:
 480                         talloc_free(ret);
 481                         return NULL;
 482         }
 483
 484         return ret;
 485 }
 486
 487
 488 /*
 489   parse a filterlist
 490   <and> ::= '&' <filterlist>
 491   <or> ::= '|' <filterlist>
 492   <filterlist> ::= <filter> | <filter> <filterlist>
 493 */
 494 static struct ldb_parse_tree *ldb_parse_filterlist(TALLOC_CTX *mem_ctx, const char **s)
 495 {
 496         struct ldb_parse_tree *ret, *next;
 497         enum ldb_parse_op op;
 498         const char *p = *s;
 499
 500         switch (*p) {
 501                 case '&':
 502                         op = LDB_OP_AND;
 503                         break;
 504                 case '|':
 505                         op = LDB_OP_OR;
 506                         break;
 507                 default:
 508                         return NULL;
 509         }
 510         p++;
 511
 512         while (isspace((unsigned char)*p)) p++;
 513
 514         ret = talloc(mem_ctx, struct ldb_parse_tree);
 515         if (!ret) {
 516                 errno = ENOMEM;
 517                 return NULL;
 518         }
 519
 520         ret->operation = op;
 521         ret->u.list.num_elements = 1;
 522         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 523         if (!ret->u.list.elements) {
 524                 errno = ENOMEM;
 525                 talloc_free(ret);
 526                 return NULL;
 527         }
 528
 529         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &p);
 530         if (!ret->u.list.elements[0]) {
 531                 talloc_free(ret);
 532                 return NULL;
 533         }
 534
 535         while (isspace((unsigned char)*p)) p++;
 536
 537         while (*p && (next = ldb_parse_filter(ret->u.list.elements, &p))) {
 538                 struct ldb_parse_tree **e;
 539                 e = talloc_realloc(ret, ret->u.list.elements,
 540                                      struct ldb_parse_tree *,
 541                                      ret->u.list.num_elements + 1);
 542                 if (!e) {
 543                         errno = ENOMEM;
 544                         talloc_free(ret);
 545                         return NULL;
 546                 }
 547                 ret->u.list.elements = e;
 548                 ret->u.list.elements[ret->u.list.num_elements] = next;
 549                 ret->u.list.num_elements++;
 550                 while (isspace((unsigned char)*p)) p++;
 551         }
 552
 553         *s = p;
 554
 555         return ret;
 556 }
 557
 558
 559 /*
 560   <not> ::= '!' <filter>
 561 */
 562 static struct ldb_parse_tree *ldb_parse_not(TALLOC_CTX *mem_ctx, const char **s)
 563 {
 564         struct ldb_parse_tree *ret;
 565         const char *p = *s;
 566
 567         if (*p != '!') {
 568                 return NULL;
 569         }
 570         p++;
 571
 572         ret = talloc(mem_ctx, struct ldb_parse_tree);
 573         if (!ret) {
 574                 errno = ENOMEM;
 575                 return NULL;
 576         }
 577
 578         ret->operation = LDB_OP_NOT;
 579         ret->u.isnot.child = ldb_parse_filter(ret, &p);
 580         if (!ret->u.isnot.child) {
 581                 talloc_free(ret);
 582                 return NULL;
 583         }
 584
 585         *s = p;
 586
 587         return ret;
 588 }
 589
 590 /*
 591   parse a filtercomp
 592   <filtercomp> ::= <and> | <or> | <not> | <simple>
 593 */
 594 static struct ldb_parse_tree *ldb_parse_filtercomp(TALLOC_CTX *mem_ctx, const char **s)
 595 {
 596         struct ldb_parse_tree *ret;
 597         const char *p = *s;
 598
 599         while (isspace((unsigned char)*p)) p++;
 600
 601         switch (*p) {
 602         case '&':
 603                 ret = ldb_parse_filterlist(mem_ctx, &p);
 604                 break;
 605
 606         case '|':
 607                 ret = ldb_parse_filterlist(mem_ctx, &p);
 608                 break;
 609
 610         case '!':
 611                 ret = ldb_parse_not(mem_ctx, &p);
 612                 break;
 613
 614         case '(':
 615         case ')':
 616                 return NULL;
 617
 618         default:
 619                 ret = ldb_parse_simple(mem_ctx, &p);
 620
 621         }
 622
 623         *s = p;
 624         return ret;
 625 }
 626
 627
 628 /*
 629   <filter> ::= '(' <filtercomp> ')'
 630 */
 631 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *mem_ctx, const char **s)
 632 {
 633         struct ldb_parse_tree *ret;
 634         const char *p = *s;
 635
 636         if (*p != '(') {
 637                 return NULL;
 638         }
 639         p++;
 640
 641         ret = ldb_parse_filtercomp(mem_ctx, &p);
 642
 643         if (*p != ')') {
 644                 return NULL;
 645         }
 646         p++;
 647
 648         while (isspace((unsigned char)*p)) {
 649                 p++;
 650         }
 651
 652         *s = p;
 653
 654         return ret;
 655 }
 656
 657
 658 /*
 659   main parser entry point. Takes a search string and returns a parse tree
 660
 661   expression ::= <simple> | <filter>
 662 */
 663 struct ldb_parse_tree *ldb_parse_tree(TALLOC_CTX *mem_ctx, const char *s)
 664 {
 665         if (s == NULL || *s == 0) {
 666                 s = "(|(objectClass=*)(distinguishedName=*))";
 667         }
 668
 669         while (isspace((unsigned char)*s)) s++;
 670
 671         if (*s == '(') {
 672                 return ldb_parse_filter(mem_ctx, &s);
 673         }
 674
 675         return ldb_parse_simple(mem_ctx, &s);
 676 }
 677
 678
 679 /*
 680   construct a ldap parse filter given a parse tree
 681 */
 682 char *ldb_filter_from_tree(TALLOC_CTX *mem_ctx, const struct ldb_parse_tree *tree)
 683 {
 684         char *s, *s2, *ret;
 685         unsigned int i;
 686
 687         if (tree == NULL) {
 688                 return NULL;
 689         }
 690
 691         switch (tree->operation) {
 692         case LDB_OP_AND:
 693         case LDB_OP_OR:
 694                 ret = talloc_asprintf(mem_ctx, "(%c", tree->operation==LDB_OP_AND?'&':'|');
 695                 if (ret == NULL) return NULL;
 696                 for (i=0;i<tree->u.list.num_elements;i++) {
 697                         s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
 698                         if (s == NULL) {
 699                                 talloc_free(ret);
 700                                 return NULL;
 701                         }
 702                         s2 = talloc_asprintf_append(ret, "%s", s);
 703                         talloc_free(s);
 704                         if (s2 == NULL) {
 705                                 talloc_free(ret);
 706                                 return NULL;
 707                         }
 708                         ret = s2;
 709                 }
 710                 s = talloc_asprintf_append(ret, ")");
 711                 if (s == NULL) {
 712                         talloc_free(ret);
 713                         return NULL;
 714                 }
 715                 return s;
 716         case LDB_OP_NOT:
 717                 s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
 718                 if (s == NULL) return NULL;
 719
 720                 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 721                 talloc_free(s);
 722                 return ret;
 723         case LDB_OP_EQUALITY:
 724                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 725                 if (s == NULL) return NULL;
 726                 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
 727                                       tree->u.equality.attr, s);
 728                 talloc_free(s);
 729                 return ret;
 730         case LDB_OP_SUBSTRING:
 731                 ret = talloc_asprintf(mem_ctx, "(%s=%s", tree->u.substring.attr,
 732                                       tree->u.substring.start_with_wildcard?"*":"");
 733                 if (ret == NULL) return NULL;
 734                 for (i = 0; tree->u.substring.chunks[i]; i++) {
 735                         s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
 736                         if (s2 == NULL) {
 737                                 talloc_free(ret);
 738                                 return NULL;
 739                         }
 740                         if (tree->u.substring.chunks[i+1] ||
 741                             tree->u.substring.end_with_wildcard) {
 742                                 s = talloc_asprintf_append(ret, "%s*", s2);
 743                         } else {
 744                                 s = talloc_asprintf_append(ret, "%s", s2);
 745                         }
 746                         if (s == NULL) {
 747                                 talloc_free(ret);
 748                                 return NULL;
 749                         }
 750                         ret = s;
 751                 }
 752                 s = talloc_asprintf_append(ret, ")");
 753                 if (s == NULL) {
 754                         talloc_free(ret);
 755                         return NULL;
 756                 }
 757                 ret = s;
 758                 return ret;
 759         case LDB_OP_GREATER:
 760                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 761                 if (s == NULL) return NULL;
 762                 ret = talloc_asprintf(mem_ctx, "(%s>=%s)",
 763                                       tree->u.equality.attr, s);
 764                 talloc_free(s);
 765                 return ret;
 766         case LDB_OP_LESS:
 767                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 768                 if (s == NULL) return NULL;
 769                 ret = talloc_asprintf(mem_ctx, "(%s<=%s)",
 770                                       tree->u.equality.attr, s);
 771                 talloc_free(s);
 772                 return ret;
 773         case LDB_OP_PRESENT:
 774                 ret = talloc_asprintf(mem_ctx, "(%s=*)", tree->u.present.attr);
 775                 return ret;
 776         case LDB_OP_APPROX:
 777                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 778                 if (s == NULL) return NULL;
 779                 ret = talloc_asprintf(mem_ctx, "(%s~=%s)",
 780                                       tree->u.equality.attr, s);
 781                 talloc_free(s);
 782                 return ret;
 783         case LDB_OP_EXTENDED:
 784                 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
 785                 if (s == NULL) return NULL;
 786                 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
 787                                       tree->u.extended.attr?tree->u.extended.attr:"",
 788                                       tree->u.extended.dnAttributes?":dn":"",
 789                                       tree->u.extended.rule_id?":":"",
 790                                       tree->u.extended.rule_id?tree->u.extended.rule_id:"",
 791                                       s);
 792                 talloc_free(s);
 793                 return ret;
 794         }
 795
 796         return NULL;
 797 }
 798
 799
 800 /*
 801   replace any occurrences of an attribute name in the parse tree with a
 802   new name
 803 */
 804 void ldb_parse_tree_attr_replace(struct ldb_parse_tree *tree,
 805                                  const char *attr,
 806                                  const char *replace)
 807 {
 808         unsigned int i;
 809         switch (tree->operation) {
 810         case LDB_OP_AND:
 811         case LDB_OP_OR:
 812                 for (i=0;i<tree->u.list.num_elements;i++) {
 813                         ldb_parse_tree_attr_replace(tree->u.list.elements[i],
 814                                                     attr, replace);
 815                 }
 816                 break;
 817         case LDB_OP_NOT:
 818                 ldb_parse_tree_attr_replace(tree->u.isnot.child, attr, replace);
 819                 break;
 820         case LDB_OP_EQUALITY:
 821         case LDB_OP_GREATER:
 822         case LDB_OP_LESS:
 823         case LDB_OP_APPROX:
 824                 if (ldb_attr_cmp(tree->u.equality.attr, attr) == 0) {
 825                         tree->u.equality.attr = replace;
 826                 }
 827                 break;
 828         case LDB_OP_SUBSTRING:
 829                 if (ldb_attr_cmp(tree->u.substring.attr, attr) == 0) {
 830                         tree->u.substring.attr = replace;
 831                 }
 832                 break;
 833         case LDB_OP_PRESENT:
 834                 if (ldb_attr_cmp(tree->u.present.attr, attr) == 0) {
 835                         tree->u.present.attr = replace;
 836                 }
 837                 break;
 838         case LDB_OP_EXTENDED:
 839                 if (tree->u.extended.attr &&
 840                     ldb_attr_cmp(tree->u.extended.attr, attr) == 0) {
 841                         tree->u.extended.attr = replace;
 842                 }
 843                 break;
 844         }
 845 }
 846
 847 /*
 848   shallow copy a tree - copying only the elements array so that the caller
 849   can safely add new elements without changing the message
 850 */
 851 struct ldb_parse_tree *ldb_parse_tree_copy_shallow(TALLOC_CTX *mem_ctx,
 852                                                    const struct ldb_parse_tree *ot)
 853 {
 854         unsigned int i;
 855         struct ldb_parse_tree *nt;
 856
 857         nt = talloc(mem_ctx, struct ldb_parse_tree);
 858         if (!nt) {
 859                 return NULL;
 860         }
 861
 862         *nt = *ot;
 863
 864         switch (ot->operation) {
 865         case LDB_OP_AND:
 866         case LDB_OP_OR:
 867                 nt->u.list.elements = talloc_array(nt, struct ldb_parse_tree *,
 868                                                    ot->u.list.num_elements);
 869                 if (!nt->u.list.elements) {
 870                         talloc_free(nt);
 871                         return NULL;
 872                 }
 873
 874                 for (i=0;i<ot->u.list.num_elements;i++) {
 875                         nt->u.list.elements[i] =
 876                                 ldb_parse_tree_copy_shallow(nt->u.list.elements,
 877                                                 ot->u.list.elements[i]);
 878                         if (!nt->u.list.elements[i]) {
 879                                 talloc_free(nt);
 880                                 return NULL;
 881                         }
 882                 }
 883                 break;
 884         case LDB_OP_NOT:
 885                 nt->u.isnot.child = ldb_parse_tree_copy_shallow(nt,
 886                                                         ot->u.isnot.child);
 887                 if (!nt->u.isnot.child) {
 888                         talloc_free(nt);
 889                         return NULL;
 890                 }
 891                 break;
 892         case LDB_OP_EQUALITY:
 893         case LDB_OP_GREATER:
 894         case LDB_OP_LESS:
 895         case LDB_OP_APPROX:
 896         case LDB_OP_SUBSTRING:
 897         case LDB_OP_PRESENT:
 898         case LDB_OP_EXTENDED:
 899                 break;
 900         }
 901
 902         return nt;
 903 }