s4-ldb: use TYPESAFE_QSORT() in the rest of the ldb code
[ira/wip.git] / source4 / lib / ldb / common / ldb_dn.c
index 639e8b2837f003f85046b9807dc521b5b4d3cd8a..c395be29007813ad365114422f0152f94cc3f5fd 100644 (file)
@@ -77,9 +77,6 @@ struct ldb_dn {
 
        unsigned int ext_comp_num;
        struct ldb_dn_ext_component *ext_components;
-
-       char extra_type;
-       struct ldb_val extra_val;
 };
 
 /* it is helpful to be able to break on this in gdb */
@@ -103,17 +100,16 @@ struct ldb_dn *ldb_dn_from_ldb_val(void *mem_ctx,
                return NULL;
        }
 
-       /* if the DN starts with B: then it has a binary blob
-        * attached. Called the binary dn parser, which will call back
-        * here for the rest of the DN */
-       if (strdn->data && strncmp((char *)strdn->data, "B:", 2) == 0) {
-               return ldb_dn_binary_from_ldb_val(mem_ctx, ldb, strdn);
-       }
-
        dn = talloc_zero(mem_ctx, struct ldb_dn);
        LDB_DN_NULL_FAILED(dn);
 
-       dn->ldb = ldb;
+       dn->ldb = talloc_get_type(ldb, struct ldb_context);
+       if (dn->ldb == NULL) {
+               /* the caller probably got the arguments to
+                  ldb_dn_new() mixed up */
+               talloc_free(dn);
+               return NULL;
+       }
 
        if (strdn->data && strdn->length) {
                const char *data = (const char *)strdn->data;
@@ -157,173 +153,6 @@ failed:
        return NULL;
 }
 
-/*
-  a version of strhex_to_str internal to ldb, for use by the binary
-  ldb code
- */
-static size_t ldb_strhex_to_str(char *p, size_t p_len, const char *strhex, 
-                               size_t strhex_len)
-{
-       size_t i;
-       size_t num_chars = 0;
-       uint8_t   lonybble, hinybble;
-       const char     *hexchars = "0123456789ABCDEF";
-       char           *p1 = NULL, *p2 = NULL;
-
-       for (i = 0; i < strhex_len && strhex[i] != 0; i++) {
-               if (!(p1 = strchr(hexchars, toupper((unsigned char)strhex[i]))))
-                       break;
-
-               i++; /* next hex digit */
-
-               if (!(p2 = strchr(hexchars, toupper((unsigned char)strhex[i]))))
-                       break;
-
-               /* get the two nybbles */
-               hinybble = PTR_DIFF(p1, hexchars);
-               lonybble = PTR_DIFF(p2, hexchars);
-
-               if (num_chars >= p_len) {
-                       break;
-               }
-
-               p[num_chars] = (hinybble << 4) | lonybble;
-               num_chars++;
-
-               p1 = NULL;
-               p2 = NULL;
-       }
-       return num_chars;
-}
-
-/* strdn may be NULL */
-struct ldb_dn *ldb_dn_binary_from_ldb_val(void *mem_ctx,
-                                         struct ldb_context *ldb,
-                                         const struct ldb_val *strdn)
-{
-       struct ldb_dn *dn;
-       const char *data;
-       size_t len;
-       char *linearized;
-       TALLOC_CTX *tmp_ctx;
-       char *p1;
-       char *p2;
-       uint32_t blen;
-       struct ldb_val bval;
-       struct ldb_val dval;
-       char *dn_str;
-       char *old;
-
-       if (strdn && strdn->data
-           && (strlen((const char*)strdn->data) != strdn->length)) {
-               /* The RDN must not contain a character with value 0x0 */
-               return NULL;
-       }
-
-       if (!strdn->data || strdn->length == 0) {
-               return NULL;
-
-       }
-
-       tmp_ctx = talloc_new(mem_ctx);
-       if (tmp_ctx == NULL) {
-               return NULL;
-       }
-
-       data = (const char *)strdn->data;
-
-       if (data[0] != 'B') {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": no prefix?\n");
-               return NULL;
-       }
-
-       len = strdn->length;
-       linearized = talloc_strndup(tmp_ctx, data, len);
-       if (linearized == NULL) {
-               goto failed;
-       }
-
-       ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": processing DN '%s'\n", linearized);
-
-       p1 = linearized;
-
-       p1++; len--;
-       
-       if (p1[0] != ':') {
-               goto failed;
-       }
-       p1++;
-       len--;
-       
-       errno = 0;
-       blen = strtoul(p1, &p2, 10);
-       if (errno != 0) {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": failed\n");
-               goto failed;
-       }
-       if (p2 == NULL) {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": failed\n");
-               goto failed;
-       }
-       if (p2[0] != ':') {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": failed\n");
-               goto failed;
-       }
-       len -= PTR_DIFF(p2,p1);//???
-       p1 = p2+1;
-       len--;
-       
-       if (blen >= len) {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": blen=%u len=%u\n", (unsigned)blen, (unsigned)len);
-               goto failed;
-       }
-
-       p2 = p1 + blen;
-       if (p2[0] != ':') {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": %s", p2);
-               goto failed;
-       }
-       dn_str = p2+1;
-       
-       bval.length = (blen/2)+1;
-       bval.data = talloc_size(tmp_ctx, bval.length);
-       if (bval.data == NULL) {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": err\n");
-               goto failed;
-       }
-       bval.data[bval.length-1] = 0;
-       
-       bval.length = ldb_strhex_to_str((char *)bval.data, bval.length,
-                                       p1, blen);
-       
-       dval.data = (uint8_t *)dn_str;
-       dval.length = strlen(dn_str);
-       
-       dn = ldb_dn_from_ldb_val(mem_ctx, ldb, &dval);
-       if (dn == NULL) {
-               ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": err\n");
-               goto failed;
-       }
-       dn->extra_type = data[0];
-       dn->extra_val = bval;
-       talloc_steal(dn, bval.data);
-
-       *dn_str = '\0';
-       old = dn->linearized;
-       dn->linearized = talloc_asprintf(dn, "%s%s", linearized, dn->linearized);
-       talloc_free(old);
-       if (dn->ext_linearized) {
-               old = dn->ext_linearized;
-               dn->ext_linearized = talloc_asprintf(dn, "%s%s", linearized, dn->ext_linearized);
-               talloc_free(old);
-       }
-       
-       return dn;
-failed:
-       talloc_free(tmp_ctx);
-       return NULL;
-}
-
 /* strdn may be NULL */
 struct ldb_dn *ldb_dn_new(void *mem_ctx,
                          struct ldb_context *ldb,
@@ -357,6 +186,7 @@ struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx,
        return NULL;
 }
 
+/* see RFC2253 section 2.4 */
 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 {
        const char *p, *s;
@@ -367,8 +197,7 @@ static int ldb_dn_escape_internal(char *dst, const char *src, int len)
        d = dst;
 
        while (p - src < len) {
-
-               p += strcspn(p, ",=\n+<>#;\\\"");
+               p += strcspn(p, ",=\n\r+<>#;\\\" ");
 
                if (p - src == len) /* found no escapable chars */
                        break;
@@ -376,14 +205,46 @@ static int ldb_dn_escape_internal(char *dst, const char *src, int len)
                /* copy the part of the string before the stop */
                memcpy(d, s, p - s);
                d += (p - s); /* move to current position */
+               
+               switch (*p) {
+               case ' ':
+                       if (p == src || (p-src)==(len-1)) {
+                               /* if at the beginning or end
+                                * of the string then escape */
+                               *d++ = '\\';
+                               *d++ = *p++;                                     
+                       } else {
+                               /* otherwise don't escape */
+                               *d++ = *p++;
+                       }
+                       break;
 
-               if (*p) { /* it is a normal escapable character */
+               case '#':
+                       /* despite the RFC, windows escapes a #
+                          anywhere in the string */
+               case ',':
+               case '+':
+               case '"':
+               case '\\':
+               case '<':
+               case '>':
+               case '?':
+                       /* these must be escaped using \c form */
                        *d++ = '\\';
                        *d++ = *p++;
-               } else { /* we have a zero byte in the string */
-                       strncpy(d, "\00", 3); /* escape the zero */
-                       d += 3;
-                       p++; /* skip the zero */
+                       break;
+
+               default: {
+                       /* any others get \XX form */
+                       unsigned char v;
+                       const char *hexbytes = "0123456789ABCDEF";
+                       v = *(const unsigned char *)p;
+                       *d++ = '\\';
+                       *d++ = hexbytes[v>>4];
+                       *d++ = hexbytes[v&0xF];
+                       p++;
+                       break;
+               }
                }
                s = p; /* move forward */
        }
@@ -459,13 +320,6 @@ static bool ldb_dn_explode(struct ldb_dn *dn)
 
        is_index = (strncmp(parse_dn, "DN=@INDEX:", 10) == 0);
 
-       if (strncmp(parse_dn, "B:", 2) == 0) {
-               parse_dn = strchr(parse_dn, ':');
-               parse_dn = strchr(parse_dn+1, ':');
-               parse_dn = strchr(parse_dn+1, ':');
-               parse_dn++;
-       }
-
        /* Empty DNs */
        if (parse_dn[0] == '\0') {
                return true;
@@ -766,11 +620,13 @@ static bool ldb_dn_explode(struct ldb_dn *dn)
 
                                continue;
 
+                       case '+':
                        case '=':
                                /* to main compatibility with earlier
                                versions of ldb indexing, we have to
                                accept the base64 encoded binary index
-                               values, which contain a '=' */
+                               values, which contain a '+' or '='
+                               which should normally be escaped */
                                if (is_index) {
                                        if ( t ) t = NULL;
                                        *d++ = *p++;
@@ -778,13 +634,10 @@ static bool ldb_dn_explode(struct ldb_dn *dn)
                                        break;
                                }
                                /* fall through */
-                       case '\n':
-                       case '+':
+                       case '\"':
                        case '<':
                        case '>':
-                       case '#':
                        case ';':
-                       case '\"':
                                /* a string with not escaped specials is invalid (tested) */
                                if ( ! escape) {
                                        ldb_dn_mark_invalid(dn);
@@ -814,17 +667,20 @@ static bool ldb_dn_explode(struct ldb_dn *dn)
 
                        default:
                                if (escape) {
-                                       if (sscanf(p, "%02x", &x) != 1) {
-                                               /* invalid escaping sequence */
-                                               ldb_dn_mark_invalid(dn);
-                                               goto failed;
+                                       if (isxdigit(p[0]) && isxdigit(p[1])) {
+                                               if (sscanf(p, "%02x", &x) != 1) {
+                                                       /* invalid escaping sequence */
+                                                       ldb_dn_mark_invalid(dn);
+                                                       goto failed;
+                                               }
+                                               p += 2;
+                                               *d++ = (unsigned char)x;
+                                       } else {
+                                               *d++ = *p++;
                                        }
-                                       escape = false;
 
-                                       p += 2;
-                                       *d++ = (unsigned char)x;
+                                       escape = false;
                                        l++;
-
                                        if ( t ) t = NULL;
                                        break;
                                }
@@ -882,29 +738,10 @@ bool ldb_dn_validate(struct ldb_dn *dn)
        return ldb_dn_explode(dn);
 }
 
-static char *data_blob_hex_string_upper(TALLOC_CTX *mem_ctx, const struct ldb_val *blob)
-{
-       int i;
-       char *hex_string;
-
-       hex_string = talloc_array(mem_ctx, char, (blob->length*2)+1);
-       if (!hex_string) {
-               return NULL;
-       }
-
-       for (i = 0; i < blob->length; i++)
-               slprintf(&hex_string[i*2], 3, "%02X", blob->data[i]);
-
-       hex_string[(blob->length*2)] = '\0';
-       return hex_string;
-}
-
-
 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 {
        int i, len;
        char *d, *n;
-       char *extra_prefix = NULL;
 
        if ( ! dn || ( dn->invalid)) return NULL;
 
@@ -915,12 +752,6 @@ const char *ldb_dn_get_linearized(struct ldb_dn *dn)
                return NULL;
        }
 
-       if (dn->extra_type == 'B') {
-               char *hexstr = data_blob_hex_string_upper(dn, &dn->extra_val);
-               extra_prefix = talloc_asprintf(dn, "B:%u:%s:", (unsigned)(dn->extra_val.length*2), hexstr);
-               talloc_free(hexstr);
-       }
-
        if (dn->comp_num == 0) {
                dn->linearized = talloc_strdup(dn, "");
                if ( ! dn->linearized) return NULL;
@@ -961,20 +792,20 @@ const char *ldb_dn_get_linearized(struct ldb_dn *dn)
        dn->linearized = talloc_realloc(dn, dn->linearized,
                                        char, (d - dn->linearized + 1));
 
-       if (extra_prefix) {
-               char *old = dn->linearized;
-               dn->linearized = talloc_asprintf(dn, "%s%s", extra_prefix, old);
-               talloc_free(old);
-               talloc_free(extra_prefix);
-       }
-
        return dn->linearized;
 }
 
+static int ldb_dn_extended_component_compare(const void *p1, const void *p2)
+{
+       const struct ldb_dn_ext_component *ec1 = (const struct ldb_dn_ext_component *)p1;
+       const struct ldb_dn_ext_component *ec2 = (const struct ldb_dn_ext_component *)p2;
+       return strcmp(ec1->name, ec2->name);
+}
+
 char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
 {
        const char *linearized = ldb_dn_get_linearized(dn);
-       char *p = NULL;
+       char *p;
        int i;
 
        if (!linearized) {
@@ -989,13 +820,12 @@ char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
                return NULL;
        }
 
-       if (dn->extra_type == 'B') {
-               char *hexstr = data_blob_hex_string_upper(mem_ctx, &dn->extra_val);
-               p = talloc_asprintf(mem_ctx, "B:%u:%s:", (unsigned)(dn->extra_val.length*2), hexstr);
-               talloc_free(hexstr);
-       } else {
-               p = talloc_strdup(mem_ctx, "");
-       }
+       /* sort the extended components by name. The idea is to make
+        * the resulting DNs consistent, plus to ensure that we put
+        * 'DELETED' first, so it can be very quickly recognised
+        */
+       TYPESAFE_QSORT(dn->ext_components, dn->ext_comp_num,
+                      ldb_dn_extended_component_compare);
 
        for (i = 0; i < dn->ext_comp_num; i++) {
                const struct ldb_dn_extended_syntax *ext_syntax;
@@ -1005,6 +835,9 @@ char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
                int ret;
 
                ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, name);
+               if (!ext_syntax) {
+                       return NULL;
+               }
 
                if (mode == 1) {
                        ret = ext_syntax->write_clear_fn(dn->ldb, mem_ctx,
@@ -1021,9 +854,11 @@ char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
                }
 
                if (i == 0) {
-                       p = talloc_asprintf_append_buffer(p, "<%s=%s>", name, val.data);
+                       p = talloc_asprintf(mem_ctx, "<%s=%s>", 
+                                           name, val.data);
                } else {
-                       p = talloc_asprintf_append_buffer(p, ";<%s=%s>",name, val.data);
+                       p = talloc_asprintf_append_buffer(p, ";<%s=%s>",
+                                                         name, val.data);
                }
 
                talloc_free(val.data);
@@ -1034,12 +869,6 @@ char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
        }
 
        if (dn->ext_comp_num && *linearized) {
-               if (strncmp(linearized, "B:", 2) == 0) {
-                       linearized = strchr(linearized, ':');
-                       linearized = strchr(linearized+1, ':');
-                       linearized = strchr(linearized+1, ':');
-                       linearized++;
-               }
                p = talloc_asprintf_append_buffer(p, ";%s", linearized);
        }
 
@@ -1050,6 +879,22 @@ char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
        return p;
 }
 
+/*
+  filter out all but an acceptable list of extended DN components
+ */
+void ldb_dn_extended_filter(struct ldb_dn *dn, const char * const *accept)
+{
+       int i;
+       for (i=0; i<dn->ext_comp_num; i++) {
+               if (!ldb_attr_in_list(accept, dn->ext_components[i].name)) {
+                       memmove(&dn->ext_components[i],
+                               &dn->ext_components[i+1],
+                               (dn->ext_comp_num-(i+1))*sizeof(dn->ext_components[0]));
+                       dn->ext_comp_num--;
+                       i--;
+               }
+       }
+}
 
 
 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
@@ -2046,11 +1891,17 @@ int ldb_dn_set_extended_component(struct ldb_dn *dn,
 {
        struct ldb_dn_ext_component *p;
        int i;
+       struct ldb_val v2;
 
        if ( ! ldb_dn_validate(dn)) {
                return LDB_ERR_OTHER;
        }
 
+       if (!ldb_dn_extended_syntax_by_name(dn->ldb, name)) {
+               /* We don't know how to handle this type of thing */
+               return LDB_ERR_INVALID_DN_SYNTAX;
+       }
+
        for (i=0; i < dn->ext_comp_num; i++) {
                if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
                        if (val) {
@@ -2064,7 +1915,7 @@ int ldb_dn_set_extended_component(struct ldb_dn *dn,
                                        ldb_dn_mark_invalid(dn);
                                        return LDB_ERR_OPERATIONS_ERROR;
                                }
-
+                               return LDB_SUCCESS;
                        } else {
                                if (i != (dn->ext_comp_num - 1)) {
                                        memmove(&dn->ext_components[i],
@@ -2087,6 +1938,13 @@ int ldb_dn_set_extended_component(struct ldb_dn *dn,
                }
        }
 
+       if (val == NULL) {
+               /* removing a value that doesn't exist is not an error */
+               return LDB_SUCCESS;
+       }
+
+       v2 = *val;
+
        p = dn->ext_components
                = talloc_realloc(dn,
                                 dn->ext_components,
@@ -2097,7 +1955,7 @@ int ldb_dn_set_extended_component(struct ldb_dn *dn,
                return LDB_ERR_OPERATIONS_ERROR;
        }
 
-       p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, val);
+       p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, &v2);
        p[dn->ext_comp_num].name = talloc_strdup(p, name);
 
        if (!dn->ext_components[i].name || !dn->ext_components[i].value.data) {
@@ -2131,7 +1989,7 @@ bool ldb_dn_is_special(struct ldb_dn *dn)
 bool ldb_dn_has_extended(struct ldb_dn *dn)
 {
        if ( ! dn || dn->invalid) return false;
-       if (dn->ext_linearized && strchr(dn->ext_linearized,'<')) return true;
+       if (dn->ext_linearized && (dn->ext_linearized[0] == '<')) return true;
        return dn->ext_comp_num != 0;
 }
 
@@ -2149,25 +2007,26 @@ bool ldb_dn_is_null(struct ldb_dn *dn)
        return false;
 }
 
-int ldb_dn_get_binary(struct ldb_dn *dn, struct ldb_val *val)
+/*
+  this updates dn->components, taking the components from ref_dn.
+  This is used by code that wants to update the DN path of a DN
+  while not impacting on the extended DN components
+ */
+int ldb_dn_update_components(struct ldb_dn *dn, const struct ldb_dn *ref_dn)
 {
-       ZERO_STRUCTP(val);
-       if (dn->extra_type != 'B') {
-               return LDB_SUCCESS;
+       dn->components = talloc_realloc(dn, dn->components,
+                                       struct ldb_dn_component, ref_dn->comp_num);
+       if (!dn->components) {
+               return LDB_ERR_OPERATIONS_ERROR;
        }
-       *val = dn->extra_val;
-       return LDB_SUCCESS;
-}
-
-int ldb_dn_set_binary(struct ldb_dn *dn, struct ldb_val *val)
-{
-       dn->extra_type = 'B';
-       dn->extra_val.data = talloc_memdup(dn, val->data, val->length);
-       dn->extra_val.length = val->length;
+       memcpy(dn->components, ref_dn->components,
+              sizeof(struct ldb_dn_component)*ref_dn->comp_num);
+       dn->comp_num = ref_dn->comp_num;
 
        talloc_free(dn->linearized);
        talloc_free(dn->ext_linearized);
-       dn->linearized = NULL;
        dn->ext_linearized = NULL;
+       dn->linearized = NULL;
+
        return LDB_SUCCESS;
 }