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