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