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)

4 files changed, 376 insertions, 129 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);