f639effc96b17f621fca53360ce84af92e6a015d
[ira/wip.git] / source4 / lib / ldb / common / ldb_match.c
1 /* 
2    ldb database library
3
4    Copyright (C) Andrew Tridgell  2004-2005
5    Copyright (C) Simo Sorce            2005
6
7      ** NOTE! The following LGPL license applies to the ldb
8      ** library. This does NOT imply that all of Samba is released
9      ** under the LGPL
10    
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.
15
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.
20
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/>.
23 */
24
25 /*
26  *  Name: ldb
27  *
28  *  Component: ldb expression matching
29  *
30  *  Description: ldb expression matching 
31  *
32  *  Author: Andrew Tridgell
33  */
34
35 #include "ldb_private.h"
36
37 /*
38   check if the scope matches in a search result
39 */
40 static int ldb_match_scope(struct ldb_context *ldb,
41                            struct ldb_dn *base,
42                            struct ldb_dn *dn,
43                            enum ldb_scope scope)
44 {
45         int ret = 0;
46
47         if (base == NULL || dn == NULL) {
48                 return 1;
49         }
50
51         switch (scope) {
52         case LDB_SCOPE_BASE:
53                 if (ldb_dn_compare(base, dn) == 0) {
54                         ret = 1;
55                 }
56                 break;
57
58         case LDB_SCOPE_ONELEVEL:
59                 if (ldb_dn_get_comp_num(dn) == (ldb_dn_get_comp_num(base) + 1)) {
60                         if (ldb_dn_compare_base(base, dn) == 0) {
61                                 ret = 1;
62                         }
63                 }
64                 break;
65                 
66         case LDB_SCOPE_SUBTREE:
67         default:
68                 if (ldb_dn_compare_base(base, dn) == 0) {
69                         ret = 1;
70                 }
71                 break;
72         }
73
74         return ret;
75 }
76
77
78 /*
79   match if node is present
80 */
81 static int ldb_match_present(struct ldb_context *ldb, 
82                              const struct ldb_message *msg,
83                              const struct ldb_parse_tree *tree,
84                              enum ldb_scope scope)
85 {
86         if (ldb_attr_dn(tree->u.present.attr) == 0) {
87                 return 1;
88         }
89
90         if (ldb_msg_find_element(msg, tree->u.present.attr)) {
91                 return 1;
92         }
93
94         return 0;
95 }
96
97 static int ldb_match_comparison(struct ldb_context *ldb, 
98                                 const struct ldb_message *msg,
99                                 const struct ldb_parse_tree *tree,
100                                 enum ldb_scope scope,
101                                 enum ldb_parse_op comp_op)
102 {
103         unsigned int i;
104         struct ldb_message_element *el;
105         const struct ldb_schema_attribute *a;
106         int ret;
107
108         /* FIXME: APPROX comparison not handled yet */
109         if (comp_op == LDB_OP_APPROX) return 0;
110
111         el = ldb_msg_find_element(msg, tree->u.comparison.attr);
112         if (el == NULL) {
113                 return 0;
114         }
115
116         a = ldb_schema_attribute_by_name(ldb, el->name);
117
118         for (i = 0; i < el->num_values; i++) {
119                 ret = a->syntax->comparison_fn(ldb, ldb, &el->values[i], &tree->u.comparison.value);
120
121                 if (ret == 0) {
122                         return 1;
123                 }
124                 if (ret > 0 && comp_op == LDB_OP_GREATER) {
125                         return 1;
126                 }
127                 if (ret < 0 && comp_op == LDB_OP_LESS) {
128                         return 1;
129                 }
130         }
131
132         return 0;
133 }
134
135 /*
136   match a simple leaf node
137 */
138 static int ldb_match_equality(struct ldb_context *ldb, 
139                               const struct ldb_message *msg,
140                               const struct ldb_parse_tree *tree,
141                               enum ldb_scope scope)
142 {
143         unsigned int i;
144         struct ldb_message_element *el;
145         const struct ldb_schema_attribute *a;
146         struct ldb_dn *valuedn;
147         int ret;
148
149         if (ldb_attr_dn(tree->u.equality.attr) == 0) {
150                 valuedn = ldb_dn_from_ldb_val(ldb, ldb, &tree->u.equality.value);
151                 if (valuedn == NULL) {
152                         return 0;
153                 }
154
155                 ret = ldb_dn_compare(msg->dn, valuedn);
156
157                 talloc_free(valuedn);
158
159                 if (ret == 0) return 1;
160                 return 0;
161         }
162
163         /* TODO: handle the "*" case derived from an extended search
164            operation without the attibute type defined */
165         el = ldb_msg_find_element(msg, tree->u.equality.attr);
166         if (el == NULL) {
167                 return 0;
168         }
169
170         a = ldb_schema_attribute_by_name(ldb, el->name);
171
172         for (i=0;i<el->num_values;i++) {
173                 if (a->syntax->comparison_fn(ldb, ldb, &tree->u.equality.value, 
174                                              &el->values[i]) == 0) {
175                         return 1;
176                 }
177         }
178
179         return 0;
180 }
181
182 static int ldb_wildcard_compare(struct ldb_context *ldb,
183                                 const struct ldb_parse_tree *tree,
184                                 const struct ldb_val value)
185 {
186         const struct ldb_schema_attribute *a;
187         struct ldb_val val;
188         struct ldb_val cnk;
189         struct ldb_val *chunk;
190         char *p, *g;
191         uint8_t *save_p = NULL;
192         int c = 0;
193
194         a = ldb_schema_attribute_by_name(ldb, tree->u.substring.attr);
195
196         if(a->syntax->canonicalise_fn(ldb, ldb, &value, &val) != 0)
197                 return -1;
198
199         save_p = val.data;
200         cnk.data = NULL;
201
202         if ( ! tree->u.substring.start_with_wildcard ) {
203
204                 chunk = tree->u.substring.chunks[c];
205                 if(a->syntax->canonicalise_fn(ldb, ldb, chunk, &cnk) != 0) goto failed;
206
207                 /* This deals with wildcard prefix searches on binary attributes (eg objectGUID) */
208                 if (cnk.length > val.length) {
209                         goto failed;
210                 }
211                 if (memcmp((char *)val.data, (char *)cnk.data, cnk.length) != 0) goto failed;
212                 val.length -= cnk.length;
213                 val.data += cnk.length;
214                 c++;
215                 talloc_free(cnk.data);
216                 cnk.data = NULL;
217         }
218
219         while (tree->u.substring.chunks[c]) {
220
221                 chunk = tree->u.substring.chunks[c];
222                 if(a->syntax->canonicalise_fn(ldb, ldb, chunk, &cnk) != 0) goto failed;
223
224                 /* FIXME: case of embedded nulls */
225                 p = strstr((char *)val.data, (char *)cnk.data);
226                 if (p == NULL) goto failed;
227                 if ( (! tree->u.substring.chunks[c + 1]) && (! tree->u.substring.end_with_wildcard) ) {
228                         do { /* greedy */
229                                 g = strstr((char *)p + cnk.length, (char *)cnk.data);
230                                 if (g) p = g;
231                         } while(g);
232                 }
233                 val.length = val.length - (p - (char *)(val.data)) - cnk.length;
234                 val.data = (uint8_t *)(p + cnk.length);
235                 c++;
236                 talloc_free(cnk.data);
237                 cnk.data = NULL;
238         }
239
240         if ( (! tree->u.substring.end_with_wildcard) && (*(val.data) != 0) ) goto failed; /* last chunk have not reached end of string */
241         talloc_free(save_p);
242         return 1;
243
244 failed:
245         talloc_free(save_p);
246         talloc_free(cnk.data);
247         return 0;
248 }
249
250 /*
251   match a simple leaf node
252 */
253 static int ldb_match_substring(struct ldb_context *ldb, 
254                                const struct ldb_message *msg,
255                                const struct ldb_parse_tree *tree,
256                                enum ldb_scope scope)
257 {
258         unsigned int i;
259         struct ldb_message_element *el;
260
261         el = ldb_msg_find_element(msg, tree->u.substring.attr);
262         if (el == NULL) {
263                 return 0;
264         }
265
266         for (i = 0; i < el->num_values; i++) {
267                 if (ldb_wildcard_compare(ldb, tree, el->values[i]) == 1) {
268                         return 1;
269                 }
270         }
271
272         return 0;
273 }
274
275
276 /*
277   bitwise-and comparator
278 */
279 static int ldb_comparator_and(const struct ldb_val *v1, const struct ldb_val *v2)
280 {
281         uint64_t i1, i2;
282         i1 = strtoull((char *)v1->data, NULL, 0);
283         i2 = strtoull((char *)v2->data, NULL, 0);
284         return ((i1 & i2) == i2);
285 }
286
287 /*
288   bitwise-or comparator
289 */
290 static int ldb_comparator_or(const struct ldb_val *v1, const struct ldb_val *v2)
291 {
292         uint64_t i1, i2;
293         i1 = strtoull((char *)v1->data, NULL, 0);
294         i2 = strtoull((char *)v2->data, NULL, 0);
295         return ((i1 & i2) != 0);
296 }
297
298
299 /*
300   extended match, handles things like bitops
301 */
302 static int ldb_match_extended(struct ldb_context *ldb, 
303                               const struct ldb_message *msg,
304                               const struct ldb_parse_tree *tree,
305                               enum ldb_scope scope)
306 {
307         int i;
308         const struct {
309                 const char *oid;
310                 int (*comparator)(const struct ldb_val *, const struct ldb_val *);
311         } rules[] = {
312                 { LDB_OID_COMPARATOR_AND, ldb_comparator_and},
313                 { LDB_OID_COMPARATOR_OR, ldb_comparator_or}
314         };
315         int (*comp)(const struct ldb_val *, const struct ldb_val *) = NULL;
316         struct ldb_message_element *el;
317
318         if (tree->u.extended.dnAttributes) {
319                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb: dnAttributes extended match not supported yet");
320                 return -1;
321         }
322         if (tree->u.extended.rule_id == NULL) {
323                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb: no-rule extended matches not supported yet");
324                 return -1;
325         }
326         if (tree->u.extended.attr == NULL) {
327                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb: no-attribute extended matches not supported yet");
328                 return -1;
329         }
330
331         for (i=0;i<ARRAY_SIZE(rules);i++) {
332                 if (strcmp(rules[i].oid, tree->u.extended.rule_id) == 0) {
333                         comp = rules[i].comparator;
334                         break;
335                 }
336         }
337         if (comp == NULL) {
338                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb: unknown extended rule_id %s",
339                           tree->u.extended.rule_id);
340                 return -1;
341         }
342
343         /* find the message element */
344         el = ldb_msg_find_element(msg, tree->u.extended.attr);
345         if (el == NULL) {
346                 return 0;
347         }
348
349         for (i=0;i<el->num_values;i++) {
350                 int ret = comp(&el->values[i], &tree->u.extended.value);
351                 if (ret == -1 || ret == 1) return ret;
352         }
353
354         return 0;
355 }
356
357 /*
358   return 0 if the given parse tree matches the given message. Assumes
359   the message is in sorted order
360
361   return 1 if it matches, and 0 if it doesn't match
362
363   this is a recursive function, and does short-circuit evaluation
364  */
365 static int ldb_match_message(struct ldb_context *ldb, 
366                              const struct ldb_message *msg,
367                              const struct ldb_parse_tree *tree,
368                              enum ldb_scope scope)
369 {
370         unsigned int i;
371         int v;
372
373         switch (tree->operation) {
374         case LDB_OP_AND:
375                 for (i=0;i<tree->u.list.num_elements;i++) {
376                         v = ldb_match_message(ldb, msg, tree->u.list.elements[i], scope);
377                         if (!v) return 0;
378                 }
379                 return 1;
380
381         case LDB_OP_OR:
382                 for (i=0;i<tree->u.list.num_elements;i++) {
383                         v = ldb_match_message(ldb, msg, tree->u.list.elements[i], scope);
384                         if (v) return 1;
385                 }
386                 return 0;
387
388         case LDB_OP_NOT:
389                 return ! ldb_match_message(ldb, msg, tree->u.isnot.child, scope);
390
391         case LDB_OP_EQUALITY:
392                 return ldb_match_equality(ldb, msg, tree, scope);
393
394         case LDB_OP_SUBSTRING:
395                 return ldb_match_substring(ldb, msg, tree, scope);
396
397         case LDB_OP_GREATER:
398                 return ldb_match_comparison(ldb, msg, tree, scope, LDB_OP_GREATER);
399
400         case LDB_OP_LESS:
401                 return ldb_match_comparison(ldb, msg, tree, scope, LDB_OP_LESS);
402
403         case LDB_OP_PRESENT:
404                 return ldb_match_present(ldb, msg, tree, scope);
405
406         case LDB_OP_APPROX:
407                 return ldb_match_comparison(ldb, msg, tree, scope, LDB_OP_APPROX);
408
409         case LDB_OP_EXTENDED:
410                 return ldb_match_extended(ldb, msg, tree, scope);
411
412         }
413
414         return 0;
415 }
416
417 int ldb_match_msg(struct ldb_context *ldb,
418                   const struct ldb_message *msg,
419                   const struct ldb_parse_tree *tree,
420                   struct ldb_dn *base,
421                   enum ldb_scope scope)
422 {
423         if ( ! ldb_match_scope(ldb, base, msg->dn, scope) ) {
424                 return 0;
425         }
426
427         return ldb_match_message(ldb, msg, tree, scope);
428 }
429
430 int ldb_match_msg_objectclass(const struct ldb_message *msg,
431                               const char *objectclass)
432 {
433         int i;
434         struct ldb_message_element *el = ldb_msg_find_element(msg, "objectClass");
435         if (!el) {
436                 return 0;
437         }
438         for (i=0; i < el->num_values; i++) {
439                 if (ldb_attr_cmp((const char *)el->values[i].data, objectclass) == 0) {
440                         return 1;
441                 }
442         }
443         return 0;
444 }
445
446
447