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