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 2 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, write to the Free Software
22 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28 * Component: ldb expression parsing
30 * Description: parse LDAP-like search expressions
32 * Author: Andrew Tridgell
37 - add RFC2254 binary string handling
38 - possibly add ~=, <= and >= handling
39 - expand the test suite
40 - add better parse error handling
45 #include "ldb/include/includes.h"
46 #include "system/locale.h"
48 struct ldb_val
ldb_binary_decode(void *mem_ctx
, const char *str
);
51 a filter is defined by:
52 <filter> ::= '(' <filtercomp> ')'
53 <filtercomp> ::= <and> | <or> | <not> | <simple>
54 <and> ::= '&' <filterlist>
55 <or> ::= '|' <filterlist>
56 <not> ::= '!' <filter>
57 <filterlist> ::= <filter> | <filter> <filterlist>
58 <simple> ::= <attributetype> <filtertype> <attributevalue>
59 <filtertype> ::= '=' | '~=' | '<=' | '>='
63 decode a RFC2254 binary string representation of a buffer.
66 struct ldb_val
ldb_binary_decode(void *mem_ctx
, const char *str
)
70 int slen
= str
?strlen(str
):0;
72 ret
.data
= (uint8_t *)talloc_size(mem_ctx
, slen
+1);
74 if (ret
.data
== NULL
) return ret
;
76 for (i
=j
=0;i
<slen
;i
++) {
79 if (sscanf(&str
[i
+1], "%02X", &c
) != 1) {
80 talloc_free(ret
.data
);
81 memset(&ret
, 0, sizeof(ret
));
84 ((uint8_t *)ret
.data
)[j
++] = c
;
87 ((uint8_t *)ret
.data
)[j
++] = str
[i
];
91 ((uint8_t *)ret
.data
)[j
] = 0;
98 encode a blob as a RFC2254 binary string, escaping any
99 non-printable or '\' characters
101 char *ldb_binary_encode(void *mem_ctx
, struct ldb_val val
)
105 int len
= val
.length
;
106 unsigned char *buf
= val
.data
;
108 for (i
=0;i
<val
.length
;i
++) {
109 if (!isprint(buf
[i
]) || strchr(" *()\\&|!\"", buf
[i
])) {
113 ret
= talloc_array(mem_ctx
, char, len
+1);
114 if (ret
== NULL
) return NULL
;
117 for (i
=0;i
<val
.length
;i
++) {
118 if (!isprint(buf
[i
]) || strchr(" *()\\&|!\"", buf
[i
])) {
119 snprintf(ret
+len
, 4, "\\%02X", buf
[i
]);
132 encode a string as a RFC2254 binary string, escaping any
133 non-printable or '\' characters. This routine is suitable for use
134 in escaping user data in ldap filters.
136 char *ldb_binary_encode_string(void *mem_ctx
, const char *string
)
139 val
.data
= discard_const_p(uint8_t, string
);
140 val
.length
= strlen(string
);
141 return ldb_binary_encode(mem_ctx
, val
);
144 /* find the first matching wildcard */
145 static char *ldb_parse_find_wildcard(char *value
)
148 value
= strpbrk(value
, "\\*");
149 if (value
== NULL
) return NULL
;
151 if (value
[0] == '\\') {
152 if (value
[1] == '\0') return NULL
;
157 if (value
[0] == '*') return value
;
163 /* return a NULL terminated list of binary strings representing the value
164 chunks separated by wildcards that makes the value portion of the filter
166 static struct ldb_val
**ldb_wildcard_decode(void *mem_ctx
, const char *string
)
168 struct ldb_val
**ret
= NULL
;
172 wc
= talloc_strdup(mem_ctx
, string
);
173 if (wc
== NULL
) return NULL
;
177 wc
= ldb_parse_find_wildcard(str
);
187 ret
= talloc_realloc(mem_ctx
, ret
, struct ldb_val
*, val
+ 2);
188 if (ret
== NULL
) return NULL
;
190 ret
[val
] = talloc(mem_ctx
, struct ldb_val
);
191 if (ret
[val
] == NULL
) return NULL
;
193 *(ret
[val
]) = ldb_binary_decode(mem_ctx
, str
);
194 if ((ret
[val
])->data
== NULL
) return NULL
;
206 static struct ldb_parse_tree
*ldb_parse_filter(void *mem_ctx
, const char **s
);
210 parse an extended match
218 the ':dn' part sets the dnAttributes boolean if present
219 the oid sets the rule_id string
222 static struct ldb_parse_tree
*ldb_parse_extended(struct ldb_parse_tree
*ret
,
223 char *attr
, char *value
)
227 ret
->operation
= LDB_OP_EXTENDED
;
228 ret
->u
.extended
.value
= ldb_binary_decode(ret
, value
);
229 if (ret
->u
.extended
.value
.data
== NULL
) goto failed
;
231 p1
= strchr(attr
, ':');
232 if (p1
== NULL
) goto failed
;
233 p2
= strchr(p1
+1, ':');
238 ret
->u
.extended
.attr
= attr
;
239 if (strcmp(p1
+1, "dn") == 0) {
240 ret
->u
.extended
.dnAttributes
= 1;
242 ret
->u
.extended
.rule_id
= talloc_strdup(ret
, p2
+1);
243 if (ret
->u
.extended
.rule_id
== NULL
) goto failed
;
245 ret
->u
.extended
.rule_id
= NULL
;
248 ret
->u
.extended
.dnAttributes
= 0;
249 ret
->u
.extended
.rule_id
= talloc_strdup(ret
, p1
+1);
250 if (ret
->u
.extended
.rule_id
== NULL
) goto failed
;
260 static enum ldb_parse_op
ldb_parse_filtertype(void *mem_ctx
, char **type
, char **value
, const char **s
)
262 enum ldb_parse_op filter
= 0;
263 char *name
, *val
, *k
;
267 /* retrieve attributetype name */
270 while ((isascii(*p
) && isalnum((unsigned char)*p
)) || (*p
== '-')) { /* attribute names can only be alphanums */
274 if (*p
== ':') { /* but extended searches have : and . chars too */
276 if (p
== NULL
) { /* malformed attribute name */
283 while (isspace((unsigned char)*p
)) p
++;
285 if (!strchr("=<>~:", *p
)) {
290 name
= (char *)talloc_memdup(mem_ctx
, t
, t1
- t
+ 1);
291 if (name
== NULL
) return 0;
294 /* retrieve filtertype */
297 filter
= LDB_OP_EQUALITY
;
298 } else if (*(p
+ 1) == '=') {
301 filter
= LDB_OP_LESS
;
305 filter
= LDB_OP_GREATER
;
309 filter
= LDB_OP_APPROX
;
313 filter
= LDB_OP_EXTENDED
;
324 while (isspace((unsigned char)*p
)) p
++;
329 while (*p
&& ((*p
!= ')') || ((*p
== ')') && (*(p
- 1) == '\\')))) p
++;
331 val
= (char *)talloc_memdup(mem_ctx
, t
, p
- t
+ 1);
340 /* remove trailing spaces from value */
341 while ((k
> val
) && (isspace((unsigned char)*(k
- 1)))) k
--;
351 <simple> ::= <attributetype> <filtertype> <attributevalue>
353 static struct ldb_parse_tree
*ldb_parse_simple(void *mem_ctx
, const char **s
)
356 struct ldb_parse_tree
*ret
;
357 enum ldb_parse_op filtertype
;
359 ret
= talloc(mem_ctx
, struct ldb_parse_tree
);
365 filtertype
= ldb_parse_filtertype(ret
, &attr
, &value
, s
);
371 switch (filtertype
) {
374 ret
->operation
= LDB_OP_PRESENT
;
375 ret
->u
.present
.attr
= attr
;
378 case LDB_OP_EQUALITY
:
380 if (strcmp(value
, "*") == 0) {
381 ret
->operation
= LDB_OP_PRESENT
;
382 ret
->u
.present
.attr
= attr
;
386 if (ldb_parse_find_wildcard(value
) != NULL
) {
387 ret
->operation
= LDB_OP_SUBSTRING
;
388 ret
->u
.substring
.attr
= attr
;
389 ret
->u
.substring
.start_with_wildcard
= 0;
390 ret
->u
.substring
.end_with_wildcard
= 0;
391 ret
->u
.substring
.chunks
= ldb_wildcard_decode(ret
, value
);
392 if (ret
->u
.substring
.chunks
== NULL
){
397 ret
->u
.substring
.start_with_wildcard
= 1;
398 if (value
[strlen(value
) - 1] == '*')
399 ret
->u
.substring
.end_with_wildcard
= 1;
405 ret
->operation
= LDB_OP_EQUALITY
;
406 ret
->u
.equality
.attr
= attr
;
407 ret
->u
.equality
.value
= ldb_binary_decode(ret
, value
);
408 if (ret
->u
.equality
.value
.data
== NULL
) {
416 ret
->operation
= LDB_OP_GREATER
;
417 ret
->u
.comparison
.attr
= attr
;
418 ret
->u
.comparison
.value
= ldb_binary_decode(ret
, value
);
419 if (ret
->u
.comparison
.value
.data
== NULL
) {
427 ret
->operation
= LDB_OP_LESS
;
428 ret
->u
.comparison
.attr
= attr
;
429 ret
->u
.comparison
.value
= ldb_binary_decode(ret
, value
);
430 if (ret
->u
.comparison
.value
.data
== NULL
) {
438 ret
->operation
= LDB_OP_APPROX
;
439 ret
->u
.comparison
.attr
= attr
;
440 ret
->u
.comparison
.value
= ldb_binary_decode(ret
, value
);
441 if (ret
->u
.comparison
.value
.data
== NULL
) {
448 case LDB_OP_EXTENDED
:
450 ret
= ldb_parse_extended(ret
, attr
, value
);
464 <and> ::= '&' <filterlist>
465 <or> ::= '|' <filterlist>
466 <filterlist> ::= <filter> | <filter> <filterlist>
468 static struct ldb_parse_tree
*ldb_parse_filterlist(void *mem_ctx
, const char **s
)
470 struct ldb_parse_tree
*ret
, *next
;
471 enum ldb_parse_op op
;
486 while (isspace((unsigned char)*p
)) p
++;
488 ret
= talloc(mem_ctx
, struct ldb_parse_tree
);
495 ret
->u
.list
.num_elements
= 1;
496 ret
->u
.list
.elements
= talloc(ret
, struct ldb_parse_tree
*);
497 if (!ret
->u
.list
.elements
) {
503 ret
->u
.list
.elements
[0] = ldb_parse_filter(ret
->u
.list
.elements
, &p
);
504 if (!ret
->u
.list
.elements
[0]) {
509 while (isspace((unsigned char)*p
)) p
++;
511 while (*p
&& (next
= ldb_parse_filter(ret
->u
.list
.elements
, &p
))) {
512 struct ldb_parse_tree
**e
;
513 e
= talloc_realloc(ret
, ret
->u
.list
.elements
,
514 struct ldb_parse_tree
*,
515 ret
->u
.list
.num_elements
+ 1);
521 ret
->u
.list
.elements
= e
;
522 ret
->u
.list
.elements
[ret
->u
.list
.num_elements
] = next
;
523 ret
->u
.list
.num_elements
++;
524 while (isspace((unsigned char)*p
)) p
++;
534 <not> ::= '!' <filter>
536 static struct ldb_parse_tree
*ldb_parse_not(void *mem_ctx
, const char **s
)
538 struct ldb_parse_tree
*ret
;
546 ret
= talloc(mem_ctx
, struct ldb_parse_tree
);
552 ret
->operation
= LDB_OP_NOT
;
553 ret
->u
.isnot
.child
= ldb_parse_filter(ret
, &p
);
554 if (!ret
->u
.isnot
.child
) {
566 <filtercomp> ::= <and> | <or> | <not> | <simple>
568 static struct ldb_parse_tree
*ldb_parse_filtercomp(void *mem_ctx
, const char **s
)
570 struct ldb_parse_tree
*ret
;
573 while (isspace((unsigned char)*p
)) p
++;
577 ret
= ldb_parse_filterlist(mem_ctx
, &p
);
581 ret
= ldb_parse_filterlist(mem_ctx
, &p
);
585 ret
= ldb_parse_not(mem_ctx
, &p
);
593 ret
= ldb_parse_simple(mem_ctx
, &p
);
603 <filter> ::= '(' <filtercomp> ')'
605 static struct ldb_parse_tree
*ldb_parse_filter(void *mem_ctx
, const char **s
)
607 struct ldb_parse_tree
*ret
;
615 ret
= ldb_parse_filtercomp(mem_ctx
, &p
);
622 while (isspace((unsigned char)*p
)) {
633 main parser entry point. Takes a search string and returns a parse tree
635 expression ::= <simple> | <filter>
637 struct ldb_parse_tree
*ldb_parse_tree(void *mem_ctx
, const char *s
)
639 if (s
== NULL
|| *s
== 0) {
640 s
= "(|(objectClass=*)(distinguishedName=*))";
643 while (isspace((unsigned char)*s
)) s
++;
646 return ldb_parse_filter(mem_ctx
, &s
);
649 return ldb_parse_simple(mem_ctx
, &s
);
654 construct a ldap parse filter given a parse tree
656 char *ldb_filter_from_tree(void *mem_ctx
, struct ldb_parse_tree
*tree
)
665 switch (tree
->operation
) {
668 ret
= talloc_asprintf(mem_ctx
, "(%c", tree
->operation
==LDB_OP_AND
?'&':'|');
669 if (ret
== NULL
) return NULL
;
670 for (i
=0;i
<tree
->u
.list
.num_elements
;i
++) {
671 s
= ldb_filter_from_tree(mem_ctx
, tree
->u
.list
.elements
[i
]);
676 s2
= talloc_asprintf_append(ret
, "%s", s
);
684 s
= talloc_asprintf_append(ret
, ")");
691 s
= ldb_filter_from_tree(mem_ctx
, tree
->u
.isnot
.child
);
692 if (s
== NULL
) return NULL
;
694 ret
= talloc_asprintf(mem_ctx
, "(!%s)", s
);
697 case LDB_OP_EQUALITY
:
698 s
= ldb_binary_encode(mem_ctx
, tree
->u
.equality
.value
);
699 if (s
== NULL
) return NULL
;
700 ret
= talloc_asprintf(mem_ctx
, "(%s=%s)",
701 tree
->u
.equality
.attr
, s
);
704 case LDB_OP_SUBSTRING
:
705 ret
= talloc_asprintf(mem_ctx
, "(%s=%s", tree
->u
.substring
.attr
,
706 tree
->u
.substring
.start_with_wildcard
?"*":"");
707 if (ret
== NULL
) return NULL
;
708 for (i
= 0; tree
->u
.substring
.chunks
[i
]; i
++) {
709 s2
= ldb_binary_encode(mem_ctx
, *(tree
->u
.substring
.chunks
[i
]));
714 if (tree
->u
.substring
.chunks
[i
+1] ||
715 tree
->u
.substring
.end_with_wildcard
) {
716 s
= talloc_asprintf_append(ret
, "%s*", s2
);
718 s
= talloc_asprintf_append(ret
, "%s", s2
);
726 s
= talloc_asprintf_append(ret
, ")");
734 s
= ldb_binary_encode(mem_ctx
, tree
->u
.equality
.value
);
735 if (s
== NULL
) return NULL
;
736 ret
= talloc_asprintf(mem_ctx
, "(%s>=%s)",
737 tree
->u
.equality
.attr
, s
);
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
);
748 ret
= talloc_asprintf(mem_ctx
, "(%s=*)", tree
->u
.present
.attr
);
751 s
= ldb_binary_encode(mem_ctx
, tree
->u
.equality
.value
);
752 if (s
== NULL
) return NULL
;
753 ret
= talloc_asprintf(mem_ctx
, "(%s~=%s)",
754 tree
->u
.equality
.attr
, s
);
757 case LDB_OP_EXTENDED
:
758 s
= ldb_binary_encode(mem_ctx
, tree
->u
.extended
.value
);
759 if (s
== NULL
) return NULL
;
760 ret
= talloc_asprintf(mem_ctx
, "(%s%s%s%s:=%s)",
761 tree
->u
.extended
.attr
?tree
->u
.extended
.attr
:"",
762 tree
->u
.extended
.dnAttributes
?":dn":"",
763 tree
->u
.extended
.rule_id
?":":"",
764 tree
->u
.extended
.rule_id
?tree
->u
.extended
.rule_id
:"",
775 replace any occurances of an attribute name in the parse tree with a
778 void ldb_parse_tree_attr_replace(struct ldb_parse_tree
*tree
,
783 switch (tree
->operation
) {
786 for (i
=0;i
<tree
->u
.list
.num_elements
;i
++) {
787 ldb_parse_tree_attr_replace(tree
->u
.list
.elements
[i
],
792 ldb_parse_tree_attr_replace(tree
->u
.isnot
.child
, attr
, replace
);
794 case LDB_OP_EQUALITY
:
798 if (ldb_attr_cmp(tree
->u
.equality
.attr
, attr
) == 0) {
799 tree
->u
.equality
.attr
= replace
;
802 case LDB_OP_SUBSTRING
:
803 if (ldb_attr_cmp(tree
->u
.substring
.attr
, attr
) == 0) {
804 tree
->u
.substring
.attr
= replace
;
808 if (ldb_attr_cmp(tree
->u
.present
.attr
, attr
) == 0) {
809 tree
->u
.present
.attr
= replace
;
812 case LDB_OP_EXTENDED
:
813 if (tree
->u
.extended
.attr
&&
814 ldb_attr_cmp(tree
->u
.extended
.attr
, attr
) == 0) {
815 tree
->u
.extended
.attr
= replace
;