source/lib/ldb/common/ldb_dn.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce 2005
   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 creation and manipulation utility functions
  29  *
  30  *  Description: - explode a dn into it's own basic elements
  31  *                 and put them in a structure (only if necessary)
  32  *               - manipulate ldb_dn structures
  33  *
  34  *  Author: Simo Sorce
  35  */
  36
  37 #include "includes.h"
  38 #include <ctype.h>
  39 #include "ldb/include/includes.h"
  40
  41 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  42
  43 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
  44
  45 /**
  46    internal ldb exploded dn structures
  47 */
  48 struct ldb_dn_component {
  49
  50         char *name;
  51         struct ldb_val value;
  52
  53         char *cf_name;
  54         struct ldb_val cf_value;
  55 };
  56
  57 struct ldb_dn {
  58
  59         struct ldb_context *ldb;
  60
  61         /* Special DNs are always linearized */
  62         bool special;
  63         bool invalid;
  64
  65         bool valid_case;
  66
  67         char *linearized;
  68         char *casefold;
  69
  70         unsigned int comp_num;
  71         struct ldb_dn_component *components;
  72
  73 };
  74
  75 /* strdn may be NULL */
  76 struct ldb_dn *ldb_dn_new(void *mem_ctx, struct ldb_context *ldb, const char *strdn)
  77 {
  78         struct ldb_dn *dn;
  79
  80         if ( (! mem_ctx) || (! ldb)) return NULL;
  81
  82         dn = talloc_zero(mem_ctx, struct ldb_dn);
  83         LDB_DN_NULL_FAILED(dn);
  84
  85         dn->ldb = ldb;
  86
  87         if (strdn) {
  88                 if (strdn[0] == '@') {
  89                         dn->special = true;
  90                 }
  91                 if (strncasecmp(strdn, "<GUID=", 6) == 0) {
  92                         /* this is special DN returned when the
  93                          * exploded_dn control is used */
  94                         dn->special = true;
  95                         /* FIXME: add a GUID string to ldb_dn structure */
  96                 } else if (strncasecmp(strdn, "<SID=", 8) == 0) {
  97                         /* this is special DN returned when the
  98                          * exploded_dn control is used */
  99                         dn->special = true;
 100                         /* FIXME: add a SID string to ldb_dn structure */
 101                 } else if (strncasecmp(strdn, "<WKGUID=", 8) == 0) {
 102                         /* this is special DN returned when the
 103                          * exploded_dn control is used */
 104                         dn->special = true;
 105                         /* FIXME: add a WKGUID string to ldb_dn structure */
 106                 }
 107                 dn->linearized = talloc_strdup(dn, strdn);
 108         } else {
 109                 dn->linearized = talloc_strdup(dn, "");
 110         }
 111         LDB_DN_NULL_FAILED(dn->linearized);
 112
 113         return dn;
 114
 115 failed:
 116         talloc_free(dn);
 117         return NULL;
 118 }
 119
 120 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx, struct ldb_context *ldb, const char *new_fmt, ...)
 121 {
 122         struct ldb_dn *dn;
 123         char *strdn;
 124         va_list ap;
 125
 126         if ( (! mem_ctx) || (! ldb)) return NULL;
 127
 128         dn = talloc_zero(mem_ctx, struct ldb_dn);
 129         LDB_DN_NULL_FAILED(dn);
 130
 131         dn->ldb = ldb;
 132
 133         va_start(ap, new_fmt);
 134         strdn = talloc_vasprintf(dn, new_fmt, ap);
 135         va_end(ap);
 136         LDB_DN_NULL_FAILED(strdn);
 137
 138         if (strdn[0] == '@') {
 139                 dn->special = true;
 140         }
 141         if (strncasecmp(strdn, "<GUID=", 6) == 0) {
 142                 /* this is special DN returned when the
 143                  * exploded_dn control is used */
 144                 dn->special = true;
 145                 /* FIXME: add a GUID string to ldb_dn structure */
 146         }
 147         dn->linearized = strdn;
 148
 149         return dn;
 150
 151 failed:
 152         talloc_free(dn);
 153         return NULL;
 154 }
 155
 156 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 157 {
 158         const char *p, *s;
 159         char *d;
 160         int l;
 161
 162         p = s = src;
 163         d = dst;
 164
 165         while (p - src < len) {
 166
 167                 p += strcspn(p, ",=\n+<>#;\\\"");
 168
 169                 if (p - src == len) /* found no escapable chars */
 170                         break;
 171
 172                 memcpy(d, s, p - s); /* copy the part of the string before the stop */
 173                 d += (p - s); /* move to current position */
 174
 175                 if (*p) { /* it is a normal escapable character */
 176                         *d++ = '\\';
 177                         *d++ = *p++;
 178                 } else { /* we have a zero byte in the string */
 179                         strncpy(d, "\00", 3); /* escape the zero */
 180                         d += 3;
 181                         p++; /* skip the zero */
 182                 }
 183                 s = p; /* move forward */
 184         }
 185
 186         /* copy the last part (with zero) and return */
 187         l = len - (s - src);
 188         memcpy(d, s, l + 1);
 189
 190         /* return the length of the resulting string */
 191         return (l + (d - dst));
 192 }
 193
 194 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 195 {
 196         char *dst;
 197
 198         if (!value.length)
 199                 return NULL;
 200
 201         /* allocate destination string, it will be at most 3 times the source */
 202         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 203         if ( ! dst) {
 204                 talloc_free(dst);
 205                 return NULL;
 206         }
 207
 208         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 209
 210         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
 211
 212         return dst;
 213 }
 214
 215 /*
 216   explode a DN string into a ldb_dn structure
 217   based on RFC4514 except that we don't support multiple valued RDNs
 218 */
 219 static bool ldb_dn_explode(struct ldb_dn *dn)
 220 {
 221         char *p, *data, *d, *dt, *t;
 222         bool trim = false;
 223         bool in_attr = false;
 224         bool in_value = false;
 225         bool in_quote = false;
 226         bool is_oid = false;
 227         bool escape = false;
 228         unsigned x;
 229         int l;
 230
 231         if ( ! dn || dn->invalid) return false;
 232
 233         if (dn->components) {
 234                 return true;
 235         }
 236
 237         if ( ! dn->linearized) {
 238                 return false;
 239         }
 240
 241         /* Empty DNs */
 242         if (dn->linearized[0] == '\0') {
 243                 return true;
 244         }
 245
 246         /* Special DNs case */
 247         if (dn->special) {
 248                 return true;
 249         }
 250
 251         /* make sure we free this if alloced previously before replacing */
 252         talloc_free(dn->components);
 253
 254         /* in the common case we have 3 or more components */
 255         /* make sure all components are zeroed, other functions depend on this */
 256         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 257         if ( ! dn->components) {
 258                 return false;
 259         }
 260         dn->comp_num = 0;
 261
 262         /* Components data space is allocated here once */
 263         data = talloc_array(dn->components, char, strlen(dn->linearized) + 1);
 264         if (!data) {
 265                 return false;
 266         }
 267
 268         p = dn->linearized;
 269         in_attr = true;
 270         trim = true;
 271         t = NULL;
 272         d = dt = data;
 273
 274         while (*p) {
 275
 276                 if (in_attr) {
 277                         if (trim) {
 278                                 if (*p == ' ') {
 279                                         p++;
 280                                         continue;
 281                                 }
 282
 283                                 /* first char */
 284                                 trim = false;
 285
 286                                 if (isdigit(*p)) {
 287                                         is_oid = true;
 288                                 } else
 289                                 if ( ! isalpha(*p)) {
 290                                         /* not a digit nor an alpha, invalid attribute name */
 291                                         dn->invalid = true;
 292                                         goto failed;
 293                                 }
 294
 295                                 *d++ = *p++;
 296                                 continue;
 297                         }
 298
 299                         if (*p == ' ') {
 300                                 p++;
 301                                 /* valid only if we are at the end */
 302                                 trim = true;
 303                                 continue;
 304                         }
 305
 306                         if (trim && (*p != '=')) {
 307                                 /* spaces/tabs are not allowed in attribute names */
 308                                 dn->invalid = true;
 309                                 goto failed;
 310                         }
 311
 312                         if (*p == '=') {
 313                                 /* attribute terminated */
 314                                 in_attr = false;
 315                                 in_value = true;
 316                                 trim = true;
 317                                 l = 0;
 318
 319                                 *d++ = '\0';
 320                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 321                                 if ( ! dn->components[dn->comp_num].name) {
 322                                         /* ouch */
 323                                         goto failed;
 324                                 }
 325
 326                                 dt = d;
 327
 328                                 p++;
 329                                 continue;
 330                         }
 331
 332                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 333                                 /* not a digit nor a dot, invalid attribute oid */
 334                                 dn->invalid = true;
 335                                 goto failed;
 336                         } else
 337                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 338                                 /* not ALPHA, DIGIT or HYPHEN */
 339                                 dn->invalid = true;
 340                                 goto failed;
 341                         }
 342
 343                         *d++ = *p++;
 344                         continue;
 345                 }
 346
 347                 if (in_value) {
 348                         if (in_quote) {
 349                                 if (*p == '\"') {
 350                                         if (p[-1] != '\\') {
 351                                                 p++;
 352                                                 in_quote = false;
 353                                                 continue;
 354                                         }
 355                                 }
 356                                 *d++ = *p++;
 357                                 l++;
 358                                 continue;
 359                         }
 360
 361                         if (trim) {
 362                                 if (*p == ' ') {
 363                                         p++;
 364                                         continue;
 365                                 }
 366
 367                                 /* first char */
 368                                 trim = false;
 369
 370                                 if (*p == '\"') {
 371                                         in_quote = true;
 372                                         p++;
 373                                         continue;
 374                                 }
 375                         }
 376
 377                         switch (*p) {
 378
 379                         /* TODO: support ber encoded values
 380                         case '#':
 381                         */
 382
 383                         case ',':
 384                                 if (escape) {
 385                                         *d++ = *p++;
 386                                         l++;
 387                                         escape = false;
 388                                         continue;
 389                                 }
 390                                 /* ok found value terminator */
 391
 392                                 if ( t ) {
 393                                         /* trim back */
 394                                         d -= (p - t);
 395                                         l -= (p - t);
 396                                 }
 397
 398                                 in_attr = true;
 399                                 in_value = false;
 400                                 trim = true;
 401
 402                                 p++;
 403                                 *d++ = '\0';
 404                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 405                                 dn->components[dn->comp_num].value.length = l;
 406                                 if ( ! dn->components[dn->comp_num].value.data) {
 407                                         /* ouch ! */
 408                                         goto failed;
 409                                 }
 410
 411                                 dt = d;
 412
 413                                 dn->comp_num++;
 414                                 if (dn->comp_num > 2) {
 415                                         dn->components = talloc_realloc(dn,
 416                                                                         dn->components,
 417                                                                         struct ldb_dn_component,
 418                                                                         dn->comp_num + 1);
 419                                         if ( ! dn->components) {
 420                                                 /* ouch ! */
 421                                                 goto failed;
 422                                         }
 423                                         /* make sure all components are zeroed, other functions depend on this */
 424                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 425                                 }
 426
 427                                 continue;
 428
 429                         case '=':
 430                         case '\n':
 431                         case '+':
 432                         case '<':
 433                         case '>':
 434                         case '#':
 435                         case ';':
 436                         case '\"':
 437                                 /* a string with not escaped specials is invalid (tested) */
 438                                 if ( ! escape) {
 439                                         dn->invalid = true;
 440                                         goto failed;
 441                                 }
 442                                 escape = false;
 443
 444                                 *d++ = *p++;
 445                                 l++;
 446
 447                                 if ( t ) t = NULL;
 448                                 break;
 449
 450                         case '\\':
 451                                 if ( ! escape) {
 452                                         escape = true;
 453                                         p++;
 454                                         continue;
 455                                 }
 456                                 escape = false;
 457
 458                                 *d++ = *p++;
 459                                 l++;
 460
 461                                 if ( t ) t = NULL;
 462                                 break;
 463
 464                         default:
 465                                 if (escape) {
 466                                         if (sscanf(p, "%02x", &x) != 1) {
 467                                                 /* invalid escaping sequence */
 468                                                 dn->invalid = true;
 469                                                 goto failed;
 470                                         }
 471                                         escape = false;
 472
 473                                         p += 2;
 474                                         *d++ = (unsigned char)x;
 475                                         l++;
 476
 477                                         if ( t ) t = NULL;
 478                                         break;
 479                                 }
 480
 481                                 if (*p == ' ') {
 482                                         if ( ! t) t = p;
 483                                 } else {
 484                                         if ( t ) t = NULL;
 485                                 }
 486
 487                                 *d++ = *p++;
 488                                 l++;
 489
 490                                 break;
 491                         }
 492
 493                 }
 494         }
 495
 496         if (in_attr || in_quote) {
 497                 /* invalid dn */
 498                 dn->invalid = true;
 499                 goto failed;
 500         }
 501
 502         /* save last element */
 503         if ( t ) {
 504                 /* trim back */
 505                 d -= (p - t);
 506                 l -= (p - t);
 507         }
 508
 509         *d++ = '\0';
 510         dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 511         dn->components[dn->comp_num].value.length = l;
 512
 513         if ( ! dn->components[dn->comp_num].value.data) {
 514                 /* ouch */
 515                 goto failed;
 516         }
 517
 518         dn->comp_num++;
 519
 520         talloc_free(data);
 521         return true;
 522
 523 failed:
 524         dn->comp_num = 0;
 525         talloc_free(dn->components);
 526         return false;
 527 }
 528
 529 bool ldb_dn_validate(struct ldb_dn *dn)
 530 {
 531         return ldb_dn_explode(dn);
 532 }
 533
 534 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 535 {
 536         int i, len;
 537         char *d, *n;
 538
 539         if ( ! dn || ( dn->invalid)) return NULL;
 540
 541         if (dn->linearized) return dn->linearized;
 542
 543         if ( ! dn->components) {
 544                 dn->invalid = true;
 545                 return NULL;
 546         }
 547
 548         if (dn->comp_num == 0) {
 549                 dn->linearized = talloc_strdup(dn, "");
 550                 if ( ! dn->linearized) return NULL;
 551                 return dn->linearized;
 552         }
 553
 554         /* calculate maximum possible length of DN */
 555         for (len = 0, i = 0; i < dn->comp_num; i++) {
 556                 len += strlen(dn->components[i].name); /* name len */
 557                 len += (dn->components[i].value.length * 3); /* max escaped data len */
 558                 len += 2; /* '=' and ',' */
 559         }
 560         dn->linearized = talloc_array(dn, char, len);
 561         if ( ! dn->linearized) return NULL;
 562
 563         d = dn->linearized;
 564
 565         for (i = 0; i < dn->comp_num; i++) {
 566
 567                 /* copy the name */
 568                 n = dn->components[i].name;
 569                 while (*n) *d++ = *n++;
 570
 571                 *d++ = '=';
 572
 573                 /* and the value */
 574                 d += ldb_dn_escape_internal( d,
 575                                 (char *)dn->components[i].value.data,
 576                                 dn->components[i].value.length);
 577                 *d++ = ',';
 578         }
 579
 580         *(--d) = '\0';
 581
 582         /* don't waste more memory than necessary */
 583         dn->linearized = talloc_realloc(dn, dn->linearized, char, (d - dn->linearized + 1));
 584
 585         return dn->linearized;
 586 }
 587
 588 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
 589 {
 590         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 591 }
 592
 593 /*
 594   casefold a dn. We need to casefold the attribute names, and canonicalize
 595   attribute values of case insensitive attributes.
 596 */
 597
 598 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 599 {
 600         int i, ret;
 601
 602         if ( ! dn || dn->invalid) return false;
 603
 604         if (dn->valid_case) return true;
 605
 606         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
 607                 return false;
 608         }
 609
 610         for (i = 0; i < dn->comp_num; i++) {
 611                 const struct ldb_attrib_handler *h;
 612
 613                 dn->components[i].cf_name = ldb_attr_casefold(dn->components, dn->components[i].name);
 614                 if (!dn->components[i].cf_name) {
 615                         goto failed;
 616                 }
 617
 618                 h = ldb_attrib_handler(dn->ldb, dn->components[i].cf_name);
 619                 ret = h->canonicalise_fn(dn->ldb, dn->components,
 620                                          &(dn->components[i].value),
 621                                          &(dn->components[i].cf_value));
 622                 if (ret != 0) {
 623                         goto failed;
 624                 }
 625         }
 626
 627         dn->valid_case = true;
 628
 629         return true;
 630
 631 failed:
 632         for (i = 0; i < dn->comp_num; i++) {
 633                 LDB_FREE(dn->components[i].cf_name);
 634                 LDB_FREE(dn->components[i].cf_value.data);
 635         }
 636         return false;
 637 }
 638
 639 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 640 {
 641         int i, len;
 642         char *d, *n;
 643
 644         if (dn->casefold) return dn->casefold;
 645
 646         if (dn->special) {
 647                 dn->casefold = talloc_strdup(dn, dn->linearized);
 648                 if (!dn->casefold) return NULL;
 649                 dn->valid_case = true;
 650                 return dn->casefold;
 651         }
 652
 653         if ( ! ldb_dn_casefold_internal(dn)) {
 654                 return NULL;
 655         }
 656
 657         if (dn->comp_num == 0) {
 658                 if (dn->linearized && dn->linearized[0] == '\0') {
 659                         /* hmm a NULL dn, should we faild casefolding ? */
 660                         dn->casefold = talloc_strdup(dn, "");
 661                         return dn->casefold;
 662                 }
 663                 /* A DN must be NULL, special, or have components */
 664                 dn->invalid = true;
 665                 return NULL;
 666         }
 667
 668         /* calculate maximum possible length of DN */
 669         for (len = 0, i = 0; i < dn->comp_num; i++) {
 670                 len += strlen(dn->components[i].cf_name); /* name len */
 671                 len += (dn->components[i].cf_value.length * 3); /* max escaped data len */
 672                 len += 2; /* '=' and ',' */
 673         }
 674         dn->casefold = talloc_array(dn, char, len);
 675         if ( ! dn->casefold) return NULL;
 676
 677         d = dn->casefold;
 678
 679         for (i = 0; i < dn->comp_num; i++) {
 680
 681                 /* copy the name */
 682                 n = dn->components[i].cf_name;
 683                 while (*n) *d++ = *n++;
 684
 685                 *d++ = '=';
 686
 687                 /* and the value */
 688                 d += ldb_dn_escape_internal( d,
 689                                 (char *)dn->components[i].cf_value.data,
 690                                 dn->components[i].cf_value.length);
 691                 *d++ = ',';
 692         }
 693         *(--d) = '\0';
 694
 695         /* don't waste more memory than necessary */
 696         dn->casefold = talloc_realloc(dn, dn->casefold, char, strlen(dn->casefold) + 1);
 697
 698         return dn->casefold;
 699 }
 700
 701 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
 702 {
 703         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
 704 }
 705
 706 /* Determine if dn is below base, in the ldap tree.  Used for
 707  * evaluating a subtree search.
 708  * 0 if they match, otherwise non-zero
 709  */
 710
 711 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
 712 {
 713         int ret;
 714         int n_base, n_dn;
 715
 716         if ( ! base || base->invalid) return 1;
 717         if ( ! dn || dn->invalid) return -1;
 718
 719         if (( ! base->valid_case) || ( ! dn->valid_case)) {
 720                 if (base->linearized && dn->linearized) {
 721                         /* try with a normal compare first, if we are lucky
 722                          * we will avoid exploding and casfolding */
 723                         int dif;
 724                         dif = strlen(dn->linearized) - strlen(base->linearized);
 725                         if (dif < 0) return dif;
 726                         if (strcmp(base->linearized, &dn->linearized[dif]) == 0) return 0;
 727                 }
 728
 729                 if ( ! ldb_dn_casefold_internal(base)) {
 730                         return 1;
 731                 }
 732
 733                 if ( ! ldb_dn_casefold_internal(dn)) {
 734                         return -1;
 735                 }
 736
 737         }
 738
 739         /* if base has more components,
 740          * they don't have the same base */
 741         if (base->comp_num > dn->comp_num) {
 742                 return (dn->comp_num - base->comp_num);
 743         }
 744
 745         if (dn->comp_num == 0) {
 746                 if (dn->special && base->special) {
 747                         return strcmp(base->linearized, dn->linearized);
 748                 } else if (dn->special) {
 749                         return -1;
 750                 } else if (base->special) {
 751                         return 1;
 752                 } else {
 753                         return 0;
 754                 }
 755         }
 756
 757         n_base = base->comp_num - 1;
 758         n_dn = dn->comp_num - 1;
 759
 760         while (n_base >= 0) {
 761                 /* compare attr names */
 762                 ret = strcmp(base->components[n_base].cf_name, dn->components[n_dn].cf_name);
 763                 if (ret != 0) return ret;
 764
 765                 /* compare attr.cf_value. */
 766                 if (base->components[n_base].cf_value.length != dn->components[n_dn].cf_value.length) {
 767                         return base->components[n_base].cf_value.length - dn->components[n_dn].cf_value.length;
 768                 }
 769                 ret = strcmp((char *)base->components[n_base].cf_value.data, (char *)dn->components[n_dn].cf_value.data);
 770                 if (ret != 0) return ret;
 771
 772                 n_base--;
 773                 n_dn--;
 774         }
 775
 776         return 0;
 777 }
 778
 779 /* compare DNs using casefolding compare functions.
 780
 781    If they match, then return 0
 782  */
 783
 784 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 785 {
 786         int i, ret;
 787
 788         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) return -1;
 789
 790         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
 791                 if (dn0->linearized && dn1->linearized) {
 792                         /* try with a normal compare first, if we are lucky
 793                          * we will avoid exploding and casfolding */
 794                         if (strcmp(dn0->linearized, dn1->linearized) == 0) return 0;
 795                 }
 796
 797                 if ( ! ldb_dn_casefold_internal(dn0)) {
 798                         return 1;
 799                 }
 800
 801                 if ( ! ldb_dn_casefold_internal(dn1)) {
 802                         return -1;
 803                 }
 804
 805         }
 806
 807         if (dn0->comp_num != dn1->comp_num) {
 808                 return (dn1->comp_num - dn0->comp_num);
 809         }
 810
 811         if (dn0->comp_num == 0) {
 812                 if (dn0->special && dn1->special) {
 813                         return strcmp(dn0->linearized, dn1->linearized);
 814                 } else if (dn0->special) {
 815                         return 1;
 816                 } else if (dn1->special) {
 817                         return -1;
 818                 } else {
 819                         return 0;
 820                 }
 821         }
 822
 823         for (i = 0; i < dn0->comp_num; i++) {
 824                 /* compare attr names */
 825                 ret = strcmp(dn0->components[i].cf_name, dn1->components[i].cf_name);
 826                 if (ret != 0) return ret;
 827
 828                 /* compare attr.cf_value. */
 829                 if (dn0->components[i].cf_value.length != dn1->components[i].cf_value.length) {
 830                         return dn0->components[i].cf_value.length - dn1->components[i].cf_value.length;
 831                 }
 832                 ret = strcmp((char *)dn0->components[i].cf_value.data, (char *)dn1->components[i].cf_value.data);
 833                 if (ret != 0) return ret;
 834         }
 835
 836         return 0;
 837 }
 838
 839 static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
 840 {
 841         struct ldb_dn_component dst;
 842
 843         memset(&dst, 0, sizeof(dst));
 844
 845         if (src == NULL) {
 846                 return dst;
 847         }
 848
 849         dst.value = ldb_val_dup(mem_ctx, &(src->value));
 850         if (dst.value.data == NULL) {
 851                 return dst;
 852         }
 853
 854         dst.name = talloc_strdup(mem_ctx, src->name);
 855         if (dst.name == NULL) {
 856                 LDB_FREE(dst.value.data);
 857                 return dst;
 858         }
 859
 860         if (src->cf_value.data) {
 861                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
 862                 if (dst.cf_value.data == NULL) {
 863                         LDB_FREE(dst.value.data);
 864                         LDB_FREE(dst.name);
 865                         return dst;
 866                 }
 867
 868                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
 869                 if (dst.cf_name == NULL) {
 870                         LDB_FREE(dst.cf_name);
 871                         LDB_FREE(dst.value.data);
 872                         LDB_FREE(dst.name);
 873                         return dst;
 874                 }
 875         } else {
 876                 dst.cf_value.data = NULL;
 877                 dst.cf_name = NULL;
 878         }
 879
 880         return dst;
 881 }
 882
 883 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
 884 {
 885         struct ldb_dn *new_dn;
 886
 887         if (!dn || dn->invalid) {
 888                 return NULL;
 889         }
 890
 891         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
 892         if ( !new_dn) {
 893                 return NULL;
 894         }
 895
 896         *new_dn = *dn;
 897
 898         if (dn->components) {
 899                 int i;
 900
 901                 new_dn->components = talloc_zero_array(new_dn, struct ldb_dn_component, dn->comp_num);
 902                 if ( ! new_dn->components) {
 903                         talloc_free(new_dn);
 904                         return NULL;
 905                 }
 906
 907                 for (i = 0; i < dn->comp_num; i++) {
 908                         new_dn->components[i] = ldb_dn_copy_component(new_dn->components, &dn->components[i]);
 909                         if ( ! new_dn->components[i].value.data) {
 910                                 talloc_free(new_dn);
 911                                 return NULL;
 912                         }
 913                 }
 914         }
 915
 916         if (dn->casefold) {
 917                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
 918                 if ( ! new_dn->casefold) {
 919                         talloc_free(new_dn);
 920                         return NULL;
 921                 }
 922         }
 923
 924         if (dn->linearized) {
 925                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
 926                 if ( ! new_dn->linearized) {
 927                         talloc_free(new_dn);
 928                         return NULL;
 929                 }
 930         }
 931
 932         return new_dn;
 933 }
 934
 935 /* modify the given dn by adding a base.
 936  *
 937  * return true if successful and false if not
 938  * if false is returned the dn may be marked invalid
 939  */
 940 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
 941 {
 942         const char *s;
 943         char *t;
 944
 945         if ( !base || base->invalid || !dn || dn->invalid) {
 946                 return false;
 947         }
 948
 949         if (dn->components) {
 950                 int i;
 951
 952                 if ( ! ldb_dn_validate(base)) {
 953                         return false;
 954                 }
 955
 956                 s = NULL;
 957                 if (dn->valid_case) {
 958                         if ( ! (s = ldb_dn_get_casefold(base))) {
 959                                 return false;
 960                         }
 961                 }
 962
 963                 dn->components = talloc_realloc(dn,
 964                                                 dn->components,
 965                                                 struct ldb_dn_component,
 966                                                 dn->comp_num + base->comp_num);
 967                 if ( ! dn->components) {
 968                         dn->invalid = true;
 969                         return false;
 970                 }
 971
 972                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
 973                         dn->components[dn->comp_num] = ldb_dn_copy_component(dn->components, &base->components[i]);
 974                         if (dn->components[dn->comp_num].value.data == NULL) {
 975                                 dn->invalid = true;
 976                                 return false;
 977                         }
 978                 }
 979
 980                 if (dn->casefold && s) {
 981                         t = talloc_asprintf(dn, "%s,%s", dn->casefold, s);
 982                         LDB_FREE(dn->casefold);
 983                         dn->casefold = t;
 984                 }
 985         }
 986
 987         if (dn->linearized) {
 988
 989                 s = ldb_dn_get_linearized(base);
 990                 if ( ! s) {
 991                         return false;
 992                 }
 993
 994                 t = talloc_asprintf(dn, "%s,%s", dn->linearized, s);
 995                 if ( ! t) {
 996                         dn->invalid = true;
 997                         return false;
 998                 }
 999                 LDB_FREE(dn->linearized);
1000                 dn->linearized = t;
1001         }
1002
1003         return true;
1004 }
1005
1006 /* modify the given dn by adding a base.
1007  *
1008  * return true if successful and false if not
1009  * if false is returned the dn may be marked invalid
1010  */
1011 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1012 {
1013         struct ldb_dn *base;
1014         char *base_str;
1015         va_list ap;
1016         bool ret;
1017
1018         if ( !dn || dn->invalid) {
1019                 return false;
1020         }
1021
1022         va_start(ap, base_fmt);
1023         base_str = talloc_vasprintf(dn, base_fmt, ap);
1024         va_end(ap);
1025
1026         if (base_str == NULL) {
1027                 return false;
1028         }
1029
1030         base = ldb_dn_new(base_str, dn->ldb, base_str);
1031
1032         ret = ldb_dn_add_base(dn, base);
1033
1034         talloc_free(base_str);
1035
1036         return ret;
1037 }
1038
1039 /* modify the given dn by adding children elements.
1040  *
1041  * return true if successful and false if not
1042  * if false is returned the dn may be marked invalid
1043  */
1044 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1045 {
1046         const char *s;
1047         char *t;
1048
1049         if ( !child || child->invalid || !dn || dn->invalid) {
1050                 return false;
1051         }
1052
1053         if (dn->components) {
1054                 int n, i, j;
1055
1056                 if ( ! ldb_dn_validate(child)) {
1057                         return false;
1058                 }
1059
1060                 s = NULL;
1061                 if (dn->valid_case) {
1062                         if ( ! (s = ldb_dn_get_casefold(child))) {
1063                                 return false;
1064                         }
1065                 }
1066
1067                 n = dn->comp_num + child->comp_num;
1068
1069                 dn->components = talloc_realloc(dn,
1070                                                 dn->components,
1071                                                 struct ldb_dn_component,
1072                                                 n);
1073                 if ( ! dn->components) {
1074                         dn->invalid = true;
1075                         return false;
1076                 }
1077
1078                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1079                         dn->components[j] = dn->components[i];
1080                 }
1081
1082                 for (i = 0; i < child->comp_num; i++) {
1083                         dn->components[i] = ldb_dn_copy_component(dn->components, &child->components[i]);
1084                         if (dn->components[i].value.data == NULL) {
1085                                 dn->invalid = true;
1086                                 return false;
1087                         }
1088                 }
1089
1090                 dn->comp_num = n;
1091
1092                 if (dn->casefold && s) {
1093                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1094                         LDB_FREE(dn->casefold);
1095                         dn->casefold = t;
1096                 }
1097         }
1098
1099         if (dn->linearized) {
1100
1101                 s = ldb_dn_get_linearized(child);
1102                 if ( ! s) {
1103                         return false;
1104                 }
1105
1106                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1107                 if ( ! t) {
1108                         dn->invalid = true;
1109                         return false;
1110                 }
1111                 LDB_FREE(dn->linearized);
1112                 dn->linearized = t;
1113         }
1114
1115         return true;
1116 }
1117
1118 /* modify the given dn by adding children elements.
1119  *
1120  * return true if successful and false if not
1121  * if false is returned the dn may be marked invalid
1122  */
1123 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1124 {
1125         struct ldb_dn *child;
1126         char *child_str;
1127         va_list ap;
1128         bool ret;
1129
1130         if ( !dn || dn->invalid) {
1131                 return false;
1132         }
1133
1134         va_start(ap, child_fmt);
1135         child_str = talloc_vasprintf(dn, child_fmt, ap);
1136         va_end(ap);
1137
1138         if (child_str == NULL) {
1139                 return false;
1140         }
1141
1142         child = ldb_dn_new(child_str, dn->ldb, child_str);
1143
1144         ret = ldb_dn_add_child(dn, child);
1145
1146         talloc_free(child_str);
1147
1148         return ret;
1149 }
1150
1151 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1152 {
1153         int i;
1154
1155         if ( ! ldb_dn_validate(dn)) {
1156                 return false;
1157         }
1158
1159         if (dn->comp_num < num) {
1160                 return false;
1161         }
1162
1163         /* free components */
1164         for (i = num; i > 0; i--) {
1165                 LDB_FREE(dn->components[dn->comp_num - i].name);
1166                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1167                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1168                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1169         }
1170
1171         dn->comp_num -= num;
1172
1173         if (dn->valid_case) {
1174                 for (i = 0; i < dn->comp_num; i++) {
1175                         LDB_FREE(dn->components[i].cf_name);
1176                         LDB_FREE(dn->components[i].cf_value.data);
1177                 }
1178                 dn->valid_case = false;
1179         }
1180
1181         LDB_FREE(dn->casefold);
1182         LDB_FREE(dn->linearized);
1183
1184         return true;
1185 }
1186
1187 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1188 {
1189         int i, j;
1190
1191         if ( ! ldb_dn_validate(dn)) {
1192                 return false;
1193         }
1194
1195         if (dn->comp_num < num) {
1196                 return false;
1197         }
1198
1199         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1200                 if (i < num) {
1201                         LDB_FREE(dn->components[i].name);
1202                         LDB_FREE(dn->components[i].value.data);
1203                         LDB_FREE(dn->components[i].cf_name);
1204                         LDB_FREE(dn->components[i].cf_value.data);
1205                 }
1206                 dn->components[i] = dn->components[j];
1207         }
1208
1209         dn->comp_num -= num;
1210
1211         if (dn->valid_case) {
1212                 for (i = 0; i < dn->comp_num; i++) {
1213                         LDB_FREE(dn->components[i].cf_name);
1214                         LDB_FREE(dn->components[i].cf_value.data);
1215                 }
1216                 dn->valid_case = false;
1217         }
1218
1219         LDB_FREE(dn->casefold);
1220         LDB_FREE(dn->linearized);
1221
1222         return true;
1223 }
1224
1225 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1226 {
1227         struct ldb_dn *new_dn;
1228
1229         new_dn = ldb_dn_copy(mem_ctx, dn);
1230         if ( !new_dn ) {
1231                 return NULL;
1232         }
1233
1234         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1235                 talloc_free(new_dn);
1236                 return NULL;
1237         }
1238
1239         return new_dn;
1240 }
1241
1242 /* Create a 'canonical name' string from a DN:
1243
1244    ie dc=samba,dc=org -> samba.org/
1245       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1246
1247    There are two formats, the EX format has the last / replaced with a newline (\n).
1248
1249 */
1250 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1251         int i;
1252         TALLOC_CTX *tmpctx;
1253         char *cracked = NULL;
1254
1255         if ( ! ldb_dn_validate(dn)) {
1256                 return NULL;
1257         }
1258
1259         tmpctx = talloc_new(mem_ctx);
1260
1261         /* Walk backwards down the DN, grabbing 'dc' components at first */
1262         for (i = dn->comp_num - 1 ; i >= 0; i--) {
1263                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1264                         break;
1265                 }
1266                 if (cracked) {
1267                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1268                                                   ldb_dn_escape_value(tmpctx, dn->components[i].value),
1269                                                   cracked);
1270                 } else {
1271                         cracked = ldb_dn_escape_value(tmpctx, dn->components[i].value);
1272                 }
1273                 if (!cracked) {
1274                         goto done;
1275                 }
1276         }
1277
1278         /* Only domain components?  Finish here */
1279         if (i < 0) {
1280                 if (ex_format) {
1281                         cracked = talloc_append_string(tmpctx, cracked, "\n");
1282                 } else {
1283                         cracked = talloc_append_string(tmpctx, cracked, "/");
1284                 }
1285                 talloc_steal(mem_ctx, cracked);
1286                 goto done;
1287         }
1288
1289         /* Now walk backwards appending remaining components */
1290         for (; i > 0; i--) {
1291                 cracked = talloc_asprintf_append(cracked, "/%s",
1292                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1293                 if (!cracked) {
1294                         goto done;
1295                 }
1296         }
1297
1298         /* Last one, possibly a newline for the 'ex' format */
1299         if (ex_format) {
1300                 cracked = talloc_asprintf_append(cracked, "\n%s",
1301                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1302         } else {
1303                 cracked = talloc_asprintf_append(cracked, "/%s",
1304                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1305         }
1306
1307         talloc_steal(mem_ctx, cracked);
1308 done:
1309         talloc_free(tmpctx);
1310         return cracked;
1311 }
1312
1313 /* Wrapper functions for the above, for the two different string formats */
1314 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1315         return ldb_dn_canonical(mem_ctx, dn, 0);
1316
1317 }
1318
1319 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1320         return ldb_dn_canonical(mem_ctx, dn, 1);
1321 }
1322
1323 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1324 {
1325         if ( ! ldb_dn_validate(dn)) {
1326                 return -1;
1327         }
1328         return dn->comp_num;
1329 }
1330
1331 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1332 {
1333         if ( ! ldb_dn_validate(dn)) {
1334                 return NULL;
1335         }
1336         if (num >= dn->comp_num) return NULL;
1337         return dn->components[num].name;
1338 }
1339
1340 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn, unsigned int num)
1341 {
1342         if ( ! ldb_dn_validate(dn)) {
1343                 return NULL;
1344         }
1345         if (num >= dn->comp_num) return NULL;
1346         return &dn->components[num].value;
1347 }
1348
1349 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1350 {
1351         if ( ! ldb_dn_validate(dn)) {
1352                 return NULL;
1353         }
1354         if (dn->comp_num == 0) return NULL;
1355         return dn->components[0].name;
1356 }
1357
1358 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1359 {
1360         if ( ! ldb_dn_validate(dn)) {
1361                 return NULL;
1362         }
1363         if (dn->comp_num == 0) return NULL;
1364         return &dn->components[0].value;
1365 }
1366
1367 int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const struct ldb_val val)
1368 {
1369         char *n;
1370         struct ldb_val v;
1371
1372         if ( ! ldb_dn_validate(dn)) {
1373                 return LDB_ERR_OTHER;
1374         }
1375
1376         if (num >= dn->comp_num) {
1377                 return LDB_ERR_OTHER;
1378         }
1379
1380         n = talloc_strdup(dn, name);
1381         if ( ! n) {
1382                 return LDB_ERR_OTHER;
1383         }
1384
1385         v.length = val.length;
1386         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1387         if ( ! v.data) {
1388                 talloc_free(n);
1389                 return LDB_ERR_OTHER;
1390         }
1391
1392         talloc_free(dn->components[num].name);
1393         talloc_free(dn->components[num].value.data);
1394         dn->components[num].name = n;
1395         dn->components[num].value = v;
1396
1397         if (dn->valid_case) {
1398                 int i;
1399                 for (i = 0; i < dn->comp_num; i++) {
1400                         LDB_FREE(dn->components[i].cf_name);
1401                         LDB_FREE(dn->components[i].cf_value.data);
1402                 }
1403                 dn->valid_case = false;
1404         }
1405         LDB_FREE(dn->casefold);
1406
1407         return LDB_SUCCESS;
1408 }
1409
1410 bool ldb_dn_is_valid(struct ldb_dn *dn)
1411 {
1412         if ( ! dn) return false;
1413         return ! dn->invalid;
1414 }
1415
1416 bool ldb_dn_is_special(struct ldb_dn *dn)
1417 {
1418         if ( ! dn || dn->invalid) return false;
1419         return dn->special;
1420 }
1421
1422 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
1423 {
1424         if ( ! dn || dn->invalid) return false;
1425         return ! strcmp(dn->linearized, check);
1426 }
1427
1428 bool ldb_dn_is_null(struct ldb_dn *dn)
1429 {
1430         if ( ! dn || dn->invalid) return false;
1431         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
1432         return false;
1433 }