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 3 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, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb dn creation and manipulation utility functions
  28  *
  29  *  Description: - explode a dn into it's own basic elements
  30  *                 and put them in a structure (only if necessary)
  31  *               - manipulate ldb_dn structures
  32  *
  33  *  Author: Simo Sorce
  34  */
  35
  36 #include "ldb_private.h"
  37 #include <ctype.h>
  38
  39 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  40
  41 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
  42
  43 /**
  44    internal ldb exploded dn structures
  45 */
  46 struct ldb_dn_component {
  47
  48         char *name;
  49         struct ldb_val value;
  50
  51         char *cf_name;
  52         struct ldb_val cf_value;
  53 };
  54
  55 struct ldb_dn_ext_component {
  56
  57         char *name;
  58         struct ldb_val value;
  59 };
  60
  61 struct ldb_dn {
  62
  63         struct ldb_context *ldb;
  64
  65         /* Special DNs are always linearized */
  66         bool special;
  67         bool invalid;
  68
  69         bool valid_case;
  70
  71         char *linearized;
  72         char *ext_linearized;
  73         char *casefold;
  74
  75         unsigned int comp_num;
  76         struct ldb_dn_component *components;
  77
  78         unsigned int ext_comp_num;
  79         struct ldb_dn_ext_component *ext_components;
  80 };
  81
  82 /* it is helpful to be able to break on this in gdb */
  83 static void ldb_dn_mark_invalid(struct ldb_dn *dn)
  84 {
  85         dn->invalid = true;
  86 }
  87
  88 /* strdn may be NULL */
  89 struct ldb_dn *ldb_dn_from_ldb_val(TALLOC_CTX *mem_ctx,
  90                                    struct ldb_context *ldb,
  91                                    const struct ldb_val *strdn)
  92 {
  93         struct ldb_dn *dn;
  94
  95         if (! ldb) return NULL;
  96
  97         if (strdn && strdn->data
  98             && (strnlen((const char*)strdn->data, strdn->length) != strdn->length)) {
  99                 /* The RDN must not contain a character with value 0x0 */
 100                 return NULL;
 101         }
 102
 103         dn = talloc_zero(mem_ctx, struct ldb_dn);
 104         LDB_DN_NULL_FAILED(dn);
 105
 106         dn->ldb = talloc_get_type(ldb, struct ldb_context);
 107         if (dn->ldb == NULL) {
 108                 /* the caller probably got the arguments to
 109                    ldb_dn_new() mixed up */
 110                 talloc_free(dn);
 111                 return NULL;
 112         }
 113
 114         if (strdn->data && strdn->length) {
 115                 const char *data = (const char *)strdn->data;
 116                 size_t length = strdn->length;
 117
 118                 if (data[0] == '@') {
 119                         dn->special = true;
 120                 }
 121                 dn->ext_linearized = talloc_strndup(dn, data, length);
 122                 LDB_DN_NULL_FAILED(dn->ext_linearized);
 123
 124                 if (data[0] == '<') {
 125                         const char *p_save, *p = dn->ext_linearized;
 126                         do {
 127                                 p_save = p;
 128                                 p = strstr(p, ">;");
 129                                 if (p) {
 130                                         p = p + 2;
 131                                 }
 132                         } while (p);
 133
 134                         if (p_save == dn->ext_linearized) {
 135                                 dn->linearized = talloc_strdup(dn, "");
 136                         } else {
 137                                 dn->linearized = talloc_strdup(dn, p_save);
 138                         }
 139                         LDB_DN_NULL_FAILED(dn->linearized);
 140                 } else {
 141                         dn->linearized = dn->ext_linearized;
 142                         dn->ext_linearized = NULL;
 143                 }
 144         } else {
 145                 dn->linearized = talloc_strdup(dn, "");
 146                 LDB_DN_NULL_FAILED(dn->linearized);
 147         }
 148
 149         return dn;
 150
 151 failed:
 152         talloc_free(dn);
 153         return NULL;
 154 }
 155
 156 /* strdn may be NULL */
 157 struct ldb_dn *ldb_dn_new(TALLOC_CTX *mem_ctx,
 158                           struct ldb_context *ldb,
 159                           const char *strdn)
 160 {
 161         struct ldb_val blob;
 162         blob.data = discard_const_p(uint8_t, strdn);
 163         blob.length = strdn ? strlen(strdn) : 0;
 164         return ldb_dn_from_ldb_val(mem_ctx, ldb, &blob);
 165 }
 166
 167 struct ldb_dn *ldb_dn_new_fmt(TALLOC_CTX *mem_ctx,
 168                               struct ldb_context *ldb,
 169                               const char *new_fmt, ...)
 170 {
 171         char *strdn;
 172         va_list ap;
 173
 174         if ( (! mem_ctx) || (! ldb)) return NULL;
 175
 176         va_start(ap, new_fmt);
 177         strdn = talloc_vasprintf(mem_ctx, new_fmt, ap);
 178         va_end(ap);
 179
 180         if (strdn) {
 181                 struct ldb_dn *dn = ldb_dn_new(mem_ctx, ldb, strdn);
 182                 talloc_free(strdn);
 183                 return dn;
 184         }
 185
 186         return NULL;
 187 }
 188
 189 /* see RFC2253 section 2.4 */
 190 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 191 {
 192         char c;
 193         char *d;
 194         int i;
 195         d = dst;
 196
 197         for (i = 0; i < len; i++){
 198                 c = src[i];
 199                 switch (c) {
 200                 case ' ':
 201                         if (i == 0 || i == len - 1) {
 202                                 /* if at the beginning or end
 203                                  * of the string then escape */
 204                                 *d++ = '\\';
 205                                 *d++ = c;
 206                         } else {
 207                                 /* otherwise don't escape */
 208                                 *d++ = c;
 209                         }
 210                         break;
 211
 212                 case '#':
 213                         /* despite the RFC, windows escapes a #
 214                            anywhere in the string */
 215                 case ',':
 216                 case '+':
 217                 case '"':
 218                 case '\\':
 219                 case '<':
 220                 case '>':
 221                 case '?':
 222                         /* these must be escaped using \c form */
 223                         *d++ = '\\';
 224                         *d++ = c;
 225                         break;
 226
 227                 case ';':
 228                 case '\r':
 229                 case '\n':
 230                 case '=':
 231                 case '\0': {
 232                         /* any others get \XX form */
 233                         unsigned char v;
 234                         const char *hexbytes = "0123456789ABCDEF";
 235                         v = (const unsigned char)c;
 236                         *d++ = '\\';
 237                         *d++ = hexbytes[v>>4];
 238                         *d++ = hexbytes[v&0xF];
 239                         break;
 240                 }
 241                 default:
 242                         *d++ = c;
 243                 }
 244         }
 245
 246         /* return the length of the resulting string */
 247         return (d - dst);
 248 }
 249
 250 char *ldb_dn_escape_value(TALLOC_CTX *mem_ctx, struct ldb_val value)
 251 {
 252         char *dst;
 253         size_t len;
 254         if (!value.length)
 255                 return NULL;
 256
 257         /* allocate destination string, it will be at most 3 times the source */
 258         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 259         if ( ! dst) {
 260                 talloc_free(dst);
 261                 return NULL;
 262         }
 263
 264         len = ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 265
 266         dst = talloc_realloc(mem_ctx, dst, char, len + 1);
 267         if ( ! dst) {
 268                 talloc_free(dst);
 269                 return NULL;
 270         }
 271         dst[len] = '\0';
 272         return dst;
 273 }
 274
 275 /*
 276   explode a DN string into a ldb_dn structure
 277   based on RFC4514 except that we don't support multiple valued RDNs
 278
 279   TODO: according to MS-ADTS:3.1.1.5.2 Naming Constraints
 280   DN must be compliant with RFC2253
 281 */
 282 static bool ldb_dn_explode(struct ldb_dn *dn)
 283 {
 284         char *p, *ex_name = NULL, *ex_value = NULL, *data, *d, *dt, *t;
 285         bool trim = true;
 286         bool in_extended = true;
 287         bool in_ex_name = false;
 288         bool in_ex_value = false;
 289         bool in_attr = false;
 290         bool in_value = false;
 291         bool in_quote = false;
 292         bool is_oid = false;
 293         bool escape = false;
 294         unsigned int x;
 295         size_t l = 0;
 296         int ret;
 297         char *parse_dn;
 298         bool is_index;
 299
 300         if ( ! dn || dn->invalid) return false;
 301
 302         if (dn->components) {
 303                 return true;
 304         }
 305
 306         if (dn->ext_linearized) {
 307                 parse_dn = dn->ext_linearized;
 308         } else {
 309                 parse_dn = dn->linearized;
 310         }
 311
 312         if ( ! parse_dn ) {
 313                 return false;
 314         }
 315
 316         is_index = (strncmp(parse_dn, "DN=@INDEX:", 10) == 0);
 317
 318         /* Empty DNs */
 319         if (parse_dn[0] == '\0') {
 320                 return true;
 321         }
 322
 323         /* Special DNs case */
 324         if (dn->special) {
 325                 return true;
 326         }
 327
 328         /* make sure we free this if allocated previously before replacing */
 329         LDB_FREE(dn->components);
 330         dn->comp_num = 0;
 331
 332         LDB_FREE(dn->ext_components);
 333         dn->ext_comp_num = 0;
 334
 335         /* in the common case we have 3 or more components */
 336         /* make sure all components are zeroed, other functions depend on it */
 337         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 338         if ( ! dn->components) {
 339                 return false;
 340         }
 341
 342         /* Components data space is allocated here once */
 343         data = talloc_array(dn->components, char, strlen(parse_dn) + 1);
 344         if (!data) {
 345                 return false;
 346         }
 347
 348         p = parse_dn;
 349         t = NULL;
 350         d = dt = data;
 351
 352         while (*p) {
 353                 if (in_extended) {
 354
 355                         if (!in_ex_name && !in_ex_value) {
 356
 357                                 if (p[0] == '<') {
 358                                         p++;
 359                                         ex_name = d;
 360                                         in_ex_name = true;
 361                                         continue;
 362                                 } else if (p[0] == '\0') {
 363                                         p++;
 364                                         continue;
 365                                 } else {
 366                                         in_extended = false;
 367                                         in_attr = true;
 368                                         dt = d;
 369
 370                                         continue;
 371                                 }
 372                         }
 373
 374                         if (in_ex_name && *p == '=') {
 375                                 *d++ = '\0';
 376                                 p++;
 377                                 ex_value = d;
 378                                 in_ex_name = false;
 379                                 in_ex_value = true;
 380                                 continue;
 381                         }
 382
 383                         if (in_ex_value && *p == '>') {
 384                                 const struct ldb_dn_extended_syntax *ext_syntax;
 385                                 struct ldb_val ex_val = {
 386                                         .data = (uint8_t *)ex_value,
 387                                         .length = d - ex_value
 388                                 };
 389
 390                                 *d++ = '\0';
 391                                 p++;
 392                                 in_ex_value = false;
 393
 394                                 /* Process name and ex_value */
 395
 396                                 dn->ext_components = talloc_realloc(dn,
 397                                                                     dn->ext_components,
 398                                                                     struct ldb_dn_ext_component,
 399                                                                     dn->ext_comp_num + 1);
 400                                 if ( ! dn->ext_components) {
 401                                         /* ouch ! */
 402                                         goto failed;
 403                                 }
 404
 405                                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, ex_name);
 406                                 if (!ext_syntax) {
 407                                         /* We don't know about this type of extended DN */
 408                                         goto failed;
 409                                 }
 410
 411                                 dn->ext_components[dn->ext_comp_num].name = talloc_strdup(dn->ext_components, ex_name);
 412                                 if (!dn->ext_components[dn->ext_comp_num].name) {
 413                                         /* ouch */
 414                                         goto failed;
 415                                 }
 416                                 ret = ext_syntax->read_fn(dn->ldb, dn->ext_components,
 417                                                           &ex_val, &dn->ext_components[dn->ext_comp_num].value);
 418                                 if (ret != LDB_SUCCESS) {
 419                                         ldb_dn_mark_invalid(dn);
 420                                         goto failed;
 421                                 }
 422
 423                                 dn->ext_comp_num++;
 424
 425                                 if (*p == '\0') {
 426                                         /* We have reached the end (extended component only)! */
 427                                         talloc_free(data);
 428                                         return true;
 429
 430                                 } else if (*p == ';') {
 431                                         p++;
 432                                         continue;
 433                                 } else {
 434                                         ldb_dn_mark_invalid(dn);
 435                                         goto failed;
 436                                 }
 437                         }
 438
 439                         *d++ = *p++;
 440                         continue;
 441                 }
 442                 if (in_attr) {
 443                         if (trim) {
 444                                 if (*p == ' ') {
 445                                         p++;
 446                                         continue;
 447                                 }
 448
 449                                 /* first char */
 450                                 trim = false;
 451
 452                                 if (!isascii(*p)) {
 453                                         /* attr names must be ascii only */
 454                                         ldb_dn_mark_invalid(dn);
 455                                         goto failed;
 456                                 }
 457
 458                                 if (isdigit(*p)) {
 459                                         is_oid = true;
 460                                 } else
 461                                 if ( ! isalpha(*p)) {
 462                                         /* not a digit nor an alpha,
 463                                          * invalid attribute name */
 464                                         ldb_dn_mark_invalid(dn);
 465                                         goto failed;
 466                                 }
 467
 468                                 /* Copy this character across from parse_dn,
 469                                  * now we have trimmed out spaces */
 470                                 *d++ = *p++;
 471                                 continue;
 472                         }
 473
 474                         if (*p == ' ') {
 475                                 p++;
 476                                 /* valid only if we are at the end */
 477                                 trim = true;
 478                                 continue;
 479                         }
 480
 481                         if (trim && (*p != '=')) {
 482                                 /* spaces/tabs are not allowed */
 483                                 ldb_dn_mark_invalid(dn);
 484                                 goto failed;
 485                         }
 486
 487                         if (*p == '=') {
 488                                 /* attribute terminated */
 489                                 in_attr = false;
 490                                 in_value = true;
 491                                 trim = true;
 492                                 l = 0;
 493
 494                                 /* Terminate this string in d
 495                                  * (which is a copy of parse_dn
 496                                  *  with spaces trimmed) */
 497                                 *d++ = '\0';
 498                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 499                                 if ( ! dn->components[dn->comp_num].name) {
 500                                         /* ouch */
 501                                         goto failed;
 502                                 }
 503
 504                                 dt = d;
 505
 506                                 p++;
 507                                 continue;
 508                         }
 509
 510                         if (!isascii(*p)) {
 511                                 /* attr names must be ascii only */
 512                                 ldb_dn_mark_invalid(dn);
 513                                 goto failed;
 514                         }
 515
 516                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 517                                 /* not a digit nor a dot,
 518                                  * invalid attribute oid */
 519                                 ldb_dn_mark_invalid(dn);
 520                                 goto failed;
 521                         } else
 522                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 523                                 /* not ALPHA, DIGIT or HYPHEN */
 524                                 ldb_dn_mark_invalid(dn);
 525                                 goto failed;
 526                         }
 527
 528                         *d++ = *p++;
 529                         continue;
 530                 }
 531
 532                 if (in_value) {
 533                         if (in_quote) {
 534                                 if (*p == '\"') {
 535                                         if (p[-1] != '\\') {
 536                                                 p++;
 537                                                 in_quote = false;
 538                                                 continue;
 539                                         }
 540                                 }
 541                                 *d++ = *p++;
 542                                 l++;
 543                                 continue;
 544                         }
 545
 546                         if (trim) {
 547                                 if (*p == ' ') {
 548                                         p++;
 549                                         continue;
 550                                 }
 551
 552                                 /* first char */
 553                                 trim = false;
 554
 555                                 if (*p == '\"') {
 556                                         in_quote = true;
 557                                         p++;
 558                                         continue;
 559                                 }
 560                         }
 561
 562                         switch (*p) {
 563
 564                         /* TODO: support ber encoded values
 565                         case '#':
 566                         */
 567
 568                         case ',':
 569                                 if (escape) {
 570                                         *d++ = *p++;
 571                                         l++;
 572                                         escape = false;
 573                                         continue;
 574                                 }
 575                                 /* ok found value terminator */
 576
 577                                 if ( t ) {
 578                                         /* trim back */
 579                                         d -= (p - t);
 580                                         l -= (p - t);
 581                                 }
 582
 583                                 in_attr = true;
 584                                 in_value = false;
 585                                 trim = true;
 586
 587                                 p++;
 588                                 *d++ = '\0';
 589
 590                                 /*
 591                                  * This talloc_memdup() is OK with the
 592                                  * +1 because *d has been set to '\0'
 593                                  * just above
 594                                  */
 595                                 dn->components[dn->comp_num].value.data = \
 596                                         (uint8_t *)talloc_memdup(dn->components, dt, l + 1);
 597                                 dn->components[dn->comp_num].value.length = l;
 598                                 if ( ! dn->components[dn->comp_num].value.data) {
 599                                         /* ouch ! */
 600                                         goto failed;
 601                                 }
 602                                 talloc_set_name_const(dn->components[dn->comp_num].value.data,
 603                                                       (const char *)dn->components[dn->comp_num].value.data);
 604
 605                                 dt = d;
 606
 607                                 dn->comp_num++;
 608                                 if (dn->comp_num > 2) {
 609                                         dn->components = talloc_realloc(dn,
 610                                                                         dn->components,
 611                                                                         struct ldb_dn_component,
 612                                                                         dn->comp_num + 1);
 613                                         if ( ! dn->components) {
 614                                                 /* ouch ! */
 615                                                 goto failed;
 616                                         }
 617                                         /* make sure all components are zeroed, other functions depend on this */
 618                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 619                                 }
 620
 621                                 continue;
 622
 623                         case '+':
 624                         case '=':
 625                                 /* to main compatibility with earlier
 626                                 versions of ldb indexing, we have to
 627                                 accept the base64 encoded binary index
 628                                 values, which contain a '+' or '='
 629                                 which should normally be escaped */
 630                                 if (is_index) {
 631                                         if ( t ) t = NULL;
 632                                         *d++ = *p++;
 633                                         l++;
 634                                         break;
 635                                 }
 636                                 /* fall through */
 637                         case '\"':
 638                         case '<':
 639                         case '>':
 640                         case ';':
 641                                 /* a string with not escaped specials is invalid (tested) */
 642                                 if ( ! escape) {
 643                                         ldb_dn_mark_invalid(dn);
 644                                         goto failed;
 645                                 }
 646                                 escape = false;
 647
 648                                 *d++ = *p++;
 649                                 l++;
 650
 651                                 if ( t ) t = NULL;
 652                                 break;
 653
 654                         case '\\':
 655                                 if ( ! escape) {
 656                                         escape = true;
 657                                         p++;
 658                                         continue;
 659                                 }
 660                                 escape = false;
 661
 662                                 *d++ = *p++;
 663                                 l++;
 664
 665                                 if ( t ) t = NULL;
 666                                 break;
 667
 668                         default:
 669                                 if (escape) {
 670                                         if (isxdigit(p[0]) && isxdigit(p[1])) {
 671                                                 if (sscanf(p, "%02x", &x) != 1) {
 672                                                         /* invalid escaping sequence */
 673                                                         ldb_dn_mark_invalid(dn);
 674                                                         goto failed;
 675                                                 }
 676                                                 p += 2;
 677                                                 *d++ = (unsigned char)x;
 678                                         } else {
 679                                                 *d++ = *p++;
 680                                         }
 681
 682                                         escape = false;
 683                                         l++;
 684                                         if ( t ) t = NULL;
 685                                         break;
 686                                 }
 687
 688                                 if (*p == ' ') {
 689                                         if ( ! t) t = p;
 690                                 } else {
 691                                         if ( t ) t = NULL;
 692                                 }
 693
 694                                 *d++ = *p++;
 695                                 l++;
 696
 697                                 break;
 698                         }
 699
 700                 }
 701         }
 702
 703         if (in_attr || in_quote) {
 704                 /* invalid dn */
 705                 ldb_dn_mark_invalid(dn);
 706                 goto failed;
 707         }
 708
 709         /* save last element */
 710         if ( t ) {
 711                 /* trim back */
 712                 d -= (p - t);
 713                 l -= (p - t);
 714         }
 715
 716         *d++ = '\0';
 717         /*
 718          * This talloc_memdup() is OK with the
 719          * +1 because *d has been set to '\0'
 720          * just above.
 721          */
 722         dn->components[dn->comp_num].value.length = l;
 723         dn->components[dn->comp_num].value.data =
 724                 (uint8_t *)talloc_memdup(dn->components, dt, l + 1);
 725         if ( ! dn->components[dn->comp_num].value.data) {
 726                 /* ouch */
 727                 goto failed;
 728         }
 729         talloc_set_name_const(dn->components[dn->comp_num].value.data,
 730                               (const char *)dn->components[dn->comp_num].value.data);
 731
 732         dn->comp_num++;
 733
 734         talloc_free(data);
 735         return true;
 736
 737 failed:
 738         LDB_FREE(dn->components); /* "data" is implicitly free'd */
 739         dn->comp_num = 0;
 740         LDB_FREE(dn->ext_components);
 741         dn->ext_comp_num = 0;
 742
 743         return false;
 744 }
 745
 746 bool ldb_dn_validate(struct ldb_dn *dn)
 747 {
 748         return ldb_dn_explode(dn);
 749 }
 750
 751 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 752 {
 753         unsigned int i;
 754         size_t len;
 755         char *d, *n;
 756
 757         if ( ! dn || ( dn->invalid)) return NULL;
 758
 759         if (dn->linearized) return dn->linearized;
 760
 761         if ( ! dn->components) {
 762                 ldb_dn_mark_invalid(dn);
 763                 return NULL;
 764         }
 765
 766         if (dn->comp_num == 0) {
 767                 dn->linearized = talloc_strdup(dn, "");
 768                 if ( ! dn->linearized) return NULL;
 769                 return dn->linearized;
 770         }
 771
 772         /* calculate maximum possible length of DN */
 773         for (len = 0, i = 0; i < dn->comp_num; i++) {
 774                 /* name len */
 775                 len += strlen(dn->components[i].name);
 776                 /* max escaped data len */
 777                 len += (dn->components[i].value.length * 3);
 778                 len += 2; /* '=' and ',' */
 779         }
 780         dn->linearized = talloc_array(dn, char, len);
 781         if ( ! dn->linearized) return NULL;
 782
 783         d = dn->linearized;
 784
 785         for (i = 0; i < dn->comp_num; i++) {
 786
 787                 /* copy the name */
 788                 n = dn->components[i].name;
 789                 while (*n) *d++ = *n++;
 790
 791                 *d++ = '=';
 792
 793                 /* and the value */
 794                 d += ldb_dn_escape_internal( d,
 795                                 (char *)dn->components[i].value.data,
 796                                 dn->components[i].value.length);
 797                 *d++ = ',';
 798         }
 799
 800         *(--d) = '\0';
 801
 802         /* don't waste more memory than necessary */
 803         dn->linearized = talloc_realloc(dn, dn->linearized,
 804                                         char, (d - dn->linearized + 1));
 805
 806         return dn->linearized;
 807 }
 808
 809 static int ldb_dn_extended_component_compare(const void *p1, const void *p2)
 810 {
 811         const struct ldb_dn_ext_component *ec1 = (const struct ldb_dn_ext_component *)p1;
 812         const struct ldb_dn_ext_component *ec2 = (const struct ldb_dn_ext_component *)p2;
 813         return strcmp(ec1->name, ec2->name);
 814 }
 815
 816 char *ldb_dn_get_extended_linearized(TALLOC_CTX *mem_ctx, struct ldb_dn *dn, int mode)
 817 {
 818         const char *linearized = ldb_dn_get_linearized(dn);
 819         char *p = NULL;
 820         unsigned int i;
 821
 822         if (!linearized) {
 823                 return NULL;
 824         }
 825
 826         if (!ldb_dn_has_extended(dn)) {
 827                 return talloc_strdup(mem_ctx, linearized);
 828         }
 829
 830         if (!ldb_dn_validate(dn)) {
 831                 return NULL;
 832         }
 833
 834         /* sort the extended components by name. The idea is to make
 835          * the resulting DNs consistent, plus to ensure that we put
 836          * 'DELETED' first, so it can be very quickly recognised
 837          */
 838         TYPESAFE_QSORT(dn->ext_components, dn->ext_comp_num,
 839                        ldb_dn_extended_component_compare);
 840
 841         for (i = 0; i < dn->ext_comp_num; i++) {
 842                 const struct ldb_dn_extended_syntax *ext_syntax;
 843                 const char *name = dn->ext_components[i].name;
 844                 struct ldb_val ec_val = dn->ext_components[i].value;
 845                 struct ldb_val val;
 846                 int ret;
 847
 848                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, name);
 849                 if (!ext_syntax) {
 850                         return NULL;
 851                 }
 852
 853                 if (mode == 1) {
 854                         ret = ext_syntax->write_clear_fn(dn->ldb, mem_ctx,
 855                                                         &ec_val, &val);
 856                 } else if (mode == 0) {
 857                         ret = ext_syntax->write_hex_fn(dn->ldb, mem_ctx,
 858                                                         &ec_val, &val);
 859                 } else {
 860                         ret = -1;
 861                 }
 862
 863                 if (ret != LDB_SUCCESS) {
 864                         return NULL;
 865                 }
 866
 867                 if (i == 0) {
 868                         p = talloc_asprintf(mem_ctx, "<%s=%s>",
 869                                             name, val.data);
 870                 } else {
 871                         p = talloc_asprintf_append_buffer(p, ";<%s=%s>",
 872                                                           name, val.data);
 873                 }
 874
 875                 talloc_free(val.data);
 876
 877                 if (!p) {
 878                         return NULL;
 879                 }
 880         }
 881
 882         if (dn->ext_comp_num && *linearized) {
 883                 p = talloc_asprintf_append_buffer(p, ";%s", linearized);
 884         }
 885
 886         if (!p) {
 887                 return NULL;
 888         }
 889
 890         return p;
 891 }
 892
 893 /*
 894   filter out all but an acceptable list of extended DN components
 895  */
 896 void ldb_dn_extended_filter(struct ldb_dn *dn, const char * const *accept_list)
 897 {
 898         unsigned int i;
 899         for (i=0; i<dn->ext_comp_num; i++) {
 900                 if (!ldb_attr_in_list(accept_list, dn->ext_components[i].name)) {
 901                         memmove(&dn->ext_components[i],
 902                                 &dn->ext_components[i+1],
 903                                 (dn->ext_comp_num-(i+1))*sizeof(dn->ext_components[0]));
 904                         dn->ext_comp_num--;
 905                         i--;
 906                 }
 907         }
 908         LDB_FREE(dn->ext_linearized);
 909 }
 910
 911
 912 char *ldb_dn_alloc_linearized(TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
 913 {
 914         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 915 }
 916
 917 /*
 918   casefold a dn. We need to casefold the attribute names, and canonicalize
 919   attribute values of case insensitive attributes.
 920 */
 921
 922 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 923 {
 924         unsigned int i;
 925         int ret;
 926
 927         if ( ! dn || dn->invalid) return false;
 928
 929         if (dn->valid_case) return true;
 930
 931         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
 932                 return false;
 933         }
 934
 935         for (i = 0; i < dn->comp_num; i++) {
 936                 const struct ldb_schema_attribute *a;
 937
 938                 dn->components[i].cf_name =
 939                         ldb_attr_casefold(dn->components,
 940                                           dn->components[i].name);
 941                 if (!dn->components[i].cf_name) {
 942                         goto failed;
 943                 }
 944
 945                 a = ldb_schema_attribute_by_name(dn->ldb,
 946                                                  dn->components[i].cf_name);
 947
 948                 ret = a->syntax->canonicalise_fn(dn->ldb, dn->components,
 949                                                  &(dn->components[i].value),
 950                                                  &(dn->components[i].cf_value));
 951                 if (ret != 0) {
 952                         goto failed;
 953                 }
 954         }
 955
 956         dn->valid_case = true;
 957
 958         return true;
 959
 960 failed:
 961         for (i = 0; i < dn->comp_num; i++) {
 962                 LDB_FREE(dn->components[i].cf_name);
 963                 LDB_FREE(dn->components[i].cf_value.data);
 964         }
 965         return false;
 966 }
 967
 968 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 969 {
 970         unsigned int i;
 971         size_t len;
 972         char *d, *n;
 973
 974         if (dn->casefold) return dn->casefold;
 975
 976         if (dn->special) {
 977                 dn->casefold = talloc_strdup(dn, dn->linearized);
 978                 if (!dn->casefold) return NULL;
 979                 dn->valid_case = true;
 980                 return dn->casefold;
 981         }
 982
 983         if ( ! ldb_dn_casefold_internal(dn)) {
 984                 return NULL;
 985         }
 986
 987         if (dn->comp_num == 0) {
 988                 dn->casefold = talloc_strdup(dn, "");
 989                 return dn->casefold;
 990         }
 991
 992         /* calculate maximum possible length of DN */
 993         for (len = 0, i = 0; i < dn->comp_num; i++) {
 994                 /* name len */
 995                 len += strlen(dn->components[i].cf_name);
 996                 /* max escaped data len */
 997                 len += (dn->components[i].cf_value.length * 3);
 998                 len += 2; /* '=' and ',' */
 999         }
1000         dn->casefold = talloc_array(dn, char, len);
1001         if ( ! dn->casefold) return NULL;
1002
1003         d = dn->casefold;
1004
1005         for (i = 0; i < dn->comp_num; i++) {
1006
1007                 /* copy the name */
1008                 n = dn->components[i].cf_name;
1009                 while (*n) *d++ = *n++;
1010
1011                 *d++ = '=';
1012
1013                 /* and the value */
1014                 d += ldb_dn_escape_internal( d,
1015                                 (char *)dn->components[i].cf_value.data,
1016                                 dn->components[i].cf_value.length);
1017                 *d++ = ',';
1018         }
1019         *(--d) = '\0';
1020
1021         /* don't waste more memory than necessary */
1022         dn->casefold = talloc_realloc(dn, dn->casefold,
1023                                       char, strlen(dn->casefold) + 1);
1024
1025         return dn->casefold;
1026 }
1027
1028 char *ldb_dn_alloc_casefold(TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
1029 {
1030         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
1031 }
1032
1033 /* Determine if dn is below base, in the ldap tree.  Used for
1034  * evaluating a subtree search.
1035  * 0 if they match, otherwise non-zero
1036  */
1037
1038 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
1039 {
1040         int ret;
1041         unsigned int n_base, n_dn;
1042
1043         if ( ! base || base->invalid) return 1;
1044         if ( ! dn || dn->invalid) return -1;
1045
1046         if (( ! base->valid_case) || ( ! dn->valid_case)) {
1047                 if (base->linearized && dn->linearized && dn->special == base->special) {
1048                         /* try with a normal compare first, if we are lucky
1049                          * we will avoid exploding and casfolding */
1050                         int dif;
1051                         dif = strlen(dn->linearized) - strlen(base->linearized);
1052                         if (dif < 0) {
1053                                 return dif;
1054                         }
1055                         if (strcmp(base->linearized,
1056                                    &dn->linearized[dif]) == 0) {
1057                                 return 0;
1058                         }
1059                 }
1060
1061                 if ( ! ldb_dn_casefold_internal(base)) {
1062                         return 1;
1063                 }
1064
1065                 if ( ! ldb_dn_casefold_internal(dn)) {
1066                         return -1;
1067                 }
1068
1069         }
1070
1071         /* if base has more components,
1072          * they don't have the same base */
1073         if (base->comp_num > dn->comp_num) {
1074                 return (dn->comp_num - base->comp_num);
1075         }
1076
1077         if ((dn->comp_num == 0) || (base->comp_num == 0)) {
1078                 if (dn->special && base->special) {
1079                         return strcmp(base->linearized, dn->linearized);
1080                 } else if (dn->special) {
1081                         return -1;
1082                 } else if (base->special) {
1083                         return 1;
1084                 } else {
1085                         return 0;
1086                 }
1087         }
1088
1089         n_base = base->comp_num - 1;
1090         n_dn = dn->comp_num - 1;
1091
1092         while (n_base != (unsigned int) -1) {
1093                 char *b_name = base->components[n_base].cf_name;
1094                 char *dn_name = dn->components[n_dn].cf_name;
1095
1096                 char *b_vdata = (char *)base->components[n_base].cf_value.data;
1097                 char *dn_vdata = (char *)dn->components[n_dn].cf_value.data;
1098
1099                 size_t b_vlen = base->components[n_base].cf_value.length;
1100                 size_t dn_vlen = dn->components[n_dn].cf_value.length;
1101
1102                 /* compare attr names */
1103                 ret = strcmp(b_name, dn_name);
1104                 if (ret != 0) return ret;
1105
1106                 /* compare attr.cf_value. */
1107                 if (b_vlen != dn_vlen) {
1108                         return b_vlen - dn_vlen;
1109                 }
1110                 ret = strncmp(b_vdata, dn_vdata, b_vlen);
1111                 if (ret != 0) return ret;
1112
1113                 n_base--;
1114                 n_dn--;
1115         }
1116
1117         return 0;
1118 }
1119
1120 /* compare DNs using casefolding compare functions.
1121
1122    If they match, then return 0
1123  */
1124
1125 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
1126 {
1127         unsigned int i;
1128         int ret;
1129
1130         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) {
1131                 return -1;
1132         }
1133
1134         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
1135                 if (dn0->linearized && dn1->linearized) {
1136                         /* try with a normal compare first, if we are lucky
1137                          * we will avoid exploding and casfolding */
1138                         if (strcmp(dn0->linearized, dn1->linearized) == 0) {
1139                                 return 0;
1140                         }
1141                 }
1142
1143                 if ( ! ldb_dn_casefold_internal(dn0)) {
1144                         return 1;
1145                 }
1146
1147                 if ( ! ldb_dn_casefold_internal(dn1)) {
1148                         return -1;
1149                 }
1150
1151         }
1152
1153         if (dn0->comp_num != dn1->comp_num) {
1154                 return (dn1->comp_num - dn0->comp_num);
1155         }
1156
1157         if (dn0->comp_num == 0) {
1158                 if (dn0->special && dn1->special) {
1159                         return strcmp(dn0->linearized, dn1->linearized);
1160                 } else if (dn0->special) {
1161                         return 1;
1162                 } else if (dn1->special) {
1163                         return -1;
1164                 } else {
1165                         return 0;
1166                 }
1167         }
1168
1169         for (i = 0; i < dn0->comp_num; i++) {
1170                 char *dn0_name = dn0->components[i].cf_name;
1171                 char *dn1_name = dn1->components[i].cf_name;
1172
1173                 char *dn0_vdata = (char *)dn0->components[i].cf_value.data;
1174                 char *dn1_vdata = (char *)dn1->components[i].cf_value.data;
1175
1176                 size_t dn0_vlen = dn0->components[i].cf_value.length;
1177                 size_t dn1_vlen = dn1->components[i].cf_value.length;
1178
1179                 /* compare attr names */
1180                 ret = strcmp(dn0_name, dn1_name);
1181                 if (ret != 0) {
1182                         return ret;
1183                 }
1184
1185                 /* compare attr.cf_value. */
1186                 if (dn0_vlen != dn1_vlen) {
1187                         return dn0_vlen - dn1_vlen;
1188                 }
1189                 ret = strncmp(dn0_vdata, dn1_vdata, dn0_vlen);
1190                 if (ret != 0) {
1191                         return ret;
1192                 }
1193         }
1194
1195         return 0;
1196 }
1197
1198 static struct ldb_dn_component ldb_dn_copy_component(
1199                                                 TALLOC_CTX *mem_ctx,
1200                                                 struct ldb_dn_component *src)
1201 {
1202         struct ldb_dn_component dst;
1203
1204         memset(&dst, 0, sizeof(dst));
1205
1206         if (src == NULL) {
1207                 return dst;
1208         }
1209
1210         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1211         if (dst.value.data == NULL) {
1212                 return dst;
1213         }
1214
1215         dst.name = talloc_strdup(mem_ctx, src->name);
1216         if (dst.name == NULL) {
1217                 LDB_FREE(dst.value.data);
1218                 return dst;
1219         }
1220
1221         if (src->cf_value.data) {
1222                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
1223                 if (dst.cf_value.data == NULL) {
1224                         LDB_FREE(dst.value.data);
1225                         LDB_FREE(dst.name);
1226                         return dst;
1227                 }
1228
1229                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
1230                 if (dst.cf_name == NULL) {
1231                         LDB_FREE(dst.cf_name);
1232                         LDB_FREE(dst.value.data);
1233                         LDB_FREE(dst.name);
1234                         return dst;
1235                 }
1236         } else {
1237                 dst.cf_value.data = NULL;
1238                 dst.cf_name = NULL;
1239         }
1240
1241         return dst;
1242 }
1243
1244 static struct ldb_dn_ext_component ldb_dn_ext_copy_component(
1245                                                 TALLOC_CTX *mem_ctx,
1246                                                 struct ldb_dn_ext_component *src)
1247 {
1248         struct ldb_dn_ext_component dst;
1249
1250         memset(&dst, 0, sizeof(dst));
1251
1252         if (src == NULL) {
1253                 return dst;
1254         }
1255
1256         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1257         if (dst.value.data == NULL) {
1258                 return dst;
1259         }
1260
1261         dst.name = talloc_strdup(mem_ctx, src->name);
1262         if (dst.name == NULL) {
1263                 LDB_FREE(dst.value.data);
1264                 return dst;
1265         }
1266
1267         return dst;
1268 }
1269
1270 struct ldb_dn *ldb_dn_copy(TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
1271 {
1272         struct ldb_dn *new_dn;
1273
1274         if (!dn || dn->invalid) {
1275                 return NULL;
1276         }
1277
1278         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
1279         if ( !new_dn) {
1280                 return NULL;
1281         }
1282
1283         *new_dn = *dn;
1284
1285         if (dn->components) {
1286                 unsigned int i;
1287
1288                 new_dn->components =
1289                         talloc_zero_array(new_dn,
1290                                           struct ldb_dn_component,
1291                                           dn->comp_num);
1292                 if ( ! new_dn->components) {
1293                         talloc_free(new_dn);
1294                         return NULL;
1295                 }
1296
1297                 for (i = 0; i < dn->comp_num; i++) {
1298                         new_dn->components[i] =
1299                                 ldb_dn_copy_component(new_dn->components,
1300                                                       &dn->components[i]);
1301                         if ( ! new_dn->components[i].value.data) {
1302                                 talloc_free(new_dn);
1303                                 return NULL;
1304                         }
1305                 }
1306         }
1307
1308         if (dn->ext_components) {
1309                 unsigned int i;
1310
1311                 new_dn->ext_components =
1312                         talloc_zero_array(new_dn,
1313                                           struct ldb_dn_ext_component,
1314                                           dn->ext_comp_num);
1315                 if ( ! new_dn->ext_components) {
1316                         talloc_free(new_dn);
1317                         return NULL;
1318                 }
1319
1320                 for (i = 0; i < dn->ext_comp_num; i++) {
1321                         new_dn->ext_components[i] =
1322                                  ldb_dn_ext_copy_component(
1323                                                 new_dn->ext_components,
1324                                                 &dn->ext_components[i]);
1325                         if ( ! new_dn->ext_components[i].value.data) {
1326                                 talloc_free(new_dn);
1327                                 return NULL;
1328                         }
1329                 }
1330         }
1331
1332         if (dn->casefold) {
1333                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
1334                 if ( ! new_dn->casefold) {
1335                         talloc_free(new_dn);
1336                         return NULL;
1337                 }
1338         }
1339
1340         if (dn->linearized) {
1341                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
1342                 if ( ! new_dn->linearized) {
1343                         talloc_free(new_dn);
1344                         return NULL;
1345                 }
1346         }
1347
1348         if (dn->ext_linearized) {
1349                 new_dn->ext_linearized = talloc_strdup(new_dn,
1350                                                         dn->ext_linearized);
1351                 if ( ! new_dn->ext_linearized) {
1352                         talloc_free(new_dn);
1353                         return NULL;
1354                 }
1355         }
1356
1357         return new_dn;
1358 }
1359
1360 /* modify the given dn by adding a base.
1361  *
1362  * return true if successful and false if not
1363  * if false is returned the dn may be marked invalid
1364  */
1365 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
1366 {
1367         const char *s;
1368         char *t;
1369
1370         if ( !base || base->invalid || !dn || dn->invalid) {
1371                 return false;
1372         }
1373
1374         if (dn->components) {
1375                 unsigned int i;
1376
1377                 if ( ! ldb_dn_validate(base)) {
1378                         return false;
1379                 }
1380
1381                 s = NULL;
1382                 if (dn->valid_case) {
1383                         if ( ! (s = ldb_dn_get_casefold(base))) {
1384                                 return false;
1385                         }
1386                 }
1387
1388                 dn->components = talloc_realloc(dn,
1389                                                 dn->components,
1390                                                 struct ldb_dn_component,
1391                                                 dn->comp_num + base->comp_num);
1392                 if ( ! dn->components) {
1393                         ldb_dn_mark_invalid(dn);
1394                         return false;
1395                 }
1396
1397                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
1398                         dn->components[dn->comp_num] =
1399                                 ldb_dn_copy_component(dn->components,
1400                                                         &base->components[i]);
1401                         if (dn->components[dn->comp_num].value.data == NULL) {
1402                                 ldb_dn_mark_invalid(dn);
1403                                 return false;
1404                         }
1405                 }
1406
1407                 if (dn->casefold && s) {
1408                         if (*dn->casefold) {
1409                                 t = talloc_asprintf(dn, "%s,%s",
1410                                                     dn->casefold, s);
1411                         } else {
1412                                 t = talloc_strdup(dn, s);
1413                         }
1414                         LDB_FREE(dn->casefold);
1415                         dn->casefold = t;
1416                 }
1417         }
1418
1419         if (dn->linearized) {
1420
1421                 s = ldb_dn_get_linearized(base);
1422                 if ( ! s) {
1423                         return false;
1424                 }
1425
1426                 if (*dn->linearized) {
1427                         t = talloc_asprintf(dn, "%s,%s",
1428                                             dn->linearized, s);
1429                 } else {
1430                         t = talloc_strdup(dn, s);
1431                 }
1432                 if ( ! t) {
1433                         ldb_dn_mark_invalid(dn);
1434                         return false;
1435                 }
1436                 LDB_FREE(dn->linearized);
1437                 dn->linearized = t;
1438         }
1439
1440         /* Wipe the ext_linearized DN,
1441          * the GUID and SID are almost certainly no longer valid */
1442         LDB_FREE(dn->ext_linearized);
1443         LDB_FREE(dn->ext_components);
1444         dn->ext_comp_num = 0;
1445
1446         return true;
1447 }
1448
1449 /* modify the given dn by adding a base.
1450  *
1451  * return true if successful and false if not
1452  * if false is returned the dn may be marked invalid
1453  */
1454 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1455 {
1456         struct ldb_dn *base;
1457         char *base_str;
1458         va_list ap;
1459         bool ret;
1460
1461         if ( !dn || dn->invalid) {
1462                 return false;
1463         }
1464
1465         va_start(ap, base_fmt);
1466         base_str = talloc_vasprintf(dn, base_fmt, ap);
1467         va_end(ap);
1468
1469         if (base_str == NULL) {
1470                 return false;
1471         }
1472
1473         base = ldb_dn_new(base_str, dn->ldb, base_str);
1474
1475         ret = ldb_dn_add_base(dn, base);
1476
1477         talloc_free(base_str);
1478
1479         return ret;
1480 }
1481
1482 /* modify the given dn by adding children elements.
1483  *
1484  * return true if successful and false if not
1485  * if false is returned the dn may be marked invalid
1486  */
1487 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1488 {
1489         const char *s;
1490         char *t;
1491
1492         if ( !child || child->invalid || !dn || dn->invalid) {
1493                 return false;
1494         }
1495
1496         if (dn->components) {
1497                 unsigned int n;
1498                 unsigned int i, j;
1499
1500                 if (dn->comp_num == 0) {
1501                         return false;
1502                 }
1503
1504                 if ( ! ldb_dn_validate(child)) {
1505                         return false;
1506                 }
1507
1508                 s = NULL;
1509                 if (dn->valid_case) {
1510                         if ( ! (s = ldb_dn_get_casefold(child))) {
1511                                 return false;
1512                         }
1513                 }
1514
1515                 n = dn->comp_num + child->comp_num;
1516
1517                 dn->components = talloc_realloc(dn,
1518                                                 dn->components,
1519                                                 struct ldb_dn_component,
1520                                                 n);
1521                 if ( ! dn->components) {
1522                         ldb_dn_mark_invalid(dn);
1523                         return false;
1524                 }
1525
1526                 for (i = dn->comp_num - 1, j = n - 1; i != (unsigned int) -1;
1527                      i--, j--) {
1528                         dn->components[j] = dn->components[i];
1529                 }
1530
1531                 for (i = 0; i < child->comp_num; i++) {
1532                         dn->components[i] =
1533                                 ldb_dn_copy_component(dn->components,
1534                                                         &child->components[i]);
1535                         if (dn->components[i].value.data == NULL) {
1536                                 ldb_dn_mark_invalid(dn);
1537                                 return false;
1538                         }
1539                 }
1540
1541                 dn->comp_num = n;
1542
1543                 if (dn->casefold && s) {
1544                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1545                         LDB_FREE(dn->casefold);
1546                         dn->casefold = t;
1547                 }
1548         }
1549
1550         if (dn->linearized) {
1551                 if (dn->linearized[0] == '\0') {
1552                         return false;
1553                 }
1554
1555                 s = ldb_dn_get_linearized(child);
1556                 if ( ! s) {
1557                         return false;
1558                 }
1559
1560                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1561                 if ( ! t) {
1562                         ldb_dn_mark_invalid(dn);
1563                         return false;
1564                 }
1565                 LDB_FREE(dn->linearized);
1566                 dn->linearized = t;
1567         }
1568
1569         /* Wipe the ext_linearized DN,
1570          * the GUID and SID are almost certainly no longer valid */
1571         LDB_FREE(dn->ext_linearized);
1572         LDB_FREE(dn->ext_components);
1573         dn->ext_comp_num = 0;
1574
1575         return true;
1576 }
1577
1578 /* modify the given dn by adding children elements.
1579  *
1580  * return true if successful and false if not
1581  * if false is returned the dn may be marked invalid
1582  */
1583 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1584 {
1585         struct ldb_dn *child;
1586         char *child_str;
1587         va_list ap;
1588         bool ret;
1589
1590         if ( !dn || dn->invalid) {
1591                 return false;
1592         }
1593
1594         va_start(ap, child_fmt);
1595         child_str = talloc_vasprintf(dn, child_fmt, ap);
1596         va_end(ap);
1597
1598         if (child_str == NULL) {
1599                 return false;
1600         }
1601
1602         child = ldb_dn_new(child_str, dn->ldb, child_str);
1603
1604         ret = ldb_dn_add_child(dn, child);
1605
1606         talloc_free(child_str);
1607
1608         return ret;
1609 }
1610
1611 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1612 {
1613         unsigned int i;
1614
1615         if ( ! ldb_dn_validate(dn)) {
1616                 return false;
1617         }
1618
1619         if (dn->comp_num < num) {
1620                 return false;
1621         }
1622
1623         /* free components */
1624         for (i = dn->comp_num - num; i < dn->comp_num; i++) {
1625                 LDB_FREE(dn->components[i].name);
1626                 LDB_FREE(dn->components[i].value.data);
1627                 LDB_FREE(dn->components[i].cf_name);
1628                 LDB_FREE(dn->components[i].cf_value.data);
1629         }
1630
1631         dn->comp_num -= num;
1632
1633         if (dn->valid_case) {
1634                 for (i = 0; i < dn->comp_num; i++) {
1635                         LDB_FREE(dn->components[i].cf_name);
1636                         LDB_FREE(dn->components[i].cf_value.data);
1637                 }
1638                 dn->valid_case = false;
1639         }
1640
1641         LDB_FREE(dn->casefold);
1642         LDB_FREE(dn->linearized);
1643
1644         /* Wipe the ext_linearized DN,
1645          * the GUID and SID are almost certainly no longer valid */
1646         LDB_FREE(dn->ext_linearized);
1647         LDB_FREE(dn->ext_components);
1648         dn->ext_comp_num = 0;
1649
1650         return true;
1651 }
1652
1653 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1654 {
1655         unsigned int i, j;
1656
1657         if ( ! ldb_dn_validate(dn)) {
1658                 return false;
1659         }
1660
1661         if (dn->comp_num < num) {
1662                 return false;
1663         }
1664
1665         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1666                 if (i < num) {
1667                         LDB_FREE(dn->components[i].name);
1668                         LDB_FREE(dn->components[i].value.data);
1669                         LDB_FREE(dn->components[i].cf_name);
1670                         LDB_FREE(dn->components[i].cf_value.data);
1671                 }
1672                 dn->components[i] = dn->components[j];
1673         }
1674
1675         dn->comp_num -= num;
1676
1677         if (dn->valid_case) {
1678                 for (i = 0; i < dn->comp_num; i++) {
1679                         LDB_FREE(dn->components[i].cf_name);
1680                         LDB_FREE(dn->components[i].cf_value.data);
1681                 }
1682                 dn->valid_case = false;
1683         }
1684
1685         LDB_FREE(dn->casefold);
1686         LDB_FREE(dn->linearized);
1687
1688         /* Wipe the ext_linearized DN,
1689          * the GUID and SID are almost certainly no longer valid */
1690         LDB_FREE(dn->ext_linearized);
1691         LDB_FREE(dn->ext_components);
1692         dn->ext_comp_num = 0;
1693
1694         return true;
1695 }
1696
1697
1698 /* replace the components of a DN with those from another DN, without
1699  * touching the extended components
1700  *
1701  * return true if successful and false if not
1702  * if false is returned the dn may be marked invalid
1703  */
1704 bool ldb_dn_replace_components(struct ldb_dn *dn, struct ldb_dn *new_dn)
1705 {
1706         int i;
1707
1708         if ( ! ldb_dn_validate(dn) || ! ldb_dn_validate(new_dn)) {
1709                 return false;
1710         }
1711
1712         /* free components */
1713         for (i = 0; i < dn->comp_num; i++) {
1714                 LDB_FREE(dn->components[i].name);
1715                 LDB_FREE(dn->components[i].value.data);
1716                 LDB_FREE(dn->components[i].cf_name);
1717                 LDB_FREE(dn->components[i].cf_value.data);
1718         }
1719
1720         dn->components = talloc_realloc(dn,
1721                                         dn->components,
1722                                         struct ldb_dn_component,
1723                                         new_dn->comp_num);
1724         if (dn->components == NULL) {
1725                 ldb_dn_mark_invalid(dn);
1726                 return false;
1727         }
1728
1729         dn->comp_num = new_dn->comp_num;
1730         dn->valid_case = new_dn->valid_case;
1731
1732         for (i = 0; i < dn->comp_num; i++) {
1733                 dn->components[i] = ldb_dn_copy_component(dn->components, &new_dn->components[i]);
1734                 if (dn->components[i].name == NULL) {
1735                         ldb_dn_mark_invalid(dn);
1736                         return false;
1737                 }
1738         }
1739         if (new_dn->linearized == NULL) {
1740                 dn->linearized = NULL;
1741         } else {
1742                 dn->linearized = talloc_strdup(dn, new_dn->linearized);
1743                 if (dn->linearized == NULL) {
1744                         ldb_dn_mark_invalid(dn);
1745                         return false;
1746                 }
1747         }
1748
1749         return true;
1750 }
1751
1752
1753 struct ldb_dn *ldb_dn_get_parent(TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
1754 {
1755         struct ldb_dn *new_dn;
1756
1757         new_dn = ldb_dn_copy(mem_ctx, dn);
1758         if ( !new_dn ) {
1759                 return NULL;
1760         }
1761
1762         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1763                 talloc_free(new_dn);
1764                 return NULL;
1765         }
1766
1767         return new_dn;
1768 }
1769
1770 /* Create a 'canonical name' string from a DN:
1771
1772    ie dc=samba,dc=org -> samba.org/
1773       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1774
1775    There are two formats,
1776    the EX format has the last '/' replaced with a newline (\n).
1777
1778 */
1779 static char *ldb_dn_canonical(TALLOC_CTX *mem_ctx, struct ldb_dn *dn, int ex_format) {
1780         unsigned int i;
1781         TALLOC_CTX *tmpctx;
1782         char *cracked = NULL;
1783         const char *format = (ex_format ? "\n" : "/" );
1784
1785         if ( ! ldb_dn_validate(dn)) {
1786                 return NULL;
1787         }
1788
1789         tmpctx = talloc_new(mem_ctx);
1790
1791         /* Walk backwards down the DN, grabbing 'dc' components at first */
1792         for (i = dn->comp_num - 1; i != (unsigned int) -1; i--) {
1793                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1794                         break;
1795                 }
1796                 if (cracked) {
1797                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1798                                                   ldb_dn_escape_value(tmpctx,
1799                                                         dn->components[i].value),
1800                                                   cracked);
1801                 } else {
1802                         cracked = ldb_dn_escape_value(tmpctx,
1803                                                         dn->components[i].value);
1804                 }
1805                 if (!cracked) {
1806                         goto done;
1807                 }
1808         }
1809
1810         /* Only domain components?  Finish here */
1811         if (i == (unsigned int) -1) {
1812                 cracked = talloc_strdup_append_buffer(cracked, format);
1813                 talloc_steal(mem_ctx, cracked);
1814                 goto done;
1815         }
1816
1817         /* Now walk backwards appending remaining components */
1818         for (; i > 0; i--) {
1819                 cracked = talloc_asprintf_append_buffer(cracked, "/%s",
1820                                                         ldb_dn_escape_value(tmpctx,
1821                                                         dn->components[i].value));
1822                 if (!cracked) {
1823                         goto done;
1824                 }
1825         }
1826
1827         /* Last one, possibly a newline for the 'ex' format */
1828         cracked = talloc_asprintf_append_buffer(cracked, "%s%s", format,
1829                                                 ldb_dn_escape_value(tmpctx,
1830                                                         dn->components[i].value));
1831
1832         talloc_steal(mem_ctx, cracked);
1833 done:
1834         talloc_free(tmpctx);
1835         return cracked;
1836 }
1837
1838 /* Wrapper functions for the above, for the two different string formats */
1839 char *ldb_dn_canonical_string(TALLOC_CTX *mem_ctx, struct ldb_dn *dn) {
1840         return ldb_dn_canonical(mem_ctx, dn, 0);
1841
1842 }
1843
1844 char *ldb_dn_canonical_ex_string(TALLOC_CTX *mem_ctx, struct ldb_dn *dn) {
1845         return ldb_dn_canonical(mem_ctx, dn, 1);
1846 }
1847
1848 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1849 {
1850         if ( ! ldb_dn_validate(dn)) {
1851                 return -1;
1852         }
1853         return dn->comp_num;
1854 }
1855
1856 int ldb_dn_get_extended_comp_num(struct ldb_dn *dn)
1857 {
1858         if ( ! ldb_dn_validate(dn)) {
1859                 return -1;
1860         }
1861         return dn->ext_comp_num;
1862 }
1863
1864 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1865 {
1866         if ( ! ldb_dn_validate(dn)) {
1867                 return NULL;
1868         }
1869         if (num >= dn->comp_num) return NULL;
1870         return dn->components[num].name;
1871 }
1872
1873 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn,
1874                                                 unsigned int num)
1875 {
1876         if ( ! ldb_dn_validate(dn)) {
1877                 return NULL;
1878         }
1879         if (num >= dn->comp_num) return NULL;
1880         return &dn->components[num].value;
1881 }
1882
1883 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1884 {
1885         if ( ! ldb_dn_validate(dn)) {
1886                 return NULL;
1887         }
1888         if (dn->comp_num == 0) return NULL;
1889         return dn->components[0].name;
1890 }
1891
1892 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1893 {
1894         if ( ! ldb_dn_validate(dn)) {
1895                 return NULL;
1896         }
1897         if (dn->comp_num == 0) return NULL;
1898         return &dn->components[0].value;
1899 }
1900
1901 int ldb_dn_set_component(struct ldb_dn *dn, int num,
1902                          const char *name, const struct ldb_val val)
1903 {
1904         char *n;
1905         struct ldb_val v;
1906
1907         if ( ! ldb_dn_validate(dn)) {
1908                 return LDB_ERR_OTHER;
1909         }
1910
1911         if (num >= dn->comp_num) {
1912                 return LDB_ERR_OTHER;
1913         }
1914
1915         if (num < 0) {
1916                 return LDB_ERR_OTHER;
1917         }
1918
1919         if (val.length > val.length + 1) {
1920                 return LDB_ERR_OTHER;
1921         }
1922
1923         n = talloc_strdup(dn, name);
1924         if ( ! n) {
1925                 return LDB_ERR_OTHER;
1926         }
1927
1928         v.length = val.length;
1929
1930         /*
1931          * This is like talloc_memdup(dn, v.data, v.length + 1), but
1932          * avoids the over-read
1933          */
1934         v.data = (uint8_t *)talloc_size(dn, v.length+1);
1935         if ( ! v.data) {
1936                 talloc_free(n);
1937                 return LDB_ERR_OTHER;
1938         }
1939         memcpy(v.data, val.data, val.length);
1940
1941         /*
1942          * Enforce NUL termination outside the stated length, as is
1943          * traditional in LDB
1944          */
1945         v.data[v.length] = '\0';
1946
1947         talloc_free(dn->components[num].name);
1948         talloc_free(dn->components[num].value.data);
1949         dn->components[num].name = n;
1950         dn->components[num].value = v;
1951
1952         if (dn->valid_case) {
1953                 unsigned int i;
1954                 for (i = 0; i < dn->comp_num; i++) {
1955                         LDB_FREE(dn->components[i].cf_name);
1956                         LDB_FREE(dn->components[i].cf_value.data);
1957                 }
1958                 dn->valid_case = false;
1959         }
1960         LDB_FREE(dn->casefold);
1961         LDB_FREE(dn->linearized);
1962
1963         /* Wipe the ext_linearized DN,
1964          * the GUID and SID are almost certainly no longer valid */
1965         LDB_FREE(dn->ext_linearized);
1966         LDB_FREE(dn->ext_components);
1967         dn->ext_comp_num = 0;
1968
1969         return LDB_SUCCESS;
1970 }
1971
1972 const struct ldb_val *ldb_dn_get_extended_component(struct ldb_dn *dn,
1973                                                     const char *name)
1974 {
1975         unsigned int i;
1976         if ( ! ldb_dn_validate(dn)) {
1977                 return NULL;
1978         }
1979         for (i=0; i < dn->ext_comp_num; i++) {
1980                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1981                         return &dn->ext_components[i].value;
1982                 }
1983         }
1984         return NULL;
1985 }
1986
1987 int ldb_dn_set_extended_component(struct ldb_dn *dn,
1988                                   const char *name, const struct ldb_val *val)
1989 {
1990         struct ldb_dn_ext_component *p;
1991         unsigned int i;
1992         struct ldb_val v2;
1993
1994         if ( ! ldb_dn_validate(dn)) {
1995                 return LDB_ERR_OTHER;
1996         }
1997
1998         if (!ldb_dn_extended_syntax_by_name(dn->ldb, name)) {
1999                 /* We don't know how to handle this type of thing */
2000                 return LDB_ERR_INVALID_DN_SYNTAX;
2001         }
2002
2003         for (i=0; i < dn->ext_comp_num; i++) {
2004                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
2005                         if (val) {
2006                                 dn->ext_components[i].value =
2007                                         ldb_val_dup(dn->ext_components, val);
2008
2009                                 dn->ext_components[i].name =
2010                                         talloc_strdup(dn->ext_components, name);
2011                                 if (!dn->ext_components[i].name ||
2012                                     !dn->ext_components[i].value.data) {
2013                                         ldb_dn_mark_invalid(dn);
2014                                         return LDB_ERR_OPERATIONS_ERROR;
2015                                 }
2016                         } else {
2017                                 if (i != (dn->ext_comp_num - 1)) {
2018                                         memmove(&dn->ext_components[i],
2019                                                 &dn->ext_components[i+1],
2020                                                 ((dn->ext_comp_num-1) - i) *
2021                                                   sizeof(*dn->ext_components));
2022                                 }
2023                                 dn->ext_comp_num--;
2024
2025                                 dn->ext_components = talloc_realloc(dn,
2026                                                    dn->ext_components,
2027                                                    struct ldb_dn_ext_component,
2028                                                    dn->ext_comp_num);
2029                                 if (!dn->ext_components) {
2030                                         ldb_dn_mark_invalid(dn);
2031                                         return LDB_ERR_OPERATIONS_ERROR;
2032                                 }
2033                         }
2034                         LDB_FREE(dn->ext_linearized);
2035
2036                         return LDB_SUCCESS;
2037                 }
2038         }
2039
2040         if (val == NULL) {
2041                 /* removing a value that doesn't exist is not an error */
2042                 return LDB_SUCCESS;
2043         }
2044
2045         v2 = *val;
2046
2047         p = dn->ext_components
2048                 = talloc_realloc(dn,
2049                                  dn->ext_components,
2050                                  struct ldb_dn_ext_component,
2051                                  dn->ext_comp_num + 1);
2052         if (!dn->ext_components) {
2053                 ldb_dn_mark_invalid(dn);
2054                 return LDB_ERR_OPERATIONS_ERROR;
2055         }
2056
2057         p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, &v2);
2058         p[dn->ext_comp_num].name = talloc_strdup(p, name);
2059
2060         if (!dn->ext_components[i].name || !dn->ext_components[i].value.data) {
2061                 ldb_dn_mark_invalid(dn);
2062                 return LDB_ERR_OPERATIONS_ERROR;
2063         }
2064         dn->ext_components = p;
2065         dn->ext_comp_num++;
2066
2067         LDB_FREE(dn->ext_linearized);
2068
2069         return LDB_SUCCESS;
2070 }
2071
2072 void ldb_dn_remove_extended_components(struct ldb_dn *dn)
2073 {
2074         LDB_FREE(dn->ext_linearized);
2075         LDB_FREE(dn->ext_components);
2076         dn->ext_comp_num = 0;
2077 }
2078
2079 bool ldb_dn_is_valid(struct ldb_dn *dn)
2080 {
2081         if ( ! dn) return false;
2082         return ! dn->invalid;
2083 }
2084
2085 bool ldb_dn_is_special(struct ldb_dn *dn)
2086 {
2087         if ( ! dn || dn->invalid) return false;
2088         return dn->special;
2089 }
2090
2091 bool ldb_dn_has_extended(struct ldb_dn *dn)
2092 {
2093         if ( ! dn || dn->invalid) return false;
2094         if (dn->ext_linearized && (dn->ext_linearized[0] == '<')) return true;
2095         return dn->ext_comp_num != 0;
2096 }
2097
2098 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
2099 {
2100         if ( ! dn || dn->invalid) return false;
2101         return ! strcmp(dn->linearized, check);
2102 }
2103
2104 bool ldb_dn_is_null(struct ldb_dn *dn)
2105 {
2106         if ( ! dn || dn->invalid) return false;
2107         if (ldb_dn_has_extended(dn)) return false;
2108         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
2109         return false;
2110 }
2111
2112 /*
2113   this updates dn->components, taking the components from ref_dn.
2114   This is used by code that wants to update the DN path of a DN
2115   while not impacting on the extended DN components
2116  */
2117 int ldb_dn_update_components(struct ldb_dn *dn, const struct ldb_dn *ref_dn)
2118 {
2119         dn->components = talloc_realloc(dn, dn->components,
2120                                         struct ldb_dn_component, ref_dn->comp_num);
2121         if (!dn->components) {
2122                 return LDB_ERR_OPERATIONS_ERROR;
2123         }
2124         memcpy(dn->components, ref_dn->components,
2125                sizeof(struct ldb_dn_component)*ref_dn->comp_num);
2126         dn->comp_num = ref_dn->comp_num;
2127
2128         LDB_FREE(dn->casefold);
2129         LDB_FREE(dn->linearized);
2130         LDB_FREE(dn->ext_linearized);
2131
2132         return LDB_SUCCESS;
2133 }
2134
2135 /*
2136   minimise a DN. The caller must pass in a validated DN.
2137
2138   If the DN has an extended component then only the first extended
2139   component is kept, the DN string is stripped.
2140
2141   The existing dn is modified
2142  */
2143 bool ldb_dn_minimise(struct ldb_dn *dn)
2144 {
2145         unsigned int i;
2146
2147         if (!ldb_dn_validate(dn)) {
2148                 return false;
2149         }
2150         if (dn->ext_comp_num == 0) {
2151                 return true;
2152         }
2153
2154         /* free components */
2155         for (i = 0; i < dn->comp_num; i++) {
2156                 LDB_FREE(dn->components[i].name);
2157                 LDB_FREE(dn->components[i].value.data);
2158                 LDB_FREE(dn->components[i].cf_name);
2159                 LDB_FREE(dn->components[i].cf_value.data);
2160         }
2161         dn->comp_num = 0;
2162         dn->valid_case = false;
2163
2164         LDB_FREE(dn->casefold);
2165         LDB_FREE(dn->linearized);
2166
2167         /* note that we don't free dn->components as this there are
2168          * several places in ldb_dn.c that rely on it being non-NULL
2169          * for an exploded DN
2170          */
2171
2172         for (i = 1; i < dn->ext_comp_num; i++) {
2173                 LDB_FREE(dn->ext_components[i].name);
2174                 LDB_FREE(dn->ext_components[i].value.data);
2175         }
2176         dn->ext_comp_num = 1;
2177
2178         dn->ext_components = talloc_realloc(dn, dn->ext_components, struct ldb_dn_ext_component, 1);
2179         if (dn->ext_components == NULL) {
2180                 ldb_dn_mark_invalid(dn);
2181                 return false;
2182         }
2183
2184         LDB_FREE(dn->ext_linearized);
2185
2186         return true;
2187 }
2188
2189 struct ldb_context *ldb_dn_get_ldb_context(struct ldb_dn *dn)
2190 {
2191         return dn->ldb;
2192 }