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 "ldb/include/ldb_parse.h"
  47 #include <ctype.h>
  48
  49
  50 /*
  51 a filter is defined by:
  52                <filter> ::= '(' <filtercomp> ')'
  53                <filtercomp> ::= <and> | <or> | <not> | <simple>
  54                <and> ::= '&' <filterlist>
  55                <or> ::= '|' <filterlist>
  56                <not> ::= '!' <filter>
  57                <filterlist> ::= <filter> | <filter> <filterlist>
  58                <simple> ::= <attributetype> <filtertype> <attributevalue>
  59                <filtertype> ::= '=' | '~=' | '<=' | '>='
  60 */
  61
  62 #define LDB_ALL_SEP "()&|=!"
  63
  64 /*
  65   return next token element. Caller frees
  66 */
  67 static char *ldb_parse_lex(TALLOC_CTX *ctx, const char **s, const char *sep)
  68 {
  69         const char *p = *s;
  70         char *ret;
  71
  72         while (isspace(*p)) {
  73                 p++;
  74         }
  75         *s = p;
  76
  77         if (*p == 0) {
  78                 return NULL;
  79         }
  80
  81         if (strchr(sep, *p)) {
  82                 (*s) = p+1;
  83                 ret = talloc_strndup(ctx, p, 1);
  84                 if (!ret) {
  85                         errno = ENOMEM;
  86                 }
  87                 return ret;
  88         }
  89
  90         while (*p && (isalnum(*p) || !strchr(sep, *p))) {
  91                 p++;
  92         }
  93
  94         if (p == *s) {
  95                 return NULL;
  96         }
  97
  98         ret = talloc_strndup(ctx, *s, p - *s);
  99         if (!ret) {
 100                 errno = ENOMEM;
 101         }
 102
 103         *s = p;
 104
 105         return ret;
 106 }
 107
 108 /*
 109   find a matching close brace in a string
 110 */
 111 static const char *match_brace(const char *s)
 112 {
 113         unsigned int count = 0;
 114         while (*s && (count != 0 || *s != ')')) {
 115                 if (*s == '(') {
 116                         count++;
 117                 }
 118                 if (*s == ')') {
 119                         count--;
 120                 }
 121                 s++;
 122         }
 123         if (! *s) {
 124                 return NULL;
 125         }
 126         return s;
 127 }
 128
 129 /*
 130    decode a RFC2254 binary string representation of a buffer.
 131    Used in LDAP filters.
 132 */
 133 struct ldb_val ldb_binary_decode(TALLOC_CTX *ctx, const char *str)
 134 {
 135         int i, j;
 136         struct ldb_val ret;
 137         int slen = strlen(str);
 138
 139         ret.data = talloc_size(ctx, slen+1);
 140         ret.length = 0;
 141         if (ret.data == NULL) return ret;
 142
 143         for (i=j=0;i<slen;i++) {
 144                 if (str[i] == '\\') {
 145                         unsigned c;
 146                         if (sscanf(&str[i+1], "%02X", &c) != 1) {
 147                                 talloc_free(ret.data);
 148                                 memset(&ret, 0, sizeof(ret));
 149                                 return ret;
 150                         }
 151                         ((uint8_t *)ret.data)[j++] = c;
 152                         i += 2;
 153                 } else {
 154                         ((uint8_t *)ret.data)[j++] = str[i];
 155                 }
 156         }
 157         ret.length = j;
 158         ((uint8_t *)ret.data)[j] = 0;
 159
 160         return ret;
 161 }
 162
 163
 164 /*
 165    encode a blob as a RFC2254 binary string, escaping any
 166    non-printable or '\' characters
 167 */
 168 const char *ldb_binary_encode(TALLOC_CTX *ctx, struct ldb_val val)
 169 {
 170         int i;
 171         char *ret;
 172         int len = val.length;
 173         unsigned char *buf = val.data;
 174
 175         for (i=0;i<val.length;i++) {
 176                 if (!isprint(buf[i]) || strchr(" *()\\&|!", buf[i])) {
 177                         len += 2;
 178                 }
 179         }
 180         ret = talloc_array(ctx, char, len+1);
 181         if (ret == NULL) return NULL;
 182
 183         len = 0;
 184         for (i=0;i<val.length;i++) {
 185                 if (!isprint(buf[i]) || strchr(" *()\\&|!", buf[i])) {
 186                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 187                         len += 3;
 188                 } else {
 189                         ret[len++] = buf[i];
 190                 }
 191         }
 192
 193         ret[len] = 0;
 194
 195         return ret;
 196 }
 197
 198 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *ctx, const char **s);
 199
 200 /*
 201   <simple> ::= <attributetype> <filtertype> <attributevalue>
 202 */
 203 static struct ldb_parse_tree *ldb_parse_simple(TALLOC_CTX *ctx, const char *s)
 204 {
 205         char *eq, *val, *l;
 206         struct ldb_parse_tree *ret;
 207
 208         ret = talloc(ctx, struct ldb_parse_tree);
 209         if (!ret) {
 210                 errno = ENOMEM;
 211                 return NULL;
 212         }
 213
 214         l = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 215         if (!l) {
 216                 talloc_free(ret);
 217                 return NULL;
 218         }
 219
 220         if (strchr("()&|=", *l)) {
 221                 talloc_free(ret);
 222                 return NULL;
 223         }
 224
 225         eq = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 226         if (!eq || strcmp(eq, "=") != 0) {
 227                 talloc_free(ret);
 228                 return NULL;
 229         }
 230         talloc_free(eq);
 231
 232         val = ldb_parse_lex(ret, &s, ")");
 233         if (val && strchr("()&|", *val)) {
 234                 talloc_free(ret);
 235                 return NULL;
 236         }
 237
 238         ret->operation = LDB_OP_SIMPLE;
 239         ret->u.simple.attr = l;
 240         ret->u.simple.value = ldb_binary_decode(ret, val);
 241
 242         return ret;
 243 }
 244
 245
 246 /*
 247   parse a filterlist
 248   <and> ::= '&' <filterlist>
 249   <or> ::= '|' <filterlist>
 250   <filterlist> ::= <filter> | <filter> <filterlist>
 251 */
 252 static struct ldb_parse_tree *ldb_parse_filterlist(TALLOC_CTX *ctx,
 253                                                    enum ldb_parse_op op, const char *s)
 254 {
 255         struct ldb_parse_tree *ret, *next;
 256
 257         ret = talloc(ctx, struct ldb_parse_tree);
 258         if (!ret) {
 259                 errno = ENOMEM;
 260                 return NULL;
 261         }
 262
 263         ret->operation = op;
 264         ret->u.list.num_elements = 1;
 265         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 266         if (!ret->u.list.elements) {
 267                 errno = ENOMEM;
 268                 talloc_free(ret);
 269                 return NULL;
 270         }
 271
 272         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &s);
 273         if (!ret->u.list.elements[0]) {
 274                 talloc_free(ret);
 275                 return NULL;
 276         }
 277
 278         while (isspace(*s)) s++;
 279
 280         while (*s && (next = ldb_parse_filter(ret->u.list.elements, &s))) {
 281                 struct ldb_parse_tree **e;
 282                 e = talloc_realloc(ret, ret->u.list.elements,
 283                                      struct ldb_parse_tree *,
 284                                      ret->u.list.num_elements+1);
 285                 if (!e) {
 286                         errno = ENOMEM;
 287                         talloc_free(ret);
 288                         return NULL;
 289                 }
 290                 ret->u.list.elements = e;
 291                 ret->u.list.elements[ret->u.list.num_elements] = next;
 292                 ret->u.list.num_elements++;
 293                 while (isspace(*s)) s++;
 294         }
 295
 296         return ret;
 297 }
 298
 299
 300 /*
 301   <not> ::= '!' <filter>
 302 */
 303 static struct ldb_parse_tree *ldb_parse_not(TALLOC_CTX *ctx, const char *s)
 304 {
 305         struct ldb_parse_tree *ret;
 306
 307         ret = talloc(ctx, struct ldb_parse_tree);
 308         if (!ret) {
 309                 errno = ENOMEM;
 310                 return NULL;
 311         }
 312
 313         ret->operation = LDB_OP_NOT;
 314         ret->u.not.child = ldb_parse_filter(ret, &s);
 315         if (!ret->u.not.child) {
 316                 talloc_free(ret);
 317                 return NULL;
 318         }
 319
 320         return ret;
 321 }
 322
 323 /*
 324   parse a filtercomp
 325   <filtercomp> ::= <and> | <or> | <not> | <simple>
 326 */
 327 static struct ldb_parse_tree *ldb_parse_filtercomp(TALLOC_CTX *ctx, const char *s)
 328 {
 329         while (isspace(*s)) s++;
 330
 331         switch (*s) {
 332         case '&':
 333                 return ldb_parse_filterlist(ctx, LDB_OP_AND, s+1);
 334
 335         case '|':
 336                 return ldb_parse_filterlist(ctx, LDB_OP_OR, s+1);
 337
 338         case '!':
 339                 return ldb_parse_not(ctx, s+1);
 340
 341         case '(':
 342         case ')':
 343                 return NULL;
 344         }
 345
 346         return ldb_parse_simple(ctx, s);
 347 }
 348
 349
 350 /*
 351   <filter> ::= '(' <filtercomp> ')'
 352 */
 353 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *ctx, const char **s)
 354 {
 355         char *l, *s2;
 356         const char *p, *p2;
 357         struct ldb_parse_tree *ret;
 358
 359         l = ldb_parse_lex(ctx, s, LDB_ALL_SEP);
 360         if (!l) {
 361                 return NULL;
 362         }
 363
 364         if (strcmp(l, "(") != 0) {
 365                 talloc_free(l);
 366                 return NULL;
 367         }
 368         talloc_free(l);
 369
 370         p = match_brace(*s);
 371         if (!p) {
 372                 return NULL;
 373         }
 374         p2 = p + 1;
 375
 376         s2 = talloc_strndup(ctx, *s, p - *s);
 377         if (!s2) {
 378                 errno = ENOMEM;
 379                 return NULL;
 380         }
 381
 382         ret = ldb_parse_filtercomp(ctx, s2);
 383         talloc_free(s2);
 384
 385         *s = p2;
 386
 387         return ret;
 388 }
 389
 390
 391 /*
 392   main parser entry point. Takes a search string and returns a parse tree
 393
 394   expression ::= <simple> | <filter>
 395 */
 396 struct ldb_parse_tree *ldb_parse_tree(TALLOC_CTX *mem_ctx, const char *s)
 397 {
 398         while (isspace(*s)) s++;
 399
 400         if (*s == '(') {
 401                 return ldb_parse_filter(mem_ctx, &s);
 402         }
 403
 404         return ldb_parse_simple(mem_ctx, s);
 405 }