source4/lib/ldb/common/ldb_parse.c

   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 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 parsing
  29  *
  30  *  Description: parse LDAP-like search expressions
  31  *
  32  *  Author: Andrew Tridgell
  33  */
  34
  35 /*
  36   TODO:
  37       - add RFC2254 binary string handling
  38       - possibly add ~=, <= and >= handling
  39       - expand the test suite
  40       - add better parse error handling
  41
  42 */
  43
  44 #include "includes.h"
  45 #include "ldb/include/ldb.h"
  46 #include <ctype.h>
  47
  48
  49 /*
  50 a filter is defined by:
  51                <filter> ::= '(' <filtercomp> ')'
  52                <filtercomp> ::= <and> | <or> | <not> | <simple>
  53                <and> ::= '&' <filterlist>
  54                <or> ::= '|' <filterlist>
  55                <not> ::= '!' <filter>
  56                <filterlist> ::= <filter> | <filter> <filterlist>
  57                <simple> ::= <attributetype> <filtertype> <attributevalue>
  58                <filtertype> ::= '=' | '~=' | '<=' | '>='
  59 */
  60
  61 #define LDB_ALL_SEP "()&|=!"
  62
  63 /*
  64   return next token element. Caller frees
  65 */
  66 static char *ldb_parse_lex(void *ctx, const char **s, const char *sep)
  67 {
  68         const char *p = *s;
  69         char *ret;
  70
  71         while (isspace((unsigned char)*p)) {
  72                 p++;
  73         }
  74         *s = p;
  75
  76         if (*p == 0) {
  77                 return NULL;
  78         }
  79
  80         if (strchr(sep, *p)) {
  81                 (*s) = p+1;
  82                 ret = talloc_strndup(ctx, p, 1);
  83                 if (!ret) {
  84                         errno = ENOMEM;
  85                 }
  86                 return ret;
  87         }
  88
  89         while (*p && (isalnum((unsigned char)*p) || !strchr(sep, *p))) {
  90                 p++;
  91         }
  92
  93         if (p == *s) {
  94                 return NULL;
  95         }
  96
  97         ret = talloc_strndup(ctx, *s, p - *s);
  98         if (!ret) {
  99                 errno = ENOMEM;
 100         }
 101
 102         *s = p;
 103
 104         return ret;
 105 }
 106
 107 /*
 108   find a matching close brace in a string
 109 */
 110 static const char *match_brace(const char *s)
 111 {
 112         unsigned int count = 0;
 113         while (*s && (count != 0 || *s != ')')) {
 114                 if (*s == '(') {
 115                         count++;
 116                 }
 117                 if (*s == ')') {
 118                         count--;
 119                 }
 120                 s++;
 121         }
 122         if (! *s) {
 123                 return NULL;
 124         }
 125         return s;
 126 }
 127
 128 /*
 129    decode a RFC2254 binary string representation of a buffer.
 130    Used in LDAP filters.
 131 */
 132 struct ldb_val ldb_binary_decode(void *mem_ctx, const char *str)
 133 {
 134         int i, j;
 135         struct ldb_val ret;
 136         int slen = str?strlen(str):0;
 137
 138         ret.data = talloc_size(mem_ctx, slen+1);
 139         ret.length = 0;
 140         if (ret.data == NULL) return ret;
 141
 142         for (i=j=0;i<slen;i++) {
 143                 if (str[i] == '\\') {
 144                         unsigned c;
 145                         if (sscanf(&str[i+1], "%02X", &c) != 1) {
 146                                 talloc_free(ret.data);
 147                                 memset(&ret, 0, sizeof(ret));
 148                                 return ret;
 149                         }
 150                         ((uint8_t *)ret.data)[j++] = c;
 151                         i += 2;
 152                 } else {
 153                         ((uint8_t *)ret.data)[j++] = str[i];
 154                 }
 155         }
 156         ret.length = j;
 157         ((uint8_t *)ret.data)[j] = 0;
 158
 159         return ret;
 160 }
 161
 162
 163 /*
 164    encode a blob as a RFC2254 binary string, escaping any
 165    non-printable or '\' characters
 166 */
 167 char *ldb_binary_encode(void *mem_ctx, struct ldb_val val)
 168 {
 169         int i;
 170         char *ret;
 171         int len = val.length;
 172         unsigned char *buf = val.data;
 173
 174         for (i=0;i<val.length;i++) {
 175                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 176                         len += 2;
 177                 }
 178         }
 179         ret = talloc_array(mem_ctx, char, len+1);
 180         if (ret == NULL) return NULL;
 181
 182         len = 0;
 183         for (i=0;i<val.length;i++) {
 184                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 185                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 186                         len += 3;
 187                 } else {
 188                         ret[len++] = buf[i];
 189                 }
 190         }
 191
 192         ret[len] = 0;
 193
 194         return ret;
 195 }
 196
 197 /* find the first matching wildcard */
 198 static char *ldb_parse_find_wildcard(char *value)
 199 {
 200         while (*value) {
 201                 value = strpbrk(value, "\\*");
 202                 if (value == NULL) return NULL;
 203
 204                 if (value[0] == '\\') {
 205                         if (value[1] == '\0') return NULL;
 206                         value += 2;
 207                         continue;
 208                 }
 209
 210                 if (value[0] == '*') return value;
 211         }
 212
 213         return NULL;
 214 }
 215
 216 /* return a NULL terminated list of binary strings representing the value
 217    chunks separated by wildcards that makes the value portion of the filter
 218 */
 219 static struct ldb_val **ldb_wildcard_decode(void *mem_ctx, const char *string)
 220 {
 221         struct ldb_val **ret = NULL;
 222         int val = 0;
 223         char *wc, *str;
 224
 225         wc = talloc_strdup(mem_ctx, string);
 226         if (wc == NULL) return NULL;
 227
 228         while (wc && *wc) {
 229                 str = wc;
 230                 wc = ldb_parse_find_wildcard(str);
 231                 if (wc && *wc) {
 232                         if (wc == str) {
 233                                 wc++;
 234                                 continue;
 235                         }
 236                         *wc = 0;
 237                         wc++;
 238                 }
 239
 240                 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
 241                 if (ret == NULL) return NULL;
 242
 243                 ret[val] = talloc(mem_ctx, struct ldb_val);
 244                 if (ret[val] == NULL) return NULL;
 245
 246                 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
 247                 if ((ret[val])->data == NULL) return NULL;
 248
 249                 val++;
 250         }
 251
 252         ret[val] = NULL;
 253
 254         return ret;
 255 }
 256
 257 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
 258
 259
 260 /*
 261   parse an extended match
 262
 263   possible forms:
 264         (attr:oid:=value)
 265         (attr:dn:oid:=value)
 266         (attr:dn:=value)
 267         (:dn:oid:=value)
 268
 269   the ':dn' part sets the dnAttributes boolean if present
 270   the oid sets the rule_id string
 271
 272 */
 273 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 274                                                  char *attr, char *value)
 275 {
 276         char *p1, *p2, *p3;
 277
 278         ret->operation = LDB_OP_EXTENDED;
 279         ret->u.extended.value = ldb_binary_decode(ret, value);
 280         if (ret->u.extended.value.data == NULL) goto failed;
 281
 282         p1 = strchr(attr, ':');
 283         if (p1 == NULL) goto failed;
 284         p2 = strchr(p1+1, ':');
 285         if (p2 == NULL) goto failed;
 286         p3 = strchr(p2+1, ':');
 287
 288         *p1 = 0;
 289         *p2 = 0;
 290         if (p3) *p3 = 0;
 291
 292         ret->u.extended.attr = talloc_strdup(ret, attr);
 293         if (ret->u.extended.attr == NULL) goto failed;
 294         if (strcmp(p1+1, "dn") == 0) {
 295                 ret->u.extended.dnAttributes = 1;
 296                 if (p3) {
 297                         ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 298                         if (ret->u.extended.rule_id == NULL) goto failed;
 299                 } else {
 300                         ret->u.extended.rule_id = NULL;
 301                 }
 302         } else {
 303                 ret->u.extended.dnAttributes = 0;
 304                 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 305                 if (ret->u.extended.rule_id == NULL) goto failed;
 306         }
 307
 308         return ret;
 309
 310 failed:
 311         talloc_free(ret);
 312         return NULL;
 313 }
 314
 315
 316 /*
 317   <simple> ::= <attributetype> <filtertype> <attributevalue>
 318 */
 319 static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char *s)
 320 {
 321         char *eq, *val, *l;
 322         struct ldb_parse_tree *ret;
 323
 324         ret = talloc(mem_ctx, struct ldb_parse_tree);
 325         if (!ret) {
 326                 errno = ENOMEM;
 327                 return NULL;
 328         }
 329
 330         l = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 331         if (!l) {
 332                 talloc_free(ret);
 333                 return NULL;
 334         }
 335
 336         if (strchr("()&|=", *l)) {
 337                 talloc_free(ret);
 338                 return NULL;
 339         }
 340
 341         eq = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 342         if (!eq || strcmp(eq, "=") != 0) {
 343                 talloc_free(ret);
 344                 return NULL;
 345         }
 346         talloc_free(eq);
 347
 348         val = ldb_parse_lex(ret, &s, ")");
 349         if (val && strchr("()&|", *val)) {
 350                 talloc_free(ret);
 351                 return NULL;
 352         }
 353
 354         if (l[strlen(l)-1] == ':') {
 355                 /* its an extended match */
 356                 return ldb_parse_extended(ret, l, val);
 357         }
 358
 359         if (val && strcmp(val, "*") == 0) {
 360                 ret->operation = LDB_OP_PRESENT;
 361                 ret->u.present.attr = l;
 362
 363                 return ret;
 364         }
 365
 366         if (val && ldb_parse_find_wildcard(val) != NULL) {
 367                 ret->operation = LDB_OP_SUBSTRING;
 368                 ret->u.substring.attr = l;
 369                 ret->u.substring.start_with_wildcard = 0;
 370                 ret->u.substring.end_with_wildcard = 0;
 371                 ret->u.substring.chunks = ldb_wildcard_decode(ret, val);
 372                 if (ret->u.substring.chunks == NULL){
 373                         talloc_free(ret);
 374                         return NULL;
 375                 }
 376                 if (val[0] == '*') ret->u.substring.start_with_wildcard = 1;
 377                 if (val[strlen(val) - 1] == '*') ret->u.substring.end_with_wildcard = 1;
 378
 379                 return ret;
 380         }
 381
 382         ret->operation = LDB_OP_SIMPLE;
 383         ret->u.simple.attr = l;
 384         ret->u.simple.value = ldb_binary_decode(ret, val);
 385         if (ret->u.simple.value.data == NULL) {
 386                 talloc_free(ret);
 387                 return NULL;
 388         }
 389
 390         return ret;
 391 }
 392
 393
 394 /*
 395   parse a filterlist
 396   <and> ::= '&' <filterlist>
 397   <or> ::= '|' <filterlist>
 398   <filterlist> ::= <filter> | <filter> <filterlist>
 399 */
 400 static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx,
 401                                                    enum ldb_parse_op op, const char *s)
 402 {
 403         struct ldb_parse_tree *ret, *next;
 404
 405         ret = talloc(mem_ctx, struct ldb_parse_tree);
 406         if (!ret) {
 407                 errno = ENOMEM;
 408                 return NULL;
 409         }
 410
 411         ret->operation = op;
 412         ret->u.list.num_elements = 1;
 413         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 414         if (!ret->u.list.elements) {
 415                 errno = ENOMEM;
 416                 talloc_free(ret);
 417                 return NULL;
 418         }
 419
 420         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &s);
 421         if (!ret->u.list.elements[0]) {
 422                 talloc_free(ret);
 423                 return NULL;
 424         }
 425
 426         while (isspace((unsigned char)*s)) s++;
 427
 428         while (*s && (next = ldb_parse_filter(ret->u.list.elements, &s))) {
 429                 struct ldb_parse_tree **e;
 430                 e = talloc_realloc(ret, ret->u.list.elements,
 431                                      struct ldb_parse_tree *,
 432                                      ret->u.list.num_elements+1);
 433                 if (!e) {
 434                         errno = ENOMEM;
 435                         talloc_free(ret);
 436                         return NULL;
 437                 }
 438                 ret->u.list.elements = e;
 439                 ret->u.list.elements[ret->u.list.num_elements] = next;
 440                 ret->u.list.num_elements++;
 441                 while (isspace((unsigned char)*s)) s++;
 442         }
 443
 444         return ret;
 445 }
 446
 447
 448 /*
 449   <not> ::= '!' <filter>
 450 */
 451 static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char *s)
 452 {
 453         struct ldb_parse_tree *ret;
 454
 455         ret = talloc(mem_ctx, struct ldb_parse_tree);
 456         if (!ret) {
 457                 errno = ENOMEM;
 458                 return NULL;
 459         }
 460
 461         ret->operation = LDB_OP_NOT;
 462         ret->u.not.child = ldb_parse_filter(ret, &s);
 463         if (!ret->u.not.child) {
 464                 talloc_free(ret);
 465                 return NULL;
 466         }
 467
 468         return ret;
 469 }
 470
 471 /*
 472   parse a filtercomp
 473   <filtercomp> ::= <and> | <or> | <not> | <simple>
 474 */
 475 static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char *s)
 476 {
 477         while (isspace((unsigned char)*s)) s++;
 478
 479         switch (*s) {
 480         case '&':
 481                 return ldb_parse_filterlist(mem_ctx, LDB_OP_AND, s+1);
 482
 483         case '|':
 484                 return ldb_parse_filterlist(mem_ctx, LDB_OP_OR, s+1);
 485
 486         case '!':
 487                 return ldb_parse_not(mem_ctx, s+1);
 488
 489         case '(':
 490         case ')':
 491                 return NULL;
 492         }
 493
 494         return ldb_parse_simple(mem_ctx, s);
 495 }
 496
 497
 498 /*
 499   <filter> ::= '(' <filtercomp> ')'
 500 */
 501 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s)
 502 {
 503         char *l, *s2;
 504         const char *p, *p2;
 505         struct ldb_parse_tree *ret;
 506
 507         l = ldb_parse_lex(mem_ctx, s, LDB_ALL_SEP);
 508         if (!l) {
 509                 return NULL;
 510         }
 511
 512         if (strcmp(l, "(") != 0) {
 513                 talloc_free(l);
 514                 return NULL;
 515         }
 516         talloc_free(l);
 517
 518         p = match_brace(*s);
 519         if (!p) {
 520                 return NULL;
 521         }
 522         p2 = p + 1;
 523
 524         s2 = talloc_strndup(mem_ctx, *s, p - *s);
 525         if (!s2) {
 526                 errno = ENOMEM;
 527                 return NULL;
 528         }
 529
 530         ret = ldb_parse_filtercomp(mem_ctx, s2);
 531         talloc_free(s2);
 532
 533         *s = p2;
 534
 535         return ret;
 536 }
 537
 538
 539 /*
 540   main parser entry point. Takes a search string and returns a parse tree
 541
 542   expression ::= <simple> | <filter>
 543 */
 544 struct ldb_parse_tree *ldb_parse_tree(void *mem_ctx, const char *s)
 545 {
 546         while (isspace((unsigned char)*s)) s++;
 547
 548         if (*s == '(') {
 549                 return ldb_parse_filter(mem_ctx, &s);
 550         }
 551
 552         return ldb_parse_simple(mem_ctx, s);
 553 }
 554
 555
 556 /*
 557   construct a ldap parse filter given a parse tree
 558 */
 559 char *ldb_filter_from_tree(void *mem_ctx, struct ldb_parse_tree *tree)
 560 {
 561         char *s, *s2, *ret;
 562         int i;
 563
 564         switch (tree->operation) {
 565         case LDB_OP_SIMPLE:
 566                 s = ldb_binary_encode(mem_ctx, tree->u.simple.value);
 567                 if (s == NULL) return NULL;
 568                 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
 569                                       tree->u.simple.attr, s);
 570                 talloc_free(s);
 571                 return ret;
 572         case LDB_OP_EXTENDED:
 573                 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
 574                 if (s == NULL) return NULL;
 575                 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)",
 576                                       tree->u.extended.attr?tree->u.extended.attr:"",
 577                                       tree->u.extended.dnAttributes?":dn":"",
 578                                       tree->u.extended.rule_id?":":"",
 579                                       tree->u.extended.rule_id?tree->u.extended.rule_id:"",
 580                                       s);
 581                 talloc_free(s);
 582                 return ret;
 583         case LDB_OP_SUBSTRING:
 584                 ret = talloc_strdup(mem_ctx, (tree->u.substring.start_with_wildcard)?"*":"");
 585                 if (ret == NULL) return NULL;
 586                 for (i = 0; tree->u.substring.chunks[i]; i++) {
 587                         s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
 588                         if (s2 == NULL) {
 589                                 talloc_free(ret);
 590                                 return NULL;
 591                         }
 592                         s = talloc_asprintf_append(ret, "%s*", s2);
 593                         if (s == NULL) {
 594                                 talloc_free(ret);
 595                                 return NULL;
 596                         }
 597                         ret = s;
 598                 }
 599                 if ( ! tree->u.substring.end_with_wildcard ) {
 600                         ret[strlen(ret) - 1] = '\0'; /* remove last wildcard */
 601                 }
 602                 return ret;
 603         case LDB_OP_PRESENT:
 604                 ret = talloc_strdup(mem_ctx, "*");
 605                 if (ret == NULL) return NULL;
 606                 return ret;
 607         case LDB_OP_AND:
 608         case LDB_OP_OR:
 609                 ret = talloc_asprintf(mem_ctx, "(%c", (char)tree->operation);
 610                 if (ret == NULL) return NULL;
 611                 for (i=0;i<tree->u.list.num_elements;i++) {
 612                         s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
 613                         if (s == NULL) {
 614                                 talloc_free(ret);
 615                                 return NULL;
 616                         }
 617                         s2 = talloc_asprintf_append(ret, "%s", s);
 618                         talloc_free(s);
 619                         if (s2 == NULL) {
 620                                 talloc_free(ret);
 621                                 return NULL;
 622                         }
 623                         ret = s2;
 624                 }
 625                 s = talloc_asprintf_append(ret, ")");
 626                 if (s == NULL) {
 627                         talloc_free(ret);
 628                         return NULL;
 629                 }
 630                 return s;
 631         case LDB_OP_NOT:
 632                 s = ldb_filter_from_tree(mem_ctx, tree->u.not.child);
 633                 if (s == NULL) return NULL;
 634
 635                 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 636                 talloc_free(s);
 637                 return ret;
 638         }
 639
 640         return NULL;
 641 }