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