source4/lib/ldb/common/ldb_dn.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce 2004
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 2 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: ldb dn explode and utility functions
  29  *
  30  *  Description: - explode a dn into it's own basic elements
  31  *                 and put them in a structure
  32  *               - manipulate ldb_dn structures
  33  *
  34  *  Author: Simo Sorce
  35  */
  36
  37 #include "includes.h"
  38 #include "ldb/include/ldb.h"
  39 #include "ldb/include/ldb_private.h"
  40 #include "ldb/include/ldb_dn.h"
  41
  42
  43 #define LDB_DN_NULL_RETURN(x) do { if (!x) return NULL; } while(0)
  44
  45 static char *escape_string(void *mem_ctx, const char *src)
  46 {
  47         const char *p, *s;
  48         char *d, *dst;
  49
  50         LDB_DN_NULL_RETURN(src);
  51
  52         /* allocate destination string, it will be at most 3 times the source */
  53         dst = d = talloc_array(mem_ctx, char, strlen(src) * 3 + 1);
  54         LDB_DN_NULL_RETURN(dst);
  55
  56         p = s = src;
  57
  58         while (p) {
  59                 p += strcspn(p, ",=\n+<>#;\\\"");
  60                 if (*p == '\0') /* no special s found, all ok */
  61                         break;
  62
  63                 if (*p) { /* copy part of the string and escape */
  64                         memcpy(d, s, p - s);
  65                         d += (p - s);
  66                         *d++ = '\\';
  67                         *d++ = *p++;
  68                         s = p;
  69                 }
  70         }
  71
  72         /* copy the last part (with zero) and return */
  73         memcpy(d, s, &src[strlen(src)] - s + 1);
  74
  75         return dst;
  76 }
  77
  78 static char *unescape_string(void *mem_ctx, const char *src)
  79 {
  80         unsigned x;
  81         char *p, *dst, *end;
  82
  83         LDB_DN_NULL_RETURN(src);
  84
  85         dst = p = talloc_strdup(mem_ctx, src);
  86         LDB_DN_NULL_RETURN(dst);
  87
  88         end = &dst[strlen(dst)];
  89
  90         while (*p) {
  91                 p += strcspn(p, ",=\n+<>#;\\\"");
  92                 if (*p == '\0') /* no escapes or specials found, all ok */
  93                         return dst;
  94
  95                 if (*p == '\\') {
  96                         if (strchr(",=\n+<>#;\\\"", p[1])) {
  97                                 memmove(p, p + 1, end - (p + 1) + 1);
  98                                 end--;
  99                                 p++;
 100                                 continue;
 101                         }
 102
 103                         if (sscanf(p + 1, "%02x", &x) == 1) {
 104                                 *p = (unsigned char)x;
 105                                 memmove(p + 1, p + 3, end - (p + 3) + 1);
 106                                 end -= 2;
 107                                 p++;
 108                                 continue;
 109                         }
 110                 }
 111
 112                 /* a string with not escaped specials is invalid */
 113
 114                 return NULL;
 115         }
 116
 117         return dst;
 118 }
 119
 120 static char *seek_to_separator(char *string, const char *separator)
 121 {
 122         char *p;
 123
 124         p = strchr(string, '=');
 125
 126         LDB_DN_NULL_RETURN(p);
 127
 128         p++;
 129
 130         /* check if there are quotes surrounding the value */
 131         p += strspn(p, " \n"); /* skip white spaces after '=' */
 132
 133         if (*p == '\"') {
 134                 p++;
 135                 while (*p != '\"') {
 136                         p = strchr(p, '\"');
 137                         LDB_DN_NULL_RETURN(p);
 138
 139                         if (*(p - 1) == '\\')
 140                                 p++;
 141                 }
 142         }
 143
 144         p += strcspn(p, separator);
 145
 146         return p;
 147 }
 148
 149 static char *ldb_dn_trim_string(char *string, const char *edge)
 150 {
 151         char *s, *p;
 152
 153         /* seek out edge from start of string */
 154         s = string + strspn(string, edge);
 155
 156         /* backwards skip from end of string */
 157         p = &s[strlen(s) - 1];
 158         while (p > s && strchr(edge, *p)) {
 159                 *p = '\0';
 160                 p--;
 161         }
 162
 163         return s;
 164 }
 165
 166 static struct ldb_dn_attribute *ldb_dn_explode_attribute(void *mem_ctx, char *raw_attribute)
 167 {
 168         struct ldb_dn_attribute *at;
 169         char *p;
 170
 171         at = talloc(mem_ctx, struct ldb_dn_attribute);
 172         LDB_DN_NULL_RETURN(at);
 173
 174         p = strchr(raw_attribute, '=');
 175
 176         LDB_DN_NULL_RETURN(p);
 177
 178         *p = '\0';
 179
 180         at->name = talloc_strdup(at, ldb_dn_trim_string(raw_attribute, " \n"));
 181         LDB_DN_NULL_RETURN(at->name);
 182
 183         p++;
 184
 185         p = ldb_dn_trim_string(p, " \n");
 186
 187         if (*p == '\"') { /* quotes at start means there must be quotes at the end */
 188                 if (p[strlen(p) - 1] != '\"') /* malformed value */
 189                         return NULL;
 190
 191                 p++;
 192                 p[strlen(p) - 1] = '\0';
 193                 at->value = talloc_strdup(at, p);
 194
 195                 return at;
 196         }
 197         /* no quotes means we must unescape the string */
 198         at->value = unescape_string(at, p);
 199         LDB_DN_NULL_RETURN(at->value);
 200
 201         return at;
 202 }
 203
 204 static struct ldb_dn_component *explode_component(void *mem_ctx, char *raw_component)
 205 {
 206         struct ldb_dn_component *dc;
 207         char *p;
 208
 209         dc = talloc(mem_ctx, struct ldb_dn_component);
 210         LDB_DN_NULL_RETURN(dc);
 211
 212         dc->attr_num = 0;
 213         dc->attributes = NULL;
 214
 215         p = raw_component;
 216
 217         /* get the components */
 218         do {
 219                 char *t;
 220
 221                 /* terminate the current attribute and return pointer to the next one */
 222                 t = seek_to_separator(p, "+");
 223                 LDB_DN_NULL_RETURN(t);
 224
 225                 if (*t) { /* here there is a separator */
 226                         *t = '\0'; /*terminate */
 227                         t++; /* a separtor means there's another attribute that follows */
 228                 }
 229
 230                 /* allocate attributes pointer */
 231                 dc->attributes = talloc_realloc(dc, dc->attributes,
 232                                                 struct ldb_dn_attribute *,
 233                                                 dc->attr_num + 1);
 234                 LDB_DN_NULL_RETURN(dc->attributes);
 235
 236                 /* store the exploded attirbute in the main structure */
 237                 dc->attributes[dc->attr_num] = ldb_dn_explode_attribute(dc->attributes, p);
 238                 LDB_DN_NULL_RETURN(dc->attributes[dc->attr_num]);
 239
 240                 dc->attr_num++;
 241
 242                 /* jump to the next attribute if any */
 243                 p = t;
 244
 245         } while(*p);
 246
 247         return dc;
 248 }
 249
 250 /* FIXME: currently consider a dn composed of only case insensitive attributes
 251           this is not correct and need to be fixed soon */
 252 static void ldb_dn_sort_attributes(struct ldb_dn *edn)
 253 {
 254         struct ldb_dn_attribute *at0, *at1;
 255         int i, j, k, l;
 256
 257         for (i = 0; i < edn->comp_num; i++) {
 258                 if (edn->components[i]->attr_num > 1) {
 259
 260                         /* it is very unlikely that there is a multivalued RDN. In that
 261                            unlikely case it is very unlikely you will find more than 2
 262                            values. So the use of bubble sort here seem to be acceptable */
 263                         for (j = 0; (j + 1) < edn->components[i]->attr_num; j++) {
 264                                 for (k = j; k >= 0; k--) {
 265                                         at0 = edn->components[i]->attributes[k];
 266                                         at1 = edn->components[i]->attributes[k + 1];
 267                                         l = ldb_caseless_cmp(at0->name, at1->name);
 268                                         if (l > 0) {
 269                                                 /* already sorted, so no bubbles to move exit inner loop */
 270                                                 break;
 271                                         }
 272                                         if (l == 0) {
 273                                                 if (ldb_caseless_cmp(at0->value, at1->value) >= 0) {
 274                                                         /* already sorted, so no bubbles to move exit inner loop */
 275                                                         break;
 276                                                 }
 277                                         }
 278
 279                                         edn->components[i]->attributes[k] = at1;
 280                                         edn->components[i]->attributes[k + 1] = at0;
 281                                 }
 282                         }
 283                 }
 284         }
 285 }
 286
 287 struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
 288 {
 289         struct ldb_dn *edn; /* the exploded dn */
 290         char *pdn, *p;
 291
 292         /* Allocate a structure to hold the exploded DN */
 293         edn = talloc(mem_ctx, struct ldb_dn);
 294         LDB_DN_NULL_RETURN(edn);
 295
 296         /* Initially there are no components */
 297         edn->comp_num = 0;
 298         edn->components = NULL;
 299
 300         pdn = p = talloc_strdup(edn, dn);
 301         if (!pdn)
 302                 goto error;
 303
 304         /* get the components */
 305         do {
 306                 char *t;
 307
 308                 /* terminate the current component and return pointer to the next one */
 309                 t = seek_to_separator(p, ",;");
 310                 if (t == NULL)
 311                         goto error;
 312
 313                 if (*t) { /* here there is a separator */
 314                         *t = '\0'; /*terminate */
 315                         t++; /* a separtor means there's another component that follows */
 316                 }
 317
 318                 /* allocate space to hold the dn component */
 319                 edn->components = talloc_realloc(edn, edn->components,
 320                                                  struct ldb_dn_component *,
 321                                                  edn->comp_num + 1);
 322                 if (edn->components == NULL)
 323                         goto error;
 324
 325                 /* store the exploded component in the main structure */
 326                 edn->components[edn->comp_num] = explode_component(edn->components, p);
 327                 if (edn->components[edn->comp_num] == NULL)
 328                         goto error;
 329
 330                 edn->comp_num++;
 331
 332                 /* jump to the next component if any */
 333                 p = t;
 334
 335         } while(*p);
 336
 337         /* sort attributes if there's any multivalued component */
 338         ldb_dn_sort_attributes(edn);
 339
 340         talloc_free(pdn);
 341         return edn;
 342
 343 error:
 344         talloc_free(edn);
 345         return NULL;
 346 }
 347
 348 char *ldb_dn_linearize(void *mem_ctx, struct ldb_dn *edn)
 349 {
 350         char *dn, *format, *ename, *evalue;
 351         int i, j;
 352
 353         dn = talloc_strdup(mem_ctx, "");
 354         LDB_DN_NULL_RETURN(dn);
 355
 356         for (i = 0; i < edn->comp_num; i++) {
 357                 if (i != 0) {
 358                         dn = talloc_append_string(mem_ctx, dn, ",");
 359                 }
 360                 for (j = 0; j < edn->components[i]->attr_num; j++) {
 361                         if (i != 0 && j == 0)
 362                                 format = ",%s=%s";
 363                         else if (i == 0 && j == 0)
 364                                 format = "%s=%s";
 365                         else
 366                                 format = "+%s=%s";
 367
 368                         ename = escape_string(mem_ctx, edn->components[i]->attributes[j]->name);
 369                         LDB_DN_NULL_RETURN(ename);
 370
 371                         evalue = escape_string(mem_ctx, edn->components[i]->attributes[j]->value);
 372                         LDB_DN_NULL_RETURN(evalue);
 373
 374                         dn = talloc_asprintf_append(dn, format, ename, evalue);
 375                         LDB_DN_NULL_RETURN(dn);
 376
 377                         talloc_free(ename);
 378                         talloc_free(evalue);
 379                 }
 380         }
 381
 382         return dn;
 383 }
 384
 385 /* FIXME: currently consider a dn composed of only case insensitive attributes
 386           this is not correct and need to be fixed soon */
 387 int ldb_dn_compare(struct ldb_dn *edn0, struct ldb_dn *edn1)
 388 {
 389         struct ldb_dn_attribute *at0, *at1;
 390         int i, j, k;
 391
 392         /* if the number of components doesn't match they differ */
 393         if (edn0->comp_num != edn1->comp_num)
 394                 return (edn1->comp_num - edn0->comp_num);
 395
 396         for (i = 0; i < edn0->comp_num; i++) {
 397
 398                 /* if the number of attributes per component doesn't match they differ */
 399                 if (edn0->components[i]->attr_num != edn1->components[i]->attr_num)
 400                         return (edn1->components[i]->attr_num - edn0->components[i]->attr_num);
 401
 402                 for (j = 0; j < edn0->components[i]->attr_num; j++) {
 403                         at0 = edn0->components[i]->attributes[j];
 404                         at1 = edn1->components[i]->attributes[j];
 405
 406                         /* compare names */
 407                         k = ldb_caseless_cmp(at0->name, at1->name);
 408                         if (k)
 409                                 return k;
 410
 411                         /* names match, compare values */
 412                         k = ldb_caseless_cmp(at0->value, at1->value);
 413                         if (k)
 414                                 return k;
 415                 }
 416         }
 417 }
 418
 419 /*
 420   casefold a dn. We need to uppercase the attribute names, and the
 421   attribute values of case insensitive attributes. We also need to remove
 422   extraneous spaces between elements
 423 */
 424 struct ldb_dn *ldb_dn_casefold(void *mem_ctx, struct ldb_dn *edn, void *user_data,
 425                                 int (* case_fold_attr_fn)(void * user_data, char * attr))
 426 {
 427         struct ldb_dn *cedn;
 428         int i, j;
 429
 430         cedn = talloc(mem_ctx, struct ldb_dn);
 431         LDB_DN_NULL_RETURN(cedn);
 432
 433         cedn->comp_num = edn->comp_num;
 434         cedn->components = talloc_array(cedn, struct ldb_dn_component *, edn->comp_num);
 435         LDB_DN_NULL_RETURN(cedn->components);
 436
 437         for (i = 0; i < edn->comp_num; i++) {
 438                 struct ldb_dn_component *dc;
 439
 440                 dc = talloc(cedn->components, struct ldb_dn_component);
 441                 LDB_DN_NULL_RETURN(dc);
 442
 443                 dc->attr_num = edn->components[i]->attr_num;
 444                 dc->attributes = edn->components[i]->attributes;
 445                 LDB_DN_NULL_RETURN(dc->attributes);
 446
 447                 for (j = 0; j < edn->components[i]->attr_num; j++) {
 448                         struct ldb_dn_attribute *at;
 449
 450                         at = talloc(dc->attributes, struct ldb_dn_attribute);
 451                         LDB_DN_NULL_RETURN(at);
 452
 453                         at->name = ldb_casefold(at, edn->components[i]->attributes[j]->name);
 454                         LDB_DN_NULL_RETURN(at->name);
 455
 456                         if (case_fold_attr_fn(user_data, at->name)) {
 457                                 at->value = ldb_casefold(at, edn->components[i]->attributes[j]->value);
 458                         } else {
 459                                 at->value = talloc_strdup(at, edn->components[i]->attributes[j]->value);
 460                         }
 461                         LDB_DN_NULL_RETURN(at->value);
 462
 463                         dc->attributes[j] = at;
 464                 }
 465
 466                 cedn->components[i] = dc;
 467         }
 468
 469         return cedn;
 470 }
 471