r8373: New wildcard matching code.

This code applies correct ldap standard wildcard matching code
removes WILDCARD matching from tdb @ATTRIBUTES, that's now handled independently
adds some more tests for wildcard matching
fixes dn comparison code in ldb_match
(This used to be commit 4eb5863042011988d85092d7dde3d809aa15bd59)

14 files changed, 413 insertions, 203 deletions

diff --git a/source4/lib/ldb/common/attrib_handlers.c b/source4/lib/ldb/common/attrib_handlers.c
index a35a450670..7f71d3574a 100644
--- a/source4/lib/ldb/common/attrib_handlers.c
+++ b/source4/lib/ldb/common/attrib_handlers.c
@@ -75,19 +75,6 @@ static int ldb_handler_fold(struct ldb_context *ldb, void *mem_ctx,
 
 
 /*
-  a case folding copy handler, removing leading and trailing spaces and
-  multiple internal spaces, and checking for wildcard characters
-*/
-static int ldb_handler_fold_wildcard(struct ldb_context *ldb, void *mem_ctx,
-				     const struct ldb_val *in, struct ldb_val *out)
-{
-	if (strchr(in->data, '*')) {
-		return -1;
-	}
-	return ldb_handler_fold(ldb, mem_ctx, in, out);
-}
-
-/*
   canonicalise a ldap Integer
   rfc2252 specifies it should be in decimal form
 */
@@ -154,59 +141,23 @@ static int ldb_comparison_fold(struct ldb_context *ldb, void *mem_ctx,
 }
 
 /*
-  compare two case insensitive strings, ignoring multiple whitespace
-  and leading and trailing whitespace
-  see rfc2252 section 8.1
-  handles wildcards
-*/
-static int ldb_comparison_fold_wildcard(struct ldb_context *ldb,
-					void *mem_ctx,
-					const struct ldb_val *v1, 
-					const struct ldb_val *v2)
-{
-	const char *s1=v1->data, *s2=v2->data;
-	while (*s1 == ' ') s1++;
-	while (*s2 == ' ') s2++;
-	/* TODO: make utf8 safe, possibly with helper function from application */
-	while (*s1 && *s2) {
-		if (s1[0] == '*' && s1[1] == 0) {
-			return 0;
-		}
-		if (toupper(*s1) != toupper(*s2)) break;
-		if (*s1 == ' ') {
-			while (s1[0] == s1[1]) s1++;
-			while (s2[0] == s2[1]) s2++;
-		}
-		s1++; s2++;
-	}
-	while (*s1 == ' ') s1++;
-	while (*s2 == ' ') s2++;
-	return (int)(*s1) - (int)(*s2);
-}
-
-
-/*
   canonicalise a attribute in DN format
 */
 static int ldb_canonicalise_dn(struct ldb_context *ldb, void *mem_ctx,
 			       const struct ldb_val *in, struct ldb_val *out)
 {
-	struct ldb_dn *dn1, *dn2;
+	struct ldb_dn *dn;
 	int ret = -1;
 
 	out->length = 0;
 	out->data = NULL;
 
-	dn1 = ldb_dn_explode(mem_ctx, in->data);
-	if (dn1 == NULL) {
+	dn = ldb_dn_explode_casefold(ldb, in->data);
+	if (dn == NULL) {
 		return -1;
 	}
-	dn2 = ldb_dn_casefold(ldb, dn1);
-	if (dn2 == NULL) {
-		goto done;
-	}
 
-	out->data = ldb_dn_linearize(mem_ctx, dn2);
+	out->data = ldb_dn_linearize(mem_ctx, dn);
 	if (out->data == NULL) {
 		goto done;
 	}
@@ -215,8 +166,7 @@ static int ldb_canonicalise_dn(struct ldb_context *ldb, void *mem_ctx,
 	ret = 0;
 
 done:
-	talloc_free(dn1);
-	talloc_free(dn2);
+	talloc_free(dn);
 
 	return ret;
 }
@@ -227,20 +177,23 @@ done:
 static int ldb_comparison_dn(struct ldb_context *ldb, void *mem_ctx,
 			     const struct ldb_val *v1, const struct ldb_val *v2)
 {
-	struct ldb_val cv1, cv2;
+	struct ldb_dn *dn1 = NULL, *dn2 = NULL;
 	int ret;
-	if (ldb_canonicalise_dn(ldb, mem_ctx, v1, &cv1) != 0 ||
-	    ldb_canonicalise_dn(ldb, mem_ctx, v2, &cv2) != 0) {
-		goto failed;
-	}
-	ret = strcmp(cv1.data, cv2.data);
-	talloc_free(cv1.data);
-	talloc_free(cv2.data);
+
+	dn1 = ldb_dn_explode_casefold(mem_ctx, v1->data);
+	if (dn1 == NULL) return -1;
+
+	dn2 = ldb_dn_explode_casefold(mem_ctx, v2->data);
+	if (dn2 == NULL) {
+		talloc_free(dn1);
+		return -1;
+	} 
+
+	ret = ldb_dn_compare(ldb, dn1, dn2);
+
+	talloc_free(dn1);
+	talloc_free(dn2);
 	return ret;
-failed:
-	talloc_free(cv1.data);
-	talloc_free(cv2.data);
-	return -1;
 }
 
 /*
@@ -299,14 +252,6 @@ static const struct ldb_attrib_handler ldb_standard_attribs[] = {
 		.comparison_fn   = ldb_comparison_fold
 	},
 	{ 
-		.attr            = LDB_SYNTAX_WILDCARD,
-		.flags           = LDB_ATTR_FLAG_WILDCARD,
-		.ldif_read_fn    = ldb_handler_copy,
-		.ldif_write_fn   = ldb_handler_copy,
-		.canonicalise_fn = ldb_handler_fold_wildcard,
-		.comparison_fn   = ldb_comparison_fold_wildcard
-	},
-	{ 
 		.attr            = LDB_SYNTAX_DN,
 		.flags           = 0,
 		.ldif_read_fn    = ldb_handler_copy,
diff --git a/source4/lib/ldb/common/ldb_dn.c b/source4/lib/ldb/common/ldb_dn.c
index 1eaf4c486b..b421a7fe75 100644
--- a/source4/lib/ldb/common/ldb_dn.c
+++ b/source4/lib/ldb/common/ldb_dn.c
@@ -315,6 +315,19 @@ struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
 	edn->comp_num = 0;
 	edn->components = NULL;
 
+	/* Special DNs case */
+	if (dn[0] == '@') {
+		edn->comp_num = 1;
+		edn->components = talloc(edn, struct ldb_dn_component);
+		if (edn->components == NULL) goto failed;
+		edn->components[0].name = talloc_strdup(edn->components, "@SPECIAL");
+		if (edn->components[0].name == NULL) goto failed;
+		edn->components[0].value.data = talloc_strdup(edn->components, dn);
+		if (edn->components[0].value.data== NULL) goto failed;
+		edn->components[0].value.length = strlen(dn);
+		return edn;
+	}
+
 	pdn = p = talloc_strdup(edn, dn);
 	LDB_DN_NULL_FAILED(pdn);
 
@@ -363,6 +376,12 @@ char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn)
 	char *dn, *value;
 	int i;
 
+	/* Special DNs */
+	if ((edn->comp_num == 1) && strcmp("@SPECIAL", edn->components[0].name) == 0) {
+		dn = talloc_strdup(mem_ctx, edn->components[0].value.data);
+		return dn;
+	}
+
 	dn = talloc_strdup(mem_ctx, "");
 	LDB_DN_NULL_FAILED(dn);
 
@@ -388,28 +407,31 @@ failed:
 }
 
 /* compare DNs using casefolding compare functions */
-int ldb_dn_compare(struct ldb_context *ldb, const struct ldb_dn *edn0, const struct ldb_dn *edn1)
+
+int ldb_dn_compare_base(struct ldb_context *ldb,
+		   const struct ldb_dn *base,
+		   const struct ldb_dn *dn)
 {
 	int i, ret;
+	int n0, n1;
 
 	/* if the number of components doesn't match they differ */
-	if (edn0->comp_num != edn1->comp_num)
-		return (edn1->comp_num - edn0->comp_num);
-
-	for (i = 0; i < edn0->comp_num; i++) {
+	n0 = base->comp_num - 1;
+	n1 = dn->comp_num - 1;
+	for (i = 0; i < base->comp_num; i++, n0--, n1--) {
 		const struct ldb_attrib_handler *h;
 
 		/* compare names (attribute names are guaranteed to be ASCII only) */
-		ret = ldb_caseless_cmp(edn0->components[i].name,
-				       edn1->components[i].name);
+		ret = ldb_caseless_cmp(base->components[n0].name,
+				       dn->components[n1].name);
 		if (ret) {
 			return ret;
 		}
 
 		/* names match, compare values */
-		h = ldb_attrib_handler(ldb, edn0->components[i].name);
-		ret = h->comparison_fn(ldb, ldb, &(edn0->components[i].value),
-						  &(edn1->components[i].value));
+		h = ldb_attrib_handler(ldb, base->components[n0].name);
+		ret = h->comparison_fn(ldb, ldb, &(base->components[n0].value),
+						  &(dn->components[n1].value));
 		if (ret) {
 			return ret;
 		}
@@ -418,6 +440,16 @@ int ldb_dn_compare(struct ldb_context *ldb, const struct ldb_dn *edn0, const str
 	return 0;
 }
 
+int ldb_dn_compare(struct ldb_context *ldb,
+		   const struct ldb_dn *edn0,
+		   const struct ldb_dn *edn1)
+{
+	if (edn0->comp_num != edn1->comp_num)
+		return (edn1->comp_num - edn0->comp_num);
+
+	return ldb_dn_compare_base(ldb, edn0, edn1);
+}
+
 /*
   casefold a dn. We need to casefold the attribute names, and canonicalize 
   attribute values of case insensitive attributes.
@@ -456,3 +488,15 @@ failed:
 	return NULL;
 }
 
+struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn)
+{
+	struct ldb_dn *edn, *cdn;
+
+	edn = ldb_dn_explode(ldb, dn);
+	if (edn == NULL) return NULL;
+
+	cdn = ldb_dn_casefold(ldb, edn);
+	
+	talloc_free(edn);
+	return cdn;
+}
diff --git a/source4/lib/ldb/common/ldb_match.c b/source4/lib/ldb/common/ldb_match.c
index 462c078d81..b32a933df3 100644
--- a/source4/lib/ldb/common/ldb_match.c
+++ b/source4/lib/ldb/common/ldb_match.c
@@ -40,72 +40,111 @@
 /*
   check if the scope matches in a search result
 */
-static int ldb_match_scope(const char *dn, const char *base, enum ldb_scope scope)
+static int ldb_match_scope(struct ldb_context *ldb,
+			   const char *base_str,
+			   const char *dn_str,
+			   enum ldb_scope scope)
 {
-	size_t dn_len, base_len;
+	struct ldb_dn *base;
+	struct ldb_dn *dn;
+	int ret = 0;
 
-	if (base == NULL) {
+	if (base_str == NULL) {
 		return 1;
 	}
 
-	base_len = strlen(base);
-	dn_len = strlen(dn);
+	base = ldb_dn_explode_casefold(ldb, base_str);
+	if (base == NULL) return 0;
 
-	if (scope != LDB_SCOPE_ONELEVEL && ldb_dn_cmp(dn, base) == 0) {
-		return 1;
-	}
-
-	if (base_len+1 >= dn_len) {
+	dn = ldb_dn_explode_casefold(ldb, dn_str);
+	if (dn == NULL) {
+		talloc_free(base);
 		return 0;
 	}
 
 	switch (scope) {
 	case LDB_SCOPE_BASE:
+		if (ldb_dn_compare(ldb, base, dn) == 0) {
+			ret = 1;
+		}
 		break;
 
 	case LDB_SCOPE_ONELEVEL:
-		if (ldb_dn_cmp(dn + (dn_len - base_len), base) == 0 &&
-		    dn[dn_len - base_len - 1] == ',' &&
-		    strchr(dn, ',') == &dn[dn_len - base_len - 1]) {
-			return 1;
+		if (dn->comp_num != base->comp_num) {
+			if (ldb_dn_compare_base(ldb, base, dn) == 0) {
+				ret = 1;
+			}
 		}
 		break;
 		
 	case LDB_SCOPE_SUBTREE:
 	default:
-		if (ldb_dn_cmp(dn + (dn_len - base_len), base) == 0 &&
-		    dn[dn_len - base_len - 1] == ',') {
-			return 1;
+		if (ldb_dn_compare_base(ldb, base, dn) == 0) {
+			ret = 1;
 		}
 		break;
 	}
 
-	return 0;
+	talloc_free(base);
+	talloc_free(dn);
+	return ret;
 }
 
 
 /*
-  match a leaf node
+  match if node is present
+*/
+static int ldb_match_present(struct ldb_context *ldb, 
+			    struct ldb_message *msg,
+			    struct ldb_parse_tree *tree,
+			    const char *base,
+			    enum ldb_scope scope)
+{
+
+	if (ldb_attr_cmp(tree->u.simple.attr, "dn") == 0) {
+		return 1;
+	}
+
+	if (ldb_msg_find_element(msg, tree->u.simple.attr)) {
+		return 1;
+	}
+
+	return 0;
+}
+
+/*
+  match a simple leaf node
 */
-static int ldb_match_leaf(struct ldb_context *ldb, 
-			  struct ldb_message *msg,
-			  struct ldb_parse_tree *tree,
-			  const char *base,
-			  enum ldb_scope scope)
+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)
 {
 	unsigned int i;
 	struct ldb_message_element *el;
 	const struct ldb_attrib_handler *h;
-
-	if (!ldb_match_scope(msg->dn, base, scope)) {
-		return 0;
-	}
+	struct ldb_dn *msgdn, *valuedn;
+	int ret;
 
 	if (ldb_attr_cmp(tree->u.simple.attr, "dn") == 0) {
-		if (strcmp(tree->u.simple.value.data, "*") == 0) {
-			return 1;
+
+		msgdn = ldb_dn_explode_casefold(ldb, msg->dn);
+		if (msgdn == NULL) return 0;
+
+		valuedn = ldb_dn_explode_casefold(ldb, tree->u.simple.value.data);
+		if (valuedn == NULL) {
+			talloc_free(msgdn);
+			return 0;
 		}
-		return ldb_dn_cmp(msg->dn, tree->u.simple.value.data) == 0;
+
+		ret = ldb_dn_compare(ldb, msgdn, valuedn);
+
+		talloc_free(msgdn);
+		talloc_free(valuedn);
+
+		if (ret == 0) return 1;
+		return 0;
 	}
 
 	el = ldb_msg_find_element(msg, tree->u.simple.attr);
@@ -113,10 +152,6 @@ static int ldb_match_leaf(struct ldb_context *ldb,
 		return 0;
 	}
 
-	if (strcmp(tree->u.simple.value.data, "*") == 0) {
-		return 1;
-	}
-
 	h = ldb_attrib_handler(ldb, el->name);
 
 	for (i=0;i<el->num_values;i++) {
@@ -129,6 +164,97 @@ static int ldb_match_leaf(struct ldb_context *ldb,
 	return 0;
 }
 
+static int ldb_wildcard_compare(struct ldb_context *ldb,
+				struct ldb_parse_tree *tree,
+				const struct ldb_val value)
+{
+	const struct ldb_attrib_handler *h;
+	struct ldb_val val;
+	struct ldb_val cnk;
+	struct ldb_val *chunk;
+	char *p, *g;
+	char *save_p = NULL;
+	int c = 0;
+
+	h = ldb_attrib_handler(ldb, tree->u.substring.attr);
+
+	if(h->canonicalise_fn(ldb, ldb, &value, &val) != 0)
+		return -1;
+
+	save_p = val.data;
+	cnk.data = NULL;
+
+	if ( ! tree->u.substring.start_with_wildcard ) {
+
+		chunk = tree->u.substring.chunks[c];
+		if(h->canonicalise_fn(ldb, ldb, chunk, &cnk) != 0) goto failed;
+
+		/* FIXME: case of embedded nulls */
+		if (strncmp(val.data, cnk.data, cnk.length) != 0) goto failed;
+		val.length -= cnk.length;
+		val.data += cnk.length;
+		c++;
+		talloc_free(cnk.data);
+		cnk.data = NULL;
+	}
+
+	while (tree->u.substring.chunks[c]) {
+
+		chunk = tree->u.substring.chunks[c];
+		if(h->canonicalise_fn(ldb, ldb, chunk, &cnk) != 0) goto failed;
+
+		/* FIXME: case of embedded nulls */
+		p = strstr(val.data, cnk.data);
+		if (p == NULL) goto failed;
+		if ( (! tree->u.substring.chunks[c + 1]) && (! tree->u.substring.end_with_wildcard) ) {
+			do { /* greedy */
+				g = strstr(p + cnk.length, cnk.data);
+				if (g) p = g;
+			} while(g);
+		}
+		val.length = val.length - (p - (char *)(val.data)) - cnk.length;
+		val.data = p + cnk.length;
+		c++;
+		talloc_free(cnk.data);
+		cnk.data = NULL;
+	}
+
+	if ( (! tree->u.substring.end_with_wildcard) && (*(val.data) != 0) ) goto failed; /* last chunk have not reached end of string */
+	talloc_free(save_p);
+	return 1;
+
+failed:
+	talloc_free(save_p);
+	talloc_free(cnk.data);
+	return 0;
+}
+
+/*
+  match a simple leaf node
+*/
+static int ldb_match_substring(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;
+
+	el = ldb_msg_find_element(msg, tree->u.simple.attr);
+	if (el == NULL) {
+		return 0;
+	}
+
+	for (i = 0; i < el->num_values; i++) {
+		if (ldb_wildcard_compare(ldb, tree, el->values[i]) == 1) {
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
 
 /*
   bitwise-and comparator
@@ -220,18 +346,24 @@ static int ldb_match_extended(struct ldb_context *ldb,
 
   this is a recursive function, and does short-circuit evaluation
  */
-int ldb_match_message(struct ldb_context *ldb, 
-		      struct ldb_message *msg,
-		      struct ldb_parse_tree *tree,
-		      const char *base,
-		      enum ldb_scope scope)
+static int ldb_match_message(struct ldb_context *ldb, 
+			     struct ldb_message *msg,
+			     struct ldb_parse_tree *tree,
+			     const char *base,
+			     enum ldb_scope scope)
 {
 	unsigned int i;
 	int v;
 
 	switch (tree->operation) {
 	case LDB_OP_SIMPLE:
-		break;
+		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);
@@ -256,5 +388,18 @@ int ldb_match_message(struct ldb_context *ldb,
 		return 0;
 	}
 
-	return ldb_match_leaf(ldb, msg, tree, base, scope);
+	return 0;
+}
+
+int ldb_match_msg(struct ldb_context *ldb,
+		  struct ldb_message *msg,
+		  struct ldb_parse_tree *tree,
+		  const char *base,
+		  enum ldb_scope scope)
+{
+	if ( ! ldb_match_scope(ldb, base, msg->dn, scope) ) {
+		return 0;
+	}
+
+	return ldb_match_message(ldb, msg, tree, base, scope);
 }
diff --git a/source4/lib/ldb/common/ldb_parse.c b/source4/lib/ldb/common/ldb_parse.c
index 841a785de5..b519489b48 100644
--- a/source4/lib/ldb/common/ldb_parse.c
+++ b/source4/lib/ldb/common/ldb_parse.c
@@ -194,6 +194,66 @@ char *ldb_binary_encode(void *mem_ctx, struct ldb_val val)
 	return ret;	
 }
 
+/* find the first matching wildcard */
+static char *ldb_parse_find_wildcard(char *value)
+{
+	while (*value) {
+		value = strpbrk(value, "\\*");
+		if (value == NULL) return NULL;
+
+		if (value[0] == '\\') {
+			if (value[1] == '\0') return NULL;
+			value += 2;
+			continue;
+		}
+
+		if (value[0] == '*') return value;
+	}
+
+	return NULL;
+}
+
+/* return a NULL terminated list of binary strings representing the value
+   chunks separated by wildcards that makes the value portion of the filter
+*/
+static struct ldb_val **ldb_wildcard_decode(void *mem_ctx, const char *string)
+{
+	struct ldb_val **ret = NULL;
+	int val = 0;
+	char *wc, *str;
+
+	wc = talloc_strdup(mem_ctx, string);
+	if (wc == NULL) return NULL;
+
+	while (wc && *wc) {
+		str = wc;
+		wc = ldb_parse_find_wildcard(str);
+		if (wc && *wc) {
+			if (wc == str) {
+				wc++;
+				continue;
+			}
+			*wc = 0;
+			wc++;
+		}
+
+		ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
+		if (ret == NULL) return NULL;
+
+		ret[val] = talloc(mem_ctx, struct ldb_val);
+		if (ret[val] == NULL) return NULL;
+
+		*(ret[val]) = ldb_binary_decode(mem_ctx, str);
+		if ((ret[val])->data == NULL) return NULL;
+
+		val++;
+	}
+
+	ret[val] = NULL;
+
+	return ret;
+}
+
 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
 
 
@@ -214,8 +274,11 @@ static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 						 char *attr, char *value)
 {
 	char *p1, *p2, *p3;
+
 	ret->operation = LDB_OP_EXTENDED;
 	ret->u.extended.value = ldb_binary_decode(ret, value);
+	if (ret->u.extended.value.data == NULL) goto failed;
+
 	p1 = strchr(attr, ':');
 	if (p1 == NULL) goto failed;
 	p2 = strchr(p1+1, ':');
@@ -241,7 +304,6 @@ static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 		ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 		if (ret->u.extended.rule_id == NULL) goto failed;
 	}
-	ret->u.extended.value = ldb_binary_decode(ret, value);
 
 	return ret;
 
@@ -293,10 +355,37 @@ static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char *s)
 		/* its an extended match */
 		return ldb_parse_extended(ret, l, val);
 	}
-	
+
+	if (val && strcmp(val, "*") == 0) {
+		ret->operation = LDB_OP_PRESENT;
+		ret->u.present.attr = l;
+
+		return ret;
+	}
+
+	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){
+			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;
 }
@@ -491,6 +580,30 @@ char *ldb_filter_from_tree(void *mem_ctx, struct ldb_parse_tree *tree)
 				      s);
 		talloc_free(s);
 		return ret;
+	case LDB_OP_SUBSTRING:
+		ret = talloc_strdup(mem_ctx, (tree->u.substring.start_with_wildcard)?"*":"");
+		if (ret == NULL) return NULL;
+		for (i = 0; tree->u.substring.chunks[i]; i++) {
+			s2 = ldb_binary_encode(mem_ctx, *(tree->u.substring.chunks[i]));
+			if (s2 == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			s = talloc_asprintf_append(ret, "%s*", s2);
+			if (s == NULL) {
+				talloc_free(ret);
+				return NULL;
+			}
+			ret = s;
+		}
+		if ( ! tree->u.substring.end_with_wildcard ) {
+			ret[strlen(ret) - 1] = '\0'; /* remove last wildcard */
+		}
+		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);
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index b2468b6ecb..8233e78f0e 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -154,7 +154,8 @@ struct ldb_debug_ops {
 
 
 /* structues for ldb_parse_tree handling code */
-enum ldb_parse_op {LDB_OP_SIMPLE=1, LDB_OP_EXTENDED=2, 
+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='!'};
 
 struct ldb_parse_tree {
@@ -166,6 +167,15 @@ struct ldb_parse_tree {
 		} simple;
 		struct {
 			char *attr;
+		} present;
+		struct {
+			char *attr;
+			int start_with_wildcard;
+			int end_with_wildcard;
+			struct ldb_val **chunks;
+		} substring;
+		struct {
+			char *attr;
 			int dnAttributes;
 			char *rule_id;
 			struct ldb_val value;
@@ -211,14 +221,12 @@ struct ldb_attrib_handler {
 };
 
 #define LDB_ATTR_FLAG_HIDDEN     (1<<0)
-#define LDB_ATTR_FLAG_WILDCARD   (1<<1)
 
 /* well-known ldap attribute syntaxes - see rfc2252 section 4.3.2 */
 #define LDB_SYNTAX_DN                   "1.3.6.1.4.1.1466.115.121.1.12"
 #define LDB_SYNTAX_DIRECTORY_STRING     "1.3.6.1.4.1.1466.115.121.1.15"
 #define LDB_SYNTAX_INTEGER              "1.3.6.1.4.1.1466.115.121.1.27"
 #define LDB_SYNTAX_OCTET_STRING         "1.3.6.1.4.1.1466.115.121.1.40"
-#define LDB_SYNTAX_WILDCARD             "LDB_SYNTAX_WILDCARD"
 #define LDB_SYNTAX_OBJECTCLASS          "LDB_SYNTAX_OBJECTCLASS"
 
 /*
diff --git a/source4/lib/ldb/include/ldb_private.h b/source4/lib/ldb/include/ldb_private.h
index 1d7d453767..da813eb588 100644
--- a/source4/lib/ldb/include/ldb_private.h
+++ b/source4/lib/ldb/include/ldb_private.h
@@ -175,11 +175,11 @@ struct ldb_module *schema_module_init(struct ldb_context *ldb, const char *optio
 const struct ldb_attrib_handler *ldb_attrib_handler(struct ldb_context *ldb,
 						    const char *attrib);
 
-int ldb_match_message(struct ldb_context *ldb, 
-		      struct ldb_message *msg,
-		      struct ldb_parse_tree *tree,
-		      const char *base,
-		      enum ldb_scope scope);
+int ldb_match_msg(struct ldb_context *ldb, 
+		  struct ldb_message *msg,
+		  struct ldb_parse_tree *tree,
+		  const char *base,
+		  enum ldb_scope scope);
 
 void ldb_remove_attrib_handler(struct ldb_context *ldb, const char *attrib);
 const struct ldb_attrib_handler *ldb_attrib_handler_syntax(struct ldb_context *ldb,
@@ -193,9 +193,10 @@ int ldb_setup_wellknown_attributes(struct ldb_context *ldb);
 /* The following definitions come from lib/ldb/common/ldb_dn.c  */
 struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn);
 char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn);
+int ldb_dn_compare_base(struct ldb_context *ldb, const struct ldb_dn *base, const struct ldb_dn *dn);
 int ldb_dn_compare(struct ldb_context *ldb, const struct ldb_dn *edn0, const struct ldb_dn *edn1);
 struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, const struct ldb_dn *edn);
-
+struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn);
 
 /* The following definitions come from lib/ldb/common/ldb_attributes.c  */
 const char **ldb_subclass_list(struct ldb_context *ldb, const char *class);
diff --git a/source4/lib/ldb/ldb_tdb/ldb_cache.c b/source4/lib/ldb/ldb_tdb/ldb_cache.c
index 0b7ddad5db..be76f7085b 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_cache.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_cache.c
@@ -39,9 +39,8 @@
 
 #define LTDB_FLAG_CASE_INSENSITIVE (1<<0)
 #define LTDB_FLAG_INTEGER          (1<<1)
-#define LTDB_FLAG_WILDCARD         (1<<2)
-#define LTDB_FLAG_HIDDEN           (1<<3)
-#define LTDB_FLAG_OBJECTCLASS      (1<<4)
+#define LTDB_FLAG_HIDDEN           (1<<2)
+#define LTDB_FLAG_OBJECTCLASS      (1<<3)
 
 /* valid attribute flags */
 static const struct {
@@ -50,7 +49,6 @@ static const struct {
 } ltdb_valid_attr_flags[] = {
 	{ "CASE_INSENSITIVE", LTDB_FLAG_CASE_INSENSITIVE },
 	{ "INTEGER", LTDB_FLAG_INTEGER },
-	{ "WILDCARD", LTDB_FLAG_WILDCARD },
 	{ "HIDDEN", LTDB_FLAG_HIDDEN },
 	{ "NONE", 0 },
 	{ NULL, 0 }
@@ -138,10 +136,6 @@ static int ltdb_attributes_load(struct ldb_module *module)
 		case 0:
 			syntax = LDB_SYNTAX_OCTET_STRING;
 			break;
-		case LTDB_FLAG_WILDCARD:
-		case LTDB_FLAG_WILDCARD | LTDB_FLAG_CASE_INSENSITIVE:
-			syntax = LDB_SYNTAX_WILDCARD;
-			break;
 		case LTDB_FLAG_CASE_INSENSITIVE:
 			syntax = LDB_SYNTAX_DIRECTORY_STRING;
 			break;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index a3317a8765..03ad0612d4 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -188,13 +188,6 @@ static int ltdb_index_dn_simple(struct ldb_module *module,
 	list->count = 0;
 	list->dn = NULL;
 
-	/*
-	  if the value is a wildcard then we can't do a match via indexing
-	*/
-	if (ltdb_has_wildcard(module, tree->u.simple.attr, &tree->u.simple.value)) {
-		return -1;
-	}
-
 	/* 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) {
@@ -581,6 +574,8 @@ static int ltdb_index_dn(struct ldb_module *module,
 		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;
@@ -638,7 +633,7 @@ static int ldb_index_filter(struct ldb_module *module, struct ldb_parse_tree *tr
 		}
 
 		ret = 0;
-		if (ldb_match_message(module->ldb, msg, tree, base, scope) == 1) {
+		if (ldb_match_msg(module->ldb, msg, tree, base, scope) == 1) {
 			ret = ltdb_add_attr_results(module, msg, attrs, &count, res);
 		}
 		talloc_free(msg);
diff --git a/source4/lib/ldb/ldb_tdb/ldb_search.c b/source4/lib/ldb/ldb_tdb/ldb_search.c
index e48043da88..3ecb2d9b39 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_search.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_search.c
@@ -188,34 +188,6 @@ static struct ldb_message *ltdb_pull_attrs(struct ldb_module *module,
 }
 
 
-
-/*
-  see if a ldb_val is a wildcard
-  return 1 if yes, 0 if no
-*/
-int ltdb_has_wildcard(struct ldb_module *module, const char *attr_name, 
-		      const struct ldb_val *val)
-{
-	const struct ldb_attrib_handler *h;
-
-	/* all attribute types recognise the "*" wildcard */
-	if (val->length == 1 && strncmp((char *)val->data, "*", 1) == 0) {
-		return 1;
-	}
-
-	if (strpbrk(val->data, "*?") == NULL) {
-		return 0;
-	}
-
-	h = ldb_attrib_handler(module->ldb, attr_name);
-	if (h->flags & LDB_ATTR_FLAG_WILDCARD) {
-		return 1;
-	}
-
-	return 0;
-}
-
-
 /*
   search the database for a single simple dn, returning all attributes
   in a single message
@@ -416,7 +388,7 @@ static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, voi
 	}
 
 	/* see if it matches the given expression */
-	if (!ldb_match_message(sinfo->module->ldb, msg, sinfo->tree, 
+	if (!ldb_match_msg(sinfo->module->ldb, msg, sinfo->tree, 
 			       sinfo->base, sinfo->scope)) {
 		talloc_free(msg);
 		return 0;
diff --git a/source4/lib/ldb/tests/schema-tests/schema.ldif b/source4/lib/ldb/tests/schema-tests/schema.ldif
index 59757d22a9..d1ad50f2cc 100644
--- a/source4/lib/ldb/tests/schema-tests/schema.ldif
+++ b/source4/lib/ldb/tests/schema-tests/schema.ldif
@@ -13,11 +13,8 @@ realm: CASE_INSENSITIVE
 userPrincipalName: CASE_INSENSITIVE
 servicePrincipalName: CASE_INSENSITIVE
 name: CASE_INSENSITIVE
-name: WILDCARD
 dn: CASE_INSENSITIVE
-dn: WILDCARD
 sAMAccountName: CASE_INSENSITIVE
-sAMAccountName: WILDCARD
 objectClass: CASE_INSENSITIVE
 unicodePwd: HIDDEN
 ntPwdHash: HIDDEN
diff --git a/source4/lib/ldb/tests/test-attribs.ldif b/source4/lib/ldb/tests/test-attribs.ldif
index e6fe1dcf5a..0bb3ebead6 100644
--- a/source4/lib/ldb/tests/test-attribs.ldif
+++ b/source4/lib/ldb/tests/test-attribs.ldif
@@ -1,6 +1,5 @@
 dn: @ATTRIBUTES
 uid: CASE_INSENSITIVE
-uid: WILDCARD
 cn: CASE_INSENSITIVE
 ou: CASE_INSENSITIVE
 dn: CASE_INSENSITIVE
diff --git a/source4/lib/ldb/tests/test-generic.sh b/source4/lib/ldb/tests/test-generic.sh
index db6377d078..3ad17fe9d3 100755
--- a/source4/lib/ldb/tests/test-generic.sh
+++ b/source4/lib/ldb/tests/test-generic.sh
@@ -45,6 +45,15 @@ $VALGRIND ldbsearch '((' uid || exit 1
 $VALGRIND ldbsearch '(objectclass=)' uid || exit 1
 $VALGRIND ldbsearch -b 'cn=Hampster Ursula,ou=Alumni Association,ou=People,o=University of Michigan,c=TEST' -s base "" sn || exit 1
 
+echo "Test wildcard match"
+$VALGRIND ldbadd $LDBDIR/tests/test-wildcard.ldif  || exit 1
+$VALGRIND ldbsearch '(cn=test*multi)'  || exit 1
+$VALGRIND ldbsearch '(cn=*test*multi*)'  || exit 1
+$VALGRIND ldbsearch '(cn=*test_multi)'  || exit 1
+$VALGRIND ldbsearch '(cn=test_multi*)'  || exit 1
+$VALGRIND ldbsearch '(cn=test*multi*test*multi)'  || exit 1
+$VALGRIND ldbsearch '(cn=test*multi*test*multi*multi_*)' || exit 1
+
 echo "Starting ldbtest indexed"
 time $VALGRIND ldbtest --num-records 100 --num-searches 500  || exit 1
 
diff --git a/source4/lib/ldb/tests/test-index.ldif b/source4/lib/ldb/tests/test-index.ldif
index 7ba0106394..a793537187 100644
--- a/source4/lib/ldb/tests/test-index.ldif
+++ b/source4/lib/ldb/tests/test-index.ldif
@@ -4,7 +4,6 @@ dn: @INDEXLIST
 
 dn: @ATTRIBUTES
 uid: CASE_INSENSITIVE
-uid: WILDCARD
 
 dn: @SUBCLASSES
 top: person
diff --git a/source4/lib/ldb/tests/test-tdb-features.sh b/source4/lib/ldb/tests/test-tdb-features.sh
index 613afef8ad..fb68733802 100644
--- a/source4/lib/ldb/tests/test-tdb-features.sh
+++ b/source4/lib/ldb/tests/test-tdb-features.sh
@@ -16,7 +16,7 @@ checkcount() {
     echo "OK: $count $expression"
 }
 
-echo "Testing case sensitve search"
+echo "Testing case sensitive search"
 cat <<EOF | $VALGRIND bin/ldbadd || exit 1
 dn: cn=t1,cn=TEST
 objectClass: testclass
@@ -24,7 +24,7 @@ test: foo
 EOF
 checkcount 1 '(test=foo)'
 checkcount 0 '(test=FOO)'
-checkcount 0 '(test=fo*)'
+checkcount 0 '(test=FO*)'
 
 echo "Making case insensitive"
 cat <<EOF | $VALGRIND bin/ldbmodify || exit 1
@@ -37,17 +37,6 @@ EOF
 echo $ldif | $VALGRIND bin/ldbmodify || exit 1
 checkcount 1 '(test=foo)'
 checkcount 1 '(test=FOO)'
-checkcount 0 '(test=fo*)'
-
-echo "adding wildcard"
-cat <<EOF | $VALGRIND bin/ldbmodify || exit 1
-dn: @ATTRIBUTES
-changetype: modify
-add: test
-test: WILDCARD
-EOF
-checkcount 1 '(test=foo)'
-checkcount 1 '(test=FOO)'
 checkcount 1 '(test=fo*)'
 
 echo "adding i"
@@ -115,7 +104,7 @@ checkcount 1 '(i=256)'
 checkcount 0 '(i=-256)'
 checkcount 1 '(test=foo)'
 checkcount 1 '(test=FOO)'
-checkcount 1 '(test=fo*)'
+checkcount 1 '(test=*f*o)'
 
 echo "making test case sensitive"
 cat <<EOF | $VALGRIND bin/ldbmodify || exit 1
@@ -126,5 +115,5 @@ test: NONE
 EOF
 checkcount 1 '(test=foo)'
 checkcount 0 '(test=FOO)'
-checkcount 0 '(test=fo*)'
+checkcount 1 '(test=f*o*)'