From 58d50a614f1b4a3fc6b60ad5f777d987263fe54f Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Wed, 31 Mar 2004 06:45:39 +0000 Subject: make a more recent snapshot of ldb available to interested people. Note that I decided to make it LGPL. ldb is not finished yet, but enough of it is there for people to get an idea of what it does, and quite a few simple tests work (This used to be commit dc6f41f9e777d37f883303ddef0d96840d80f78e) --- source4/lib/ldb/common/ldb_parse.c | 460 +++++++++++++++++++++++++++++++++++++ 1 file changed, 460 insertions(+) create mode 100644 source4/lib/ldb/common/ldb_parse.c (limited to 'source4/lib/ldb/common/ldb_parse.c') diff --git a/source4/lib/ldb/common/ldb_parse.c b/source4/lib/ldb/common/ldb_parse.c new file mode 100644 index 0000000000..4f8d469e6c --- /dev/null +++ b/source4/lib/ldb/common/ldb_parse.c @@ -0,0 +1,460 @@ +/* + ldb database library + + Copyright (C) Andrew Tridgell 2004 + + ** NOTE! The following LGPL license applies to the ldb + ** library. This does NOT imply that all of Samba is released + ** under the LGPL + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +/* + * Name: ldb + * + * Component: ldb expression parsing + * + * Description: parse LDAP-like search expressions + * + * Author: Andrew Tridgell + */ + +/* + TODO: + - add RFC2254 binary string handling + - possibly add ~=, <= and >= handling + - expand the test suite + - add better parse error handling + +*/ + +#include "includes.h" + + +/* +a filter is defined by: + ::= '(' ')' + ::= | | | + ::= '&' + ::= '|' + ::= '!' + ::= | + ::= + ::= '=' | '~=' | '<=' | '>=' +*/ + +/* + return next token element. Caller frees +*/ +static char *ldb_parse_lex(const char **s) +{ + const char *p = *s; + char *ret; + + while (isspace(*p)) { + p++; + } + *s = p; + + if (*p == 0) { + return NULL; + } + + if (strchr("()&|=!", *p)) { + (*s) = p+1; + ret = strndup(p, 1); + if (!ret) { + errno = ENOMEM; + } + return ret; + } + + while (*p && (isalnum(*p) || !strchr("()&|=!", *p))) { + p++; + } + + if (p == *s) { + return NULL; + } + + ret = strndup(*s, p - *s); + if (!ret) { + errno = ENOMEM; + } + + *s = p; + + return ret; +} + +/* + find a matching close brace in a string +*/ +static const char *match_brace(const char *s) +{ + unsigned int count = 0; + while (*s && (count != 0 || *s != ')')) { + if (*s == '(') { + count++; + } + if (*s == ')') { + count--; + } + s++; + } + if (! *s) { + return NULL; + } + return s; +} + + +static struct ldb_parse_tree *ldb_parse_filter(const char **s); + +/* + ::= +*/ +static struct ldb_parse_tree *ldb_parse_simple(const char *s) +{ + char *eq, *val, *l; + struct ldb_parse_tree *ret; + + l = ldb_parse_lex(&s); + if (!l) { + fprintf(stderr, "Unexpected end of expression\n"); + return NULL; + } + + if (strchr("()&|=", *l)) { + fprintf(stderr, "Unexpected token '%s'\n", l); + free(l); + return NULL; + } + + eq = ldb_parse_lex(&s); + if (!eq || strcmp(eq, "=") != 0) { + fprintf(stderr, "Expected '='\n"); + free(l); + if (eq) free(eq); + return NULL; + } + free(eq); + + val = ldb_parse_lex(&s); + if (val && strchr("()&|=", *val)) { + fprintf(stderr, "Unexpected token '%s'\n", val); + free(l); + if (val) free(val); + return NULL; + } + + ret = malloc_p(struct ldb_parse_tree); + if (!ret) { + errno = ENOMEM; + return NULL; + } + + ret->operation = LDB_OP_SIMPLE; + ret->u.simple.attr = l; + ret->u.simple.value.data = val; + ret->u.simple.value.length = val?strlen(val):0; + + return ret; +} + + +/* + parse a filterlist + ::= '&' + ::= '|' + ::= | +*/ +static struct ldb_parse_tree *ldb_parse_filterlist(enum ldb_parse_op op, const char *s) +{ + struct ldb_parse_tree *ret, *next; + + ret = malloc_p(struct ldb_parse_tree); + if (!ret) { + errno = ENOMEM; + return NULL; + } + + ret->operation = op; + ret->u.list.num_elements = 1; + ret->u.list.elements = malloc_p(struct ldb_parse_tree *); + if (!ret->u.list.elements) { + errno = ENOMEM; + free(ret); + return NULL; + } + + ret->u.list.elements[0] = ldb_parse_filter(&s); + if (!ret->u.list.elements[0]) { + free(ret->u.list.elements); + free(ret); + return NULL; + } + + while (isspace(*s)) s++; + + while (*s && (next = ldb_parse_filter(&s))) { + struct ldb_parse_tree **e; + e = realloc_p(ret->u.list.elements, + struct ldb_parse_tree *, + ret->u.list.num_elements+1); + if (!e) { + errno = ENOMEM; + ldb_parse_tree_free(next); + ldb_parse_tree_free(ret); + return NULL; + } + ret->u.list.elements = e; + ret->u.list.elements[ret->u.list.num_elements] = next; + ret->u.list.num_elements++; + while (isspace(*s)) s++; + } + + return ret; +} + + +/* + ::= '!' +*/ +static struct ldb_parse_tree *ldb_parse_not(const char *s) +{ + struct ldb_parse_tree *ret; + + ret = malloc_p(struct ldb_parse_tree); + if (!ret) { + errno = ENOMEM; + return NULL; + } + + ret->operation = LDB_OP_NOT; + ret->u.not.child = ldb_parse_filter(&s); + if (!ret->u.not.child) { + free(ret); + return NULL; + } + + return ret; +} + +/* + parse a filtercomp + ::= | | | +*/ +static struct ldb_parse_tree *ldb_parse_filtercomp(const char *s) +{ + while (isspace(*s)) s++; + + switch (*s) { + case '&': + return ldb_parse_filterlist(LDB_OP_AND, s+1); + + case '|': + return ldb_parse_filterlist(LDB_OP_OR, s+1); + + case '!': + return ldb_parse_not(s+1); + + case '(': + case ')': + fprintf(stderr, "Unexpected token '%c'\n", *s); + return NULL; + } + + return ldb_parse_simple(s); +} + + +/* + ::= '(' ')' +*/ +static struct ldb_parse_tree *ldb_parse_filter(const char **s) +{ + char *l, *s2; + const char *p, *p2; + struct ldb_parse_tree *ret; + + l = ldb_parse_lex(s); + if (!l) { + fprintf(stderr, "Unexpected end of expression\n"); + return NULL; + } + + if (strcmp(l, "(") != 0) { + free(l); + fprintf(stderr, "Expected '('\n"); + return NULL; + } + free(l); + + p = match_brace(*s); + if (!p) { + fprintf(stderr, "Parse error - mismatched braces\n"); + return NULL; + } + p2 = p + 1; + + s2 = strndup(*s, p - *s); + if (!s2) { + errno = ENOMEM; + return NULL; + } + + ret = ldb_parse_filtercomp(s2); + free(s2); + + *s = p2; + + return ret; +} + + +/* + main parser entry point. Takes a search string and returns a parse tree + + expression ::= | +*/ +struct ldb_parse_tree *ldb_parse_tree(const char *s) +{ + while (isspace(*s)) s++; + + if (*s == '(') { + return ldb_parse_filter(&s); + } + + return ldb_parse_simple(s); +} + +/* + free a parse tree returned from ldb_parse_tree() +*/ +void ldb_parse_tree_free(struct ldb_parse_tree *tree) +{ + int i; + + switch (tree->operation) { + case LDB_OP_SIMPLE: + free(tree->u.simple.attr); + if (tree->u.simple.value.data) free(tree->u.simple.value.data); + break; + + case LDB_OP_AND: + case LDB_OP_OR: + for (i=0;iu.list.num_elements;i++) { + ldb_parse_tree_free(tree->u.list.elements[i]); + } + if (tree->u.list.elements) free(tree->u.list.elements); + break; + + case LDB_OP_NOT: + ldb_parse_tree_free(tree->u.not.child); + break; + } + + free(tree); +} + +#if TEST_PROGRAM +/* + return a string representation of a parse tree + used for debugging +*/ +static char *tree_string(struct ldb_parse_tree *tree) +{ + char *s = NULL; + char *s1, *s2; + int i; + + switch (tree->operation) { + case LDB_OP_SIMPLE: + asprintf(&s, "( %s = \"%s\" )", tree->u.simple.attr, + (char *)tree->u.simple.value.data); + break; + + case LDB_OP_AND: + case LDB_OP_OR: + asprintf(&s, "( %c", tree->operation==LDB_OP_AND?'&':'|'); + if (!s) return NULL; + + for (i=0;iu.list.num_elements;i++) { + s1 = tree_string(tree->u.list.elements[i]); + if (!s1) { + free(s); + return NULL; + } + asprintf(&s2, "%s %s", s, s1); + free(s); + free(s1); + s = s2; + } + if (!s) { + return NULL; + } + asprintf(&s2, "%s )", s); + free(s); + s = s2; + break; + + case LDB_OP_NOT: + s1 = tree_string(tree->u.not.child); + asprintf(&s, "( ! %s )", s1); + free(s1); + break; + } + return s; +} + + +/* + print a tree + */ +static void print_tree(struct ldb_parse_tree *tree) +{ + char *s = tree_string(tree); + printf("%s\n", s); + free(s); +} + + + int main(void) +{ + char line[1000]; + int ret = 0; + + while (fgets(line, sizeof(line)-1, stdin)) { + struct ldb_parse_tree *tree; + + if (line[strlen(line)-1] == '\n') { + line[strlen(line)-1] = 0; + } + tree = ldb_parse_tree(line); + if (!tree) { + fprintf(stderr, "Failed to parse\n"); + ret = 1; + continue; + } + print_tree(tree); + ldb_parse_tree_free(tree); + } + + return ret; +} +#endif /* TEST_PROGRAM */ + -- cgit