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