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