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/>.
26 static struct ldb_parse_tree
*ldb_parse_filter(void *mem_ctx
, const char **s
);
28 static int ldb_parse_hex2char(const char *x
)
30 if (isxdigit(x
[0]) && isxdigit(x
[1])) {
31 const char h1
= x
[0], h2
= x
[1];
34 if (h1
>= 'a') c
= h1
- (int)'a' + 10;
35 else if (h1
>= 'A') c
= h1
- (int)'A' + 10;
36 else if (h1
>= '0') c
= h1
- (int)'0';
38 if (h2
>= 'a') c
+= h2
- (int)'a' + 10;
39 else if (h2
>= 'A') c
+= h2
- (int)'A' + 10;
40 else if (h2
>= '0') c
+= h2
- (int)'0';
51 structures for ldb_parse_tree handling code
53 enum ldb_parse_op
{ LDB_OP_AND
=1, LDB_OP_OR
=2, LDB_OP_NOT
=3,
54 LDB_OP_EQUALITY
=4, LDB_OP_SUBSTRING
=5,
55 LDB_OP_GREATER
=6, LDB_OP_LESS
=7, LDB_OP_PRESENT
=8,
56 LDB_OP_APPROX
=9, LDB_OP_EXTENDED
=10 };
58 struct ldb_parse_tree
{
59 enum ldb_parse_op operation
;
62 struct ldb_parse_tree
*child
;
70 int start_with_wildcard
;
71 int end_with_wildcard
;
72 struct ldb_val
**chunks
;
88 unsigned int num_elements
;
89 struct ldb_parse_tree
**elements
;
95 decode a RFC2254 binary string representation of a buffer.
98 static struct ldb_val
ldb_binary_decode(void *mem_ctx
, const char *str
)
102 size_t slen
= str
?strlen(str
):0;
104 ret
.data
= (uint8_t *)talloc_size(mem_ctx
, slen
+1);
106 if (ret
.data
== NULL
) return ret
;
108 for (i
=j
=0;i
<slen
;i
++) {
109 if (str
[i
] == '\\') {
112 c
= ldb_parse_hex2char(&str
[i
+1]);
114 talloc_free(ret
.data
);
115 memset(&ret
, 0, sizeof(ret
));
118 ((uint8_t *)ret
.data
)[j
++] = c
;
121 ((uint8_t *)ret
.data
)[j
++] = str
[i
];
125 ((uint8_t *)ret
.data
)[j
] = 0;
134 encode a blob as a RFC2254 binary string, escaping any
135 non-printable or '\' characters
137 char *ldb_binary_encode(void *mem_ctx
, struct ldb_val val
)
141 size_t len
= val
.length
;
142 unsigned char *buf
= val
.data
;
144 for (i
=0;i
<val
.length
;i
++) {
145 if (!isprint(buf
[i
]) || strchr(" *()\\&|!\"", buf
[i
])) {
149 ret
= talloc_array(mem_ctx
, char, len
+1);
150 if (ret
== NULL
) return NULL
;
153 for (i
=0;i
<val
.length
;i
++) {
154 if (!isprint(buf
[i
]) || strchr(" *()\\&|!\"", buf
[i
])) {
155 snprintf(ret
+len
, 4, "\\%02X", buf
[i
]);
169 static enum ldb_parse_op
ldb_parse_filtertype(void *mem_ctx
, char **type
, char **value
, const char **s
)
171 enum ldb_parse_op filter
= 0;
172 char *name
, *val
, *k
;
176 /* retrieve attributetype name */
179 if (*p
== '@') { /* for internal attributes the first char can be @ */
183 while ((isascii(*p
) && isalnum((unsigned char)*p
)) || (*p
== '-') || (*p
== '.')) {
184 /* attribute names can only be alphanums */
188 if (*p
== ':') { /* but extended searches have : and . chars too */
190 if (p
== NULL
) { /* malformed attribute name */
197 while (isspace((unsigned char)*p
)) p
++;
199 if (!strchr("=<>~:", *p
)) {
204 name
= (char *)talloc_memdup(mem_ctx
, t
, t1
- t
+ 1);
205 if (name
== NULL
) return 0;
208 /* retrieve filtertype */
211 filter
= LDB_OP_EQUALITY
;
212 } else if (*(p
+ 1) == '=') {
215 filter
= LDB_OP_LESS
;
219 filter
= LDB_OP_GREATER
;
223 filter
= LDB_OP_APPROX
;
227 filter
= LDB_OP_EXTENDED
;
238 while (isspace((unsigned char)*p
)) p
++;
243 while (*p
&& ((*p
!= ')') || ((*p
== ')') && (*(p
- 1) == '\\')))) p
++;
245 val
= (char *)talloc_memdup(mem_ctx
, t
, p
- t
+ 1);
254 /* remove trailing spaces from value */
255 while ((k
> val
) && (isspace((unsigned char)*(k
- 1)))) k
--;
264 /* find the first matching wildcard */
265 static char *ldb_parse_find_wildcard(char *value
)
268 value
= strpbrk(value
, "\\*");
269 if (value
== NULL
) return NULL
;
271 if (value
[0] == '\\') {
272 if (value
[1] == '\0') return NULL
;
277 if (value
[0] == '*') return value
;
283 /* return a NULL terminated list of binary strings representing the value
284 chunks separated by wildcards that makes the value portion of the filter
286 static struct ldb_val
**ldb_wildcard_decode(void *mem_ctx
, const char *string
)
288 struct ldb_val
**ret
= NULL
;
289 unsigned int val
= 0;
292 wc
= talloc_strdup(mem_ctx
, string
);
293 if (wc
== NULL
) return NULL
;
297 wc
= ldb_parse_find_wildcard(str
);
307 ret
= talloc_realloc(mem_ctx
, ret
, struct ldb_val
*, val
+ 2);
308 if (ret
== NULL
) return NULL
;
310 ret
[val
] = talloc(mem_ctx
, struct ldb_val
);
311 if (ret
[val
] == NULL
) return NULL
;
313 *(ret
[val
]) = ldb_binary_decode(mem_ctx
, str
);
314 if ((ret
[val
])->data
== NULL
) return NULL
;
327 parse an extended match
335 the ':dn' part sets the dnAttributes boolean if present
336 the oid sets the rule_id string
339 static struct ldb_parse_tree
*ldb_parse_extended(struct ldb_parse_tree
*ret
,
340 char *attr
, char *value
)
344 ret
->operation
= LDB_OP_EXTENDED
;
345 ret
->u
.extended
.value
= ldb_binary_decode(ret
, value
);
346 if (ret
->u
.extended
.value
.data
== NULL
) goto failed
;
348 p1
= strchr(attr
, ':');
349 if (p1
== NULL
) goto failed
;
350 p2
= strchr(p1
+1, ':');
355 ret
->u
.extended
.attr
= attr
;
356 if (strcmp(p1
+1, "dn") == 0) {
357 ret
->u
.extended
.dnAttributes
= 1;
359 ret
->u
.extended
.rule_id
= talloc_strdup(ret
, p2
+1);
360 if (ret
->u
.extended
.rule_id
== NULL
) goto failed
;
362 ret
->u
.extended
.rule_id
= NULL
;
365 ret
->u
.extended
.dnAttributes
= 0;
366 ret
->u
.extended
.rule_id
= talloc_strdup(ret
, p1
+1);
367 if (ret
->u
.extended
.rule_id
== NULL
) goto failed
;
379 <simple> ::= <attributetype> <filtertype> <attributevalue>
381 static struct ldb_parse_tree
*ldb_parse_simple(void *mem_ctx
, const char **s
)
384 struct ldb_parse_tree
*ret
;
385 enum ldb_parse_op filtertype
;
387 ret
= talloc(mem_ctx
, struct ldb_parse_tree
);
393 filtertype
= ldb_parse_filtertype(ret
, &attr
, &value
, s
);
399 switch (filtertype
) {
402 ret
->operation
= LDB_OP_PRESENT
;
403 ret
->u
.present
.attr
= attr
;
406 case LDB_OP_EQUALITY
:
408 if (strcmp(value
, "*") == 0) {
409 ret
->operation
= LDB_OP_PRESENT
;
410 ret
->u
.present
.attr
= attr
;
414 if (ldb_parse_find_wildcard(value
) != NULL
) {
415 ret
->operation
= LDB_OP_SUBSTRING
;
416 ret
->u
.substring
.attr
= attr
;
417 ret
->u
.substring
.start_with_wildcard
= 0;
418 ret
->u
.substring
.end_with_wildcard
= 0;
419 ret
->u
.substring
.chunks
= ldb_wildcard_decode(ret
, value
);
420 if (ret
->u
.substring
.chunks
== NULL
){
425 ret
->u
.substring
.start_with_wildcard
= 1;
426 if (value
[strlen(value
) - 1] == '*')
427 ret
->u
.substring
.end_with_wildcard
= 1;
433 ret
->operation
= LDB_OP_EQUALITY
;
434 ret
->u
.equality
.attr
= attr
;
435 ret
->u
.equality
.value
= ldb_binary_decode(ret
, value
);
436 if (ret
->u
.equality
.value
.data
== NULL
) {
444 ret
->operation
= LDB_OP_GREATER
;
445 ret
->u
.comparison
.attr
= attr
;
446 ret
->u
.comparison
.value
= ldb_binary_decode(ret
, value
);
447 if (ret
->u
.comparison
.value
.data
== NULL
) {
455 ret
->operation
= LDB_OP_LESS
;
456 ret
->u
.comparison
.attr
= attr
;
457 ret
->u
.comparison
.value
= ldb_binary_decode(ret
, value
);
458 if (ret
->u
.comparison
.value
.data
== NULL
) {
466 ret
->operation
= LDB_OP_APPROX
;
467 ret
->u
.comparison
.attr
= attr
;
468 ret
->u
.comparison
.value
= ldb_binary_decode(ret
, value
);
469 if (ret
->u
.comparison
.value
.data
== NULL
) {
476 case LDB_OP_EXTENDED
:
478 ret
= ldb_parse_extended(ret
, attr
, value
);
491 <and> ::= '&' <filterlist>
492 <or> ::= '|' <filterlist>
493 <filterlist> ::= <filter> | <filter> <filterlist>
495 static struct ldb_parse_tree
*ldb_parse_filterlist(void *mem_ctx
, const char **s
)
497 struct ldb_parse_tree
*ret
, *next
;
498 enum ldb_parse_op op
;
513 while (isspace((unsigned char)*p
)) p
++;
515 ret
= talloc(mem_ctx
, struct ldb_parse_tree
);
522 ret
->u
.list
.num_elements
= 1;
523 ret
->u
.list
.elements
= talloc(ret
, struct ldb_parse_tree
*);
524 if (!ret
->u
.list
.elements
) {
530 ret
->u
.list
.elements
[0] = ldb_parse_filter(ret
->u
.list
.elements
, &p
);
531 if (!ret
->u
.list
.elements
[0]) {
536 while (isspace((unsigned char)*p
)) p
++;
538 while (*p
&& (next
= ldb_parse_filter(ret
->u
.list
.elements
, &p
))) {
539 struct ldb_parse_tree
**e
;
540 e
= talloc_realloc(ret
, ret
->u
.list
.elements
,
541 struct ldb_parse_tree
*,
542 ret
->u
.list
.num_elements
+ 1);
548 ret
->u
.list
.elements
= e
;
549 ret
->u
.list
.elements
[ret
->u
.list
.num_elements
] = next
;
550 ret
->u
.list
.num_elements
++;
551 while (isspace((unsigned char)*p
)) p
++;
560 <not> ::= '!' <filter>
562 static struct ldb_parse_tree
*ldb_parse_not(void *mem_ctx
, const char **s
)
564 struct ldb_parse_tree
*ret
;
572 ret
= talloc(mem_ctx
, struct ldb_parse_tree
);
578 ret
->operation
= LDB_OP_NOT
;
579 ret
->u
.isnot
.child
= ldb_parse_filter(ret
, &p
);
580 if (!ret
->u
.isnot
.child
) {
594 <filtercomp> ::= <and> | <or> | <not> | <simple>
596 static struct ldb_parse_tree
*ldb_parse_filtercomp(void *mem_ctx
, const char **s
)
598 struct ldb_parse_tree
*ret
;
601 while (isspace((unsigned char)*p
)) p
++;
605 ret
= ldb_parse_filterlist(mem_ctx
, &p
);
609 ret
= ldb_parse_filterlist(mem_ctx
, &p
);
613 ret
= ldb_parse_not(mem_ctx
, &p
);
621 ret
= ldb_parse_simple(mem_ctx
, &p
);
632 <filter> ::= '(' <filtercomp> ')'
634 static struct ldb_parse_tree
*ldb_parse_filter(void *mem_ctx
, const char **s
)
636 struct ldb_parse_tree
*ret
;
644 ret
= ldb_parse_filtercomp(mem_ctx
, &p
);
651 while (isspace((unsigned char)*p
)) {
663 main parser entry point. Takes a search string and returns a parse tree
665 expression ::= <simple> | <filter>
667 struct ldb_parse_tree
*ldb_parse_tree(void *mem_ctx
, const char *s
)
669 if (s
== NULL
|| *s
== 0) {
670 s
= "(|(objectClass=*)(distinguishedName=*))";
673 while (isspace((unsigned char)*s
)) s
++;
676 return ldb_parse_filter(mem_ctx
, &s
);
679 return ldb_parse_simple(mem_ctx
, &s
);