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