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