source/lib/ldb/common/ldb_match.c

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