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 0;
 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) {
 545                 struct ldb_parse_tree **e;
 546                 if (*p == ')') {
 547                         break;
 548                 }
 549
 550                 next = ldb_parse_filter(ret->u.list.elements, &p);
 551                 if (next == NULL) {
 552                         /* an invalid filter element */
 553                         talloc_free(ret);
 554                         return NULL;
 555                 }
 556                 e = talloc_realloc(ret, ret->u.list.elements,
 557                                      struct ldb_parse_tree *,
 558                                      ret->u.list.num_elements + 1);
 559                 if (!e) {
 560                         errno = ENOMEM;
 561                         talloc_free(ret);
 562                         return NULL;
 563                 }
 564                 ret->u.list.elements = e;
 565                 ret->u.list.elements[ret->u.list.num_elements] = next;
 566                 ret->u.list.num_elements++;
 567                 while (isspace((unsigned char)*p)) p++;
 568         }
 569
 570         *s = p;
 571
 572         return ret;
 573 }
 574
 575
 576 /*
 577   <not> ::= '!' <filter>
 578 */
 579 static struct ldb_parse_tree *ldb_parse_not(TALLOC_CTX *mem_ctx, const char **s)
 580 {
 581         struct ldb_parse_tree *ret;
 582         const char *p = *s;
 583
 584         if (*p != '!') {
 585                 return NULL;
 586         }
 587         p++;
 588
 589         ret = talloc(mem_ctx, struct ldb_parse_tree);
 590         if (!ret) {
 591                 errno = ENOMEM;
 592                 return NULL;
 593         }
 594
 595         ret->operation = LDB_OP_NOT;
 596         ret->u.isnot.child = ldb_parse_filter(ret, &p);
 597         if (!ret->u.isnot.child) {
 598                 talloc_free(ret);
 599                 return NULL;
 600         }
 601
 602         *s = p;
 603
 604         return ret;
 605 }
 606
 607 /*
 608   parse a filtercomp
 609   <filtercomp> ::= <and> | <or> | <not> | <simple>
 610 */
 611 static struct ldb_parse_tree *ldb_parse_filtercomp(TALLOC_CTX *mem_ctx, const char **s)
 612 {
 613         struct ldb_parse_tree *ret;
 614         const char *p = *s;
 615
 616         while (isspace((unsigned char)*p)) p++;
 617
 618         switch (*p) {
 619         case '&':
 620                 ret = ldb_parse_filterlist(mem_ctx, &p);
 621                 break;
 622
 623         case '|':
 624                 ret = ldb_parse_filterlist(mem_ctx, &p);
 625                 break;
 626
 627         case '!':
 628                 ret = ldb_parse_not(mem_ctx, &p);
 629                 break;
 630
 631         case '(':
 632         case ')':
 633                 return NULL;
 634
 635         default:
 636                 ret = ldb_parse_simple(mem_ctx, &p);
 637
 638         }
 639
 640         *s = p;
 641         return ret;
 642 }
 643
 644
 645 /*
 646   <filter> ::= '(' <filtercomp> ')'
 647 */
 648 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *mem_ctx, const char **s)
 649 {
 650         struct ldb_parse_tree *ret;
 651         const char *p = *s;
 652
 653         if (*p != '(') {
 654                 return NULL;
 655         }
 656         p++;
 657
 658         ret = ldb_parse_filtercomp(mem_ctx, &p);
 659
 660         if (*p != ')') {
 661                 return NULL;
 662         }
 663         p++;
 664
 665         while (isspace((unsigned char)*p)) {
 666                 p++;
 667         }
 668
 669         *s = p;
 670
 671         return ret;
 672 }
 673
 674
 675 /*
 676   main parser entry point. Takes a search string and returns a parse tree
 677
 678   expression ::= <simple> | <filter>
 679 */
 680 struct ldb_parse_tree *ldb_parse_tree(TALLOC_CTX *mem_ctx, const char *s)
 681 {
 682         if (s == NULL || *s == 0) {
 683                 s = "(|(objectClass=*)(distinguishedName=*))";
 684         }
 685
 686         while (isspace((unsigned char)*s)) s++;
 687
 688         if (*s == '(') {
 689                 return ldb_parse_filter(mem_ctx, &s);
 690         }
 691
 692         return ldb_parse_simple(mem_ctx, &s);
 693 }
 694
 695
 696 /*
 697   construct a ldap parse filter given a parse tree
 698 */
 699 char *ldb_filter_from_tree(TALLOC_CTX *mem_ctx, const struct ldb_parse_tree *tree)
 700 {
 701         char *s, *s2, *ret;
 702         unsigned int i;
 703
 704         if (tree == NULL) {
 705                 return NULL;
 706         }
 707
 708         switch (tree->operation) {
 709         case LDB_OP_AND:
 710         case LDB_OP_OR:
 711                 ret = talloc_asprintf(mem_ctx, "(%c", tree->operation==LDB_OP_AND?'&':'|');
 712                 if (ret == NULL) return NULL;
 713                 for (i=0;i<tree->u.list.num_elements;i++) {
 714                         s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
 715                         if (s == NULL) {
 716                                 talloc_free(ret);
 717                                 return NULL;
 718                         }
 719                         s2 = talloc_asprintf_append(ret, "%s", s);
 720                         talloc_free(s);
 721                         if (s2 == NULL) {
 722                                 talloc_free(ret);
 723                                 return NULL;
 724                         }
 725                         ret = s2;
 726                 }
 727                 s = talloc_asprintf_append(ret, ")");
 728                 if (s == NULL) {
 729                         talloc_free(ret);
 730                         return NULL;
 731                 }
 732                 return s;
 733         case LDB_OP_NOT:
 734                 s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
 735                 if (s == NULL) return NULL;
 736
 737                 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 738                 talloc_free(s);
 739                 return ret;
 740         case LDB_OP_EQUALITY:
 741                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 742                 if (s == NULL) return NULL;
 743                 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
 744                                       tree->u.equality.attr, s);
 745                 talloc_free(s);
 746                 return ret;
 747         case LDB_OP_SUBSTRING:
 748                 ret = talloc_asprintf(mem_ctx, "(%s=%s", tree->u.substring.attr,
 749                                       tree->u.substring.start_with_wildcard?"*":"");
 750                 if (ret == NULL) return NULL;
 751                 for (i = 0; tree->u.substring.chunks[i]; i++) {
 752                         s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
 753                         if (s2 == NULL) {
 754                                 talloc_free(ret);
 755                                 return NULL;
 756                         }
 757                         if (tree->u.substring.chunks[i+1] ||
 758                             tree->u.substring.end_with_wildcard) {
 759                                 s = talloc_asprintf_append(ret, "%s*", s2);
 760                         } else {
 761                                 s = talloc_asprintf_append(ret, "%s", s2);
 762                         }
 763                         if (s == NULL) {
 764                                 talloc_free(ret);
 765                                 return NULL;
 766                         }
 767                         ret = s;
 768                 }
 769                 s = talloc_asprintf_append(ret, ")");
 770                 if (s == NULL) {
 771                         talloc_free(ret);
 772                         return NULL;
 773                 }
 774                 ret = s;
 775                 return ret;
 776         case LDB_OP_GREATER:
 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_LESS:
 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_PRESENT:
 791                 ret = talloc_asprintf(mem_ctx, "(%s=*)", tree->u.present.attr);
 792                 return ret;
 793         case LDB_OP_APPROX:
 794                 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 795                 if (s == NULL) return NULL;
 796                 ret = talloc_asprintf(mem_ctx, "(%s~=%s)",
 797                                       tree->u.equality.attr, s);
 798                 talloc_free(s);
 799                 return ret;
 800         case LDB_OP_EXTENDED:
 801                 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
 802                 if (s == NULL) return NULL;
 803                 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
 804                                       tree->u.extended.attr?tree->u.extended.attr:"",
 805                                       tree->u.extended.dnAttributes?":dn":"",
 806                                       tree->u.extended.rule_id?":":"",
 807                                       tree->u.extended.rule_id?tree->u.extended.rule_id:"",
 808                                       s);
 809                 talloc_free(s);
 810                 return ret;
 811         }
 812
 813         return NULL;
 814 }
 815
 816
 817 /*
 818   walk a parse tree, calling the provided callback on each node
 819 */
 820 int ldb_parse_tree_walk(struct ldb_parse_tree *tree,
 821                         int (*callback)(struct ldb_parse_tree *tree, void *),
 822                         void *private_context)
 823 {
 824         unsigned int i;
 825         int ret;
 826
 827         ret = callback(tree, private_context);
 828         if (ret != LDB_SUCCESS) {
 829                 return ret;
 830         }
 831
 832         switch (tree->operation) {
 833         case LDB_OP_AND:
 834         case LDB_OP_OR:
 835                 for (i=0;i<tree->u.list.num_elements;i++) {
 836                         ret = ldb_parse_tree_walk(tree->u.list.elements[i], callback, private_context);
 837                         if (ret != LDB_SUCCESS) {
 838                                 return ret;
 839                         }
 840                 }
 841                 break;
 842         case LDB_OP_NOT:
 843                 ret = ldb_parse_tree_walk(tree->u.isnot.child, callback, private_context);
 844                 if (ret != LDB_SUCCESS) {
 845                         return ret;
 846                 }
 847                 break;
 848         case LDB_OP_EQUALITY:
 849         case LDB_OP_GREATER:
 850         case LDB_OP_LESS:
 851         case LDB_OP_APPROX:
 852         case LDB_OP_SUBSTRING:
 853         case LDB_OP_PRESENT:
 854         case LDB_OP_EXTENDED:
 855                 break;
 856         }
 857         return LDB_SUCCESS;
 858 }
 859
 860 struct parse_tree_attr_replace_ctx {
 861         const char *attr;
 862         const char *replace;
 863 };
 864
 865 /*
 866   callback for ldb_parse_tree_attr_replace()
 867  */
 868 static int parse_tree_attr_replace(struct ldb_parse_tree *tree, void *private_context)
 869 {
 870         struct parse_tree_attr_replace_ctx *ctx = private_context;
 871         switch (tree->operation) {
 872         case LDB_OP_EQUALITY:
 873         case LDB_OP_GREATER:
 874         case LDB_OP_LESS:
 875         case LDB_OP_APPROX:
 876                 if (ldb_attr_cmp(tree->u.equality.attr, ctx->attr) == 0) {
 877                         tree->u.equality.attr = ctx->replace;
 878                 }
 879                 break;
 880         case LDB_OP_SUBSTRING:
 881                 if (ldb_attr_cmp(tree->u.substring.attr, ctx->attr) == 0) {
 882                         tree->u.substring.attr = ctx->replace;
 883                 }
 884                 break;
 885         case LDB_OP_PRESENT:
 886                 if (ldb_attr_cmp(tree->u.present.attr, ctx->attr) == 0) {
 887                         tree->u.present.attr = ctx->replace;
 888                 }
 889                 break;
 890         case LDB_OP_EXTENDED:
 891                 if (tree->u.extended.attr &&
 892                     ldb_attr_cmp(tree->u.extended.attr, ctx->attr) == 0) {
 893                         tree->u.extended.attr = ctx->replace;
 894                 }
 895                 break;
 896         default:
 897                 break;
 898         }
 899         return LDB_SUCCESS;
 900 }
 901
 902 /*
 903   replace any occurrences of an attribute name in the parse tree with a
 904   new name
 905 */
 906 void ldb_parse_tree_attr_replace(struct ldb_parse_tree *tree,
 907                                  const char *attr,
 908                                  const char *replace)
 909 {
 910         struct parse_tree_attr_replace_ctx ctx;
 911
 912         ctx.attr    = attr;
 913         ctx.replace = replace;
 914
 915         ldb_parse_tree_walk(tree, parse_tree_attr_replace, &ctx);
 916 }
 917
 918 /*
 919   shallow copy a tree - copying only the elements array so that the caller
 920   can safely add new elements without changing the message
 921 */
 922 struct ldb_parse_tree *ldb_parse_tree_copy_shallow(TALLOC_CTX *mem_ctx,
 923                                                    const struct ldb_parse_tree *ot)
 924 {
 925         unsigned int i;
 926         struct ldb_parse_tree *nt;
 927
 928         nt = talloc(mem_ctx, struct ldb_parse_tree);
 929         if (!nt) {
 930                 return NULL;
 931         }
 932
 933         *nt = *ot;
 934
 935         switch (ot->operation) {
 936         case LDB_OP_AND:
 937         case LDB_OP_OR:
 938                 nt->u.list.elements = talloc_array(nt, struct ldb_parse_tree *,
 939                                                    ot->u.list.num_elements);
 940                 if (!nt->u.list.elements) {
 941                         talloc_free(nt);
 942                         return NULL;
 943                 }
 944
 945                 for (i=0;i<ot->u.list.num_elements;i++) {
 946                         nt->u.list.elements[i] =
 947                                 ldb_parse_tree_copy_shallow(nt->u.list.elements,
 948                                                 ot->u.list.elements[i]);
 949                         if (!nt->u.list.elements[i]) {
 950                                 talloc_free(nt);
 951                                 return NULL;
 952                         }
 953                 }
 954                 break;
 955         case LDB_OP_NOT:
 956                 nt->u.isnot.child = ldb_parse_tree_copy_shallow(nt,
 957                                                         ot->u.isnot.child);
 958                 if (!nt->u.isnot.child) {
 959                         talloc_free(nt);
 960                         return NULL;
 961                 }
 962                 break;
 963         case LDB_OP_EQUALITY:
 964         case LDB_OP_GREATER:
 965         case LDB_OP_LESS:
 966         case LDB_OP_APPROX:
 967         case LDB_OP_SUBSTRING:
 968         case LDB_OP_PRESENT:
 969         case LDB_OP_EXTENDED:
 970                 break;
 971         }
 972
 973         return nt;
 974 }