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(*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(*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 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
 198
 199
 200 /*
 201   parse an extended match
 202
 203   possible forms:
 204         (attr:oid:=value)
 205         (attr:dn:oid:=value)
 206         (attr:dn:=value)
 207         (:dn:oid:=value)
 208
 209   the ':dn' part sets the dnAttributes boolean if present
 210   the oid sets the rule_id string
 211
 212 */
 213 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 214                                                  char *attr, char *value)
 215 {
 216         char *p1, *p2, *p3;
 217         ret->operation = LDB_OP_EXTENDED;
 218         ret->u.extended.value = ldb_binary_decode(ret, value);
 219         p1 = strchr(attr, ':');
 220         if (p1 == NULL) goto failed;
 221         p2 = strchr(p1+1, ':');
 222         if (p2 == NULL) goto failed;
 223         p3 = strchr(p2+1, ':');
 224
 225         *p1 = 0;
 226         *p2 = 0;
 227         if (p3) *p3 = 0;
 228
 229         ret->u.extended.attr = talloc_strdup(ret, attr);
 230         if (ret->u.extended.attr == NULL) goto failed;
 231         if (strcmp(p1+1, "dn") == 0) {
 232                 ret->u.extended.dnAttributes = 1;
 233                 if (p3) {
 234                         ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 235                         if (ret->u.extended.rule_id == NULL) goto failed;
 236                 } else {
 237                         ret->u.extended.rule_id = NULL;
 238                 }
 239         } else {
 240                 ret->u.extended.dnAttributes = 0;
 241                 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 242                 if (ret->u.extended.rule_id == NULL) goto failed;
 243         }
 244         ret->u.extended.value = ldb_binary_decode(ret, value);
 245
 246         return ret;
 247
 248 failed:
 249         talloc_free(ret);
 250         return NULL;
 251 }
 252
 253
 254 /*
 255   <simple> ::= <attributetype> <filtertype> <attributevalue>
 256 */
 257 static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char *s)
 258 {
 259         char *eq, *val, *l;
 260         struct ldb_parse_tree *ret;
 261
 262         ret = talloc(mem_ctx, struct ldb_parse_tree);
 263         if (!ret) {
 264                 errno = ENOMEM;
 265                 return NULL;
 266         }
 267
 268         l = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 269         if (!l) {
 270                 talloc_free(ret);
 271                 return NULL;
 272         }
 273
 274         if (strchr("()&|=", *l)) {
 275                 talloc_free(ret);
 276                 return NULL;
 277         }
 278
 279         eq = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 280         if (!eq || strcmp(eq, "=") != 0) {
 281                 talloc_free(ret);
 282                 return NULL;
 283         }
 284         talloc_free(eq);
 285
 286         val = ldb_parse_lex(ret, &s, ")");
 287         if (val && strchr("()&|", *val)) {
 288                 talloc_free(ret);
 289                 return NULL;
 290         }
 291
 292         if (l[strlen(l)-1] == ':') {
 293                 /* its an extended match */
 294                 return ldb_parse_extended(ret, l, val);
 295         }
 296
 297         ret->operation = LDB_OP_SIMPLE;
 298         ret->u.simple.attr = l;
 299         ret->u.simple.value = ldb_binary_decode(ret, val);
 300
 301         return ret;
 302 }
 303
 304
 305 /*
 306   parse a filterlist
 307   <and> ::= '&' <filterlist>
 308   <or> ::= '|' <filterlist>
 309   <filterlist> ::= <filter> | <filter> <filterlist>
 310 */
 311 static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx,
 312                                                    enum ldb_parse_op op, const char *s)
 313 {
 314         struct ldb_parse_tree *ret, *next;
 315
 316         ret = talloc(mem_ctx, struct ldb_parse_tree);
 317         if (!ret) {
 318                 errno = ENOMEM;
 319                 return NULL;
 320         }
 321
 322         ret->operation = op;
 323         ret->u.list.num_elements = 1;
 324         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 325         if (!ret->u.list.elements) {
 326                 errno = ENOMEM;
 327                 talloc_free(ret);
 328                 return NULL;
 329         }
 330
 331         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &s);
 332         if (!ret->u.list.elements[0]) {
 333                 talloc_free(ret);
 334                 return NULL;
 335         }
 336
 337         while (isspace(*s)) s++;
 338
 339         while (*s && (next = ldb_parse_filter(ret->u.list.elements, &s))) {
 340                 struct ldb_parse_tree **e;
 341                 e = talloc_realloc(ret, ret->u.list.elements,
 342                                      struct ldb_parse_tree *,
 343                                      ret->u.list.num_elements+1);
 344                 if (!e) {
 345                         errno = ENOMEM;
 346                         talloc_free(ret);
 347                         return NULL;
 348                 }
 349                 ret->u.list.elements = e;
 350                 ret->u.list.elements[ret->u.list.num_elements] = next;
 351                 ret->u.list.num_elements++;
 352                 while (isspace(*s)) s++;
 353         }
 354
 355         return ret;
 356 }
 357
 358
 359 /*
 360   <not> ::= '!' <filter>
 361 */
 362 static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char *s)
 363 {
 364         struct ldb_parse_tree *ret;
 365
 366         ret = talloc(mem_ctx, struct ldb_parse_tree);
 367         if (!ret) {
 368                 errno = ENOMEM;
 369                 return NULL;
 370         }
 371
 372         ret->operation = LDB_OP_NOT;
 373         ret->u.not.child = ldb_parse_filter(ret, &s);
 374         if (!ret->u.not.child) {
 375                 talloc_free(ret);
 376                 return NULL;
 377         }
 378
 379         return ret;
 380 }
 381
 382 /*
 383   parse a filtercomp
 384   <filtercomp> ::= <and> | <or> | <not> | <simple>
 385 */
 386 static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char *s)
 387 {
 388         while (isspace(*s)) s++;
 389
 390         switch (*s) {
 391         case '&':
 392                 return ldb_parse_filterlist(mem_ctx, LDB_OP_AND, s+1);
 393
 394         case '|':
 395                 return ldb_parse_filterlist(mem_ctx, LDB_OP_OR, s+1);
 396
 397         case '!':
 398                 return ldb_parse_not(mem_ctx, s+1);
 399
 400         case '(':
 401         case ')':
 402                 return NULL;
 403         }
 404
 405         return ldb_parse_simple(mem_ctx, s);
 406 }
 407
 408
 409 /*
 410   <filter> ::= '(' <filtercomp> ')'
 411 */
 412 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s)
 413 {
 414         char *l, *s2;
 415         const char *p, *p2;
 416         struct ldb_parse_tree *ret;
 417
 418         l = ldb_parse_lex(mem_ctx, s, LDB_ALL_SEP);
 419         if (!l) {
 420                 return NULL;
 421         }
 422
 423         if (strcmp(l, "(") != 0) {
 424                 talloc_free(l);
 425                 return NULL;
 426         }
 427         talloc_free(l);
 428
 429         p = match_brace(*s);
 430         if (!p) {
 431                 return NULL;
 432         }
 433         p2 = p + 1;
 434
 435         s2 = talloc_strndup(mem_ctx, *s, p - *s);
 436         if (!s2) {
 437                 errno = ENOMEM;
 438                 return NULL;
 439         }
 440
 441         ret = ldb_parse_filtercomp(mem_ctx, s2);
 442         talloc_free(s2);
 443
 444         *s = p2;
 445
 446         return ret;
 447 }
 448
 449
 450 /*
 451   main parser entry point. Takes a search string and returns a parse tree
 452
 453   expression ::= <simple> | <filter>
 454 */
 455 struct ldb_parse_tree *ldb_parse_tree(void *mem_ctx, const char *s)
 456 {
 457         while (isspace(*s)) s++;
 458
 459         if (*s == '(') {
 460                 return ldb_parse_filter(mem_ctx, &s);
 461         }
 462
 463         return ldb_parse_simple(mem_ctx, s);
 464 }
 465
 466
 467 /*
 468   construct a ldap parse filter given a parse tree
 469 */
 470 char *ldb_filter_from_tree(void *mem_ctx, struct ldb_parse_tree *tree)
 471 {
 472         char *s, *s2, *ret;
 473         int i;
 474
 475         switch (tree->operation) {
 476         case LDB_OP_SIMPLE:
 477                 s = ldb_binary_encode(mem_ctx, tree->u.simple.value);
 478                 if (s == NULL) return NULL;
 479                 ret = talloc_asprintf(mem_ctx, "(%s=%s)",
 480                                       tree->u.simple.attr, s);
 481                 talloc_free(s);
 482                 return ret;
 483         case LDB_OP_EXTENDED:
 484                 s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
 485                 if (s == NULL) return NULL;
 486                 ret = talloc_asprintf(mem_ctx, "(%s%s%s%s=%s)",
 487                                       tree->u.extended.attr?tree->u.extended.attr:"",
 488                                       tree->u.extended.dnAttributes?":dn":"",
 489                                       tree->u.extended.rule_id?":":"",
 490                                       tree->u.extended.rule_id?tree->u.extended.rule_id:"",
 491                                       s);
 492                 talloc_free(s);
 493                 return ret;
 494         case LDB_OP_AND:
 495         case LDB_OP_OR:
 496                 ret = talloc_asprintf(mem_ctx, "(%c", (char)tree->operation);
 497                 if (ret == NULL) return NULL;
 498                 for (i=0;i<tree->u.list.num_elements;i++) {
 499                         s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
 500                         if (s == NULL) {
 501                                 talloc_free(ret);
 502                                 return NULL;
 503                         }
 504                         s2 = talloc_asprintf_append(ret, "%s", s);
 505                         talloc_free(s);
 506                         if (s2 == NULL) {
 507                                 talloc_free(ret);
 508                                 return NULL;
 509                         }
 510                         ret = s2;
 511                 }
 512                 s = talloc_asprintf_append(ret, ")");
 513                 if (s == NULL) {
 514                         talloc_free(ret);
 515                         return NULL;
 516                 }
 517                 return s;
 518         case LDB_OP_NOT:
 519                 s = ldb_filter_from_tree(mem_ctx, tree->u.not.child);
 520                 if (s == NULL) return NULL;
 521
 522                 ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 523                 talloc_free(s);
 524                 return ret;
 525         }
 526
 527         return NULL;
 528 }