4 Copyright (C) Andrew Tridgell 2004-2005
5 Copyright (C) Simo Sorce 2005
7 ** NOTE! The following LGPL license applies to the ldb
8 ** library. This does NOT imply that all of Samba is released
11 This library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU Lesser General Public
13 License as published by the Free Software Foundation; either
14 version 3 of the License, or (at your option) any later version.
16 This library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 Lesser General Public License for more details.
21 You should have received a copy of the GNU Lesser General Public
22 License along with this library; if not, see <http://www.gnu.org/licenses/>.
28 * Component: ldb expression matching
30 * Description: ldb expression matching
32 * Author: Andrew Tridgell
35 #include "ldb_private.h"
36 #include "dlinklist.h"
39 check if the scope matches in a search result
41 static int ldb_match_scope(struct ldb_context
*ldb
,
48 if (base
== NULL
|| dn
== NULL
) {
54 if (ldb_dn_compare(base
, dn
) == 0) {
59 case LDB_SCOPE_ONELEVEL
:
60 if (ldb_dn_get_comp_num(dn
) == (ldb_dn_get_comp_num(base
) + 1)) {
61 if (ldb_dn_compare_base(base
, dn
) == 0) {
67 case LDB_SCOPE_SUBTREE
:
69 if (ldb_dn_compare_base(base
, dn
) == 0) {
80 match if node is present
82 static int ldb_match_present(struct ldb_context
*ldb
,
83 const struct ldb_message
*msg
,
84 const struct ldb_parse_tree
*tree
,
85 enum ldb_scope scope
, bool *matched
)
87 const struct ldb_schema_attribute
*a
;
88 struct ldb_message_element
*el
;
90 if (ldb_attr_dn(tree
->u
.present
.attr
) == 0) {
95 el
= ldb_msg_find_element(msg
, tree
->u
.present
.attr
);
101 a
= ldb_schema_attribute_by_name(ldb
, el
->name
);
103 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
106 if (a
->syntax
->operator_fn
) {
108 for (i
= 0; i
< el
->num_values
; i
++) {
109 int ret
= a
->syntax
->operator_fn(ldb
, LDB_OP_PRESENT
, a
, &el
->values
[i
], NULL
, matched
);
110 if (ret
!= LDB_SUCCESS
) return ret
;
111 if (*matched
) return LDB_SUCCESS
;
121 static int ldb_match_comparison(struct ldb_context
*ldb
,
122 const struct ldb_message
*msg
,
123 const struct ldb_parse_tree
*tree
,
124 enum ldb_scope scope
,
125 enum ldb_parse_op comp_op
, bool *matched
)
128 struct ldb_message_element
*el
;
129 const struct ldb_schema_attribute
*a
;
131 /* FIXME: APPROX comparison not handled yet */
132 if (comp_op
== LDB_OP_APPROX
) {
133 return LDB_ERR_INAPPROPRIATE_MATCHING
;
136 el
= ldb_msg_find_element(msg
, tree
->u
.comparison
.attr
);
142 a
= ldb_schema_attribute_by_name(ldb
, el
->name
);
144 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
147 for (i
= 0; i
< el
->num_values
; i
++) {
148 if (a
->syntax
->operator_fn
) {
150 ret
= a
->syntax
->operator_fn(ldb
, comp_op
, a
, &el
->values
[i
], &tree
->u
.comparison
.value
, matched
);
151 if (ret
!= LDB_SUCCESS
) return ret
;
152 if (*matched
) return LDB_SUCCESS
;
154 int ret
= a
->syntax
->comparison_fn(ldb
, ldb
, &el
->values
[i
], &tree
->u
.comparison
.value
);
160 if (ret
> 0 && comp_op
== LDB_OP_GREATER
) {
164 if (ret
< 0 && comp_op
== LDB_OP_LESS
) {
176 match a simple leaf node
178 static int ldb_match_equality(struct ldb_context
*ldb
,
179 const struct ldb_message
*msg
,
180 const struct ldb_parse_tree
*tree
,
181 enum ldb_scope scope
,
185 struct ldb_message_element
*el
;
186 const struct ldb_schema_attribute
*a
;
187 struct ldb_dn
*valuedn
;
190 if (ldb_attr_dn(tree
->u
.equality
.attr
) == 0) {
191 valuedn
= ldb_dn_from_ldb_val(ldb
, ldb
, &tree
->u
.equality
.value
);
192 if (valuedn
== NULL
) {
193 return LDB_ERR_INVALID_DN_SYNTAX
;
196 ret
= ldb_dn_compare(msg
->dn
, valuedn
);
198 talloc_free(valuedn
);
200 *matched
= (ret
== 0);
204 /* TODO: handle the "*" case derived from an extended search
205 operation without the attibute type defined */
206 el
= ldb_msg_find_element(msg
, tree
->u
.equality
.attr
);
212 a
= ldb_schema_attribute_by_name(ldb
, el
->name
);
214 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
217 for (i
=0;i
<el
->num_values
;i
++) {
218 if (a
->syntax
->operator_fn
) {
219 ret
= a
->syntax
->operator_fn(ldb
, LDB_OP_EQUALITY
, a
,
220 &tree
->u
.equality
.value
, &el
->values
[i
], matched
);
221 if (ret
!= LDB_SUCCESS
) return ret
;
222 if (*matched
) return LDB_SUCCESS
;
224 if (a
->syntax
->comparison_fn(ldb
, ldb
, &tree
->u
.equality
.value
,
225 &el
->values
[i
]) == 0) {
236 static int ldb_wildcard_compare(struct ldb_context
*ldb
,
237 const struct ldb_parse_tree
*tree
,
238 const struct ldb_val value
, bool *matched
)
240 const struct ldb_schema_attribute
*a
;
243 struct ldb_val
*chunk
;
244 uint8_t *save_p
= NULL
;
247 if (tree
->operation
!= LDB_OP_SUBSTRING
) {
249 return LDB_ERR_INAPPROPRIATE_MATCHING
;
252 a
= ldb_schema_attribute_by_name(ldb
, tree
->u
.substring
.attr
);
254 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
257 if (tree
->u
.substring
.chunks
== NULL
) {
262 if (a
->syntax
->canonicalise_fn(ldb
, ldb
, &value
, &val
) != 0) {
263 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
269 if ( ! tree
->u
.substring
.start_with_wildcard
) {
271 chunk
= tree
->u
.substring
.chunks
[c
];
272 if (a
->syntax
->canonicalise_fn(ldb
, ldb
, chunk
, &cnk
) != 0) goto mismatch
;
274 /* This deals with wildcard prefix searches on binary attributes (eg objectGUID) */
275 if (cnk
.length
> val
.length
) {
279 * Empty strings are returned as length 0. Ensure
280 * we can cope with this.
282 if (cnk
.length
== 0) {
286 if (memcmp((char *)val
.data
, (char *)cnk
.data
, cnk
.length
) != 0) goto mismatch
;
287 val
.length
-= cnk
.length
;
288 val
.data
+= cnk
.length
;
290 talloc_free(cnk
.data
);
294 while (tree
->u
.substring
.chunks
[c
]) {
297 chunk
= tree
->u
.substring
.chunks
[c
];
298 if(a
->syntax
->canonicalise_fn(ldb
, ldb
, chunk
, &cnk
) != 0) {
302 * Empty strings are returned as length 0. Ensure
303 * we can cope with this.
305 if (cnk
.length
== 0) {
308 if (cnk
.length
> val
.length
) {
312 if ( (tree
->u
.substring
.chunks
[c
+ 1]) == NULL
&&
313 (! tree
->u
.substring
.end_with_wildcard
) ) {
315 * The last bit, after all the asterisks, must match
316 * exactly the last bit of the string.
319 p
= val
.data
+ val
.length
- cnk
.length
;
328 * Values might be binary blobs. Don't use string
329 * search, but memory search instead.
331 p
= memmem((const void *)val
.data
, val
.length
,
332 (const void *)cnk
.data
, cnk
.length
);
336 /* move val to the end of the match */
338 val
.length
-= (p
- val
.data
);
342 TALLOC_FREE(cnk
.data
);
352 talloc_free(cnk
.data
);
357 match a simple leaf node
359 static int ldb_match_substring(struct ldb_context
*ldb
,
360 const struct ldb_message
*msg
,
361 const struct ldb_parse_tree
*tree
,
362 enum ldb_scope scope
, bool *matched
)
365 struct ldb_message_element
*el
;
367 el
= ldb_msg_find_element(msg
, tree
->u
.substring
.attr
);
373 for (i
= 0; i
< el
->num_values
; i
++) {
375 ret
= ldb_wildcard_compare(ldb
, tree
, el
->values
[i
], matched
);
376 if (ret
!= LDB_SUCCESS
) return ret
;
377 if (*matched
) return LDB_SUCCESS
;
386 bitwise and/or comparator depending on oid
388 static int ldb_comparator_bitmask(const char *oid
, const struct ldb_val
*v1
, const struct ldb_val
*v2
,
395 if (v1
->length
>= sizeof(ibuf
)-1) {
396 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
398 memcpy(ibuf
, (char *)v1
->data
, v1
->length
);
399 ibuf
[v1
->length
] = 0;
400 i1
= strtoull(ibuf
, &endptr
, 0);
401 if (endptr
!= NULL
) {
402 if (endptr
== ibuf
|| *endptr
!= 0) {
403 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
407 if (v2
->length
>= sizeof(ibuf
)-1) {
408 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
411 memcpy(ibuf
, (char *)v2
->data
, v2
->length
);
412 ibuf
[v2
->length
] = 0;
413 i2
= strtoull(ibuf
, &endptr
, 0);
414 if (endptr
!= NULL
) {
415 if (endptr
== ibuf
|| *endptr
!= 0) {
416 return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX
;
419 if (strcmp(LDB_OID_COMPARATOR_AND
, oid
) == 0) {
420 *matched
= ((i1
& i2
) == i2
);
421 } else if (strcmp(LDB_OID_COMPARATOR_OR
, oid
) == 0) {
422 *matched
= ((i1
& i2
) != 0);
424 return LDB_ERR_INAPPROPRIATE_MATCHING
;
429 static int ldb_match_bitmask(struct ldb_context
*ldb
,
431 const struct ldb_message
*msg
,
432 const char *attribute_to_match
,
433 const struct ldb_val
*value_to_match
,
437 struct ldb_message_element
*el
;
439 /* find the message element */
440 el
= ldb_msg_find_element(msg
, attribute_to_match
);
446 for (i
=0;i
<el
->num_values
;i
++) {
448 struct ldb_val
*v
= &el
->values
[i
];
450 ret
= ldb_comparator_bitmask(oid
, v
, value_to_match
, matched
);
451 if (ret
!= LDB_SUCCESS
) {
466 static int ldb_comparator_false(struct ldb_context
*ldb
,
468 const struct ldb_message
*msg
,
469 const char *attribute_to_match
,
470 const struct ldb_val
*value_to_match
,
478 static const struct ldb_extended_match_rule
*ldb_find_extended_match_rule(struct ldb_context
*ldb
,
481 struct ldb_extended_match_entry
*extended_match_rule
;
483 for (extended_match_rule
= ldb
->extended_match_rules
;
485 extended_match_rule
= extended_match_rule
->next
) {
486 if (strcmp(extended_match_rule
->rule
->oid
, oid
) == 0) {
487 return extended_match_rule
->rule
;
496 extended match, handles things like bitops
498 static int ldb_match_extended(struct ldb_context
*ldb
,
499 const struct ldb_message
*msg
,
500 const struct ldb_parse_tree
*tree
,
501 enum ldb_scope scope
, bool *matched
)
503 const struct ldb_extended_match_rule
*rule
;
505 if (tree
->u
.extended
.dnAttributes
) {
506 /* FIXME: We really need to find out what this ":dn" part in
507 * an extended match means and how to handle it. For now print
508 * only a warning to have s3 winbind and other tools working
509 * against us. - Matthias */
510 ldb_debug(ldb
, LDB_DEBUG_WARNING
, "ldb: dnAttributes extended match not supported yet");
512 if (tree
->u
.extended
.rule_id
== NULL
) {
513 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "ldb: no-rule extended matches not supported yet");
514 return LDB_ERR_INAPPROPRIATE_MATCHING
;
516 if (tree
->u
.extended
.attr
== NULL
) {
517 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "ldb: no-attribute extended matches not supported yet");
518 return LDB_ERR_INAPPROPRIATE_MATCHING
;
521 rule
= ldb_find_extended_match_rule(ldb
, tree
->u
.extended
.rule_id
);
524 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "ldb: unknown extended rule_id %s",
525 tree
->u
.extended
.rule_id
);
529 return rule
->callback(ldb
, rule
->oid
, msg
,
530 tree
->u
.extended
.attr
,
531 &tree
->u
.extended
.value
, matched
);
535 Check if a particular message will match the given filter
537 set *matched to true if it matches, false otherwise
539 returns LDB_SUCCESS or an error
541 this is a recursive function, and does short-circuit evaluation
543 int ldb_match_message(struct ldb_context
*ldb
,
544 const struct ldb_message
*msg
,
545 const struct ldb_parse_tree
*tree
,
546 enum ldb_scope scope
, bool *matched
)
553 if (scope
!= LDB_SCOPE_BASE
&& ldb_dn_is_special(msg
->dn
)) {
554 /* don't match special records except on base searches */
558 switch (tree
->operation
) {
560 for (i
=0;i
<tree
->u
.list
.num_elements
;i
++) {
561 ret
= ldb_match_message(ldb
, msg
, tree
->u
.list
.elements
[i
], scope
, matched
);
562 if (ret
!= LDB_SUCCESS
) return ret
;
563 if (!*matched
) return LDB_SUCCESS
;
569 for (i
=0;i
<tree
->u
.list
.num_elements
;i
++) {
570 ret
= ldb_match_message(ldb
, msg
, tree
->u
.list
.elements
[i
], scope
, matched
);
571 if (ret
!= LDB_SUCCESS
) return ret
;
572 if (*matched
) return LDB_SUCCESS
;
578 ret
= ldb_match_message(ldb
, msg
, tree
->u
.isnot
.child
, scope
, matched
);
579 if (ret
!= LDB_SUCCESS
) return ret
;
580 *matched
= ! *matched
;
583 case LDB_OP_EQUALITY
:
584 return ldb_match_equality(ldb
, msg
, tree
, scope
, matched
);
586 case LDB_OP_SUBSTRING
:
587 return ldb_match_substring(ldb
, msg
, tree
, scope
, matched
);
590 return ldb_match_comparison(ldb
, msg
, tree
, scope
, LDB_OP_GREATER
, matched
);
593 return ldb_match_comparison(ldb
, msg
, tree
, scope
, LDB_OP_LESS
, matched
);
596 return ldb_match_present(ldb
, msg
, tree
, scope
, matched
);
599 return ldb_match_comparison(ldb
, msg
, tree
, scope
, LDB_OP_APPROX
, matched
);
601 case LDB_OP_EXTENDED
:
602 return ldb_match_extended(ldb
, msg
, tree
, scope
, matched
);
605 return LDB_ERR_INAPPROPRIATE_MATCHING
;
609 return 0 if the given parse tree matches the given message. Assumes
610 the message is in sorted order
612 return 1 if it matches, and 0 if it doesn't match
615 int ldb_match_msg(struct ldb_context
*ldb
,
616 const struct ldb_message
*msg
,
617 const struct ldb_parse_tree
*tree
,
619 enum ldb_scope scope
)
624 if ( ! ldb_match_scope(ldb
, base
, msg
->dn
, scope
) ) {
628 ret
= ldb_match_message(ldb
, msg
, tree
, scope
, &matched
);
629 if (ret
!= LDB_SUCCESS
) {
630 /* to match the old API, we need to consider this a
637 int ldb_match_msg_error(struct ldb_context
*ldb
,
638 const struct ldb_message
*msg
,
639 const struct ldb_parse_tree
*tree
,
641 enum ldb_scope scope
,
644 if ( ! ldb_match_scope(ldb
, base
, msg
->dn
, scope
) ) {
649 return ldb_match_message(ldb
, msg
, tree
, scope
, matched
);
652 int ldb_match_msg_objectclass(const struct ldb_message
*msg
,
653 const char *objectclass
)
656 struct ldb_message_element
*el
= ldb_msg_find_element(msg
, "objectClass");
660 for (i
=0; i
< el
->num_values
; i
++) {
661 if (ldb_attr_cmp((const char *)el
->values
[i
].data
, objectclass
) == 0) {
668 _PRIVATE_
int ldb_register_extended_match_rules(struct ldb_context
*ldb
)
670 struct ldb_extended_match_rule
*bitmask_and
;
671 struct ldb_extended_match_rule
*bitmask_or
;
672 struct ldb_extended_match_rule
*always_false
;
675 /* Register bitmask-and match */
676 bitmask_and
= talloc_zero(ldb
, struct ldb_extended_match_rule
);
677 if (bitmask_and
== NULL
) {
678 return LDB_ERR_OPERATIONS_ERROR
;
681 bitmask_and
->oid
= LDB_OID_COMPARATOR_AND
;
682 bitmask_and
->callback
= ldb_match_bitmask
;
684 ret
= ldb_register_extended_match_rule(ldb
, bitmask_and
);
685 if (ret
!= LDB_SUCCESS
) {
689 /* Register bitmask-or match */
690 bitmask_or
= talloc_zero(ldb
, struct ldb_extended_match_rule
);
691 if (bitmask_or
== NULL
) {
692 return LDB_ERR_OPERATIONS_ERROR
;
695 bitmask_or
->oid
= LDB_OID_COMPARATOR_OR
;
696 bitmask_or
->callback
= ldb_match_bitmask
;
698 ret
= ldb_register_extended_match_rule(ldb
, bitmask_or
);
699 if (ret
!= LDB_SUCCESS
) {
703 /* Register always-false match */
704 always_false
= talloc_zero(ldb
, struct ldb_extended_match_rule
);
705 if (always_false
== NULL
) {
706 return LDB_ERR_OPERATIONS_ERROR
;
709 always_false
->oid
= SAMBA_LDAP_MATCH_ALWAYS_FALSE
;
710 always_false
->callback
= ldb_comparator_false
;
712 ret
= ldb_register_extended_match_rule(ldb
, always_false
);
713 if (ret
!= LDB_SUCCESS
) {
721 register a new ldb extended matching rule
723 int ldb_register_extended_match_rule(struct ldb_context
*ldb
,
724 const struct ldb_extended_match_rule
*rule
)
726 const struct ldb_extended_match_rule
*lookup_rule
;
727 struct ldb_extended_match_entry
*entry
;
729 lookup_rule
= ldb_find_extended_match_rule(ldb
, rule
->oid
);
731 return LDB_ERR_ENTRY_ALREADY_EXISTS
;
734 entry
= talloc_zero(ldb
, struct ldb_extended_match_entry
);
736 return LDB_ERR_OPERATIONS_ERROR
;
739 DLIST_ADD_END(ldb
->extended_match_rules
, entry
);