r8585: add to ldb and ldap comparison functionality

better pares filters
Approx is currently only a stub need to dig more info to
understand what it really means and how it works exactly
(This used to be commit a9e8cd0bad27ed2b3c6a12302e787ba3c9a70a3c)

5 files changed, 420 insertions, 257 deletions

diff --git a/source4/lib/ldb/common/ldb_match.c b/source4/lib/ldb/common/ldb_match.c
index 3664855ddd..97e0a60ace 100644
--- a/source4/lib/ldb/common/ldb_match.c
+++ b/source4/lib/ldb/common/ldb_match.c
@@ -113,14 +113,53 @@ static int ldb_match_present(struct ldb_context *ldb,
 	return 0;
 }
 
+static int ldb_match_comparison(struct ldb_context *ldb, 
+				struct ldb_message *msg,
+				struct ldb_parse_tree *tree,
+				const char *base,
+				enum ldb_scope scope,
+				enum ldb_parse_op comp_op)
+{
+	unsigned int i;
+	struct ldb_message_element *el;
+	const struct ldb_attrib_handler *h;
+	int ret;
+
+	/* FIXME: APPROX comparison not handled yet */
+	if (comp_op == LDB_OP_APPROX) return 0;
+
+	el = ldb_msg_find_element(msg, tree->u.comparison.attr);
+	if (el == NULL) {
+		return 0;
+	}
+
+	h = ldb_attrib_handler(ldb, el->name);
+
+	for (i = 0; i < el->num_values; i++) {
+		ret = h->comparison_fn(ldb, ldb, &el->values[i], &tree->u.comparison.value);
+
+		if (ret == 0) {
+			return 1;
+		}
+		if (ret > 0 && comp_op == LDB_OP_GREATER) {
+			return 1;
+		}
+		if (ret < 0 && comp_op == LDB_OP_LESS) {
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
 /*
   match a simple leaf node
 */
-static int ldb_match_simple(struct ldb_context *ldb, 
-			    struct ldb_message *msg,
-			    struct ldb_parse_tree *tree,
-			    const char *base,
-			    enum ldb_scope scope)
+static int ldb_match_equality(struct ldb_context *ldb, 
+			      struct ldb_message *msg,
+			      struct ldb_parse_tree *tree,
+			      const char *base,
+			      enum ldb_scope scope)
 {
 	unsigned int i;
 	struct ldb_message_element *el;
@@ -128,12 +167,12 @@ static int ldb_match_simple(struct ldb_context *ldb,
 	struct ldb_dn *msgdn, *valuedn;
 	int ret;
 
-	if (ldb_attr_cmp(tree->u.simple.attr, "dn") == 0) {
+	if (ldb_attr_cmp(tree->u.equality.attr, "dn") == 0) {
 
 		msgdn = ldb_dn_explode_casefold(ldb, msg->dn);
 		if (msgdn == NULL) return 0;
 
-		valuedn = ldb_dn_explode_casefold(ldb, tree->u.simple.value.data);
+		valuedn = ldb_dn_explode_casefold(ldb, tree->u.equality.value.data);
 		if (valuedn == NULL) {
 			talloc_free(msgdn);
 			return 0;
@@ -148,7 +187,7 @@ static int ldb_match_simple(struct ldb_context *ldb,
 		return 0;
 	}
 
-	el = ldb_msg_find_element(msg, tree->u.simple.attr);
+	el = ldb_msg_find_element(msg, tree->u.equality.attr);
 	if (el == NULL) {
 		return 0;
 	}
@@ -156,7 +195,7 @@ static int ldb_match_simple(struct ldb_context *ldb,
 	h = ldb_attrib_handler(ldb, el->name);
 
 	for (i=0;i<el->num_values;i++) {
-		if (h->comparison_fn(ldb, ldb, &tree->u.simple.value, 
+		if (h->comparison_fn(ldb, ldb, &tree->u.equality.value, 
 				     &el->values[i]) == 0) {
 			return 1;
 		}
@@ -242,7 +281,7 @@ static int ldb_match_substring(struct ldb_context *ldb,
 	unsigned int i;
 	struct ldb_message_element *el;
 
-	el = ldb_msg_find_element(msg, tree->u.simple.attr);
+	el = ldb_msg_find_element(msg, tree->u.substring.attr);
 	if (el == NULL) {
 		return 0;
 	}
@@ -357,21 +396,6 @@ static int ldb_match_message(struct ldb_context *ldb,
 	int v;
 
 	switch (tree->operation) {
-	case LDB_OP_SIMPLE:
-		return ldb_match_simple(ldb, msg, tree, base, scope);
-
-	case LDB_OP_PRESENT:
-		return ldb_match_present(ldb, msg, tree, base, scope);
-
-	case LDB_OP_SUBSTRING:
-		return ldb_match_substring(ldb, msg, tree, base, scope);
-
-	case LDB_OP_EXTENDED:
-		return ldb_match_extended(ldb, msg, tree, base, scope);
-
-	case LDB_OP_NOT:
-		return ! ldb_match_message(ldb, msg, tree->u.isnot.child, base, scope);
-
 	case LDB_OP_AND:
 		for (i=0;i<tree->u.list.num_elements;i++) {
 			v = ldb_match_message(ldb, msg, tree->u.list.elements[i],
@@ -387,6 +411,31 @@ static int ldb_match_message(struct ldb_context *ldb,
 			if (v) return 1;
 		}
 		return 0;
+
+	case LDB_OP_NOT:
+		return ! ldb_match_message(ldb, msg, tree->u.isnot.child, base, scope);
+
+	case LDB_OP_EQUALITY:
+		return ldb_match_equality(ldb, msg, tree, base, scope);
+
+	case LDB_OP_SUBSTRING:
+		return ldb_match_substring(ldb, msg, tree, base, scope);
+
+	case LDB_OP_GREATER:
+		return ldb_match_comparison(ldb, msg, tree, base, scope, LDB_OP_GREATER);
+
+	case LDB_OP_LESS:
+		return ldb_match_comparison(ldb, msg, tree, base, scope, LDB_OP_LESS);
+
+	case LDB_OP_PRESENT:
+		return ldb_match_present(ldb, msg, tree, base, scope);
+
+	case LDB_OP_APPROX:
+		return ldb_match_comparison(ldb, msg, tree, base, scope, LDB_OP_APPROX);
+
+	case LDB_OP_EXTENDED:
+		return ldb_match_extended(ldb, msg, tree, base, scope);
+
 	}
 
 	return 0;
diff --git a/source4/lib/ldb/common/ldb_parse.c b/source4/lib/ldb/common/ldb_parse.c
index 933ff18f2b..83fcc73941 100644
--- a/source4/lib/ldb/common/ldb_parse.c
+++ b/source4/lib/ldb/common/ldb_parse.c
@@ -58,73 +58,6 @@ a filter is defined by:
                <filtertype> ::= '=' | '~=' | '<=' | '>='
 */
 
-#define LDB_ALL_SEP "()&|=!"
-
-/*
-  return next token element. Caller frees
-*/
-static char *ldb_parse_lex(void *ctx, const char **s, const char *sep)
-{
-	const char *p = *s;
-	char *ret;
-
-	while (isspace((unsigned char)*p)) {
-		p++;
-	}
-	*s = p;
-
-	if (*p == 0) {
-		return NULL;
-	}
-
-	if (strchr(sep, *p)) {
-		(*s) = p+1;
-		ret = talloc_strndup(ctx, p, 1);
-		if (!ret) {
-			errno = ENOMEM;
-		}
-		return ret;
-	}
-
-	while (*p && (isalnum((unsigned char)*p) || !strchr(sep, *p))) {
-		p++;
-	}
-
-	if (p == *s) {
-		return NULL;
-	}
-
-	ret = talloc_strndup(ctx, *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;
-}
-
 /*
    decode a RFC2254 binary string representation of a buffer.
    Used in LDAP filters.
@@ -273,7 +206,7 @@ static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret, 
 						 char *attr, char *value)
 {
-	char *p1, *p2, *p3;
+	char *p1, *p2;
 
 	ret->operation = LDB_OP_EXTENDED;
 	ret->u.extended.value = ldb_binary_decode(ret, value);
@@ -282,18 +215,14 @@ static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 	p1 = strchr(attr, ':');
 	if (p1 == NULL) goto failed;
 	p2 = strchr(p1+1, ':');
-	if (p2 == NULL) goto failed;
-	p3 = strchr(p2+1, ':');
 
 	*p1 = 0;
-	*p2 = 0;
-	if (p3) *p3 = 0;
+	if (p2) *p2 = 0;
 
-	ret->u.extended.attr = talloc_strdup(ret, attr);
-	if (ret->u.extended.attr == NULL) goto failed;
+	ret->u.extended.attr = attr;
 	if (strcmp(p1+1, "dn") == 0) {
 		ret->u.extended.dnAttributes = 1;
-		if (p3) {
+		if (p2) {
 			ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 			if (ret->u.extended.rule_id == NULL) goto failed;
 		} else {
@@ -312,14 +241,104 @@ failed:
 	return NULL;
 }
 
+static enum ldb_parse_op ldb_parse_filtertype(void *mem_ctx, char **type, char **value, const char **s)
+{
+	enum ldb_parse_op filter = 0;
+	char *name, *val, *k;
+	const char *p = *s;
+	const char *t, *t1;
+
+	/* retrieve attributetype name */
+	t = p;
+
+	while ((isascii(*p) && isalnum((unsigned char)*p)) || (*p == '-')) { /* attribute names can only be alphanums */
+		p++;
+	}
+
+	if (*p == ':') { /* but extended searches have : and . chars too */
+		p = strstr(p, ":=");
+		if (p == NULL) { /* malformed attribute name */
+			return 0;
+		}
+	}
+
+	t1 = p;
+
+	while (isspace((unsigned char)*p)) p++;
+
+	if (!strchr("=<>~:", *p)) {
+		return 0;
+	}
+
+	/* save name */
+	name = talloc_memdup(mem_ctx, t, t1 - t + 1);
+	if (name == NULL) return 0;
+	name[t1 - t] = '\0';
+
+	/* retrieve filtertype */
+
+	if (*p == '=') {
+		filter = LDB_OP_EQUALITY;
+	} else if (*(p + 1) == '=') {
+		switch (*p) {
+		case '<':
+			filter = LDB_OP_LESS;
+			p++;
+			break;
+		case '>':
+			filter = LDB_OP_GREATER;
+			p++;
+			break;
+		case '~':
+			filter = LDB_OP_APPROX;
+			p++;
+			break;
+		case ':':
+			filter = LDB_OP_EXTENDED;
+			p++;
+			break;
+		}
+	}
+	if (!filter) {
+		talloc_free(name);
+		return filter;
+	}
+	p++;
+
+	while (isspace((unsigned char)*p)) p++;
+
+	/* retieve value */
+	t = p;
+
+	while (*p && ((*p != ')') || ((*p == ')') && (*(p - 1) == '\\')))) p++;
+
+	val = talloc_memdup(mem_ctx, t, p - t + 1);
+	if (val == NULL) {
+		talloc_free(name);
+		return 0;
+	}
+	val[p - t] = '\0';
+
+	k = &(val[p - t]);
+
+	/* remove trailing spaces from value */
+	while ((k > val) && (isspace((unsigned char)*(k - 1)))) k--;
+	*k = '\0';
+
+	*type = name;
+	*value = val;
+	*s = p;
+	return filter;
+}
 
 /*
   <simple> ::= <attributetype> <filtertype> <attributevalue>
 */
-static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char *s)
+static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char **s)
 {
-	char *eq, *val, *l;
+	char *attr, *value;
 	struct ldb_parse_tree *ret;
+	enum ldb_parse_op filtertype;
 
 	ret = talloc(mem_ctx, struct ldb_parse_tree);
 	if (!ret) {
@@ -327,64 +346,92 @@ static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char *s)
 		return NULL;
 	}
 
-	l = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
-	if (!l) {
+	filtertype = ldb_parse_filtertype(ret, &attr, &value, s);
+	if (!filtertype) {
 		talloc_free(ret);
 		return NULL;
 	}
 
-	if (strchr("()&|=", *l)) {
-		talloc_free(ret);
-		return NULL;
-	}
+	switch (filtertype) {
 
-	eq = ldb_parse_lex(ret, &s, LDB_ALL_SEP);
-	if (!eq || strcmp(eq, "=") != 0) {
-		talloc_free(ret);
-		return NULL;
-	}
-	talloc_free(eq);
+		case LDB_OP_EQUALITY:
 
-	val = ldb_parse_lex(ret, &s, ")");
-	if (val && strchr("()&|", *val)) {
-		talloc_free(ret);
-		return NULL;
-	}
+			if (strcmp(value, "*") == 0) {
+				ret->operation = LDB_OP_PRESENT;
+				ret->u.present.attr = attr;
+				break;
+			}
 
-	if (l[strlen(l)-1] == ':') {
-		/* its an extended match */
-		return ldb_parse_extended(ret, l, val);
-	}
+			if (ldb_parse_find_wildcard(value) != NULL) {
+				ret->operation = LDB_OP_SUBSTRING;
+				ret->u.substring.attr = attr;
+				ret->u.substring.start_with_wildcard = 0;
+				ret->u.substring.end_with_wildcard = 0;
+				ret->u.substring.chunks = ldb_wildcard_decode(ret, value);
+				if (ret->u.substring.chunks == NULL){
+					talloc_free(ret);
+					return NULL;
+				}
+				if (value[0] == '*')
+					ret->u.substring.start_with_wildcard = 1;
+				if (value[strlen(value) - 1] == '*')
+					ret->u.substring.end_with_wildcard = 1;
+				talloc_free(value);
+
+				break;
+			}
+
+			ret->operation = LDB_OP_EQUALITY;
+			ret->u.equality.attr = attr;
+			ret->u.equality.value = ldb_binary_decode(ret, value);
+			if (ret->u.equality.value.data == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			talloc_free(value);
+			break;
+
+		case LDB_OP_GREATER:
+			ret->operation = LDB_OP_GREATER;
+			ret->u.comparison.attr = attr;
+			ret->u.comparison.value = ldb_binary_decode(ret, value);
+			if (ret->u.comparison.value.data == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			talloc_free(value);
+			break;
+
+		case LDB_OP_LESS:
+			ret->operation = LDB_OP_LESS;
+			ret->u.comparison.attr = attr;
+			ret->u.comparison.value = ldb_binary_decode(ret, value);
+			if (ret->u.comparison.value.data == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			talloc_free(value);
+			break;
+
+		case LDB_OP_APPROX:
+			ret->operation = LDB_OP_APPROX;
+			ret->u.comparison.attr = attr;
+			ret->u.comparison.value = ldb_binary_decode(ret, value);
+			if (ret->u.comparison.value.data == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			talloc_free(value);
+			break;
 
-	if (val && strcmp(val, "*") == 0) {
-		ret->operation = LDB_OP_PRESENT;
-		ret->u.present.attr = l;
+		case LDB_OP_EXTENDED:
 
-		return ret;
-	}
+			ret = ldb_parse_extended(ret, attr, value);
+			break;
 
-	if (val && ldb_parse_find_wildcard(val) != NULL) {
-		ret->operation = LDB_OP_SUBSTRING;
-		ret->u.substring.attr = l;
-		ret->u.substring.start_with_wildcard = 0;
-		ret->u.substring.end_with_wildcard = 0;
-		ret->u.substring.chunks = ldb_wildcard_decode(ret, val);
-		if (ret->u.substring.chunks == NULL){
+		default:
 			talloc_free(ret);
 			return NULL;
-		}
-		if (val[0] == '*') ret->u.substring.start_with_wildcard = 1;
-		if (val[strlen(val) - 1] == '*') ret->u.substring.end_with_wildcard = 1;
-
-		return ret;
-	}
-
-	ret->operation = LDB_OP_SIMPLE;
-	ret->u.simple.attr = l;
-	ret->u.simple.value = ldb_binary_decode(ret, val);
-	if (ret->u.simple.value.data == NULL) {
-		talloc_free(ret);
-		return NULL;
 	}
 
 	return ret;
@@ -397,10 +444,25 @@ static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char *s)
   <or> ::= '|' <filterlist>
   <filterlist> ::= <filter> | <filter> <filterlist>
 */
-static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx,
-						   enum ldb_parse_op op, const char *s)
+static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx, const char **s)
 {
 	struct ldb_parse_tree *ret, *next;
+	enum ldb_parse_op op;
+	const char *p = *s;
+
+	switch (*p) {
+		case '&':
+			op = LDB_OP_AND;
+			break;
+		case '|':
+			op = LDB_OP_OR;
+			break;
+		default:
+			return NULL;
+	}
+	p++;
+
+	while (isspace((unsigned char)*p)) p++;
 
 	ret = talloc(mem_ctx, struct ldb_parse_tree);
 	if (!ret) {
@@ -417,19 +479,19 @@ static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx,
 		return NULL;
 	}
 
-	ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &s);
+	ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &p);
 	if (!ret->u.list.elements[0]) {
 		talloc_free(ret);
 		return NULL;
 	}
 
-	while (isspace((unsigned char)*s)) s++;
+	while (isspace((unsigned char)*p)) p++;
 
-	while (*s && (next = ldb_parse_filter(ret->u.list.elements, &s))) {
+	while (*p && (next = ldb_parse_filter(ret->u.list.elements, &p))) {
 		struct ldb_parse_tree **e;
 		e = talloc_realloc(ret, ret->u.list.elements, 
 				     struct ldb_parse_tree *, 
-				     ret->u.list.num_elements+1);
+				     ret->u.list.num_elements + 1);
 		if (!e) {
 			errno = ENOMEM;
 			talloc_free(ret);
@@ -438,9 +500,11 @@ static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx,
 		ret->u.list.elements = e;
 		ret->u.list.elements[ret->u.list.num_elements] = next;
 		ret->u.list.num_elements++;
-		while (isspace((unsigned char)*s)) s++;
+		while (isspace((unsigned char)*p)) p++;
 	}
 
+	*s = p;
+
 	return ret;
 }
 
@@ -448,9 +512,15 @@ static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx,
 /*
   <not> ::= '!' <filter>
 */
-static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char *s)
+static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char **s)
 {
 	struct ldb_parse_tree *ret;
+	const char *p = *s;
+
+	if (*p != '!') {
+		return NULL;
+	}
+	p++;
 
 	ret = talloc(mem_ctx, struct ldb_parse_tree);
 	if (!ret) {
@@ -459,12 +529,14 @@ static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char *s)
 	}
 
 	ret->operation = LDB_OP_NOT;
-	ret->u.isnot.child = ldb_parse_filter(ret, &s);
+	ret->u.isnot.child = ldb_parse_filter(ret, &p);
 	if (!ret->u.isnot.child) {
 		talloc_free(ret);
 		return NULL;
 	}
 
+	*s = p;
+
 	return ret;
 }
 
@@ -472,26 +544,37 @@ static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char *s)
   parse a filtercomp
   <filtercomp> ::= <and> | <or> | <not> | <simple>
 */
-static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char *s)
+static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char **s)
 {
-	while (isspace((unsigned char)*s)) s++;
+	struct ldb_parse_tree *ret;
+	const char *p = *s;
 
-	switch (*s) {
+	while (isspace((unsigned char)*p)) p++;
+
+	switch (*p) {
 	case '&':
-		return ldb_parse_filterlist(mem_ctx, LDB_OP_AND, s+1);
+		ret = ldb_parse_filterlist(mem_ctx, &p);
+		break;
 
 	case '|':
-		return ldb_parse_filterlist(mem_ctx, LDB_OP_OR, s+1);
+		ret = ldb_parse_filterlist(mem_ctx, &p);
+		break;
 
 	case '!':
-		return ldb_parse_not(mem_ctx, s+1);
+		ret = ldb_parse_not(mem_ctx, &p);
+		break;
 
 	case '(':
 	case ')':
 		return NULL;
+
+	default:
+		ret = ldb_parse_simple(mem_ctx, &p);
+
 	}
 
-	return ldb_parse_simple(mem_ctx, s);
+	*s = p;
+	return ret;
 }
 
 
@@ -500,37 +583,26 @@ static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char *s)
 */
 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s)
 {
-	char *l, *s2;
-	const char *p, *p2;
 	struct ldb_parse_tree *ret;
+	const char *p = *s;
 
-	l = ldb_parse_lex(mem_ctx, s, LDB_ALL_SEP);
-	if (!l) {
+	if (*p != '(') {
 		return NULL;
 	}
+	p++;
 
-	if (strcmp(l, "(") != 0) {
-		talloc_free(l);
-		return NULL;
-	}
-	talloc_free(l);
+	ret = ldb_parse_filtercomp(mem_ctx, &p);
 
-	p = match_brace(*s);
-	if (!p) {
+	if (*p != ')') {
 		return NULL;
 	}
-	p2 = p + 1;
+	p++;
 
-	s2 = talloc_strndup(mem_ctx, *s, p - *s);
-	if (!s2) {
-		errno = ENOMEM;
-		return NULL;
+	while (isspace((unsigned char)*p)) {
+		p++;
 	}
 
-	ret = ldb_parse_filtercomp(mem_ctx, s2);
-	talloc_free(s2);
-
-	*s = p2;
+	*s = p;
 
 	return ret;
 }
@@ -549,7 +621,7 @@ struct ldb_parse_tree *ldb_parse_tree(void *mem_ctx, const char *s)
 		return ldb_parse_filter(mem_ctx, &s);
 	}
 
-	return ldb_parse_simple(mem_ctx, s);
+	return ldb_parse_simple(mem_ctx, &s);
 }
 
 
@@ -562,22 +634,42 @@ char *ldb_filter_from_tree(void *mem_ctx, struct ldb_parse_tree *tree)
 	int i;
 
 	switch (tree->operation) {
-	case LDB_OP_SIMPLE:
-		s = ldb_binary_encode(mem_ctx, tree->u.simple.value);
+	case LDB_OP_AND:
+	case LDB_OP_OR:
+		ret = talloc_asprintf(mem_ctx, "(%c", (char)tree->operation);
+		if (ret == NULL) return NULL;
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
+			if (s == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			s2 = talloc_asprintf_append(ret, "%s", s);
+			talloc_free(s);
+			if (s2 == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			ret = s2;
+		}
+		s = talloc_asprintf_append(ret, ")");
+		if (s == NULL) {
+			talloc_free(ret);
+			return NULL;
+		}
+		return s;
+	case LDB_OP_NOT:
+		s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
 		if (s == NULL) return NULL;
-		ret = talloc_asprintf(mem_ctx, "(%s=%s)", 
-				      tree->u.simple.attr, s);
+
+		ret = talloc_asprintf(mem_ctx, "(!%s)", s);
 		talloc_free(s);
 		return ret;
-	case LDB_OP_EXTENDED:
-		s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
+	case LDB_OP_EQUALITY:
+		s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 		if (s == NULL) return NULL;
-		ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)", 
-				      tree->u.extended.attr?tree->u.extended.attr:"", 
-				      tree->u.extended.dnAttributes?":dn":"",
-				      tree->u.extended.rule_id?":":"", 
-				      tree->u.extended.rule_id?tree->u.extended.rule_id:"", 
-				      s);
+		ret = talloc_asprintf(mem_ctx, "(%s=%s)", 
+				      tree->u.equality.attr, s);
 		talloc_free(s);
 		return ret;
 	case LDB_OP_SUBSTRING:
@@ -600,39 +692,40 @@ char *ldb_filter_from_tree(void *mem_ctx, struct ldb_parse_tree *tree)
 			ret[strlen(ret) - 1] = '\0'; /* remove last wildcard */
 		}
 		return ret;
+	case LDB_OP_GREATER:
+		s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
+		if (s == NULL) return NULL;
+		ret = talloc_asprintf(mem_ctx, "(%s>=%s)", 
+				      tree->u.equality.attr, s);
+		talloc_free(s);
+		return ret;
+	case LDB_OP_LESS:
+		s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
+		if (s == NULL) return NULL;
+		ret = talloc_asprintf(mem_ctx, "(%s<=%s)", 
+				      tree->u.equality.attr, s);
+		talloc_free(s);
+		return ret;
 	case LDB_OP_PRESENT:
 		ret = talloc_strdup(mem_ctx, "*");
 		if (ret == NULL) return NULL;
 		return ret;
-	case LDB_OP_AND:
-	case LDB_OP_OR:
-		ret = talloc_asprintf(mem_ctx, "(%c", (char)tree->operation);
-		if (ret == NULL) return NULL;
-		for (i=0;i<tree->u.list.num_elements;i++) {
-			s = ldb_filter_from_tree(mem_ctx, tree->u.list.elements[i]);
-			if (s == NULL) {
-				talloc_free(ret);
-				return NULL;
-			}
-			s2 = talloc_asprintf_append(ret, "%s", s);
-			talloc_free(s);
-			if (s2 == NULL) {
-				talloc_free(ret);
-				return NULL;
-			}
-			ret = s2;
-		}
-		s = talloc_asprintf_append(ret, ")");
-		if (s == NULL) {
-			talloc_free(ret);
-			return NULL;
-		}
-		return s;
-	case LDB_OP_NOT:
-		s = ldb_filter_from_tree(mem_ctx, tree->u.isnot.child);
+	case LDB_OP_APPROX:
+		s = ldb_binary_encode(mem_ctx, tree->u.equality.value);
 		if (s == NULL) return NULL;
-
-		ret = talloc_asprintf(mem_ctx, "(!%s)", s);
+		ret = talloc_asprintf(mem_ctx, "(%s~=%s)", 
+				      tree->u.equality.attr, s);
+		talloc_free(s);
+		return ret;
+	case LDB_OP_EXTENDED:
+		s = ldb_binary_encode(mem_ctx, tree->u.extended.value);
+		if (s == NULL) return NULL;
+		ret = talloc_asprintf(mem_ctx, "(%s%s%s%s:=%s)", 
+				      tree->u.extended.attr?tree->u.extended.attr:"", 
+				      tree->u.extended.dnAttributes?":dn":"",
+				      tree->u.extended.rule_id?":":"", 
+				      tree->u.extended.rule_id?tree->u.extended.rule_id:"", 
+				      s);
 		talloc_free(s);
 		return ret;
 	}
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index 485e2bc730..6670089902 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -154,20 +154,21 @@ struct ldb_debug_ops {
 
 
 /* structues for ldb_parse_tree handling code */
-enum ldb_parse_op {LDB_OP_SIMPLE=1, LDB_OP_EXTENDED=2,
-		   LDB_OP_SUBSTRING=3, LDB_OP_PRESENT=4,
-		   LDB_OP_AND='&', LDB_OP_OR='|', LDB_OP_NOT='!'};
+enum ldb_parse_op { LDB_OP_AND=1, LDB_OP_OR=2, LDB_OP_NOT=3,
+		    LDB_OP_EQUALITY=4, LDB_OP_SUBSTRING=5,
+		    LDB_OP_GREATER=6, LDB_OP_LESS=7, LDB_OP_PRESENT=8,
+		    LDB_OP_APPROX=9, LDB_OP_EXTENDED=10 };
 
 struct ldb_parse_tree {
 	enum ldb_parse_op operation;
 	union {
 		struct {
-			char *attr;
-			struct ldb_val value;
-		} simple;
+			struct ldb_parse_tree *child;
+		} isnot;
 		struct {
 			char *attr;
-		} present;
+			struct ldb_val value;
+		} equality;
 		struct {
 			char *attr;
 			int start_with_wildcard;
@@ -176,6 +177,13 @@ struct ldb_parse_tree {
 		} substring;
 		struct {
 			char *attr;
+		} present;
+		struct {
+			char *attr;
+			struct ldb_val value;
+		} comparison;
+		struct {
+			char *attr;
 			int dnAttributes;
 			char *rule_id;
 			struct ldb_val value;
@@ -184,9 +192,6 @@ struct ldb_parse_tree {
 			unsigned int num_elements;
 			struct ldb_parse_tree **elements;
 		} list;
-		struct {
-			struct ldb_parse_tree *child;
-		} isnot;
 	} u;
 };
 
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index 87b52ac366..1cfebe6864 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -190,13 +190,13 @@ static int ltdb_index_dn_simple(struct ldb_module *module,
 
 	/* if the attribute isn't in the list of indexed attributes then
 	   this node needs a full search */
-	if (ldb_msg_find_idx(index_list, tree->u.simple.attr, NULL, LTDB_IDXATTR) == -1) {
+	if (ldb_msg_find_idx(index_list, tree->u.equality.attr, NULL, LTDB_IDXATTR) == -1) {
 		return -1;
 	}
 
 	/* the attribute is indexed. Pull the list of DNs that match the 
 	   search criterion */
-	dn = ldb_dn_key(ldb, tree->u.simple.attr, &tree->u.simple.value);
+	dn = ldb_dn_key(ldb, tree->u.equality.attr, &tree->u.equality.value);
 	if (!dn) return -1;
 
 	msg = talloc(list, struct ldb_message);
@@ -256,7 +256,7 @@ static int ltdb_index_dn_objectclass(struct ldb_module *module,
 	struct ldb_context *ldb = module->ldb;
 	unsigned int i;
 	int ret;
-	const char *target = tree->u.simple.value.data;
+	const char *target = tree->u.equality.value.data;
 	const char **subclasses;
 
 	list->count = 0;
@@ -273,16 +273,16 @@ static int ltdb_index_dn_objectclass(struct ldb_module *module,
 	for (i=0;subclasses[i];i++) {
 		struct ldb_parse_tree tree2;
 		struct dn_list *list2;
-		tree2.operation = LDB_OP_SIMPLE;
-		tree2.u.simple.attr = talloc_strdup(list, LTDB_OBJECTCLASS);
-		if (!tree2.u.simple.attr) {
+		tree2.operation = LDB_OP_EQUALITY;
+		tree2.u.equality.attr = talloc_strdup(list, LTDB_OBJECTCLASS);
+		if (!tree2.u.equality.attr) {
 			return -1;
 		}
-		tree2.u.simple.value.data = talloc_strdup(tree2.u.simple.attr, subclasses[i]);
-		if (tree2.u.simple.value.data == NULL) {
+		tree2.u.equality.value.data = talloc_strdup(tree2.u.equality.attr, subclasses[i]);
+		if (tree2.u.equality.value.data == NULL) {
 			return -1;			
 		}
-		tree2.u.simple.value.length = strlen(subclasses[i]);
+		tree2.u.equality.value.length = strlen(subclasses[i]);
 		list2 = talloc(list, struct dn_list);
 		if (list2 == NULL) {
 			return -1;
@@ -297,7 +297,7 @@ static int ltdb_index_dn_objectclass(struct ldb_module *module,
 				talloc_free(list2);
 			}
 		}
-		talloc_free(tree2.u.simple.attr);
+		talloc_free(tree2.u.equality.attr);
 	}
 
 	return ret;
@@ -311,7 +311,7 @@ static int ltdb_index_dn_leaf(struct ldb_module *module,
 			      const struct ldb_message *index_list,
 			      struct dn_list *list)
 {
-	if (ldb_attr_cmp(tree->u.simple.attr, LTDB_OBJECTCLASS) == 0) {
+	if (ldb_attr_cmp(tree->u.equality.attr, LTDB_OBJECTCLASS) == 0) {
 		return ltdb_index_dn_objectclass(module, tree, index_list, list);
 	}
 	return ltdb_index_dn_simple(module, tree, index_list, list);
@@ -570,17 +570,6 @@ static int ltdb_index_dn(struct ldb_module *module,
 	int ret = -1;
 
 	switch (tree->operation) {
-	case LDB_OP_SIMPLE:
-		ret = ltdb_index_dn_leaf(module, tree, index_list, list);
-		break;
-
-	case LDB_OP_PRESENT:
-	case LDB_OP_SUBSTRING:
-	case LDB_OP_EXTENDED:
-		/* we can't index with fancy bitops yet */
-		ret = -1;
-		break;
-
 	case LDB_OP_AND:
 		ret = ltdb_index_dn_and(module, tree, index_list, list);
 		break;
@@ -592,6 +581,20 @@ static int ltdb_index_dn(struct ldb_module *module,
 	case LDB_OP_NOT:
 		ret = ltdb_index_dn_not(module, tree, index_list, list);
 		break;
+
+	case LDB_OP_EQUALITY:
+		ret = ltdb_index_dn_leaf(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_SUBSTRING:
+	case LDB_OP_GREATER:
+	case LDB_OP_LESS:
+	case LDB_OP_PRESENT:
+	case LDB_OP_APPROX:
+	case LDB_OP_EXTENDED:
+		/* we can't index with fancy bitops yet */
+		ret = -1;
+		break;
 	}
 
 	return ret;
diff --git a/source4/lib/ldb/tests/test-generic.sh b/source4/lib/ldb/tests/test-generic.sh
index cc9f41954f..0e2cb187a1 100755
--- a/source4/lib/ldb/tests/test-generic.sh
+++ b/source4/lib/ldb/tests/test-generic.sh
@@ -64,5 +64,18 @@ if [ $count != 3 ]; then
     exit 1
 fi
 
+echo "Testing compare"
+count=`$VALGRIND ldbsearch '(cn>=U)' cn | grep '^dn' | wc -l`
+if [ $count != 2 ]; then
+    echo returned $count records - expected 2
+    exit 1
+fi
+
+count=`$VALGRIND ldbsearch '(cn<=U)' cn | grep '^dn' | wc -l`
+if [ $count != 13 ]; then
+    echo returned $count records - expected 13
+    exit 1
+fi
+
 echo "Testing binary file attribute value"
 $VALGRIND ldbmodify $LDBDIR/tests/photo.ldif || exit 1