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(TALLOC_CTX *ctx, 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 = talloc_strndup(ctx, 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 = talloc_strndup(ctx, *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(TALLOC_CTX *ctx, const char **s);
 132
 133 /*
 134   <simple> ::= <attributetype> <filtertype> <attributevalue>
 135 */
 136 static struct ldb_parse_tree *ldb_parse_simple(TALLOC_CTX *ctx, const char *s)
 137 {
 138         char *eq, *val, *l;
 139         struct ldb_parse_tree *ret;
 140
 141         ret = talloc_p(ctx, struct ldb_parse_tree);
 142         if (!ret) {
 143                 errno = ENOMEM;
 144                 return NULL;
 145         }
 146
 147         l = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 148         if (!l) {
 149                 talloc_free(ret);
 150                 return NULL;
 151         }
 152
 153         if (strchr("()&|=", *l)) {
 154                 talloc_free(ret);
 155                 return NULL;
 156         }
 157
 158         eq = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
 159         if (!eq || strcmp(eq, "=") != 0) {
 160                 talloc_free(ret);
 161                 return NULL;
 162         }
 163         talloc_free(eq);
 164
 165         val = ldb_parse_lex(ret, &s, ")");
 166         if (val && strchr("()&|", *val)) {
 167                 talloc_free(ret);
 168                 return NULL;
 169         }
 170
 171         ret->operation = LDB_OP_SIMPLE;
 172         ret->u.simple.attr = l;
 173         ret->u.simple.value.data = val;
 174         ret->u.simple.value.length = val?strlen(val):0;
 175
 176         return ret;
 177 }
 178
 179
 180 /*
 181   parse a filterlist
 182   <and> ::= '&' <filterlist>
 183   <or> ::= '|' <filterlist>
 184   <filterlist> ::= <filter> | <filter> <filterlist>
 185 */
 186 static struct ldb_parse_tree *ldb_parse_filterlist(TALLOC_CTX *ctx,
 187                                                    enum ldb_parse_op op, const char *s)
 188 {
 189         struct ldb_parse_tree *ret, *next;
 190
 191         ret = talloc_p(ctx, struct ldb_parse_tree);
 192         if (!ret) {
 193                 errno = ENOMEM;
 194                 return NULL;
 195         }
 196
 197         ret->operation = op;
 198         ret->u.list.num_elements = 1;
 199         ret->u.list.elements = talloc_p(ret, struct ldb_parse_tree *);
 200         if (!ret->u.list.elements) {
 201                 errno = ENOMEM;
 202                 talloc_free(ret);
 203                 return NULL;
 204         }
 205
 206         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &s);
 207         if (!ret->u.list.elements[0]) {
 208                 talloc_free(ret);
 209                 return NULL;
 210         }
 211
 212         while (isspace(*s)) s++;
 213
 214         while (*s && (next = ldb_parse_filter(ret->u.list.elements, &s))) {
 215                 struct ldb_parse_tree **e;
 216                 e = talloc_realloc_p(ret, ret->u.list.elements,
 217                                      struct ldb_parse_tree *,
 218                                      ret->u.list.num_elements+1);
 219                 if (!e) {
 220                         errno = ENOMEM;
 221                         talloc_free(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(TALLOC_CTX *ctx, const char *s)
 238 {
 239         struct ldb_parse_tree *ret;
 240
 241         ret = talloc_p(ctx, 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(ret, &s);
 249         if (!ret->u.not.child) {
 250                 talloc_free(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(TALLOC_CTX *ctx, const char *s)
 262 {
 263         while (isspace(*s)) s++;
 264
 265         switch (*s) {
 266         case '&':
 267                 return ldb_parse_filterlist(ctx, LDB_OP_AND, s+1);
 268
 269         case '|':
 270                 return ldb_parse_filterlist(ctx, LDB_OP_OR, s+1);
 271
 272         case '!':
 273                 return ldb_parse_not(ctx, s+1);
 274
 275         case '(':
 276         case ')':
 277                 return NULL;
 278         }
 279
 280         return ldb_parse_simple(ctx, s);
 281 }
 282
 283
 284 /*
 285   <filter> ::= '(' <filtercomp> ')'
 286 */
 287 static struct ldb_parse_tree *ldb_parse_filter(TALLOC_CTX *ctx, const char **s)
 288 {
 289         char *l, *s2;
 290         const char *p, *p2;
 291         struct ldb_parse_tree *ret;
 292
 293         l = ldb_parse_lex(ctx, s, LDB_ALL_SEP);
 294         if (!l) {
 295                 return NULL;
 296         }
 297
 298         if (strcmp(l, "(") != 0) {
 299                 talloc_free(l);
 300                 return NULL;
 301         }
 302         talloc_free(l);
 303
 304         p = match_brace(*s);
 305         if (!p) {
 306                 return NULL;
 307         }
 308         p2 = p + 1;
 309
 310         s2 = talloc_strndup(ctx, *s, p - *s);
 311         if (!s2) {
 312                 errno = ENOMEM;
 313                 return NULL;
 314         }
 315
 316         ret = ldb_parse_filtercomp(ctx, s2);
 317         talloc_free(s2);
 318
 319         *s = p2;
 320
 321         return ret;
 322 }
 323
 324
 325 /*
 326   main parser entry point. Takes a search string and returns a parse tree
 327
 328   expression ::= <simple> | <filter>
 329 */
 330 struct ldb_parse_tree *ldb_parse_tree(struct ldb_context *ldb, const char *s)
 331 {
 332         while (isspace(*s)) s++;
 333
 334         if (*s == '(') {
 335                 return ldb_parse_filter(ldb, &s);
 336         }
 337
 338         return ldb_parse_simple(ldb, s);
 339 }
 340
 341 /*
 342   free a parse tree returned from ldb_parse_tree()
 343 */
 344 void ldb_parse_tree_free(struct ldb_context *ldb, struct ldb_parse_tree *tree)
 345 {
 346         talloc_free(tree);
 347 }
 348