Line data Source code
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 : /*
47 : * Maximum depth of the filter parse tree, the value chosen is small enough to
48 : * avoid triggering ASAN stack overflow checks. But large enough to be useful.
49 : *
50 : * On Windows clients the maximum number of levels of recursion allowed is 100.
51 : * In the LDAP server, Windows restricts clients to 512 nested
52 : * (eg) OR statements.
53 : */
54 : #define LDB_MAX_PARSE_TREE_DEPTH 128
55 :
56 : /*
57 : a filter is defined by:
58 : <filter> ::= '(' <filtercomp> ')'
59 : <filtercomp> ::= <and> | <or> | <not> | <simple>
60 : <and> ::= '&' <filterlist>
61 : <or> ::= '|' <filterlist>
62 : <not> ::= '!' <filter>
63 : <filterlist> ::= <filter> | <filter> <filterlist>
64 : <simple> ::= <attributetype> <filtertype> <attributevalue>
65 : <filtertype> ::= '=' | '~=' | '<=' | '>='
66 : */
67 :
68 : /*
69 : decode a RFC2254 binary string representation of a buffer.
70 : Used in LDAP filters.
71 : */
72 43454778 : struct ldb_val ldb_binary_decode(TALLOC_CTX *mem_ctx, const char *str)
73 : {
74 1032017 : size_t i, j;
75 1032017 : struct ldb_val ret;
76 43454778 : size_t slen = str?strlen(str):0;
77 :
78 43454778 : ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
79 43454778 : ret.length = 0;
80 43454778 : if (ret.data == NULL) return ret;
81 :
82 940756811 : for (i=j=0;i<slen;i++) {
83 897302035 : if (str[i] == '\\') {
84 5435846 : uint8_t c;
85 5435846 : bool ok;
86 :
87 196319340 : ok = hex_byte(&str[i+1], &c);
88 196319340 : if (!ok) {
89 2 : talloc_free(ret.data);
90 2 : memset(&ret, 0, sizeof(ret));
91 2 : return ret;
92 : }
93 196319338 : ((uint8_t *)ret.data)[j++] = c;
94 196319338 : i += 2;
95 : } else {
96 700982695 : ((uint8_t *)ret.data)[j++] = str[i];
97 : }
98 : }
99 43454776 : ret.length = j;
100 43454776 : ((uint8_t *)ret.data)[j] = 0;
101 :
102 43454776 : return ret;
103 : }
104 :
105 600131750 : static bool need_encode(unsigned char cval)
106 : {
107 589620976 : if (cval < 0x20 || cval > 0x7E || strchr(" *()\\&|!\"", cval)) {
108 392639082 : return true;
109 : }
110 199558000 : return false;
111 : }
112 :
113 : /*
114 : encode a blob as a RFC2254 binary string, escaping any
115 : non-printable or '\' characters
116 : */
117 16775938 : char *ldb_binary_encode(TALLOC_CTX *mem_ctx, struct ldb_val val)
118 : {
119 523742 : size_t i;
120 523742 : char *ret;
121 16775938 : size_t len = val.length;
122 16775938 : unsigned char *buf = val.data;
123 :
124 316841813 : for (i=0;i<val.length;i++) {
125 309469051 : if (need_encode(buf[i])) {
126 196319541 : len += 2;
127 : }
128 : }
129 16775938 : ret = talloc_array(mem_ctx, char, len+1);
130 16775938 : if (ret == NULL) return NULL;
131 :
132 16252196 : len = 0;
133 316841813 : for (i=0;i<val.length;i++) {
134 300065875 : if (need_encode(buf[i])) {
135 196319541 : snprintf(ret+len, 4, "\\%02X", buf[i]);
136 196319541 : len += 3;
137 : } else {
138 103746334 : ret[len++] = buf[i];
139 : }
140 : }
141 :
142 16775938 : ret[len] = 0;
143 :
144 16775938 : return ret;
145 : }
146 :
147 : /*
148 : encode a string as a RFC2254 binary string, escaping any
149 : non-printable or '\' characters. This routine is suitable for use
150 : in escaping user data in ldap filters.
151 : */
152 1378981 : char *ldb_binary_encode_string(TALLOC_CTX *mem_ctx, const char *string)
153 : {
154 79801 : struct ldb_val val;
155 1378981 : if (string == NULL) {
156 0 : return NULL;
157 : }
158 1378981 : val.data = discard_const_p(uint8_t, string);
159 1378981 : val.length = strlen(string);
160 1378981 : return ldb_binary_encode(mem_ctx, val);
161 : }
162 :
163 : /* find the first matching wildcard */
164 39119382 : static char *ldb_parse_find_wildcard(char *value)
165 : {
166 235438718 : while (*value) {
167 235438714 : value = strpbrk(value, "\\*");
168 235438714 : if (value == NULL) return NULL;
169 :
170 196398562 : if (value[0] == '\\') {
171 196319336 : if (value[1] == '\0') return NULL;
172 196319336 : value += 2;
173 196319336 : continue;
174 : }
175 :
176 79226 : if (value[0] == '*') return value;
177 : }
178 :
179 3 : return NULL;
180 : }
181 :
182 : /* return a NULL terminated list of binary strings representing the value
183 : chunks separated by wildcards that makes the value portion of the filter
184 : */
185 34453 : static struct ldb_val **ldb_wildcard_decode(TALLOC_CTX *mem_ctx, const char *string)
186 : {
187 34453 : struct ldb_val **ret = NULL;
188 34453 : unsigned int val = 0;
189 11 : char *wc, *str;
190 :
191 34453 : wc = talloc_strdup(mem_ctx, string);
192 34453 : if (wc == NULL) return NULL;
193 :
194 98936 : while (wc && *wc) {
195 64483 : str = wc;
196 64483 : wc = ldb_parse_find_wildcard(str);
197 64483 : if (wc && *wc) {
198 44773 : if (wc == str) {
199 29963 : wc++;
200 29963 : continue;
201 : }
202 14810 : *wc = 0;
203 14810 : wc++;
204 : }
205 :
206 34520 : ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
207 34520 : if (ret == NULL) return NULL;
208 :
209 34520 : ret[val] = talloc(mem_ctx, struct ldb_val);
210 34520 : if (ret[val] == NULL) return NULL;
211 :
212 34520 : *(ret[val]) = ldb_binary_decode(mem_ctx, str);
213 34520 : if ((ret[val])->data == NULL) return NULL;
214 :
215 34520 : val++;
216 : }
217 :
218 34453 : if (ret != NULL) {
219 34453 : ret[val] = NULL;
220 : }
221 :
222 34442 : return ret;
223 : }
224 :
225 : static struct ldb_parse_tree *ldb_parse_filter(
226 : TALLOC_CTX *mem_ctx,
227 : const char **s,
228 : unsigned depth,
229 : unsigned max_depth);
230 :
231 :
232 : /*
233 : parse an extended match
234 :
235 : possible forms:
236 : (attr:oid:=value)
237 : (attr:dn:oid:=value)
238 : (attr:dn:=value)
239 : (:dn:oid:=value)
240 :
241 : the ':dn' part sets the dnAttributes boolean if present
242 : the oid sets the rule_id string
243 :
244 : */
245 4389492 : static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
246 : char *attr, char *value)
247 : {
248 135458 : char *p1, *p2;
249 :
250 4389492 : ret->operation = LDB_OP_EXTENDED;
251 4389492 : ret->u.extended.value = ldb_binary_decode(ret, value);
252 4389492 : if (ret->u.extended.value.data == NULL) goto failed;
253 :
254 4389492 : p1 = strchr(attr, ':');
255 4389492 : if (p1 == NULL) goto failed;
256 4389492 : p2 = strchr(p1+1, ':');
257 :
258 4389492 : *p1 = 0;
259 4389492 : if (p2) *p2 = 0;
260 :
261 4389492 : ret->u.extended.attr = attr;
262 4389492 : if (strcmp(p1+1, "dn") == 0) {
263 0 : ret->u.extended.dnAttributes = 1;
264 0 : if (p2) {
265 0 : ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
266 0 : if (ret->u.extended.rule_id == NULL) goto failed;
267 : } else {
268 0 : ret->u.extended.rule_id = NULL;
269 : }
270 : } else {
271 4389492 : ret->u.extended.dnAttributes = 0;
272 4389492 : ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
273 4389492 : if (ret->u.extended.rule_id == NULL) goto failed;
274 : }
275 :
276 4254034 : return ret;
277 :
278 0 : failed:
279 0 : talloc_free(ret);
280 0 : return NULL;
281 : }
282 :
283 139043923 : static enum ldb_parse_op ldb_parse_filtertype(TALLOC_CTX *mem_ctx, char **type, char **value, const char **s)
284 : {
285 139043923 : enum ldb_parse_op filter = 0;
286 4752843 : char *name, *val, *k;
287 139043923 : const char *p = *s;
288 4752843 : const char *t, *t1;
289 :
290 : /* retrieve attributetype name */
291 139043923 : t = p;
292 :
293 139043923 : if (*p == '@') { /* for internal attributes the first char can be @ */
294 716581 : p++;
295 : }
296 :
297 1891988471 : while ((isascii(*p) && isalnum((unsigned char)*p)) || (*p == '-') || (*p == '.')) {
298 : /* attribute names can only be alphanums */
299 1752944548 : p++;
300 : }
301 :
302 139043923 : if (*p == ':') { /* but extended searches have : and . chars too */
303 4389494 : p = strstr(p, ":=");
304 4389494 : if (p == NULL) { /* malformed attribute name */
305 2 : return 0;
306 : }
307 : }
308 :
309 139043921 : t1 = p;
310 :
311 139043921 : while (isspace((unsigned char)*p)) p++;
312 :
313 139043921 : if (!strchr("=<>~:", *p)) {
314 4 : return 0;
315 : }
316 :
317 : /* save name */
318 139043917 : name = (char *)talloc_memdup(mem_ctx, t, t1 - t + 1);
319 139043917 : if (name == NULL) return 0;
320 139043917 : name[t1 - t] = '\0';
321 :
322 : /* retrieve filtertype */
323 :
324 139043917 : if (*p == '=') {
325 130026767 : filter = LDB_OP_EQUALITY;
326 4399813 : } else if (*p != '\0' && *(p + 1) == '=') {
327 4399809 : switch (*p) {
328 1292 : case '<':
329 1292 : filter = LDB_OP_LESS;
330 1292 : p++;
331 1292 : break;
332 9025 : case '>':
333 9025 : filter = LDB_OP_GREATER;
334 9025 : p++;
335 9025 : break;
336 0 : case '~':
337 0 : filter = LDB_OP_APPROX;
338 0 : p++;
339 0 : break;
340 4389492 : case ':':
341 4389492 : filter = LDB_OP_EXTENDED;
342 4389492 : p++;
343 4389492 : break;
344 : }
345 : }
346 134426578 : if (!filter) {
347 4 : talloc_free(name);
348 4 : return 0;
349 : }
350 139043913 : p++;
351 :
352 139045515 : while (isspace((unsigned char)*p)) p++;
353 :
354 : /* retrieve value */
355 169043552 : t = p;
356 :
357 1524618586 : while (*p && ((*p != ')') || ((*p == ')') && (*(p - 1) == '\\')))) p++;
358 :
359 139043913 : val = (char *)talloc_memdup(mem_ctx, t, p - t + 1);
360 139043913 : if (val == NULL) {
361 0 : talloc_free(name);
362 0 : return 0;
363 : }
364 139043913 : val[p - t] = '\0';
365 :
366 139043913 : k = &(val[p - t]);
367 :
368 : /* remove trailing spaces from value */
369 139043913 : while ((k > val) && (isspace((unsigned char)*(k - 1)))) k--;
370 139043913 : *k = '\0';
371 :
372 139043913 : *type = name;
373 139043913 : *value = val;
374 139043913 : *s = p;
375 139043913 : return filter;
376 : }
377 :
378 : /*
379 : <simple> ::= <attributetype> <filtertype> <attributevalue>
380 : */
381 139043923 : static struct ldb_parse_tree *ldb_parse_simple(TALLOC_CTX *mem_ctx, const char **s)
382 : {
383 4752843 : char *attr, *value;
384 4752843 : struct ldb_parse_tree *ret;
385 4752843 : enum ldb_parse_op filtertype;
386 :
387 139043923 : ret = talloc_zero(mem_ctx, struct ldb_parse_tree);
388 139043923 : if (!ret) {
389 0 : errno = ENOMEM;
390 0 : return NULL;
391 : }
392 :
393 139043923 : filtertype = ldb_parse_filtertype(ret, &attr, &value, s);
394 139043923 : if (!filtertype) {
395 10 : talloc_free(ret);
396 10 : return NULL;
397 : }
398 :
399 139043913 : switch (filtertype) {
400 :
401 0 : case LDB_OP_PRESENT:
402 0 : ret->operation = LDB_OP_PRESENT;
403 0 : ret->u.present.attr = attr;
404 0 : break;
405 :
406 134644104 : case LDB_OP_EQUALITY:
407 :
408 134644104 : if (strcmp(value, "*") == 0) {
409 95589205 : ret->operation = LDB_OP_PRESENT;
410 95589205 : ret->u.present.attr = attr;
411 95589205 : break;
412 : }
413 :
414 39054899 : if (ldb_parse_find_wildcard(value) != NULL) {
415 34453 : ret->operation = LDB_OP_SUBSTRING;
416 34453 : ret->u.substring.attr = attr;
417 34453 : ret->u.substring.start_with_wildcard = 0;
418 34453 : ret->u.substring.end_with_wildcard = 0;
419 34453 : ret->u.substring.chunks = ldb_wildcard_decode(ret, value);
420 34453 : if (ret->u.substring.chunks == NULL){
421 0 : talloc_free(ret);
422 0 : return NULL;
423 : }
424 34453 : if (value[0] == '*')
425 29963 : ret->u.substring.start_with_wildcard = 1;
426 34453 : if (value[strlen(value) - 1] == '*')
427 14743 : ret->u.substring.end_with_wildcard = 1;
428 34453 : talloc_free(value);
429 :
430 34453 : break;
431 : }
432 :
433 39020446 : ret->operation = LDB_OP_EQUALITY;
434 39020446 : ret->u.equality.attr = attr;
435 39020446 : ret->u.equality.value = ldb_binary_decode(ret, value);
436 39020446 : if (ret->u.equality.value.data == NULL) {
437 2 : talloc_free(ret);
438 2 : return NULL;
439 : }
440 39020444 : talloc_free(value);
441 39020444 : break;
442 :
443 9025 : case LDB_OP_GREATER:
444 9025 : ret->operation = LDB_OP_GREATER;
445 9025 : ret->u.comparison.attr = attr;
446 9025 : ret->u.comparison.value = ldb_binary_decode(ret, value);
447 9025 : if (ret->u.comparison.value.data == NULL) {
448 0 : talloc_free(ret);
449 0 : return NULL;
450 : }
451 9025 : talloc_free(value);
452 9025 : break;
453 :
454 1292 : case LDB_OP_LESS:
455 1292 : ret->operation = LDB_OP_LESS;
456 1292 : ret->u.comparison.attr = attr;
457 1292 : ret->u.comparison.value = ldb_binary_decode(ret, value);
458 1292 : if (ret->u.comparison.value.data == NULL) {
459 0 : talloc_free(ret);
460 0 : return NULL;
461 : }
462 1292 : talloc_free(value);
463 1292 : break;
464 :
465 0 : case LDB_OP_APPROX:
466 0 : ret->operation = LDB_OP_APPROX;
467 0 : ret->u.comparison.attr = attr;
468 0 : ret->u.comparison.value = ldb_binary_decode(ret, value);
469 0 : if (ret->u.comparison.value.data == NULL) {
470 0 : talloc_free(ret);
471 0 : return NULL;
472 : }
473 0 : talloc_free(value);
474 0 : break;
475 :
476 4389492 : case LDB_OP_EXTENDED:
477 :
478 4389492 : ret = ldb_parse_extended(ret, attr, value);
479 4389492 : break;
480 :
481 0 : default:
482 0 : talloc_free(ret);
483 0 : return NULL;
484 : }
485 :
486 134291071 : return ret;
487 : }
488 :
489 :
490 : /*
491 : parse a filterlist
492 : <and> ::= '&' <filterlist>
493 : <or> ::= '|' <filterlist>
494 : <filterlist> ::= <filter> | <filter> <filterlist>
495 : */
496 50574029 : static struct ldb_parse_tree *ldb_parse_filterlist(
497 : TALLOC_CTX *mem_ctx,
498 : const char **s,
499 : unsigned depth,
500 : unsigned max_depth)
501 : {
502 1866890 : struct ldb_parse_tree *ret, *next;
503 1866890 : enum ldb_parse_op op;
504 50574029 : const char *p = *s;
505 :
506 50574029 : switch (*p) {
507 5167423 : case '&':
508 5167423 : op = LDB_OP_AND;
509 5167423 : break;
510 45256823 : case '|':
511 45256823 : op = LDB_OP_OR;
512 45256823 : break;
513 0 : default:
514 0 : return NULL;
515 : }
516 50574029 : p++;
517 :
518 50574029 : while (isspace((unsigned char)*p)) p++;
519 :
520 50574029 : ret = talloc(mem_ctx, struct ldb_parse_tree);
521 50574029 : if (!ret) {
522 0 : errno = ENOMEM;
523 0 : return NULL;
524 : }
525 :
526 50574029 : ret->operation = op;
527 50574029 : ret->u.list.num_elements = 1;
528 50574029 : ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
529 50574029 : if (!ret->u.list.elements) {
530 0 : errno = ENOMEM;
531 0 : talloc_free(ret);
532 0 : return NULL;
533 : }
534 :
535 101148058 : ret->u.list.elements[0] =
536 50574029 : ldb_parse_filter(ret->u.list.elements, &p, depth, max_depth);
537 50574029 : if (!ret->u.list.elements[0]) {
538 118 : talloc_free(ret);
539 118 : return NULL;
540 : }
541 :
542 50573911 : while (isspace((unsigned char)*p)) p++;
543 :
544 103807736 : while (*p) {
545 3835351 : struct ldb_parse_tree **e;
546 103807736 : if (*p == ')') {
547 48707020 : break;
548 : }
549 :
550 55202289 : next = ldb_parse_filter(
551 53233827 : ret->u.list.elements, &p, depth, max_depth);
552 53233827 : if (next == NULL) {
553 : /* an invalid filter element */
554 2 : talloc_free(ret);
555 2 : return NULL;
556 : }
557 53233825 : e = talloc_realloc(ret, ret->u.list.elements,
558 : struct ldb_parse_tree *,
559 : ret->u.list.num_elements + 1);
560 53233825 : if (!e) {
561 0 : errno = ENOMEM;
562 0 : talloc_free(ret);
563 0 : return NULL;
564 : }
565 53233825 : ret->u.list.elements = e;
566 53233825 : ret->u.list.elements[ret->u.list.num_elements] = next;
567 53233825 : ret->u.list.num_elements++;
568 53233825 : while (isspace((unsigned char)*p)) p++;
569 : }
570 :
571 50573909 : *s = p;
572 :
573 50573909 : return ret;
574 : }
575 :
576 :
577 : /*
578 : <not> ::= '!' <filter>
579 : */
580 1355586 : static struct ldb_parse_tree *ldb_parse_not(
581 : TALLOC_CTX *mem_ctx,
582 : const char **s,
583 : unsigned depth,
584 : unsigned max_depth)
585 : {
586 52980 : struct ldb_parse_tree *ret;
587 1355586 : const char *p = *s;
588 :
589 1355586 : if (*p != '!') {
590 0 : return NULL;
591 : }
592 1355586 : p++;
593 :
594 1355586 : ret = talloc(mem_ctx, struct ldb_parse_tree);
595 1355586 : if (!ret) {
596 0 : errno = ENOMEM;
597 0 : return NULL;
598 : }
599 :
600 1355586 : ret->operation = LDB_OP_NOT;
601 1355586 : ret->u.isnot.child = ldb_parse_filter(ret, &p, depth, max_depth);
602 1355586 : if (!ret->u.isnot.child) {
603 11 : talloc_free(ret);
604 11 : return NULL;
605 : }
606 :
607 1355575 : *s = p;
608 :
609 1355575 : return ret;
610 : }
611 :
612 : /*
613 : parse a filtercomp
614 : <filtercomp> ::= <and> | <or> | <not> | <simple>
615 : */
616 176572376 : static struct ldb_parse_tree *ldb_parse_filtercomp(
617 : TALLOC_CTX *mem_ctx,
618 : const char **s,
619 : unsigned depth,
620 : unsigned max_depth)
621 : {
622 6570537 : struct ldb_parse_tree *ret;
623 176572376 : const char *p = *s;
624 :
625 176572376 : while (isspace((unsigned char)*p)) p++;
626 :
627 176572376 : switch (*p) {
628 5317206 : case '&':
629 5317206 : ret = ldb_parse_filterlist(mem_ctx, &p, depth, max_depth);
630 5317206 : break;
631 :
632 45256823 : case '|':
633 45256823 : ret = ldb_parse_filterlist(mem_ctx, &p, depth, max_depth);
634 45256823 : break;
635 :
636 1355586 : case '!':
637 1355586 : ret = ldb_parse_not(mem_ctx, &p, depth, max_depth);
638 1355586 : break;
639 :
640 0 : case '(':
641 : case ')':
642 0 : return NULL;
643 :
644 124642761 : default:
645 124642761 : ret = ldb_parse_simple(mem_ctx, &p);
646 :
647 : }
648 :
649 176572376 : *s = p;
650 176572376 : return ret;
651 : }
652 :
653 : /*
654 : <filter> ::= '(' <filtercomp> ')'
655 : */
656 176572377 : static struct ldb_parse_tree *ldb_parse_filter(
657 : TALLOC_CTX *mem_ctx,
658 : const char **s,
659 : unsigned depth,
660 : unsigned max_depth)
661 : {
662 6570537 : struct ldb_parse_tree *ret;
663 176572377 : const char *p = *s;
664 :
665 : /*
666 : * Check the depth of the parse tree, and reject the input if
667 : * max_depth exceeded. This avoids stack overflow
668 : * issues.
669 : */
670 176572377 : if (depth > max_depth) {
671 1 : return NULL;
672 : }
673 176572376 : depth++;
674 :
675 176572376 : if (*p != '(') {
676 0 : return NULL;
677 : }
678 176572376 : p++;
679 :
680 176572376 : ret = ldb_parse_filtercomp(mem_ctx, &p, depth, max_depth);
681 :
682 176572376 : if (*p != ')') {
683 132 : return NULL;
684 : }
685 176572241 : p++;
686 :
687 176572241 : while (isspace((unsigned char)*p)) {
688 0 : p++;
689 : }
690 :
691 176572241 : *s = p;
692 :
693 176572241 : return ret;
694 : }
695 :
696 :
697 : /*
698 : main parser entry point. Takes a search string and returns a parse tree
699 :
700 : expression ::= <simple> | <filter>
701 : */
702 85810097 : struct ldb_parse_tree *ldb_parse_tree(TALLOC_CTX *mem_ctx, const char *s)
703 : {
704 85810097 : unsigned depth = 0;
705 :
706 85810098 : while (s && isspace((unsigned char)*s)) s++;
707 :
708 85810097 : if (s == NULL || *s == 0) {
709 44509266 : s = "(|(objectClass=*)(distinguishedName=*))";
710 : }
711 :
712 85810097 : if (*s == '(') {
713 71408935 : return ldb_parse_filter(
714 : mem_ctx, &s, depth, LDB_MAX_PARSE_TREE_DEPTH);
715 : }
716 :
717 14401162 : return ldb_parse_simple(mem_ctx, &s);
718 : }
719 :
720 :
721 : /*
722 : construct a ldap parse filter given a parse tree
723 : */
724 250640 : char *ldb_filter_from_tree(TALLOC_CTX *mem_ctx, const struct ldb_parse_tree *tree)
725 : {
726 22 : char *s, *s2, *ret;
727 22 : unsigned int i;
728 :
729 250640 : if (tree == NULL) {
730 0 : return NULL;
731 : }
732 :
733 250640 : switch (tree->operation) {
734 72770 : case LDB_OP_AND:
735 : case LDB_OP_OR:
736 72770 : ret = talloc_asprintf(mem_ctx, "(%c", tree->operation==LDB_OP_AND?'&':'|');
737 72770 : if (ret == NULL) return NULL;
738 244402 : for (i=0;i<tree->u.list.num_elements;i++) {
739 171632 : s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
740 171632 : if (s == NULL) {
741 0 : talloc_free(ret);
742 0 : return NULL;
743 : }
744 171632 : s2 = talloc_asprintf_append(ret, "%s", s);
745 171632 : talloc_free(s);
746 171632 : if (s2 == NULL) {
747 0 : talloc_free(ret);
748 0 : return NULL;
749 : }
750 171632 : ret = s2;
751 : }
752 72770 : s = talloc_asprintf_append(ret, ")");
753 72770 : if (s == NULL) {
754 0 : talloc_free(ret);
755 0 : return NULL;
756 : }
757 72770 : return s;
758 10805 : case LDB_OP_NOT:
759 10805 : s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
760 10805 : if (s == NULL) return NULL;
761 :
762 10805 : ret = talloc_asprintf(mem_ctx, "(!%s)", s);
763 10805 : talloc_free(s);
764 10805 : return ret;
765 50608 : case LDB_OP_EQUALITY:
766 50608 : s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
767 50608 : if (s == NULL) return NULL;
768 50608 : ret = talloc_asprintf(mem_ctx, "(%s=%s)",
769 50608 : tree->u.equality.attr, s);
770 50608 : talloc_free(s);
771 50608 : return ret;
772 10163 : case LDB_OP_SUBSTRING:
773 10163 : ret = talloc_asprintf(mem_ctx, "(%s=%s", tree->u.substring.attr,
774 10163 : tree->u.substring.start_with_wildcard?"*":"");
775 10163 : if (ret == NULL) return NULL;
776 20326 : for (i = 0; tree->u.substring.chunks && tree->u.substring.chunks[i]; i++) {
777 10163 : s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
778 10163 : if (s2 == NULL) {
779 0 : talloc_free(ret);
780 0 : return NULL;
781 : }
782 10163 : if (tree->u.substring.chunks[i+1] ||
783 10163 : tree->u.substring.end_with_wildcard) {
784 10163 : s = talloc_asprintf_append(ret, "%s*", s2);
785 : } else {
786 0 : s = talloc_asprintf_append(ret, "%s", s2);
787 : }
788 10163 : if (s == NULL) {
789 0 : talloc_free(ret);
790 0 : return NULL;
791 : }
792 10163 : ret = s;
793 : }
794 10163 : s = talloc_asprintf_append(ret, ")");
795 10163 : if (s == NULL) {
796 0 : talloc_free(ret);
797 0 : return NULL;
798 : }
799 10185 : ret = s;
800 10163 : return ret;
801 7 : case LDB_OP_GREATER:
802 7 : s = ldb_binary_encode(mem_ctx, tree->u.comparison.value);
803 7 : if (s == NULL) return NULL;
804 7 : ret = talloc_asprintf(mem_ctx, "(%s>=%s)",
805 7 : tree->u.comparison.attr, s);
806 7 : talloc_free(s);
807 7 : return ret;
808 6 : case LDB_OP_LESS:
809 6 : s = ldb_binary_encode(mem_ctx, tree->u.comparison.value);
810 6 : if (s == NULL) return NULL;
811 6 : ret = talloc_asprintf(mem_ctx, "(%s<=%s)",
812 6 : tree->u.comparison.attr, s);
813 6 : talloc_free(s);
814 6 : return ret;
815 100815 : case LDB_OP_PRESENT:
816 100815 : ret = talloc_asprintf(mem_ctx, "(%s=*)", tree->u.present.attr);
817 100815 : return ret;
818 0 : case LDB_OP_APPROX:
819 0 : s = ldb_binary_encode(mem_ctx, tree->u.comparison.value);
820 0 : if (s == NULL) return NULL;
821 0 : ret = talloc_asprintf(mem_ctx, "(%s~=%s)",
822 0 : tree->u.comparison.attr, s);
823 0 : talloc_free(s);
824 0 : return ret;
825 5466 : case LDB_OP_EXTENDED:
826 5466 : s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
827 5466 : if (s == NULL) return NULL;
828 21864 : ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
829 5466 : tree->u.extended.attr?tree->u.extended.attr:"",
830 5466 : tree->u.extended.dnAttributes?":dn":"",
831 5466 : tree->u.extended.rule_id?":":"",
832 5466 : tree->u.extended.rule_id?tree->u.extended.rule_id:"",
833 : s);
834 5466 : talloc_free(s);
835 5466 : return ret;
836 : }
837 :
838 0 : return NULL;
839 : }
840 :
841 :
842 : /*
843 : walk a parse tree, calling the provided callback on each node
844 : */
845 432093143 : int ldb_parse_tree_walk(struct ldb_parse_tree *tree,
846 : int (*callback)(struct ldb_parse_tree *tree, void *),
847 : void *private_context)
848 : {
849 18472130 : unsigned int i;
850 18472130 : int ret;
851 :
852 432093143 : ret = callback(tree, private_context);
853 432093143 : if (ret != LDB_SUCCESS) {
854 0 : return ret;
855 : }
856 :
857 432093143 : switch (tree->operation) {
858 119659854 : case LDB_OP_AND:
859 : case LDB_OP_OR:
860 386040518 : for (i=0;i<tree->u.list.num_elements;i++) {
861 260930966 : ret = ldb_parse_tree_walk(tree->u.list.elements[i], callback, private_context);
862 260930966 : if (ret != LDB_SUCCESS) {
863 0 : return ret;
864 : }
865 : }
866 119659854 : break;
867 5463279 : case LDB_OP_NOT:
868 5463279 : ret = ldb_parse_tree_walk(tree->u.isnot.child, callback, private_context);
869 5463279 : if (ret != LDB_SUCCESS) {
870 0 : return ret;
871 : }
872 5252065 : break;
873 288709094 : case LDB_OP_EQUALITY:
874 : case LDB_OP_GREATER:
875 : case LDB_OP_LESS:
876 : case LDB_OP_APPROX:
877 : case LDB_OP_SUBSTRING:
878 : case LDB_OP_PRESENT:
879 : case LDB_OP_EXTENDED:
880 288709094 : break;
881 : }
882 413621013 : return LDB_SUCCESS;
883 : }
884 :
885 : struct parse_tree_attr_replace_ctx {
886 : const char *attr;
887 : const char *replace;
888 : };
889 :
890 : /*
891 : callback for ldb_parse_tree_attr_replace()
892 : */
893 0 : static int parse_tree_attr_replace(struct ldb_parse_tree *tree, void *private_context)
894 : {
895 0 : struct parse_tree_attr_replace_ctx *ctx = private_context;
896 0 : switch (tree->operation) {
897 0 : case LDB_OP_EQUALITY:
898 0 : if (ldb_attr_cmp(tree->u.equality.attr, ctx->attr) == 0) {
899 0 : tree->u.equality.attr = ctx->replace;
900 : }
901 0 : break;
902 0 : case LDB_OP_GREATER:
903 : case LDB_OP_LESS:
904 : case LDB_OP_APPROX:
905 0 : if (ldb_attr_cmp(tree->u.comparison.attr, ctx->attr) == 0) {
906 0 : tree->u.comparison.attr = ctx->replace;
907 : }
908 0 : break;
909 0 : case LDB_OP_SUBSTRING:
910 0 : if (ldb_attr_cmp(tree->u.substring.attr, ctx->attr) == 0) {
911 0 : tree->u.substring.attr = ctx->replace;
912 : }
913 0 : break;
914 0 : case LDB_OP_PRESENT:
915 0 : if (ldb_attr_cmp(tree->u.present.attr, ctx->attr) == 0) {
916 0 : tree->u.present.attr = ctx->replace;
917 : }
918 0 : break;
919 0 : case LDB_OP_EXTENDED:
920 0 : if (tree->u.extended.attr &&
921 0 : ldb_attr_cmp(tree->u.extended.attr, ctx->attr) == 0) {
922 0 : tree->u.extended.attr = ctx->replace;
923 : }
924 0 : break;
925 0 : default:
926 0 : break;
927 : }
928 0 : return LDB_SUCCESS;
929 : }
930 :
931 : /*
932 : replace any occurrences of an attribute name in the parse tree with a
933 : new name
934 : */
935 0 : void ldb_parse_tree_attr_replace(struct ldb_parse_tree *tree,
936 : const char *attr,
937 : const char *replace)
938 : {
939 0 : struct parse_tree_attr_replace_ctx ctx;
940 :
941 0 : ctx.attr = attr;
942 0 : ctx.replace = replace;
943 :
944 0 : ldb_parse_tree_walk(tree, parse_tree_attr_replace, &ctx);
945 0 : }
946 :
947 : /*
948 : shallow copy a tree - copying only the elements array so that the caller
949 : can safely add new elements without changing the message
950 : */
951 439302 : struct ldb_parse_tree *ldb_parse_tree_copy_shallow(TALLOC_CTX *mem_ctx,
952 : const struct ldb_parse_tree *ot)
953 : {
954 3923 : unsigned int i;
955 3923 : struct ldb_parse_tree *nt;
956 :
957 439302 : nt = talloc(mem_ctx, struct ldb_parse_tree);
958 439302 : if (!nt) {
959 0 : return NULL;
960 : }
961 :
962 439302 : *nt = *ot;
963 :
964 439302 : switch (ot->operation) {
965 121432 : case LDB_OP_AND:
966 : case LDB_OP_OR:
967 121432 : nt->u.list.elements = talloc_array(nt, struct ldb_parse_tree *,
968 : ot->u.list.num_elements);
969 121432 : if (!nt->u.list.elements) {
970 0 : talloc_free(nt);
971 0 : return NULL;
972 : }
973 :
974 422665 : for (i=0;i<ot->u.list.num_elements;i++) {
975 602466 : nt->u.list.elements[i] =
976 301233 : ldb_parse_tree_copy_shallow(nt->u.list.elements,
977 301233 : ot->u.list.elements[i]);
978 301233 : if (!nt->u.list.elements[i]) {
979 0 : talloc_free(nt);
980 0 : return NULL;
981 : }
982 : }
983 120668 : break;
984 12421 : case LDB_OP_NOT:
985 24842 : nt->u.isnot.child = ldb_parse_tree_copy_shallow(nt,
986 12421 : ot->u.isnot.child);
987 12421 : if (!nt->u.isnot.child) {
988 0 : talloc_free(nt);
989 0 : return NULL;
990 : }
991 12421 : break;
992 302290 : case LDB_OP_EQUALITY:
993 : case LDB_OP_GREATER:
994 : case LDB_OP_LESS:
995 : case LDB_OP_APPROX:
996 : case LDB_OP_SUBSTRING:
997 : case LDB_OP_PRESENT:
998 : case LDB_OP_EXTENDED:
999 302290 : break;
1000 : }
1001 :
1002 435379 : return nt;
1003 : }
1004 :
1005 : /* Get the attribute (if any) associated with the top node of a parse tree. */
1006 751489425 : const char *ldb_parse_tree_get_attr(const struct ldb_parse_tree *tree)
1007 : {
1008 751489425 : switch (tree->operation) {
1009 396818925 : case LDB_OP_AND:
1010 : case LDB_OP_OR:
1011 : case LDB_OP_NOT:
1012 396818925 : return NULL;
1013 280988791 : case LDB_OP_EQUALITY:
1014 280988791 : return tree->u.equality.attr;
1015 3843396 : case LDB_OP_SUBSTRING:
1016 3843396 : return tree->u.substring.attr;
1017 5619453 : case LDB_OP_GREATER:
1018 : case LDB_OP_LESS:
1019 : case LDB_OP_APPROX:
1020 5619453 : return tree->u.comparison.attr;
1021 54730907 : case LDB_OP_PRESENT:
1022 54730907 : return tree->u.present.attr;
1023 23534 : case LDB_OP_EXTENDED:
1024 23534 : return tree->u.extended.attr;
1025 : }
1026 :
1027 0 : return NULL;
1028 : }
|
