4 Copyright (C) Andrew Tridgell 2004
6 ** NOTE! The following LGPL license applies to the ldb
7 ** library. This does NOT imply that all of Samba is released
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.
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.
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/>.
27 * Component: ldb expression parsing
29 * Description: parse LDAP-like search expressions
31 * Author: Andrew Tridgell
36 - add RFC2254 binary string handling
37 - possibly add ~=, <= and >= handling
38 - expand the test suite
39 - add better parse error handling
43 #include "ldb_private.h"
44 #include "system/locale.h"
47 a filter is defined by:
48 <filter> ::= '(' <filtercomp> ')'
49 <filtercomp> ::= <and> | <or> | <not> | <simple>
50 <and> ::= '&' <filterlist>
51 <or> ::= '|' <filterlist>
52 <not> ::= '!' <filter>
53 <filterlist> ::= <filter> | <filter> <filterlist>
54 <simple> ::= <attributetype> <filtertype> <attributevalue>
55 <filtertype> ::= '=' | '~=' | '<=' | '>='
59 decode a RFC2254 binary string representation of a buffer.
62 struct ldb_val ldb_binary_decode(void *mem_ctx, const char *str)
66 int slen = str?strlen(str):0;
68 ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
70 if (ret.data == NULL) return ret;
72 for (i=j=0;i<slen;i++) {
75 if (sscanf(&str[i+1], "%02X", &c) != 1) {
76 talloc_free(ret.data);
77 memset(&ret, 0, sizeof(ret));
80 ((uint8_t *)ret.data)[j++] = c;
83 ((uint8_t *)ret.data)[j++] = str[i];
87 ((uint8_t *)ret.data)[j] = 0;
92 static bool need_encode(unsigned char cval)
94 if (cval < 0x20 || cval > 0x7E || strchr(" *()\\&|!\"", cval)) {
101 encode a blob as a RFC2254 binary string, escaping any
102 non-printable or '\' characters
104 char *ldb_binary_encode(void *mem_ctx, struct ldb_val val)
108 int len = val.length;
109 unsigned char *buf = val.data;
111 for (i=0;i<val.length;i++) {
112 if (need_encode(buf[i])) {
116 ret = talloc_array(mem_ctx, char, len+1);
117 if (ret == NULL) return NULL;
120 for (i=0;i<val.length;i++) {
121 if (need_encode(buf[i])) {
122 snprintf(ret+len, 4, "\\%02X", buf[i]);
135 encode a string as a RFC2254 binary string, escaping any
136 non-printable or '\' characters. This routine is suitable for use
137 in escaping user data in ldap filters.
139 char *ldb_binary_encode_string(void *mem_ctx, const char *string)
142 val.data = discard_const_p(uint8_t, string);
143 val.length = strlen(string);
144 return ldb_binary_encode(mem_ctx, val);
147 /* find the first matching wildcard */
148 static char *ldb_parse_find_wildcard(char *value)
151 value = strpbrk(value, "\\*");
152 if (value == NULL) return NULL;
154 if (value[0] == '\\') {
155 if (value[1] == '\0') return NULL;
160 if (value[0] == '*') return value;
166 /* return a NULL terminated list of binary strings representing the value
167 chunks separated by wildcards that makes the value portion of the filter
169 static struct ldb_val **ldb_wildcard_decode(void *mem_ctx, const char *string)
171 struct ldb_val **ret = NULL;
175 wc = talloc_strdup(mem_ctx, string);
176 if (wc == NULL) return NULL;
180 wc = ldb_parse_find_wildcard(str);
190 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
191 if (ret == NULL) return NULL;
193 ret[val] = talloc(mem_ctx, struct ldb_val);
194 if (ret[val] == NULL) return NULL;
196 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
197 if ((ret[val])->data == NULL) return NULL;
209 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
213 parse an extended match
221 the ':dn' part sets the dnAttributes boolean if present
222 the oid sets the rule_id string
225 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
226 char *attr, char *value)
230 ret->operation = LDB_OP_EXTENDED;
231 ret->u.extended.value = ldb_binary_decode(ret, value);
232 if (ret->u.extended.value.data == NULL) goto failed;
234 p1 = strchr(attr, ':');
235 if (p1 == NULL) goto failed;
236 p2 = strchr(p1+1, ':');
241 ret->u.extended.attr = attr;
242 if (strcmp(p1+1, "dn") == 0) {
243 ret->u.extended.dnAttributes = 1;
245 ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
246 if (ret->u.extended.rule_id == NULL) goto failed;
248 ret->u.extended.rule_id = NULL;
251 ret->u.extended.dnAttributes = 0;
252 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
253 if (ret->u.extended.rule_id == NULL) goto failed;
263 static enum ldb_parse_op ldb_parse_filtertype(void *mem_ctx, char **type, char **value, const char **s)
265 enum ldb_parse_op filter = 0;
266 char *name, *val, *k;
270 /* retrieve attributetype name */
273 if (*p == '@') { /* for internal attributes the first char can be @ */
277 while ((isascii(*p) && isalnum((unsigned char)*p)) || (*p == '-') || (*p == '.')) {
278 /* attribute names can only be alphanums */
282 if (*p == ':') { /* but extended searches have : and . chars too */
284 if (p == NULL) { /* malformed attribute name */
291 while (isspace((unsigned char)*p)) p++;
293 if (!strchr("=<>~:", *p)) {
298 name = (char *)talloc_memdup(mem_ctx, t, t1 - t + 1);
299 if (name == NULL) return 0;
302 /* retrieve filtertype */
305 filter = LDB_OP_EQUALITY;
306 } else if (*(p + 1) == '=') {
309 filter = LDB_OP_LESS;
313 filter = LDB_OP_GREATER;
317 filter = LDB_OP_APPROX;
321 filter = LDB_OP_EXTENDED;
332 while (isspace((unsigned char)*p)) p++;
337 while (*p && ((*p != ')') || ((*p == ')') && (*(p - 1) == '\\')))) p++;
339 val = (char *)talloc_memdup(mem_ctx, t, p - t + 1);
348 /* remove trailing spaces from value */
349 while ((k > val) && (isspace((unsigned char)*(k - 1)))) k--;
359 <simple> ::= <attributetype> <filtertype> <attributevalue>
361 static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char **s)
364 struct ldb_parse_tree *ret;
365 enum ldb_parse_op filtertype;
367 ret = talloc(mem_ctx, struct ldb_parse_tree);
373 filtertype = ldb_parse_filtertype(ret, &attr, &value, s);
379 switch (filtertype) {
382 ret->operation = LDB_OP_PRESENT;
383 ret->u.present.attr = attr;
386 case LDB_OP_EQUALITY:
388 if (strcmp(value, "*") == 0) {
389 ret->operation = LDB_OP_PRESENT;
390 ret->u.present.attr = attr;
394 if (ldb_parse_find_wildcard(value) != NULL) {
395 ret->operation = LDB_OP_SUBSTRING;
396 ret->u.substring.attr = attr;
397 ret->u.substring.start_with_wildcard = 0;
398 ret->u.substring.end_with_wildcard = 0;
399 ret->u.substring.chunks = ldb_wildcard_decode(ret, value);
400 if (ret->u.substring.chunks == NULL){
405 ret->u.substring.start_with_wildcard = 1;
406 if (value[strlen(value) - 1] == '*')
407 ret->u.substring.end_with_wildcard = 1;
413 ret->operation = LDB_OP_EQUALITY;
414 ret->u.equality.attr = attr;
415 ret->u.equality.value = ldb_binary_decode(ret, value);
416 if (ret->u.equality.value.data == NULL) {
424 ret->operation = LDB_OP_GREATER;
425 ret->u.comparison.attr = attr;
426 ret->u.comparison.value = ldb_binary_decode(ret, value);
427 if (ret->u.comparison.value.data == NULL) {
435 ret->operation = LDB_OP_LESS;
436 ret->u.comparison.attr = attr;
437 ret->u.comparison.value = ldb_binary_decode(ret, value);
438 if (ret->u.comparison.value.data == NULL) {
446 ret->operation = LDB_OP_APPROX;
447 ret->u.comparison.attr = attr;
448 ret->u.comparison.value = ldb_binary_decode(ret, value);
449 if (ret->u.comparison.value.data == NULL) {
456 case LDB_OP_EXTENDED:
458 ret = ldb_parse_extended(ret, attr, value);
472 <and> ::= '&' <filterlist>
473 <or> ::= '|' <filterlist>
474 <filterlist> ::= <filter> | <filter> <filterlist>
476 static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx, const char **s)
478 struct ldb_parse_tree *ret, *next;
479 enum ldb_parse_op op;
494 while (isspace((unsigned char)*p)) p++;
496 ret = talloc(mem_ctx, struct ldb_parse_tree);
503 ret->u.list.num_elements = 1;
504 ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
505 if (!ret->u.list.elements) {
511 ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &p);
512 if (!ret->u.list.elements[0]) {
517 while (isspace((unsigned char)*p)) p++;
519 while (*p && (next = ldb_parse_filter(ret->u.list.elements, &p))) {
520 struct ldb_parse_tree **e;
521 e = talloc_realloc(ret, ret->u.list.elements,
522 struct ldb_parse_tree *,
523 ret->u.list.num_elements + 1);
529 ret->u.list.elements = e;
530 ret->u.list.elements[ret->u.list.num_elements] = next;
531 ret->u.list.num_elements++;
532 while (isspace((unsigned char)*p)) p++;
542 <not> ::= '!' <filter>
544 static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char **s)
546 struct ldb_parse_tree *ret;
554 ret = talloc(mem_ctx, struct ldb_parse_tree);
560 ret->operation = LDB_OP_NOT;
561 ret->u.isnot.child = ldb_parse_filter(ret, &p);
562 if (!ret->u.isnot.child) {
574 <filtercomp> ::= <and> | <or> | <not> | <simple>
576 static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char **s)
578 struct ldb_parse_tree *ret;
581 while (isspace((unsigned char)*p)) p++;
585 ret = ldb_parse_filterlist(mem_ctx, &p);
589 ret = ldb_parse_filterlist(mem_ctx, &p);
593 ret = ldb_parse_not(mem_ctx, &p);
601 ret = ldb_parse_simple(mem_ctx, &p);
611 <filter> ::= '(' <filtercomp> ')'
613 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s)
615 struct ldb_parse_tree *ret;
623 ret = ldb_parse_filtercomp(mem_ctx, &p);
630 while (isspace((unsigned char)*p)) {
641 main parser entry point. Takes a search string and returns a parse tree
643 expression ::= <simple> | <filter>
645 struct ldb_parse_tree *ldb_parse_tree(void *mem_ctx, const char *s)
647 if (s == NULL || *s == 0) {
648 s = "(|(objectClass=*)(distinguishedName=*))";
651 while (isspace((unsigned char)*s)) s++;
654 return ldb_parse_filter(mem_ctx, &s);
657 return ldb_parse_simple(mem_ctx, &s);
662 construct a ldap parse filter given a parse tree
664 char *ldb_filter_from_tree(void *mem_ctx, struct ldb_parse_tree *tree)
673 switch (tree->operation) {
676 ret = talloc_asprintf(mem_ctx, "(%c", tree->operation==LDB_OP_AND?'&':'|');
677 if (ret == NULL) return NULL;
678 for (i=0;i<tree->u.list.num_elements;i++) {
679 s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
684 s2 = talloc_asprintf_append(ret, "%s", s);
692 s = talloc_asprintf_append(ret, ")");
699 s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
700 if (s == NULL) return NULL;
702 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
705 case LDB_OP_EQUALITY:
706 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
707 if (s == NULL) return NULL;
708 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
709 tree->u.equality.attr, s);
712 case LDB_OP_SUBSTRING:
713 ret = talloc_asprintf(mem_ctx, "(%s=%s", tree->u.substring.attr,
714 tree->u.substring.start_with_wildcard?"*":"");
715 if (ret == NULL) return NULL;
716 for (i = 0; tree->u.substring.chunks[i]; i++) {
717 s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
722 if (tree->u.substring.chunks[i+1] ||
723 tree->u.substring.end_with_wildcard) {
724 s = talloc_asprintf_append(ret, "%s*", s2);
726 s = talloc_asprintf_append(ret, "%s", s2);
734 s = talloc_asprintf_append(ret, ")");
742 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
743 if (s == NULL) return NULL;
744 ret = talloc_asprintf(mem_ctx, "(%s>=%s)",
745 tree->u.equality.attr, s);
749 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
750 if (s == NULL) return NULL;
751 ret = talloc_asprintf(mem_ctx, "(%s<=%s)",
752 tree->u.equality.attr, s);
756 ret = talloc_asprintf(mem_ctx, "(%s=*)", tree->u.present.attr);
759 s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
760 if (s == NULL) return NULL;
761 ret = talloc_asprintf(mem_ctx, "(%s~=%s)",
762 tree->u.equality.attr, s);
765 case LDB_OP_EXTENDED:
766 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
767 if (s == NULL) return NULL;
768 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
769 tree->u.extended.attr?tree->u.extended.attr:"",
770 tree->u.extended.dnAttributes?":dn":"",
771 tree->u.extended.rule_id?":":"",
772 tree->u.extended.rule_id?tree->u.extended.rule_id:"",
783 replace any occurances of an attribute name in the parse tree with a
786 void ldb_parse_tree_attr_replace(struct ldb_parse_tree *tree,
791 switch (tree->operation) {
794 for (i=0;i<tree->u.list.num_elements;i++) {
795 ldb_parse_tree_attr_replace(tree->u.list.elements[i],
800 ldb_parse_tree_attr_replace(tree->u.isnot.child, attr, replace);
802 case LDB_OP_EQUALITY:
806 if (ldb_attr_cmp(tree->u.equality.attr, attr) == 0) {
807 tree->u.equality.attr = replace;
810 case LDB_OP_SUBSTRING:
811 if (ldb_attr_cmp(tree->u.substring.attr, attr) == 0) {
812 tree->u.substring.attr = replace;
816 if (ldb_attr_cmp(tree->u.present.attr, attr) == 0) {
817 tree->u.present.attr = replace;
820 case LDB_OP_EXTENDED:
821 if (tree->u.extended.attr &&
822 ldb_attr_cmp(tree->u.extended.attr, attr) == 0) {
823 tree->u.extended.attr = replace;
830 shallow copy a tree - copying only the elements array so that the caller
831 can safely add new elements without changing the message
833 struct ldb_parse_tree *ldb_parse_tree_copy_shallow(TALLOC_CTX *mem_ctx,
834 const struct ldb_parse_tree *ot)
837 struct ldb_parse_tree *nt;
839 nt = talloc(mem_ctx, struct ldb_parse_tree);
846 switch (ot->operation) {
849 nt->u.list.elements = talloc_array(nt, struct ldb_parse_tree *,
850 ot->u.list.num_elements);
851 if (!nt->u.list.elements) {
856 for (i=0;i<ot->u.list.num_elements;i++) {
857 nt->u.list.elements[i] =
858 ldb_parse_tree_copy_shallow(nt->u.list.elements,
859 ot->u.list.elements[i]);
860 if (!nt->u.list.elements[i]) {
867 nt->u.isnot.child = ldb_parse_tree_copy_shallow(nt,
869 if (!nt->u.isnot.child) {
874 case LDB_OP_EQUALITY:
878 case LDB_OP_SUBSTRING:
880 case LDB_OP_EXTENDED: