source4/lib/ldb/ldb_tdb/ldb_parse.c

   1  /*
   2    Unix SMB/CIFS implementation.
   3
   4    parse a LDAP-like expression
   5
   6    Copyright (C) Andrew Tridgell 2004
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21 */
  22
  23 /*
  24   TODO:
  25       - add RFC2254 binary string handling
  26       - possibly add ~=, <= and >= handling
  27       - expand the test suite
  28       - add better parse error handling
  29
  30 */
  31
  32 #include "includes.h"
  33
  34
  35 /*
  36 a filter is defined by:
  37                <filter> ::= '(' <filtercomp> ')'
  38                <filtercomp> ::= <and> | <or> | <not> | <simple>
  39                <and> ::= '&' <filterlist>
  40                <or> ::= '|' <filterlist>
  41                <not> ::= '!' <filter>
  42                <filterlist> ::= <filter> | <filter> <filterlist>
  43                <simple> ::= <attributetype> <filtertype> <attributevalue>
  44                <filtertype> ::= '=' | '~=' | '<=' | '>='
  45 */
  46
  47 /*
  48   return next token element. Caller frees
  49 */
  50 static char *ldb_parse_lex(const char **s)
  51 {
  52         const char *p = *s;
  53         char *ret;
  54
  55         while (isspace(*p)) {
  56                 p++;
  57         }
  58         *s = p;
  59
  60         if (*p == 0) {
  61                 return NULL;
  62         }
  63
  64         if (strchr("()&|=!", *p)) {
  65                 (*s) = p+1;
  66                 ret = strndup(p, 1);
  67                 if (!ret) {
  68                         errno = ENOMEM;
  69                 }
  70                 return ret;
  71         }
  72
  73         while (*p && (isalnum(*p) || !strchr("()&|=!", *p))) {
  74                 p++;
  75         }
  76
  77         if (p == *s) {
  78                 return NULL;
  79         }
  80
  81         ret = strndup(*s, p - *s);
  82         if (!ret) {
  83                 errno = ENOMEM;
  84         }
  85
  86         *s = p;
  87
  88         return ret;
  89 }
  90
  91 /*
  92   find a matching close brace in a string
  93 */
  94 static const char *match_brace(const char *s)
  95 {
  96         unsigned int count = 0;
  97         while (*s && (count != 0 || *s != ')')) {
  98                 if (*s == '(') {
  99                         count++;
 100                 }
 101                 if (*s == ')') {
 102                         count--;
 103                 }
 104                 s++;
 105         }
 106         if (! *s) {
 107                 return NULL;
 108         }
 109         return s;
 110 }
 111
 112
 113 static struct ldb_parse_tree *ldb_parse_filter(const char **s);
 114
 115 /*
 116   <simple> ::= <attributetype> <filtertype> <attributevalue>
 117 */
 118 static struct ldb_parse_tree *ldb_parse_simple(const char *s)
 119 {
 120         char *eq, *val, *l;
 121         struct ldb_parse_tree *ret;
 122
 123         l = ldb_parse_lex(&s);
 124         if (!l) {
 125                 fprintf(stderr, "Unexpected end of expression\n");
 126                 return NULL;
 127         }
 128
 129         if (strchr("()&|=", *l)) {
 130                 fprintf(stderr, "Unexpected token '%s'\n", l);
 131                 free(l);
 132                 return NULL;
 133         }
 134
 135         eq = ldb_parse_lex(&s);
 136         if (!eq || strcmp(eq, "=") != 0) {
 137                 fprintf(stderr, "Expected '='\n");
 138                 free(l);
 139                 if (eq) free(eq);
 140                 return NULL;
 141         }
 142         free(eq);
 143
 144         val = ldb_parse_lex(&s);
 145         if (val && strchr("()&|=", *val)) {
 146                 fprintf(stderr, "Unexpected token '%s'\n", val);
 147                 free(l);
 148                 if (val) free(val);
 149                 return NULL;
 150         }
 151
 152         ret = malloc_p(struct ldb_parse_tree);
 153         if (!ret) {
 154                 errno = ENOMEM;
 155                 return NULL;
 156         }
 157
 158         ret->operation = LDB_OP_SIMPLE;
 159         ret->u.simple.attr = l;
 160         ret->u.simple.value.data = val;
 161         ret->u.simple.value.length = val?strlen(val):0;
 162
 163         return ret;
 164 }
 165
 166
 167 /*
 168   parse a filterlist
 169   <and> ::= '&' <filterlist>
 170   <or> ::= '|' <filterlist>
 171   <filterlist> ::= <filter> | <filter> <filterlist>
 172 */
 173 static struct ldb_parse_tree *ldb_parse_filterlist(enum ldb_parse_op op, const char *s)
 174 {
 175         struct ldb_parse_tree *ret, *next;
 176
 177         ret = malloc_p(struct ldb_parse_tree);
 178         if (!ret) {
 179                 errno = ENOMEM;
 180                 return NULL;
 181         }
 182
 183         ret->operation = op;
 184         ret->u.list.num_elements = 1;
 185         ret->u.list.elements = malloc_p(struct ldb_parse_tree *);
 186         if (!ret->u.list.elements) {
 187                 errno = ENOMEM;
 188                 free(ret);
 189                 return NULL;
 190         }
 191
 192         ret->u.list.elements[0] = ldb_parse_filter(&s);
 193         if (!ret->u.list.elements[0]) {
 194                 free(ret->u.list.elements);
 195                 free(ret);
 196                 return NULL;
 197         }
 198
 199         while (isspace(*s)) s++;
 200
 201         while (*s && (next = ldb_parse_filter(&s))) {
 202                 struct ldb_parse_tree **e;
 203                 e = realloc_p(ret->u.list.elements,
 204                               struct ldb_parse_tree *,
 205                               ret->u.list.num_elements+1);
 206                 if (!e) {
 207                         errno = ENOMEM;
 208                         ldb_parse_tree_free(next);
 209                         ldb_parse_tree_free(ret);
 210                         return NULL;
 211                 }
 212                 ret->u.list.elements = e;
 213                 ret->u.list.elements[ret->u.list.num_elements] = next;
 214                 ret->u.list.num_elements++;
 215                 while (isspace(*s)) s++;
 216         }
 217
 218         return ret;
 219 }
 220
 221
 222 /*
 223   <not> ::= '!' <filter>
 224 */
 225 static struct ldb_parse_tree *ldb_parse_not(const char *s)
 226 {
 227         struct ldb_parse_tree *ret;
 228
 229         ret = malloc_p(struct ldb_parse_tree);
 230         if (!ret) {
 231                 errno = ENOMEM;
 232                 return NULL;
 233         }
 234
 235         ret->operation = LDB_OP_NOT;
 236         ret->u.not.child = ldb_parse_filter(&s);
 237         if (!ret->u.not.child) {
 238                 free(ret);
 239                 return NULL;
 240         }
 241
 242         return ret;
 243 }
 244
 245 /*
 246   parse a filtercomp
 247   <filtercomp> ::= <and> | <or> | <not> | <simple>
 248 */
 249 static struct ldb_parse_tree *ldb_parse_filtercomp(const char *s)
 250 {
 251         while (isspace(*s)) s++;
 252
 253         switch (*s) {
 254         case '&':
 255                 return ldb_parse_filterlist(LDB_OP_AND, s+1);
 256
 257         case '|':
 258                 return ldb_parse_filterlist(LDB_OP_OR, s+1);
 259
 260         case '!':
 261                 return ldb_parse_not(s+1);
 262
 263         case '(':
 264         case ')':
 265                 fprintf(stderr, "Unexpected token '%c'\n", *s);
 266                 return NULL;
 267         }
 268
 269         return ldb_parse_simple(s);
 270 }
 271
 272
 273 /*
 274   <filter> ::= '(' <filtercomp> ')'
 275 */
 276 static struct ldb_parse_tree *ldb_parse_filter(const char **s)
 277 {
 278         char *l, *s2;
 279         const char *p, *p2;
 280         struct ldb_parse_tree *ret;
 281
 282         l = ldb_parse_lex(s);
 283         if (!l) {
 284                 fprintf(stderr, "Unexpected end of expression\n");
 285                 return NULL;
 286         }
 287
 288         if (strcmp(l, "(") != 0) {
 289                 free(l);
 290                 fprintf(stderr, "Expected '('\n");
 291                 return NULL;
 292         }
 293         free(l);
 294
 295         p = match_brace(*s);
 296         if (!p) {
 297                 fprintf(stderr, "Parse error - mismatched braces\n");
 298                 return NULL;
 299         }
 300         p2 = p + 1;
 301
 302         s2 = strndup(*s, p - *s);
 303         if (!s2) {
 304                 errno = ENOMEM;
 305                 return NULL;
 306         }
 307
 308         ret = ldb_parse_filtercomp(s2);
 309         free(s2);
 310
 311         *s = p2;
 312
 313         return ret;
 314 }
 315
 316
 317 /*
 318   main parser entry point. Takes a search string and returns a parse tree
 319
 320   expression ::= <simple> | <filter>
 321 */
 322 struct ldb_parse_tree *ldb_parse_tree(const char *s)
 323 {
 324         while (isspace(*s)) s++;
 325
 326         if (*s == '(') {
 327                 return ldb_parse_filter(&s);
 328         }
 329
 330         return ldb_parse_simple(s);
 331 }
 332
 333 /*
 334   free a parse tree returned from ldb_parse_tree()
 335 */
 336 void ldb_parse_tree_free(struct ldb_parse_tree *tree)
 337 {
 338         int i;
 339
 340         switch (tree->operation) {
 341         case LDB_OP_SIMPLE:
 342                 free(tree->u.simple.attr);
 343                 if (tree->u.simple.value.data) free(tree->u.simple.value.data);
 344                 break;
 345
 346         case LDB_OP_AND:
 347         case LDB_OP_OR:
 348                 for (i=0;i<tree->u.list.num_elements;i++) {
 349                         ldb_parse_tree_free(tree->u.list.elements[i]);
 350                 }
 351                 if (tree->u.list.elements) free(tree->u.list.elements);
 352                 break;
 353
 354         case LDB_OP_NOT:
 355                 ldb_parse_tree_free(tree->u.not.child);
 356                 break;
 357         }
 358
 359         free(tree);
 360 }
 361
 362 #if TEST_PROGRAM
 363 /*
 364   return a string representation of a parse tree
 365   used for debugging
 366 */
 367 static char *tree_string(struct ldb_parse_tree *tree)
 368 {
 369         char *s = NULL;
 370         char *s1, *s2;
 371         int i;
 372
 373         switch (tree->operation) {
 374         case LDB_OP_SIMPLE:
 375                 asprintf(&s, "( %s = \"%s\" )", tree->u.simple.attr,
 376                          (char *)tree->u.simple.value.data);
 377                 break;
 378
 379         case LDB_OP_AND:
 380         case LDB_OP_OR:
 381                 asprintf(&s, "( %c", tree->operation==LDB_OP_AND?'&':'|');
 382                 if (!s) return NULL;
 383
 384                 for (i=0;i<tree->u.list.num_elements;i++) {
 385                         s1 = tree_string(tree->u.list.elements[i]);
 386                         if (!s1) {
 387                                 free(s);
 388                                 return NULL;
 389                         }
 390                         asprintf(&s2, "%s %s", s, s1);
 391                         free(s);
 392                         free(s1);
 393                         s = s2;
 394                 }
 395                 if (!s) {
 396                         return NULL;
 397                 }
 398                 asprintf(&s2, "%s )", s);
 399                 free(s);
 400                 s = s2;
 401                 break;
 402
 403         case LDB_OP_NOT:
 404                 s1 = tree_string(tree->u.not.child);
 405                 asprintf(&s, "( ! %s )", s1);
 406                 free(s1);
 407                 break;
 408         }
 409         return s;
 410 }
 411
 412
 413 /*
 414   print a tree
 415  */
 416 static void print_tree(struct ldb_parse_tree *tree)
 417 {
 418         char *s = tree_string(tree);
 419         printf("%s\n", s);
 420         free(s);
 421 }
 422
 423
 424  int main(void)
 425 {
 426         char line[1000];
 427         int ret = 0;
 428
 429         while (fgets(line, sizeof(line)-1, stdin)) {
 430                 struct ldb_parse_tree *tree;
 431
 432                 if (line[strlen(line)-1] == '\n') {
 433                         line[strlen(line)-1] = 0;
 434                 }
 435                 tree = ldb_parse_tree(line);
 436                 if (!tree) {
 437                         fprintf(stderr, "Failed to parse\n");
 438                         ret = 1;
 439                         continue;
 440                 }
 441                 print_tree(tree);
 442                 ldb_parse_tree_free(tree);
 443         }
 444
 445         return ret;
 446 }
 447 #endif /* TEST_PROGRAM */
 448